Clustering text in Python

Question

Ho bisogno di raggruppare alcuni documenti di testo e ho cercato varie opzioni. Sembra che LingPipe possa raggruppare il testo normale senza conversione precedente (per lo spazio vettoriale, ecc.), Ma è l'unico strumento che ho visto che afferma esplicitamente di lavorare sulle stringhe.

Esistono strumenti Python in grado di raggruppare direttamente il testo? In caso contrario, qual è il modo migliore per gestirlo?

Answer 1

La qualità del testo di clustering dipende principalmente da due fattori:

1. qualche nozione di somiglianza tra i documenti che si desidera inserire nel cluster. Ad esempio, è facile distinguere tra articoli di cronaca sullo sport e la politica nello spazio vettoriale via tfidf-cosine-distance. È molto più difficile raggruppare recensioni di prodotti in "buono" o "cattivo" in base a questa misura.

2. Il metodo di raggruppamento stesso. Sai quanti cluster ci saranno? Ok, usa i kmea. Non ti interessa la precisione ma vuoi mostrare una bella struttura ad albero per la navigazione dei risultati di ricerca? Utilizzare una sorta di clustering gerarchico.

Non esiste una soluzione di cluster di testo, che funzioni bene in qualsiasi circostanza. E quindi probabilmente non è abbastanza per prendere alcuni software di clustering fuori dalla scatola e lanciare i tuoi dati su di esso.

Detto questo, ecco un codice sperimentale che ho utilizzato qualche tempo fa per giocare con il clustering del testo. I documenti sono rappresentati come vettori tfidf normalizzati e la somiglianza è misurata come distanza coseno. Il metodo di cluster stesso è majorclust.

import sys 
from math import log, sqrt 
from itertools import combinations 

def cosine_distance(a, b): 
    cos = 0.0 
    a_tfidf = a["tfidf"] 
    for token, tfidf in b["tfidf"].iteritems(): 
     if token in a_tfidf: 
      cos += tfidf * a_tfidf[token] 
    return cos 

def normalize(features): 
    norm = 1.0/sqrt(sum(i**2 for i in features.itervalues())) 
    for k, v in features.iteritems(): 
     features[k] = v * norm 
    return features 

def add_tfidf_to(documents): 
    tokens = {} 
    for id, doc in enumerate(documents): 
     tf = {} 
     doc["tfidf"] = {} 
     doc_tokens = doc.get("tokens", []) 
     for token in doc_tokens: 
      tf[token] = tf.get(token, 0) + 1 
     num_tokens = len(doc_tokens) 
     if num_tokens > 0: 
      for token, freq in tf.iteritems(): 
       tokens.setdefault(token, []).append((id, float(freq)/num_tokens)) 

    doc_count = float(len(documents)) 
    for token, docs in tokens.iteritems(): 
     idf = log(doc_count/len(docs)) 
     for id, tf in docs: 
      tfidf = tf * idf 
      if tfidf > 0: 
       documents[id]["tfidf"][token] = tfidf 

    for doc in documents: 
     doc["tfidf"] = normalize(doc["tfidf"]) 

def choose_cluster(node, cluster_lookup, edges): 
    new = cluster_lookup[node] 
    if node in edges: 
     seen, num_seen = {}, {} 
     for target, weight in edges.get(node, []): 
      seen[cluster_lookup[target]] = seen.get(
       cluster_lookup[target], 0.0) + weight 
     for k, v in seen.iteritems(): 
      num_seen.setdefault(v, []).append(k) 
     new = num_seen[max(num_seen)][0] 
    return new 

def majorclust(graph): 
    cluster_lookup = dict((node, i) for i, node in enumerate(graph.nodes)) 

    count = 0 
    movements = set() 
    finished = False 
    while not finished: 
     finished = True 
     for node in graph.nodes: 
      new = choose_cluster(node, cluster_lookup, graph.edges) 
      move = (node, cluster_lookup[node], new) 
      if new != cluster_lookup[node] and move not in movements: 
       movements.add(move) 
       cluster_lookup[node] = new 
       finished = False 

    clusters = {} 
    for k, v in cluster_lookup.iteritems(): 
     clusters.setdefault(v, []).append(k) 

    return clusters.values() 

def get_distance_graph(documents): 
    class Graph(object): 
     def __init__(self): 
      self.edges = {} 

     def add_edge(self, n1, n2, w): 
      self.edges.setdefault(n1, []).append((n2, w)) 
      self.edges.setdefault(n2, []).append((n1, w)) 

    graph = Graph() 
    doc_ids = range(len(documents)) 
    graph.nodes = set(doc_ids) 
    for a, b in combinations(doc_ids, 2): 
     graph.add_edge(a, b, cosine_distance(documents[a], documents[b])) 
    return graph 

def get_documents(): 
    texts = [ 
     "foo blub baz", 
     "foo bar baz", 
     "asdf bsdf csdf", 
     "foo bab blub", 
     "csdf hddf kjtz", 
     "123 456 890", 
     "321 890 456 foo", 
     "123 890 uiop", 
    ] 
    return [{"text": text, "tokens": text.split()} 
      for i, text in enumerate(texts)] 

def main(args): 
    documents = get_documents() 
    add_tfidf_to(documents) 
    dist_graph = get_distance_graph(documents) 

    for cluster in majorclust(dist_graph): 
     print "=========" 
     for doc_id in cluster: 
      print documents[doc_id]["text"] 

if __name__ == '__main__': 
    main(sys.argv) 

Per le applicazioni reali, si potrebbe utilizzare un tokenizzatore decente, utilizzare numeri interi, invece di token-stringhe e non CALC un O (n^2) distanza-matrix ...

Answer 2

Sembra possibile utilizzare semplici strumenti della riga di comando UNIX per estrarre il contenuto del testo di tali documenti in file di testo, quindi utilizzare una soluzione Python pura per il clustering effettivo.

ho trovato un frammento di codice per i dati di clustering in generale:

http://www.daniweb.com/code/snippet216641.html

pacchetto A Python per questo:

http://python-cluster.sourceforge.net/

altro pacchetto python (utilizzato principalmente per bioinformatica):

http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/software.htm#pycluster

Answer 3

C'è Python biblioteca NLTK che supporta l'analisi linguistica compreso il testo di clustering