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

Question

我在一个python项目中研究RNA结构的进化（用字符串表示，例如：“（（（…））”，其中括号表示基对）。关键是我有一个理想的结构和一个向理想结构进化的种群。我已经实现了所有的东西，但是我想添加一个特性，在这里我可以得到“桶的数量”，即每一代人口中最具代表性的k个结构。

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

谢谢！

Answer 1

K-means并不真正关心所涉及的数据类型。你所需要做的就是用某种方法来测量一个项目到另一个项目的“距离”。它将根据距离来做它的事情，而不管它是如何从底层数据计算出来的。

也就是说，我还没有使用scipy.cluster.vq，所以我不确定如何告诉它项目之间的关系，或者如何计算从项目a到项目B的距离

Answer 2

K-均值只适用于欧几里德距离。编辑距离，如Levenshtein不甚至服从三角形不等式可能服从三角形不等式，但不是欧几里得的。对于您感兴趣的度量类型，最好使用不同的算法，例如分层聚类：http://en.wikipedia.org/wiki/Hierarchical_clustering

或者，只需将你的RNA列表转换成一个加权图，在边缘有Levenshtein权重，然后将其分解成最小生成树。在某种意义上，树中连接最紧密的节点将是“最具代表性的”。

Answer 3

如果使用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。

例如，使用^{}'s实现k-medoids，使用^{}'s实现Levenshtein距离

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']