Участник:Ян-Мартин Тамм/Строгий алгоритм С средних
| Строгий алгоритм С средних (K-means, Hard C-Means) | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(n) }[/math] |
| Объём входных данных | [math]\displaystyle{ mn+1 }[/math] |
| Объём выходных данных | [math]\displaystyle{ cn }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ - }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ - }[/math] |
Описание алгоритма
Строгий алгоритм C средних, более известный как K-средних, решает задачу разделения векторов в многомерном пространстве на заданное количество кластеров. При этом каждый вектор принадлежит только одному кластеру, поэтому алгоритм называется строгим, в то время как нечеткий алгоритм C средних (Fuzzy C-means, Soft K-means) определяет степень принадлежности вектора каждому из кластеров.
Данная задача является NP-трудной, тем не менее описываемый алгоритм сходится к локальному оптимуму. Глобальный оптимум не гарантируется и зависит от первоначального распределения центров кластеров и их количества.
Общая идея алгоритма такова: произвольным образом выбираем центры кластеров, после чего повторяем следующие два действия, пока не будет выполнено условие остановки:
- Распределяем каждый вектор в ближайший кластер
- Пересчитываем значения центров как среднее значение координат векторов в каждом кластере
Минимизируется сумма расстояний векторов от центров их кластеров. Остановка производится если либо значение данной функции становится ниже некоторого порога, либо мало изменяется по сравнению с предыдущей итерацией.
Математическое описание алгоритма
Дано множество d-мерных векторов [math]\displaystyle{ U=\{u_1, u_2, ..., u_n\} }[/math] и число кластеров [math]\displaystyle{ k \in \mathbb{N} }[/math]. Требуется разбить множество [math]\displaystyle{ U }[/math] на [math]\displaystyle{ k }[/math] непересекающихся непустых кластеров [math]\displaystyle{ C_1, C_2, ..., C_k }[/math] таких, что [math]\displaystyle{ {\bigcup \limits _{i = 1}^k C_i} = U }[/math].
Для этого минимизируется функция [math]\displaystyle{
J = \sum\limits_{i=1}^k J_i = \sum\limits_{i=1}^k \sum\limits_{ u \in C_i} \|u-c_i \|^2
}[/math], где [math]\displaystyle{ c_i }[/math]— центр масс векторов кластера [math]\displaystyle{ C_i }[/math].
Произвольным образом инициализируем центры кластеров [math]\displaystyle{ c_1, c_2, ..., c_k }[/math], после чего начинается основная часть алгоритма.
- Каждый вектор [math]\displaystyle{ u_l }[/math] определяем в ближайший к нему кластер [math]\displaystyle{ C_i }[/math], то есть такой, что [math]\displaystyle{ \|u_l-c_i\|^2 \leqslant \|u_l-c_j\|^2 \;\; \forall i \neq j; \;\; (i,j=1,2,\ldots,k, \; l = 1,2,\ldots,n) }[/math]. Хранить информацию о принадлежности векторов кластерам будем в матрице [math]\displaystyle{ M }[/math] следующего вида:
- [math]\displaystyle{ m_{ij} = \begin{cases} 1, & u_j \in C_i \\ 0, & \text{otherwise} \end{cases} }[/math]
- Считаем значение функции [math]\displaystyle{ J }[/math] и прекращаем работу алгоритма, если это значение меньше заданного порога [math]\displaystyle{ \epsilon }[/math], либо значение мало изменилось после текущей итерации.
- Обновляем значения центров кластеров
- [math]\displaystyle{ c_i = \frac{1}{|C_i|} \sum\limits_{u \in C_i} u \;\; (i=1,2,\ldots,k) }[/math]
- Возвращаемся к распределению векторов по кластерам.