K-means - это стандартный алгоритм кластеризации без наблюдения, который, учитывая набор «точек» и количество кластеров K, назначит каждую «точку» одному из K кластеров.

Псевдокод К-средних

Обратите внимание, что существует много вариантов K-средних. Вы должны реализовать алгоритм, который я описываю ниже. Вы можете иметь некоторые вариации в алгоритме или использовать встроенные модули, если вы получите тот же результат, что и этот алгоритм, с теми же начальными точками.

В этой задаче все входные данные будут точками на 2D-плоскости (каждая точка представлена ​​своими координатами в x и 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    

Входы и выходы

• Вы можете использовать K и P STDINкак аргумент функции и т. Д.
• P и точки в P могут быть представлены с использованием любой структуры, которая естественна для наборов / списков на выбранном вами языке.
• K - строго положительное целое число.
• Вы можете предположить, что входные данные действительны.
• Всегда будет хотя бы K очков в P.
• Вы можете выводить кластеры в STDOUT, возвращать их из функции и т. Д.
• Порядок кластеров и порядок внутри кластеров не имеет значения. -Вы можете вернуть группы точек для представления кластеров, или каждая точка помечена идентификатором для кластера (например, целое число).

Контрольные примеры

Поскольку получающиеся кластеры зависят от того, какие точки были изначально выбраны, вы можете не все получить одинаковые результаты (или один и тот же результат каждый раз, когда запускаете свой код).

Следовательно, используйте выходные данные только в качестве примера.

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

счет

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.

Matlab, 25 байт

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

Для данной n x 2матрицы (например, по одной строке на точку [[4,8]; [15,16]; [23,42]; [-13.37,-12.1]; [666,-666]]) эта функция возвращает список меток для каждой входной точки.

C ++, 479 474 байта

Всего в 20 раз больше, чем 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]);}}

Вход / выход алгоритма представляет собой набор точек ( struct P) с xи y; и выходные данные являются теми же самыми, с их iустановленными, чтобы указать индекс выходного кластера, в котором заканчивается точка.

Это дополнение iтакже используется для идентификации кластеров. В основном цикле ближайший центроид к каждой точке находится путем сортировки копии текущих центроидов по близости к этой точке.

Это обрабатывает вырожденные случаи (пустые кластеры), сохраняя предыдущую позицию соответствующих центроидов (см. Определение P::n, которое также возвращает расстояние до предыдущего центроида). Несколько символов могут быть сохранены, если предположить, что они не возникнут.

Неуправляемый, с основным

#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 байта

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

Определяет вспомогательный глагол, pкоторый берет список точек и центроидов и классифицирует каждую точку по индексу ближайшего центроида. Затем он использует это, чтобы повторить процесс выбора нового центроида, беря средние значения точек в каждом кластере, пока он не сходится, а затем разделить точки для вывода.

Применение

Значение k задается как целое число на LHS. Список точек представлен в виде двумерного массива на RHS. Здесь он указывается в виде списка точек, который преобразуется в двумерный массив 5 x 2. Выходными данными будет метка, для которой кластер каждой точке принадлежит в том же порядке, что и входные.

Если вы хотите использовать фиксированное начальное число для воспроизводимых результатов, замените его ?на ?.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

объяснение

[:(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 байт)

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

Это функция, которая принимает данные в виде k pстека. Предполагается, что точки представлены двойными, а не целыми числами. Он не подразумевает ничего явно относительно размерности точек, поэтому он будет группироваться так же хорошо в 6-мерном евклидовом пространстве, как и в указанном 2-мерном.

Онлайн демо

Mathematica 14 12 байт

Поскольку встроенные модули разрешены, это должно быть сделано.

FindClusters

пример

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

Желе , 24 байта

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

Попробуйте онлайн!

Использует функции, которые были реализованы после публикации этого вызова. Предположительно, это больше не конкурирует .

объяснение

_ÆḊ¥þ³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 байта

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)

Попробуйте онлайн!

Принимает в Pкачестве матрицы, с xи yкоординатами в первом и втором столбце соответственно. Возвращает Pс добавлением первого столбца, который указывает индекс кластера (целое число).

Мне пришлось переопределить w, скопировав источник, nnet::which.is.maxчтобы соответствовать требованию, что кластер выбирается случайным образом в случае связей. В противном случае я бы использовал which.minот baseв общей сложности 210 байтов. Есть все еще место для игры в гольф, но я не хотел запутывать это слишком много, чтобы дать другим возможность обнаружить возможные проблемы в моем коде.

Юлия 213 байт

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

Возвращает массив той же длины p, что и целые числа, указывающие, к какому кластеру принадлежит соответствующий элемент p.

Я думаю, что есть еще много возможностей для оптимизации обратного отсчета символов.

(Конечно, я мог бы просто использовать пакет Clustering.jl, чтобы сделать это тривиально)