我可以在字符串上使用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算法嗎？

回答

相關問題