ГЛАВА 7. ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ

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

В этой главе мы сделаем некоторые замечания о развитии кластерного анализа за последние четыре десятилетия.

Первоначальное описание и определение предмета, известного сейчас под названием «кластерный анализ», было сделано Трионом [361] в 1939 г. В недавно вышедшей книге Триона и Бейли [371, 1970] они рассматривают вычислительную систему ВСПУ, предназначенную для решения задач кластеризации и факторного анализа в области социологии. В книге Фишера [108, 1968] рассматриваются специальные методы, применяемые в задачах агрегирования в экономике. Коул [57, 1969] рассматривает работы, представленные на коллоквиум по численной таксономии. В недавно вышедшей книге Джардайна и Сибсона [180] читатель найдет математическое обоснование методов, которыми пользуются в биологической таксономии; эти методы на самом деле имеют более широкое применение. Исследование этих методов продолжено в [175], [177], [178] и [179]. Ими. же был предложен аксиоматический подход к кластерному анализу. Андерберг написал книгу по кластерному

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

Болл [13] сделал прекрасный обзор и сравнение различных методов «поиска кластеров». Он разбивает все методы на семь групп: 1) вероятностные, 2) методы обнаружения сигнала, 3) кластеризации, 4) группировки, 5) собственных значений, 6) отыскания минимальной моды, 7) остальные. Наиболее употребительными методами, под которыми обычно и понимается кластерный анализ, являются методы кластеризации (3) и методы группировки (4). Ступенчатые методы, которые обсуждались в главе 1, — это методы группировки, а методы минимальной дисперсии той же главы принадлежат к группе методов кластеризации. Метод отыскания минимальной моды требует предварительного разбиения наблюдений на классы. Класс собственных значений Холла сродни факторному анализу и методу главных компонент многомерного анализа.

Другой класс, который включает в себя метод оценивания функции плотности, обсуждался в главе 5. Вероятностные методы Холла могут быть обобщены и на этот случай.

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

Широкое признание нашел кластерный метод Болла и Холла [15], [16], [18] ИСОМАН (итеративный самообучающийся метод анализа данных). Этот метод был коротко упомянут в главе 1 как метод минимальной дисперсии. Он применялся, в частности, в задаче регистрации отдаленных объектов (мультиспектральные данные сканирования) в НАСА, в Центре пилотируемых

космических кораблей. Инструкцию по его эксплуатации можно найти в [166], [191], [193].- Окончательная версия ИСОМАНа была предложена Каном и Холли [194]. Применение ИСОМАН было показано на примере регистрации отдаленных объектов (мульти-спектральные данные сканирования), который был описан в предыдущей главе.

Другим полезным методом является добавочный (adding) алгоритм Хартигена (записи лекций), который также описан у Кана и Холли [194]. Этот метод относится к классу разделительных (divise) иерархических алгоритмов. Кан и Холли обсуждают и другие методы, которые также применяются и весьма полезны (см. [325], [208], [404] и [302]).

Целью патерн-рекогносцировки, как и кластерного анализа, является разбиение данных на группы. Однако в патерн-анализе для каждого наблюдения известно, к какому классу информации оно принадлежит. Наджи [270] предлагает прекрасный обзор по патерн-рекогносцировке. Его статья насчитывает 148 ссылок.

Методы кластеризации могут быть разбиты на два больших класса: 1) разделительные, 2) агломеративные. Не надо только путать понятия алгоритма и метода. Данный метод может принадлежать либо к классу разделительных, либо к классу агломеративных методов. Разделительные методы разбивают множество объектов на группы, а агломеративные, наоборот, объединяют объекты в группы (кластеры). Разделительные методы были введены Эдвардсом и Кавалли-Сфорца [93], МакНотоном-Смитом и другими [235] и Ресчиньо и Макакоро [293]. Класс агломеративных методов шире; некоторые из этих методов были описаны в главе 1, [223], [234], [387]. Ступенчатый алгоритм кластеризации, рассмотренный в главе 1, является агломеративным алгоритмом. Агломеративные процедуры в общем случае не обязательно итеративные и предполагают существование правила объединения двух кластеров.

Некоторые методы, строго говоря, нельзя отнести ни к классу разделительных, ни к классу агломеративных; к таким методам относятся, например, методы, описанные в главе 1 [18], [33] и [237]. К этому же классу относится метод динамического программирования Дженсена [183], описанный в главе 4.

Очень мало сделано в области сравнения кластерных

методов. Очень трудно бывает определить, какой метод лучше. Выбор метода зависит как от целей исследования, так и от вида данных. Более того, в некоторых случаях вообще невозможно сравнивать два метода. Гауером [137] были сделаны сравнения методов Сокала и Миченера [334], Эвардса и Кавалли-Сфорца [93], Уильямса и Ламберта [394]. Рэнд [288] предлагает объективный критерий сравнения двух различных методов кластеризации. По другим вопросам применения кластерных методов см. Джардайн и Сибсон [180], глава 2, Борко [34] и Грин и Рао [144].

Фишер и Ван Несс [102] определили некоторые условия приемлемости, которые можно считать желательными почти во всех случаях кластерного анализа и сравнения этих свойств для некоторых стандартных методов. Условия приемлемости позволяют отбросить те процедуры, которые приводят к «плохому» разбиению на группы. Однако одновременно с исключением «плохих» методов применение этих условий в некоторых случаях приводит к отбрасыванию и пригодных методов кластеризации. Некоторые из условий приемлемости, рассматриваемые в [102], обсуждаются также Хартигеном [162], Джонсоном [186], Джардайном и Сибсоном [178]. Работа Фишера и Ван Несса [103], в которой рассматриваются проблемы приемлемости дискриминантного анализа, также представляет некоторый интерес.

Желаемое число кластеров, которые будут получены в результате применения того или иного метода кластеризации, может быть неизвестно. Часто это число не определяется из результатов кластеризации. В иерархических (агломеративных) и разделительных методах исследователь может найти нужное из рассмотрения различных иерархических уровней. В динамическом подходе число необходимо знать заранее. Методы паттерн-рекогносцировки также требуют предварительного знания значения .

Следующий, достаточно неопределенный момент связан с понятием сходимости метода. Это понятие обсуждалось нами при рассмотрении некоторых методов минимальной дисперсии в главе 1. Результаты кластеризации должны быть единственными. Если данные мультимодальны, а моды определены достаточно хорошо, то результаты кластеризации имеют тенденцию быть единственными

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

Методы, которые мы обсуждали в этой монографии, предназначались для кластеризации объектов или элементов. Однако эти же методы можно применять и для кластеризации признаков или характеристик. В [161] Хартиген предлагает метод двойной кластеризации, т. е. метод, который кластеризует и по объектам и по признакам одновременно.

Кластерный анализ тесно связан с другими методами многомерного анализа, методом главных компонент, дискриминантным анализом, факторным анализом.

Дискриминантный анализ предназначен для получения предварительной классификации данных. Перегруппировывая данные и вычисляя новое значение дискриминантной функции в результате итераций, приходят к «наилучшему» разбиению данных на группы. Касетти [45], Ханг и Дюбс [170] описывают программу применения этого метода. Мейер [261] предлагает аналогичный метод, в котором пользуются одной характеристикой, представляющей наибольший интерес. В более поздней статье Мейер [263] рассматривает метод, при котором матрица наблюдений предварительно сокращается с помощью метода главных компонент, после чего для построения кластеров вводится критерий расстояния и линейная дискриминационная функция. Урбах [375] предложил метод дискриминантного анализа разбиения разнородной многомерной совокупности на группы; разбиения повторяются до тех пор, пока не будет получен удовлетворительный результат, который записывается в терминах вероятности «плохой» классификации.