k- означает кластеризацию

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

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

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

Описание [ править ]

Учитывая набор наблюдений ( x ₁ , x ₂ , ..., x _n ), где каждое наблюдение является d- мерным вещественным вектором, k- означает, что кластеризация направлена ​​на разделение n наблюдений на k (≤  n ) множеств 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}}$

где μ _i - среднее значение точек в S _i . Это эквивалентно минимизации попарных квадратов отклонений точек в одном кластере:

${\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}}$

Эквивалентность можно вывести из тождества . Поскольку общая дисперсия постоянна, это эквивалентно максимизации суммы квадратов отклонений между точками в разных кластерах (сумма квадратов между кластерами, BCSS) ^[1], что следует из закона общей дисперсии .${\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} )}$

История [ править ]

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

Алгоритмы [ править ]

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

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

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

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

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

где каждому назначается ровно один , даже если он может быть назначен двум или более из них.${\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 помещает их все ближе к центру набора данных. Согласно Хамерли и др. ^[10], метод случайного разбиения обычно предпочтительнее для таких алгоритмов, как k -гармонические средние и нечеткие k- средние. Для максимизации ожиданий и стандартовk -средних алгоритмов, предпочтительнее метод инициализации Forgy. Однако всестороннее исследование, проведенное Селеби и др. ^[11] , показало, что популярные методы инициализации, такие как Forgy, Random Partition и Maximin, часто работают плохо, тогда как подход Брэдли и Файяда ^[12] работает «последовательно» в «лучшей группе». а k -means ++ работает "в целом хорошо".

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

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

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

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

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

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

Сложность [ править ]

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

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

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

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

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

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

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

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

Варианты [ править ]

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

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

${\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 является входным параметром: неправильный выбор k может привести к плохим результатам. Вот почему при выполнении k- средних важно выполнять диагностические проверки для определения количества кластеров в наборе данных .
• Сходимость к локальному минимуму может привести к противоречивым («неправильным») результатам (см. Пример на рис.).

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

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

Приложения [ править ]

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 -medoids , подход, который заставляет центральную точку каждого кластера быть одной из фактических точек, то есть он использует medoids вместо центроидов .

Программные реализации [ править ]

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

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

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

• Accord.NET содержит реализации C # для k- средних, k- средних ++ и k- режимов.
• ALGLIB содержит параллельные реализации C ++ и C # для k- средних и k- средних ++.
• AOSP содержит реализацию на Java для k- средних.
• CrimeStat реализует два пространственных алгоритма k- средних, один из которых позволяет пользователю определять начальные местоположения.
• ELKI содержит k -средние (с итерациями Ллойда и Маккуина, а также различные инициализации, такие как инициализация k -means ++) и различные более сложные алгоритмы кластеризации.
• Smile содержит k -means и множество других алгоритмов и визуализации результатов (для java, kotlin и scala).
• Julia содержит реализацию k -means в пакете JuliaStats Clustering.
• KNIME содержит узлы для k- средних и k -медоидов.
• Mahout содержит k- средние на основе MapReduce .
• mlpack содержит реализацию k- средств на C ++ .
• Октава содержит k -средние.
• OpenCV содержит реализацию k -means.
• Orange включает компонент для кластеризации k- средних с автоматическим выбором k и оценки силуэта кластера.
• PSPP содержит k -средние. Команда QUICK CLUSTER выполняет кластеризацию k- средних значений для набора данных.
• R содержит три варианта k- средних.
• SciPy и scikit-learn содержат несколько реализаций k -means.
• Spark MLlib реализует распределенный алгоритм k- средних.
• Torch содержит пакет unsup , который обеспечивает кластеризацию k- средних.
• Weka содержит k -средние и x -средства.

Собственный [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]