集群数量未知的无监督集群
artificial-intelligence
cluster-analysis
machine-learning
5
0

我在3维中有大量的向量。我需要基于欧几里得距离对它们进行聚类,以使任何特定聚类中的所有向量之间的欧几里得距离都小于阈值“ T”。

我不知道有多少集群。最后,可能存在不属于任何群集的单个矢量,因为对于空间中的任何矢量,其欧式距离都不小于“ T”。

在此应使用哪些现有算法/方法?

参考资料:
Stack Overflow
收藏
评论
共 3 个回答
高赞 时间 活跃

moooeeeep的答案建议使用分层聚类。我想详细说明如何选择群集的阈值。

一种方法是基于不同的阈值t1t2t3 ,...计算聚类,然后为聚类的“质量”计算度量。前提是具有最佳群集数的群集的质量将具有质量度量的最大值。

我过去使用的高质量指标的一个例子是Calinski-Harabasz。简要地说:您可以计算平均集群间距离,并将它们除以集群内距离。最佳聚类分配将具有彼此最分开的聚类和“最紧密”的聚类。

顺便说一句,您不必使用分层群集。您还可以使用类似k -means的方法,对每个k进行预先计算,然后选择Calinski-Harabasz得分最高的k

如果您需要更多参考资料,请告诉我,我会在硬盘上搜寻一些论文。

收藏
评论

查看DBSCAN算法。它根据矢量的局部密度进行聚类,即它们的距离不得超过ε距离,并且可以自动确定聚类数。它还认为离群点(即,具有不足够数量的ε-邻居的点)不属于群集。 Wikipedia页面链接到一些实现。

收藏
评论

您可以使用分层聚类 。这是一种相当基本的方法,因此有许多可用的实现。例如,它包含在Python的scipy中

例如,请参见以下脚本:

import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster

# generate 3 clusters of each around 100 points and one orphan point
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20

# clustering
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")

# plotting
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "threshold: %f, number of clusters: %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()

产生的结果类似于下图。 集群

作为参数给出的阈值是距离值,在此基础上,决定是否将点/群集合并到另一个群集中。也可以指定所使用的距离度量。

请注意,有多种方法可用于计算群集内/群集间相似度,例如最近点之间的距离,最远点之间的距离,到群集中心的距离等。 scipys分层聚类模块( 单个/完整/平均...链接 )也支持其中一些方法。根据您的帖子,我认为您想使用完整的链接

请注意,如果小型(单点)群集不满足其他群集的相似性标准(即距离阈值),则此方法也允许它们。


还有其他一些性能会更好的算法,这些算法在具有大量数据点的情况下将变得有意义。正如其他答案/评论所建议的那样,您可能还想看看DBSCAN算法:


有关这些和其他集群算法的概述,请查看以下演示页面(Python的scikit-learn库的内容):

从该位置复制的图像:

http://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html

如您所见,每种算法都会对需要考虑的簇的数量和形状做出一些假设。是算法强加的隐式假设,还是参数化指定的显式假设。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号