machine-learning - 如何对一组字符串进行聚类？

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 和信息检索，并且广泛应用于拥有字符/信息序列(例如遗传信息)的情况。因为必须保留序列，所以我们可以使用 n 元语法的概念。我在下面的示例中使用二元语法，但您可以概括为更高阶的语法。 N 元语法有助于保留数据中的顺序模式。别担心 - 我们不断借鉴其他科学领域的想法 - 甚至编辑距离和动态编程最初也不是计算机科学概念。

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

因此，我们的目标是从数据字符串中创建一个类似向量的词袋 - 并且这些向量可以轻松地输入到任何机器学习工具或库中进行聚类。步骤快速摘要:-

1. 收集二元组(和一元组等)
2. 创建字典以获取Bag Of Words(附代码)
3. 创建从字符串获取向量的功能

让我们开始吧

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-grams 甚至所有可能的 uni-gram、bi-gram 和 tri-grams 的完整集合。请随意尝试。

现在如何将字符串转换为向量？我们将定义一个函数，将字符串转换为向量，并处理特定 n 元语法出现的次数。这称为“词袋”。在这里，这些是一袋袋屏幕。以下两个函数可以帮助您实现这一点:

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)

然后我终于使用 KMeans 类的 km.labels_ 属性看到了我的集群的样子。

这是您的集群。查看控制台(底部)窗口 - 有十个集群。

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

享受吧!