K-means ist ein standardmäßiger unbeaufsichtigter Clustering-Algorithmus, der bei einer Menge von "Punkten" und einer Anzahl von Clustern K jeden "Punkt" einem von K Clustern zuweist.

Pseudocode von K-Mitteln

Beachten Sie, dass es viele Varianten von K-Mitteln gibt. Sie müssen den unten beschriebenen Algorithmus implementieren. Möglicherweise haben Sie einige Variationen des Algorithmus oder verwenden integrierte Funktionen, solange Sie bei gleichen Anfangspunkten das gleiche Ergebnis wie bei diesem Algorithmus erzielen.

Bei dieser Herausforderung sind alle Eingaben Punkte in der 2D-Ebene (jeder Punkt wird durch seine Koordinaten in x und y dargestellt).

Inputs: K, the number of clusters
        P, the set of points

Choose K points of P uniformly at random
Each chosen point is the initial centroid of its cluster

Loop:
     For each point in P:
         Assign to the cluster whose centroid is the nearest (Euclidean distance)
         In case of a tie, any of the tied cluster can be chosen

     Recompute the centroid of each cluster:
         Its x coordinate is the average of all x's of the points in the cluster
         Its y coordinate is the average of all y's of the points in the cluster

Until the clusters don't change from one iteration to the next

Output: the set of clusters    

Eingänge und Ausgänge

• Sie können K und P durch STDINoder als Funktionsargument usw. führen.
• P und die Punkte in P können mit einer beliebigen Struktur dargestellt werden, die für Mengen / Listen in der Sprache Ihrer Wahl natürlich ist.
• K ist eine streng positive ganze Zahl.
• Sie können davon ausgehen, dass Eingaben gültig sind.
• Es wird immer mindestens K Punkte in P geben.
• Sie können die Cluster an ausgeben STDOUT, sie von einer Funktion zurückgeben usw.
• Die Reihenfolge der Cluster und die Reihenfolge innerhalb der Cluster ist unwichtig. - Sie können entweder Punktgruppen zurückgeben, um Cluster darzustellen, oder jeden Punkt mit einer Kennung für den Cluster (z. B. einer Ganzzahl) kennzeichnen.

Testfälle

Da die resultierenden Cluster davon abhängen, welche Punkte ursprünglich ausgewählt wurden, erhalten Sie möglicherweise nicht alle dieselben Ergebnisse (oder jedes Mal dasselbe Ergebnis, wenn Sie Ihren Code ausführen).

Nehmen Sie daher nur die Ausgabe als Beispielausgabe.

Input:
  K = 1
  P = [[1,2.5]]
Output:
  [[[1,2.5]]]

Input:
  K = 3
  P = [[4,8], [15,16], [23,42], [-13.37,-12.1], [666,-666]]
Output:
  [[[666,-666]],[[-13.37,-12.1],[4,8]],[[15,16],[23,42]]]

Input:
  K = 2
  P = [[1,1], [1,1], [1,1]]
Output:
  [[[1,1]],[[1,1],[1,1]]]

Wertung

Dies ist Code-Golf , daher gewinnt die kürzeste Antwort in Bytes.

Matlab, 25 Bytes

@(x,k)kmeans(x,k,'S','u')

Bei einer gegebenen n x 2Matrix (z. B. eine Zeile pro Punkt [[4,8]; [15,16]; [23,42]; [-13.37,-12.1]; [666,-666]]) gibt diese Funktion eine Liste von Beschriftungen für jeden Eingabepunkt zurück.

C ++, 479 474 Bytes

Nur ~ 20x so viel wie Matlab!

Golf gespielt

#define V vector<P>
#define f float
struct P{f x,y,i=0;f d(P&p){return(p.x-x)*(p.x-x)+(p.y-y)*(p.y-y);}f n(P&p){return i?x/=i,y/=i,d(p):x=p.x,y=p.y,0;}f a(P&p){x+=p.x,y+=p.y,i++;}};P z;int l(P a,P b){return a.d(z)<b.d(z);}f m(f k,V&p){f s=p.size(),i,j=0,t=1;V c(k),n=c,d;for(random_shuffle(p.begin(),p.end());j<k;c[j].i=j++)c[j]=p[j];for(;t;c=n,n=V(k)){for(i=0;i<s;i++)d=c,z=p[i],sort(d.begin(),d.end(),l),j=d[0].i,p[i].i=j,n[j].a(p[i]);for(j=t=0;j<k;j++)t+=n[j].n(c[j]);}}

Die Eingabe / Ausgabe in den Algorithmus ist eine Menge von Punkten ( struct P) mit xund y; und die Ausgabe ist dieselbe Menge, wobei ihre iMenge den Index des Ausgabeclusters angibt, in dem der Punkt endet.

Dieses Extra iwird auch verwendet, um die Cluster zu identifizieren. In der Hauptschleife wird der nächstgelegene Schwerpunkt zu jedem Punkt gefunden, indem eine Kopie der aktuellen Schwerpunkte nach der Nähe zu diesem Punkt sortiert wird.

Dies behandelt entartete Fälle (leere Cluster), indem die vorherige Position der entsprechenden Schwerpunkte beibehalten wird (siehe Definition von P::n, die auch den Abstand zum vorherigen Schwerpunkt zurückgibt). Ein paar Zeichen könnten gespart werden, wenn angenommen wird, dass diese nicht auftauchen.

Ungolfed, mit Haupt

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

#define V vector<P>
#define f float
struct P{
    f x,y,i=0;
    f d(P&p){return(p.x-x)*(p.x-x)+(p.y-y)*(p.y-y);} // distance squared
    f n(P&p){return i?x/=i,y/=i,d(p):x=p.x,y=p.y,0;} // normalize-or-reset
    f a(P&p){x+=p.x,y+=p.y,i++;}                     // add coordinates
};
P z;int l(P a,P b){return a.d(z)<b.d(z);}            // closer-to-z comparator 
f m(f k,V&p){
    f s=p.size(),i,j=0,t=1;V c(k),n=c,d;
    for(random_shuffle(p.begin(),p.end());j<k;c[j].i=j++)
        c[j]=p[j];                                // initial random assignment
    for(;t;c=n,n=V(k)){                           
        for(i=0;i<s;i++)                          // assign to clusters
            d=c,z=p[i],sort(d.begin(),d.end(),l),
            j=d[0].i,p[i].i=j,n[j].a(p[i]);       // and add those coords
        for(j=t=0;j<k;j++)t+=n[j].n(c[j]);        // normalize & count changes
    }        
}

int main(int argc, char **argv) {
    srand((unsigned long)time(0));

    int k;
    V p;
    sscanf(argv[1], "%d", &k);
    printf("Input:\n");
    for (int i=2,j=0; i<argc; i+=2, j++) {
        P n;
        sscanf(argv[i], "%f", &(n.x));
        sscanf(argv[i+1], "%f", &(n.y));
        p.push_back(n);
        printf("%d : %f,%f\n", j, p[j].x, p[j].y);
    }

    m(k,p);
    printf("Clusters:\n");
    for (int q=0; q<k; q++) {
        printf("%d\n", q);
        for (unsigned int i=0; i<p.size(); i++) {
            if (p[i].i == q) printf("\t%f,%f (%d)\n", p[i].x, p[i].y, i);
        }
    }
    return 0;
}

J, 60 54 Bytes

p=:[:(i.<./)"1([:+/&.:*:-)"1/
]p](p(+/%#)/.[)^:_(?#){]

Definiert ein Hilfsverb, pdas eine Liste von Punkten und Schwerpunkten erstellt und jeden Punkt anhand des Index des nächsten Schwerpunkts klassifiziert. Anschließend wird der Vorgang der Auswahl eines neuen Schwerpunkts wiederholt, indem die Durchschnittswerte der Punkte in jedem Cluster bis zur Konvergenz ermittelt und anschließend die Punkte für die Ausgabe aufgeteilt werden.

Verwendungszweck

Der Wert von k wird als Ganzzahl in der LHS angegeben. Die Liste der Punkte wird als 2d-Array auf der rechten Seite angegeben. Hier wird es als eine Liste von Punkten angegeben, die in ein 2d-Array von 5 x 2 umgeformt wird. Die Ausgabe ist die Bezeichnung, für die jeder Punkt in derselben Reihenfolge wie die Eingabe zum Cluster gehört.

Wenn Sie einen festen Samen für reproduzierbare Ergebnisse verwenden möchten, ersetzen Sie den ?durch einen ?.at (?#).

   p =: [:(i.<./)"1([:+/&.:*:-)"1/
   f =: ]p](p(+/%#)/.[)^:_(?#){]
   3 f (5 2 $ 4 8 15 16 23 42 _13.37 _12.1 666 _666)
0 1 1 0 2

Erläuterung

[:(i.<./)"1([:+/&.:*:-)"1/  Input: points on LHS, centroids on RHS
           (          )"1/  Form a table between each point and centroid and for each
                     -        Find the difference elementwise
            [:     *:         Square each
              +/&.:           Reduce using addition
                              Apply the inverse of square (square root) to that sum
[:(     )"1                 For each row of that table
     <./                      Reduce using min
   i.                         Find the index of the minimum in that row
                            Returns a list of indices for each point that shows
                            which centroid it belongs to

]p](p(+/%#)/.[)^:_(?#){]  Input: k on LHS, points on RHS
                    #     Count the number of points
                   ?      Choose k values in the range [0, len(points))
                          without repetition
                       ]  Identity function, get points
                      {   Select the points at the indices above
  ]                       Identity function, get points
   (         )^:_         Repeat until convergence
    p                       Get the labels for each point
             [              Identity function, get points
           /.               Partition the points using the labels and for each
      +/                      Take the sums of points elementwise
         #                    Get the number of points
        %                     Divide sum elementwise by the count
                            Return the new values as the next centroids
]                         Identity function, get points
 p                        Get the labels for each point and return it

CJam (60 Bytes)

{:Pmr<1/2P,#{:z{_:+\,/}f%:C,{P{C\f{.-Yf#:+}_:e<#1$=},\;}%}*}

Dies ist eine Funktion, die ihre Eingabe in der Form k pauf dem Stapel übernimmt . Es wird davon ausgegangen, dass die Punkte mit Doppel und nicht mit Int dargestellt werden. Es wird nicht implizit etwas über die Dimension der Punkte angenommen, daher würde es sich im euklidischen 6-D-Raum genauso gut gruppieren wie im angegebenen 2-D-Raum.

Online-Demo

Mathematica 14 12 Bytes

Da Einbauten erlaubt sind, sollte dies der Fall sein.

FindClusters

Beispiel

FindClusters[{{4, 8}, {15, 16}, {23, 42}, {-13.37, -12.1}, {666, -666}}, 3]

{{{4, 8}, {-13.37, -12.1}}, {{15, 16}, {23, 42}}, {{666, -666}}}

Gelee , 24 Bytes

_ÆḊ¥þ³i"Ṃ€$
ẊḣµÇÆmƙ³µÐLÇ

Probieren Sie es online aus!

Verwendet Funktionen, die implementiert wurden, nachdem diese Herausforderung veröffentlicht wurde. Angeblich ist dies nicht mehr konkurrierend .

Erläuterung

_ÆḊ¥þ³i"Ṃ€$  Helper link. Input: array of points
             (Classify) Given a size-k array of points, classifies
             each point in A to the closet point in the size-k array
    þ        Outer product with
     ³       All points, P
   ¥         Dyadic chain
_              Subtract
 ÆḊ            Norm
          $  Monadic chain
      i"     Find first index, vectorized
        Ṃ€   Minimum each

ẊḣµÇÆmƙ³µÐLÇ  Main link. Input: array of points P, integer k
  µ           Start new monadic chain
Ẋ               Shuffle P
 ḣ              Take the first k
        µ     Start new monadic chain
   Ç            Call helper (Classify)
      ƙ         Group with those values the items of
       ³        All points, P
    Æm            Take the mean of each group
         ÐL   Repeat that until the results converge
           Ç  Call helper (Classify)

R , 273 Bytes

function(K,P,C=P[sample(nrow(P),K),]){while(T){D=C
U=sapply(1:nrow(P),function(i)w(dist(rbind(P[i,],C))[1:K]))
C=t(sapply(1:K,function(i)colMeans(P[U==i,,drop=F])))
T=isTRUE(all.equal(C,D))}
cbind(U,P)}
w=function(x,y=seq_along(x)[x==min(x)])"if"(length(y)>1,sample(y,1),y)

Probieren Sie es online aus!

Nimmt Pals Matrix mit xund yKoordinaten in der ersten bzw. zweiten Spalte. Gibt Peine erste Spalte zurück, die den Clusterindex (Ganzzahl) angibt.

Ich musste neu definieren, windem ich die Quelle von kopierte nnet::which.is.max, um der Anforderung zu entsprechen, dass der Cluster bei Bindungen zufällig ausgewählt wird. Ansonsten würde ich which.minab basefür insgesamt 210 Bytes verwenden. Es gibt immer noch Platz zum Golfen, aber ich wollte es nicht zu sehr verschleiern, um anderen die Möglichkeit zu geben, mögliche Probleme in meinem Code zu erkennen.

Julia 213 Bytes

function f(p,k)
A=0
P=size(p,1)
c=p[randperm(P)[1:k],:]
while(true)
d=[norm(c[i]-p[j]) for i in 1:k, j in 1:P]
a=mapslices(indmin,d,1)
a==A&&return a
A=a
c=[mean(p[vec(a.==i),:],1) for i in 1:k]
end
end

Gibt ein Array mit der gleichen Länge wie zurück p, wobei Ganzzahlen angeben, zu welchem ​​Cluster das entsprechende Element pgehört.

Ich denke, es gibt noch einiges an Spielraum, um den Countdown der Charaktere zu optimieren.

(Natürlich könnte ich einfach das Paket Clustering.jl verwenden, um es trivial zu machen)