Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ВВЕДЕНИЕ В АНАЛИЗ ДАННЫХ
Посмотреть оригинал

Проблема инициализации К-средних и аномальные кластеры

Подходы к инициализации К-средних

Многочисленные прогоны для инициализации К-средних

Для инициализации метода /(-средних нужно задать:

  • (i) количество кластеров, К;
  • (ii) начальные центры, с = (cv с2,ск).

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

  • а) до применения метода кластеризации;
  • б) во время применения метода кластеризации;
  • в) после применения метода кластеризации.

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

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

Методы типа (в) основаны на многократном применении метода Х-средних, начиная со случайных X центров, и обработке результатов. Обычно задаются каким-либо числом прогонов, например Р= 100, выбирают какой-либо диапазон изменения X, например, от 2 до 20, после чего делают Р прогонов метода при каждом заданном К из этого диапазона. Результат каждого такого прогона оценивают критерием квадратичной ошибки V(S, с) (см. выражение (4.9)). Обозначим через VK минимальное из этих К значений W(5, с). Последовательность WK при разных К из рассматриваемого диапазона значений используется для того, чтобы увидеть, какое К привело бы к лучшему значению WK. К сожалению, лучшее WK не обязательно является минимумом WK, потому что минимальное значение критерия квадратичной ошибки может только убывать с ростом К (математический факт). Имеется ряд предложений о том, как использовать флуктуации в поведении WK, чтобы оценить «правильное» X. К сожалению, все они не очень надежны. Экспериментальный анализ показал, что одно из самых надежных — это «среднепотолочное» правило Хартигана (см. [25]). Правило Хартигана основано на том предположении, что если имеется X* кластеров, четко отделенных друг от друга, то для X < X* кластеров (X + 1)-кластерное разбиение по методу Х-средних должно походить на X-кластерное разбиение и получаться из него разделением одного из кластеров на две части. При этом WK+{ значительно меньше, чем WK. С другой стороны, при К > К*, и Х-кластерное и (X + 1 )-кластерное разбиения должны в основном совпадать с «правильным» Х*-кластерным разбиением с точностью до нескольких «правильных» случайно разделенных кластеров; при этом VK и WK+ j не сильно различаются. На основе этих соображений рассчитывается индекс Хартигана:

начиная с К = 2 и последовательно увеличивая X. Здесь, как и ранее, N — количество объектов. В качестве оценки X* при этом берется первое значение X, при котором Нк становится меньше, чем 10. В экспериментах, описанных в [25], правило Хартигана оказалось наилучшим из девяти различных критериев, предложенных в литературе, причем порог 10 оказался не сильно чувствительным к 10—20%-ным изменениям.

Рабочий пример 4.5. Индекс Хартигана для выбора количества кластеров

Рассмотрим значения Нк для данных об ирисах и городах побережья, полученных в результате 100 прогонов метода Х-средних на данных, нормализованных вычитанием среднего и делением на размах, начиная с К случайных центров (табл. 4.15). Каждый прогон повторяется дважды (см. первый и второй наборы в табл. 4.15) для демонстрации типичных колебаний значений Нк с учетом того, что эмпирические значения WK могут быть не оптимальными. В частности, в случае второго множества результатов, полученного методом К-срсдних на данных о городах, видно нарушение свойства положительности Нк (поскольку нормальное WK должно уменьшаться с ростом К). Монотонность И^ нарушается, потому что значения WK на результатах 100 прогонов нс обязательно минимальны глобально.

«Естественное» количество кластеров в данных об ирисах по критерию Хартигана не 3, как утверждается ботаниками, а намного больше, 11! В данных о городах критерий бы определил 4 «естественных» кластера. Однако следует иметь в виду, что точное значение 10 в правиле Хартигана недостаточно для того, чтобы сделать определенный вывод его достижение должно сопровождаться значительным изменением значения Нк. Сильное изменение происходит при К = 5, вероятно, именно это число можно использовать в качестве «естественного» числа кластеров в данных о городах. Аналогично, значительное изменение значения Нк в данных об ирисах происходит при К = 3, именно это число, по-видимому, является количеством естественных кластеров данного множества.

Таблица 4.14

Значения индекса Хартигана Нк для К, меняющегося в диапазоне от 2 до 11, вычисленные по результатам двух различных 100 прогонов метода /С-средних, начиная со случайных К

объектов в качестве начальных центров

Наборы данных

К= 2

3

4

5

6

7

8

9

10

11

Ирисы

1-й набор

108,3

38,8

29,6

24,1

18,6

15,0

16,1

15,4

15,4

9,4

2-й набор

108,3

38,8

29,6

24,1

18,7

15,4

15,6

15,7

16,0

7,2

Города

1-й набор

13,2

10,5

9,3

5,0

4,7

3,1

3,0

3,2

3,2

1,6

2-й набор

13,2

10,5

9,3

5,8

4,1

2,5

3,0

7,2

-0,2

1,8

Самостоятельная работа

4.6.1. Рассчитайте значения индекса Хартигана по 100 прогонам метода Х-средних при каждом К = 3, 4, ..., 11 как на данных об ирисах, так и на данных о городах английского побережья.. Сравните полученные вами значения с величинами, содержащимися в табл. 4.14.

В целом, использование прогонов метода /С-средних, начиная со случайных центров, ограничено ситуациями, когда количество объектов не слишком велико. С ростом количества объектов до нескольких тысяч количество прогонов метода, необходимых для достижения нужного значения WK может стать чрезмерно большим. Кроме того, критерий W(5, с) сам по себе имеет ряд существенных изъянов; его следует использовать только в совокупности со стратегией, основанной на знании структуры данных.

Другое направление использования результатов Р прогонов метода К-срсдних при различных К — это агрегирование всех Р полученных разбиений при каждом К: чем ближе К к «правильному» значению К*, тем точнее «агрегированное» или «консенсусное» разбиение воспроизводит структуру данных. Это направление активно развивается в последнее время, но нс будет здесь рассматриваться, так как выходит за рамки данного текста.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
     

    Популярные страницы