Алгоритм k-means

Итеративные алгоритмы

Итеративные алгоритмы называются так потому, что итеративно перераспределяют объекты между кластерами.

Общая идея алгоритмов *-means: Минимизация расстояний между объектами в кластерах. Останов происходит, когда минимизировать расстояния больше уже невозможно. Минимизируемая функция в случае k-means такова: - объект кластеризации (точка) - центр кластера (центроид). | X | = N, | C | = M

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

Описание алгоритма 0. Первоначальное распределение объектов по кластерам. Выбираются С точек. На первом шаге эти точки считаются центрами кластеров. Выбор начальных центроидов может осуществляться путем подбора наблюдений для максимизации начального расстояния, случайным выбором наблюдений или выбором первых наблюдений.

1. Итеративное перераспределение объектов по кластерам. Объекты распределяются по кластерам путем подсчета расстояния от объекта до центров кластеров и выбора наименьшего.

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

3. Если c_j = c_{j − 1}, то это означает, что кластерные центры стабилизировались и соответственно распределение закончено. Иначе переходим к шагу 1.

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

• простота использования;
• быстрота использования;
• понятность и прозрачность алгоритма.

Недостатки алгоритма k-средних:

• алгоритм слишком чувствителен к выбросам, которые могут искажать среднее.

Возможным решением этой проблемы является использование модификации алгоритма - алгоритм k-медианы;

• алгоритм может медленно работать на больших базах данных. Возможным решением

данной проблемы является использование выборки данных.

Более строгой интерпретацией этого алгоритма является алгоритм hard c-means. Его отличия - в минимизируемой функции и строгости самого алгоритма:

u_ij = 1, если , и u_ij = 0,, если нет. То есть минимизируется расстояние от точек до центроида, а не от центроида до точек.

Тогда формула центроида тоже несколько меняется:

Сам же метод не меняется.

Farthest First - еще одна модификация k-means, особенностью его является изначальный выбор центроидов - от 2 и выше они выбираются по принципу удаленности от остальных(центроидом выбирается точка, наиболее отдаленная от остальных центроидов).