Вопрос или проблема
Пусть $A=\{A_1,A_2,\cdots,A_m\}$ и $B=\{B_1,B_2,\cdots,B_n\}$ — это два множества точек в $k$-мерном евклидовом пространстве. Каждая точка $A_i$ или $B_i$ может рассматриваться как вектор признаков выборки данных. Я хочу знать, похожи ли два распределения $A$ и $B$ или нет.
Я могу провести одновариантный анализ, нарисовав $k$ гистограмм для $A$ и $B$ соответственно, и посмотреть на разницу между ними для каждого $k$.
Или я могу поступить следующим образом; вот что я спрашиваю. $A$ и $B$ представляют собой два кластера точек в евклидоном пространстве. Поэтому я могу измерить расстояние между этими двумя кластерами. Может быть несколько способов определения расстояния, я могу определить его как минимальное расстояние, например
$$d(A,B)=\min_{i,j}||A_i-B_j||$$
где $||\cdot||$ — это L2-норма. Либо я могу определить расстояние как расстояние между центроидами
$$d(A,B)=||C_A-C_B||$$
где
$$
\begin{align*}
C_A&=\frac1m\sum_{i=1}^mA_i\\
C_B&=\frac1n\sum_{j=1}^nB_j
\end{align*}
$$
В качестве альтернативного способа установления расстояния я могу учитывать стандартные отклонения кластеров;
$$d(A,B)=\frac{||C_A-C_B||}{s_As_B}$$
где $s_A$ и $s_B$ — это стандартные отклонения соответственно $A$ и $B$.
или я могу определить следующим образом
$$
\begin{align*}
d(A,B)&=\frac{||C_A-C_B||}{{s_A}^2{s_B}^2}\\
d(A,B)&=\frac{||C_A-C_B||}{{s_A}^2+{s_B}^2}
\end{align*}
$$
Существует ли стандартный способ определения этого расстояния?
Примечание 1: Я слышал слово «внутрикластерная сумма вариаций» в контексте кластеризации K-средних. Но, похоже, это не связано со стандартным отклонением.
Примечание 2: чат GPT рекомендовал последнее уравнение.
Как это часто бывает в науке о данных, нет одного стандартного решения, это зависит от случая и от того, что вы пытаетесь достичь. Более того, существуют связанные концепции, похожие на метрики расстояния между кластерами.
В дальнейшем я постараюсь дать обзор некоторых известных методов (возможно, некоторые из них пропущены), структурировать их и попытаться объяснить, когда использовать что:
Расстояние между кластерами
Кластер — это регион пространства признаков
Типично алгоритмы кластеризации пытаются разделить пространство признаков на непересекающиеся кластеры. Это означает, что для большинства точек кластера соседние точки принадлежат тому же кластеру (могут быть исключения для выбросов и точек на границе с другими кластерами), и мы можем представить кластер как регион в пространстве признаков.
Ключевые свойства кластеров:
- их расположение (часто определяется центроидом)
- их внутренний размер, расстояние или диаметр, например, среднее/максимальное расстояние между точками кластера. В качестве альтернативы, среднее или максимальное расстояние до центроида. Вариация также может быть мерой внутреннего диаметра, но я бы считал это больше свойством распределения
- их расстояние до других кластеров (между центроидом, некоторыми точками или всеми точками)
Из этих свойств можно сформулировать ряд метрик расстояния:
Абсолютные расстояния
Здесь я в основном повторяю ваши предложенные метрики:
- Минимальные расстояния
$$d_{\mathrm{min}}(A,B) = \min_{i,j}\|A_i-B_j\|$$
Это акцентирует внимание на «разрыве» между двумя кластерами и должно использоваться, когда абсолютное - Расстояние центроидов
$$d_{\mathrm{centroid}}(A,B) = \|C_A-C_B\|$$
Это полностью игнорирует «размер» или «диаметр». Даже сильные перекрытия могут не повлиять на эту метрику. Используйте с осторожностью, когда разрыв можно полностью игнорировать. - Среднее расстояние
$$d_{\mathrm{avg}}(A,B) = \frac{1}{|A|\cdot|B|}\sum_i\sum_j\|A_i-B_j\|$$
Это учитывает и расположение, и диаметр. В некоторых случаях вас больше интересует среднее расстояние от одной точки $A$ до одной точки $B$ - Другие статистические показатели: максимальное расстояние, медианное расстояние и т.д. могут подходить для некоторых специфических случаев.
Нормализованные / относительные расстояния
В некоторых случаях имеет смысл оценивать расстояния относительно размера кластеров. Расстояние 10 между двумя кластерами, каждый из которых имеет диаметр 1, может казаться «большим» по сравнению с расстоянием 50 между кластерами диаметром 1000.
Примечание: Относительные расстояния часто не являются метриками расстояния в математическом смысле. Обычно они не удовлетворяют неравенству треугольника!
Проверка адекватности: Если вы удвоите значения всех признаков (что удвоит все расстояния и диаметр), относительное расстояние должно оставаться тем же (инвариантность масштаба). Ваши предложенные относительные метрики (также как и те, которые предлагает chatGPT) не проходят эту проверку.
Подходы могут заключаться в нормализации по какому-либо среднему значению или сумме диаметра обоих кластеров. Используя диаметр / внутрикластерное расстояние $d_\mathrm{within}(A)$ и абсолютное расстояние (смотрите выше для выбора) $d_{\mathrm{abs}}(A,B)$, это (некоторые) варианты:
$$\frac{d_{\mathrm{abs}}(A,B)}{d_\mathrm{within}(A) + d_\mathrm{within}(B)}$$
$$\frac{d_{\mathrm{abs}}(A,B)}{\sqrt{d_\mathrm{within}(A)^2 + d_\mathrm{within}(B)^2}}$$
$$\frac{d_{\mathrm{abs}}(A,B)}{\sqrt{d_\mathrm{within}(A)d_\mathrm{within}(B)}}$$
В вашем случае $d_\mathrm{within}(A)=s_A$ я бы предложил второй вариант, поскольку дисперсии могут быть аддитивными.
Оценка кластеризаций
Если ваша цель — оценить кластеризации, существуют индексы, которые вычисляют значение для кластеризации с $m$ кластерами. Это, например, используется для определения оптимального числа кластеров: производится кластеризация с $m=m_L,m_L+1,\ldots,m_H$ кластерами, и выбирается кластеризация с наилучшим индексом кластера.
Популярные алгоритмы:
Подробное объяснение их выходило бы за рамки этого уже длинного ответа.
Расстояния между распределениями
В отличие от кластеров, распределения могут (и часто будут) перекрываться. Расстояния между распределениями обычно основаны на стохастических, статистических или информационно-теоретических концепциях.
Существуют несколько подходов для измерения расстояния, сходства или различия между распределениями. Некоторые известные подходы:
- Статистические тесты. Этот подход, как правило, проверяет, принадлежат ли известные точки / образцы обоих распределений различным распределениям.
- Дивергенция Кульбака-Лейблера. Это расстояние (но не метрика) между двумя распределениями. Оно часто используется, чтобы увидеть, насколько близкое наблюдаемое распределение к теоретическому. Особенно это используется, когда предположения о распределениях делаются в моделях, но также имеет и другие применения. Примечание: дивергенция КЛ не симметрична!
- Расстояние Вассерштейна с особым случаем оптимального транспорта. Описательно оно измеряет, насколько далеко нужно переместить точки $A$, чтобы получить распределение $B$
Ответ или решение
Определение расстояния между двумя кластерами точек в многомерном евклидном пространстве является важной задачей в области анализа данных и машинного обучения. В этом ответе мы рассмотрим стандарты, методы и подходы, которые могут быть использованы для измерения расстояния между кластерами, а также выделим контекст, в котором каждый метод наиболее подходит.
1. Понимание кластеров
Кластеры представляют собой группы точек, которые обладают схожими характеристиками. Основные свойства кластеров включают:
- Расположение: Обычно определяется через центроид кластера.
- Размер (диаметр): Можно определить как среднее или максимальное расстояние между точками внутри кластера.
- Расстояние до других кластеров: Включает в себя различные методы оценки расстояний между позициями кластеров.
2. Методы определения расстояния между кластерами
Существует несколько подходов к измерению расстояния между кластерами. Рассмотрим наиболее распространенные из них:
2.1 Непосредственные расстояния
-
Минимальное расстояние:
[
d{\text{min}}(A, B) = \min{i,j} |A_i – B_j|
]
Этот метод фокусируется на минимальном расстоянии между точками двух кластеров. Важно учитывать, что, если кластеры пересекаются, это может привести к неоптимальным результатам. -
Расстояние центроидов:
[
d_{\text{centroid}}(A, B) = |C_A – C_B|
]
Этот метод игнорирует размеры кластеров и их перестановку, что может быть недостатком при анализе более сложных распределений. -
Среднее расстояние:
[
d_{\text{avg}}(A, B) = \frac{1}{|A| \cdot |B|} \sum_i \sum_j |A_i – B_j|
]
Это обобщенный подход, обладающий особенностями как по расположению, так и по размеру кластеров.
2.2 Нормализованные расстояния
Иногда целесообразно нормализовать расстояния, учитывая размеры кластеров:
-
Относительное расстояние:
[
d(A, B) = \frac{d{\text{abs}}(A, B)}{d{\text{within}}(A) + d_{\text{within}}(B)}
]
Это помогает учесть варьирование размеров кластеров и точность измерения. Нормализация покажет более адекватные результаты при наличии пересечений кластеров. -
Другие методы:
Можно также рассмотреть расстояние по формуле:
[
d(A, B) = \frac{d{\text{abs}}(A, B)}{\sqrt{d{\text{within}}(A)^2 + d_{\text{within}}(B)^2}}
]
или нормализованное по произведению диаметров.
3. Оценка кластеризации
При оценке качества кластеризации можно использовать специальные индексы, например:
- Индекс Данна
- Индекс Дэви–Боулдина
- Силуэтный индекс
Эти метрики помогают выбрать наилучшее количество кластеров и анализировать эффективность кластеризации с точки зрения различных статистических параметров.
4. Расстояние между распределениями
Важно помнить, что расстояния между кластерами могут отличаться от расстояний между распределениями. Существуют методы, такие как Kullback-Leibler дивергенция и Wasserstein расстояние, которые помогают оценить подобие распределений.
Заключение
Выбор подходящего метода для измерения расстояния между кластерами зависит от контекста задачи и особенностей данных. Использование различных метрик и их комбинаций позволит эффективно анализировать кластерные структуры и их взаимосвязи. Для практического применения важно провести предварительный анализ, чтобы выбрать наилучший подход, соответствующий спецификам ваших данных и целей анализа.