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

Question

我正在研究一个python项目,在那里我研究RNA结构演化(例如表示为字符串:"(((...)))"其中括号代表碱基对.关键是我有一个理想的结构和一个向理想结构发展的人口.我实现了一切,但是我想添加一个功能,我可以获得"桶数",即每代人口中最具代表性的k结构.

我在考虑使用k-means算法,但我不确定如何将它与字符串一起使用.我找到了scipy.cluster.vq,但我不知道如何在我的情况下使用它.

谢谢!

Answer 1

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

这似乎......很难.也许你正在寻找Levenshtein距离？

注意,存在可以与非欧几里德距离度量(例如Levenshtein距离)一起使用的K均值算法的变体.K-medoids例如,(又称PAM)可以应用于具有任意距离度量的数据.

例如,使用Pycluster的执行k-medoids,和nltk的实施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']

Answer 2

K-means仅适用于欧氏距离.编辑距离如Levenshtein甚至不服从三角不等式可能服从三角不等式,但不是欧几里得.对于您感兴趣的各种指标,最好使用不同类型的算法,例如分层聚类:http://en.wikipedia.org/wiki/Hierarchical_clustering

或者,只需将您的RNA列表转换为加权图形,边缘使用Levenshtein权重,然后将其分解为最小生成树.在某种意义上,该树的连接最多的节点将是"最具代表性的".

Answer 3

K-means 并不真正关心所涉及数据的类型。执行 K 均值所需的只是某种方法来测量从一个项目到另一个项目的“距离”。它会根据距离来完成任务，而不管它是如何从基础数据计算出来的。

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