0

我正在尝试使用 Kruskal 的最小生成树算法进行 K-Means 聚类。我最初的设计是运行输入的全长 Kruskal 算法并产生一个 MST，然后删除最后的 k-1 个边（或等效的 k-1 个最昂贵的边）。

当然，这与运行 Kruskal 算法并在它添加最后 k-1 条边之前停止它是一样的。

我想使用第二种策略，即不是运行全长 Kruskal 算法，而是在到目前为止的集群数等于 K 之后停止它。我正在使用 Union-Find 数据结构并在此 Union-Find 数据中使用列表对象结构体。

此图上的每个顶点都由其在此列表中的当前簇表示，例如，[1,2,3...]表示顶点 1、2、3 位于它们不同的独立簇中。如果连接两个顶点，则列表数据结构上的相应索引将更新以反映这一点。

例如，合并顶点 2 和 3 会使列表数据对象保留为[1,2,2,4,5.....]

我的策略是每次合并两个节点时，计算列表中 DISTINCT 元素的数量，如果它等于所需集群的数量，则停止。我担心这可能不是最有效的选择。有没有一种方法可以有效地计算列表中不同对象的数量？

4

2 回答 2

2

最简单也可能最有效的是

len(set(l))

清单在哪里l。如果合适的话，您可以首先考虑将数据存储在集合中而不是列表中。

请注意，要使其正常工作， 的元素l必须是可散列的，这对于数字是有保证的，但对于通用“对象”则不是。

于 2012-12-14T09:12:59.350 回答
1

一种方法是对列表进行排序，然后通过将每个元素与前一个元素进行比较来遍历元素。如果它们不等于您的“不同计数器”的总和 1。此操作为 O(n)，对于排序，您可以使用您喜欢的排序算法，例如快速排序或归并排序，但我猜您使用的库中有可用的排序算法。

另一种选择是创建一个哈希表并添加所有元素。插入的数量将是不同的元素，因为不会插入重复的元素。我认为这是 O(1) 在最好的情况下，所以也许这是更好的解决方案。祝你好运！

希望这可以帮助，

迪达克·佩雷斯

于 2012-12-14T09:17:41.553 回答