분산 계층적 클러스터링

https://stackoverflow.com/questions/84820

01-07-2019
|

문제

계층적 클러스터링에 도움이 될 수 있는 알고리즘이 있습니까?Google의 map-reduce에는 k-clustering의 예만 있습니다.계층적 클러스터링의 경우 노드 간에 작업을 분할하는 것이 어떻게 가능한지 잘 모르겠습니다.내가 찾은 다른 리소스는 다음과 같습니다. http://issues.apache.org/jira/browse/MAHOUT-19그러나 어떤 알고리즘이 사용되는지는 분명하지 않습니다.

해결책

먼저 계층 구조를 상향식으로 작성할 것인지 하향식으로 작성할 것인지 결정해야 합니다.

상향식은 계층적 응집 클러스터링이라고 합니다.다음은 간단하고 잘 문서화된 알고리즘입니다. http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html.

상향식 알고리즘을 배포하는 것은 각 분산 프로세스에서 적절한 클러스터를 선택하기 위해 전체 데이터 세트가 필요하기 때문에 까다롭습니다.또한 동일한 수준에 있는 둘 이상의 클러스터에 데이터 포인트를 추가하지 않도록 현재 수준의 클러스터 목록이 필요합니다.

하향식 계층 구성을 호출합니다. 분열적인 클러스터링. K-평균 계층 구조의 노드를 분할하는 방법을 결정하는 하나의 옵션입니다.이 문서에서는 노드 분할을 위한 K-평균 및 PDDP(주방향 분할 분할)를 살펴봅니다. http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf.결국 각 상위 노드를 상대적으로 균형이 잘 잡힌 하위 노드로 분할하면 됩니다.

하향식 접근 방식은 배포하기가 더 쉽습니다.첫 번째 노드 분할 후 생성된 각 노드는 분산 프로세스로 전달되어 다시 분할될 수 있습니다.각 분산 프로세스는 분할 중인 데이터 세트의 하위 집합만 인식하면 됩니다.상위 프로세스만 전체 데이터 세트를 인식합니다.

또한 각 분할은 병렬로 수행될 수 있습니다.k-평균에 대한 두 가지 예:

다른 팁

Clark Olson은 계층적 클러스터링을 위한 여러 분산 알고리즘을 검토합니다.

씨.에프.올슨."계층 적 클러스터링을위한 평행 알고리즘." 병렬 컴퓨팅, 21:1313-1325, 1995, 도이:10.1016/0167-8191(95)00017-I.

Parunaket al.개미가 둥지를 정렬하는 방법에서 영감을 얻은 알고리즘을 설명하십시오.

시간.Van Dyke Parunak, Richard Rohwer, Theodore C.Belding 및 Sven Brueckner :"동적 분산 된 계층 적 클러스터링." ~ 안에 진행엔지니어링 자체 조직 시스템에 관한 제 4 차 국제 워크숍 (ESOA), 2006, 도이:10.1007/978-3-540-69868-5

약간 오래된 경우 매우 읽기 쉬운 내용을 확인하십시오. Olson의 검토(1995).그 이후로 대부분의 논문은 액세스하는 데 수수료가 필요했습니다.:-)

R을 사용한다면 시도해 보는 것이 좋습니다. PVClust 다음을 사용하여 병렬성을 달성합니다. 눈, 또 다른 R 모듈.

당신도 볼 수 있습니다 네트워크에서 커뮤니티 구조 찾기 및 평가 Newman과 Girvan은 네트워크에서 커뮤니티를 평가하기 위한 접근 방식(및 이 접근 방식을 기반으로 한 알고리즘 세트)과 커뮤니티 품질로의 네트워크 분할 측정(그래프 모듈성)을 제안합니다.

Self-Organizing 지도(Kohonen의 신경망 방법)를 사용하여 수행되는 작업 중 일부를 볼 수 있습니다...에있는 사람들 비엔나 공과대학교 성장하는 계층적 맵 알고리즘의 분산 계산에 대한 일부 작업을 수행했습니다.

이것은 클러스터링 질문의 가장자리에 있으므로 도움이 되지 않을 수도 있지만 더 가까운 것은 생각할 수 없습니다.)

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow