如何在不指定聚类数的情况下对列表项进行聚类

Question

我的目标是根据下面列表中任意两个相邻项目之间的距离，将这些项目分成不同的组。组的数量没有具体要求，只要相邻项目之间的最大距离不超过某个值，它们就可以被归为同一组。

我的尝试

import itertools
max_dist=20
_list=[1,48,52,59,89,94,103,147,151,165]
Ideal_result= [[1],[48,52,59],[89,94,103],[147,151,165]]

def clust(list_x, max_dist):
    q=[]
    for a, b in itertools.combinations(list_x,2):
        if b-a<=20:
            q.append(a),(b)
        else:continue
        yield q
print list(clust(_list,max_dist))

输出结果：

[[48,48,52,89,89,94,147,147,151],[48,48,52,89,89,94,147,147,151],..]`

输出结果完全不对，但我只是想展示一下我的尝试。

有没有什么建议可以让我得到理想的结果？谢谢。

Answer 1

这个代码能通过你的测试：

def cluster(items, key_func):
    items = sorted(items)
    clusters = [[items[0]]]
    for item in items[1:]:
        cluster = clusters[-1]
        last_item = cluster[-1]
        if key_func(item, last_item):
            cluster.append(item)
        else:
            clusters.append([item])
    return clusters

在这里，key_func 函数会返回 True，如果当前的项和前一个项应该被归为同一组：

>>> cluster([1,48,52,59,89,94,103,147,151,165], lambda curr, prev: curr-prev < 20)
[[1], [48, 52, 59], [89, 94, 103], [147, 151, 165]]

另一种可能性是修改 "等效代码"，让 itertools.groupby() 的关键函数也能接受多个参数。