Математические методы теории классификации

Размещено на http://www.allbest.ru/

1

1

Научный журнал КубГАУ, №95(01), 2014 года

Математические методы теории классификации

1. Введение. Основные понятия

Термин «классификация» имеет несколько основных смысла. Во-первых, это система классов. Во-вторых, это действие, связанное с системой классов. Согласно [1, с.6] «термином «классификация» обозначают, по крайней мере, три разные вещи: процедуру построения классификации (выделение классов - А.О.), построенную классификацию (систему выделенных классов - А.О.) и процедуру ее использования (например, правила отнесения вновь поступающего объекта к одному из ранее выделенных классов -А.О.)» Выделим естественную триаду: построение классификаций - их изучение - и применение, в соответствии с которой упорядочим анализ задач классификации.

Математическая теория классификации - обширная область прикладной статистики и эконометрики [2, 3]. Какие научные исследования относить к этой теории? Исходя из потребностей специалиста, применяющего математические методы классификации, целесообразно принять, что сюда входят исследования, во-первых, отнесенные самими авторами к этой теории; во вторых, связанные с ней общностью тематики, хотя бы их авторы и не упоминали термин «классификация». Это предполагает сложную внутреннюю структуру рассматриваемой научной области.

Следует иметь в виду, что в литературе наряду с термином «классификация» в близких смыслах используются термины «группировка», «распознавание образов», «диагностика», «дискриминация», «сортировка», «типология», «таксономия» и др. Терминологический разнобой связан прежде всего с традициями научных кланов, к которым относятся авторы публикаций, а также с внутренним делением самой теории классификации.

В научных исследованиях по современной теории классификации можно выделить два относительно самостоятельных направления. Одно из них опирается на опыт таких наук, как биология, география, геология, и таких прикладных областей, как ведение классификаторов продукции и библиотечное дело. Типичные объекты рассмотрения - классификация химических элементов (таблица Д.И. Менделеева), биологическая систематика, универсальная десятичная классификация публикаций (УДК), классификатор товаров на основе штрих-кодов. Опыт этого направления с гносеологических позиций обобщен в [1], соответствующий математический аппарат приведен в [4, 5].

Другое направление опирается на опыт технических исследований, экономики, маркетинговых исследований, социологии, медицины. Типичные задачи - техническая и медицинская диагностика. А также, например, разбиение на группы отраслей промышленности, тесно связанных между собой, выделение групп однородной продукции. Обычно используются такие термины, как «кластер-анализ», «распознавание образов» или «дискриминантный анализ». [6]. Краткое осмысление опыта и современного состояния этого направления дано в [7].

Это направление обычно опирается на математические модели; для проведения расчетов интенсивно используется ЭВМ. Однако относить его к математике столь же нецелесообразно, как астрономию или квантовую механику. Рассматриваемые математические модели можно и нужно изучать на формальном уровне, и такие исследования проводятся. Но направление в целом сконцентрировано на решении конкретных задач прикладных областей и вносит вклад в технические или экономические науки, медицину, социологию, но, как правило, математики не рассматривают полученные научные результаты как вклад в математику.

В 60-х годах XX века внутри прикладной статистики (в понимании этой науки, раскрытом в [2, 8, 9]) достаточно четко оформилась область, посвященная методам классификации. Несколько модифицируя формулировки М. Дж. Кендалла и А. Стьюарта 1966 г. (см. русский перевод [10, с.437]), в теории классификации выделим три подобласти: кластеризация (кластер-анализ) и группировка, статистический анализ классификаций, дискриминация (дискриминантный анализ). Опишем эти подобласти.

При кластеризации и группировке целью является выявление и выделение классов. Синонимы: построение классификации, распознавание образов без учителя, автоматическая классификация без учителя, типология, таксономия и др. Задача кластер-анализа состоит в выяснении по эмпирическим данным, насколько элементы «группируются» или распадаются на изолированные «скопления», «кластеры» (от cluster (англ.) - гроздь, скопление). Иными словами, задача - выявление естественного разбиения на классы, свободного от субъективизма исследователя, а цель - выделение групп однородных объектов, сходных между собой, при резком отличии этих групп друг от друга.

При группировке, наоборот, «мы хотим разбить элементы на группы независимо от того, естественны ли границы разбиения или нет» [10, с.437]. Цель по-прежнему состоит в выявлении групп однородных объектов, сходных между собой (как в кластер-анализе), однако «соседние» группы могут не иметь резких различий (в отличие от кластер-анализа). Границы между группами условны, не являются естественными, зависят от субъективизма исследователя. Аналогично при лесоустройстве проведение просек (границ участков) зависит от специалистов лесного ведомства, а не от свойств леса.

Задачи кластеризации и группировки принципиально различны, хотя для их решения могут применяться одни и те же алгоритмы. Важная для практической деятельности проблема состоит в том, чтобы понять, разрешима ли задача кластер-анализа для конкретных данных или возможна только их группировка, поскольку совокупность объектов достаточно однородна и не разбивается на резко разделяющиеся между собой кластеры.

Как правило, в математических задачах кластеризации и группировки основное - выбор метрики, расстояния между объектами, меры близости, сходства, различия. Хорошо известно, что для любого заданного разбиения объектов на группы и любого числа > 0 можно указать метрику такую, что расстояния между объектами из одной группы будут меньше , а между объектами из разных групп - больше 1/. Тогда любой разумный алгоритм кластеризации даст именно заданное разбиение. Поэтому весьма важен выбор метрики, адекватной решаемой прикладной задаче. Некоторые подходы к выбору расстояния в задачах классификации рассмотрены в обзоре [11].

В дискриминантном анализе классы предполагаются заданными - плотностями вероятностей или обучающими выборками. Задача состоит в том, чтобы вновь поступающий объект отнести в один из этих классов. У понятия «дискриминация» имеется много синонимов: диагностика, распознавание образов с учителем, автоматическая классификация с учителем, статистическая классификация и т.д. Для построения системы диагностических классов используют разнообразные методы кластерного анализа и группировки объектов.

Наименее известен второй член триады (отсутствующий у Кендалла и Стьюарта [10]) - изучение отношений эквивалентности, полученных в результате построения системы диагностических классов. Например, эксперты разбивают объекты экспертизы на группы схожих между собой. Ответ каждого из них - классификация (т.е. разбиение на классы исходного множества объектов экспертизы, в другой терминологии - отношение эквивалентности). Как построить итоговое мнение комиссии экспертов? Статистический анализ отношений эквивалентности - часть статистики бинарных отношений и тем самым - статистики объектов нечисловой природы [2, 12]. Помимо общих результатов этой области прикладной статистики, представляют интерес частные результаты, полученные специально для отношений эквивалентности [13].

Диагностика в узком смысле слова (процедура использования классификации, т.е. отнесения вновь поступающего объекта к одному из выделенных ранее классов) - предмет дискриминантного анализа. Отметим, что с точки зрения статистики объектов нечисловой природы дискриминантный анализ является частным случаем общей схемы регрессионного анализа, соответствующим ситуации, когда зависимая переменная принимает конечное число значений, а именно - номера классов, а вместо квадрата разности стоит функция потерь от неправильной классификации [2, 12]. Однако есть ряд специфических постановок, выделяющих задачи диагностики среди всех регрессионных задач.

2. Основные постановки задач построения классификаций

Процедуры построения диагностических правил делятся на вероятностные и детерминированные. К первым относятся задачи расщепления смесей [15-17]. В них предполагается, что распределение вновь поступающего случайного элемента является смесью вероятностных законов, соответствующих диагностическим классам. Как и при выборе степени полинома в регрессии [2, 18], при анализе данных о веществах и материалах встает вопрос оценки числа элементов смеси, т.е. числа диагностических классов. Нами изучены результаты применения обычно рекомендуемого критерия Уилкса для оценки числа элементов смеси. Оказалось [19], что оценка с помощью критерия Уилкса не является состоятельной, асимптотическое распределение этой оценки - геометрическое, как и в случае задач восстановления зависимости [2, 18]. Итак, продемонстрирована несостоятельность обычно используемых оценок. Для получения состоятельных оценок достаточно связать уровень значимости в критерии Уилкса с объемом выборки, как это предложено в работах [20, 21] для задач регрессии.

В рамках задач расщепления смесей важно обратить внимание на одно распространенное заблуждение. Иногда рекомендуют сначала построить систему диагностических классов, а потом в каждом диагностическом классе отдельно проводить регрессионный анализ (в классическом смысле) или применять иные методы многомерного статистического анализа. Однако необходимо подчеркнуть, что при этом нельзя опираться на вероятностную модель многомерного нормального распределения, так как распределения результатов наблюдений, попавших в определенный кластер, будут отнюдь не нормальным, а усеченным нормальным (усечение определяется границами кластера), как это подробнее разъяснено в статье [19].

Перейдем к детерминированному случаю. Как уже отмечалось, задачи построения системы диагностических классов целесообразно разбить на два типа: с четко разделенными кластерами (задачи кластер-анализа) и с условными границами, непрерывно переходящими друг в друга классами (задачи группировки). Такое деление полезно, хотя в обоих случаях могут применяться одинаковые алгоритмы [22 - 25].

Сколько существует алгоритмов построения системы диагностических правил? Иногда называют то или иное число. На самом же деле их бесконечно много.

Действительно, часто применяется т.н. агломеративный иерархический алгоритм «Дендрограмма», в котором вначале все элементы рассматриваются как отдельные кластеры, а затем на каждом шагу объединяются два наиболее близких кластера. Для работы «Дендрограммы» необходимо задать правило вычисления расстояния между кластерами. Оно вычисляется через расстояние d(x,у) между элементами х и у. Поскольку d^a(x,y) при 0 < a < 1 также расстояние, то каждому значению степени а соответствует свой алгоритм.

Расстояние между кластерами рассчитывается как средняя связь (отсюда и еще название - алгоритм средней связи), т.е. как среднее арифметическое расстояний между парами объектов, один из которых входит в первый кластер, а другой - во второй. После ряда шагов все объекты объединяются вместе, и результат работы алгоритма представляет собой дерево последовательных объединений (в терминах теории графов), т.н. «Дендрограмму». Из нее можно выделить кластеры разными способами. Один подход - исходя из заданного числа кластеров. Другой - из соображений предметной области. Третий - исходя из устойчивости (если разбиение долго не менялось при возрастании порога объединения - значит, оно отражает реальность). И т.д.

Каким из бесконечного (континуального) семейство алгоритмов средней связи пользоваться при обработке данных? Дело осложняется тем, что практически в любом пространстве мер близости различных видов существует весьма много [11]. Именно в связи с обсуждаемой проблемой следует указать [26] на принципиальное различие между кластер-анализом и задачами группировки.

Если классы реальны (в соответствии с определением, данным в [19]), естественны, существуют на самом деле, четко отделены друг от друга, то любой алгоритм кластер-анализа их выделит. Следовательно, в качестве критерия естественности классификации следует рассматривать устойчивость относительно выбора алгоритма кластер-анализа.

Проверить устойчивость можно, применив к данным несколько подходов, например, столь непохожие алгоритмы, как «ближнего соседа» и «дальнего соседа». Они отличаются от алгоритма средней связи способом введения расстояния между кластерами. В алгоритме «ближнего соседа» расстоянием между кластерами называется минимальное из расстояний между парами объектов, один из которых входит в первый кластер, а другой - во второй. А в алгоритме дальнего соседа расстоянием между кластерами называется максимальное из расстояний между парами объектов, один из которых входит в первый кластер, а другой - во второй.

Если полученные результаты содержательно близки, то они адекватны действительности. В противном случае следует предположить, что естественной классификации не существует, задача кластер-анализа не имеет решения, и можно проводить только группировку.

В более общем подходе агломеративные иерархические алгоритмы типа «Дендрограмма» при различных значениях параметра а, 0 < a < 1, применяются для обработки одних и тех же реальных данных. Если при всех а получается практически одинаковое разбиение элементов на кластеры, т.е. результат работы алгоритма устойчив по отношению к изменению а (в смысле общей схемы устойчивости, предложенной в [27]), то имеем «естественную» классификацию. В противном случае результат зависит от субъективно выбранного исследователем параметра а, т.е. задача кластер-анализа неразрешима (предполагаем, что выбор а нельзя специально обосновать). Задача группировки в этой ситуации имеет много решений. Из них можно выбрать одно по дополнительным критериям.

Следовательно, получаем эвристический критерий: если решение задачи кластер-анализа существует, то оно находится с помощью любого алгоритма. Целесообразно использовать наиболее простой. Так, для классификации социально-психологических характеристик способных к математике школьников [28] мы использовали алгоритм [29]. На программирование и счет на ЭВМ ушло около полугода. Через несколько лет с помощью алгоритмов «ближайшего соседа» и «дальнего соседа» кластер-анализ был проведен вручную за 1,5 часа. С содержательной точки зрения, полученные разбиения отличались мало Фактически анализировались иерархические деревья разбиений, поскольку все три алгоритма включали одномерные параметры, смысл которых -- расстояние между объединяемыми на очередном шагу кластерами.. Поэтому есть основания считать, что с помощью этих алгоритмов действительно выявлена «реальная» структура данных.

3. Проблема поиска естественной классификации

Широко обсуждается проблема поиска естественной классификации (в отличие от искусственной). Приведенные в [1, 7, 30] высказывания дают представление о больших расхождениях в понимании «естественной классификации». Констатируем, что этот термин является нечетким (в смысле математической теории нечеткости [31, 32]), как, впрочем, и многие другие термины, как научно-технические, так и используемые в обыденном языке. В книге [33] и статье [32] подробно обоснована нечеткость естественного языка и тот факт, что «мы мыслим нечетко». Однако это не слишком мешает решать производственные и жизненные проблемы. Кажущееся рациональным требование выработать сначала строгие определения, а потом развивать науку - невыполнимо. Следовать ему - значит отвлекать силы от реальных задач. При системном подходе (в интерпретации монографии [4]) к теории классификации становится ясно, что строгие определения можно надеяться получить на последних этапах построения теории. Мы же сейчас находимся в начале пути. Поэтому, не давая здесь определения понятию «естественная классификация», обсудим, как проверить на «естественность» классификацию (набор диагностических классов), полученную расчетным путем.

Можно выделить два критерия «естественности», по поводу которых имеется относительное согласие:

А. Естественная классификация должна быть реальной, соответствующей действительному миру, лишенной внесенного исследователем субъективизма;

Б. Естественная классификация должна быть важной или с научной точки зрения (давать возможность прогноза, предсказания новых свойств, сжатия информации и т.д.), или с практической.

Пусть классификация проводится на основе информации об объектах, представленной в виде матрицы «объект-признак» или матрицы попарных расстояний (мер близости или различия). Пусть алгоритм классификации дал разбиение на кластеры. Как можно получить доводы в пользу естественности этой классификации? Например, уверенность в том, что она - закон природы, может появиться только в результате длительного ее изучения и практического применения. Это соображение относится и к другим перечисленным в [1] критериев, а также к критерию Б (важности). Сосредоточимся на критерии А (реальности).

Понятие «реальности» кластера требует специального обсуждения (оно начато нами в работе [19]). Рассмотрим существо различий между понятиями «классификация» и «группировка». Пусть, к примеру, необходимо деревья, растущие в определенной местности, разбить на группы находящихся рядом друг с другом. Ясна интуитивная разница между несколькими отдельными рощами, далеко отстоящими друг от друга и разделенными полями, и сплошным лесом, разбитым просеками на квадраты с целью лесоустройства. Однако формально определить эту разницу столь же сложно, как определить понятие «куча зерен», чем занимались еще в Древней Греции [32].

Переформулируем сказанное в терминах «кластер-анализа» и «методов группировки». Выделенные с помощью первого подхода кластеры реальны, а потому могут рассматриваться как кандидаты в «естественные». Группировка дает «искусственные» классы, которые не могут быть «естественными».

Выборку из унимодального распределения можно, видимо, рассматривать как «естественный», «реальный» кластер. Применим к ней какой-либо алгоритм классификации («Форель», «ближнего соседа» и т.п. [34 - 37]). Он даст разбиение на классы, которые, разумеется, не являются «реальными», поскольку отражают прежде всего свойства алгоритма, а не исходных данных. Как отличить такую ситуацию от противоположной, когда имеются реальные кластеры и алгоритм классификации более или менее точно их выделяет? Как известно, «критерий истины - практика», но слишком много времени необходимо для применения подобного критерия. Поэтому представляет интерес критерий, оценивающий «реальность» выделяемых с помощью алгоритма классификации кластеров одновременно с его применением.

Такой показатель существует - это критерий устойчивости. Общая схема формулирования и изучения проблем устойчивости выводов в математических моделях реальных явлений и процессов предложена в [27]. В частности, поскольку значения признаков всегда измеряются с погрешностями, то «реальное» разбиение должно быть устойчиво (т.е. не меняться или меняться слабо) при малых отклонениях исходных данных. Алгоритмов классификации существует бесконечно много, и «реальное» разбиение должно быть устойчиво по отношению к переходу к другому алгоритму. Другими словами, если «реальное» разбиение на диагностические классы возможно, то оно находится с помощью любого алгоритма автоматической классификация. Следовательно, критерием естественности классификации может служить совпадение результатов работы двух достаточно различающихся алгоритмов, например «ближнего соседа» и «дальнего соседа».

Нами рассмотрены Программная реализация осуществлена в разработанных под научным руководством автора пакетах ППАНД и ДИСАН [38]. два типа «глобальных» критериев «естественности классификации», касающихся разбиения в целом. «Локальные» критерии относятся к отдельным кластерам. Простейшая постановка такова: достаточно ли однородны два кластера (две совокупности) для их объединения? Если объединение возможно, то кластеры не являются «естественными». Преимущество этой постановки в том, что она допускает применение статистических критериев однородности двух выборок.

В одномерном случае (классификация по одному признаку) разработано большое число подобных критериев -- Смирнова, омега-квадрат (Лемана-Розенблатта), Вилкоксона, Ван-дер-Вардена, Стьюдента и др. [39 - 42]. Имеются критерии и для многомерных данных [26, 43]. Для одного из видов объектов нечисловой природы [12] - люсианов - статистические методы выделения «реальных» кластеров развиты в [12, 44].

Как и для иных методов прикладной статистики, свойства алгоритмов кластер-анализа необходимо изучать на вероятностных моделях [17]. Это требование относится и к условиям естественного объединения двух кластеров. Для многомерных кластеров робастная процедура проверки допустимости объединения предложена в [45], непараметрическая - в [26].

Вероятностные постановки нужно применять, в частности, при перенесении результатов, полученных по выборке, на генеральную совокупность [46]. Вероятностная теория кластер-анализа и методов группировки различна для исходных данных в виде таблиц «объект признак» и в виде матриц сходства. Для первых параметрическая теория - это «расщепление смесей» [15-17]. Непараметрическая теория основана на непараметрических оценках плотностей вероятностей и их мод [14, 15, 30, 48]. Основные результаты, связанные с непараметрическими оценками плотностей в произвольных пространствах, обсуждаются ниже.

Если исходные данные - матрица сходства ||d(x,y)||, то необходимо признать, что законченной вероятностно-статистической теории пока нет. Подходы к ее построению обсуждались в [19]. Рассмотрим модель, позволяющую разработать расчетные методы. Предположим, что результаты наблюдений можно рассматривать как выборку из некоторого распределения с монотонно убывающей плотностью при увеличении расстояния от некоторого центра. Примененный к подобным данным какой-либо алгоритм кластер-анализа порождает некоторое разбиение. Ясно, что оно - чисто формальное, поскольку выделенным таксонам (кластерам) не соответствуют никакие «реальные» классы. Другими словами, задача кластер-анализа не имеет решения, а алгоритм дает лишь группировку. При обработке реальных данных вид плотности неизвестен. Проблема состоит в том, чтобы определить результат работы алгоритма (реальные кластеры или формальные группы) Подробнее см. [19]..

Частный случай этой проблемы - проверка обоснованности объединения двух кластеров, которые мы рассматриваем как два множества объектов, а именно, {a₁, a₂,…, a_k} и {b₁, b₂,…, b_m}. Пусть, например, используется алгоритм типа «Дендрограммы». Ряд авторов высказывали следующую идею. Пусть есть две совокупности мер близости: внутри кластеров d(a_i,a_j), 1<i<j<k, d(b,b), 1<<<m и между кластерами d(a_i,b), 1<i<k, 1<<m. Эти совокупности предлагается рассматривать как независимые выборки и проверять гипотезу о совпадении их функций распределения. Если гипотеза не отвергается, объединение кластеров считается обоснованным; в противном случае - объединять нельзя, алгоритм прекращает работу. В [49] для проверки однородности использовался критерий Вилкоксона U, а в [50] - критерий типа ² (Лемана-Розенблатта).

В рассматриваемом подходе есть две некорректности. Во-первых, меры близости не являются независимыми случайными величинами. Во-вторых, не учитывается, что объединяются не произвольные заранее фиксированные кластеры, а полученные в результате работы некоторого алгоритма, и их состав оказывается случайным [19, разд. 4]. От первой из этих некорректностей можно частично избавиться. А именно, в [51] в предположении независимости и одинаковой распределенности элементов произвольного пространства a₁, a₂,…, a_k, b₁, b₂,…, b_m установлено, что при достаточно большом числе элементов кластеров зависимость мер близости не влияет на распределение статистики Вилкоксона U (сумма рангов элементов первой совокупности мер близости в объединении двух описанных выше совокупностей мер близости). На основе этой теоремы разработан алгоритм проверки статистической гипотезы, согласно которой объединение двух кластеров образует однородную совокупность. Если величина U слишком мала, статистическая гипотеза однородности (т.е. обоснованности объединения двух кластеров) отклоняется (на заданном уровне значимости), и возможность объединения отбрасывается (подробнее см. в [30]).

Что касается глобальных критериев, то для изучения устойчивости по отношению к малым отклонениям исходных данных естественно использовать метод статистических испытаний и проводить расчеты по «возмущенным» данным. Некоторые теоретические утверждения, касающиеся влияния «возмущений» на кластеры различных типов, получены в статье [19].

Итак, одна из основных проблем при построении классификации - проверка «реальности» кластера, его объективного существования независимо от расчетов исследователя. Эта проблема давно обсуждается специалистами различных областей (см., например, [52]). Отметим, что идея устойчивости как критерия «реальности» иногда реализуется неадекватно. Так, в статье [53] для алгоритмов типа «Дендрограмма» предлагается выделять разбиения, которым соответствуют наибольшие приращения расстояния между кластерами между очередными объединениями кластеров. Для данных [28] это предложение не дало полезных результатов - были получены различные разбиения: три алгоритма - три разбиения. И с теоретической точки зрения предложение [53] несостоятельно, что нетрудно показать.

Действительно, рассмотрим алгоритм «ближнего соседа», использующий меру близости d(x,у), и однопараметрическое семейство алгоритмов с мерой близости d^a(x,y), а>0, также являющихся алгоритмами «ближнего соседа». Тогда дендрограммы, полученные с помощью этих алгоритмов, совпадают при всех a, поскольку при их реализации происходит лишь сравнение мер близости между объектами. Другими словами, дендрограмма, полученная с помощью алгоритма «ближнего соседа», является адекватной в порядковой шкале (измерения меры близости d(x,у)), т.е. сохраняется при любом строго возрастающем преобразовании этой меры [27]. Однако выделенные по методу [53] «устойчивые разбиения» меняются. В частности, при достаточно большом а «наиболее объективным» по [53] будет, как нетрудно показать, разбиение на два кластера! Таким образом, разбиение, выдвинутое в [53] как «устойчивое», на самом деле оказывается весьма неустойчивым.

Несколько слов о вычислительной сходимости алгоритмов кластер-анализа, другими словами, об устойчивости кластеров в процессе вычислений. Алгоритмы кластер-анализа и группировки зачастую являются итерационными. Например, формулируется правило улучшения шаг за шагом решения задачи кластер-анализа, но момент остановки вычислений не обсуждается. Примером является известный алгоритм «Форель» [22], в котором улучшается положение центра кластера. В этом алгоритме на каждом шаге строится шар определенного заранее радиуса, выделяются элементы кластеризуемой совокупности, попадающие в этот шар, и новый центр кластера строится как центр тяжести выделенных элементов. При анализе алгоритма «Форель» возникает проблема: завершится ли процесс улучшения центра кластера через конечное число шагов или же он может быть бесконечным. Она получила название «проблема остановки». Для широкого класса так называемых «эталонных алгоритмов» проблема остановки решена: процесс улучшения остановится через конечное число шагов [19].

Отметим, что алгоритмы кластер-анализа могут быть модифицированы разнообразными способами. Например, описывая алгоритм «Форель» в стиле статистики объектов нечисловой природы [12], заметим, что вычисление центра тяжести для совокупности многомерных точек - это нахождение эмпирического среднего для меры близости, равной квадрату евклидова расстояния. Если взять более естественную меру близости - само евклидово расстояние, то получим эталонный алгоритм кластер-анализа «Медиана», отличающийся от «Форели» тем, что новый центр строится не с помощью средних арифметических координат элементов, попавших в кластер, а с помощью медиан.

Проблема остановки возникает не только при построении системы классов. Она принципиально важна и при оценивании параметров вероятностных распределений методом максимального правдоподобия. Обычно не представляет большого труда выписать систему уравнений максимального правдоподобия и предложить решать ее каким-либо численным методом. Однако когда остановиться, сколько итераций сделать, какая точность оценивания будет при этом достигнута? Общий ответ, видимо, невозможно найти, но обычно нет ответа и для конкретных семейств. Именно поэтому не рекомендуем решать системы уравнений максимального правдоподобия, предлагая вместо них одношаговые оценки [54]. Эти оценки задаются конечными формулами, но асимптотически столь же хороши, как и оценки максимального правдоподобия.

Исходными данными для решения задач кластер-анализа могут быть не только матрицы попарных мер близости (мер различия, расстояний), но и матрицы типа «объект признак». Есть двойственность: классифицироваться могут как объекты, так и признаки. Меры близости между признаками могут быть рассчитаны на основе коэффициентов корреляции [55]. Один из первых методов кластер-анализа - метод корреляционных плеяд [56] - предназначен именно для классификации признаков.

Сводке, анализу и сопоставлению различных методов кластер-анализа посвящены монографии [57-60]. Выделим разрабатываемую в ИПУ РАН глубокую теорию «классификационного анализа данных» [61 - 64], имеющую разнообразные применения [65, 66]. Интересные подходы к типологии и классификации разработаны в социологических исследованиях [67 - 69]. Оригинальные методы классификации разработаны и с успехом применены А.Т. Фоменко для статистического анализа исторических текстов [70]. Микроагрегирование оказалось полезным для защиты конфиденциальных данных [71]. Отметим алгоритмы снижения размерности (многомерного шкалирования, визуализации), позволяющие придать наглядность процедурам выделения кластеров [72 - 76].

Ряд важных результатов в теории и практике классификации достигнут без интенсивного применения математических методов [77, 78]. Однако в настоящей статье ограничиваемся рассмотрением только математических методов классификации.

4. Основные постановки задач дискриминантного анализа

Перейдем к этапу применения диагностических правил, когда классы, к одному из которых нужно отнести вновь поступающий объект, уже выделены. Разработано большое количество методов принятия диагностических решений [79 - 83]. Одни из них излагаются согласно традициям математической статистики [43, 84 - 87]. Среди них выделим работы [88 - 92], развивающие дискриминантный анализ в ситуации, когда число неизвестных параметров растет пропорционально объему выборки (асимптотика растущей размерности А.Н. Колмогорова).

Другие авторы предпочитают использовать термин «распознавание образов» [93 - 98]. С точки зрения статистики объектов нечисловой природы речь идет о восстановлении зависимости, когда функция принимает номинальные значения - номера классов [12, 99]. Специфика прикладных областей отражается на процедурах диагностики [100 - 102].

Для решения задач диагностики в вероятностно-статистической постановке используют два подхода - параметрический и непараметрический. Первый из них обычно основан на использовании того или иного индекса (рейтинга) и сравнения его с порогом. Индекс может быть построен по статистическим данным, например, как в классическом линейном дискриминантном анализе Фишера [103]. Часто индекс представляет собой линейную функцию от характеристик, выбранных специалистами предметной области, коэффициенты которой подбирают эмпирически. Непараметрический подход связан с леммой Неймана-Пирсона в математической статистике и с теорией статистических решений. Он опирается на использование непараметрических оценок плотностей распределений вероятностей, описывающих диагностические классы.

Обсудим ситуацию подробнее. Методы диагностики, как и статистические методы в целом, делятся на параметрические [104, 105] и непараметрические [106, 107]. Первые основаны на предположении, что классы описываются распределениями из некоторых параметрических семейств. Обычно рассматривают многомерные нормальные распределения, при этом зачастую без обоснования принимают гипотезу о том, что ковариационные матрицы для различных классов совпадают. Именно в таких предположениях сформулирован классический дискриминантный анализ Фишера. Как известно, обычно не только нет теоретических оснований считать, что наблюдения извлечены из нормального распределения, но и проверка статистических гипотез согласия с нормальным законом дает отрицательный результат [2, 3]. Известно также, что по выборкам, объем которых не превосходит 50, нельзя сделать обоснованный вывод о принадлежности к нормальному закону [108].

Поэтому более корректными, чем параметрические, являются непараметрические методы диагностики. Исходная идея таких методов основана на лемме Неймана-Пирсона, входящей в стандартный курс математической статистики. Согласно этой лемме оптимальное решение об отнесении вновь поступающего объекта (сигнала, наблюдения и др.) к одному из двух классов принимается на основе отношения плотностей f(x)/g(x), где f(x) - плотность распределения, соответствующая первому классу, а g(x) - плотность распределения, соответствующая второму классу.

Если плотности распределения неизвестны, то применяют их непараметрические оценки, построенные по обучающим выборкам. Пусть обучающая выборка объектов из первого класса состоит из n элементов, а обучающая выборка для второго класса - из m объектов. Тогда рассчитывают значения непараметрических оценок плотностей f_n(x) и g_m(x) для первого и второго классов соответственно, а диагностическое решение принимают по их отношению. Таким образом, для решения задачи диагностики достаточно научиться строить непараметрические оценки плотности для выборок объектов произвольной природы.

Ряд видов непараметрических оценок плотности распределения в пространствах произвольной природы предложен и изучен в [109, 48, 30, 110, 111]. Методы построения таких оценок плотности подробно рассмотрены в литературе по прикладной статистике и эконометрике [1, 2, 12]. На их основе этих оценок могут быть построены непараметрические правила диагностики. Их достоинством является универсальность, возможность применения без необходимости обоснования трудно проверяемых условий (например, нормальности распределения характеристик объектов оценки). Недостатком является отсутствие явных формул. Кроме того, для построения непараметрического решающего правила нужны обучающие выборки.

С теоретической точки зрения использование непараметрических оценок плотности дает возможность построить асимптотически оптимальное решающее правило. Как показано в работе [112], при выборе алгоритма для практического использования необходимо учитывать его быстродействие, допустимые объемы обучающих выборок и другие характеристики, в результате вместо алгоритма на основе отношения непараметрических оценок плотностей наиболее приемлемым может оказаться иной алгоритм.

Параметрическая теория обычно опирается на использование для описания классов многомерных нормальных распределений. В линейном дискриминантном анализе Р. Фишера [103] дополнительно предполагается, что ковариационные матрицы двух классов совпадают. Тогда оптимальное правило диагностики использует некоторый порог K. Вновь поступающий объект относят к первому классу, если f(x₁, x₂, …, x_m) < K, и ко второму, если f(x₁, x₂, …, x_m) > K, где обобщающий показатель (рейтинг)

f(x₁, x₂, …, x_m) = a₁x₁ + a₂x₂ + … + a_mx_m(1)

есть линейная функция от единичных показателей (факторов) x₁, x₂, …, x_m. Таким образом, теория классификации тесно связана с теорией рейтингов.

О математических теориях рейтингов. При разработке управленческих решений с целью совместного учета и соизмерении различных факторов, частичного снятия неопределенности широко используются рейтинги. В частности, для сведения к однокритериальной постановке могут быть применены методы построения единого (интегрального) критерия (рейтинга). Термин «рейтинг» происходит от английского «to rate» (оценивать) и «rating» (оценка, оценивание). Оценка - это число, градация качественного признака (удовл., хор., отл.), реже - упорядочение (ранжировка) или математический объект иной природы. Согласно [113, с.8]: «В современном понимании рейтинг - это комплексная оценка состояния субъекта, которая позволяет отнести его к некоторым классу или категории». Имеется достаточное согласие в среде специалистов для того, чтобы использовать термин «рейтинг» как синоним термина «интегральный (единый, обобщенный, системный) критерий (оценка, показатель), позволяющий сравнивать объекты (субъекты) с интересующей пользователя (этим термином) точки зрения. В частности, рейтинги целесообразно использовать при целеполагании (для соизмерения целей).

Для описания многообразия различных видов рейтингов выделим три варианта постановок задач:

1. Непосредственная оценка.

2. Оценка с использованием обучающих выборок.

3. Оценка на основе системы показателей с весовыми коэффициентами.

Под непосредственной оценкой понимаем постановку задачи, в которой итоговый результат получается при непосредственной обработке некоторого множества оценок, без привлечения дополнительной информации о дополнительных объектах или об оценках (весах) дополнительных факторов (признаков). Пример - усреднение чисел. В этом, казалось бы, простейшем примере возникает ряд вопросов. Каким средним пользоваться - средним арифметическим или медианой? Или иными - средним геометрическим и т.п. Некоторые ответы дает теория измерений [2, 3]. При усреднении других видов ответов экспертов теория усложняется. Например, усреднение бинарных отношений может проводиться путем расчета медианы Кемени [12, 114]. При этом может варьироваться как вид меры близости (расстояние Кемени, или его квадрат, или аналог на основе коэффициента ранговой корреляции Спирмена, или D-метрика и т.п.), так и множество бинарных отношений, по которому проводится минимизация [2].

Для оценки с использованием обучающих выборок применяют линейный дискриминантный анализ Р. Фишера, непараметрический дискриминантный анализ на основе использования непараметрических оценок плотностей в пространствах произвольной природы, а также иные методы распознавания образов с учителем, в том числе нейросетевые [115]. Традиционная процедура такова. Первый этап - построение системы показателей. Сначала составляют возможно более полный исходный перечень. Затем список показателей сокращают. Например, проводят кластер-анализ показателей, оставляя из каждого кластера по одному представителю. Отбор информативного подмножества признаков в дискриминантном анализе - самостоятельный раздел прикладной статистики. Следующий этап - непосредственное построение линейного рейтинга на основе отобранных показателей с помощью алгоритмов дискриминантного анализа Фишера.

При оценке на основе системы показателей с весовыми коэффициентами основные составляющие процедур - показатели (факторы), индексы и границы. Для построения системы показателей, обычно иерархической (единичные показатели - групповые - обобщенный) применяют экспертные методы и статистические (формальные) методы выделения информативного подмножества признаков. Способы усреднения (расчета индексов) при переходе от единичных показателей к групповым и от групповых к обобщенному выбирают на основе тех же принципов, что и при непосредственной оценке, но с использованием взвешенных средних. Веса задают либо непосредственно, либо косвенно - с помощью экспертных упорядочений, парных сравнений или обучающих выборок (экспертно-статистический метод).

Важный частный случай - бинарные рейтинги [116], когда рейтинговая оценка принимает два значения. Объект оценки с помощью бинарного рейтинга относится к одному из двух классов. Следовательно, теория бинарных рейтингов - часть дискриминантного анализа, имеющего целью отнесение объекта к одному из двух классов, заданными плотностями вероятностей или обучающими выборками.

Часто строят рейтинг в виде функции f(x₁, x₂, …, x_m) от единичных показателей (факторов) x₁, x₂, …, x_m. , а для принятия решения используют порог K. Принимают определенное решение, если f(x₁, x₂, …, x_m) < K, и альтернативное, если f(x₁, x₂, …, x_m) > K. В этом случае для принятия решения используется бинарный рейтинг вида g(f(x₁, x₂, …, x_m)), где функция g принимает два значения, а именно, g(z) = 0 при z < K и g(z) = 1 при z > K.

На основе бинарных рейтингов можно сконструировать рейтинг с большим числом градаций. Пусть рейтинговая оценка h принимает одно из трех значений A < B < C. С ней можно связать два бинарных рейтинга p и q, таких, что для первого из них p = 0 при h < C и p =1 при h = C, для второго q = 0 при h < B и q =1 при h > B. Ясно, что h = A тогда и только тогда, когда p = q =0, и h = C тогда и только тогда, когда p =q =1, в то время как h = B тогда и только тогда, когда p =0, q = 1. Таким образом, использование рейтинга h с тремя возможными значениями эквивалентно использованию двух бинарных рейтингов p и q.

Популярны линейные рейтинги, заданные формулой (1). Коэффициенты a₁, a₂, …, a_m называют коэффициентами важности (весомости, значимости). Их определяют либо экспертным путем, либо по статистическим данным, используя обучающие выборки [117-119]. Глубокая теория качественной и количественной важности критериев развита В.В. Подиновским [120-122].

По одним и тем же данным могут быть построены различные рейтинги. Например, с помощью обучающих выборок можно построить непараметрический бинарный рейтинг (заданный алгоритмически) и линейный рейтинг (по Р.Фишеру). В той же прикладной задаче может оказаться полезным также и линейный рейтинг на основе экспертных оценок коэффициентов. Есть и иные методы, в частности, основанные на использовании нейросетей для диагностики и рейтингования [115].

О сравнении алгоритмов диагностики по результатам обработки реальных данных. В прикладных исследованиях применяют различные методы дискриминантного анализа, основанные на вероятностно-статистических моделях, а также с ними не связанные, т.е. эвристические, использующие детерминированные методы анализа данных. Независимо от «происхождения», каждый подобный алгоритм должен быть исследован как на параметрических и непараметрических вероятностно-статистических моделях порождения данных, так и на различных массивах реальных данных. Цель такого исследования - выбор наилучшего алгоритма в определенной области применения, включение его в стандартные программные продукты, методические материалы, учебные программы и пособия. Но для этого надо уметь сравнивать алгоритмы диагностики по качеству. Как это делать?

При построении информационно-исследовательской системы диагностики материалов (ИИСДМ) (прообраз - диалоговая система «АРМ материаловеда», разработанная нами для ВНИИ эластомерных материалов) возникает задача сравнения прогностических правил «по силе». Прогностическое правило - это алгоритм, позволяющий по характеристикам материала прогнозировать его свойства. Если прогноз дихотомичен («есть» или «нет»), то правило является алгоритмом диагностики, при котором материал относится к одному из двух классов.

Прогностические правила могут быть извлечены из научно-технической литературы и практики. обычно каждое из них формулируется в терминах небольшого числа признаков, но наборы признаков сильно меняются от правила к правилу. Поскольку в ИИСДМ должно фиксироваться лишь ограниченное число признаков, то возникает проблема их отбора. Естественно отбирать лишь те их них, которые входят в наборы, дающие наиболее «надежные» прогнозы. Для придания точного смысла термину «надежный» необходимо иметь способ сравнения алгоритмов диагностики по прогностической «силе».

Результаты обработки реальных данных с помощью некоторого алгоритма диагностики в рассматриваемом случае двух классов описываются долями правильной диагностики - в первом классе и - во втором, с учетом долей классов в объединенной совокупности .

Нередко [6] как показатель качества алгоритма диагностики (прогностической «силы») используют долю правильной диагностики . Однако показатель определяется, в частности, через характеристики , частично заданные исследователем (например, на них влияет тактика отбора образцов для изучения). В аналогичной медицинской задаче величина оказалась больше для тривиального прогноза, согласно которому у всех больных течение заболевания будет благоприятно. Тривиальный прогноз сравнивался с алгоритмом выделения больных с прогнозируемым тяжелым течением заболевания. Он был разработан группы под руководством академика АН СССР И.М. Гельфанда. Применение этого алгоритма с медицинской точки зрения вполне оправдано [123]. Итак, по доле правильной классификации алгоритм группы И.М. Гельфанда оказался хуже тривиального - объявить всех больных легкими, не требующими специального наблюдения. Этот вывод очевидно нелеп. И причина появления нелепости вполне понятна. Хотя доля тяжелых больных невелика, но смертельные исходы сосредоточены именно в этой группе больных. Поэтому целесообразна гипердиагностика - рациональнее часть легких больных объявить тяжелыми, чем сделать ошибку в противоположную сторону.

Применение теории статистических решений [124, 125] требует знания потерь от ошибочной диагностики, а в большинстве научно-технических и экономических задач определить потери сложно. В частности, из-за необходимости оценивать человеческую жизнь в денежных единицах. По этическим соображениям это, на наш взгляд, недопустимо.

Для выявления информативного набора признаков целесообразно использовать метод пересчета на модель линейного дискриминантного анализа [30, 51], согласно которому статистической оценкой «прогностической силы» является «эмпирическая прогностическая сила» , где - функция стандартного нормального распределения с математическим ожиданием 0 и дисперсией 1, а - обратная ей функция.

Если классы описываются выборками из многомерных нормальных совокупностей с одинаковыми матрицами ковариаций, а для классификации применяется классический линейный дискриминантный анализ Р.Фишера, то величина d* представляет собой состоятельную статистическую оценку расстояния Махаланобиса между двумя рассматриваемыми совокупностями независимо от порогового значения, определяющего конкретное решающее правило. В общем случае показатель вводится как эвристический. Распределение является асимптотически нормальным, что позволяет строить доверительные интервалы для [2, 3].

Как проверить обоснованность пересчета на модель линейного дискриминантного анализа? Допустим, что классификация состоит в вычислении некоторого прогностического индекса у и сравнении его с заданным порогом с. Объект относят к первому классу, если у<с, ко второму, если у>с. Прогностический индекс - это обычно линейная функция (1) от характеристик рассматриваемых объектов. Возьмем два значения порога с₁ и c₂. Если пересчет на модель линейного дискриминантного анализа обоснован, то, как можно показать, «прогностические силы» для обоих правил совпадают: . Выполнение этого равенства можно проверить как статистическую гипотезу. Расчетные алгоритмы предложены в [30, 51] и включены в [2, 3].

Экспертно-статистический метод. Оценивание экспертами коэффициентов линейного рейтинга не всегда надежно. Особенно в ситуации, когда экспертов мало, а разброс мнений экспертов велик. Тогда представляется целесообразным не оценивать коэффициенты, а привлечь высококвалифицированных экспертов для глобальной оценки, т.е. оценки непосредственно обобщающего показателя (рейтинга) Y = f(x₁, x₂, …, x_m) = a₁x₁ + a₂x₂ + … + a_mx_m..