在Python中，您如何将这三个区域分组/聚类到数组中？

Question

所以你有一个数组

1
2
3
60
70
80
100
220
230
250

为了更好的理解：

在Python（v2.6）中如何将这三个区域分组/聚类到数组中，以便在这种情况下得到三个包含[1 2 3]、[60 70 80 100]和[220 230 250]的数组。

背景：纵坐标是频率，横坐标是数字。这些数字是由它们的频率表示的十个最高振幅。我想从中创建三个离散的数字以进行模式识别。可能会有更多点，但它们都被相对较大的频率差异所分组，就像您在此示例中看到的在约50和约0之间以及在约100和约220之间。请注意，什么是大的，什么是小的会改变，但聚类之间的差异与组/聚类元素之间的差异相比仍然显着。

- Zurechtweiser

---

这不是一个特定的Python问题。你需要首先选择一个合适的聚类算法，并看看如何在Python中实现它（或者是否已经实现，例如在SciPy中）。 - Björn Pollex

如果问题和数据集总是如此，您可以使用自己的“自制”启发式算法，并对其进行微调以适应您的数据。但是，如果复杂性稍微大一些，我认为您不能避免学习答案中提出的许多好建议和算法。 - heltonbiker

这并不总是“像这样的”。差异在于：1.更多的数字。2.聚类之间的间隔不同。3.聚类中元素之间的间隔不同。然而，仍然存在的是元素间隔和聚类间隔之间的差异显着，换句话说：Delta（元素）<< Delta（聚类）。 - Zurechtweiser

事实上，stats.stackexchange.com是一个更好的提问平台，那里可能已经有一些类似的问题了。 - Has QUIT--Anony-Mousse

Answer 1

如果 x 只是代表索引，那么请注意你的数据点实际上是一维的。你可以使用Scipy的 cluster.vq 模块进行点聚类，该模块实现了k-means算法。

>>> import numpy as np
>>> from scipy.cluster.vq import kmeans, vq
>>> y = np.array([1,2,3,60,70,80,100,220,230,250])
>>> codebook, _ = kmeans(y, 3)  # three clusters
>>> cluster_indices, _ = vq(y, codebook)
>>> cluster_indices
array([1, 1, 1, 0, 0, 0, 0, 2, 2, 2])

这个结果的意思是：前三个点形成一个聚类1（任意标签），接下来的四个点形成聚类0，最后的三个点形成聚类2。根据索引对原始点进行分组留给读者作为练习。

如果想了解更多Python中的聚类算法，请查看scikit-learn。

- Fred Foo

---

我不喜欢“留给读者作为练习”的说法，因为它显得很傲慢。 - Zurechtweiser

这个短语仅表示我太忙/懒得解决列表处理的枯燥工作，我相信你可以自己解决。它也会分散回答的核心。我不明白其中哪里显得傲慢，我当然没有傲慢的意思。 - Fred Foo

好的，看起来这只是一个简单的误解。 - Zurechtweiser

如果你觉得结果很令人信服，可以尝试对数据集array=list(range(15))进行处理。K-means算法不适用于一维数据，特别是在不知道k的情况下。事实上，关于k-means唯一值得说的好话就是它非常容易实现。 - Has QUIT--Anony-Mousse

我不是在试图让你的答案看起来不好。对于一维数据，k-means算法并没有太多意义，但我的观点是，a) k-means算法对数据做了很多隐含的假设：簇的数目相同且数量已知；b) 聚类不仅仅是将对象分组，而实际上是以解决特定任务为前提的对象分组方式，这不能由算法回答，而只能由领域专家回答。 - Has QUIT--Anony-Mousse

Answer 2

这是一个用Python实现的简单算法，用于检查一个值是否与聚类的平均值相比过于偏离（以标准差为度量）:

from math import sqrt

def stat(lst):
    """Calculate mean and std deviation from the input list."""
    n = float(len(lst))
    mean = sum(lst) / n
    stdev = sqrt((sum(x*x for x in lst) / n) - (mean * mean)) 
    return mean, stdev

def parse(lst, n):
    cluster = []
    for i in lst:
        if len(cluster) <= 1:    # the first two values are going directly in
            cluster.append(i)
            continue

        mean,stdev = stat(cluster)
        if abs(mean - i) > n * stdev:    # check the "distance"
            yield cluster
            cluster[:] = []    # reset cluster to the empty list

        cluster.append(i)
    yield cluster           # yield the last cluster

这将返回您在示例中所期望的结果，其中5 < n < 9:

>>> array = [1, 2, 3, 60, 70, 80, 100, 220, 230, 250]
>>> for cluster in parse(array, 7):
...     print(cluster)
[1, 2, 3]
[60, 70, 80, 100]
[220, 230, 250]

- Rik Poggi

---

数组 = [1, 2, 3, 4, 60, 70, 80, 100, 220, 230, 250] 将代码分成两个数组 1->3 和 4->250。 - Zurechtweiser

问题在于我在Python3中进行了测试，而在Python2中，使用整数n的sum(lst) / n结果为整数，因此mean为1而不是1.5。将len(lst)转换为float即可解决问题（我已编辑代码）。 - Rik Poggi

这可能是迄今为止提出的最明智的方法之一（例如，在range（1,15）上运行kmeans）。然而，您仍应该思考一下您想要实现什么。有许多方法可以产生这样的数组拆分；哪个方法适合取决于您使用它的目的以及您的真实数据长什么样子。这个答案+1，因为它不仅仅因为它是聚类就使用kmeans，而是实际考虑了问题。 - Has QUIT--Anony-Mousse

自上次发布以来已经很长时间了，但您能否考虑使用字典内嵌字典而不是数组=[1,2,3...]的代码？ - billwild

@RikPoggi，您能否看一下我的问题，它在这里使用了您的代码： http://stackoverflow.com/questions/18721774/python-cluster-variables-in-list-of-tuples-by-2-factors-silmutanously - Irek

我知道时间有点久了，这个解决方案很好但是能不能自动化n呢？一个固定的数字并不总是能得到正确的结果。例如，假设n=7在大多数情况下都可以工作，但对于这个数组 [130, 167, 213, 441, 445, 451, 478, 515, 526, 564, 655, 782, 1261] 它无法正确分组。 3,9,1 对我来说是最好的选择，但实际上是3,3,6,1。 - Ergec

Answer 3

我假设您想要一个相当好但简单的算法。

如果您知道您需要N个簇，则可以取输入列表（已排序）中连续成员之间的差异（delta）。例如，在numpy中：

 deltas = diff( sorted(input) )

那么你可以将截断点放在发现的前N-2个最大差异处。

如果你不知道N是多少，情况会更加棘手。在这种情况下，您可以在看到大于某个大小的增量时放置截断点。这将成为一个手动调整的参数，虽然不太好，但可能已经足够好了。

- Adrian Ratnapala

Answer 4

您可以用不同的方法来解决这个问题。当您使用“聚类”这个关键词时，其中一个显而易见的方法是使用kmeans（请参阅其他回复）。

但是，您可能需要先更仔细地了解自己实际上在做什么或试图做什么，而不仅仅是在您的数据上随机使用函数。

就我所知，从您的问题中可以看出，您有一些一维值，希望将它们分成一个未知数量的组，是吗？好吧，k-means 可能会起作用，但事实上，您只需查找数据集中前 k 大的差异即可。例如，对于任何索引 i>0，请计算 k[i] - k[i-1]，并选择此大于其他部分的 k 索引。最可能的情况是，您的结果实际上比使用 k-means 更好且更快。

Python 代码如下：

k = 2
a = [1, 2, 3, 60, 70, 80, 100, 220, 230, 250]
a.sort()
b=[] # A *heap* would be faster
for i in range(1, len(a)):
  b.append( (a[i]-a[i-1], i) )
b.sort()
# b now is [... (20, 6), (20, 9), (57, 3), (120, 7)]
# and the last ones are the best split points.
b = map(lambda p: p[1], b[-k:])
b.sort()
# b now is: [3, 7]
b.insert(0, 0)
b.append(len(a) + 1)
for i in range(1, len(b)):
  print a[b[i-1]:b[i]],
# Prints [1, 2, 3] [60, 70, 80, 100] [220, 230, 250]

（这实际上可以看作是简单的单链接聚类！）

一种更先进的方法，实际上摆脱了参数k，计算b[*][1]的平均值和标准偏差，并在数值大于mean+2*stddev时进行分裂。尽管如此，这仍然是一个相当粗糙的启发式方法。另一个选择是实际上假设一个值分布，例如k个正态分布，然后使用Levenberg-Marquardt将这些分布拟合到您的数据。

但这真的是你想做的吗？

首先，尝试定义什么应该是群集，而什么不应该是群集。第二部分更重要。

- Has QUIT--Anony-Mousse

---

我认为我的定义是全面的。如果不是，请具体说明您缺少什么。 - Zurechtweiser

insert()需要传入2个参数，但只传入了1个。 - Zurechtweiser

@RichartBremer：我认为他/她的意思是 b.insert(0,0)，因为 b 保存了“breaker”索引，所以它还需要第一个（0）来开始。 - Rik Poggi

Answer 5

你可以使用最近邻聚类。对于一个点属于其中一个簇，它的最近邻也必须属于该簇。对于你展示的情况，你只需要沿着x轴迭代并比较相邻点之间的差异。当与前一个点的差异大于与下一个点的差异时，表示开始了一个新的簇。

- Michael J. Barber