可以对字符串使用K均值算法吗？

Question

我正在做一个Python项目，研究RNA结构的演变。RNA结构用字符串表示，比如“(((...)))”，其中括号代表碱基对。我的目标是有一个理想的结构，然后让一个种群逐渐演变到这个理想结构。我已经实现了所有的功能，但我想增加一个新特性，就是能够获取“桶的数量”，也就是在每一代中，种群里最具代表性的k个结构。

我在考虑使用k-means算法，但不太确定如何把它应用到字符串上。我找到了scipy.cluster.vq这个库，但不知道在我的情况下该怎么用。

谢谢！

Answer 1

K-means算法只适用于欧几里得距离，也就是我们常说的直线距离。像Levenshtein这样的编辑距离可能在某些情况下符合三角不等式，但它并不是欧几里得距离。对于你感兴趣的这些度量方式，使用其他类型的算法会更合适，比如层次聚类：http://en.wikipedia.org/wiki/Hierarchical_clustering

另外，你也可以把你的RNA列表转换成一个加权图，边的权重用Levenshtein距离表示，然后将其分解成一个最小生成树。这个树中连接最紧密的节点在某种意义上就是“最具代表性”的节点。

Answer 2

如果你使用 scipy.cluster.vq.kmeans 这个函数，你会遇到一个问题：这个函数是用欧几里得距离来衡量数据之间的相似度的。为了把你的问题转化为可以用 k-means 聚类解决的形式，你需要找到一种方法，把你的字符串转换成数字向量，并且还要能解释为什么用欧几里得距离来衡量相似度是合理的。

这听起来……有点难。也许你其实想用 莱文斯坦距离 呢？

值得注意的是，有一些 K-means 算法的变种 可以使用非欧几里得距离的度量（比如莱文斯坦距离）。例如，K-medoids（也叫 PAM） 可以应用于任意距离度量的数据。

举个例子，使用 Pycluster 的 k-medoids 实现，以及 nltk 的 莱文斯坦距离实现，

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

Answer 3

K-means算法其实不太在乎数据的类型。你只需要一种方法来衡量一个项目和另一个项目之间的“距离”。它会根据这些距离来进行操作，而不管这些距离是如何从底层数据计算出来的。

不过，我没有使用过scipy.cluster.vq，所以我不太清楚你是怎么告诉它项目之间的关系，或者如何计算从项目A到项目B的距离。