3

Java で凝集クラスタリング アルゴリズムを作成していますが、削除操作に問題があります。クラスターの数が初期数の半分に達すると、常に失敗するようです。

以下のサンプル コードでclustersは、 はCollection<Collection<Integer>>.

      while(clusters.size() > K){
           // determine smallest distance between clusters
           Collection<Integer> minclust1 = null;
           Collection<Integer> minclust2 = null;
           double mindist = Double.POSITIVE_INFINITY;

           for(Collection<Integer> cluster1 : clusters){
                for(Collection<Integer> cluster2 : clusters){
                     if( cluster1 != cluster2 && getDistance(cluster1, cluster2) < mindist){
                          minclust1 = cluster1;
                          minclust2 = cluster2;
                          mindist = getDistance(cluster1, cluster2);
                     }
                }
           }

           // merge the two clusters
           minclust1.addAll(minclust2);
           clusters.remove(minclust2);
      }

ループを数回実行すると、clusters.remove(minclust2)最終的に false が返されますが、その理由はわかりません。

最初に 10 個のクラスターを作成して、このコードをテストしました。それぞれに 1 から 10 までの整数が 1 つずつあります。距離は 0 から 1 の間の乱数です。いくつかの println ステートメントを追加した後の出力を次に示します。クラスターの数の後に、実際のクラスター、マージ操作、および clusters.remove(minclust2) の結果を出力します。

Clustering: 10 clusters
[[3], [1], [10], [5], [9], [7], [2], [4], [6], [8]]
[5] <- [6]
true
Clustering: 9 clusters
[[3], [1], [10], [5, 6], [9], [7], [2], [4], [8]]
[7] <- [8]
true
Clustering: 8 clusters
[[3], [1], [10], [5, 6], [9], [7, 8], [2], [4]]
[10] <- [9]
true
Clustering: 7 clusters
[[3], [1], [10, 9], [5, 6], [7, 8], [2], [4]]
[5, 6] <- [4]
true
Clustering: 6 clusters
[[3], [1], [10, 9], [5, 6, 4], [7, 8], [2]]
[3] <- [2]
true
Clustering: 5 clusters
[[3, 2], [1], [10, 9], [5, 6, 4], [7, 8]]
[10, 9] <- [5, 6, 4]
false
Clustering: 5 clusters
[[3, 2], [1], [10, 9, 5, 6, 4], [5, 6, 4], [7, 8]]
[10, 9, 5, 6, 4] <- [5, 6, 4]
false
Clustering: 5 clusters
[[3, 2], [1], [10, 9, 5, 6, 4, 5, 6, 4], [5, 6, 4], [7, 8]]
[10, 9, 5, 6, 4, 5, 6, 4] <- [5, 6, 4]
false

[10, 9, 5, 6, 4, 5, 6, 4, ...] セットは、そこから無限に成長します。

編集：明確にするために、HashSet<Integer>クラスター内の各クラスターに対してを使用しています（a HashSet<HashSet<Integer>>).

4

3 に答える 3

5

ああ。すでにSet(またはMapキー) にある値を変更すると、必ずしも正しい位置にあるとは限らず、ハッシュ コードがキャッシュされます。削除して変更し、再度挿入する必要があります。

于 2009-04-16T00:47:41.510 に答える
1

示されているテストでは、remove複数の整数を含むコレクションを初めて削除しようとすると失敗します。これは常に当てはまりますか？

使用されるコレクションの具体的なタイプは何ですか?

于 2009-04-16T00:31:41.690 に答える
0

明らかな問題は、clusters.removeおそらくequals削除する要素を見つけるために使用していることです。残念ながらequals、コレクションでは、通常、同じコレクションであるかどうかではなく、要素が同じであるかどうかを比較します (この点では、C# の方が適していると思います)。

簡単な修正は、 （私が思うに）clustersとして作成することです。Collections.newSetFromMap(new IdentityHashMap<Collection<Integer>, Boolean>())

于 2009-04-16T00:23:43.503 に答える