使用 python 聚类字符串的最佳方法

Question

我有 3200000 个字符串（字母表的所有可能组合 = 'ACDEFGHIKLMNPQRSTVWY'）。数据小例子：

['AAAAA', 'AAAAC', 'AAAAD', 'AAAAE', 'AAAAF', 'AAAAG', 'AAAAH',
 'AAAAI', 'AAAAK', 'AAAAL', 'AAAAM', 'AAAAN', 'AAAAP', 'AAAAQ',
 'AAAAR', 'AAAAS', 'AAAAT', 'AAAAV', 'AAAAW', 'AAAAY', 'AAACA',
 'AAACC', 'AAACD', 'AAACE', 'AAACF', 'AAACG', 'AAACH', 'AAACI',
 'AAACK', 'AAACL', 'AAACM', 'AAACN', 'AAACP', 'AAACQ', 'AAACR',
 'AAACS', 'AAACT', 'AAACV', 'AAACW', 'AAACY'...]

我用这段代码来构造小字符串的大列表。

def get_all_possible_kmers(alphabet, k):
    return [''.join(char) for char in itertools.product(alphabet, repeat=k)]

我的意图是将所有字符串聚集成 shared/similar 个字符组合的组，即那些是单个字符串的排列。会有不同的组，例如： a1b1c1d1e1 ， a1b1c1d2 ， a1b2c2 .... a5 。每个集群都必须包含 a1b4、b1a4、a1c4 等组合。因此，每个集群将包括所有字符串，这些字符串是给定字符串组合的排列，例如abbbb、babbb 等我可以使用任何 python 工具来进行这种聚类吗？我在考虑使用某种距离度量，如汉明距离或 levenshtein 距离。

你们有什么适合开始的方向吗？

谢谢你的时间和知识。

保罗

Answer 1

您可以使用 collections.Counter 生成簇哈希并更新字典中的集合。

例如：

from collections import Counter, defaultdict

clusters = defaultdict(set)
for item in get_all_possible_kmers(alphabet, k):
    clusters[str(Counter(item))].add(item)

您还可以将 str(Counter(item)) 格式化为您需要的格式 (a1b4...)

此外，您可以通过在获得下一个 kmer 时更新聚类来简化计算。

使用 python 聚类字符串的最佳方法

Best way for clustering strings using python

python

cluster-analysis