Puis-je utiliser l'algorithme de K-means sur une chaîne de caractères?
je travaille sur un projet python où j'étudie l'évolution de la structure de L'ARN (représentée par une chaîne de caractères par exemple: "(((...)))" où les parenthèses représentent les paires de bases). Le fait est que j'ai une structure idéale et une population qui évolue vers la structure idéale. J'ai tout mis en œuvre mais je voudrais ajouter une fonctionnalité Où je peux obtenir le "nombre de seaux", c'est-à-dire les k structures les plus représentatives de la population à chaque génération.
je suis je pense à utiliser l'algorithme de K-means, mais je ne sais pas comment l'utiliser avec des chaînes. J'ai trouvé scipy.cluster.vq mais je ne sais pas comment l'utiliser dans mon cas.
merci!
3 réponses
k-means ne se soucie pas vraiment du type de données impliquées. Tout ce que vous devez faire un k-means est un moyen de mesurer une "distance" d'un élément à un autre. Il va faire son truc basé sur les distances, indépendamment de la façon dont il se trouve être calculé à partir des données sous-jacentes.
cela dit, je n'ai pas utilisé scipy.cluster.vq, donc je ne suis pas sûr exactement comment vous lui Dites la relation entre les articles, ou comment calculer une distance de l'article A à l'article B.
un problème que vous rencontreriez si vous utilisiez scipy.cluster.vq.kmeans c'est que cette fonction utilise la distance Euclidienne pour mesurer la proximité. Pour transformer votre problème en un problème résolu par k-means clustering, vous devez trouver un moyen de convertir vos chaînes en numérique vecteurs et être en mesure de justifier à l'aide de la distance Euclidienne comme une mesure raisonnable de proximité.
cela semble... difficile. Peut-être que vous êtes à la recherche pour Levenshtein à la place?
Remarque: il n'y variantes de l'algorithme K-means qui peut fonctionner avec des mesures de distance non-Euclideance (comme la distance Levenshtein). K-medoids (alias PAM), par exemple, peut être appliqué à des données avec une métrique de distance arbitraire.
par exemple, en utilisant Pycluster mise en oeuvre de k-medoids et nltk mise en place de 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)
donne un résultat comme
['apple', 'Doppler', 'applaud', 'append']
['stake', 'steak', 'teak', 'sleek']
['barker', 'baker', 'bismark', 'park']
K - signifie seulement fonctionne avec la distance euclidienne. Éditer des distances comme Levenshtein ne pas même obéir à l'inégalité du triangle peut obéir à l'inégalité du triangle, mais ne sont pas euclidiens. Pour les types de mesures qui vous intéressent, il est préférable d'utiliser un autre type d'algorithme, comme le regroupement hiérarchique:http://en.wikipedia.org/wiki/Hierarchical_clustering
alternativement, il suffit de convertir votre liste D'ARN en un graphe pondéré, avec Levenshtein pèse sur les bords, puis le décompose en un arbre couvrant minimum. Les noeuds les plus connectés de cet arbre seront, en un sens, le "plus représentatif".