Участник:Msindeeva/Алгоритм k средних: различия между версиями
Msindeeva (обсуждение | вклад) (Первый вариант статьи) |
Msindeeva (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | Алгоритм k средних | ||
| + | Автор статьи: Синдеева Мария, группа 416 | ||
| + | |||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Алгоритм k средних''' - это алгоритм кластерного анализа, используемый в | + | '''Алгоритм k средних''' - это алгоритм кластерного анализа, используемый в Data Mining. Цель алгоритма - разделить <math>n</math> наблюдений на <math>k</math> кластеров, в которых каждое наблюдение принадлежит к кластеру с ближайшим центром, который служит прототипом всего кластера. Эта задача является NP-сложной, но существуют эффективные эвристические алгоритмы, быстро сходящиеся к локальному минимуму. |
| − | Алгоритм k средних является наиболее популярным | + | Алгоритм k средних является наиболее популярным методом кластеризации. Он был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. |
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| Строка 26: | Строка 29: | ||
Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение F не увеличивается, поэтому зацикливание невозможно. | Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение F не увеличивается, поэтому зацикливание невозможно. | ||
| − | Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого | + | Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого шага часто выбирают <math>k</math> случайных векторов среди <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math>. |
Версия 23:17, 30 октября 2017
Алгоритм 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] 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].
2 Программная реализация алгоритма
3 Литература
- MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
- MacKay, David (2003). "An Example Inference Task: Clustering"
