K-means est un algorithme de clustering non supervisé standard qui, étant donné un ensemble de "points" et un certain nombre de clusters K, attribuera chaque "point" à l'un des K clusters.

Pseudo-code de K-means

Notez qu'il existe de nombreuses variantes de K-means. Vous devez implémenter l'algorithme que je décris ci-dessous. Vous pouvez avoir une certaine variation sur l'algorithme ou utiliser des intégrés tant que vous obtiendrez le même résultat que cet algorithme étant donné les mêmes points initiaux.

Dans ce défi, toutes les entrées seront des points sur le plan 2D (chaque point est représenté par ses coordonnées en x et y).

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    

Entrées et sorties

• Vous pouvez faire passer K et P STDIN, ou comme argument de fonction, etc.
• P et les points de P peuvent être représentés en utilisant n'importe quelle structure naturelle pour les ensembles / listes dans la langue de votre choix.
• K est un entier strictement positif.
• Vous pouvez supposer que les entrées sont valides.
• Il y aura toujours au moins K points en P.
• Vous pouvez sortir les clusters vers STDOUT, les renvoyer d'une fonction, etc.
• L'ordre des clusters et l'ordre à l'intérieur des clusters sont sans importance. -Vous pouvez soit renvoyer des groupes de points pour représenter des grappes, soit chaque point étiqueté avec un identifiant pour la grappe (par exemple un entier).

Cas de test

Étant donné que les clusters résultants dépendent des points initialement choisis, vous n'obtiendrez peut-être pas tous les mêmes résultats (ou le même résultat à chaque fois que vous exécutez votre code).

Par conséquent, prenez uniquement la sortie comme exemple de sortie.

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

Notation

Il s'agit de code-golf , donc la réponse la plus courte en octets l'emporte.

Matlab, 25 octets

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

Étant donné une n x 2matrice (une ligne par point, par exemple [[4,8]; [15,16]; [23,42]; [-13.37,-12.1]; [666,-666]]), cette fonction renvoie une liste d'étiquettes pour chaque point d'entrée.

C ++, 479 474 octets

Seulement ~ 20x autant que Matlab!

Golfé

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

L'entrée / sortie de l'algorithme est un ensemble de points ( struct P) avec xet y; et la sortie est le même ensemble, avec leur iensemble pour indiquer l'indice du cluster de sortie dans lequel se termine le point.

Cet extra iest également utilisé pour identifier les clusters. Dans la boucle principale, le centroïde le plus proche de chaque point est trouvé en triant une copie des centroïdes actuels par proximité de ce point.

Cela gère les cas dégénérés (grappes vides) en conservant la position précédente des centroïdes correspondants (voir la définition de P::n, qui renvoie également la distance au centroïde précédent). Quelques caractères pourraient être sauvés en supposant qu'ils ne se reproduiraient pas.

Non golfé, avec main

#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 octets

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

Définit un verbe auxiliaire pqui prend une liste de points et de centroïdes et classe chaque point par l'index du centroïde le plus proche. Ensuite, il l'utilise pour répéter le processus de choix d'un nouveau centroïde en prenant les moyennes des points dans chaque cluster jusqu'à ce qu'il converge, puis pour partitionner les points pour la sortie.

Usage

La valeur de k est donnée sous forme d'entier sur le LHS. La liste des points est donnée sous forme d'un tableau 2D sur le RHS. Ici, il est spécifié comme une liste de points qui est remodelée en un tableau 2D de 5 x 2. La sortie sera l'étiquette pour laquelle le cluster appartient à chaque point dans le même ordre que l'entrée.

Si vous désirez utiliser une graine fixe pour des résultats reproductibles, remplacer ?par un ?.à (?#).

   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

Explication

[:(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 octets)

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

Il s'agit d'une fonction qui prend son entrée sous la forme k psur la pile. Il suppose que les points sont représentés par des doubles, pas des entiers. Il ne suppose implicitement rien de la dimension des points, il se regrouperait donc aussi bien dans l'espace euclidien 6-D que dans le 2-D spécifié.

Démo en ligne

Mathematica 14 12 octets

Étant donné que les intégrés sont autorisés, cela devrait le faire.

FindClusters

Exemple

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

Gelée , 24 octets

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

Essayez-le en ligne!

Utilise les fonctionnalités qui ont été implémentées après la publication de ce défi. Soi-disant, ce n'est plus non concurrentiel .

Explication

_ÆḊ¥þ³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 octets

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)

Essayez-le en ligne!

Prend Pcomme matrice, avec xet ycoordonne respectivement dans la première et la deuxième colonne. Renvoie Pavec une première colonne ajoutée qui indique l'index de cluster (entier).

J'ai dû redéfinir wen copiant la source de nnet::which.is.maxpour se conformer à l'exigence selon laquelle le cluster est choisi aléatoirement en cas d'égalité. Sinon, j'utiliserais which.minde basepour un total de 210 octets. Il y a encore de la place pour le golf mais je ne voulais pas trop le masquer pour donner aux autres une chance de repérer les problèmes possibles dans mon code.

Julia 213 octets

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

Renvoie un tableau de la même longueur que p, avec des entiers indiquant à quel cluster l'élément correspondant pappartient.

Je pense qu'il y a encore pas mal de possibilités pour optimiser le décompte des personnages.

(Bien sûr, je pourrais simplement utiliser le package Clustering.jl pour le faire trivialement)