K-means es un algoritmo de agrupamiento estándar no supervisado que, dado un conjunto de "puntos" y una cantidad de grupos K, asignará cada "punto" a uno de los K grupos.

Pseudocódigo de K-medias

Tenga en cuenta que hay muchas variantes de K-means. Tienes que implementar el algoritmo que describo a continuación. Es posible que tenga alguna variación en el algoritmo o use elementos integrados siempre que obtenga el mismo resultado que este algoritmo con los mismos puntos iniciales.

En este desafío, todas las entradas serán puntos en el plano 2D (cada punto está representado por sus coordenadas en x e 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    

Entradas y salidas

• Puede tomar K y P STDIN, o como un argumento de función, etc.
• P y los puntos en P pueden representarse utilizando cualquier estructura que sea natural para los conjuntos / listas en el idioma que elija.
• K es un entero estrictamente positivo.
• Puede suponer que las entradas son válidas.
• Siempre habrá al menos K puntos en P.
• Puede enviar los clústeres a STDOUT, devolverlos desde una función, etc.
• El orden de los grupos y el orden dentro de los grupos no es importante. -Puede devolver grupos de puntos para representar grupos, o cada punto etiquetado con un identificador para el grupo (por ejemplo, un número entero).

Casos de prueba

Dado que los grupos resultantes dependen de los puntos elegidos inicialmente, es posible que no todos obtengan los mismos resultados (o el mismo resultado cada vez que ejecute su código).

Por lo tanto, solo tome la salida como salida de ejemplo.

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

Puntuación

Este es el código de golf , por lo que gana la respuesta más corta en bytes.

Matlab, 25 bytes

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

Dada una n x 2matriz (una fila por punto, por ejemplo [[4,8]; [15,16]; [23,42]; [-13.37,-12.1]; [666,-666]]), esta función devuelve una lista de etiquetas para cada punto de entrada.

C ++, 479 474 bytes

¡Solo ~ 20 veces más que Matlab!

Golfed

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

La entrada / salida al algoritmo es un conjunto de puntos ( struct P) con xy y; y la salida es el mismo conjunto, con su iconjunto para indicar el índice del clúster de salida en el que termina el punto.

Ese extra itambién se utiliza para identificar los grupos. En el bucle principal, el centroide más cercano a cada punto se encuentra ordenando una copia de los centroides actuales por proximidad a ese punto.

Esto maneja casos degenerados (grupos vacíos) manteniendo la posición anterior de los centroides correspondientes (ver definición de P::n, que también devuelve la distancia al centroide anterior). Se podrían guardar algunos caracteres asumiendo que estos no aparecerán.

Sin golf, con principal

#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(+/%#)/.[)^:_(?#){]

Define un verbo auxiliar pque toma una lista de puntos y centroides y clasifica cada punto por el índice del centroide más cercano. Luego, utiliza eso para repetir el proceso de elegir un nuevo centroide tomando los promedios de los puntos en cada grupo hasta que converja, y luego para dividir los puntos para la salida.

Uso

El valor de k se da como un entero en el LHS. La lista de puntos se da como una matriz 2d en el RHS. Aquí se especifica como una lista de puntos que se forma en una matriz 2d de 5 x 2. La salida será la etiqueta para qué grupo pertenece cada punto en el mismo orden que la entrada.

Si desea utilizar una semilla fija para obtener resultados reproducibles, reemplace la ?con un ?.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

Explicación

[:(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$=},\;}%}*}

Esta es una función que toma su entrada en la forma k pen la pila. Se supone que los puntos se representan con dobles, no con int. No asume implícitamente nada sobre la dimensión de los puntos, por lo que se agruparía igualmente bien en el espacio euclidiano 6-D que en el 2-D especificado.

Demostración en línea

Mathematica 14 12 bytes

Dado que los elementos integrados están permitidos, esto debería hacerlo.

FindClusters

Ejemplo

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

Jalea , 24 bytes

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

Pruébalo en línea!

Utiliza características que se implementaron después de publicar este desafío. Supuestamente, esto ya no es no competitivo .

Explicación

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

Pruébalo en línea!

Toma Pcomo una matriz, con xy ycoordenadas en la primera y segunda columna respectivamente. Devuelve Pcon una primera columna agregada que indica el índice del clúster (entero).

Tuve que redefinir wcopiando la fuente de nnet::which.is.maxpara cumplir con el requisito de que el clúster se elija al azar en caso de empate. De lo contrario, usaría which.mindesde baseun total de 210 bytes. Todavía hay espacio para jugar al golf, pero no quería ofuscarlo demasiado para dar a otros la oportunidad de detectar posibles problemas dentro de mi código.

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

Devuelve una matriz de la misma longitud que p, con enteros que indican a qué clúster ppertenece el elemento correspondiente .

Creo que todavía hay bastante margen para optimizar la cuenta atrás del personaje.

(Por supuesto, podría usar el paquete Clustering.jl para hacerlo trivialmente)