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 的整数。距离是 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 (a HashSet<HashSet<Integer>>).

4

3 回答 3

5

啊。当您更改已经在 a Set（或Map键）中的值时，它不一定在正确的位置，并且哈希码将被缓存。您需要删除它，更改它，然后重新插入它。

于 2009-04-16T00:47:41.510 回答
1

在显示的测试中，remove第一次尝试删除包含多个整数的集合时失败。总是这样吗？

使用的 Collection 的具体类型是什么？

于 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 回答