K-means é um algoritmo de clustering não supervisionado padrão que, dado um conjunto de "pontos" e um número de clusters K, atribuirá cada "ponto" a um dos K ​​clusters.

Pseudo-código de K-significa

Observe que existem muitas variantes de médias K. Você precisa implementar o algoritmo que estou descrevendo abaixo. Você pode ter alguma variação no algoritmo ou usar built-ins desde que obtenha o mesmo resultado que esse algoritmo, considerando os mesmos pontos iniciais.

Neste desafio, todas as entradas serão pontos no plano 2D (cada ponto é representado por suas coordenadas em 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 e saídas

• Você pode passar K e P através STDINou como argumento de função, etc.
• P e os pontos em P podem ser representados usando qualquer estrutura natural para conjuntos / listas no seu idioma de escolha.
• K é um número inteiro estritamente positivo.
• Você pode assumir que as entradas são válidas.
• Sempre haverá pelo menos K pontos em P.
• Você pode enviar os clusters STDOUT, retorná-los de uma função etc.
• A ordem dos clusters e a ordem dentro dos clusters não é importante. -Você pode retornar grupos de pontos para representar clusters ou cada ponto rotulado com um identificador para o cluster (por exemplo, um número inteiro).

Casos de teste

Como os clusters resultantes dependem de quais pontos foram escolhidos inicialmente, nem todos poderão obter os mesmos resultados (ou o mesmo resultado sempre que executar seu código).

Portanto, tome apenas a saída como exemplo de saída.

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

Pontuação

Isso é código-golfe , então a resposta mais curta em bytes vence.

Matlab, 25 bytes

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

Dada uma n x 2matriz (uma linha por ponto, por exemplo [[4,8]; [15,16]; [23,42]; [-13.37,-12.1]; [666,-666]]), essas funções retornam uma lista de rótulos para cada ponto de entrada.

C ++, 479 474 bytes

Apenas ~ 20x mais do que o Matlab!

Golfe

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

A entrada / saída para o algoritmo é um conjunto de pontos ( struct P) com xe y; e a saída é o mesmo conjunto, com os respectivos ipara indicar o índice do cluster de saída em que o ponto termina.

Esse extra itambém é usado para identificar os clusters. No loop principal, o centróide mais próximo de cada ponto é encontrado, classificando uma cópia dos centróides atuais por proximidade a esse ponto.

Isso lida com casos degenerados (grupos vazios) mantendo a posição anterior dos centróides correspondentes (consulte a definição de P::n, que também retorna a distância entre os centróides anteriores). Alguns caracteres podem ser salvos assumindo que eles não aparecerão.

Ungolfed, com 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 um verbo auxiliar pque pega uma lista de pontos e centróides e classifica cada ponto pelo índice do centróide mais próximo. Em seguida, ele usa isso para repetir o processo de escolha de um novo centróide, tomando as médias dos pontos em cada cluster até convergir e, em seguida, particionando os pontos para a saída.

Uso

O valor de k é dado como um número inteiro no LHS. A lista de pontos é apresentada como uma matriz 2D no RHS. Aqui, ele é especificado como uma lista de pontos que são remodelados em uma matriz 2d de 5 x 2. A saída será o rótulo para o qual cluster cada ponto pertence na mesma ordem que a entrada.

Se você deseja usar uma semente fixa para obter resultados reproduzíveis, substitua ?por ?.a (?#).

   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

Explicação

[:(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 é uma função que recebe sua entrada no formulário k pna pilha. Assume que os pontos são representados com duplos, não ints. Ele não assume implicitamente nada sobre a dimensão dos pontos, portanto se agruparia igualmente bem no espaço euclidiano 6-D como no 2-D especificado.

Demonstração online

Mathematica 14 12 bytes

Como os embutidos são permitidos, isso deve ser feito.

FindClusters

Exemplo

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

Gelatina , 24 bytes

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

Experimente online!

Usa os recursos implementados após o lançamento deste desafio. Supostamente, isso não é mais uma competição .

Explicação

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

Experimente online!

Toma Pcomo matriz, com xe ycoordenadas na primeira e na segunda coluna, respectivamente. Retorna Pcom uma primeira coluna adicionada que indica o índice do cluster (inteiro).

Eu tive que redefinir wcopiando a fonte de nnet::which.is.maxpara estar em conformidade com o requisito de que o cluster seja escolhido aleatoriamente em caso de vínculo. Caso contrário, eu usaria a which.minpartir basede um total de 210 bytes. Ainda há espaço para jogar golfe, mas eu não queria ofuscar muito para dar aos outros a chance de detectar possíveis problemas no meu 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

Retorna uma matriz do mesmo comprimento que p, com números inteiros indicando a qual cluster o elemento correspondente ppertence.

Acho que ainda há um pouco de escopo para otimizar a contagem de caracteres.

(É claro que eu poderia usar o pacote Clustering.jl para fazer isso trivialmente)