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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ 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]\displaystyle{ \boldsymbol\mu_i }[/math] - центр кластера [math]\displaystyle{ G_i }[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ O(n(k+N)I) }[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• C + MPI

Литература

• 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"