4

我想探索大数组中数据项之间的关系。每个数据项由多维向量表示。首先，我决定使用集群化。我有兴趣找到集群（数据向量组）之间的层次关系。我能够计算我的向量之间的距离。所以第一步我找到了最小的生成树。之后，我需要根据生成树中的链接对数据向量进行分组。但是在这一步我很不安——如何将不同的向量组合成层次聚类？我正在使用启发式方法：如果两个向量相连，并且它们之间的距离非常小 - 这意味着它们在同一个簇中，如果两个 wectors 链接但它们之间的距离大于阈值 - 这意味着它们在具有共同根簇的不同簇中。

但也许有更好的解决方案？

谢谢

PS 谢谢大家！

事实上，我尝试使用 k-means 和 CLOPE 的一些变体，但没有得到好的结果。

所以，现在我知道我的数据集的集群实际上具有复杂的结构（比 n 球体复杂得多）。

这就是为什么我想使用层次聚类。另外我猜集群看起来像 n 维连接（如 3d 或 2d 链）。所以我使用单链接策略。但是我很困扰 - 如何将不同的集群相互组合（在什么情况下我必须制作共同的根集群，在什么情况下我必须将所有子集群组合在一个集群中？）。我正在使用这样简单的策略：

  • 如果集群（或向量）彼此太接近 - 我将它们的内容组合成一个集群（由阈值调节）
  • 如果集群（或向量）彼此相距太远 - 我正在创建根集群并将它们放入其中

但是使用这种策略，我得到了非常大的簇树。我试图找到令人满意的阈值。但也许有更好的策略来生成集群树？

这是一张简单的图片，描述了我的问题：

在此处输入图像描述

4

2 回答 2

4

在这方面已经做了很多工作。通常的建议是从 K-means 聚类开始，除非您有非常好的理由不这样做 - 但 K-means 不进行层次聚类（通常无论如何），所以您可能有充分的理由不这样做（尽管它完全可以通过第一次创建集群来进行分层 K-means，然后再进行一次，使用每个集群的质心作为一个点，并继续直到您拥有尽可能少的高级集群）。

不过，还有很多其他的聚类模型，也有不少论文涵盖了相对优势和劣势，例如：

  1. 成对聚类和图形模型
  2. 超越成对聚类
  3. 并行成对聚类
  4. 快速贪心成对距离聚类。算法及其在发现主题中的应用。大数据集中的结构。
  5. 成对聚类算法
  6. 层次凝聚聚类

一点谷歌搜索会出现更多。回顾一下我从事聚类研究时的研究目录，我有几十篇论文，我记得还有很多我看过但没有留下来的，还有很多我从未得到过的机会真的连看。

于 2011-07-11T04:31:52.033 回答
2

有一整套聚类算法。其中，最小生成树又名单链接聚类具有一些很好的理论特性，如http://www.cs.uwaterloo.ca/~mackerma/Taxonomy.pdf中所述。特别是，如果您采用最小生成树并删除所有长度超过某个阈值长度的链接，那么将点分组到集群中应该具有该大小的任何分组的剩余链接的最小总长度，原因与 Kruskal 算法相同生成最小生成树。

但是，不能保证最小生成树最适合您的特定目的，所以我认为您应该从聚类算法中写下您实际需要的内容，然后基于此选择一种方法，或者尝试各种不同的方法对您的数据进行聚类算法，看看哪个在实践中是最好的。

于 2011-07-11T05:40:25.790 回答