Журнал - Руководство по методам измерения расстояний для кластеризации K-средних

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

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

Кластеризация K-средних - один из многих алгоритмов кластеризации. Идея заключается в том, чтобы определить кластеры таким образом, чтобы минимизировать общую вариацию внутри кластера (известную как общая вариация внутри кластера). Алгоритм K-средних можно резюмировать следующим образом:

1. Specify the number of clusters(k) to be created.
2. Select randomly k objects from the data-set as the initial cluster centers or means.
3. Assign each observation to their closest centroid, based on the specified distance[the type of distance is what we will be exploring in this article, in the above case it is Euclidean] between the object and the centroid.
4. For each of the k clusters update the cluster centroid by calculating the new mean values of all the data points in the cluster. The centroid of a K-th cluster is a vector of length p containing the means of all variables for the observations in the K-th cluster; p is the number of variables.
5. Iteratively minimize the total within sum of square. That is, iterate steps 3 and 4 until the cluster assignments stop changing or the maximum number of iterations is reached.

В R мы рассчитываем кластер K-средних по:

Kmeans(x, centers, iter.max = 10, nstart = 1, method = "euclidean")
where
x        > Data frame
centers  > Number of clusters
iter.max > The maximum number of iterations allowed
nstart   > How many random sets of center should be chosen
method   > The distance measure to be used
There are other options too of calculating kmeans clustering but this is the usual pattern.

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

Измерения расстояния между точками данных

Методы разделены на 2 группы: одна основана на захвате геометрического разделения, а другая зависит от корреляции. Мы рассмотрим каждую из них.

Геометрическое разделение

Евклидово, Манхэттенское и максимальное (Чебычевское) расстояние

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

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

Общая формула расстояния Минковского для 2 точек p и q:

дан кем-то:

Расстояние Минковского обычно используется с r равным 1 или 2, что соответствует манхэттенскому расстоянию и евклидову расстоянию соответственно. В предельном случае, когда r достигает бесконечности, мы получаем расстояние Чебичева.

Более простой способ понять это на картинке ниже

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

Манхэттенское расстояние должно давать более надежные результаты, тогда как на евклидово расстояние, вероятно, будут влиять выбросы. То же самое относится к более высоким значениям «p» в формуле расстояния Минковского. По мере увеличения значения p мера расстояния становится более восприимчивой к потере устойчивости, и выбросы в нескольких измерениях начинают преобладать над значением расстояния.

Можно сделать интересное наблюдение о разнице между ними, если мы нарисуем «круг», используя эти разные меры расстояния вместо евклидовой меры по умолчанию. Поскольку мы знаем, что круг - это геометрическое место точки, равноудаленной от заданной точки, центра круга. Теперь, если мы используем меры расстояния Манхэттена или Чебычева для измерения расстояния между точками от центра мы получаем «квадраты» вместо обычных «круглых» кругов.

Канберрское расстояние

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

Расстояние Хэмминга

Для категориальных переменных (мужской / женский или маленький / средний / большой) мы можем определить расстояние как 0, если две точки находятся в одной категории, и 1 в противном случае. Если все переменные категоричны, вы можете использовать расстояние Хэмминга, которое подсчитывает количество несовпадений.
Вы также можете преобразовать категориальные переменные в индикаторные переменные, по одной для каждого уровня переменной.
Если категории упорядочены (например, малые / средние / большие), так что некоторые категории «ближе »Друг к другу, а затем вы можете преобразовать их в числовую последовательность. Например, (маленький / средний / большой) может соответствовать (1/2/3). Затем вы можете использовать евклидово расстояние или другие расстояния для количественных данных.

Расстояние Махаланобиса

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

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

Расстояния на основе корреляции

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

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

Расстояние корреляции Пирсона

Корреляция Пирсона измеряет степень линейной связи между двумя профилями. Корреляционный анализ Пирсона - наиболее часто используемый метод. Это также известно как параметрическая корреляция, которая зависит от распределения данных. Это расстояние основано на коэффициенте корреляции Пирсона, который рассчитывается на основе значений выборки и их стандартных отклонений. Коэффициент корреляции ‘r’ принимает значения от –1 (большая отрицательная корреляция) до +1 (большая положительная корреляция).

Есть еще несколько вариантов этого расстояния:

Абсолютное расстояние корреляции Пирсона: на этом расстоянии используется абсолютное значение коэффициента корреляции Пирсона; следовательно, соответствующее расстояние находится между 0 и 1.
Расстояние нецентрированной корреляции: Это то же самое, что и корреляция Пирсона, за исключением того, что средние выборки установлены на ноль в выражении для нецентрированной корреляции. Нецентрированный коэффициент корреляции находится между –1 и +1; следовательно, расстояние находится между 0 и 2.
Абсолютное нецентрированное расстояние корреляции: Это то же самое, что и абсолютная корреляция Пирсона, за исключением того, что средние выборки установлены на ноль в выражении для нецентрированной корреляции. Нецентрированный коэффициент корреляции находится между 0 и +1; следовательно, расстояние находится между 0 и 1.

Косинусное корреляционное расстояние Эйзена

Это частный случай корреляции Пирсона, когда оба элемента x ¯ и y ¯ заменены нулем:

Расстояние корреляции Спирмена и Кендалла

Корреляция Спирмена между двумя переменными равна корреляции Пирсона между значениями ранга этих двух переменных; в то время как корреляция Пирсона оценивает линейные отношения, корреляция Спирмена оценивает монотонные отношения (линейные или нет). Если нет повторяющихся значений данных, идеальная корреляция Спирмена +1 или -1 возникает, когда каждая из переменных является идеальной монотонная функция другого.

Интуитивно корреляция Спирмена между двумя переменными будет высокой, когда наблюдения имеют схожий (или идентичный для корреляции 1) ранг (т. Е. Метку относительного положения наблюдений внутри переменной: 1-й, 2-й, 3-й и т. Д.) Между две переменные, и низкий, когда наблюдения имеют несходный (или полностью противоположный для корреляции -1) ранг между двумя переменными.

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

Коэффициент Спирмена подходит как для непрерывных, так и для дискретных порядковых переменных. Как ρ Спирмена, так и τ Кендалла можно сформулировать как частные случаи более общего коэффициента корреляции.

Несколько указателей на кластеризацию k-средних

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

Лучшего измерения расстояния не существует.

Для данного набора данных существует только лучшая мера расстояния. Выбор меры расстояния БУДЕТ влиять на вашу кластеризацию, но это зависит от набора данных и от цели, какая мера расстояния наиболее подходит для вашего конкретного приложения.