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

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

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

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

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

Описание

Учитывая набор наблюдений ( x ₁ , x ₂ , ..., x _n ) , где каждое наблюдение представляет собой $d$-мерный действительный вектор, k кластеризация -средних направлена ​​на разделение n наблюдений на k ( ≤ n ) множеств S = { S ₁ , S ₂ , ..., S _k } так, чтобы минимизировать сумму квадратов внутри кластера ( WCSS) (т.е. дисперсия ). Формально цель состоит в том, чтобы найти: $$\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}$$ где µ _i — среднее значение (также называемое центроидом) точек в $S_{i}$, то есть $${\boldsymbol {\mu _{i}}}={\frac {1}{|S_{i}|}}\sum _{\mathbf {x} \in S_{i}}\mathbf {x} ,$$ $|S_{i}|$ размер $S_{i}$, и $\|\cdot \|$ это обычный л ² норма . Это эквивалентно минимизации попарных квадратичных отклонений точек в одном кластере: $$\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}}$. Поскольку общая дисперсия постоянна, это эквивалентно максимизации суммы квадратов отклонений между точками в разных кластерах (сумма квадратов между кластерами, BCSS). Это детерминированное соотношение также связано с законом полной дисперсии в теории вероятностей.

История

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

Алгоритмы

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

Сходимость k -средних

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

Учитывая начальный набор k, означает m ₁ ⁽¹⁾ , ..., м _к ⁽¹⁾ (см. ниже), алгоритм выполняется путем чередования двух шагов:

1. Шаг назначения : Присвойте каждое наблюдение кластеру с ближайшим средним значением: с наименьшим квадратом евклидова расстояния . (Математически это означает разделение наблюдений в соответствии с диаграммой Вороного, созданной с помощью этих средств.) $$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\},$$ где каждый $x_{p}$ присваивается ровно одному $S^{(t)}$, даже если его можно было назначить двум или более из них.
2. Шаг обновления : пересчитать средние значения ( центроиды ) для наблюдений, назначенных каждому кластеру. $$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 становится стабильным. Алгоритм не гарантирует нахождения оптимума.

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

Псевдокод

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

def k_means_cluster(k, points):
    # Initialization: choose k centroids (Forgy, Random Partition, etc.)
    centroids = [c1, c2, ..., ck]
    
    # Initialize clusters list
    clusters = [[] for _ in range(k)]
    
    # Loop until convergence
    converged = false
    while not converged:
        # Clear previous clusters
        clusters = [[] for _ in range(k)]
    
        # Assign each point to the "closest" centroid 
        for point in points:
            distances_to_each_centroid = [distance(point, centroid) for centroid in centroids]
            cluster_assignment = argmin(distances_to_each_centroid)
            clusters[cluster_assignment].append(point)
        
        # Calculate new centroids
        #   (the standard implementation uses the mean of all points in a
        #     cluster to determine the new centroid)
        new_centroids = [calculate_centroid(cluster) for cluster in clusters]
        
        converged = (new_centroids == centroids)
        centroids = new_centroids
        
        if converged:
            return clusters

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

Обычно используемые методы инициализации — Forgy и Random Partition. Метод Форги случайным образом выбирает k наблюдений из набора данных и использует их в качестве начальных средних значений. Метод случайного разделения сначала случайным образом назначает кластер каждому наблюдению, а затем переходит к этапу обновления, таким образом вычисляя начальное среднее значение как центроид случайно назначенных точек кластера. Метод Форги имеет тенденцию распределять исходные средние значения, в то время как случайное разделение помещает их все ближе к центру набора данных. По мнению Хамерли и др., метод случайного разделения обычно предпочтительнее для таких алгоритмов, как k -гармонические средние и нечеткие k -средние. Для максимизации ожидания и стандартных алгоритмов k -средних предпочтителен метод инициализации Форги. Всестороннее исследование Селеби и др., однако обнаружил, что популярные методы инициализации, такие как Forgy, Random Partition и Maximin, часто работают плохо, тогда как подход Брэдли и Файяда работает «постоянно» в «лучшей группе», а k -means++ работает «в целом хорошо».

• Демонстрация стандартного алгоритма
• 
  1. k исходных «средств» (в данном случае k =3) генерируются случайным образом внутри предметной области (показаны цветом).
• 
  2. k кластеров создаются путем сопоставления каждого наблюдения с ближайшим средним значением. Разделы здесь представляют собой диаграмму Вороного, созданную с помощью этих средств.
• 
  3. Центроид каждого из k кластеров становится новым средним.
• 
  4. Шаги 2 и 3 повторяются до тех пор, пока не будет достигнута сходимость.

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

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

Сложность

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

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

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

Время работы алгоритма Ллойда (и большинства его вариантов) составляет $O(nkdi)$, где:

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

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

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

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

Оптимальное количество кластеров

Основная статья: Определение количества кластеров в наборе данных

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

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

Вариации

• Оптимизация естественных разрывов Дженкса : k -средние применяются к одномерным данным
• k Кластеризация -медианов использует медиану в каждом измерении вместо среднего значения, и таким образом минимизируется $L_{1}$ норма ( геометрия такси ).
• k -medoids (также: Разделение вокруг медоидов, PAM) использует медоид вместо среднего значения и таким образом минимизирует сумму расстояний для произвольных функций расстояния.
• Нечеткая кластеризация C-средних — это мягкая версия k -средних, где каждая точка данных имеет нечеткую степень принадлежности к каждому кластеру.
• Модели гауссовой смеси , обученные с помощью алгоритма ожидания-максимизации (алгоритм EM), поддерживают вероятностные назначения кластерам вместо детерминированных назначений и многомерные гауссовы распределения вместо средних значений.
• k -means++ выбирает начальные центры таким образом, чтобы дать доказуемую верхнюю границу цели WCSS.
• Алгоритм фильтрации использует k -d деревья для ускорения каждого шага k -средних.
• Некоторые методы пытаются ускорить каждый шаг k -средних, используя неравенство треугольника .
• Избегайте локальных оптимумов, меняя точки между кластерами.
• Алгоритм кластеризации сферических k -средних подходит для текстовых данных.
• Иерархические варианты, такие как Bisecting k -means, X-средняя кластеризация и кластеризация G-средств многократно разбивать кластеры для построения иерархии , а также может попытаться автоматически определить оптимальное количество кластеров в наборе данных.
• Внутренние меры оценки кластера , такие как силуэт кластера, могут быть полезны при определении количества кластеров .
• -средние Минковского Взвешенные k автоматически рассчитывают веса признаков, специфичных для кластера, поддерживая интуитивное представление о том, что признак может иметь разную степень релевантности для разных признаков. Эти веса также можно использовать для повторного масштабирования заданного набора данных, увеличивая вероятность оптимизации индекса достоверности кластера при ожидаемом количестве кластеров.
• Мини-партия k -означает: k -означает вариацию с использованием образцов «мини-партии» для наборов данных, которые не помещаются в память.
• Метод Оцу

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

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

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

Шаг назначения

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

Шаг обновления

Далее он определяет $n,m\in \{1,\ldots ,k\}$ и $x\in S_{n}$ для которого следующая функция достигает максимума $$\Delta (m,n,x)=\varphi (S_{n})+\varphi (S_{m})-\varphi (S_{n}\setminus \{x\})-\varphi (S_{m}\cup \{x\}).$$ Для $x,n,m$ которые достигают этого максимума, $x$ уходит из кластера $S_{n}$ в кластер $S_{m}$.

Прекращение действия

Алгоритм завершается один раз $\Delta (m,n,x)$ меньше нуля для всех $x,n,m$.

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

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

Обсуждение

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

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

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

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

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

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

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

Приложения

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

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

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

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

Пример изображения только с красным и зеленым каналом (для иллюстрации)

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

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

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

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

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

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

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

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

Основная статья: Изучение функций

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

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

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

Последние события

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

Связь с другими алгоритмами

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

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

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

к -СВД

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие проблемы

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

Реализации программного обеспечения

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

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

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

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

Собственный

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

• Аясди
• Математика
• МАТЛАБ
• OriginPro
• РапидМайнер
• SAP Хана
• САС
• СПСС
• Был

См. также

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