102

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

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

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

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

我查看了类似的问题，但大多数人建议使用 k-means 来聚类点，例如scipy，对于像我这样的初学者来说使用起来非常混乱。另外我认为 k-means 更适合二维或更多维聚类，对吧？有什么方法可以根据数字将 N 个数字的数组划分为多个分区/聚类？

有些人还建议进行严格的范围划分，但它并不总是按预期呈现结果

4

5 回答 5

138

不要对一维问题使用多维聚类算法。一个维度比你天真的想的要特殊得多，因为你实际上可以对它进行排序，这让事情变得容易多了。

事实上，它通常甚至不称为聚类，而是例如分割或自然中断优化。

您可能想查看Jenks Natural Breaks Optimization和类似的统计方法。核密度估计也是一种很好的查看方法，具有强大的统计背景。密度的局部最小值是将数据分成集群的好地方，这样做有统计上的原因。KDE 可能是对一维数据进行聚类的最可靠的方法。

使用 KDE，一维数据表现得更好，这一点再次变得明显。在一维中，您有局部最小值；但在 2D 中，您可能有鞍点和这样的“可能”分裂点。请参阅此鞍点的维基百科插图，了解这样的点可能适合或不适合拆分集群。

有关如何在 Python 中执行此操作的示例，请参见此答案（绿色标记是集群模式；红色标记是数据被切割的点；y 轴是密度的对数似然）：

KDE 与 Python

于 2012-07-17T05:38:50.717 回答
7

这个简单的算法有效：

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.

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

于 2021-07-06T13:02:46.080 回答
4

您可以寻找离散化算法。一维离散化问题与您所要求的非常相似。他们根据频率、分箱策略等决定截止点。

weka在其离散化过程中使用以下算法。

weka.filters.supervised.attribute.Discretize

使用 Fayyad & Irani 的 MDL 方法或 Kononeko 的 MDL 标准

weka.filters.unsupervised.attribute.Discretize

使用简单的分箱

于 2012-07-18T10:14:33.700 回答
3

CKwrap是一个快速而直接的 k-means 聚类函数，虽然文档有点少。

示例用法

点安装ckwrap

import ckwrap

nums= np.array([1,1,2,3,10,11,13,67,71])
km = ckwrap.ckmeans(nums,3)

print(km.labels)
# [0 0 0 0 1 1 1 2 2]


buckets = [[],[],[]]
for i in range(len(nums)):
    buckets[km.labels[i]].append(nums[i])
print(buckets)
# [[1, 1, 2, 3], [10, 11, 13], [67, 71]]
exit()

我希望作者打算让您使用 nd 数组功能，而不是创建列表列表。

其他措施：

km.centers
km.k
km.sizes
km.totss
km.betweenss
km.withinss

底层算法基于这篇文章。

于 2021-05-20T01:30:35.913 回答
0

迟到的回应，只是为了记录。您可以使用Ckmeans.1d.dp对一维数组进行分区。

这种方法保证了最优性，它是 O(n^2)，其中 n 是观察次数。实现是在 C++ 中，在 R 中有一个包装器。

于 2021-12-28T18:39:52.893 回答