거리 매트릭스를 입력으로 클러스터링하는 [평가] 알고리즘

Question

누군가 거리 매트릭스를 입력으로 사용할 수있는 클러스터링 알고리즘을 제안 할 수 있습니까? 또는 거리 매트릭스를 기반으로 클러스터링의 "장점"을 평가할 수있는 알고리즘?

현재 데이터를 두 개의 클러스터로 나누기 위해 Kruskal의 알고리즘 (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm)을 수정했습니다. 그것은 문제가있다. 데이터에 별개의 클러스터가없는 경우에도 알고리즘은 하나의 요소가 포함 된 하나의 클러스터와 나머지 요소가 모두 포함 된 두 개의 클러스터를 생성합니다. 이 경우에는 모든 요소가 포함 된 하나의 클러스터와 비어있는 하나의 클러스터가 있습니다.

이러한 유형의 클러스터링을 수행 할 수있는 알고리즘이 있습니까?

클러스터링이 얼마나 잘 수행되었는지 또는 더 많은 클러스터가 데이터에 존재 하는지를 예측할 수있는 알고리즘이 있습니까?

알고리즘은 거리 (유사성) 행렬 만 입력으로 사용해야합니다.

Answer 1

또는 거리 행렬에 기초하여 또한 클러스터링 의 "양호"를 평가할 수있는 알고리즘?

KNN은 클러스터링 할당의 "장점"을 평가하는 데 유용해야합니다.

는이 속한 클러스터 (의 "클러스터 라벨")에 따라 표시된 각 지점과의 거리 행렬을 감안할 때 :

1. 테스트 클러스터 라벨에 대한 각 지점의 클러스터 라벨을 K에서 암시 적 방법은 다음과 같습니다 -nearest 이웃 분류
2. 만약 이웃 분류 된 포인트는 클러스터
3. 합 일어나 당신의 픽셀 하나 하나에서 "선 (善) 등급 '기여의 전체"선 (善) "등급을 낮춘다, 대체 클러스터를 의미 가까운이-K 전체 클러스터에 대한 총 "우수 등급"

k-means 클러스터 분석과 달리 알고리즘은 잘못 분류 된 점에 대한 정보를 반환합니다. 이 정보를 사용하여 특정 지점을 새 클러스터에 재 지정함으로써 클러스터링의 전반적인 "장점"을 향상시킬 수 있습니다.

알고리즘은 클러스터의 중심의 배치에 대해 아무것도 알지 못하므로 전역 클러스터 밀도에 대해 아무것도 알지 못하므로 로컬 및 전 세계적으로 밀도가 높은 클러스터를 보장하는 유일한 방법은 범위 알고리즘을 실행하는 것입니다 k 값의 범위에 대한 선량을 최대화하는 배열을 찾는 것.

상당량의 포인트를 얻으려면이 알고리즘을 최적화해야합니다. 각 포인트를 기준으로 가장 가까운 포인트를 추적하는 해시 테이블을 사용할 수도 있습니다. 그렇지 않으면이 알고리즘은 계산하는 데 꽤 오래 걸릴 것입니다.클러스터의 수를 추정하는 데 사용할 수 있습니다

Answer 2

몇 가지 방법은 다음과 같습니다

• Minimum Description Length
• Bayesian Information Criterion
• The gap statistic

Answer 3

scipy.cluster.hierarchy 실행 3 단계, 단지 matlab에 (TM)와 같은 clusterdata :

Y = scipy.spatial.distance.pdist(pts) # you have this already 
Z = hier.linkage(Y, method) # N-1 
T = hier.fcluster(Z, ncluster, criterion=criterion) 

여기 linkage은 수정 된 Kruskal, dunno 일 수 있습니다. 이 SO answer (에헴)은 위의 것을 사용합니다.
클러스터링의 척도로서 반경 = 클러스터 중심까지의 거리 rms는 빠르고 2 차원/3 차원의 경우 입니다.

Npt, ndim, ncluster, hier/flat에 대해 알려주십시오. 클러스터링은 규모가 크며 한 가지 크기만으로는 적합하지 않습니다.