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

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

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

спасибо!

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 3

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

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