Как я узнаю, что мой алгоритм кластеризации k-средних страдает проклятием размерности?

Я считаю, что название этого вопроса говорит само за себя.

Это помогает подумать о том, что такое проклятие размерности . На CV есть несколько очень хороших тем, которые стоит прочитать. Вот с чего начать: Объясните «Проклятие размерности» ребенку .

Отмечу, что вас интересует, как это относится к кластеризации средних. Стоит знать, что k -means - это стратегия поиска, позволяющая минимизировать (только) квадрат Евклидова расстояния. В свете этого стоит подумать о том, как евклидово расстояние относится к проклятию размерности (см. Почему евклидово расстояние не является хорошей метрикой в ​​больших измерениях? ). $k$$k$

Короткий ответ из этих тем состоит в том, что объем (размер) пространства увеличивается с невероятной скоростью по сравнению с количеством измерений. Даже измерений (которые не кажутся мне слишком «многомерными») могут навлечь проклятие. Если ваши данные были равномерно распределены по всему пространству, все объекты становятся приблизительно равноудаленными друг от друга. Однако, как отмечает @ Anony-Mousse в своем ответе на этот вопрос, это явление зависит от того, как данные располагаются в пространстве; если они не одинаковы, у вас не обязательно возникнет эта проблема. Это приводит к вопросу о том, являются ли однородно распределенные многомерные данные вообще очень распространенными (см .: действительно ли существует «проклятие размерности» в реальных данных? ). $10$

$10$$k$$k$

$[0,\ 1]$$[0,\ \sqrt{\sum D}]$

$k$$k$Как понять недостатки К-средних )

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

$N$$0.5\cdot N\cdot(N-1)$

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

$\frac 1 6$$\int_{x_i=0}^1\int_{x_j=0}^1 (x_i-x_j)^2 dx_i dx_j$runifrnorm

Вот симуляция для измерения от 1 до 500, особенности равномерного распределения от 0 до 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}