无监督聚类及未知簇数

Question

我有一组大量的三维向量。 我需要根据欧几里得距离将它们聚类，使得任何特定簇中的所有向量彼此之间的欧几里德距离小于阈值“T”。

我不知道存在多少个簇。最后可能存在单独的向量，因为它与空间中的任何向量的欧几里德距离都不小于“T”，而不属于任何簇。

应该使用哪些现有算法/方法？

- London guy

---

一定要在维基百科上查看DBSCAN。 - Has QUIT--Anony-Mousse

@Anony-Mousse 你有什么想法可以从DBSCAN获取簇代表吗？ - Divij Sehgal

DBSCAN聚类可以具有任意形状。那么什么是一个好的“代表”呢？ - Has QUIT--Anony-Mousse

DBSCAN 带有示例用法：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN - Jean Monet

Answer 1

你可以使用层次聚类。这是一个相当基本的方法，因此有许多实现可用。例如，它包含在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 层次聚类模块（single/complete/average... linkage）也支持其中一些方法。根据您的帖子，我认为您想使用 complete linkage。

请注意，如果小的（单点）簇不符合其他簇的相似性标准，即距离阈值，则该方法也允许它们存在。

---

还有其他算法可以更好地处理大量数据点的情况。正如其他答案/评论所建议的那样，您可能还想看一下DBSCAN算法：

• 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

---

如果您想了解更多关于这些聚类算法的信息，还可以查看Python scikit-learn库的演示页面：

• http://scikit-learn.org/stable/modules/clustering.html

从那个地方复制的图像：

正如您所见，每个算法都对需要考虑的簇的数量和形状做出了一些假设。无论是算法强加的隐含假设还是参数化指定的显式假设。

- moooeeeep

---

但是这种聚类方式不允许存在孤立向量，对吗？根据我在这里写的条件，如果有一个向量与空间中的任何其他向量的欧几里得距离都大于“T”，那么它应该被单独保留。希望这一点清楚了 - 如果之前没有表达清楚，对不起。 - London guy

@AbhishekShivkumar - 请看我的编辑。当然也可能存在单点聚类。 - moooeeeep

那么，有人如何找到聚类的中心？ - Euler_Salter

@Euler_Salter 您可以按簇进行排序，然后按簇进行分组，接着为每个簇计算各点的平均/中位坐标。 - moooeeeep

Answer 2

moooeeeep的回答建议使用分层聚类。我想进一步说明如何选择聚类的阈值。

一种方法是基于不同的阈值t1，t2，t3等计算聚类，然后计算聚类"质量"的指标。前提是具有最佳聚类数的聚类的质量指标将具有最大值。

我过去使用的一个好质量指标示例是Calinski-Harabasz。简而言之：计算平均簇间距离并将其除以簇内距离。最优的聚类分配将具有相互之间分离度最大的群集，并且群集最为"紧密"。

顺便说一下，您不必使用分层聚类。您还可以使用像k-means这样的东西，为每个k预先计算，然后选择具有最高Calinski-Harabasz得分的k。

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

- Max

---

是的，我需要一些关于分层聚类和Calinski-Harabasz得分的论文！谢谢 - change

我知道这已经过时了，但我也对Calinski-Harabasz k均值与分层Calinski-Harabasz感兴趣。 - physincubus

Answer 3

了解一下DBSCAN算法。它基于向量的局部密度进行聚类，即向量之间的距离不能超过某个ε值，并且可以自动确定聚类数量。此外，它还考虑了异常值，即那些没有足够数量的ε邻居点的点不会被归为任何一个簇中。维基百科页面链接了一些实现。

- Fred Foo

Answer 4

使用OPTICS，它在大数据集上表现良好。

OPTICS：Ordering Points To Identify the Clustering Structure（有序点识别聚类结构），与DBSCAN密切相关，找到高密度的核心样本，并从它们扩展聚类1。与DBSCAN不同的是，对于可变邻域半径保留聚类层次结构。比当前sklearn实现的DBSCAN更适合用于大型数据集

from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)

根据您的需求微调eps，min_samples。

- Ravindra babu

Answer 5

我想通过使用层次聚类来补充moooeeeep的答案。 尽管选择阈值相当“随意”，但这个解决方案对我很有用。 参考其他来源并进行自己的测试后，我得到了更好的方法，可以通过树状图轻松选择阈值：

from scipy.cluster import hierarchy
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt

ori_array = ["Your_list_here"]
ward_array = hierarchy.ward(pdist(ori_array))
dendrogram = hierarchy.dendrogram(hierarchy.linkage(ori_array, method  = "ward"))
plt.title('Dendrogram')
plt.xlabel('Customers')
plt.ylabel('Euclidean distances')
plt.show()

你会看到如下的图形点击这里。然后通过绘制水平线，比如在距离=1的位置，连接数将成为你期望的聚类数量。所以在这里我选择阈值=1来得到4个聚类。

threshold = 1
clusters_list = hierarchy.fcluster(ward_array, threshold, criterion="distance")
print("Clustering list: {}".format(clusters_list))

现在，cluster_list 中的每个值都将是 ori_array 中相应点的分配簇标识符。

- Phạm Tùng Lâm

Answer 6

你可能没有解决方案：当任意两个不同的输入数据点之间的距离始终大于T时，就会出现这种情况。如果你想仅从输入数据计算聚类数，可以查看MCG，这是一种具有自动停止准则的分层聚类方法：请参阅https://hal.archives-ouvertes.fr/hal-02124947/document中的免费研讨论文（包含参考文献）。

- Petitjean

Answer 7

我需要一种方法来对OCR输出的行进行“模糊排序”，当输出有时是无序的，但在块内，行通常是有序的。在这种情况下，要排序的项目是描述位置'x'，'y'和大小'w'，'h'的字典。一般的聚类算法似乎过于复杂，而且我需要在排序期间保持项目的顺序。在这里，我可以将容差tol设置为大约1/4的行间距，并使用字段'y'调用它。

def fuzzy_lod_sort(lod, field, tol):
    # fuzzy sort lod into bins within +/- tol
    # maintain original order.
    
    # first determine the bins.
    val_list = [d[field] for d in lod]
    vals_sorted = sorted(val_list)
    
    bins_lol = []
    i = 0
    for j, v in enumerate(vals_sorted):
        if not j:
            bins_lol.append([v])
            continue
            
        cur_bin_avg = statistics.mean(bins_lol[i])
        if abs(cur_bin_avg - v) <= tol:
            bins_lol[i].append(v)
            continue
        
        i += 1
        bins_lol.append([v])
        
    # now sort into the bins, maintaining the original order.
    # the bins will be the center of the range of 'y'.
    bins = [statistics.mean(binlist) for binlist in bins_lol]
    
    # initialize the list of bins
    lolod = []
    for _ in range(len(bins)):
        lolod.append([])
    
    for d in lod:
        bin_idx = closest_bin_idx(bins, d[field])
        lolod[bin_idx].append(d)

    # now join the bins.
    result_lod = []
    for lod in lolod:
        result_lod.extend(lod)
    
    return result_lod
    
        
def closest_bin(bins, val):
    return min(bins, key=lambda bin:abs(bin - val))
    
    
def closest_bin_idx(bins, val):
    return bins.index(closest_bin(bins, val))

麻烦在于OCR输出的'y'坐标是基于单词周围的轮廓线，同一行中后面的单词可能具有比先前的单词更低的'y'坐标。 因此，完全按'y'排序无法正常工作。 这很像聚类算法，但意图略有不同。 我对数据点的统计信息不感兴趣，但我对每个点位于哪个聚类组非常感兴趣，并且保持原始顺序非常重要。

也许有一些方式使用内置排序进行模糊排序，这可能是一维问题聚类选项的替代方案。

- Ray Lutz