6

我需要对一组二维数据进行一些聚类分析（我可能会在此过程中添加额外的维度）。

分析本身将形成输入可视化的数据的一部分，而不是输入到另一个过程（例如径向基函数网络）。

为此，我想找到一组主要“看起来正确”的集群，而不是阐明一些隐藏的模式。

我的直觉是，k-means将是一个很好的起点，但是找到合适数量的集群来运行算法是有问题的。

我要解决的问题是：

如何确定 k的“最佳”值， 以使形成的集群稳定且可视觉验证？

问题：

  • 假设这不是 NP 完全的，那么找到一个好的k的时间复杂度是多少。（可能以运行 k-means 算法的次数报告）。
  • k-means 是这类问题的一个很好的起点吗？如果是这样，您会推荐哪些其他方法。一个由轶事/经验支持的具体例子是 maxi-bon。
  • 您会推荐哪些捷径/近似值来提高性能。
4

8 回答 8

5

对于聚类数量未知的问题，凝聚层次聚类通常是比 k-means 更好的方法。

凝聚聚类产生树状结构，越靠近树干，聚类的数量越少，因此很容易扫描所有数量的聚类。该算法首先将每个点分配给自己的集群，然后重复对两个最近的质心进行分组。跟踪分组序列允许对任意数量的可能集群进行即时快照。因此，当您不知道需要多少组时，通常最好使用这种技术而不是 k-means。

还有其他层次聚类方法（参见 Imran 评论中建议的论文）。凝聚式方法的主要优点是有许多现成的实现供您使用。

于 2009-11-09T23:16:46.580 回答
2

Here's my approximate solution:

  1. Start with k=2.
  2. For a number of tries:
    1. Run the k-means algorithm to find k clusters.
    2. Find the mean square distance from the origin to the cluster centroids.
  3. Repeat the 2-3, to find a standard deviation of the distances. This is a proxy for the stability of the clusters.
  4. If stability of clusters for k < stability of clusters for k - 1 then return k - 1
  5. Increment k by 1.

The thesis behind this algorithm is that the number of sets of k clusters is small for "good" values of k.

If we can find a local optimum for this stability, or an optimal delta for the stability, then we can find a good set of clusters which cannot be improved by adding more clusters.

于 2009-11-09T16:50:43.963 回答
2

在之前的回答中，我解释了如何在视觉聚类中使用自组织图 (SOM) 。

否则，存在一种称为X-Means的 K-Means 算法的变体，除了通过使用KD-trees解决可伸缩性问题外，它还能够通过优化贝叶斯信息准则 (BIC)来找到集群的数量。Weka包含 X-Means 的实现以及许多其他聚类算法，所有这些都在一个易于使用的 GUI 工具中。

最后，您可以参考此页面，该页面讨论了肘部方法以及其他用于确定数据集中聚类数量的技术。

于 2009-11-09T23:39:22.610 回答
2

为了使用 k-means，您应该知道有多少簇。您不能尝试简单的元优化，因为您要添加的集群越多（每个数据点最多 1 个集群），就越会导致过度拟合。您可能会寻找一些集群验证方法并用它优化 k 超参数，但根据我的经验，它很少能很好地工作。它也非常昂贵。

如果我是你，我会做一个 PCA，最终在多项式空间上（注意你的可用时间），这取决于你对输入的了解，并沿着最具代表性的组件聚集。

有关您的数据集的更多信息将非常有助于获得更准确的答案。

于 2009-11-09T14:23:38.600 回答
1

您可能会查看有关集群验证的论文。这是涉及微阵列分析的论文中引用的一个，该分析涉及对具有相关表达水平的基因进行聚类。

一种这样的技术是轮廓测量，它评估标记点与其质心的接近程度。一般的想法是，如果一个点被分配给一个质心但仍然靠近其他质心，那么它可能被分配给了错误的质心。通过跨训练集计算这些事件并查看各种k均值聚类，人们寻找k使得标记点整体落入“最佳”或最小模糊排列。

应该说，聚类更多的是一种数据可视化和探索技术。很难确定一个聚类是否正确地解释了数据，尤其是其他聚类。最好将您的聚类与其他相关信息合并。是否有一些关于您的数据的功能或其他信息，例如您知道某些聚类是不可能的？这可以大大减少您的解决方案空间。

于 2009-11-09T14:15:06.337 回答
1

从您的维基百科链接：

关于计算复杂度，k-means 聚类问题是：

  • NP-hard一般欧几里得空间 d 甚至对于 2 个集群
  • 即使在平面上，也适用于一般数量的集群 k 的 NP-hard
  • 如果 k 和 d 固定，则问题可以在 O(ndk+1 log n) 时间内准确解决，其中 n 是要聚类的实体数

因此，通常使用各种启发式算法。

也就是说，找到一个好的 k 值通常是一个启发式过程（即您尝试一些并选择最好的）。

我认为 k-means 是一个很好的起点，它简单且易于实现（或复制）。如果您有严重的性能问题，请仅进一步查看。

如果您要聚类的点集非常大，则一阶优化将是随机选择一个小子集，使用该集来查找您的 k-means。

于 2009-11-09T14:18:27.257 回答
1

选择最佳 K 可以看作是模型选择问题。一种可能的方法是最小描述长度，在这种情况下意味着：您可以存储一个包含所有点的表（在这种情况下 K=N）。在另一个极端，您有 K=1，并且所有点都存储为它们与单个质心的距离。Manning 和 Schutze 的信息检索简介这一部分建议将Akaike 信息准则最小化作为最优 K 的启发式。

于 2009-11-24T10:30:33.940 回答
1

这个问题属于“聚类优化问题”的“内部评估”类，目前最先进的解决方案似乎使用 **Silhouette* 系数*，如此处所述

https://en.wikipedia.org/wiki/Cluster_analysis#Applications

在这里：

https://en.wikipedia.org/wiki/Silhouette_(clustering)：

“轮廓图和平均值可用于确定数据集中的自然簇数”

scikit-learn 在此处 提供了该方法的示例使用实现http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html

于 2016-10-18T11:52:22.847 回答