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）の1つが最も少ないものを選択します。これで、これを新しいクラスターにマージできます。

私の懸念は、ここでマージすることの正確な意味は何ですか？どうすればいいのですか？または、単にそれらをそのままにして、新しいクラスターという名前を付けますか？

また、新しいクラスターの各要素と他のクラスターとの間の平均距離を見つけるにはどうすればよいですか？

また、平均を計算するには、与えられた式は|C1|で割ると言います および|C2|。つまり、ここで要素の数で割る必要があるということですか（1つのグループあたり8で、マージされるクラスターを掛けたものですか？）

どんな助けでも大歓迎です。ありがとうございました。

4

1 に答える 1

2

ボトムアップクラスターが必要なように聞こえます。アイデアは、いくつかの単集合から始めることです

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

2つ以上のセットがありますが、最も近いペアを選択し、それらをそれらの和集合に置き換えます。これはやや恣意的に行います。

{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 に答える