string - 通过替换对数百万个字符串进行分组

Question

我有大量(XXM-XXXM)字符串，看起来像(一个小样本):

我不知道所有可能的错误字符串，也不知道它们的排列。我想将所有类似的错误分组在一起，并生成一些统计信息，显示每个错误字符串组的错误计数。

所以，本质上，我想将最相似的字符串分组在一起，并且字符串可以属于多个组。

谢谢!

Answer 1

免责声明:我以前从未解决过这样的问题。

我可以想出几种方法来思考你的问题:

• 您正在尝试将每一行聚类为一组聚类
  • 检查数据挖掘算法
• 簇中每条线之间的差异会很小，两个不同簇中线之间的差异会相当大
• 您可以通过比较两条线的集合交集来快速收集相似的线:set(line1.split) & set(line2.split) - 结果集中的元素计数是指示这两条线有多接近。

一段 Python 代码可能如下所示:

import fileinput

CLUSTER_COUNT = 5
MAX_DISTANCE = 5

def main():
    clusters = [Cluster() for i in range(CLUSTER_COUNT)]
    MAXDISTANCE = 3
    for line in  fileinput.input():
        words = set(line.split())
        cluster = sorted(clusters, key=lambda c: c.distanceTo(words))[0]
        cluster.addLine(words, line)

    # print out results (FIXME: write clusters to separate files)
    for cluster in clusters:
        print "CLUSTER:", cluster.intersection
        for line in cluster.lines:
            print line
        print "-" * 80
        print

class Cluster(object):
    def __init__(self):
        self.intersection = set()
        self.lines = []
    def distanceTo(self, words):
        if len(self.intersection) == 0:
            return MAX_DISTANCE 
        return len(words) - len(self.intersection & words)
    def addLine(self, words, line):
        self.lines.append(line) 
        if len(self.intersection) == 0:
            self.intersection = words
        else:
            self.intersection = self.intersection & words

if __name__ == '__main__':
    main()

如果您在主要数据上运行它，您最终应该得到几个集群。注意:更改代码以将簇写入单独的文件。我认为您会希望再次递归地通过代码运行集群，直到找到您感兴趣的子集。