객체를 클러스터링하는 방법(좌표 없이)

StackOverflow https://stackoverflow.com/questions/691922

문제

불투명한 개체 목록이 있습니다.나는 그들 사이의 거리만 계산할 수 있습니다(사실이 아니며 문제에 대한 조건을 설정하는 것뿐입니다).

class Thing {
    public double DistanceTo(Thing other);
}

이러한 개체를 클러스터링하고 싶습니다.클러스터 수를 제어하고 "가까운" 객체가 동일한 클러스터에 있도록 하고 싶습니다.

List<Cluster> cluster(int numClusters, List<Thing> things);

누구든지 나에게 도움이 될 수 있는 일부 클러스터링 알고리즘(간단할수록 좋습니다!)이나 라이브러리를 제안(및 링크 ;-))할 수 있습니까?

설명 대부분의 클러스터링 알고리즘에서는 개체가 N차원 공간에 배치되어야 합니다.이 공간은 클러스터의 "중심"을 찾는 데 사용됩니다.내 경우에는 N이 무엇인지도 모르고, 객체에서 좌표계를 추출하는 방법도 모른다. 내가 아는 것은 두 물체가 얼마나 멀리 떨어져 있는지뿐입니다. 그 정보만을 활용하는 좋은 클러스터링 알고리즘을 찾고 싶습니다.

개체의 "냄새"를 기반으로 클러스터링하고 있다고 상상해 보십시오.2D 평면에 "냄새"를 배치하는 방법을 모르지만 두 냄새가 유사한지 여부는 알 수 있습니다.

도움이 되었습니까?

해결책

찾고 계신 것 같아요 K-메도이드.클러스터 수를 지정한다는 점에서 K-평균과 같습니다. 케이, 하지만 K-평균처럼 클러스터링하는 개체를 "평균화"하는 개념이 필요하지 않습니다.

대신 모든 클러스터에는 대표자가 있습니다. 메도이드, 이는 중앙에 가장 가까운 클러스터의 구성원입니다."수단" 대신 "중앙값"을 찾는 K-평균 버전으로 생각할 수 있습니다.당신에게 필요한 것은 클러스터링을 위한 거리 측정법뿐입니다. 나는 당신이 인용한 것과 정확히 같은 이유로 내 작업 중 일부에서 이것을 사용했습니다.

Naive K-medoids는 가장 빠른 알고리즘은 아니지만 귀하의 목적에 충분히 적합한 빠른 변형이 있습니다.다음은 알고리즘에 대한 설명과 해당 구현에 대한 문서 링크입니다. 아르 자형:

  1. 팸 K-medoids의 기본 O(n^2) 구현입니다.
  2. 클라라 훨씬 빠른 PAM 샘플링 버전입니다.PAM을 사용하여 무작위로 샘플링된 개체 하위 집합을 클러스터링하고 하위 집합을 기반으로 전체 개체 집합을 그룹화하는 방식으로 작동합니다.이를 통해 매우 좋은 클러스터링을 빠르게 얻을 수 있습니다.

더 많은 정보가 필요하시면, 여기 종이가 있어요 이는 이러한 방법과 기타 K-medoids 방법에 대한 개요를 제공합니다.

다른 팁

다음은 중심을 찾는 K-Means 요구 사항이없는 클러스터링 알고리즘에 대한 개요입니다.

  1. 모든 객체 사이의 거리를 결정하십시오. 녹음 N 대부분의 별도 개체.
    [클러스터의 뿌리, 시간 O (N^2)]
  2. 이 각각을 할당하십시오 N 랜덤 포인트 N 새로운 고유 한 클러스터.
  3. 다른 모든 개체에 대해 :
    [클러스터, 시간 O (n^2)에 개체 할당]
    1. 각 클러스터에 대해 :
      1. 클러스터의 각 객체의 거리를 물체까지 평균하여 클러스터에서 해당 물체까지의 평균 거리는 계산합니다.
    2. 가장 가까운 클러스터에 객체를 할당하십시오.

이 알고리즘은 확실히 객체를 클러스터링합니다. 그러나 런타임입니다 o (n^2). 게다가 처음에는 안내됩니다 N 선택한 포인트.

누구든지 이것을 개선 할 수 있습니까 (초기 선택에 덜 의존하는 더 나은 런타임 성능)? 나는 당신의 아이디어를보고 싶습니다.

다음은 빠른 알고리즘입니다.

While (points_left > 0) {
 Select a random point that is not already clustered
 Add point and all points within x distance 
   that aren't already clustered to a new cluster.
}

또는 읽으십시오 Wikipedia 페이지. K- 평균 클러스터링은 좋은 선택입니다.

K- 평균 알고리즘은 각 지점을 중심 (Centroid라고도 함)이 가장 가까운 클러스터에 할당합니다. 중심은 클러스터의 모든 지점의 평균입니다. 즉, 좌표는 클러스터의 모든 지점에 비해 각 차원의 산술 평균입니다.

알고리즘 단계는 다음과 같습니다.

* Choose the number of clusters, k.
* Randomly generate k clusters and determine the cluster centers, or
  directly generate k random points as cluster centers.
* Assign each point to the nearest cluster center.
* Recompute the new cluster centers.
* Repeat the two previous steps until some convergence criterion is
  met (usually that the assignment hasn't changed).

이 알고리즘의 주요 장점은 단순성과 속도로 큰 데이터 세트에서 실행할 수 있습니다. 결과적 인 클러스터는 초기 임의의 할당에 의존하기 때문에 각 실행에 동일한 결과를 얻지 못한다는 단점이 있습니다. 클러스터 내 분산을 최소화하지만 결과에 전 세계 최소 분산이 있는지 확인하지는 않습니다. 또 다른 단점은 정의 가능한 평균의 개념에 대한 요구 사항이 항상 그런 것은 아닙니다. 이러한 데이터 세트의 경우 k- 메드 변형이 적절합니다.

이 접근법은 어떻습니까 :

  1. 모든 객체를 하나의 클러스터에 할당하십시오.
  2. 두 개체를 찾아 ㅏ 그리고 비, 그것은 같은 클러스터 내에 있는데 케이, 그리고 그것은 최대 거리 간격입니다. 명확히하기 위해서는 하나가 있어야합니다 ㅏ 그리고 비 전체 세트의 경우 하나가 아닙니다 ㅏ 그리고 비 각 클러스터에 대해.
  3. 분할 클러스터 케이 두 개의 클러스터로 K1 그리고 K2, 하나는 물체가 있습니다 ㅏ 그리고 하나는 물체가 있습니다 비.
  4. 클러스터의 다른 모든 객체의 경우 케이, 그것들을 추가하십시오 K1 또는 K2 해당 클러스터의 다른 모든 객체에 대한 최소 평균 거리를 결정합니다.
  5. N 클러스터가 형성 될 때까지 2-5 단계를 반복하십시오.

효율성은 꽤 나쁘지만이 알고리즘은 상당히 좋은 클러스터링을 제공해야한다고 생각합니다. 효율성을 향상시키기 위해 3 단계를 변경하여 클러스터에있는 모든 객체와의 평균 거리가 아닌 클러스터를 시작한 원래 객체까지 최소 거리를 찾을 수 있습니다.

계통 발생 학적 DNA 서열 분석은 정기적으로 [정렬] 거리 행렬과 함께 텍스트 문자열에서 계층 적 클러스터링을 사용합니다. 다음은 클러스터링을위한 멋진 r 튜토리얼입니다.

(바로 가기 : "계층 적 응집 적"섹션으로 바로 가십시오 ...)

다음은 다른 [언어] 라이브러리입니다.

이 접근법은 얼마나 많은 [k] "천연"클러스터가 있고 위의 K- 평균 접근법에 대한 뿌리로 사용할 객체가 있는지 결정하는 데 도움이 될 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top