20

我用谷歌搜索过,我已经测试过了,这让我束手无策。我有一个需要按相似度分组的数字列表。例如,在 [1, 6, 9, 100, 102, 105, 109, 134, 139] 的列表中,将 1 6 9 放入列表中,将 100、102、105 和 109 放入列表中列表,以及 134 和 139。我的数学很糟糕,我已经尝试过这个,但我无法让它工作。为了尽可能明确,我希望将彼此相距 10 个值以内的数字分组。任何人都可以帮忙吗?谢谢。

4

3 回答 3

39

有很多方法可以进行聚类分析。一种简单的方法是查看连续数据元素之间的间隙大小:

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())
于 2013-02-09T01:31:56.090 回答
6

这将找到组:

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 没有像您的示例显示的那样实际排序,您需要先对其进行排序。

于 2013-02-09T01:29:33.817 回答
3

首先,您可以轻松地将任何序列转换为相邻项目对的序列。只需开球,将其向前移动,然后将未移位和未移位的副本拉上拉链。唯一的技巧是您需要从(<something>, 1)or开始(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
于 2013-03-19T04:30:17.203 回答