Python-Cluster-Analyse

    Das wunderbare Buch „Programming a collective mind“ hat mich dazu inspiriert, diesen Beitrag zu schreiben, der auf seinen Motiven zum Thema Clusteranalyse basiert.

    In einem Beitrag bestand der Wunsch, die Clusteranalyse, ihre schöne Implementierung in Python und insbesondere die visuelle Darstellung von Clustern - Dendrogrammen - in Betracht zu ziehen .

    Der Beispielcode basiert auf dem Beispielcode aus dem Buch.


    Die Hauptidee der Cluster-Analyse besteht darin, zwischen den Datengruppen zu isolieren, in denen sich die Elemente etwas ähneln. Tatsächlich erfolgt im Rahmen einer solchen Analyse eine gewisse Klassifizierung der untersuchten Daten aufgrund ihrer Verteilung in Gruppen. Diese Gruppen sind hierarchisch geordnet und die Struktur der resultierenden Cluster nach der Analyse kann in Form eines Baums dargestellt werden - eines Dendrogramms („Dendro“, wie Sie wissen, auf Griechisch „Baum“).

    Das Ähnlichkeitsmaß für jede Aufgabe kann unterschiedlich festgelegt werden, am einfachsten sind jedoch der euklidische Abstand und der Pearson-Korrelationskoeffizient . Im Beispiel wird der Pearson-Korrelationskoeffizient untersucht, der jedoch leicht ersetzt werden kann.

    Im Allgemeinen ist die historische Clusteranalyse in den Geisteswissenschaften am populärsten geworden, und eine der ersten Aufgaben, für die sie angewendet wurde, war die Analyse von Daten über alte Bestattungen.

    Der Algorithmus zum Aufbau von Clustern ist im Prinzip einfach und logisch.

    Die anfänglichen Daten für den Algorithmus sind eine Liste einiger Elemente und eine Funktion der Ähnlichkeit zwischen ihnen ("Nähe" von Elementen). Jedes Element hat "Koordinaten" in einem bestimmten Raum (zum Beispiel im Raum der Anzahl der Wörter), anhand derer die Ähnlichkeit zwischen den Elementen berechnet wird.

    Beispiel: Elemente - Blogs, 2 "Koordinaten" - Die Anzahl der Wörter "php" und "xml" im Inhalt von Blogs.
    Das Blog Nummer 1 - 7 mal fand das Wort "php" und 5 mal "xml". Dann sind die "Koordinaten" des Blogs Nummer 1 im Raum der Nummer dieser Wörter (7; 5).
    Das Blog Nummer 2 - 6 mal fand das Wort "php" und 4 mal "xml". Dann die "Koordinaten" des Blogs Nummer 2 im Raum der Nummer dieser Wörter - (6; 4).
    Die Ähnlichkeit wird mit der Funktion - Euklidischer Abstand bestimmt. Am Ausgang erhalten wir einen Clusterbaum (Clusterhierarchie). Der Algorithmus funktioniert wie folgt: 1) Schritt 1: Betrachte jedes Element der Ursprungsliste als Cluster und füge sie der Zusammenführungsliste hinzu. 2) Schritt 2 - N: Finde die nächsten Cluster und füge sie zu einer neuen zusammen ("Koordinaten" der neuen - die Hälfte der Summe der "Koordinaten" der zusammengeführten). Neu In der in die Liste der Verbände und die Anfangscluster - von entfernen der Liste . Somit gibt es bei jedem Schritt in der Zusammenführungsliste weniger Elemente.
    d(blog1, blog2) = sqrt( (7-6)^2 + (5-4)^2) = 1.414








    Stop-Kriterium : Das Vorhandensein eines einzigen Clusters in der Liste der Vereinheitlichungen , mit dem nichts zu kombinieren ist (Erhalten eines

    solchen Clusters, des "Root" -Clusters).
    1. def hcluster(rows,distance=pearson):
    2.  distances={}
    3.  currentclustid=-1
    4.  
    5.  # Clusters are initially just the rows
    6.  clust=[bicluster(rows[i],id=i) for i in range(len(rows))]
    7.  
    8.  while len(clust)>1:
    9.   lowestpair=(0,1)
    10.   closest=distance(clust[0].vec,clust[1].vec)
    11.  
    12.   # loop through every pair looking for the smallest distance
    13.   for i in range(len(clust)):
    14.    for j in range(i+1,len(clust)):
    15.     # distances is the cache of distance calculations
    16.     if (clust[i].id,clust[j].id) not in distances:
    17.      distances[(clust[i].id,clust[j].id)]=distance(clust[i].vec,clust[j].vec)
    18.  
    19.     d=distances[(clust[i].id,clust[j].id)]
    20.  
    21.     if d
    22.      closest=d
    23.      lowestpair=(i,j)
    24.  
    25.   # calculate the average of the two clusters
    26.   mergevec=[
    27.   (clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0
    28.   for i in range(len(clust[0].vec))]
    29.  
    30.   # create the new cluster
    31.   newcluster=bicluster(mergevec,left=clust[lowestpair[0]],
    32.              right=clust[lowestpair[1]],
    33.              distance=closest,id=currentclustid)
    34.  
    35.   # cluster ids that weren't in the original set are negative
    36.   currentclustid-=1
    37.   del clust[lowestpair[1]]
    38.   del clust[lowestpair[0]]
    39.   clust.append(newcluster)
    40.  
    41.  return clust[0]
    * This source code was highlighted with Source Code Highlighter.


    Im Beispiel wird ein Beispiel für eine Clusteranalyse des Inhalts von Programmierblogs betrachtet. Das Buch behandelt englischsprachige Blogs, aber ich habe beschlossen, 35 russischsprachige Begriffe im Hinblick auf das Auftreten von englischsprachigen Begriffen zu analysieren. Um die Ergebnisse der Analyse anzuzeigen, mussten die Namen der Blogs mithilfe einer kleinen Bibliothek übersetzt werden.

    Das vollständige Archiv mit allen notwendigen Dateien und Skripten in Python kann heruntergeladen werden - clusters.zip
    Zusammensetzung des Archivs: feedlist.txt mit einer Liste von RSS-Blogs, die Sie zum Beispiel solchen Inhalten entnehmen können (aus der Suche http://lenta.yandex.ru/feed_search). xml? text = programming ): Das Dendrogrammerstellungsprogramm selbst besteht aus 2 Skripten (Datenerfassung + Verarbeitung), die nacheinander gestartet werden:
    blogdata.txt – собранная информация по блогам для кластеризации
    clusters.py - скрипт построения кластеров
    draw_dendrograms.py - скрипт запуска построения кластеров и рисования дендрограмм (вызывает функции скрипта clusters.py)
    feedlist.txt - список RSS блогов для анализа
    generatefeedvector.py - скрипт сбора информации по блогам и формирования blogdata.txt

    translit.py, utils.py - скрипты для транслитерации названий блогов




    feeds.feedburner.com/nayjest
    www.codenet.ru/export/read.xml
    feeds2.feedburner.com/simplecoding
    feeds2.feedburner.com/nickspring
    feeds2.feedburner.com/Sribna
    community.livejournal.com/ru_cpp/data/rss
    community.livejournal.com/ru_lambda/data/rss
    feeds2.feedburner.com/rusarticles
    feeds2.feedburner.com/Jstoolbox
    feeds2.feedburner.com/rsdn/cpp
    4matic.wordpress.com/feed
    www.nowa.cc/external.php?type=RSS2
    www.gotdotnet.ru/blogs/gaidar/rss
    community.livejournal.com/ru_programmers/data/rss
    www.compdoc.ru/rssdok.php
    feeds2.feedburner.com/rsdn/philosophy
    softwaremaniacs.org/blog/feed
    community.livejournal.com/new_ru_php/data/rss
    www.newsrss.ru/mein_rss/rss_cdata.xml
    feeds2.feedburner.com/5an
    subscribe.ru/archive/comp.soft.prog.linuxp/index.rss
    feeds.feedburner.com/mrkto
    rbogatyrev.livejournal.com/data/rss
    feeds2.feedburner.com/poisonsblog
    community.livejournal.com/ruby_ru/data/rss
    feeds2.feedburner.com/devoid
    rgt.rpod.ru/rss.xml
    feeds2.feedburner.com/rsdn/decl
    feeds2.feedburner.com/Toeveryonethe
    www.osp.ru/rss/Software.rss
    feeds2.feedburner.com/Freshcoder
    blogs.technet.com/craftsmans_notes/rss.xml
    feeds2.feedburner.com/RuRubyRails
    feeds2.feedburner.com/bitby
    opita.net/rss.xml



    python generatefeedvector.py

    python draw_dengrograms.py


    Damit das Beispiel funktioniert, benötigen Sie die Python Imaging Library (PIL), die Sie von www.pythonware.com/products/pil herunterladen können.
    Nach dem Entpacken wird sie wie gewohnt installiert:
    python setup.py install

    Und hier ist der interessanteste Punkt. Als Ergebnis der Skripte wurden die folgenden Dendrogramme erhalten:
    1) für Blogs (in voller Qualität - img-fotki.yandex.ru/get/4100/serg-panarin.0/0_21f52_b8057f0d_-1-orig.jpg )

    Bild

    2) für Wörter (vollständig quality - img-fotki.yandex.ru/get/4102/serg-panarin.0/0_21f53_dcdea04f_-1-orig.jpg )

    Bild

    Durch Ändern von feedlist.txt können Sie beliebige Blogs analysieren und Ihre Dendrogramme abrufen.

    Jetzt auch beliebt: