кластеризация методом k-средних

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

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

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

При наличии набора наблюдений ( x ₁ , x ₂ , ..., x _n ) , где каждое наблюдение является -мерным действительным вектором, кластеризация k -средних направлена _​​на разбиение n наблюдений на k ( ≤ n ) наборов S = { S ₁ , S ₂ , ..., Sk } таким образом, чтобы минимизировать внутрикластерную сумму квадратов (WCSS) (т. е. дисперсию ). Формально цель состоит в том, чтобы найти: где μ _i - среднее значение (также называемое центроидом) точек в , т. е. - размер , а - обычная норма L ² . Это эквивалентно минимизации попарных квадратов отклонений точек в одном кластере: Эквивалентность может быть выведена из тождества . Поскольку общая дисперсия постоянна, это эквивалентно максимизации суммы квадратов отклонений между точками в разных кластерах (междукластерная сумма квадратов, BCSS). ^[1] Эта детерминированная связь также связана с законом полной дисперсии в теории вероятностей.${\displaystyle d}$$${\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}=\mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}}$$${\displaystyle S_{i}}$$${\displaystyle {\boldsymbol {\mu _{i}}}={\frac {1}{|S_{i}|}}\sum _{\mathbf {x} \in S_{i}}\mathbf {x} ,}$$${\displaystyle |S_{i}|}$${\displaystyle S_{i}}$${\displaystyle \|\cdot \|}$$${\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\,{\frac {1}{|S_{i}|}}\,\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}}$$${\textstyle |S_{i}|\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\frac {1}{2}}\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}}$

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

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

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

1. Шаг назначения : назначить каждое наблюдение кластеру с ближайшим средним значением: с наименьшим квадратом евклидова расстояния . ^[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)}}$
2. Шаг обновления : пересчитать средние значения ( центроиды ) для наблюдений, назначенных каждому кластеру.$${\displaystyle m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$$

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

Алгоритм сходится, когда назначения больше не меняются или, что эквивалентно, когда WCSS становится стабильным. Алгоритм не гарантирует нахождение оптимума. ^[9]

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

Псевдокод

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

определение  k_means_cluster ( k ,  points ): # Инициализация: выбрать k центроидов (Forgy, Random Partition и т. д.) центроиды  =  [ c1 ,  c2 ,  ... ,  ck ]  # Инициализация списка кластеров кластеры  =  [[]  для  _  в  диапазоне ( k )]  # Цикл до сходимости конвергентный  =  ложный пока  не  сошлись : # Очистить предыдущие кластеры кластеры  =  [[]  для  _  в  диапазоне ( k )]  # Назначаем каждую точку «ближайшему» центроиду для  точки  в  точках : distances_to_each_centroid  =  [ расстояние ( точка ,  центроид )  для  центроида  в  центроидах ] cluster_assignment  =  argmin ( расстояния_до_каждого_центроида ) кластеры [ кластер_назначение ] .append ( точка )​  # Рассчитать новые центроиды # (стандартная реализация использует среднее значение всех точек в # кластер для определения нового центроида) new_centroids  =  [ calcul_centroid ( cluster )  для  кластера  в  кластерах ]  конвергентный  =  ( new_centroids  ==  centroids ) центроиды  =  новые_центроиды  если  сходится : возврат  кластеров

Обычно используемые методы инициализации — это Forgy и Random Partition. ^[10] Метод Forgy случайным образом выбирает k наблюдений из набора данных и использует их в качестве начальных средних. Метод Random Partition сначала случайным образом назначает кластер каждому наблюдению, а затем переходит к шагу обновления, таким образом вычисляя начальное среднее значение, которое является центроидом случайно назначенных точек кластера. Метод Forgy имеет тенденцию разбрасывать начальные средние значения, в то время как Random Partition помещает все из них близко к центру набора данных. Согласно Hamerly et al., ^[10] метод Random Partition обычно предпочтительнее для таких алгоритмов, как 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]}
• NP-трудно для общего числа кластеров k даже в плоскости, ^[17]
• Если k и d (размерность) фиксированы, то задача может быть точно решена за время , где n — число объектов, которые необходимо сгруппировать. ^[18]${\displaystyle O(n^{dk+1})}$

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

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

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

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

• В худшем случае алгоритму Ллойда требуются итерации, так что сложность алгоритма Ллойда в худшем случае является суперполиномиальной . ^[20]${\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 точек в целочисленной решетке . ^[21]${\displaystyle O(dn^{4}M^{2})}$ ${\displaystyle \{1,\dots ,M\}^{d}}$

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

Нахождение оптимального количества кластеров ( k ) для кластеризации методом k -средних является важным шагом для обеспечения того, чтобы результаты кластеризации были значимыми и полезными. ^[26] Существует несколько методов определения подходящего количества кластеров. Вот некоторые из наиболее часто используемых методов:

• Метод локтя (кластеризация) : этот метод включает построение графика объясненной вариации как функции числа кластеров и выбор локтя кривой в качестве числа кластеров для использования. ^[27] Однако понятие «локтя» не является четко определенным, и известно, что оно не является надежным. ^[28]
• Силуэт (кластеризация) : Анализ силуэта измеряет качество кластеризации и дает представление о расстоянии разделения между полученными кластерами. ^[29] Более высокая оценка силуэта указывает на то, что объект хорошо соответствует своему собственному кластеру и плохо соответствует соседним кластерам.
• Статистика разрыва : Статистика разрыва сравнивает общую внутрикластерную вариацию для различных значений k с их ожидаемыми значениями при нулевом эталонном распределении данных. ^[30] Оптимальное значение k — это значение, которое дает наибольшую статистику разрыва.
• Индекс Дэвиса-Боулдина : Индекс Дэвиса-Боулдина является мерой того, насколько велико разделение между кластерами. ^[31] Более низкие значения индекса Дэвиса-Боулдина указывают на модель с лучшим разделением.
• Индекс Калински-Харабаша : этот индекс оценивает кластеры на основе их компактности и разделения. Индекс рассчитывается с использованием отношения дисперсии между кластерами к дисперсии внутри кластера, причем более высокие значения указывают на более определенные кластеры. ^[32]
• Индекс Рэнда : он вычисляет долю согласия между двумя кластерами, учитывая обе пары элементов, которые правильно отнесены к одному и тому же или разным кластерам. ^[33] Более высокие значения указывают на большее сходство и лучшее качество кластеризации. Чтобы обеспечить более точную меру, скорректированный индекс Рэнда (ARI), введенный Хьюбертом и Араби в 1985 году, корректирует индекс Рэнда, корректируя ожидаемое сходство всех пар из-за случайности. ^[34]

• Оптимизация естественных разрывов Дженкса : k -средние, применяемые к одномерным данным
• Кластеризация k -медиан использует медиану в каждом измерении вместо среднего значения, и таким образом минимизируетнорму ( геометрия такси ).${\displaystyle L_{1}}$
• k -медоиды (также: разбиение по медоидам, PAM) используют медоид вместо среднего значения, и таким образом минимизируют сумму расстояний для произвольных функций расстояния.
• Нечеткая кластеризация C-средних — это мягкая версия метода k -средних, где каждая точка данных имеет нечеткую степень принадлежности к каждому кластеру.
• Модели гауссовой смеси , обученные с помощью алгоритма максимизации ожидания (алгоритм EM), поддерживают вероятностные назначения кластерам вместо детерминированных назначений и многомерные гауссовские распределения вместо средних значений.
• k -means++ выбирает начальные центры таким образом, чтобы получить доказуемую верхнюю границу цели WCSS.
• Алгоритм фильтрации использует k -d деревья для ускорения каждого шага k -средних. ^[35]
• Некоторые методы пытаются ускорить каждый шаг k -средних, используя неравенство треугольника . ^{[22] [23] [24] [36] [25]}
• Избежать локальных оптимумов можно, переставив точки между кластерами. ^[9]
• Алгоритм сферической кластеризации k -средних подходит для текстовых данных. ^[37]
• Иерархические варианты, такие как деление k -средних пополам, ^[38] кластеризация X-средних ^[39] и кластеризация G-средних ^[40], многократно разбивают кластеры для построения иерархии , а также могут попытаться автоматически определить оптимальное количество кластеров в наборе данных.
• Внутренние меры оценки кластера , такие как силуэт кластера, могут быть полезны при определении количества кластеров .
• Взвешенные по Минковскому k -средние автоматически вычисляют веса признаков, характерные для кластера, поддерживая интуитивную идею о том, что признак может иметь разную степень релевантности для разных признаков. ^[41] Эти веса также можно использовать для повторного масштабирования заданного набора данных, увеличивая вероятность оптимизации индекса валидности кластера при ожидаемом количестве кластеров. ^[42]
• Мини-пакет k -средних: вариация k -средних с использованием образцов «мини-пакетов» для наборов данных, которые не помещаются в память. ^[43]
• Метод Оцу

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

Пусть будет индивидуальной стоимостью , определяемой с центром кластера.${\displaystyle \varphi (S_{j})}$${\displaystyle S_{j}}$${\textstyle \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}\setminus \{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}$

Могут использоваться различные стратегии принятия перемещения. В стратегии первого улучшения может быть применено любое улучшающее перемещение, тогда как в стратегии наилучшего улучшения все возможные перемещения итеративно тестируются, и только лучшее применяется на каждой итерации. Первый подход благоприятствует скорости, а второй подход в целом благоприятствует качеству решения за счет дополнительного времени вычислений. Функция, используемая для вычисления результата перемещения, также может быть эффективно оценена с помощью равенства ^[44]${\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 -средних и его вариации сходятся только к локальным минимумам задачи кластеризации минимальной суммы квадратов, определяемой как Во многих исследованиях предпринимались попытки улучшить поведение сходимости алгоритма и максимизировать шансы достижения глобального оптимума (или, по крайней мере, локальных минимумов лучшего качества). Методы инициализации и перезапуска, обсуждавшиеся в предыдущих разделах, являются одной из альтернатив для поиска лучших решений. Совсем недавно глобальные алгоритмы оптимизации, основанные на ветвях и границах и полуопределенном программировании, дали «доказанно оптимальные» решения для наборов данных, содержащих до 4177 сущностей и 20531 признаков. ^[45] Как и ожидалось, из-за NP-трудности нижележащей задачи оптимизации время вычислений оптимальных алгоритмов для k -средних быстро увеличивается за пределами этого размера. Оптимальные решения для малых и средних масштабов по-прежнему остаются ценными в качестве эталонного инструмента для оценки качества других эвристик. Чтобы найти высококачественные локальные минимумы в контролируемом вычислительном времени, но без гарантий оптимальности, в других работах изучались метаэвристики и другие методы глобальной оптимизации , например, основанные на инкрементальных подходах и выпуклой оптимизации, ^[46] случайных обменах ^[47] (т. е. итеративный локальный поиск ), поиске переменного соседства ^[48] и генетических алгоритмах . ^{[49] [50]} Действительно известно, что нахождение лучших локальных минимумов задачи кластеризации минимальной суммы квадратов может иметь решающее значение между неудачей и успехом при восстановлении кластерных структур в пространствах признаков высокой размерности. ^[50]$${\displaystyle \mathop {\operatorname {arg\,min} } _{\mathbf {S} }\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}.}$$

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

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

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

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

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

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

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

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

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

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

Кластеризация k -средних использовалась в качестве шага обучения признакам (или обучения словарю ) как в ( полу- ) контролируемом обучении, так и в неконтролируемом обучении . ^[53] Основной подход заключается в том, чтобы сначала обучить представление кластеризации k -средних с использованием входных обучающих данных (которые не обязательно должны быть помечены). Затем, чтобы спроецировать любые входные данные в новое пространство признаков, функция «кодирования», такая как пороговое матричное произведение данных с местоположениями центроидов, вычисляет расстояние от данных до каждого центроида или просто индикаторную функцию для ближайшего центроида, ^{[53] [54]} или некоторое плавное преобразование расстояния. ^[55] В качестве альтернативы, преобразование расстояния выборка-кластер через гауссовскую RBF , получает скрытый слой сети радиальной базисной функции . ^[56]

Такое использование k -средних успешно сочеталось с простыми линейными классификаторами для полуконтролируемого обучения в NLP (в частности, для распознавания именованных сущностей ) ^[57] и в компьютерном зрении . В задаче распознавания объектов было обнаружено, что он демонстрирует сопоставимую производительность с более сложными подходами к обучению признакам, такими как автоэнкодеры и ограниченные машины Больцмана . ^[55] Однако для эквивалентной производительности обычно требуется больше данных, поскольку каждая точка данных вносит вклад только в один «признак». ^[53]

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

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

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

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

Расслабленное решение кластеризации k -средних, указанное кластерными индикаторами, дается анализом главных компонент (PCA). ^{[61] [62]} Интуиция заключается в том, что k -средние описывают сферические (шаровые) кластеры. Если данные имеют 2 кластера, линия, соединяющая два центроида, является наилучшим 1-мерным направлением проекции, которое также является первым направлением PCA. Разрезание линии в центре масс разделяет кластеры (это непрерывная релаксация дискретного кластерного индикатора). Если данные имеют три кластера, 2-мерная плоскость, охватываемая тремя кластерными центроидами, является наилучшей 2-мерной проекцией. Эта плоскость также определяется первыми двумя измерениями PCA. Хорошо разделенные кластеры эффективно моделируются шарообразными кластерами и, таким образом, обнаруживаются k -средними. Не шарообразные кластеры трудно разделить, когда они находятся близко. Например, два кластера в форме полумесяца, переплетенные в пространстве, плохо разделяются при проецировании на подпространство PCA. Не следует ожидать, что k -средние будут хорошо работать с этими данными. ^[63] Легко привести контрпримеры к утверждению, что подпространство центроида кластера охватывается главными направлениями. ^[64]

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

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

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

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

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

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

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

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

• Алгоритм BFR
• Центроидальная мозаика Вороного
• Кластерный анализ
• ДБСКАН
• Голова/хвост ломаются
• k q -квартиры
• к - означает++
• Алгоритм Линде–Бузо–Грея
• Самоорганизующаяся карта