Das finden der Mitte eines Clusters

Ich habe Folgendes problem - aus abstrakten, um den Schlüssel Fragen.

Habe ich jeweils 10 Punkten, die in einiger Entfernung von den anderen. Ich möchte

in der Lage sein zu finden, das Zentrum des Clusters, d.h. der Punkt für die paarweisen Abstand zu jedem anderen Punkt wird minimiert,

lassen Sie p(j) ~ p(k) stellen die paarweisen Abstand beteen Punkte j und k

p(i) ist der Mittelpunkt der cluster-iff p(i) s verwendet.t. min[sum(p(j)~p(k))] für 0 < j,k <= n, wo wir n Punkte im cluster
bestimmen, wie die Aufteilung der cluster in zwei Cluster aufgeteilt, sobald die Anzahl der Datenpunkte im cluster geht über eine Schwelle t.

Diesem nicht-euklidischen Raum. Aber die Entfernungen lassen sich wie folgt zusammenfassen - p(i), Punkt i:

       p(1)    p(2)    p(3)    p(4)    p(5)    p(6)    p(7)    p(8)    p(9)    p(10)
p(1)    0       2       1       3       2       3       3       2       3        4
p(2)    2       0       1       3       2       3       3       2       3        4
p(3)    1       1       0       2       0       1       2       1       2        3
p(4)    3       3       2       0       1       2       3       2       3        4      
p(5)    2       2       1       1       0       1       2       1       2        3   
p(6)    3       3       2       2       1       0       3       2       3        4   
p(7)    3       3       2       3       2       3       0       1       2        3  
p(8)    2       2       1       2       1       2       1       0       1        2 
p(9)    3       3       2       3       2       3       2       1       0        1
p(10)   4       4       3       4       3       4       3       2       1        0

Wie würde ich berechnen, was ist der Mittelpunkt dieser cluster?

Bitte definieren Sie "center cluster"
Nifle - getan ... habt Ihr Ideen
Die Anwendung hat zu tun mit clustering-Konzepte - meine Anwendung ist ein semantisches Daten speichern - die Punkte stellen abstrakte Objekte. Ich will cluster von Objekten feststellen zu können "Konzepte"
Meinst du das: wählen Sie ich, minimiert [sum(p(i)~p(j)] für 0 < j <= n, so dass p(i) ist das Zentrum? Wenn dem so ist, denke ich, dass deine Antwort zu Teil 1; sonst bin ich nicht sicher, was du meinst.
in Worten, wir wollen eine Minimierung der paarweisen Distanzen für alle Paare von Punkten in einem cluster. Der Punkt gibt die minimale ist der Mittelpunkt.

InformationsquelleAutor Ankur | 2009-08-10

8

Soweit ich das verstanden habe sieht es wie K-Means-Clustering, und das, was Sie suchen, ist in der Regel bekannt als "Medoids'.

Siehe hier: http://en.wikipedia.org/wiki/Medoids oder hier: http://en.wikipedia.org/wiki/K-medoids
- Von Ihnen positiv bewertet werden: diese Tat sieht aus wie der Weg zu gehen für nicht-euklidischen Metriken. Aber es erfordert noch, dass zumindest die Dreiecks-Ungleichung gilt; ich gestehe, ich bin nicht geduldig genug, um stellen Sie sicher, dass für Ankur ' s-Beispiel.
- Jim, der dreiecksungleichung macht halt in meinem "metrischer Raum", so dann sollte das klappen.
InformationsquelleAutor Darknight

Ich kann mich über zu haben, der Schauder, der kommt nur vor der Anzeige völlige Dummheit. Aber nicht diese Rendite leicht zu brute-force? In Python:

distances = [
[ 0 , 2 , 1 , 3 , 2 , 3 , 3 , 2 , 3 , 4 , ],
[ 2 , 0 , 1 , 3 , 2 , 3 , 3 , 2 , 3 , 4 , ],
[ 1 , 1 , 0 , 2 , 0 , 1 , 2 , 1 , 2 , 3 , ],
[ 3 , 3 , 2 , 0 , 1 , 2 , 3 , 2 , 3 , 4 , ],
[ 2 , 2 , 1 , 1 , 0 , 1 , 2 , 1 , 2 , 3 , ],
[ 3 , 3 , 2 , 2 , 1 , 0 , 3 , 2 , 3 , 4 , ],
[ 3 , 3 , 2 , 3 , 2 , 3 , 0 , 1 , 2 , 3 , ],
[ 2 , 2 , 1 , 2 , 1 , 2 , 1 , 0 , 1 , 2 , ],
[ 3 , 3 , 2 , 3 , 2 , 3 , 2 , 1 , 0 , 1 , ],
[ 4 , 4 , 3 , 4 , 3 , 4 , 3 , 2 , 1 , 0 , ],
]

currentMinimum = 99999

for point in range ( 10 ) :
    distance_sum = 0
    for second_point in range ( 10 ) :
        if point == second_point : continue
        distance_sum += distances [ point ] [ second_point ]
    print '>>>>>', point, distance_sum 

    if distance_sum < currentMinimum :
        currentMinimum = distance_sum 
        centre = point

print centre

Hallo Bill, ich habe zu einem ähnlichen Schluss kommen. Sobald Sie den cluster, und Sie möchten, wählte das Zentrum eines Clusters, das ist so ziemlich der Weg, es zu tun. Was ich Tue, ist dieses: ich beginnen mit einem einzigen cluster, da fange ich mit der 1-Daten zeigen, wie mehr hinzu, und mein cluster wird, größer als eine Schwelle t, habe ich es geteilt. Ich wähle dann die zwei furtherest Punkte als Zentren der neuen Cluster. Jeder Punkt wird dann zugewiesen, an einem der beiden Punkte je nachdem, was näher ist. Dann das eigentliche Zentrum in jedem cluster berechnet.

InformationsquelleAutor Bill Bell

1

a)
- finden, der median oder der Durchschnitt der Werte aller Entfernungen. = avgAll
- Für jedes p, finden Durchschnittliche Entfernung zu anderen Maschinen. = avgP(i)
- Holen die näher als center. avgAll ~= avgP(i)
b)
keine Idee für heute..

vielleicht für jedes p, finden Sie die Maschine näher.

durch diese Logik erstellen Sie ein Diagramm.

als irgendwie (noch habe ich keine Ahnung) unterteilen das Diagramm

InformationsquelleAutor ufukgun
0

Was Sie zu tun versuchen, oder zumindest (b) gehört zur Cluster-Analyse. Ein Zweig der Mathematik /Statistik /ökonometrie, wo Datenpunkte (z.B. Punkte im n-dimensionalen Raum) sind geteilt in Gruppen oder Cluster. Wie Sie dies tun, ist keine triviale Frage, es gibt viele, viele Möglichkeiten.

Lesen Sie mehr auf der wikipedia-Artikel zu Clusteranalyse.

InformationsquelleAutor Martijn

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.