Могу ли я использовать алгоритм K-средних для строки? - PullRequest
Новая
       20

Могу ли я использовать алгоритм K-средних для строки?

15 голосов
/ 09 июня 2011

Я работаю над проектом на python, в котором я изучаю эволюцию структуры РНК (представленную в виде строки, например: "(((...)))", где круглые скобки представляют базовые пары). Дело в том, что у меня идеальная структура и население, которое развивается в сторону идеальной структуры. Я реализовал все, однако я хотел бы добавить функцию, в которой я могу получить «количество сегментов», то есть k наиболее представительных структур в популяции в каждом поколении.

Я думал об использовании алгоритма k-средних, но я не уверен, как использовать его со строками. Я нашел scipy.cluster.vq , но я не знаю, как использовать его в моем случае.

спасибо!

Ответы [ 3 ]

11 голосов
/ 09 июня 2011

Одна из проблем, с которой вы столкнетесь при использовании scipy.cluster.vq.kmeans, заключается в том, что эта функция использует евклидово расстояние для измерения близости.Чтобы объединить вашу проблему в единую разрешимую с помощью k-means кластеризацию, вам нужно найти способ преобразовать ваши строки в числовые векторы и уметь оправдать использование евклидова расстояния в качестве разумной меры близости.

Это кажется ... сложным.Возможно, вы ищете расстояние Левенштейна вместо?

Обратите внимание, что есть варианты алгоритма K-средних , которые могут работать с неевклидовыми метриками расстояния (такими как Левенштейнрасстояние).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']
8 голосов
/ 09 июня 2011

K-означает, работает только с евклидовым расстоянием.Редактирование расстояний, таких как Левенштейн, даже не подчиняется неравенству треугольника может подчиняться неравенству треугольника, но не является евклидовым.Для тех видов метрик, которые вас интересуют, лучше использовать другой тип алгоритма, например, иерархическую кластеризацию: http://en.wikipedia.org/wiki/Hierarchical_clustering

В качестве альтернативы просто преобразуйте список РНК в взвешенный граф,с весами Левенштейна по краям, а затем разложить его в минимальное остовное дерево.Наиболее связанные узлы этого дерева будут, в некотором смысле, «наиболее представительными».

2 голосов
/ 09 июня 2011

K-means на самом деле не заботится о типе используемых данных. Все, что вам нужно для выполнения K-средних, это какой-то способ измерить «расстояние» от одного предмета до другого. Он будет делать свое дело на основе расстояний, независимо от того, как это произойдет, исходя из базовых данных.

Тем не менее, я не использовал scipy.cluster.vq, поэтому я не уверен, как именно вы скажете ему связь между элементами или как вычислить расстояние от элемента A до элемента B.

...