具有未知簇数的无监督聚类 [英] Unsupervised clustering with unknown number of clusters
问题描述
我有大量的 3 维向量.我需要根据欧几里德距离对这些进行聚类，以便任何特定集群中的所有向量彼此之间的欧几里德距离小于阈值T".
我不知道有多少集群存在.最后，可能存在不属于任何集群的单个向量，因为其欧氏距离不小于空间中的任何向量的T".
这里应该使用哪些现有的算法/方法?
您可以使用).根据您的帖子，我认为您希望使用
如您所见，每个算法都会对需要考虑的集群的数量和形状做出一些假设.无论是算法强加的隐式假设还是参数化指定的显式假设.
I have a large set of vectors in 3 dimensions. I need to cluster these based on Euclidean distance such that all the vectors in any particular cluster have a Euclidean distance between each other less than a threshold "T".
I do not know how many clusters exist. At the end, there may be individual vectors existing that are not part of any cluster because its euclidean distance is not less than "T" with any of the vectors in the space.
What existing algorithms / approach should be used here?
You can use hierarchical clustering. It is a rather basic approach, so there are lots of implementations available. It is for example included in Python's scipy.
See for example the following script:
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()
Which produces a result similar to the following image.
The threshold given as a parameter is a distance value on which basis the decision is made whether points/clusters will be merged into another cluster. The distance metric being used can also be specified.
Note that there are various methods for how to compute the intra-/inter-cluster similarity, e.g. distance between the closest points, distance between the furthest points, distance to the cluster centers and so on. Some of these methods are also supported by scipys hierarchical clustering module (single/complete/average... linkage). According to your post I think you would want to use complete linkage.
Note that this approach also allows small (single point) clusters if they don't meet the similarity criterion of the other clusters, i.e. the distance threshold.
There are other algorithms that will perform better, which will become relevant in situations with lots of data points. As other answers/comments suggest you might also want to have a look at the DBSCAN algorithm:
- https://en.wikipedia.org/wiki/DBSCAN
- http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html
- http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN
For a nice overview on these and other clustering algorithms, also have a look at this demo page (of Python's scikit-learn library):
Image copied from that place:
As you can see, each algorithm makes some assumptions about the number and shape of the clusters that need to be taken into account. Be it implicit assumptions imposed by the algorithm or explicit assumptions specified by parameterization.
这篇关于具有未知簇数的无监督聚类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
