algorithm - 位序列的层次聚类

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.