1 Свойства и структура алгоритма

1.9 Входные и выходные данные алгоритма

Входные данные

• 
  Матрица из n⋅d элементов xi,j∈R, i=1,...,n, j=1,...,d, – координат векторов (наблюдений).
  
• 
  Целое положительное число k, k≤n – количество кластеров.
  

Объем входных данных
1 целое число + n⋅d вещественных чисел (при условии, что координаты – вещественные числа).
Выходные данные
n целых положительных чисел L1,...,Ln– номера кластеров, соотвествующие каждому вектору (при условии, что нумерация кластеров начинается с 1).
Объем выходных данных
n целых положительных чисел.

1.10 Свойства алгоритма

Вычислительная мощность
Вычислительная мощность алгоритма k-means равна ikdnnd=ki, где k – число кластеров, i – число итераций алгоритма.
Детерминированность и Устойчивость
Алгоритм k-means является итерационным. Количество итераций алгоритма в общем случае не фиксируется и зависит от начального расположения объектов в пространстве, параметра k, а также от начального приближения центров кластеров, μ1,...,μk. В результате этого может варьироваться результат работы алгоритма. При неудачном выборе начальных параметров итерационный процесс может сойтись к локальному оптимуму^[8]. По этим причинам алгоритм не является ни детермирированным, ни устойчивым.
Соотношение последовательной и параллельной сложности алгоритма
Θk−meansΨk−means=O(ikdn)O(i⋅log(kdn))
Сильные стороны алгоритма:

• 
  Сравнительно высокая эффективность при простоте реализации
  
• 
  Высокое качество кластеризации
  
• 
  Возможность распараллеливания
  
• 
  Существование множества модификаций
  

Недостатки алгоритма^[9]:

• 
  Количество кластеров является параметром алгоритма
  
• 
  Чувствительность к начальным условиям
  

Инициализация центров кластеров в значительной степени влияет на результат кластеризации.

• 
  Чувствительность к выбросам и шумам
  

Выбросы, далекие от центров настоящих кластеров, все равно учитываются при вычислении их центров.

• 
  Возможность сходимости к локальному оптимуму
  

Итеративный подход не дает гарантии сходимости к оптимальному решению.

• 
  Использование понятия "среднего"
  

Алгоритм неприменим к данным, для которых не определено понятие "среднего", например, категориальным данным.