비트 시퀀스에 대한 계층 적 클러스터링

Question

이것은 숙제 문제이며 그것을 이해하는 데 어려움을 겪고 있습니다. 홈 작업 질문은 내가 처음에 내가 클러스터로 그들 모두를 고려하고 가장 가까운 사람을 병합 시작해야 책을 읽어

Cluster the following bitsequences using hierarchical clustering. If d(:,:) defines the 
distace between two bitsequences a and b, d(a,b) = Hamming-Distance(a,b) . If C1 and C2 are 
two clusters, the distance between C1 and C2 is d(C1,C2) = 1/|C1||C2| Summation(a belongs C1, b belongs C2) d(a,b). 
Show the cluster hierarchchy with all the intermediate steps. 

1 10001011 
2 11010111 
3 00101010 
4 00011110 
5 10101110 
6 11100001 

입니다. 새 클러스터가 형성됩니다. 이제 질문에서 말한 것처럼 두 클러스터의 각 요소 사이의 거리를 평균화하여이 새 클러스터와 다른 클러스터 사이의 거리를 계산하여이 새로 형성된 클러스터에 가장 가까운 클러스터를 찾아야합니다.

내 솔루션 : 나는 모든 쌍 사이의 해밍 거리를 찾고 C3과 C5 (해밍 거리가 2) 중 하나 이상을 선택합니다. 이제이 작업을 새 클러스터로 병합 할 수 있습니다.

내 관심사는 여기에 병합 된 것이 정확히 무엇입니까? 어떻게해야합니까? 간단히 말해서 나는 그대로 유지하고 새로운 클러스터로 지으겠습니까?

그리고 새 클러스터의 각 요소와 다른 클러스터 간의 평균 거리는 어떻게 찾습니까?

또한 평균을 계산하기 위해 주어진 공식은 | C1 | 및 | C2 |. 그렇다면 요소 수 (그룹당 8 개가 병합되는 클러스터 수와 같은 8 개)로 여기에서 나누어야 함을 의미합니까?

모든 도움을 주실 수 있습니다. 감사합니다.

Answer 1

마치 상향식 클러스터를 원하는 것처럼 들립니다. 몇 가지 싱글 톤 세트로 시작하는 아이디어입니다.

{1} {2} {3} {4} {5} {6} 

두 개 이상의 세트가있는 동안 가장 가까운 페어를 선택하고 합집합으로 교체하십시오. 나는 이것을 임의로 할 것이다.

{1, 2} {3} {4} {5} {6} 
{1, 2} {3, 6} {4} {5} 
{1, 2} {3, 4, 6} {5} 
{1, 2, 5} {3, 4, 6} 
{1, 2, 3, 4, 5, 6} 

계층 적 클러스터링은 알고리즘에 존재했던 모든 세트로 구성됩니다. 이들은 X가 Y의 자손 인 경우, 트리로 가시화 될 수 있으며, 다음 X는 Y.

  {1,2,3,4,5,6} 
     /   \ 
     /   \ 
     /    \ 
    {1,2,5}   {3,4,6} 
    / \   / \ 
    {1,2}  \  {3,6}  \ 
/ \  \ / \  \ 
{1} {2} {5} {3} {6} {4} 

평균 거리의 식으로 계산된다들의 서브 세트이고; | C1 | 및 | C2 | 는 각각 클러스터 1과 2의 시퀀스 수입니다. 시퀀스의 길이는 한 쌍의 해밍 거리를 계산할 때만 관련됩니다. 예를 들어 클러스터 {1, 2}와 {3, 4, 6} 사이의 거리는 (d (1,3) + d (1,4) + d (1,6) + d + d (2,4) + d (2,6))/6이다.