确定k近邻的最佳k值

Question

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

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

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

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

我要说的问题是：

如何确定k的“最佳”值，从而使所形成的簇是稳定的和可视可验证的

问题：

• 假设这不是NP-完全的，找到一个好的k的时间复杂度是多少(可能在运行k-means算法的次数中得到了报告)。
• K-是这类问题的好起点吗？如果是的话，你还会推荐什么其他的方法。一个具体的例子，在一个轶事/经验的支持下，将是马西邦。
• 你会推荐什么样的捷径/近似来提高性能。

Answer 1

对于簇数未知的问题，聚类分层聚类往往是一种比k-均值更好的方法。

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

还有其他分层聚类方法(见Imran的评论中提出的论文)。集团化方法的主要优点是有许多实现可以供您使用。

Answer 2

为了使用k-均值，您应该知道有多少个集群。您不能尝试简单的元优化，因为您将添加的集群越多(每个数据点最多可以添加一个集群)，就越会导致您的过度适应。您可能会寻找一些集群验证方法，并使用它来优化k超参数，但根据我的经验，它很少能正常工作。它也很贵。

如果我是您，我将进行PCA，最终在多项式空间上(注意您的可用时间)，这取决于您对输入的了解程度，并沿着大多数代表组件进行聚类。

更多关于你的数据集的信息对于一个更精确的答案是非常有帮助的。

Answer 3

这是我的近似解：

1. 从k=2开始。
2. 多次尝试：
   1. 运行k-均值算法来查找k簇。
   2. 找到从原点到星系团质心的均方距离。

​

1. 重复2-3，找出距离的标准差.这是集群的稳定性的代理。
2. 如果k的簇稳定性
3. 增量k乘以1。

该算法的理论基础是k簇的集合数对于k的“好”值来说是很小的。

如果我们能找到稳定的局部最优或稳定的最优增量，那么我们就可以找到一组很好的簇，它们不能通过加入更多的簇而得到改进。