СРАВНЕНИЕ МЕТОДОВ КЛАСТЕРИЗАЦИИ

Как мы уже говорили, с помощью разных методов кластеризации можно получить различные результаты для одних и тех же данных. Теперь попробуем разобраться, почему так происходит. Мы постоянно отмечали, что некоторые методы имеют присущие только им особенности и свойства. Например, метод одиночной связи имеет тенденцию к образованию длинных цепочек кластеров, в то время как метод Уорда склонен к образованию плотных гипер-сферических кластеров. Понимание того, что различные методы кластеризации будут порождать заметно различающиеся результаты, имеет более чем просто академический интерес, поскольку эти методы применяются к исследованию реальных данных без особых раздумий, рутинно. Лучше еще до исчерпывающего анализа данных знать сильные и слабые стороны различных методов, чем внезапно обнаружить, что результаты анализа во многом обязаны свойствам самого метода, а не внутренней структуре данных.

Многие сравнения кластерных методов сводятся к оценке, насколько хорошо различные методы кластеризации восстанавливают известную структуру данных. Хотя в некоторых из этих исследований были использованы реальные данные с такими же характеристиками, в большинстве случаев применялись искусственные данные, полученные с помощью моделирования методом Монте-Карло и выборочного метода, которые специально создавались для имитации особенностей реальных данных (например, данные, имитирующие результаты MMPI-теста (Blashfield and Morey, 1980). Чаще всего наборы данных подбирались в соответствии со свойствами важных видов распределений, таких, как двумерное нормальное, многомерное нормальное и многомерное гамма-распределения. В зависимости от цели сравнения эти наборы данных изменялись в размерах (число объектов на кластер), форме кластеров, числе кластеров в данных, степени перекрытия кластеров, наличии выбросов и степени полноты классификации (должна ли классификация быть исчерпывающей) некоторые сравнения проводились на наборах данных, удовлетворяющих ультраметрическому неравенству — более строгому варианту неравенства треугольника, описанному в разд. II (Mulligan and Issac, 1980). Внимание было уделено последствиям использования различных мер сходства.

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

1) характеристики кластерной структуры;

2) наличие выбросов и степень полноты классификации;

3) степень перекрытия кластеров;

4) выбор меры сходства.

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

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

Наличие выбросов и степень полноты классификации, требуемая при кластеризации, — важные факторы, влияющие на работу метода. Полная классификация является исчерпывающей: все рассматриваемые объекты должны быть размещены по группам. Основанное на методе Монте-Карло исследование влияния этого фактора показывает, что, если требуется полная классификация и данные имеют мало выбросов, то метод Уорда дает превосходное восстановление известной кластерной структуры (Kuiper and Fisher, 1975; Mojena, 1977). Однако в работах (Blashfield and Morey, 1980; Edelbrock, 1979; Edelbrock and McLaughlin, 1979; Milligan, 1980) показано, что если степень полноты классификации уменьшается, то кластеризация по методу средней связи дает восстановление такое же, что и по методу Уорда. Миллиган и Иссак (1980), воспользовавшись данными с ультраметрикой, доказали, что в действительности метод средней связи может работать лучше метода Уорда даже в случае полной классификации. Вообще может показаться, что на работе расширяющих пространство методов неблагоприятно сказывается присутствие большого числа выбросов, но это утверждение еще требует проверки. Важно помнить, что выбросы — это не просто обособленные объекты; на самом деле они могут быть представителями подгрупп, о которых в выборке содержится мало данных. Следовательно, очевидное решение проблемы выбросов (отбросить эти данные) должно быть хорошо продуманным. Независимо от их интерпретации выбросы необходимо тщательно исследовать еще до применения кластерного анализа. Для каждого выброса необходимо определить, почему он так отличен от других объектов.

Проблема перекрытия кластеров аналогична проблемам степени полноты классификации и наличия выбросов в выборке данных. Перекрытие кластеров — это просто степень, с которой кластеры занимают одно и то же пространство.

Кластеры могут быть хорошо разделенными, но могут находиться и близко один к другому. Кроме того, могут присутствовать шумовые точки, т. е. точки данных, лежащие между границами кластеров. Как было показано, все эти факторы оказывают сильное влияние на работу методов кластеризации, а также, в случае перекрытия кластеров метод Уорда работает лучше большинства других методов кластеризации (Bayne et. al., 1980), тогда как метод средней связи работает плохо (Bayne et. al., 1980; Milligan, 1980). Однако при прочих равных условиях метод средней связи дает классификацию такой же полноты, что и метод Уорда для хорошо разделенных кластеров. Если же требования к полноте классификации ослаблены и допускаются перекрытия кластеров, то этот метод опять будет эквивалентен методу Уорда (Edelbrock, 1979; Edelbrock and McLaughlin, 1979; Milligan, 1980).

И наконец, на работу методов кластеризации влияет выбор меры сходства. К сожалению, были изучены только две меры: евклидово расстояние и коэффициент смешанного момента корреляции. Фактически во всех описанных выше исследованиях по методу Монте-Карло сравнивалась работа метода Уорда, использовавшего евклидово расстояние, и метода средней связи, применявшего коэффициент смешанного момента корреляции. Хотя, кажется, выбор меры все же приводит к некоторым различиям в результатах, его воздействие скрадывается воздействием характеристик кластерной структуры, требуемой степени полноты классификации и перекрытия кластеров. Надо еще очень много поработать с другими коэффициентами, прежде чем можно будет оценить влияние выбора меры сходства на работу методов кластеризации.