И.Д. Мандель - Кластерный анализ (И.Д. Мандель - Кластерный анализ.djvu), страница 9

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

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

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

Видимо, совсем не случайно установлено, что считавшиеся прежде эвристическими процедуры оптимизируют некоторые функционалы. Резкой границы между подходами нет, наоборот, есть предположение, что каждая прямая процедура на самом деле доставляет экстремум какой-то функции, которую, правда, надо отыскать (см., напр., (18]). И напротив, каждому функционалу скорее всего соответствует свое определение кластера. Большая работа по выяснению такого рода связей между подходами еще далека от завершения, но ее результаты представляются многообещающими (см. 2.3.4). зв Наконец, можно выделить третье направление решения задачи кластеризации, наиболее позднее по срокам развития (середина 70-х годов).

Его можно называть апнроксимационным. Основная идея подхода заключается в следующем: отношения, заложенные в исходных данных, требуется наилучшим образом аппроксимировать отношением, отвечающим нашему представлению о классификации. Классификация обычно задает отношение эквивалентности, а исходные данные могут быть отражены по-разному. Например, матрицу «объект-объект» расстояний можно рассматривать как метризованную толерантность. Тогда задача стоит так: найти эквивалентность, ближайшую (в некотором смысле) в исходной толерантности. Возможны и другие постановки такого вида (2.3). Конечно, алгоритмы аппроксимации носят оптимизационный характер.

Но целесообразно выделить эти процедуры как в силу их своеобразной направленности, так и потому, что сами они порождают определенные функционалы качества. Возможно, наиболее серьезные теоретические результаты будут получены именно на пути анализа процедур аппроксимации при разных предположениях. Рассмотренные три направления в задаче кластеризации, как и некоторые ранее делавшиеся классификации алгоритмов [5, 30, 62 и др.], не бесспорны и даже не вполне строги. Как отмечалось, типы могут пересекаться, и, видимо, зона пересечения будет с углублением теоретических разработок возрастать.

Вообще надо отметить, что вопрос о классификации алгоритмов классификации, поставленный лет пятнадцать назад, не нашел до сих пор приемлемого решения. глл. клдссиеикдция Алгоритмов Варианты классификации обсуждались А. А. Дорофеюком [30), С. А. Айвазяном и др. [5), Н. Г. Загоруйко [38], Б. Г. Миркиным [63), А. Р. Лейбкиндом и др. [47), Дж.

Гудом [28), Р. Кормаком ]!20], Дж. Хартиганом [)3)) и многими другими авторами. При этом различными были ие только схемы классификации, но и первичные установки исследователей — чрезвычайно обильные и весьма частные свойства классификаций, перечисляемые в ]28] (отчастм и в [47] ), почти никак не связаны с четким, но довольно схематичным делением методов в [30) и т. д. Предлагаемая ниже группировка в значнтельной мере опирается на схемы перечисленных авторов. Классификацию алгоритмов приходится вести по нескольким качественным признакам, поэтому, например, ожидать стройной упорядоченности не приходится — сочетания признаков носят фасетный характер.

Рассмотрим важнейшие основания для деления. !. Характер отношения, которое отыскивается как результат классификации 1.!. Разбиение с непересекающимися классами (отношение эквивалентности). Все объекты внутри найденного класса считаются тождественными, а объекты разных классов — нет. Почти все процедуры, описанные в 2.2 и 2.3, отыскивают такие разбиения.

39 1.2. Разбиение с пересекающимися классами. Задается по-разному: введением степени принадлежности объекта к классу в духе теории размытых множеств [34, 331, определением вероятности принадлежности объекта к классу [76) или просто перечнем объектов в зоне пересечения. Некоторые из рассмотренных ниже алгоритмов допускают пересекающиеся классы, но специально рассматривать такие процедуры нам кажется нецелесообразным, поскольку в конечном счете все равно исследователь вынужден отнести куда-либо каждый объект (см.

другую точку зрения в [131, !10] н др.). 1.3. Иерархическое дерево. Процедуры классификации отыскивают целую систему вложенных разбиений. Такая сложная структура далеко не всегда соответствует представлениям о строении совокуп- . ности. Но иерархическими алгоритмами можно отыскивать и «обычные» разбиения, стоит лишь задать число классов, порог и т.

д, В таком аспекте мы и будем их рассматривать. Исторически такие востановки существуют с начала 50-х годов и идут от биологической систематики. Нередка нх называют задачами таксономии (в отличие от других задач кластеризации). В обзоре [зо! они вообще не были зачислены в разряд методов автоматической классификации. 1.4. Отношение произвольной структуры. Наиболее общий способ анализа структуры множества — аппроксимация его некоторым отношением с произвольной (заранее заданной) структурой. Такая задача, вообще говоря, выходит за рамки кластер-анализа. Но ее можно рассматривать расширительно, связав произвольную структуру со способом операционализации некоторой «суперцели» классификации [37, с. 88) (см.

3.2). 2. Степень участия человека в процедуре выделения кластеров 2.1. Человек не принимает участия в работе алгоритма, классификация производится машинным способом. Таковы многие процедуры в 2.2 и все — в 2.3. Конечно, отсутствие человека понимается в узком смысле: исследователь формирует исходные данные, выбирает расстояние, задает параметры классификации, но сам в процесс работы алгоритма не вмешивается, разбиение получает как готовый результат.

2.2. Человек участвует в процессе получения разбиения. ЭВМ (алгоритм) выдает не собственно классификацию, а информацию, на основании которой человек принимает решения о разбиении. Такими процедурами фактически являются все методы визуализации данных (см. 3.1), упорядочения матриц связи и др. Они обычно дают максимально полезные содержательные результаты, несмотря на свою «нестрогость» и «человеческий произвол». 40 3, Характер априорных сведений (задаваемых параметров) для работы алгоритма 3 !. Априорные сведения отсутствуют (свободная классификация) Считается, что отсутствие задаваемых параметров необходимо для выделения естественной, а не навязанной структуры исходных данных.