Участник:Msindeeva/Алгоритм k средних

Алгоритм k средних

Автор статьи: Синдеева Мария, группа 416

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

1.1 Общее описание алгоритма

Алгоритм k средних - это алгоритм кластерного анализа, используемый в Data Mining. Цель алгоритма - разделить [math]n[/math] наблюдений на [math]k[/math] кластеров, в которых каждое наблюдение принадлежит к кластеру с ближайшим центром, который служит прототипом всего кластера. Эта задача является NP-сложной, но существуют эффективные эвристические алгоритмы, быстро сходящиеся к локальному минимуму.

Алгоритм k средних является наиболее популярным методом кластеризации. Он был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом.

1.2 Математическое описание алгоритма

Входные параметры: [math]n[/math] наблюдений (векторов) [math](\mathbf x_1, \mathbf x_2, .. \mathbf x_n)[/math], [math]k[/math] - число кластеров.

Также входным параметром можно считать метрику для векторов, например евклидово расстояние [math]d(x, y) = \sum_{i = 1}^{l} (x_i - y_i )^2[/math] - одна из самых популярных используемых метрик.

Формально нам необходимо найти такое разделение [math](\mathbf x_1, \mathbf x_2, .. \mathbf x_n)[/math] на подмножества [math]G = (G_1, .. G_k)[/math], минимизирующие сумму квадратов расстояний до их центров, или суммарное квадратичное отклонение:

[math] J = \underset{\mathbf{G}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x \in G_i} d(\mathbf x, \boldsymbol\mu_i)^2, [/math]

где [math]\boldsymbol\mu_i[/math] - центр кластера [math]G_i[/math]

Алгоритм работает итерационно, каждая итерация алгоритма представляет собой следующее:

• Пересчитать центр масс для каждого кластера, полученного на предыдущем шаге: [math]\boldsymbol \mu_i = \frac{\sum_{\mathbf x_i \in G_i}\mathbf x_i}{|G_i|}, i = 1, 2, .. k[/math]
• Переразбить векторы на кластеры в соответствии с расстоянием до новых посчитанных центров: [math]z_i = \underset{\mathbf{j}} {\operatorname{arg\,min}} \{d(\mathbf x_i, \boldsymbol \mu_j)\}, i = 1, 2, .. n[/math]

Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение [math]J[/math] не увеличивается, поэтому зацикливание невозможно.

Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого шага часто выбирают [math]k[/math] случайных векторов среди [math](\mathbf x_1, \mathbf x_2, .. \mathbf x_n)[/math].

1.3 Вычислительное ядро алгоритма

Две основные составляющие алгоритма:

Вычислительное ядро алгоритма можно считать состоящим из двух частей:

• Пересчет расстояний ярлыков кластеров векторам. Это ядро подразумевает многократное вычисление евклидовых расстояний между [math]N[/math]-мерными векторами.
• Пересчет новых центроидов. В этом ядре осуществляются в основном операции сложения [math]N[/math]-мерных векторов.

1.4 Макроструктура алгоритма

Алгоритм представляет собой циклическое чередование двух этапов, описанных выше, причем каждый использует результаты предыдущего.

Так как расстояния векторов до центроидов никак не связаны друг с другом, подсчет этих расстояний выполняется параллельно друг другу.

1.5 Схема реализации последовательного алгоритма

Структура алгоритма описывается так:

1. Инициализация центроидов [math]\mu_1, ... \mu_k[/math].
2. Последовательное вычисление расстояний векторов до этих центроидов и разбиение по кластерам с этими центрами.
3. Нахождение изменения метрики [math]J[/math]. Если оно меньше некоего заданного порога, то центроиды найдены.
4. Пересчет центроидов в новых кластерах.
5. Переход к шагу 2.

1.6 Последовательная сложность алгоритма

Пусть на входе [math]n[/math] векторов длины [math]N[/math], выделяется [math]k[/math] кластеров.

Вычислительная сложность подсчета квадрата расстояния между двумя векторами: [math]2N - 1[/math] сложений и вычитаний, [math]N[/math] умножений. Таким образом, сложность подсчета метрики [math]J[/math] для одной итерации: [math]n * k * (2N - 1)[/math] сложений, [math]n * k * N[/math] умножений. Пересчет кластеров (поиск среднего ариметического векторов в кластере): [math](n - k) * N[/math] сложений, [math]k * N[/math] делений. Итого, если [math]I[/math] - число итераций, общая сложность: [math](n * k *(2N - 1) + n * k * N + (n - k) * N + k * N) * I = (3N * n * k - n * k + n * N) * I[/math].

Таким образом, общая сложность: [math]O(NnkI)[/math]

1.7 Информационный граф алгоритма

Рисунок 1. Информационный граф алгоритма k средних

1. Первичная инициализация центроидов
2. Первичная метрика
3. Подсчет расстояния между вектором и центроидом
4. Выбор кластера для вектора а основе расстояний до центроидов
5. Подсчет метрики J (сумма квадратов расстояний)
6. Расчет нового центроида
7. Сравнение новой метрики со старой

1.8 Ресурс параллелизма алгоритма

• Сложность второго яруса информационного графа составляет [math]3N - 1[/math] операций
• Сложность третьего яруса - [math]n * k - 1[/math] операций
• Сложность четвертого яруса - [math](max(cluster size) - 1) * N + N = N * max(cluster size)[/math], где максимальный размер кластера зависит от входных данных, но на каждой итерации не больше [math]n - k + 1[/math]

Итого сложность при максимальной параллелизации: [math]I * (3N - 1 + n * k - 1 + (n - k + 1) * N) = I * (4N - 2 + nk + nN - kN)[/math]:

[math]O(n(k+N)I)[/math]

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

Входные параметры: [math]n[/math] векторов размерности [math]N[/math], [math]k[/math] - число кластеров

Объем входных данных: [math]O(N * n * k)[/math]

Выходные данные: k центроидов

Объем выходных данных: [math]O(N * k)[/math]

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

• Не гарантируется достижение глобального минимума суммарного квадратичного отклонения [math]J[/math], а только одного из локальных минимумов.
• Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
• Число кластеров надо знать заранее.

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

Изменяемые параметры запуска реализации алгоритма:

• Число процессоров: [math][1, 2, 4, 8, 16, 32, 64, 128][/math];
• Число векторов: [math][150, 500, 100][/math]. Размерность [math](N = 4)[/math] и число кластеров [math](k = 4)[/math] не изменяется

На графике показана зависимость производительности (количество операций в секунду) от числа процессов и числа векторов.

Рисунок 2. Масштабируемость алгоритма k средних

2.7 Существующие реализации алгоритма

• C + MPI

3 Литература

• MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
• MacKay, David (2003). "An Example Inference Task: Clustering"
• Jing Zhang, Gongqing Wu, Xuegang Hu, Shiying Li, Shuilong Hao (2012). "A Parallel K-Means Clustering Algorithm with MPI"