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

我正在研究一个python项目，在那里我研究RNA结构的演变（例如：“（（（...）））”括号代表碱基对）。重点是我有一个理想的结构和一个朝着理想结构发展的人口。我已经实现了一切，但是我想添加一个功能，让我可以得到“桶数”，即每代人群中k个最具代表性的结构。我可以在字符串上使用K-means算法吗？

我正在考虑使用k-means算法，但我不确定如何在字符串中使用它。我发现scipy.cluster.vq，但我不知道如何在我的情况下使用它。

谢谢！

来源

2011-06-09 Doni

K-means并不真正关心涉及的数据的类型。所有你需要做一个K-means是衡量一个物品到另一个物品“距离”的方法。它会根据距离来做它的事情，而不管这些事情是如何从底层数据计算出来的。

这么说，我没有用过scipy.cluster.vq，所以我不知道你究竟是如何告诉它的项目，或之间的关系如何计算项B.

来源

2011-06-09 13:40:15

这个答案没有任何意义。两串RNA之间的“距离”是什么，它使A）服从三角形不等式，B）是欧氏几何？有许多聚类算法，并且在这种情况下，特别是如何使用k-means会有用。 – sclv 2011-06-09 16:51:55

我正在使用的距离是结构距离，例如序列：（1）“（（（...）））”和（2）“（（（（..））））“ 有一个距离1，因为插入的唯一区别是 – Doni 2011-06-09 20:35:08

杰里，请你解释一下这可能是如何工作的吗？正如@sclv在他的回答中提到的，K-means只适用于欧几里德距离。似乎不可能将其应用于字符串，因为在每一步中，都需要将质心转换为表示最近数据点平均值的绝对位置......对于任意距离度量，似乎[** K-medoids **] （https://en.wikipedia.org/wiki/K-medoids）会起作用，因为它使用数据点作为质心来代替 – Adam 2016-06-04 00:35:43

一个问题，你从项目A的距离如果使用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实施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']

来源

2011-06-09 13:47:46 unutbu

K-装置只能与欧几里得距离的结果。编辑距离如Levenshtein不要求 ~~甚至服从三角不等式~~ 可能服从三角不等式，但不是欧几里德。对于您感兴趣的各种指标，您最好使用不同的算法，例如分级群集：http://en.wikipedia.org/wiki/Hierarchical_clustering

或者，只需将您的RNA列表转换为加权图，Levenshtein权重为边缘，然后将其分解为最小生成树。从某种意义上说，这棵树中最相关的节点将是“最有代表性的”。

来源

2011-06-09 13:58:14 sclv

[Levenshtein距离和三角不平等]（http://richardminerich.com/2012/09/levenshtein-distance-and-the-triangle-inequality/） – 2016-03-30 13:56:32

谢谢，修复！令人尴尬的是，博客的作者是我的一位朋友:-) – sclv 2016-03-30 15:43:56

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

回答

相关问题