2009-05-12 9 views
19

Stellen Sie sich folgendes Problem:Best Clustering-Algorithmus? (Einfach erklärt)

  • Sie haben eine Datenbank über 20.000 Texte in einer Tabelle mit dem Namen „Artikel“
  • Sie mögen die diejenigen für eine Verbindung mit einem Cluster-Algorithmus, um anzuzeigen, Verwandte Artikel zusammen
  • der Algorithmus flachen clustering (nicht hierarchisch)
  • die zugehörigen Artikel eingefügt werden sollen, in die Tabelle „verwandten“
  • der Cluster-Algorithmus, ob zwei oder mor entscheiden sollte tun soll e Artikel beziehen oder nicht, basierend auf den Texten
  • ich in PHP codieren wollen, aber Beispiele mit Pseudo-Code oder anderen Programmiersprachen sind ok, auch

ich einen ersten Entwurf mit einer Funktionskontrolle codiert haben (), die "wahr" ergibt, wenn die zwei eingegebenen Artikel verwandt sind, und "falsch", wenn nicht. Der Rest des Codes (Auswahl der Artikel aus der Datenbank, Auswahl der zu vergleichenden Artikel, Einfügen der zugehörigen Artikel) ist ebenfalls abgeschlossen. Vielleicht kannst du auch den Rest verbessern. Aber der wichtigste Punkt, der mir wichtig ist, ist die Funktion check(). Es wäre also großartig, wenn Sie einige Verbesserungen oder ganz andere Ansätze veröffentlichen könnten.

ANSATZ 1

<?php 
$zeit = time(); 
function check($str1, $str2){ 
    $minprozent = 60; 
    similar_text($str1, $str2, $prozent); 
    $prozent = sprintf("%01.2f", $prozent); 
    if ($prozent > $minprozent) { 
     return TRUE; 
    } 
    else { 
     return FALSE; 
    } 
} 
$sql1 = "SELECT id, text FROM articles ORDER BY RAND() LIMIT 0, 20"; 
$sql2 = mysql_query($sql1); 
while ($sql3 = mysql_fetch_assoc($sql2)) { 
    $rel1 = "SELECT id, text, MATCH (text) AGAINST ('".$sql3['text']."') AS score FROM articles WHERE MATCH (text) AGAINST ('".$sql3['text']."') AND id NOT LIKE ".$sql3['id']." LIMIT 0, 20"; 
    $rel2 = mysql_query($rel1); 
    $rel2a = mysql_num_rows($rel2); 
    if ($rel2a > 0) { 
     while ($rel3 = mysql_fetch_assoc($rel2)) { 
      if (check($sql3['text'], $rel3['text']) == TRUE) { 
       $id_a = $sql3['id']; 
       $id_b = $rel3['id']; 
       $rein1 = "INSERT INTO related (article1, article2) VALUES ('".$id_a."', '".$id_b."')"; 
       $rein2 = mysql_query($rein1); 
       $rein3 = "INSERT INTO related (article1, article2) VALUES ('".$id_b."', '".$id_a."')"; 
       $rein4 = mysql_query($rein3); 
      } 
     } 
    } 
} 
?> 

ANSATZ 2 [nur überprüfen()]

<?php 
function square($number) { 
    $square = pow($number, 2); 
    return $square; 
} 
function check($text1, $text2) { 
    $words_sub = text_splitter($text2); // splits the text into single words 
    $words = text_splitter($text1); // splits the text into single words 
    // document 1 start 
    $document1 = array(); 
    foreach ($words as $word) { 
     if (in_array($word, $words)) { 
      if (isset($document1[$word])) { $document1[$word]++; } else { $document1[$word] = 1; } 
     } 
    } 
    $rating1 = 0; 
    foreach ($document1 as $temp) { 
     $rating1 = $rating1+square($temp); 
    } 
    $rating1 = sqrt($rating1); 
    // document 1 end 
    // document 2 start 
    $document2 = array(); 
    foreach ($words_sub as $word_sub) { 
     if (in_array($word_sub, $words)) { 
      if (isset($document2[$word_sub])) { $document2[$word_sub]++; } else { $document2[$word_sub] = 1; } 
     } 
    } 
    $rating2 = 0; 
    foreach ($document2 as $temp) { 
     $rating2 = $rating2+square($temp); 
    } 
    $rating2 = sqrt($rating2); 
    // document 2 end 
    $skalarprodukt = 0; 
    for ($m=0; $m<count($words)-1; $m++) { 
     $skalarprodukt = $skalarprodukt+(array_shift($document1)*array_shift($document2)); 
    } 
    if (($rating1*$rating2) == 0) { continue; } 
    $kosinusmass = $skalarprodukt/($rating1*$rating2); 
    if ($kosinusmass < 0.7) { 
     return FALSE; 
    } 
    else { 
     return TRUE; 
    } 
} 
?> 

Ich möchte auch sagen, dass ich weiß, dass es viele Algorithmen für das Clustering sind aber an jeder Stelle gibt es nur die mathematische Beschreibung, die für mich etwas schwierig zu verstehen ist. Codierungsbeispiele in (Pseudo-) Code wären also großartig.

Ich hoffe, Sie können mir helfen. Danke im Voraus!

+1

Es gibt WordPress Plugins (ja, yuck, ich weiß, verschone mich das), die eine überraschend gute Arbeit bei diesem tun, sie führen tatsächlich vernünftige Clustering (in der Regel tun sie TF-IDF mit der Rückseite der Wörter mit k-Mittel oder etwas So können Sie sie für Inspirationen verwenden (einige davon sind Open Source unter MIT). –

+2

Ich denke, Anony-Mousse hat Recht: Clustering ist hier nicht das ideale Werkzeug. Wenn jedes Dokument nur zu einem Cluster gehört, liegt das Problem darin, dass Dokumente nahe den Grenzen eines Clusters Dokumenten in anderen benachbarten Clustern ähnlicher sind als die meisten Dokumente in ihrem eigenen Cluster. –

Antwort

15

Die Standardmethode, die ich kenne, um Textdaten wie Sie zu verwenden, besteht darin, die "Tasche der Wörter" -Technik zu verwenden.

Erstellen Sie zuerst ein 'Histogramm' der Wörter für jeden Artikel. Sagen wir, zwischen all Ihren Artikeln haben Sie nur 500 eindeutige Wörter zwischen ihnen. Dann wird dieses Histogramm ein Vektor (Array, Liste, was auch immer) der Größe 500 sein, wobei die Daten die Anzahl der Male sind, die jedes Wort in dem Artikel erscheint. Wenn also die erste Stelle in dem Vektor das Wort repräsentiert ‚fragte‘, und das Wort erschien 5-mal in dem Artikel, Vektor [0] würde 5 sein:

for word in article.text 
    article.histogram[indexLookup[word]]++ 

nun alle zwei Artikel zu vergleichen, ist es ziemlich einfach. Wir haben einfach die beiden Vektoren multiplizieren:

def check(articleA, articleB) 
    rtn = 0 
    for a,b in zip(articleA.histogram, articleB.histogram) 
     rtn += a*b 
    return rtn > threshold 

(Sorry für mit Python statt PHP, meine PHP ist rostig und die Verwendung von Zip macht, dass etwas einfacher)

Dies ist die Grundidee. Beachten Sie, dass der Schwellenwert halb willkürlich ist. Sie werden wahrscheinlich einen guten Weg finden wollen, um das Skalarprodukt Ihrer Histogramme zu normalisieren (das wird fast die Artikellänge irgendwo berücksichtigen müssen) und entscheiden, was Sie als "verwandt" betrachten.

Sie sollten auch nicht jedes Wort in Ihr Histogramm einfügen. Im Allgemeinen möchten Sie diejenigen, die halbhäufig verwendet werden, einbeziehen: Nicht in jedem Artikel oder nur in einem Artikel. Dies spart Ihnen ein wenig Aufwand für Ihr Histogramm und erhöht den Wert Ihrer Beziehungen.

By the way, ist diese Technik näher beschrieben here

+0

Vielen Dank! Ich habe versucht, Ihren Ansatz in PHP zu kodieren und hier ist das Ergebnis: http://paste.bradleygill.com/index.php?paste_id=9290 Ich hoffe, dass Ihr PHP immer noch gut genug ist, um zu sagen, ob es korrekt ist oder nicht. – caw

+1

Es scheint mir jedoch richtig zu sein, dass Sie je nach Ihrer Anwendung ernsthaft erwägen wollen, den Status des Begriffs Vektoren beizubehalten. Ziehen Sie auch in Betracht, die Punktzahl durch die Länge des Artikels zu dividieren, die der Länge des Artikels b entspricht. Andernfalls werden Sie eine Verzerrung für lange Artikel feststellen, die nur marginal verwandt sind. – Albinofrenchy

+0

Sorry, sicherlich eine blöde Frage, aber was genau meinst du mit "erwäge den Zustand des Begriffs Vektoren zu erhalten". Zum zweiten Punkt: Meinst du "$ score = $ score/$ length_a * $ length_b" oder "$ score = $ score/($ length_a * $ length_b)"? Wahrscheinlich der erste, oder? – caw

0

Was bedeutet die similar_text Funktion in Ansatz # 1 aussieht wie genannt? Ich denke, dass Sie nicht Clustering, sondern eine Ähnlichkeitsmetrik meinen. Ich kann den White-Walloun-Histogrammansatz nicht wirklich verbessern - ein interessantes Problem, um etwas zu lesen.

Allerdings implementieren Sie check(), Sie müssen es verwenden, um mindestens 200M Vergleiche zu machen (die Hälfte von 20000^2). Die Cutoff für „related“ Artikel können begrenzen, was Sie in der Datenbank speichern, scheint aber zu willkürlich alle nützlichen Clustering von Texten zu fangen,

Mein Ansatz check() zurückzukehren, um die „Ähnlichkeit“ Metrik ($prozent oder rtn zu ändern wäre). Schreiben Sie die 20K x 20K Matrix in eine Datei und verwenden Sie ein externes Programm, um ein Clustering durchzuführen, um die nächsten Nachbarn für jeden Artikel zu identifizieren, die Sie in die Tabelle related laden können. Ich würde das Clustering in R tun - es gibt eine nette tutorial zum Clustering von Daten in einer Datei unter R von php.

+0

Die Funktion ashite_text() "berechnet die Ähnlichkeit zwischen zwei Strings wie in Oliver [1993]" beschrieben. Ja, Sie haben Recht, es ist eher eine Ähnlichkeitsmaße. Aber Sie brauchen Ähnlichkeitsprüfungen für das Clustering, nicht wahr? – caw

1

Ich glaube, Sie brauchen einige Design-Entscheidungen über Clustering zu machen, und von dort weiter:

  1. Warum Sie Texte Clustering sind? Möchten Sie zusammengehörige Dokumente zusammen anzeigen? Möchten Sie Ihren Dokumentenkorpus über Cluster erkunden?
  2. Als Ergebnis möchten Sie flat oder hierarchical Clustering?
  3. Jetzt haben wir das Problem der Komplexität, in zwei Dimensionen: erstens, die Anzahl und Art der Features, die Sie aus dem Text erstellen - einzelne Wörter können in die Zehntausende zählen. Sie können versuchen, einige feature selection - wie die N am meisten informativen Wörter oder die N Wörter am häufigsten erscheinen, nach dem Ignorieren stop words.
  4. Zweitens möchten Sie minimieren, wie oft Sie die Ähnlichkeit zwischen Dokumenten messen. Wie Bubaker richtig bemerkt, kann die Überprüfung der Ähnlichkeit zwischen allen Dokumentenpaaren zu viel sein. Wenn das Clustering in eine kleine Anzahl von Clustern ausreicht, können Sie K-means clustering in Betracht ziehen, was im Grunde Folgendes bedeutet: Wählen Sie initiale K-Dokumente als Cluster-Zentren, weisen Sie jedes Dokument dem nächsten Cluster zu, berechnen Sie Cluster-Zentren neu, indem Sie Vektormittel suchen und iterieren. Dies kostet nur K * Anzahl der Dokumente pro Iteration. Ich glaube, dass es auch Heuristiken gibt, um die benötigte Anzahl von Berechnungen für das hierarchische Clustering zu reduzieren.
+0

Danke, gute Fragen! 1) Ich möchte verwandte Dokumente zusammen anzeigen. 2) Der Algorithmus sollte Flat Clustering durchführen. 3) Dies wäre nützlich, wenn die Texte lang wären, aber in meinem Fall enthalten die Artikel höchstens 510 Zeichen. Es ist also nicht wirklich notwendig, oder? 4) Der Ansatz mit k-means klingt gut, aber ich brauche viele Cluster und neue Cluster müssen kontinuierlich erstellt werden. Kann ich aber k-means verwenden? – caw

+0

Sie können K-Mittel verwenden, wobei K sehr groß ist. Die Kosten müssen die Ähnlichkeit jedes Dokuments mit jedem der Zentren der Cluster überprüfen. "Continuously create new clusters" klingt für mich wie ein hierarchisches Top-down-Clustering, aber Sie können in mehreren Epochen arbeiten - beginnen Sie mit einem kleinen K, führen Sie K-means, bis es konvergiert, und verwenden Sie diese Cluster. Erhöhen Sie später K, führen Sie K-means von Anfang an erneut aus und verwenden Sie die resultierenden Cluster usw. –

+0

Oh, ich wusste nicht, wie k-means genau funktioniert.Wenn es so funktioniert, kann ich es nicht verwenden, da ich die Anzahl der Cluster-Zentren nicht kenne. Ich habe eine Datenbank mit Nachrichtenartikeln und alle Artikel zum selben Thema sollten gruppiert werden. – caw

5

Vielleicht Clustering ist die falsche Strategie hier?

Wenn Sie ähnliche Artikel anzuzeigen, Verwendung Ähnlichkeitssuche statt.

Für Textartikel wird dies gut verstanden. Fügen Sie einfach Ihre Artikel in eine Textsuchdatenbank wie Lucene ein und verwenden Sie Ihren aktuellen Artikel als Suchanfrage.In Lucene gibt es eine query called MoreLikeThis, die genau das ausführt: ähnliche Artikel finden.

Clustering ist das falsche Werkzeug, weil (insbesondere mit Ihren Anforderungen), jeder Artikel in einige Cluster gesetzt werden muss; und die zugehörigen Elemente wären für jedes Objekt im Cluster gleich. Wenn es Ausreißer in der Datenbank gibt - ein sehr wahrscheinlicher Fall - könnten sie Ihre Clusterbildung ruinieren. Außerdem können Cluster sehr groß sein. Da es keine Größenbeschränkung gibt, kann der Cluster-Algorithmus entscheiden, die Hälfte Ihres Datensatzes in demselben Cluster zu speichern. So haben Sie 10000 verwandte Artikel für jeden Artikel in Ihrer Datenbank. Mit Ähnlichkeitssuche können Sie nur die Top-10 ähnliche Elemente für jedes Dokument erhalten!

Last but not least: Vergessen Sie PHP für Clustering. Es ist nicht dafür ausgelegt und nicht performant genug. Aber Sie können wahrscheinlich auf einen Lucene-Index von PHP gut genug zugreifen.