python - 使用 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)]

我的意图是将所有字符串聚集在共享/相似字符组合的组中，即那些是单个字符串的排列的字符串。会有不同的组，例如: a1b1c1d1e1 、 a1b1c1d2 、 a1b2c2 .... a5 。每个簇必须包含 a1b4、b1a4、a1c4 等组合。 因此，每个簇将包含作为给定字符串组合的排列的所有字符串，例如巴布、巴布等 我可以使用任何 python 工具来进行这种聚类吗？ 我正在考虑使用某种距离度量，例如汉明距离或编辑距离。

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

感谢您的时间和知识。

保罗

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 时更新集群来简化计算。