python - 我可以在字符串上使用 K-means 算法吗？

Question

我正在研究 RNA 结构进化的 python 项目(表示为字符串，例如:“(((...)))”，其中括号代表碱基对)。关键是我有一个理想的结构和一个朝着理想结构进化的人口。我已经实现了所有内容，但是我想添加一个功能，我可以获得“桶数”，即每一代人口中 k 个最具代表性的结构。

我正在考虑使用 k-means 算法，但我不确定如何将它用于字符串。我找到了 scipy.cluster.vq但我不知道如何在我的案例中使用它。

谢谢!

Answer 1

如果使用 scipy.cluster.vq.kmeans，您将面临的一个问题是该函数使用欧氏距离来衡量接近度。要将您的问题强行转化为可通过 k-means 聚类解决的问题，您必须找到一种方法将字符串转换为数值向量，并能够证明使用欧几里德距离作为合理度量亲密。

这似乎……很难。也许您正在寻找 Levenshtein distance相反？

注意有variants of the K-means algorithm可以使用非欧几里得距离度量(例如 Levenshtein 距离)。 K-medoids(又名 PAM)，例如，can be applied to data with an arbitrary distance metric .

例如，使用 Pycluster's k-medoids 和 nltk's 的实现编辑距离的实现，

import nltk.metrics.distance as distance
import Pycluster as PC

words = ['apple', 'Doppler', 'applaud', 'append', 'barker', 
         'baker', 'bismark', 'park', 'stake', 'steak', 'teak', 'sleek']

dist = [distance.edit_distance(words[i], words[j]) 
        for i in range(1, len(words))
        for j in range(0, i)]

labels, error, nfound = PC.kmedoids(dist, nclusters=3)
cluster = dict()
for word, label in zip(words, labels):
    cluster.setdefault(label, []).append(word)
for label, grp in cluster.items():
    print(grp)

产生这样的结果

['apple', 'Doppler', 'applaud', 'append']
['stake', 'steak', 'teak', 'sleek']
['barker', 'baker', 'bismark', 'park']