你如何在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]

背景:

y轴是频率,x轴是数字.这些数字是由它们的频率表示的十个最高幅度.我想从它们创建三个离散数字用于模式识别.可能会有更多的点,但所有这些点都按照相对较大的频率差异进行分组,如本例所示,在大约50和大约0之间以及大约100和大约220之间.请注意,什么是大的,什么是小变化但是与群组/群集的元素之间的差异相比,群集之间的差异仍然很大.

Answer 1

这是一个在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]

Answer 2

如果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.

Answer 3

我假设你想要一个非常好但很简单的算法.

如果您知道需要N个簇,则可以获取(已排序)输入列表的连续成员之间的差异(增量).例如在numpy:

 deltas = diff( sorted(input) )

然后你可以把你的cuttoffs放在你发现N-2最大差异的地方.

如果你不知道N是什么,事情会更棘手.每当看到大于特定大小的delta时,您可以放置​​cuttoffs.这将是一个手动调整的参数,这不是很好,但可能对你来说足够好.

Answer 4

您可以通过各种方式解决此问题.抛出关键字"clustering"时,其中一个显而易见的是使用kmeans(参见其他回复).

但是,您可能希望首先更清楚地了解您实际在做什么或尝试做什么.而不是仅仅在您的数据上抛出随机函数.

据我所知,你有一些1维值,你想将它们分成未知数量的组,对吧？好吧,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],并在值大于say时分割mean+2*stddev.这仍然是一个相当粗糙的启发式.另一个选择是实际假设一个值分布,例如k正态分布,然后使用例如Levenberg-Marquardt来拟合数据的分布.

但这真的是你想要做的吗？

首先尝试定义什么应该是一个集群,什么不是.第二部分更为重要.