Алговики - Вклад [ru]

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

2017-12-01T01:26:48Z

Msindeeva:

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

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

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

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

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

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

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

Входные параметры: <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>.

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

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

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

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

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

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

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

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

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

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

Пусть на входе <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>

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

[[Файл:infograph_k_means.png|thumb|none|500px|Рисунок 1. Информационный граф алгоритма k средних]]

# Первичная инициализация центроидов
# Первичная метрика
# Подсчет расстояния между вектором и центроидом
# Выбор кластера для вектора а основе расстояний до центроидов
# Подсчет метрики J (сумма квадратов расстояний)
# Расчет нового центроида
# Сравнение новой метрики со старой

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

* Сложность второго яруса информационного графа составляет <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>

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
Изменяемые параметры запуска реализации алгоритма:

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

[[Файл:Scalability_k_means.png|thumb|none|500px|Рисунок 2. Масштабируемость алгоритма k средних]]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
* [http://www.ece.northwestern.edu/~wkliao/Kmeans/index.html 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"

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

2017-12-01T00:11:37Z

Msindeeva:

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

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

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

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

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

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

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

Входные параметры: <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>.

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

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

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

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

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

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

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

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

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

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

Пусть на входе <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>

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

[[Файл:infograph_k_means.png|thumb|none|500px|Рисунок 1. Информационный граф алгоритма k средних]]

# Первичная инициализация центроидов
# Первичная метрика
# Подсчет расстояния между вектором и центроидом
# Выбор кластера для вектора а основе расстояний до центроидов
# Подсчет метрики J (сумма квадратов расстояний)
# Расчет нового центроида
# Сравнение новой метрики со старой

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

* Сложность второго яруса информационного графа составляет <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>

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
Изменяемые параметры запуска реализации алгоритма:

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

[[Файл:Scalability_k_means.png|thumb|none|500px|Рисунок 2. Масштабируемость алгоритма k средних]]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
* [http://www.ece.northwestern.edu/~wkliao/Kmeans/index.html 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"

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

2017-12-01T00:02:16Z

Msindeeva: Финальная версия

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

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

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

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

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

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

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

Входные параметры: <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>.

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

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

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

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

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

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

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

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

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

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

Пусть на входе <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>

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

[[Файл:infograph_k_means.png|thumb|none|500px|Рисунок 1. Информационный граф алгоритма k средних]]

# Первичная инициализация центроидов
# Первичная метрика
# Подсчет расстояния между вектором и центроидом
# Выбор кластера для вектора а основе расстояний до центроидов
# Подсчет метрики J (сумма квадратов расстояний)
# Расчет нового центроида
# Сравнение новой метрики со старой

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

* Сложность второго яруса информационного графа составляет <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>

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
Изменяемые параметры запуска реализации алгоритма:

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

[[Файл:Scalability_k_means.png|thumb|none|500px|Рисунок 2. Масштабируемость]]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
* [http://www.ece.northwestern.edu/~wkliao/Kmeans/index.html 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"

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

2017-11-30T19:57:54Z

Msindeeva: /* Свойства и структура алгоритма */ Добавлены все отсутствовавшие разделы

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

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

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

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

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

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

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

Входные параметры: <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>.

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

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

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

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

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

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

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

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

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

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

Пусть на входе <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>

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

[[Файл:infograph_k_means.png|thumb|none|500px|Рисунок 1. Информационный граф алгоритма k средних]]

# Первичная инициализация центроидов
# Первичная метрика
# Подсчет расстояния между вектором и центроидом
# Выбор кластера для вектора а основе расстояний до центроидов
# Подсчет метрики J (сумма квадратов расстояний)
# Расчет нового центроида
# Сравнение новой метрики со старой

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

* Сложность второго яруса информационного графа составляет <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>

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

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

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

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

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

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

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

== Программная реализация алгоритма ==
== Литература ==
* MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
* MacKay, David (2003). "An Example Inference Task: Clustering"

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

2017-10-30T20:18:39Z

Msindeeva:

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

2017-10-30T20:17:37Z

Msindeeva:

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

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

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

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

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

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

Входные параметры: <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>
F = \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>

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

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

== Программная реализация алгоритма ==
== Литература ==
* MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
* MacKay, David (2003). "An Example Inference Task: Clustering"

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

2017-10-23T21:00:07Z

Msindeeva: Первый вариант статьи

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

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

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

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

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

Входные параметры: <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>
F = \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>

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

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

== Программная реализация алгоритма ==
== Литература ==
* MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
* MacKay, David (2003). "An Example Inference Task: Clustering"