태그 보관물: k-means

k-means

k- 평균 군집 알고리즘이 차원의 저주로 고통 받고 있음을 어떻게 알 수 있습니까? 모든 것을

나는이 질문의 제목이 모든 것을 말해 준다고 믿는다.



답변

차원의 저주가 무엇인지 생각하는 데 도움이됩니다 . CV에는 읽을 가치가있는 몇 가지 매우 유용한 스레드가 있습니다. 시작하는 장소는 다음과 같습니다 . 어린이에게“차원의 저주”를 설명하십시오 .

이것이 적용되는 방식에 관심이 있음을 유의하십시오.

케이

클러스터링을 의미합니다. 알아두면 가치가 있습니다.

케이

-means는 제곱 유클리드 거리를 최소화하기위한 검색 전략입니다. 이를 고려할 때 유클리드 거리가 차원의 저주와 어떤 관련이 있는지에 대해 생각할 가치 가 있습니다 (유클리드 거리가 높은 차원에서 좋은 지표가 아닌 이유는 무엇입니까? 참조 ).

이 스레드의 짧은 대답은 공간의 볼륨 (크기)이 치수 수에 비해 놀라운 속도로 증가한다는 것입니다. 조차

10

차원은 (나에게 ‘고차원 적’이라고 보이지는 않지만) 저주를 가져올 수 있습니다. 데이터가 해당 공간 전체에 균일하게 분산 된 경우 모든 객체가 서로 거의 등거리에있게됩니다. 그러나 @ Anony-Mousse 가 그 질문 에 대한 답변 에서 언급 한 것처럼이 현상은 데이터가 공간 내에 어떻게 배열되는지에 달려 있습니다. 그들이 균일하지 않다면, 반드시이 문제가있는 것은 아닙니다. 이것은 균일하게 분포 된 고차원 데이터가 전혀 공통적인지에 대한 질문으로 이어진다 ( “차원의 저주”가 실제 데이터에 실제로 존재 하는가? ).

중요한 것은 변수의 수 (데이터의 문자 차원)가 아니라 데이터의 효과적인 차원이라고 주장합니다. 가정하에

10

치수가 ‘너무 높음’

케이

즉, 가장 간단한 전략은 보유하고있는 기능의 수를 세는 것입니다. 그러나 효과적인 차원으로 생각하고 싶다면 PCA (Principal Components Analysis)를 수행하고 고유 값이 어떻게 떨어지는 지 살펴볼 수 있습니다. 대부분의 변형이 몇 가지 차원 (일반적으로 데이터 세트의 원래 차원을 가로 질러 절단)으로 존재하는 것이 일반적입니다. 즉, 문제가 발생할 가능성이 적다는 것을 의미합니다

케이

유효 치수가 실제로 훨씬 작다는 의미입니다.

보다 복잡한 접근법은 @ hxd1011이 그의 대답 에서 제안하는 선을 따라 데이터 세트에서 쌍 거리의 분포를 조사하는 입니다. 단순한 한계 분포를 살펴보면 가능한 균일성에 대한 힌트를 얻을 수 있습니다. 간격 내에 놓 이도록 모든 변수를 정규화하면

[0, 1]

쌍별 거리는 간격 내에 있어야합니다.

[0, ∑디]

. 거리가 너무 멀면 문제가 발생할 수 있습니다. 다른 한편으로, 다중 모달 분포는 희망적 일 수 있습니다 (여기서 내 대답의 예 : 클러스터링에서 이진 변수와 연속 변수를 함께 사용하는 방법은 무엇입니까? )를 볼 수 있습니다.

그러나 여부

케이

‘작업’한다는 의미는 여전히 복잡한 질문입니다. 데이터에 의미있는 잠재 그룹이 있다고 가정 할 때 반드시 모든 차원 또는 변동을 최대화하는 구성된 차원 (예 : 기본 구성 요소)에 존재하지는 않습니다. 군집은 변동이 적은 차원에있을 수 있습니다 ( 분산이 적은 PC가“유용한”PCA의 예 참조 ). 즉, 몇 가지 차원 또는 저 변량 PC에서 서로 가깝고 잘 분리 된 점을 가진 클러스터를 가질 수 있지만, 변이가 큰 PC에서는 원격으로 유사하지 않습니다.

케이

-따라서 클러스터를 무시하고 대신 가짜 클러스터를 선택합니다 (일부 예제는 여기에서 볼 수 있습니다 : K-means의 단점을 이해하는 방법 ).


답변

내 대답은 K 평균으로 제한되지 않지만 거리 기반 방법에 대한 차원의 저주가 있는지 확인하십시오. K- 평균은 거리 측정 (예 : 유클리드 거리)을 기반으로합니다.

알고리즘을 실행하기 전에 거리 메트릭 분포, 즉 데이터의 모든 쌍에 대한 모든 거리 메트릭을 확인할 수 있습니다. 당신이 가지고 있다면

데이터 포인트

0.5⋅엔⋅(엔−1)

거리 측정 항목. 데이터가 너무 크면 샘플을 확인할 수 있습니다.

차원 문제의 저주가 있다면,이 값들이 서로 매우 가깝다는 것입니다. 이것은 모든 사람이 가까이 있거나 멀리 떨어져 있고 거리 측정이 기본적으로 쓸모가 없다는 것을 의미하기 때문에 매우 직관적으로 보입니다.


이러한 반 직관적 인 결과를 보여주는 시뮬레이션이 있습니다. 모든 지형지 물이 균일하게 분포되어 있고 치수가 너무 많으면 모든 거리 측정 항목이

16

에서 오는

∫엑스나는=01∫엑스제이=01(엑스나는−엑스제이)2디엑스나는디엑스제이

. 균일 분포를 다른 분포로 자유롭게 변경하십시오. 예를 들어 정규 분포로 변경 runif하면 (로 변경 rnorm) 큰 차원의 다른 수로 수렴됩니다.

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))
}


답변