16

私は、RNA構造の進化を研究するPythonプロジェクトに取り組んでいます（たとえば、「（（（...）））」の文字列で表され、括弧は塩基対を表します）。重要なのは、私には理想的な構造と、理想的な構造に向かって進化する人口があるということです。私はすべてを実装しましたが、「バケットの数」、つまり各世代の母集団で最も代表的なk個の構造を取得できる機能を追加したいと思います。

k-meansアルゴリズムを使用することを考えていましたが、文字列での使用方法がわかりません。scipy.cluster.vqを見つけましたが、私の場合の使用方法がわかりません。

ありがとう！

4

4 に答える 4

12

を使用する場合に直面する問題の1つscipy.cluster.vq.kmeansは、その関数がユークリッド距離を使用して近さを測定することです。クラスタリングによって問題を解決可能なものにまとめるにk-meansは、文字列を数値ベクトルに変換し、ユークリッド距離を妥当な近さの尺度として使用して正当化できる方法を見つける必要があります。

それは...難しいようです。おそらく、代わりにレーベンシュタイン距離を探していますか？

非ユークリッド距離メトリック（レーベンシュタイン距離など）で機能するK-meansアルゴリズムのバリエーションがあることに注意してください。K-medoids（別名PAM）は、たとえば、任意の距離メトリックを持つデータに適用できます。

たとえば、のPycluster実装とレーベンシュタイン距離の実装を使用すると、k-medoidsnltk

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-09T13:47:46.207 に答える
10

K-means はユークリッド距離でのみ機能します。レーベンシュタインなどの編集距離は、三角形の不等式には従わない 三角形の不等式には従うかもしれませんが、ユークリッドではありません。関心のある種類のメトリックについては、階層型クラスタリングなどの別の種類のアルゴリズムを使用することをお勧めします: http://en.wikipedia.org/wiki/Hierarchical_clustering

あるいは、RNA のリストを重み付きグラフに変換し、端にレーベンシュタインの重みを付けてから、それを最小全域木に分解します。そのツリーの最も接続されたノードは、ある意味で「最も代表的な」ものになります。

于 2011-06-09T13:58:14.500 に答える
2

K-meansは、関連するデータのタイプを実際には気にしません。K-meansを実行するために必要なのは、あるアイテムから別のアイテムまでの「距離」を測定する方法だけです。基になるデータからどのように計算されるかに関係なく、距離に基づいて処理を実行します。

とはいえ、私は使ったことがscipy.cluster.vqないので、アイテム間の関係をどのように伝えるのか、アイテムAからアイテムBまでの距離を計算する方法が正確にはわかりません。

于 2011-06-09T13:40:15.757 に答える