0

这是一个家庭作业问题，我在理解它时遇到了一些困难。家庭作业问题是

    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 乘以它合并到的集群？）

任何帮助是极大的赞赏。谢谢你。

4

1 回答 1

2

听起来好像您想要自下而上的集群。这个想法是，从一些单例集开始

{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。

于 2011-11-15T22:32:29.170 回答