如何聚类一组字符串？

Question

我的数据集看起来像这样

['', 'ABCDH', '', '', 'H', 'HHIH', '', '', '', '', '', '', '', '', '', '', '', 'FECABDAI', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'FABHJJFFFFEEFGEE', 'FFFF', '', '', '', '', '', '', '', '', '', 'FF', 'F', 'FF', 'F', 'F', 'FFFFFFIFF', '', 'FFFFFFF', 'F', '', '', 'F', '', '', '', '', '', '', '', 'F', '', '', 'ABB', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'FF', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'F', 'FFEIE', 'FF', 'ABABCDIIJCCFG', '', 'FABACFFF', 'FEGGIHJCABAGGFEFGGFEECA', '', 'FF', 'FFGEFGGFFG', 'F', 'FFF', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'I', '', '', 'ABIIII', '', '', '', '', 'I', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'AAAAA', 'AFGFE', 'FGFEEFGFEFGFEFGJJGFEACHJ', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'JFEFFFFFFF', '', 'AAIIJFFGEFGCABAGG', '', '', '', '', '', '', '', '', '', 'F', 'JFJFJFJ', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'F', '', '', '', '', '', '', '', '', 'F', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'F', 'FGFEFGFE', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '']

这只是一个示例，但我会有更多的字符串。我如何对它们进行聚类，使每个聚类都有某种模式

Answer 1

我建议的想法起源于文本处理、NLP 和信息检索，并且广泛用于具有 characters/information 序列（如遗传信息）的情况。因为您必须保留序列，所以我们可以使用 n-gram 的概念。我在以下示例中使用二元语法，但您可以概括为更高阶的语法。 N-gram 有助于保留数据中的 顺序模式 。别担心 - 我们一直在借鉴其他科学领域的想法 - 甚至编辑距离和动态规划最初也不是计算机科学概念。

有很多可能的方法来解决这个问题 - 每一种都是独一无二的，并且没有正确的方法 - 至少没有足够的研究来证明哪一种是正确的。这是我的看法。

因此，我们的目标是从您的数据字符串中创建一个类似词袋的向量——并且这些向量可以很容易地馈送到任何机器学习工具或库中进行聚类。步骤的快速总结：-

收集二元组（和一元组等）
创建字典获取词袋（附代码）
创建从字符串中获取向量的功能

让我们开始吧

import numpy
from sklearn.cluster import KMeans
def getStringBigrams(string):
    if len(string) <= 0: return []
    if len(string) == 1: return string[0] # Handle strings with only one character = extract unigram
    return [string[i]+string[i+1] for i in range(len(string)-1)]

def getDataBigrams(strings):
    return [getStringBigrams(x) for x in strings]

所以这里这些函数会将给定的字符串转换为一组两个字符（如果只有一个字符，则为单个字符）。您可以修改它们以捕获 3-gram 或什至是所有可能的 uni-、bi- 和 tri-gram 的完整集合。随意尝试。

现在如何将字符串转换为向量？我们将定义一个将字符串转换为向量的函数，以处理特定 n-gram 出现的次数。这称为词袋。在这里，这些是屏幕袋。以下两个函数可以帮助您：

def generateDictionary(data):
    '''
    This function identifies unique n-grams in your data.
    '''
    vocab = set()
    for line in data:
        for item in line:
            vocab.add(item)
    dictionary = {}
    i=0
    for item in vocab:
        dictionary[item] = i
        i+=1
    return dictionary

    def doc2Bow(bigramData, dictionary):
    ''' 
    Take single document in bigram format and return a vector
    '''
    vect = [0]*len(dictionary) # Initialize vector to zero
    for gram in bigramData:
        vect[dictionary[gram]]+=1
    return numpy.asarray(vect)  # Convert to numpy vector

瞧！我们完成了。现在将您的数据向量提供给您选择的任何 K-Means 实现。我使用了 SKLearn。

strings = ['', 'ABCDH', '', '', 'H', 'HHIH', '', '', '', '', '', '', '', '', '', '', '', 'FECABDAI', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'FABHJJFFFFEEFGEE', 'FFFF', '', '', '', '', '', '', '', '', '', 'FF', 'F', 'FF', 'F', 'F', 'FFFFFFIFF', '', 'FFFFFFF', 'F', '', '', 'F', '', '', '', '', '', '', '', 'F', '', '', 'ABB', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'FF', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'F', 'FFEIE', 'FF', 'ABABCDIIJCCFG', '', 'FABACFFF', 'FEGGIHJCABAGGFEFGGFEECA', '', 'FF', 'FFGEFGGFFG', 'F', 'FFF', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'I', '', '', 'ABIIII', '', '', '', '', 'I', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'AAAAA', 'AFGFE', 'FGFEEFGFEFGFEFGJJGFEACHJ', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'JFEFFFFFFF', '', 'AAIIJFFGEFGCABAGG', '', '', '', '', '', '', '', '', '', 'F', 'JFJFJFJ', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'F', '', '', '', '', '', '', '', '', 'F', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', 'F', 'FGFEFGFE', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '']

您应该选择从文件中读取字符串

strings = [x for x in strings if len(x) > 0] # Just cleanup for experiment purpose
nGramData = getDataBigrams(strings)
dictionary = generateDictionary(nGramData)
data = [doc2Bow(nGramData[i], dictionary) for i in range(len(nGramData))]

K = 10
km = KMeans(init='k-means++', n_clusters=K, n_init=10)

km.fit(data)

然后我终于看到我的集群使用 km.labels_ 属性的 KMeans class。

这是您的集群。查看控制台（底部）window - 有十个集群。

现在你可以修改我在代码中写的特征生成，看看你的修改效果如何。不仅仅是二元组，而是提取所有可能的一元组、二元组和三元组，并使用它们来创建 BOW。会有显着差异。您还可以使用字符串的长度作为特征。您还可以试验其他算法，包括层次聚类。请务必在修改后将更新结果发送给我。

尽情享受吧！

如何聚类一组字符串？

How to cluster a set of strings?

machine-learning

cluster-analysis

k-means

hierarchical-clustering