¿Puedo usar el algoritmo K-means en una cadena?

Question

Estoy trabajando en un proyecto de python donde estudio la evolución de la estructura del ARN (representada como una cadena por ejemplo: "(((...)))" donde los paréntesis representan pares de bases). El punto es que tengo una estructura ideal y una población que evoluciona hacia la estructura ideal. Lo he implementado todo; sin embargo, me gustaría agregar una función donde pueda obtener el "número de cubos", es decir, las k estructuras más representativas de la población en cada generación.

Estaba pensando en usar el algoritmo k-means, pero no estoy seguro de cómo usarlo con strings. Encontré scipy.cluster.vq pero no sé cómo usarlo en mi caso.

gracias!

Answer 1

A K-means realmente no le importa el tipo de datos involucrados. Todo lo que necesita para hacer un K-means es una forma de medir una "distancia" de un elemento a otro. Hará lo suyo en función de las distancias, independientemente de cómo se compute a partir de los datos subyacentes.

Dicho esto, no he utilizado scipy.cluster.vq, así que no estoy seguro de cómo lo cuentas la relación entre los artículos, o cómo calcular una distancia desde el punto A al punto B.

Answer 2

Uno de los problemas que se enfrentarían si se usa scipy.cluster.vq.kmeans es que esa función usa la distancia euclidiana para medir la cercanía. Para adaptar su problema a uno que pueda resolverse mediante el clúster k-means, debe encontrar la manera de convertir sus cadenas en vectores numéricos y poder justificar el uso de la distancia euclidiana como una medida razonable de cercanía.

Eso parece ... difícil. Quizás estás buscando Levenshtein distance en su lugar?

Tenga en cuenta que hay variants of the K-means algorithm que pueden funcionar con métricas de distancia que no sean Euclideance (como la distancia Levenshtein). K-medoids (también conocido como PAM), por ejemplo, can be applied to data with an arbitrary distance metric.

Por ejemplo, usando Pycluster's aplicación de k-medoids, y nltk's aplicación de Levenshtein distancia,

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) 

produce un resultado como

['apple', 'Doppler', 'applaud', 'append'] 
['stake', 'steak', 'teak', 'sleek'] 
['barker', 'baker', 'bismark', 'park'] 

Answer 3

K-means sólo funciona con la distancia euclidiana. Editar distancias como Levenshtein no incluso obedecer la desigualdad del triángulo puede obedecer la desigualdad del triángulo, pero no son euclidian. Para los tipos de métricas que le interesan, es mejor utilizar un tipo diferente de algoritmo, como el agrupamiento jerárquico: http://en.wikipedia.org/wiki/Hierarchical_clustering

Alternativamente, simplemente convierta su lista de ARN en un gráfico ponderado, con los pesos de Levenshtein en los bordes, y luego descomponerlo en un árbol de expansión mínimo. Los nodos más conectados de ese árbol serán, en cierto sentido, los "más representativos".