位序列的层次聚类

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.