位序列的分層聚類

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倍，它被合併到羣集中）？

任何幫助是非常感謝。 謝謝。

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（2,3） + d（2,4）+ d（2,6））/ 6。