К-средство кластеризации - K-means clustering

Не путать с Алгоритм K-ближайших соседей.

k-средства кластеризации это метод векторное квантование, первоначально из обработка сигналов, которая направлена ​​на раздел п наблюдения в k кластеры, в которых каждое наблюдение принадлежит кластер с ближайшим иметь в виду (центры кластеров или кластерные центроид ), служащая прототипом кластера. Это приводит к разделению пространства данных на Клетки Вороного. k- означает, что кластеризация минимизирует внутрикластерные различия (квадрат евклидовых расстояний ), но не регулярные евклидовы расстояния, что было бы труднее Проблема Вебера: среднее оптимизирует квадратичные ошибки, тогда как только геометрическая медиана минимизирует евклидовы расстояния. Например, лучшие евклидовы решения можно найти, используя k-медианы и k-medoids.

Задача сложна в вычислительном отношении (NP-жесткий ); однако эффективный эвристические алгоритмы быстро сходиться к локальный оптимум. Обычно они похожи на алгоритм максимизации ожидания за смеси из Гауссовские распределения с помощью итеративного подхода к уточнению, применяемого как k-означает и Моделирование гауссовой смеси. Оба они используют кластерные центры для моделирования данных; тем не мение, k- означает, что кластеризация имеет тенденцию находить кластеры сопоставимой пространственной протяженности, в то время как механизм максимизации ожидания позволяет кластерам иметь разные формы.

Алгоритм имеет слабое отношение к k-классификатор ближайшего соседа, популярный машинное обучение метод классификации, который часто путают с k-значит из-за названия. Применение классификатора 1-ближайшего соседа к центрам кластеров, полученным k-значит классифицирует новые данные по существующим кластерам. Это известно как классификатор ближайшего центроида или же Алгоритм Роккио.

Описание

Учитывая набор наблюдений (Икс₁, Икс₂, ..., Икс_п), где каждое наблюдение представляет собой d-мерный действительный вектор, k-смысл кластеризации направлен на разделение п наблюдения в k (≤ п) наборы S = {S₁, S₂, ..., S_k}, чтобы минимизировать сумму квадратов внутри кластера (WCSS) (т.е. отклонение ). Формально цель - найти:

${\displaystyle {\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}}$

куда μ_я среднее значение точек в S_я. Это эквивалентно минимизации попарных квадратов отклонений точек в одном кластере:

${\displaystyle {\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\,{\frac {1}{2|S_{i}|}}\,\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}}$

Эквивалентность можно вывести из тождества ${\displaystyle \sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}=\sum _{\mathbf {x} \neq \mathbf {y} \in S_{i}}(\mathbf {x} -{\boldsymbol {\mu }}_{i})({\boldsymbol {\mu }}_{i}-\mathbf {y} )}$. Поскольку общая дисперсия постоянна, это эквивалентно максимизации суммы квадратов отклонений между точками в разные кластеры (межкластерная сумма квадратов, BCSS),^[1] что следует из закон полной дисперсии.

История

Период, термин "k-средства "впервые использовал Джеймс Маккуин в 1967 году,^[2] хотя идея восходит к Хьюго Штайнхаус в 1956 г.^[3] Стандартный алгоритм был впервые предложен Стюартом Ллойдом из Bell Labs в 1957 г. как техника для импульсно-кодовая модуляция, хотя она не публиковалась как журнальная статья до 1982 года.^[4] В 1965 году Эдвард В. Форги опубликовал, по сути, тот же метод, поэтому его иногда называют алгоритмом Ллойда – Форги.^[5]

Алгоритмы

Стандартный алгоритм (наивное k-среднее)

Конвергенция k-средства

Наиболее распространенный алгоритм использует метод итеративного уточнения. Из-за его повсеместного распространения его часто называют k-значит алгоритм "; его также называют Алгоритм Ллойда, особенно в сообществе компьютерных наук. Иногда это также называют "наивным k-средства », потому что существуют гораздо более быстрые альтернативы.^[6]

Учитывая начальный набор k средства м₁⁽¹⁾,...,м_k⁽¹⁾ (см. ниже) алгоритм работает, чередуя два шага:^[7]

Шаг присвоения: Назначьте каждое наблюдение в кластер с ближайшим средним: с наименьшим квадратом Евклидово расстояние.^[8] (Математически это означает разделение наблюдений в соответствии с Диаграмма Вороного генерируется средствами.)

${\displaystyle S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-m_{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}},}$

где каждый ${\displaystyle x_{p}}$ присваивается ровно одному ${\displaystyle S^{(t)}}$, даже если он может быть назначен двум или более из них.

Шаг обновления: Пересчитать означает (центроиды ) для наблюдений, назначенных каждому кластеру.

${\displaystyle m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$

Алгоритм сойдется, когда назначения больше не меняются. Не гарантируется, что алгоритм найдет оптимум.^[9]

Алгоритм часто представляется как отнесение объектов к ближайшему кластеру по расстоянию. Использование другой функции расстояния, отличной от (возведенного в квадрат) евклидова расстояния, может препятствовать сходимости алгоритма. Различные модификации k-средства типа сферические k-средства и k-медоиды были предложены для использования других мер расстояния.

Методы инициализации

Обычно используемые методы инициализации - это Forgy и Random Partition.^[10] Метод Forgy случайным образом выбирает k наблюдения из набора данных и использует их в качестве начальных средств. Метод случайного разбиения сначала случайным образом назначает кластер каждому наблюдению, а затем переходит к этапу обновления, таким образом вычисляя начальное среднее значение как центроид случайно назначенных точек кластера. Метод Forgy имеет тенденцию разбрасывать начальные средние, в то время как Random Partition помещает их все ближе к центру набора данных. Согласно Hamerly et al.,^[10] метод случайного разбиения обычно предпочтительнее для таких алгоритмов, как k-гармонические средства и нечеткие k-средства. Для максимизации ожиданий и стандартов k-смысл алгоритмов, метод инициализации Forgy предпочтительнее. Всестороннее исследование Celebi et al.,^[11] однако было обнаружено, что популярные методы инициализации, такие как Forgy, Random Partition и Maximin, часто работают плохо, тогда как подход Брэдли и Файяда^[12] выступает «стабильно» в «лучшей группе» и k-значит ++ работает "в целом хорошо".

• Демонстрация стандартного алгоритма
• 

  1. k начальное "означает" (в данном случае k= 3) случайным образом генерируются в области данных (показаны цветом).

• 

  2. k кластеры создаются путем связывания каждого наблюдения с ближайшим средним. Перегородки здесь представляют собой Диаграмма Вороного генерируется средствами.

• 

  3. В центроид каждого из k кластеры становятся новым средним.

• 

  4. Шаги 2 и 3 повторяются до достижения сходимости.

Алгоритм не гарантирует сходимости к глобальному оптимуму. Результат может зависеть от начальных кластеров. Поскольку алгоритм обычно быстрый, его обычно запускают несколько раз с разными начальными условиями. Однако производительность в худшем случае может быть медленной: в частности, определенные наборы точек, даже в двух измерениях, сходятся за экспоненциальное время, то есть 2^{Ω (п)}.^[13] Эти наборы точек, похоже, не возникают на практике: это подтверждается тем фактом, что сглаженный время работы k-средство полиномиально.^[14]

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

Сложность

Поиск оптимального решения k-значит проблему кластеризации наблюдений в d размеры:

• NP-жесткий в целом Евклидово пространство (из d габариты) даже для двух кластеров,^{[15][16][17][18]}
• NP-жесткий для общего количества кластеров k даже в самолете,^[19]
• если k и d (размерность) фиксированы, задача может быть решена точно в срок ${\displaystyle O(n^{dk+1})}$, куда п - количество объектов для кластеризации.^[20]

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

Время работы алгоритма Ллойда (и большинства его вариантов) составляет ${\displaystyle O(nkdi)}$,^[9][21] куда:

• п это количество d-мерные векторы (для кластеризации)
• k количество кластеров
• я количество итераций, необходимых до сходимости.

Для данных, которые имеют структуру кластеризации, количество итераций до сходимости часто невелико, и результаты улучшаются лишь незначительно после первой дюжины итераций. Поэтому алгоритм Ллойда на практике часто считается «линейным» сложным, хотя худший случай суперполином при выполнении до сходимости.^[22]

• В худшем случае алгоритм Ллойда нуждается в ${\displaystyle i=2^{\Omega ({\sqrt {n}})}}$ итераций, так что наихудшая сложность алгоритма Ллойда равна суперполином.^[22]
• Ллойда k-смысл алгоритма имеет полиномиально сглаженное время работы. Показано, что^[14] для произвольного набора п указывает в ${\displaystyle [0,1]^{d}}$, если каждая точка независимо возмущается нормальным распределением со средним 0 и дисперсия ${\displaystyle \sigma ^{2}}$, то ожидаемое время работы k-средний алгоритм ограничен ${\displaystyle O(n^{34}k^{34}d^{8}\log ^{4}(n)/\sigma ^{6})}$, который является полиномом от п, k, d и ${\displaystyle 1/\sigma }$.
• Лучшие оценки доказаны для простых случаев. Например, показано, что время работы k-средний алгоритм ограничен ${\displaystyle O(dn^{4}M^{2})}$ за п указывает в целочисленная решетка ${\displaystyle \{1,\dots ,M\}^{d}}$.^[23]

Алгоритм Ллойда - стандартный подход к этой проблеме. Однако он тратит много времени на вычисление расстояний между каждым из k центров кластера и n точками данных. Поскольку точки обычно остаются в одних и тех же кластерах после нескольких итераций, большая часть этой работы не нужна, что делает наивную реализацию очень неэффективной. Некоторые реализации используют кэширование и неравенство треугольника для создания границ и ускорения алгоритма Ллойда.^{[9][24][25][26][27]}

Вариации

• Оптимизация естественных перерывов Дженкса: k-средства, применяемые к одномерным данным
• kкластеризация медианы использует медиану в каждом измерении вместо среднего, и таким образом минимизирует ${\displaystyle L_{1}}$ норма (Геометрия такси ).
• k-медоиды (также: Partitioning Around Medoids, PAM) использует medoid вместо среднего, и таким образом минимизирует сумму расстояний для произвольный функции расстояния.
• Кластеризация нечетких C-средних это мягкая версия k- означает, что каждая точка данных имеет нечеткую степень принадлежности к каждому кластеру.
• Гауссова смесь модели обучены с алгоритм максимизации ожидания (Алгоритм EM) поддерживает вероятностные назначения кластерам вместо детерминированных назначений и многомерные гауссовские распределения вместо средних.
• k-значит ++ выбирает начальные центры таким образом, чтобы получить доказуемую верхнюю границу цели WCSS.
• Алгоритм фильтрации использует kd-деревья чтобы ускорить каждый k-значит шаг.^[28]
• Некоторые методы пытаются ускорить каждый k- означает шаг с использованием неравенство треугольника.^{[24][25][26][29][27]}
• Избегайте локальных оптимумов, меняя точки между кластерами.^[9]
• Сферический k-значит алгоритм кластеризации подходит для текстовых данных.^[30]
• Иерархические варианты, например, деление пополам k-средства,^[31] X-означает кластеризацию^[32] и G-средства кластеризации^[33] многократно разбивать кластеры для построения иерархии, а также может попытаться автоматически определить оптимальное количество кластеров в наборе данных.
• Оценка внутреннего кластера такие меры, как силуэт кластера может быть полезным в определение количества кластеров.
• Минковского взвешенный k-means автоматически вычисляет веса конкретных характеристик кластера, поддерживая интуитивно понятную идею о том, что функция может иметь разную степень релевантности для разных функций.^[34] Эти веса также можно использовать для изменения масштаба данного набора данных, увеличивая вероятность того, что индекс достоверности кластера будет оптимизирован при ожидаемом количестве кластеров.^[35]
• Мини-партия k-средства: k- означает изменение с использованием «мини-пакетных» выборок для наборов данных, которые не помещаются в памяти.^[36]

Метод Хартигана – Вонга

Метод Хартигана и Вонга^[9] предоставляет вариант k- означает алгоритм, который приближается к локальному минимуму задачи минимальной суммы квадратов с различными обновлениями решения. Метод представляет собой местный поиск который итеративно пытается переместить образец в другой кластер, пока этот процесс улучшает целевую функцию. Когда ни один образец не может быть перемещен в другой кластер с улучшением цели, метод останавливается (в локальном минимуме). Аналогично классическому k- означает, что этот подход остается эвристическим, поскольку он не обязательно гарантирует, что окончательное решение будет оптимальным в глобальном масштабе.

Позволять ${\displaystyle \varphi (S_{j})}$ быть индивидуальной стоимостью ${\displaystyle S_{j}}$ определяется ${\displaystyle \sum _{x\in S_{j}}(x-\mu _{j})^{2}}$, с ${\displaystyle \mu _{j}}$ центр кластера.

Шаг присвоения: Метод Хартигана и Вонга начинается с разделения точек на случайные кластеры. ${\displaystyle \{S_{j}\}_{j\in \{1,\cdots k\}}}$.

Шаг обновления: Затем он определяет ${\displaystyle n,m\in \{1,\ldots ,k\}}$ и ${\displaystyle x\in S_{n}}$ для которого следующая функция достигает максимума

${\displaystyle \Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\smallsetminus \{x\})-\varphi (S_{m}\cup \{x\}).}$

Для ${\displaystyle x,n,m}$ которые достигают этого минимума, ${\displaystyle x}$ переходит из кластера ${\displaystyle S_{n}}$ в кластер ${\displaystyle S_{m}}$.

Прекращение: Алгоритм завершается один раз ${\displaystyle \Delta (m,n,x)}$ больше нуля для всех ${\displaystyle x,n,m}$.

Могут использоваться разные стратегии принятия ходов. В первое улучшение стратегия, любое улучшающее перемещение может быть применено, тогда как в лучшее улучшение стратегии, все возможные перемещения тестируются итеративно, и на каждой итерации применяется только лучшее. Первый подход способствует скорости, независимо от того, способствует ли последний подход в целом качеству решения за счет дополнительного времени вычислений. Функция ${\displaystyle \Delta }$ используемый для расчета результата перемещения, также можно эффективно оценить, используя равенство^[37]

${\displaystyle \Delta (x,n,m)={\frac {\mid S_{n}\mid }{\mid S_{n}\mid -1}}\cdot \lVert \mu _{n}-x\rVert ^{2}-{\frac {\mid S_{m}\mid }{\mid S_{m}\mid +1}}\cdot \lVert \mu _{m}-x\rVert ^{2}.}$

Глобальная оптимизация и метаэвристика

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

${\displaystyle {\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}.}$

Во многих исследованиях предпринимались попытки улучшить поведение алгоритма сходимости и максимизировать шансы на достижение глобального оптимума (или, по крайней мере, локальных минимумов лучшего качества). Методы инициализации и перезапуска, рассмотренные в предыдущих разделах, являются одной из альтернатив для поиска лучших решений. Совсем недавно алгоритмы математического программирования, основанные на разветвленный и генерация столбца разработали «проверенно оптимальные» решения для наборов данных, содержащих до 2300 объектов.^[38] Как и ожидалось, из-за NP-твердость В приведенной ниже задаче оптимизации время вычисления оптимальных алгоритмов для K-средних быстро превышает этот размер. Оптимальные решения для малых и средних предприятий по-прежнему ценны в качестве эталонного инструмента для оценки качества других эвристик. Чтобы найти локальные минимумы высокого качества за контролируемое время вычислений, но без гарантий оптимальности, в других работах исследовались метаэвристика и другие глобальная оптимизация методы, например, основанные на инкрементальных подходах и выпуклой оптимизации,^[39] случайные свопы^[40] (т.е. повторный локальный поиск ), поиск переменного района^[41]и генетические алгоритмы.^[42][43] Действительно, известно, что нахождение лучших локальных минимумов задачи кластеризации с минимальной суммой квадратов может иметь значение между неудачей и успехом восстановления кластерных структур в пространствах признаков высокой размерности.^[43]

Обсуждение

Типичный пример k- означает сходимость к локальному минимуму. В этом примере результат k- означает, что кластеризация (правый рисунок) противоречит очевидной кластерной структуре набора данных. Маленькие кружки - это точки данных, четыре лучевых звезды - это центроиды (средние). Начальная конфигурация представлена ​​на левом рисунке. Алгоритм сходится после пяти итераций, представленных на рисунках слева направо. Иллюстрация была подготовлена ​​с помощью Java-апплета Mirkes.^[44]

k- означает результат кластеризации для Набор данных о цветке ириса и реальные виды, визуализированные с помощью ELKI. Кластерные средние обозначены более крупными полупрозрачными символами.

k- означает кластеризацию vs. EM кластеризация на искусственном наборе данных («мышь»). Тенденция k-средства для создания кластеров одинакового размера приводят к плохим результатам здесь, в то время как EM выигрывает от гауссовых распределений с различным радиусом, присутствующим в наборе данных.

Три ключевые особенности k-средства, которые делают его эффективным, часто считаются его самым большим недостатком:

• Евклидово расстояние используется как метрика и отклонение используется как мера кластерного разброса.
• Количество кластеров k является входным параметром: неправильный выбор k может дать плохие результаты. Поэтому при исполнении k- значит, важно проводить диагностические проверки для определение количества кластеров в наборе данных.
• Сходимость к локальному минимуму может привести к противоречивым («неправильным») результатам (см. Пример на рис.).

Ключевое ограничение k-смыслом является его кластерная модель. Концепция основана на сферических кластерах, которые можно разделить, так что среднее значение сходится к центру кластера. Ожидается, что кластеры будут одинакового размера, так что назначение ближайшему центру кластера будет правильным. Например, когда применяется k-средства стоимостью ${\displaystyle k=3}$ на хорошо известные Набор данных о цветке ириса, результат часто не может разделить три Ирис виды, содержащиеся в наборе данных. С ${\displaystyle k=2}$, будут обнаружены два видимых кластера (один, содержащий два вида), тогда как с ${\displaystyle k=3}$ один из двух кластеров будет разделен на две четные части. Фактически, ${\displaystyle k=2}$ более подходит для этого набора данных, несмотря на то, что набор данных содержит 3 классы. Как и любой другой алгоритм кластеризации, k- означает, что результат предполагает, что данные удовлетворяют определенным критериям. Он хорошо работает с некоторыми наборами данных и не работает с другими.

Результат k-средства можно рассматривать как Клетки Вороного кластерных средств. Поскольку данные распределяются посередине между средними кластерами, это может привести к неоптимальному разбиению, как можно увидеть в примере с «мышью». Гауссовские модели, используемые алгоритм максимизации ожидания (возможно, обобщение k-средства) более гибкие, имея как дисперсии, так и ковариации. Таким образом, результат ЭМ позволяет приспособить кластеры переменного размера намного лучше, чем k-значит, а также коррелированные кластеры (не в этом примере). Напротив, EM требует оптимизации большего числа свободных параметров и создает некоторые методологические проблемы из-за исчезающих кластеров или плохо обусловленных ковариационных матриц. K-средство тесно связано с непараметрическими Байесовское моделирование.^[45]

Приложения

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

Векторное квантование

Основная статья: Векторное квантование

Двухканальное (для наглядности - только красный и зеленый каналы) цветное изображение.

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

k-средство происходит от обработки сигналов и до сих пор находит применение в этой области. Например, в компьютерная графика, цветное квантование это задача сокращения цветовая палитра изображения на фиксированное количество цветов k. В k-значит алгоритм легко может быть использован для этой задачи и дает конкурентоспособные результаты. Пример использования этого подхода: сегментация изображений. Другие варианты использования векторного квантования включают: неслучайная выборка, так как k-средства легко можно использовать для выбора k различные, но прототипы объектов из большого набора данных для дальнейшего анализа.

Кластерный анализ

Основная статья: Кластерный анализ

В кластерном анализе k-средний алгоритм может быть использован для разделения набора входных данных на k перегородки (кластеры).

Однако чистый k- означает, что алгоритм не очень гибкий и, как таковой, имеет ограниченное использование (за исключением случаев, когда векторное квантование, как указано выше, на самом деле является желаемым вариантом использования). В частности, параметр k известно, что его трудно выбрать (как обсуждалось выше), если он не задан внешними ограничениями. Еще одно ограничение заключается в том, что его нельзя использовать с произвольными функциями расстояния или нечисловыми данными. Для этих случаев использования многие другие алгоритмы лучше.

Особенности обучения

k- означает, что кластеризация использовалась как особенности обучения (или же изучение словаря ) шаг, либо в (полу- )контролируемое обучение или же обучение без учителя.^[46] Основной подход - сначала обучить k- означает представление кластеризации с использованием входных обучающих данных (которые не нужно маркировать). Затем, чтобы проецировать любые входные данные в новое пространство признаков, функция "кодирования", такая как пороговое матричное произведение датума с местоположениями центроидов, вычисляет расстояние от точки данных до каждого центроида или просто индикаторная функция для ближайший центроид,^[46][47] или какое-то плавное преобразование расстояния.^[48] В качестве альтернативы, преобразование расстояния образец-кластер через Гауссовский RBF, получает скрытый слой сеть радиальных базисных функций.^[49]

Это использование k-средство удачно сочетается с простым, линейные классификаторы для полу-контролируемого обучения в НЛП (специально для признание названного лица )^[50] И в компьютерное зрение. Было обнаружено, что в задаче распознавания объектов он демонстрирует сопоставимую производительность с более сложными подходами к изучению функций, такими как автокодеры и ограниченные машины Больцмана.^[48] Однако обычно требуется больше данных для эквивалентной производительности, потому что каждая точка данных вносит вклад только в одну «функцию».^[46]

Отношение к другим алгоритмам

Модель гауссовой смеси

Основная статья: Модель гауссовой смеси

Медленный «стандартный алгоритм» для k- означает кластеризацию и связанные с ней алгоритм максимизации ожидания, является частным случаем модели гауссовой смеси, а именно предельным случаем, когда все ковариации фиксируются диагональными, равными и имеют бесконечно малую дисперсию.^[51]:850 Вместо небольших отклонений можно также использовать назначение жесткого кластера, чтобы показать другую эквивалентность k- означает кластеризацию в частный случай моделирования «жесткой» гауссовой смеси.^{[52](11.4.2.5)} Это не означает, что эффективно использовать моделирование гауссовой смеси для вычисления k-значит, но только то, что существует теоретическая взаимосвязь, и что моделирование гауссовой смеси можно интерпретировать как обобщение k-средства; напротив, было предложено использовать кластеризацию k-средних, чтобы найти отправные точки для моделирования гауссовой смеси на сложных данных.^[51]:849

К-СВД

Основная статья: К-СВД

Еще одно обобщение kАлгоритм -средний - это алгоритм K-SVD, который оценивает точки данных как разреженную линейную комбинацию «векторов кодовой книги». k-средство соответствует частному случаю использования одного вектора кодовой книги с весом 1.^[53]

Анализ главных компонентов

Основная статья: Анализ главных компонентов

Расслабленное решение k- означает кластеризацию, определяемую индикаторами кластера, с помощью анализа главных компонентов (PCA).^[54][55] Интуиция такова, что k-средства описывают скопления сферической (шарообразной) формы. Если данные имеют 2 кластера, линия, соединяющая два центроида, является лучшим направлением одномерной проекции, которое также является первым направлением PCA. Разрезание линии в центре масс разделяет кластеры (это непрерывная релаксация дискретного индикатора кластера). Если данные имеют три кластера, двумерная плоскость, охватываемая тремя центроидами кластера, является лучшей двумерной проекцией. Эта плоскость также определяется первыми двумя размерами PCA. Хорошо разделенные кластеры эффективно моделируются кластерами в форме шара и, таким образом, обнаруживаются k-средства. Грозди, не имеющие формы шара, трудно разделить, когда они расположены близко. Например, два скопления в форме полумесяца, переплетенные в пространстве, плохо разделяются при проецировании на подпространство PCA. k-средства не должны преуспевать на этих данных.^[56] Несложно привести контрпримеры к утверждению, что подпространство центроида кластера охватывает основные направления.^[57]

Кластеризация среднего сдвига

Основная статья: Средний сдвиг

Базовые алгоритмы кластеризации среднего сдвига поддерживают набор точек данных того же размера, что и набор входных данных. Первоначально этот набор копируется из входного набора. Затем этот набор итеративно заменяется средним значением тех точек в наборе, которые находятся на заданном расстоянии от этой точки. Напротив, k- означает, что этот обновленный набор ограничен k точек обычно намного меньше, чем количество точек во входном наборе данных, и заменяет каждую точку в этом наборе средним значением всех точек в входной набор которые находятся ближе к этой точке, чем к любой другой (например, в разделе Вороного каждой точки обновления). Алгоритм среднего сдвига, который похож на k-значит, называется вероятность среднего сдвига, заменяет набор точек, подлежащих замене, на среднее значение всех точек во входном наборе, которые находятся на заданном расстоянии от изменяющегося набора.^[58] Одно из преимуществ среднего сдвига над k- означает, что количество кластеров не указывается заранее, потому что средний сдвиг, скорее всего, приведет к обнаружению только нескольких кластеров, если существует только небольшое их количество. Однако средний сдвиг может быть намного медленнее, чем k-значит, и по-прежнему требует выбора параметра полосы пропускания. Среднее смещение имеет мягкие варианты.

Независимый компонентный анализ

Основная статья: Независимый компонентный анализ

При предположении о разреженности и при предварительной обработке входных данных с помощью отбеливающее преобразование, k-means производит решение задачи линейного анализа независимых компонентов (ICA). Это помогает объяснить успешное применение k-значит особенности обучения.^[59]

Двусторонняя фильтрация

Основная статья: Двусторонний фильтр

k-means неявно предполагает, что порядок набора входных данных не имеет значения. Двусторонний фильтр похож на k-средства и средний сдвиг в том, что он поддерживает набор точек данных, которые итеративно заменяются средствами. Однако двусторонний фильтр ограничивает вычисление среднего (взвешенного по ядру), чтобы включать только точки, которые близки по порядку входных данных.^[58] Это делает его применимым к таким проблемам, как шумоподавление изображения, где пространственное расположение пикселей в изображении имеет решающее значение.

Подобные проблемы

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

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

Различные реализации алгоритма демонстрируют различия в производительности: самая быстрая из тестовых данных завершается за 10 секунд, самая медленная - за 25 988 секунд (~ 7 часов).^[1] Различия можно объяснить качеством реализации, языками и различиями компиляторов, разными критериями завершения и уровнями точности, а также использованием индексов для ускорения.

Бесплатное программное обеспечение / открытый исходный код

Следующие реализации доступны в Бесплатное / открытое программное обеспечение лицензии с общедоступным исходным кодом.

• Accord.NET содержит реализации C # для k-средства, k-значит ++ и k-режимы.
• АЛГЛИБ содержит параллельные реализации C ++ и C # для k-средства и k-значит ++.
• AOSP содержит реализацию Java для k-средства.
• CrimeStat реализует два пространственных k- означает алгоритмы, один из которых позволяет пользователю определять начальные местоположения.
• ELKI содержит k-средства (с итерацией Ллойда и Маккуина, а также с различными инициализациями, такими как k-means ++ initialization) и различные более продвинутые алгоритмы кластеризации.
• Улыбка содержит k-средства и многие другие алгоритмы и визуализация результатов (для java, kotlin и scala).
• Юля содержит k- означает реализацию в пакете JuliaStats Clustering.
• KNIME содержит узлы для k-средства и k-медоиды.
• Mahout содержит Уменьшение карты основан k-средства.
• mlpack содержит реализацию на C ++ k-средства.
• Октава содержит k-средства.
• OpenCV содержит k- означает реализацию.
• апельсин включает компонент для k-средства кластеризации с автоматическим выбором k и оценка силуэта кластера.
• PSPP содержит k-значит, команда БЫСТРЫЙ КЛАСТЕР выполняет k-значит кластеризацию по набору данных.
• р содержит три k-значит вариации.
• SciPy и scikit-learn содержать несколько k- означает реализации.
• Искра MLlib реализует распределенную k- означает алгоритм.
• Факел содержит неподготовленный пакет, который предоставляет k- означает кластеризацию.
• Weka содержит k-средства и Икс-средства.

Проприетарный

Следующие реализации доступны в проприетарный условия лицензии и может не иметь общедоступного исходного кода.

• Аясди
• Mathematica
• MATLAB
• OriginPro
• RapidMiner
• SAP HANA
• SAS
• SPSS
• Stata

Смотрите также

• Алгоритм BFR
• Центроидная мозаика Вороного
• Голова / хвост ломается
• k кв. квартир
• K-означает ++
• Алгоритм Линде – Бузо – Грея
• Самоорганизующаяся карта

Рекомендации

1. Кригель, Ханс-Петер; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки времени выполнения: сравниваем ли мы алгоритмы или реализации?». Знания и информационные системы. 52 (2): 341–378. Дои:10.1007 / s10115-016-1004-2. ISSN  0219-1377. S2CID  40772241.
2. Маккуин, Дж. Б. (1967). Некоторые методы классификации и анализа многомерных наблюдений. Труды 5-го симпозиума Беркли по математической статистике и теории вероятностей. 1. Калифорнийский университет Press. С. 281–297. МИСТЕР  0214227. Zbl  0214.46201. Получено 2009-04-07.
3. Штайнхаус, Гюго (1957). "Sur la division des corps matériels en party". Бык. Акад. Полон. Sci. (На французском). 4 (12): 801–804. МИСТЕР  0090073. Zbl  0079.16403.
4. Ллойд, Стюарт П. (1957). «Квантование по методу наименьших квадратов в PCM». Бумага Bell Telephone Laboratories. Значительно позже опубликовано в журнале: Ллойд, Стюарт П. (1982). «Квантование методом наименьших квадратов в PCM» (PDF). IEEE Transactions по теории информации. 28 (2): 129–137. CiteSeerX  10.1.1.131.1338. Дои:10.1109 / TIT.1982.1056489. Получено 2009-04-15.
5. Форджи, Эдвард В. (1965). «Кластерный анализ многомерных данных: эффективность против интерпретируемости классификаций». Биометрия. 21 (3): 768–769. JSTOR  2528559.
6. Пеллег, Дэн; Мур, Эндрю (1999). «Ускорение точных алгоритмов k-средних с помощью геометрических рассуждений». Труды Пятой Международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных - KDD '99. Сан-Диего, Калифорния, США: ACM Press: 277–281. Дои:10.1145/312129.312248. ISBN  9781581131437. S2CID  13907420.
7. Маккей, Дэвид (2003). «Глава 20. Пример задачи вывода: кластеризация» (PDF). Теория информации, логические выводы и алгоритмы обучения. Издательство Кембриджского университета. С. 284–292. ISBN  978-0-521-64298-9. МИСТЕР  2012999.
8. Поскольку квадратный корень является монотонной функцией, это также минимальное присвоение евклидова расстояния.
9. Hartigan, J. A .; Вонг, М.А. (1979). "Алгоритм AS 136: A k-Алгоритм кластеризации средств ». Журнал Королевского статистического общества, серия C. 28 (1): 100–108. JSTOR  2346830.
10. Хэмерли, Грег; Элкан, Чарльз (2002). "Альтернативы k-смысл алгоритма, который находит лучшие кластеры " (PDF). Материалы одиннадцатой международной конференции по управлению информацией и знаниями (CIKM).
11. Селеби, М. Э .; Kingravi, H.A .; Вела, П. А. (2013). "Сравнительное исследование эффективных методов инициализации для k-значит алгоритм кластеризации ». Экспертные системы с приложениями. 40 (1): 200–210. arXiv:1209.1960. Дои:10.1016 / j.eswa.2012.07.021. S2CID  6954668.
12. Брэдли, Пол С .; Файяд, Усама М. (1998). "Уточнение начальных точек для k-Кластеризация средств ». Материалы Пятнадцатой Международной конференции по машинному обучению.
13. Ваттани, А. (2011). «k-means требует экспоненциально много итераций даже в плоскости» (PDF). Дискретная и вычислительная геометрия. 45 (4): 596–616. Дои:10.1007 / s00454-011-9340-1. S2CID  42683406.
14. Артур, Дэвид; Manthey, B .; Роглин, Х. (2009). «k-means имеет полиномиально сглаженную сложность». Материалы 50-го симпозиума по основам информатики (FOCS). arXiv:0904.1113.
15. Гарей, М .; Johnson, D .; Витсенхаузен, Х. (1982-03-01). «Сложность обобщенной проблемы Ллойда - Макса (Корр.)». IEEE Transactions по теории информации. 28 (2): 255–256. Дои:10.1109 / TIT.1982.1056488. ISSN  0018-9448.
16. Клейнберг, Джон; Пападимитриу, Христос; Рагхаван, Прабхакар (1998-12-01). «Микроэкономический взгляд на интеллектуальный анализ данных». Интеллектуальный анализ данных и обнаружение знаний. 2 (4): 311–324. Дои:10.1023 / А: 1009726428407. ISSN  1384-5810. S2CID  15252504.
17. Aloise, D .; Deshpande, A .; Hansen, P .; Попат П. (2009). «NP-твердость евклидовой кластеризации по сумме квадратов». Машинное обучение. 75 (2): 245–249. Дои:10.1007 / s10994-009-5103-0.
18. Dasgupta, S .; Фройнд, Ю. (июль 2009 г.). «Деревья случайных проекций для векторного квантования». IEEE Transactions по теории информации. 55 (7): 3229–3242. arXiv:0805.1390. Дои:10.1109 / TIT.2009.2021326. S2CID  666114.
19. Махаджан, Мина; Нимбхоркар, Праджакта; Варадараджан, Кастури (2009). Планар k-Средняя проблема NP-Hard. Конспект лекций по информатике. 5431. С. 274–285. CiteSeerX  10.1.1.331.1306. Дои:10.1007/978-3-642-00202-1_24. ISBN  978-3-642-00201-4.
20. Inaba, M .; Katoh, N .; Имаи, Х. (1994). Применение взвешенных диаграмм Вороного и рандомизации к дисперсионным k-кластеризация. Материалы 10-го симпозиума ACM по вычислительной геометрии. С. 332–339. Дои:10.1145/177424.178042.
21. Мэннинг, Кристофер Д.; Рагхаван, Прабхакар; Шютце, Хинрих (2008). Введение в поиск информации. Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0521865715. OCLC  190786122.
22. Артур, Дэвид; Васильвицкий, Сергей (01.01.2006). Как медленно k-смысл Метод?. Материалы двадцать второго ежегодного симпозиума по вычислительной геометрии. SCG '06. Нью-Йорк, Нью-Йорк, США: ACM. С. 144–153. Дои:10.1145/1137856.1137880. ISBN  978-1595933409. S2CID  3084311.
23. Бхоумик, Абхишек (2009). "Теоретический анализ алгоритма Ллойда для k-средства кластеризации " (PDF). Архивировано из оригинал (PDF) на 2015-12-08. Смотрите также здесь.
24. Филлипс, Стивен Дж. (2002-01-04). «Ускорение K-средних и связанных алгоритмов кластеризации». В Маунт, Дэвид М .; Стейн, Клиффорд (ред.). Ускорение k-Средства и связанные алгоритмы кластеризации. Конспект лекций по информатике. 2409. Springer Berlin Heidelberg. С. 166–177. Дои:10.1007/3-540-45643-0_13. ISBN  978-3-540-43977-6.
25. Элкан, Чарльз (2003). "Использование неравенства треугольника для ускорения k-средства" (PDF). Материалы двадцатой Международной конференции по машинному обучению (ICML).
26. Хамерли, Грег. "Изготовление k-значит еще быстрее ». CiteSeerX  10.1.1.187.3017.
27. Хэмерли, Грег; Дрейк, Джонатан (2015). Ускорение алгоритма Ллойда для k-средства кластеризации. Алгоритмы частичной кластеризации. С. 41–78. Дои:10.1007/978-3-319-09259-1_2. ISBN  978-3-319-09258-4.
28. Канунго, Тапас; Маунт, Дэвид М.; Нетаньяху, Натан С.; Пятко, Кристина Д.; Сильверман, Рут; Ву, Анджела Ю. (2002). "Эффективный kАлгоритм кластеризации средств: Анализ и реализация » (PDF). IEEE Transactions по анализу шаблонов и машинному анализу. 24 (7): 881–892. Дои:10.1109 / TPAMI.2002.1017616. Получено 2009-04-24.
29. Дрейк, Джонатан (2012). "Ускоренный k-средство с адаптивными границами расстояния " (PDF). 5-й семинар NIPS по оптимизации для машинного обучения, OPT2012.
30. Dhillon, I. S .; Модха, Д. М. (2001). «Разложение понятий для больших разреженных текстовых данных с использованием кластеризации». Машинное обучение. 42 (1): 143–175. Дои:10.1023 / а: 1007612920971.
31. Steinbach, M .; Karypis, G .; Кумар, В. (2000). ""Сравнение методов кластеризации документов ". В". KDD Workshop по интеллектуальному анализу текста. 400 (1): 525–526.
32. Pelleg, D .; И Мур, А. В. (2000, июнь). "X-означает: расширение k-средства с эффективной оценкой количества кластеров ". В ICML, Vol. 1
33. Хэмерли, Грег; Элкан, Чарльз (2004). «Изучение k в k-средних» (PDF). Достижения в системах обработки нейронной информации. 16: 281.
34. Amorim, R.C .; Миркин Б. (2012). "Метрика Минковского, взвешивание признаков и инициализация аномального кластера в k-Кластеризация средств ». Распознавание образов. 45 (3): 1061–1075. Дои:10.1016 / j.patcog.2011.08.012.
35. Amorim, R.C .; Хенниг, К. (2015). «Восстановление количества кластеров в наборах данных с шумовыми характеристиками с использованием коэффициентов масштабирования функций». Информационные науки. 324: 126–145. arXiv:1602.06989. Дои:10.1016 / j.ins.2015.06.039. S2CID  315803.
36. Скалли, Дэвид (2010). "Интернет-масштаб k-средства кластеризации ". Материалы 19-й международной конференции во всемирной паутине.. ACM. стр. 1177–1178. Получено 2016-12-21.
37. Телгарский, Матус. «Метод Хартигана: k-смысл кластеризации без Вороного » (PDF).
38. Алоиза, Даниэль; Хансен, Пьер; Либерти, Лев (2012). «Улучшенный алгоритм генерации столбцов для кластеризации по минимальной сумме квадратов». Математическое программирование. 131 (1–2): 195–220. Дои:10.1007 / s10107-010-0349-7. S2CID  17550257.
39. Багиров, А. М .; Taheri, S .; Угон, Дж. (2016). «Негладкий подход программирования постоянного тока к задачам кластеризации с минимальной суммой квадратов». Распознавание образов. 53: 12–24. Дои:10.1016 / j.patcog.2015.11.011.
40. Френти, Паси (2018). «Эффективность кластеризации случайного свопа». Журнал больших данных. 5 (1): 1–21. Дои:10.1186 / s40537-018-0122-у.
41. Hansen, P .; Младенович, Н. (2001). «J-средство: новая эвристика локального поиска для кластеризации по минимальной сумме квадратов». Распознавание образов. 34 (2): 405–413. Дои:10.1016 / S0031-3203 (99) 00216-2.
42. Кришна, К .; Мурти, М. Н. (1999). «Генетический алгоритм k-средних». IEEE Transactions по системам, человеку и кибернетике, часть B: кибернетика. 29 (3): 433–439. Дои:10.1109/3477.764879. PMID  18252317.
43. Грибель, Даниил; Видаль, Тибо (2019). «HG-означает: масштабируемая гибридная метаэвристика для кластеризации с минимальной суммой квадратов». Распознавание образов. 88: 569–583. arXiv:1804.09813. Дои:10.1016 / j.patcog.2018.12.022. S2CID  13746584.
44. Миркс, Э. "К-означает и k-medoids апплет ". Получено 2 января 2016.
45. Кулис, Брайан; Джордан, Майкл И. (26.06.2012). Повторное посещение k-средства: новые алгоритмы через байесовские непараметрики (PDF). ICML. С. 1131–1138. ISBN  9781450312851.
46. Коутс, Адам; Нг, Эндрю Ю. (2012). "Обучающие представления функций с k-средства" (PDF). В Монтавоне, Дж .; Орр, Г. Б .; Мюллер, К.-Р. (ред.). Нейронные сети: хитрости торговли. Springer.
47. Чурка, Габриэлла; Танец, Кристофер С .; Fan, Lixin; Вилламовски, Ютта; Брей, Седрик (2004). Визуальная категоризация с помощью наборов ключевых точек (PDF). Семинар ECCV по статистическому обучению в компьютерном зрении.
48. Коутс, Адам; Ли, Хонглак; Нг, Эндрю Ю. (2011). Анализ однослойных сетей при неконтролируемом обучении функций (PDF). Международная конференция по искусственному интеллекту и статистике (AISTATS). Архивировано из оригинал (PDF) на 2013-05-10.
49. Швенкер, Фридхельм; Kestler, Hans A .; Пальма, Гюнтер (2001). «Три этапа обучения для сетей с радиальной базисной функцией». Нейронные сети. 14 (4–5): 439–458. CiteSeerX  10.1.1.109.312. Дои:10.1016 / s0893-6080 (01) 00027-2. PMID  11411631.
50. Линь, Деканг; У, Сяоюнь (2009). Кластеризация фраз для разборчивого обучения (PDF). Ежегодное собрание ACL и IJCNLP. С. 1030–1038.
51. Press, W. H .; Теукольский, С. А .; Vetterling, W. T .; Фланнери, Б. П. (2007). "Раздел 16.1. Модели гауссовой смеси и k-Кластеризация средств ». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк (Нью-Йорк): Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
52. Кевин П. Мерфи (2012). Машинное обучение: вероятностная перспектива. Кембридж, Массачусетс: MIT Press. ISBN  978-0-262-30524-2. OCLC  810414751.
53. Аарон, Михал; Элад, Майкл; Брукштейн, Альфред (2006). «K-SVD: алгоритм создания переполненных словарей для разреженного представления» (PDF). Транзакции IEEE при обработке сигналов. 54 (11): 4311. Bibcode:2006ITSP ... 54.4311A. Дои:10.1109 / TSP.2006.881199. S2CID  7477309.
54. Чжа, Хунъюань; Дин, Крис; Гу, Мин; Он, Сяофэн; Саймон, Хорст Д. (декабрь 2001 г.). "Спектральная релаксация для k-средства кластеризации » (PDF). Системы обработки нейронной информации, том 14 (NIPS 2001): 1057–1064.
55. Дин, Крис; Он, Сяофэн (июль 2004 г.). «К-означает кластеризацию с помощью анализа главных компонентов» (PDF). Труды международной конференции по машинному обучению (ICML 2004): 225–232.
56. Дриней, Петрос; Frieze, Alan M .; Каннан, Рави; Вемпала, Сантош; Винай, Вишванатан (2004). «Кластеризация больших графов с помощью разложения по сингулярным числам» (PDF). Машинное обучение. 56 (1–3): 9–33. Дои:10.1023 / b: mach.0000033113.59016.96. S2CID  5892850. Получено 2012-08-02.
57. Коэн, Майкл Б .; Старейшина, Сэм; Муско, Кэмерон; Муско, Кристофер; Персу, Мадалина (2014). "Снижение размерности для k- означает кластеризацию и приближение низкого ранга (Приложение B) ». arXiv:1410.6801 [cs.DS ].
58. Литтл, Макс А .; Джонс, Ник С. (2011). "Обобщенные методы и решатели для кусочно-постоянных сигналов: Часть I" (PDF). Труды Королевского общества А. 467 (2135): 3088–3114. Bibcode:2011RSPSA.467.3088L. Дои:10.1098 / rspa.2010.0671. ЧВК  3191861. PMID  22003312.
59. Винников, Алон; Шалев-Шварц, Шай (2014). «K-means восстанавливает фильтры ICA, когда независимых компонентов мало» (PDF). Труды Международной конференции по машинному обучению (ICML 2014).