algorithm

Question 1

3 차원의 큰 벡터 세트가 있습니다. 특정 클러스터의 모든 벡터가 임계 값 “T”보다 작은 서로 간의 유클리드 거리를 갖도록 유클리드 거리를 기반으로 이들을 클러스터링해야합니다.

얼마나 많은 클러스터가 존재하는지 모르겠습니다. 마지막에는 유클리드 거리가 공간의 벡터와 함께 “T”보다 작지 않기 때문에 클러스터의 일부가 아닌 개별 벡터가 존재할 수 있습니다.

여기에 어떤 기존 알고리즘 / 접근법을 사용해야합니까?

Question 2

계층 적 클러스터링을 사용할 수 있습니다 . 다소 기본적인 접근 방식이므로 사용 가능한 많은 구현이 있습니다. 예를 들어 Python의 scipy에 포함되어 있습니다 .

예를 들어 다음 스크립트를 참조하십시오.

import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster

# generate 3 clusters of each around 100 points and one orphan point
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20

# clustering
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")

# plotting
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "threshold: %f, number of clusters: %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()

다음 이미지와 유사한 결과가 생성됩니다.
클러스터

매개 변수로 주어진 임계 값은 점 / 군집이 다른 군집에 병합되는지 여부를 결정하는 기준이되는 거리 값입니다. 사용중인 거리 측정법도 지정할 수 있습니다.

클러스터 내 / 내부 유사성을 계산하는 방법에는 다양한 방법이 있습니다. 예를 들어 가장 가까운 점 사이의 거리, 가장 먼 점 사이의 거리, 클러스터 중심까지의 거리 등이 있습니다. 이러한 방법 중 일부는 scipys 계층 적 클러스터링 모듈 ( single / complete / average … linkage ) 에서도 지원됩니다 . 귀하의 게시물에 따르면 완전한 연결 을 사용하고 싶을 것 입니다.

이 접근 방식은 다른 클러스터의 유사성 기준, 즉 거리 임계 값을 충족하지 않는 경우 작은 (단일 포인트) 클러스터도 허용합니다.

더 나은 성능을 발휘하는 다른 알고리즘이 있으며 데이터 포인트가 많은 상황에서 관련성이 있습니다. 다른 답변 / 댓글이 제안했듯이 DBSCAN 알고리즘을 살펴볼 수도 있습니다.

이들 및 기타 클러스터링 알고리즘에 대한 멋진 개요를 보려면이 데모 페이지 (Python의 scikit-learn 라이브러리)를 참조하십시오.

http://scikit-learn.org/stable/modules/clustering.html

해당 장소에서 복사 한 이미지 :

보시다시피 각 알고리즘은 고려해야 할 클러스터의 수와 모양에 대해 몇 가지 가정을합니다. 알고리즘에 의해 부과 된 암시 적 가정 또는 매개 변수화에 의해 지정된 명시 적 가정입니다.

Question 3

moooeeeep의 대답은 계층 적 클러스터링을 사용하는 것이 좋습니다. 클러스터링의 임계 값 을 선택 하는 방법에 대해 자세히 설명하고 싶었습니다 .

한 가지 방법은 서로 다른 임계 값 t1 , t2 , t3 , …을 기반으로 클러스터링 을 계산 한 다음 클러스터링의 “품질”에 대한 메트릭을 계산하는 것입니다. 전제는 최적 의 클러스터 수를 사용하는 클러스터링 의 품질이 품질 메트릭의 최대 값을 갖는다는 것입니다.

내가 과거에 사용한 좋은 품질 메트릭의 예는 Calinski-Harabasz입니다. 간단히 말해서, 평균 클러스터 간 거리를 계산하고이를 클러스터 내 거리로 나눕니다. 최적의 클러스터링 할당에는 서로 가장 많이 분리 된 클러스터와 “가장 단단한”클러스터가 있습니다.

그런데 계층 적 클러스터링을 사용할 필요가 없습니다. k- 평균 과 같은 것을 사용 하여 각 k 에 대해 미리 계산 한 다음 Calinski-Harabasz 점수가 가장 높은 k 를 선택할 수도 있습니다.

참고 문헌이 더 필요한지 알려 주시면 제 하드 디스크를 샅샅이 뒤져서 몇 가지 서류를 드리겠습니다.

Question 4

DBSCAN 알고리즘을 확인하십시오 . 벡터의 로컬 밀도를 기반으로 클러스터링됩니다. 즉, ε 거리 이상 떨어져서 는 안되며 클러스터 수를 자동으로 결정할 수 있습니다. 또한 특이 치, 즉 ε- 이웃 수가 충분 하지 않은 점을 클러스터의 일부가 아닌 것으로 간주합니다. Wikipedia 페이지는 몇 가지 구현으로 연결됩니다.

Question 5

큰 데이터 세트와 잘 작동하는 OPTICS를 사용하십시오 .

OPTICS : 주문 포인트 DBSCAN과 밀접하게 관련된 클러스터링 구조를 식별하기 위해 고밀도의 핵심 샘플을 찾아 클러스터를 확장합니다 1 . DBSCAN과 달리 가변 인접 반경에 대한 클러스터 계층 구조를 유지합니다. DBSCAN의 현재 sklearn 구현보다 대규모 데이터 세트에서 사용하기에 더 적합합니다.

from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)

귀하의 요구 사항에 따라 eps, min_samples 를 미세 조정 하십시오.

Question 6

솔루션이 없을 수도 있습니다. 두 개의 서로 다른 입력 데이터 점 사이의 거리가 항상 T보다 큰 경우입니다. 입력 데이터에서만 클러스터 수를 계산하려면 계층 적 클러스터링 인 MCG를 살펴볼 수 있습니다. 자동 중지 기준을 사용하는 방법 : https://hal.archives-ouvertes.fr/hal-02124947/document (서지 참조 포함) 에서 무료 세미나 문서를 참조하십시오.

Question 7

계층 적 클러스터링을 사용하여 moooeeeep의 답변에 추가하고 싶습니다. 이 솔루션은 저에게 효과적이지만 임계 값을 선택하는 것은 “무작위”입니다. 다른 소스를 참조하고 직접 테스트하여 더 나은 방법을 얻었으며 덴드로 그램으로 임계 값을 쉽게 선택할 수 있습니다.

from scipy.cluster import hierarchy
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt

ori_array = ["Your_list_here"]
ward_array = hierarchy.ward(pdist(ori_array))
dendrogram = hierarchy.dendrogram(hierarchy.linkage(ori_array, method  = "ward"))
plt.title('Dendrogram')
plt.xlabel('Customers')
plt.ylabel('Euclidean distances')
plt.show()

여기를 클릭하면 이와 같은 플롯을 볼 수
있습니다 . 그런 다음 수평선을 그리면 거리 = 1에서 접속사 수가 원하는 클러스터 수가됩니다. 그래서 여기에서는 4 개의 클러스터에 대해 임계 값 = 1을 선택합니다.

threshold = 1
clusters_list = hierarchy.fcluster(ward_array, threshold, criterion="distance")
print("Clustering list: {}".format(clusters_list))

이제 cluster_list의 각 값은 ori_array의 해당 지점에 할당 된 cluster-id가됩니다.