在Python中对数字进行分组/聚类

Question

我在网上查了很多资料，也自己试过，但还是搞不定这个问题。我有一串数字，想把它们按相似性分组。比如说，在这个数字列表 [1, 6, 9, 100, 102, 105, 109, 134, 139] 中，1、6、9 应该分到一组，100、102、105 和 109 也应该分到一组，而134和139则是另一组。我数学不好，试了很多次都没成功。为了更清楚，我想把那些相差不超过10的数字放在一起。有没有人能帮帮我？谢谢！

Answer 1

首先，你可以很简单地把任何一串东西变成一对一对相邻的项。只需要把它复制一份，向前移动一位，然后把这两份合并在一起。唯一需要注意的是，你得从 (<something>, 1) 或者 (139, <something>) 开始，因为在这种情况下，我们想要的不是每一对元素，而是每个元素对应的一对：

def pairify(it):
    it0, it1 = itertools.tee(it, 2)
    first = next(it0)
    return zip(itertools.chain([first, first], it0), it1)

（这不是最简单的写法，但我觉得对那些不熟悉 itertools 的人来说，这种写法可能更容易理解。）

>>> a = [1, 6, 9, 100, 102, 105, 109, 134, 139]
>>> list(pairify(a))
[(1, 1), (1, 6), (6, 9), (9, 100), (100, 102), (102, 105), (105, 109), (109, 134), (134, 139)]

接下来，使用一个稍微复杂一点的版本，基于 Ned Batchelder 的方法，你可以直接用 groupby。

不过，我觉得在这种情况下，这样做可能会比直接写一个生成器来实现同样的功能更复杂。

def cluster(sequence, maxgap):
    batch = []
    for prev, val in pairify(sequence):
        if val - prev >= maxgap:
            yield batch
            batch = []
        else:
            batch.append(val)
    if batch:
        yield batch

Answer 2

这段代码会找到分组：

nums = [1, 6, 9, 100, 102, 105, 109, 134, 139]
for k, g in itertools.groupby(nums, key=lambda n: n//10):
    print k, list(g)

0 [1, 6, 9]
10 [100, 102, 105, 109]
13 [134, 139]

注意，如果你的数字（nums）并不是像你示例中那样已经排好序的，你需要先把它们排序。

Answer 3

进行聚类分析的方法有很多种。其中一种简单的方法是观察相邻数据元素之间的间隔大小：

def cluster(data, maxgap):
    '''Arrange data into groups where successive elements
       differ by no more than *maxgap*

        >>> cluster([1, 6, 9, 100, 102, 105, 109, 134, 139], maxgap=10)
        [[1, 6, 9], [100, 102, 105, 109], [134, 139]]

        >>> cluster([1, 6, 9, 99, 100, 102, 105, 134, 139, 141], maxgap=10)
        [[1, 6, 9], [99, 100, 102, 105], [134, 139, 141]]

    '''
    data.sort()
    groups = [[data[0]]]
    for x in data[1:]:
        if abs(x - groups[-1][-1]) <= maxgap:
            groups[-1].append(x)
        else:
            groups.append([x])
    return groups

if __name__ == '__main__':
    import doctest
    print(doctest.testmod())