1D数字阵列聚类

Question

可能重复:
最佳地聚类一维数据？

所以,假设我有一个这样的数组:

[1,1,2,3,10,11,13,67,71]

有没有一种方便的方法将数组分区为这样的东西？

[[1,1,2,3],[10,11,13],[67,71]]

我查看了类似的问题,但是大多数人建议使用k-means来聚集点,比如scipy,这对像我这样的初学者来说非常混乱.另外我认为k-means更适合两维或更多维聚类吧？有没有办法根据数字将N个数组分组到多个分区/聚类？

有些人还提出了严格的范围分区,但并不总是按预期呈现结果

Answer 1

不要将多维聚类算法用于一维问题.单个维度比你想象的要特别得多,因为你可以对它进行实际排序,这会让事情变得更容易.

实际上,它通常甚至不称为聚类,而是例如分段或自然中断优化.

您可能想看看Jenks Natural Breaks Optimization和类似的统计方法.核密度估计也是一种很好的方法,具有强大的统计背景.密度的局部最小值是将数据分成簇的好地方,有统计学的理由这样做.KDE可能是用于聚类1维数据的最合理方法.

使用KDE,再次证明一维数据表现得更好.在1D,你有当地的最小值; 但在2D中你可能有马鞍点和这样的"可能"分裂点.请参阅此维基百科关于鞍点的插图,了解这一点可能适合或不适合拆分群集.

Answer 2

这个简单的算法有效：

points = [0.1, 0.31,  0.32, 0.45, 0.35, 0.40, 0.5 ]

clusters = []
eps = 0.2
points_sorted = sorted(points)
curr_point = points_sorted[0]
curr_cluster = [curr_point]
for point in points_sorted[1:]:
    if point <= curr_point + eps:
        curr_cluster.append(point)
    else:
        clusters.append(curr_cluster)
        curr_cluster = [point]
    curr_point = point
clusters.append(curr_cluster)
print(clusters)

上面的示例簇指向一个组，使得组中的每个元素至多eps远离该组中的另一个元素。DBSCAN这就像的聚类算法eps=0.2, min_samples=1。正如其他人指出的那样，一维数据可以让您直接解决问题，而不是使用像DBSCAN.

对于一些包含我测试过的元素的小型数据集，上述算法的速度提高了 10-100 倍<1000。