K-średnich jest standardowym nie nadzorowanym algorytmem grupowania, który, biorąc pod uwagę zestaw „punktów” i pewną liczbę klastrów K, przypisze każdy „punkt” do jednego z K klastrów.

Pseudokod K-średnich

Zauważ, że istnieje wiele wariantów K-średnich. Musisz zaimplementować algorytm, który opisuję poniżej. Możesz mieć pewne różnice w algorytmie lub użyć wbudowanych, o ile uzyskasz taki sam wynik jak ten algorytm, mając te same punkty początkowe.

W tym wyzwaniu wszystkie dane wejściowe będą punktami na płaszczyźnie 2D (każdy punkt jest reprezentowany przez jego współrzędne w xiy).

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    

Wejścia i wyjścia

• Możesz wziąć K i P przez STDIN, lub jako argument funkcji itp.
• P i punkty w P można przedstawić za pomocą dowolnej struktury, która jest naturalna dla zestawu / list w wybranym języku.
• K jest ściśle dodatnią liczbą całkowitą.
• Możesz założyć, że dane wejściowe są prawidłowe.
• Zawsze będzie co najmniej K punktów w P.
• Możesz wyprowadzać klastry do STDOUT, zwracać je z funkcji itp.
• Kolejność klastrów i kolejność wewnątrz klastrów jest nieistotna. -Można albo zwrócić grupy punktów, które reprezentują klastry, albo każdy punkt oznaczony identyfikatorem klastra (np. Liczba całkowita).

Przypadki testowe

Ponieważ powstałe klastry zależą od tego, które punkty zostały początkowo wybrane, nie wszyscy mogą uzyskać takie same wyniki (lub ten sam wynik przy każdym uruchomieniu kodu).

Dlatego dane wyjściowe należy traktować tylko jako dane wyjściowe.

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]]]

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Matlab, 25 bajtów

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

Biorąc pod uwagę n x 2macierz (np. Jeden wiersz na punkt [[4,8]; [15,16]; [23,42]; [-13.37,-12.1]; [666,-666]]), funkcja ta zwraca listę etykiet dla każdego punktu wejściowego.

C ++, 479 474 bajty

Tylko ~ 20x więcej niż Matlab!

Grał w golfa

#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]);}}

Wejście / wyjście algorytmu jest zbiorem punktów ( struct P) z xi y; a dane wyjściowe są tego samego zestawu, z ich izestawem wskazującym indeks klastra wyjściowego, w którym kończy się punkt.

Dodatek iten służy również do identyfikacji klastrów. W głównej pętli centroid najbliżej każdego punktu znajduje się poprzez posortowanie kopii bieżących centroidów według odległości od tego punktu.

To obsługuje przypadki zdegenerowane (puste klastry) poprzez zachowanie poprzedniej pozycji odpowiadających centroidów (patrz definicja P::n, która również zwraca odległość do poprzedniej centroidy). Można zapisać kilka znaków, zakładając, że nie pojawią się one.

Bez golfa, z głównym

#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 bajtów

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

Definiuje czasownik pomocniczy, pktóry pobiera listę punktów i centroidów i klasyfikuje każdy punkt według indeksu najbliższego środka ciężkości. Następnie używa tego, aby powtórzyć proces wyboru nowego środka ciężkości, biorąc średnie wartości punktów w każdym skupieniu, aż się zbiegnie, a następnie dzieląc punkty na dane wyjściowe.

Stosowanie

Wartość k jest podana jako liczba całkowita na LHS. Lista punktów jest podana jako tablica 2d na RHS. Tutaj jest określony jako lista punktów, które są przekształcane w tablicę 2d o wymiarach 5 x 2. Wyjście będzie etykietą, dla której klaster każdy punkt należy w tej samej kolejności co dane wejściowe.

Jeśli pragniesz użyć stałego materiału siewnego dla powtarzalnych wyników, wymienić ?z ?.na (?#).

   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

Wyjaśnienie

[:(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 bajtów)

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

Jest to funkcja, która przyjmuje dane wejściowe w formie k pstosu. Zakłada się, że punkty są reprezentowane przez podwójne, a nie ints. Nie zakłada domyślnie niczego o wymiarze punktów, więc skupiałby się równie dobrze w 6-D przestrzeni euklidesowej, jak w określonej 2-D.

Demo online

Mathematica 14 12 bajtów

Ponieważ wbudowane są dozwolone, powinno to zrobić.

FindClusters

Przykład

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}}}

Galaretka , 24 bajty

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

Wypróbuj online!

Korzysta z funkcji zaimplementowanych po opublikowaniu tego wyzwania. Podobno nie jest to już niekonkurencyjne .

Wyjaśnienie

_ÆḊ¥þ³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 bajtów

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)

Wypróbuj online!

Staje się Pjako matryca z xi ywspółrzędne w pierwszej i drugiej kolumnie, odpowiednio. Zwraca Pz dodaną pierwszą kolumną, która wskazuje indeks klastra (liczba całkowita).

Musiałem przedefiniować w, kopiując źródło z, nnet::which.is.maxaby dostosować się do wymogu losowego wybierania klastra w przypadku powiązań. W przeciwnym razie użyłbym which.minz basew sumie 210 bajtów. Wciąż jest pole do gry w golfa, ale nie chciałem zbytnio zaciemniać go, aby dać innym szansę dostrzeżenia możliwych problemów w moim kodzie.

Julia 213 bajtów

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

Zwraca tablicę o tej samej długości co p, z liczbami całkowitymi wskazującymi, do którego klastra należy odpowiedni element p.

Myślę, że wciąż istnieje spory zakres, aby zoptymalizować odliczanie postaci.

(Oczywiście mogę po prostu użyć pakietu Clustering.jl, aby zrobić to trywialnie)