Особенности метода

Метод /С-средних имеет сильные стороны, обеспечивающие его популярность. Концептуально он моделирует процесс создания типологии человеком, при этом типы характеризуются центрами ск и кластерами Sk. Кроме того, алгоритм имеет хорошие вычислительные характеристики: вычисления просты и интуитивны, метод сходится быстро и не требует много памяти.

Метод имеет и слабые стороны:

  • (а) каким-то образом необходимо инициализировать число кластеров К и начальные центры;
  • (б) результаты сильно зависят от инициализации и нормализации исходных данных;
  • (в) метод не защищен от присутствия «случайных», «проходных» объектов или признаков, которые могут сильно исказить результаты;
  • (г) не проработаны вопросы интерпретации кластеров в тех случаях, когда центры не слишком отличаются от вектора средних на всем множестве.

Существуют модификации метода /С-средних, позволяющие частично преодолеть указанные проблемы [ 181. Одна из них, нацеленная на решение проблемы (а), будет рассмотрена далее в параграфе 4.6.

Рабочий пример 4.2. Зависимость метода Х-средних от начальных данных: преимущества и недостатки

Очевидный минус метода /С-средних заключается в том, что его результаты зависят от начальных данных — центров и количества кластеров К. Действительно, если на старте выбрать неправильные центры, то результаты метода будут неутешительными.

В некоторых пакетах, таких как SPSS, в качестве центров выбираются первые К объектов. Если применить этот прием к данным о компаниях, начальные центры будут в объектах Av, Ап и As. В этом случае метод выдаст не слишком удачные кластеры SI = {Av, Ва, Br}, S2 = {Ап}, и S3 = {As, Bu, Ci, Су} (см. вопрос 4.10). Ясно, что этот результат определяется неудачным выбором начальных центров — из одного и того же кластера. Однако даже если начальные центры берутся из правильных кластеров, это необязательно гарантирует правильный результат. Начнем, например, с точек Av, Ва и Ci (отметим, что данные компании производят разные продукты!). Попробуйте самостоятельно убедиться в том, что итоговый результат будет удручающим — SI = {Av, An, As}, S2 = {Ва, Ви}, S3 = {Br, Ci, Су} (см. также вопрос 4.11).

На рис. 4.13 продемонстрирован тот факт, что нестабильность результатов метода возникает не в каком-то специально подстроенном случае — такая вещь происходит достаточно часто. На данном рисунке проиллюстрированы два четких кластера, которые можно представить как равномерно распределенные множества точек, и две различных инициализации: симметричная представлена на рис. 4.13, а, асимметричная — на рис. 4.13, 6. В случае К = 2 правило минимального расстояния приводит к проведению гиперплоскости, которая ортогонально разделяет два центра и проходит через середину линии, соединяющей эти два центра; гиперплоскость показана на рис. 4.13 как прямая, разделяющая центры. На рис. 4.13, а изображен случай, когда начальные центры более или менее симметрично расположены друг относительно друга. Поэтому линия, проходящая через середину, действительно отделит кластеры друг от друга. На рис. 4.13, б начальные центры сильно асимметричны. В этом случае разделяющая линия отсечет кусок одного из данных кластеров, изменяя тем самым местоположение будущих центров. Финальное деление тоже будет проходить через один из кластеров, что совершенно противоречит здравому смыслу.

Ситуация двух четко разделенных кластеров при двух разных начальных инициализациях, которые могут привести как к правильному разделению на кластеры (случай я), так и неправильному (случай 6)

Рис. 4.13. Ситуация двух четко разделенных кластеров при двух разных начальных инициализациях, которые могут привести как к правильному разделению на кластеры (случай я), так и неправильному (случай 6)

Еще один пример неоптимальности результатов метода iC-срсдних, с использованием только четырех точек, представлен на рис. 4.14.

Пример неудачной работы метода К-средних при поиске двух кластеров на множестве четырех точек плоскости (рисунок справа)

Рис. 4.14. Пример неудачной работы метода К-средних при поиске двух кластеров на множестве четырех точек плоскости (рисунок справа)

Рабочий пример 43. Близкие кластеры могут оказаться дальними для К-средних

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

Парадоксальная ситуация, при которой способ формирования кластеров зависит от распределения объектов по точкам А, В, С

Рис. 4.15. Парадоксальная ситуация, при которой способ формирования кластеров зависит от распределения объектов по точкам А, В, С

Рассмотрим случай, представленный на рис. 4.15: три множества объектов, каждое попало в одну и ту же точку, А, В, С. Два из них состоят из 100 объектов в каждом (в точках А и В), а третье состоит из одного объекта в точке С. Примем, что расстояние между А и В — 2, а между В и С — 10. В таком случае возможно только два случая двухкластерного разбиения: (i) 200 точек из А и В в одном кластере и одна точка в другом кластере (С); (ii) 100 точек из А в одном кластере и 101 точка — из В и С — в другом. Третье разбиение, состоящее из кластера В и кластера А + С, не может быть оптимальным, потому что кластер Л + С более растянут, нежели схожий кластер В + С в случае (ii).

Сравним значения критерия /С-средних на этих двух вариантах при использовании квадрата Евклидова расстояния между точками и центрами. Как объяснено в разделе 0.4.5, критерием метода является минимизация суммы расстояний от объектов до центров кластеров, которым они принадлежат.

В случае (i) центр кластера А + В будет расположен в середине интервала между А и В, на расстоянии 1 от каждого. Следовательно, сумма всех квадратичных Евклидовых расстояний до центра равна 200 • 1 = 200. Так как кластер С состоит только из одного объекта, он ничего не вкладывает в значение критерия /С-средних, который, таким образом, равен 200.

В случае (ii) у кластера В + С есть центр, который является центром масс В и С, т.е. расположен на расстоянии d = 10/101 от В. Следовательно, значение критерия /С-средних равно 100 • d2 + (10 - d)2, что меньше, чем 100 • (1 / 10)2 + + 102 = 101, так как d < 1/10 и 10 - d < 10. Вклад кластера А в критерий равен 0, потому что все 100 объектов расположены в точке А, которая, следовательно, является центром данного кластера.

Таким образом, случай (ii) более выгоден: значение критерия /С-средних в данном случае нс превышает 101, тогда как в случае (i) оно равно 200. При этом объединение В и С в (ii) противоречит интуиции, так как А значительно ближе к В, чем С. Это означает, что критерий метода /С-средних скорее способствует более равномерному распределению объектов между кластерами, чем объединению наиболее близких объектов.

Но нет худа без добра: параллельный метод /С-средних ведет именно к интуитивному, хотя и не оптимальному, решению. Действительно, начав с наиболее удаленных точек А и С как исходных центров, мы всегда будем получать вариант (i) как результат!

Рабочий пример 4.4. Устойчивость критерия К-средних на нормализованных данных

Существует мнение, что критерий /С-средних хорош только для разделения сферических кластеров. Но это не совсем так. Метод успешно работает и на кластерах, сильно отличающихся по форме. Чтобы убедиться в этом, сгенерируем два таких кластера на плоскости так, чтобы один образовывал кружок, а второй — сильно растянутую полосу. Пусть кластер-круг состоит из 100, а кластер-полоса — из 200 объектов. Первый кластер — множество точек (х> у)у где каждая компонента имеет Гауссово распределение со средним в 1 и стандартным отклонением 0,5. Второй кластер состоит из точек, равномерно распределенных в прямоугольнике со сторонами длиной 40 и 1, причем этот прямоугольник расположен параллельно оси х в районе значения у = 5 (рис. 4.16 слева) или в районе у = 3 (рис. 4.16 справа).

Если обрабатывать эти данные как есть, то метод /С-средних не сможет отделить сгенерированные кластеры друг от друга. Как и на рис. 4.13, метод отделит круг и прилегающую часть полосы, порядка 50 объектов, от остальной ее части. Однако ситуация меняется, если перейти к стандартизованным данным. Если вычесть из каждого признака, х и у, его среднее, а потом разделить результат на размах или стандартное отклонение признака, метод /С-средних сработает. Попробуйте самостоятельно убедиться, что на нормализованных данных левой стороны рис. 4.16 метод /С-средиих, при К = 2, начиная с наиболее удаленных друг от друга объектов, приводит в точности к двум сгенерированным кластерам. Конечно, результат изменится для не столь структурированных данных в правой части рис. 4.16. Если нормализовать данные правой части рисунка стандартными отклонениями признаков, то структура двух кластеров воспроизводится методом /С-средних с очень небольшой ошибкой — только ближайшие 5 точек полосы добавляются к кругу, остальные 195 объектов образуют другой кластер. Результат получается похуже, если нормализовать признаки их размахами. В этом случае 32 объекта полосы присоединятся к кругу — ошибка 32 / 300, около 10%. Докажите это самостоятельно.

Двумерное множество, состоящее из двух кластеров разной формы, круга и полосы; координаты центров по оси ординат равны 1 (круг) и 5,5 (полоса) на левом рисунке, и 1 и 3,5 — на правом

Рис. 4.16. Двумерное множество, состоящее из двух кластеров разной формы, круга и полосы; координаты центров по оси ординат равны 1 (круг) и 5,5 (полоса) на левом рисунке, и 1 и 3,5 — на правом

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >