kmeans

k -means кластеризация

Описание

пример

idx = kmeans(X,k) выполняет k -means кластеризацию, чтобы разбить наблюдения матрицы данных n -by p X в k кластеры, и возвращает вектор n -by-1 (idx) содержащие кластерные индексы каждого наблюдения. Строки X соответствуют точкам, а столбцы - переменным.

По умолчанию kmeans использует квадратную метрику Евклидова расстояния и алгоритм k -means + + для инициализации центра кластера.

пример

idx = kmeans(X,k,Name,Value) возвращает индексы кластера с дополнительными опциями, заданными одним или несколькими Name,Value аргументы в виде пар.

Например, задайте расстояние косинуса, количество раз, чтобы повторить кластеризацию с помощью новых начальных значений или использовать параллельные вычисления.

пример

[idx,C] = kmeans(___) возвращает k положения центроида кластера в k-by - p матрица C.

пример

[idx,C,sumd] = kmeans(___) возвращает внутри кластера суммы расстояний от точки до центроида в k-by-1 векторная sumd.

пример

[idx,C,sumd,D] = kmeans(___) Возвраты расстояния от каждой точки до каждого центроида в n -by - k матрица D.

Примеры

свернуть все

Данные кластера с помощью k-средних значений, затем постройте график областей кластера.

Загрузите набор данных радужки Фишера. Используйте длины и ширины лепестков в качестве предикторов.

load fisheriris
X = meas(:,3:4);

figure;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)'; 
ylabel 'Petal Widths (cm)';

Figure contains an axes. The axes with title Fisher's Iris Data contains an object of type line.

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

Группируйте данные. Задайте k = 3 кластера.

rng(1); % For reproducibility
[idx,C] = kmeans(X,3);

idx является вектором предсказанных индексов кластера, соответствующих наблюдениям в X. C - матрица 3 на 2, содержащая окончательные положения центроида.

Использование kmeans для вычисления расстояния от каждого центроида до точек на сетке. Для этого передайте центроиды (C) и точки на сетке, чтобы kmeans, и реализуйте одну итерацию алгоритма.

x1 = min(X(:,1)):0.01:max(X(:,1));
x2 = min(X(:,2)):0.01:max(X(:,2));
[x1G,x2G] = meshgrid(x1,x2);
XGrid = [x1G(:),x2G(:)]; % Defines a fine grid on the plot

idx2Region = kmeans(XGrid,3,'MaxIter',1,'Start',C);
Warning: Failed to converge in 1 iterations.
    % Assigns each node in the grid to the closest centroid

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

Постройте график областей кластера.

figure;
gscatter(XGrid(:,1),XGrid(:,2),idx2Region,...
    [0,0.75,0.75;0.75,0,0.75;0.75,0.75,0],'..');
hold on;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)';
ylabel 'Petal Widths (cm)'; 
legend('Region 1','Region 2','Region 3','Data','Location','SouthEast');
hold off;

Figure contains an axes. The axes with title Fisher's Iris Data contains 4 objects of type line. These objects represent Region 1, Region 2, Region 3, Data.

Случайным образом сгенерируйте выборочные данные.

rng default; % For reproducibility
X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2)];

figure;
plot(X(:,1),X(:,2),'.');
title 'Randomly Generated Data';

Figure contains an axes. The axes with title Randomly Generated Data contains an object of type line.

Похоже, в данных есть два кластера.

Разделите данные на два кластера и выберите лучшее расположение из пяти инициализаций. Отобразите окончательный выход.

opts = statset('Display','final');
[idx,C] = kmeans(X,2,'Distance','cityblock',...
    'Replicates',5,'Options',opts);
Replicate 1, 3 iterations, total sum of distances = 201.533.
Replicate 2, 5 iterations, total sum of distances = 201.533.
Replicate 3, 3 iterations, total sum of distances = 201.533.
Replicate 4, 3 iterations, total sum of distances = 201.533.
Replicate 5, 2 iterations, total sum of distances = 201.533.
Best total sum of distances = 201.533

По умолчанию программа инициализирует репликацию отдельно, используя k-средних значений + +.

Постройте график кластеров и центроидов кластера.

figure;
plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12)
hold on
plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12)
plot(C(:,1),C(:,2),'kx',...
     'MarkerSize',15,'LineWidth',3) 
legend('Cluster 1','Cluster 2','Centroids',...
       'Location','NW')
title 'Cluster Assignments and Centroids'
hold off

Figure contains an axes. The axes with title Cluster Assignments and Centroids contains 3 objects of type line. These objects represent Cluster 1, Cluster 2, Centroids.

Можно определить, насколько хорошо разделены кластеры, передав idx на silhouette.

Кластеризация больших наборов данных может занять время, особенно если вы используете онлайн-обновления (по умолчанию). Если у вас есть лицензия Parallel Computing Toolbox ™ и вы устанавливаете опции для параллельных вычислений, то kmeans запускает каждую задачу кластеризации (или репликацию) параллельно. И, если Replicates> 1, затем параллельные вычисления уменьшают время до сходимости.

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

Mu = bsxfun(@times,ones(20,30),(1:20)'); % Gaussian mixture mean
rn30 = randn(30,30);
Sigma = rn30'*rn30; % Symmetric and positive-definite covariance
Mdl = gmdistribution(Mu,Sigma); % Define the Gaussian mixture distribution

rng(1); % For reproducibility
X = random(Mdl,10000);

Mdl является 30-мерным gmdistribution модель с 20 компонентами. X является матрицей 10000 на 30 данных, сгенерированных из Mdl.

Задайте опции для параллельных вычислений.

stream = RandStream('mlfg6331_64');  % Random number stream
options = statset('UseParallel',1,'UseSubstreams',1,...
    'Streams',stream);

Входной параметр 'mlfg6331_64' от RandStream задает использование мультипликативного алгоритма генератора Фибоначчи с отставанием. options является массивом структур с полями, которые задают опции для управления оценкой.

Кластеризуйте данные с помощью k-средних значений кластеризации. Задайте, что в данных k = 20 кластеров и увеличьте количество итераций. Обычно целевая функция содержит локальные минимумы. Задайте 10 репликаций, чтобы помочь найти более низкий, локальный минимум.

tic; % Start stopwatch timer
[idx,C,sumd,D] = kmeans(X,20,'Options',options,'MaxIter',10000,...
    'Display','final','Replicates',10);
Starting parallel pool (parpool) using the 'local' profile ...
connected to 6 workers.
Replicate 5, 72 iterations, total sum of distances = 7.73161e+06.
Replicate 1, 64 iterations, total sum of distances = 7.72988e+06.
Replicate 3, 68 iterations, total sum of distances = 7.72576e+06.
Replicate 4, 84 iterations, total sum of distances = 7.72696e+06.
Replicate 6, 82 iterations, total sum of distances = 7.73006e+06.
Replicate 7, 40 iterations, total sum of distances = 7.73451e+06.
Replicate 2, 194 iterations, total sum of distances = 7.72953e+06.
Replicate 9, 105 iterations, total sum of distances = 7.72064e+06.
Replicate 10, 125 iterations, total sum of distances = 7.72816e+06.
Replicate 8, 70 iterations, total sum of distances = 7.73188e+06.
Best total sum of distances = 7.72064e+06
toc % Terminate stopwatch timer
Elapsed time is 61.915955 seconds.

Командное окно указывает, что доступно шесть работников. Количество работников может варьироваться в вашей системе. В Командном окне отображается количество итераций и значение целевой функции терминала для каждого тиража. Выходные аргументы содержат результаты репликации 9, поскольку она имеет самую низкую общую сумму расстояний.

kmeans выполняет k-средних значений кластеризацию, чтобы разбить данные на k кластеров. Когда у вас есть новый набор данных для кластера, можно создать новые кластеры, которые включают существующие данные и новые данные, используя kmeans. The kmeans функция поддерживает генерацию кода C/C + +, поэтому можно сгенерировать код, который принимает обучающие данные и возвращает результаты кластеризации, а затем развертывает код на устройстве. В этом рабочем процессе вы должны передать обучающие данные, которые могут быть значительного размера. Чтобы сохранить память на устройстве, можно разделить обучение и предсказание при помощи kmeans и pdist2, соответственно.

Использование kmeans для создания кластеров в MATLAB ® и использования pdist2 в сгенерированном коде для назначения новых данных существующим кластерам. Для генерации кода задайте функцию точки входа, которая принимает положения центроида кластера и новый набор данных и возвращает индекс ближайшего кластера. Затем сгенерируйте код для функции точки входа.

Для генерации кода C/C + + требуется Coder™ MATLAB ®.

Выполните k-средних значений

Сгенерируйте набор обучающих данных с помощью трех распределений.

rng('default') % For reproducibility
X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2);
    randn(100,2)*0.75];

Разделите обучающие данные на три кластера с помощью kmeans.

[idx,C] = kmeans(X,3);

Постройте график кластеров и центроидов кластера.

figure
gscatter(X(:,1),X(:,2),idx,'bgm')
hold on
plot(C(:,1),C(:,2),'kx')
legend('Cluster 1','Cluster 2','Cluster 3','Cluster Centroid')

Figure contains an axes. The axes contains 4 objects of type line. These objects represent Cluster 1, Cluster 2, Cluster 3, Cluster Centroid.

Назначение новых данных существующим кластерам

Сгенерируйте тестовые данные набор.

Xtest = [randn(10,2)*0.75+ones(10,2);
    randn(10,2)*0.5-ones(10,2);
    randn(10,2)*0.75];

Классификация набора тестовых данных с помощью существующих кластеров. Найдите ближайший центроид из каждой точки тестовых данных при помощи pdist2.

[~,idx_test] = pdist2(C,Xtest,'euclidean','Smallest',1);

Постройте график тестовых данных и пометьте тестовые данные с помощью idx_test при помощи gscatter.

gscatter(Xtest(:,1),Xtest(:,2),idx_test,'bgm','ooo')
legend('Cluster 1','Cluster 2','Cluster 3','Cluster Centroid', ...
    'Data classified to Cluster 1','Data classified to Cluster 2', ...
    'Data classified to Cluster 3')

Figure contains an axes. The axes contains 7 objects of type line. These objects represent Cluster 1, Cluster 2, Cluster 3, Cluster Centroid, Data classified to Cluster 1, Data classified to Cluster 2, Data classified to Cluster 3.

Сгенерируйте код

Сгенерируйте код С, который присваивает новые данные существующим кластерам. Обратите внимание, что для генерации кода C/C + + требуется Coder™ MATLAB ®.

Задайте функцию точки входа с именем findNearestCentroid который принимает положения центроида и новые данные, а затем находит ближайший кластер при помощи pdist2.

Добавьте %#codegen директива компилятора (или прагма) к функции точки входа после сигнатуры функции, чтобы указать, что вы намерены сгенерировать код для алгоритма MATLAB. Добавление этой директивы предписывает анализатору кода MATLAB помочь вам диагностировать и исправить нарушения, которые могут привести к ошибкам во время генерации кода.

type findNearestCentroid % Display contents of findNearestCentroid.m
function idx = findNearestCentroid(C,X) %#codegen
[~,idx] = pdist2(C,X,'euclidean','Smallest',1); % Find the nearest centroid

Примечание.Если нажать кнопку, расположенную в правом верхнем разделе этой страницы и открыть этот пример в MATLAB ®, MATLAB ® открывает папку примера. Эта папка включает файл функции точки входа.

Сгенерируйте код при помощи codegen (MATLAB Coder). Поскольку C и C++ являются статически типизированными языками, вы должны определить свойства всех переменных в функции точки входа во время компиляции. Чтобы задать тип данных и размер массива входов findNearestCentroid, передайте выражение MATLAB, которое представляет множество значений с определенным типом данных и размером массива при помощи -args опция. Для получения дополнительной информации смотрите Задать аргументы переменного размера для генерации кода.

codegen findNearestCentroid -args {C,Xtest}
Code generation successful.

codegen генерирует MEX-функцию findNearestCentroid_mex с зависящим от платформы внутренним абонентом.

Проверьте сгенерированный код.

myIndx = findNearestCentroid(C,Xtest);
myIndex_mex = findNearestCentroid_mex(C,Xtest);
verifyMEX = isequal(idx_test,myIndx,myIndex_mex)
verifyMEX = logical
   1

isequal возвращает логический 1 (true), что означает, что все входы равны. Сравнение подтверждает, что pdist2 function, the findNearestCentroid функция, и MEX-функция возвращает тот же индекс.

Можно также сгенерировать оптимизированный код CUDA ® с помощью GPU Coder™.

cfg = coder.gpuConfig('mex');
codegen -config cfg findNearestCentroid -args {C,Xtest}

Для получения дополнительной информации о генерации кода смотрите Рабочий процесс генерации общего кода. Для получения дополнительной информации о кодере GPU смотрите Запуск с кодером GPU (GPU Coder) и Поддерживаемые функции (GPU Coder).

Входные параметры

свернуть все

Данные, заданные как числовая матрица. Строки X соответствуют наблюдениям, а столбцы соответствуют переменным.

Если X является числовым вектором, тогда kmeans рассматривает его как n-на-1 матрицу данных, независимо от ее ориентации.

Программное обеспечение лечит NaNs в X как отсутствующие данные и удаляет любую строку X который содержит, по крайней мере, один NaN. Удаление строк X уменьшает размер выборки. kmeans функция возвращает NaN для соответствующего значения в выходном аргументе idx.

Типы данных: single | double

Количество кластеров в данных, заданное как положительное целое число.

Типы данных: single | double

Аргументы в виде пар имя-значение

Задайте необязательные разделенные разделенными запятой парами Name,Value аргументы. Name - имя аргумента и Value - соответствующее значение. Name должны находиться внутри кавычек. Можно задать несколько аргументов в виде пар имен и значений в любом порядке Name1,Value1,...,NameN,ValueN.

Пример: 'Distance','cosine','Replicates',10,'Options',statset('UseParallel',1) задает расстояние косинуса, 10 репликация кластеров с различными начальными значениями и использование параллельных вычислений.

Уровень выхода для отображения в Командном окне, заданный как разделенная разделенными запятой парами, состоящая из 'Display' и один из следующих опций:

  • 'final' - Отображает результаты окончательной итерации

  • 'iter' - Отображает результаты каждой итерации

  • 'off' - Ничего не отображает

Пример: 'Display','final'

Метрика расстояния, в p-мерное пространство, используемое для минимизации, задается как разделенная разделенными запятой парами, состоящая из 'Distance' и 'sqeuclidean', 'cityblock', 'cosine', 'correlation', или 'hamming'.

kmeans вычисляет центроидные кластеры по-разному для поддерживаемых метрик расстояния. В этой таблице представлены доступные метрики расстояния. В формулах x является наблюдением (то есть строкой X) и c является центроидом (a вектора-строки).

Метрика расстоянияОписаниеФормула
'sqeuclidean'

Квадратное Евклидово расстояние (по умолчанию). Каждый центроид является средним значением точек в этом кластере.

d(x,c)=(xc)(xc)

'cityblock'

Сумма абсолютных различий, т.е. L 1 расстояние. Каждый центроид является компонентной медианой точек в этом кластере.

d(x,c)=j=1p|xjcj|

'cosine'

Один минус косинус включенного угла между точками (рассматривается как векторы). Каждый центроид является средним значением точек в этом кластере, после нормализации этих точек к единичной евклидовой длине.

d(x,c)=1xc(xx)(cc)

'correlation'

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

d(x,c)=1(xx¯)(cc¯)(xx¯)(xx¯)(cc¯)(cc¯),

где

  • x¯=1p(j=1pxj)1p

  • c¯=1p(j=1pcj)1p

  • 1p - вектор-строка из p таковых.

'hamming'

Эта метрика подходит только для двоичных данных.

Это доля бит, которые различаются. Каждый центроид является компонентной медианой точек в этом кластере.

d(x,y)=1pj=1pI{xjyj},

где I - функция индикации.

Пример: 'Distance','cityblock'

Действие, которое необходимо предпринять, если кластер теряет все свои наблюдения представителей, заданные как разделенная разделенными запятой парами, состоящая из 'EmptyAction' и один из следующих опций.

ЗначениеОписание
'error'

Считайте пустой кластер ошибкой.

'drop'

Удалите все кластеры, которые становятся пустыми. kmeans устанавливает соответствующие возвращаемые значения в C и D на NaN.

'singleton'

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

Пример: 'EmptyAction','error'

Максимальное количество итераций, заданное как разделенная разделенными запятой парами, состоящая из 'MaxIter' и положительное целое число.

Пример: 'MaxIter',1000

Типы данных: double | single

Флаг онлайн-обновления, заданный как разделенная разделенными запятой парами, состоящая из 'OnlinePhase' и 'off' или 'on'.

Если OnlinePhase является on, затем kmeans выполняет фазу оперативного обновления в дополнение к фазе пакетного обновления. Онлайн- фаза может занимать много времени для больших наборов данных, но гарантирует решение, которое является локальным минимумом критерия расстояния. Другими словами, программное обеспечение находит раздел данных, в котором перемещение любой одной точки в другой кластер увеличивает общую сумму расстояний.

Пример: 'OnlinePhase','on'

Опции для управления итерационным алгоритмом для минимизации критериев аппроксимации, заданные как разделенная разделенными запятой парами, состоящая из 'Options' и массив структур, возвращенный statset. Поддерживаемые поля массива структур задают опции для управления итеративным алгоритмом.

В этой таблице представлены поддерживаемые поля. Обратите внимание, что для поддерживаемых полей требуется Parallel Computing Toolbox™.

ОбластьОписание
'Streams'

A RandStream объект или массив ячеек таких объектов. Если вы не задаете Streams, kmeans использует поток по умолчанию или потоки. Если вы задаете Streams, используйте один объект, кроме тех случаев, когда существуют все следующие условия:

  • У вас открытый параллельный пул.

  • UseParallel является true.

  • UseSubstreams является false.

В этом случае используйте массив ячеек того же размера, что и параллельный пул. Если параллельный пул не открыт, то Streams должен предоставить один поток случайных чисел.

'UseParallel'
  • Если true и Replicates > 1, затем kmeans реализует алгоритм k-means на каждом реплике параллельно.

  • Если Parallel Computing Toolbox не установлен, то расчеты происходят в последовательном режиме. Значение по умолчанию является false, что указывает на последовательный расчет.

'UseSubstreams'Установите значение true для параллельного вычисления воспроизводимым способом. Значение по умолчанию является false. Чтобы вычислить воспроизводимо, установите Streams к типу, разрешающему субпотоки: 'mlfg6331_64' или 'mrg32k3a'.

Чтобы гарантировать более предсказуемые результаты, используйте parpool (Parallel Computing Toolbox) и явным образом создать параллельный пул перед вызовом kmeans и настройка 'Options',statset('UseParallel',1).

Пример: 'Options',statset('UseParallel',1)

Типы данных: struct

Количество раз, чтобы повторить кластеризацию с использованием новых начальных положений центроида кластера, заданное как разделенная разделенными запятой парами, состоящая из 'Replicates' и целое число. kmeans возвращает решение с самым низким sumd.

Можно задать 'Replicates' неявно путем предоставления трехмерные массивы в качестве значения для 'Start' аргумент пары "имя-значение".

Пример: 'Replicates',5

Типы данных: double | single

Метод выбора начальных положений центроида кластера (или seeds), заданный как разделенная разделенными запятой парами, состоящая из 'Start' и 'cluster', 'plus', 'sample', 'uniform', числовую матрицу или числовой массив. В этой таблице представлены доступные опции выбора семян.

ЗначениеОписание
'cluster'

Выполните предварительную фазу кластеризации на случайном 10% -подвыборку X когда количество наблюдений в подвыборке больше k. Эта предварительная фаза сама инициализируется с помощью 'sample'.

Если количество наблюдений в случайном 10% -подвыборка меньше k, затем программное обеспечение выбирает k наблюдения от X наугад.

'plus' (по умолчанию)Выберите k начальные значения путем реализации алгоритма k -means + + для инициализации центра кластера.
'sample'Выберите k наблюдения от X наугад.
'uniform'Выберите k точки равномерно случайным образом из области значений X. Недопустимо использование расстояния Хемминга.
числовая матрицаk-by - p матрица начальных местоположений центроида. Строки Start соответствуют семенам. Программное обеспечение выводит k от первой размерности Start, так что можно пройти [] для k.
числовой массивk-by- p -by- r массив начальных местоположений центроида. Строки каждой страницы соответствуют семенам. Третья размерность вызывает репликацию стандартной программы кластеризации. Страница j содержит набор начальных чисел для репликации j. Программа выводит количество репликаций (заданное 'Replicates' Аргумент пары "имя-значение") от размера третьей размерности.

Пример: 'Start','sample'

Типы данных: char | string | double | single

Выходные аргументы

свернуть все

Индексы кластера, возвращенные как числовой вектор-столбец. idx имеет столько строк, сколько X, и каждая строка указывает назначение кластера соответствующего наблюдения.

Расположения центроида кластера, возвращенные как числовая матрица. C является k-by - p матрица, где j строка является центроидом j кластера.

Внутри-кластерные суммы расстояний между точками и центроидами, возвращенные в виде числа вектора-столбца. sumd является kВектор -by-1, где j элемента является суммой расстояний от точки до центроида в j кластера. По умолчанию, kmeans использует квадратное Евклидово расстояние (см 'Distance' метрики).

Расстояния от каждой точки до каждого центроида, возвращаемые в виде числовой матрицы. D является n -by- k матрица, где элемент (j, m) является расстоянием от j наблюдения до m центроида. По умолчанию ,kmeans использует квадратное Евклидово расстояние (см 'Distance' метрики).

Подробнее о

свернуть все

k -Means кластеризация

k-means clustering, или алгоритм Ллойда [2], является итеративным алгоритмом разбиения данных, который присваивает n наблюдения точно одному из k кластеров, заданных центроидами, где k выбирается перед началом алгоритма.

Алгоритм протекает следующим образом:

  1. Выберите k центра кластеров (centroid). Например, выберите k наблюдения случайным образом (при помощи 'Start','sample') или используйте алгоритм k -means + + для инициализации центра кластеров (по умолчанию).

  2. Вычислите расстояния от точки до кластера до центроида всех наблюдений до каждого центроида.

  3. Существует два способа продолжения (заданные OnlinePhase):

    • Обновление пакета - присвоение каждого наблюдения кластеру с ближайшим центроидом.

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

    Для получения дополнительной информации см. «Алгоритмы».

  4. Вычислите среднее значение наблюдений в каждом кластере, чтобы получить k новых местоположений центроида.

  5. Повторяйте шаги с 2 по 4, пока назначения кластеров не не изменятся или не будет достигнуто максимальное количество итераций.

k -меанс + + Алгоритм

k -means++ algorithm использует эвристический метод, чтобы найти семена центроидов для кластеризации k-means. Согласно Артуру и Васильвицкому [1], k-means + + улучшает время работы алгоритма Ллойда и качество конечного решения.

Алгоритм k -means + + выбирает семена следующим образом, принимая, что количество кластеров k.

  1. Выберите наблюдение равномерно случайным образом из набора данных, X. Выбранное наблюдение является первым центроидом и обозначается c 1.

  2. Вычислите расстояния от каждого наблюдения до c 1. Обозначите расстояние между c j и m наблюдения какd(xm,cj).

  3. Выберите следующий центроид, c 2 случайным образом из X с вероятностью

    d2(xm,c1)j=1nd2(xj,c1).

  4. Чтобы выбрать центр j:

    1. Вычислите расстояния от каждого наблюдения до каждого центроида и присвойте каждое наблюдение ближайшему центроиду.

    2. Для m = 1,..., n и p = 1,..., j - 1, выберите j центроида случайным образом из X с вероятностью

      d2(xm,cp){h;xhCp}d2(xh,cp),

      где Cp - набор всех наблюдений, ближайших к центроиду cp и xm принадлежит Cp.

      То есть выберите каждый последующий центр с вероятностью, пропорциональной расстоянию от себя до ближайшего центра, который вы уже выбрали.

  5. Повторите шаг 4, пока не будут выбраны k центроиды.

Артур и Васильвицкий [1] демонстрируют, используя симуляционное исследование для нескольких ориентаций кластера, что k-means + + достигает более высокой сходимости к более низкой сумме расстояний внутри кластера, суммы квадратов от точки до кластера и центроида, чем алгоритм Ллойда.

Алгоритмы

  • kmeans использует двухфазный итеративный алгоритм, чтобы минимизировать сумму расстояний от точки до центроида, суммированных по всем k кластеры.

    1. Эта первая фаза использует batch updates, где каждая итерация состоит из переназначения точек ближайшему центроиду кластера, все сразу, с последующим пересчетом центроидов кластера. Эта фаза иногда не сходится к решению, которое является локальным минимумом. То есть раздел данных, где перемещение любой отдельной точки в другой кластер, увеличивает общую сумму расстояний. Это более вероятно для небольших наборов данных. Пакетная фаза является быстрой, но потенциально только аппроксимирует решение как начальная точка для второй фазы.

    2. Эта вторая фаза использует online updates, где точки индивидуально переназначиваются, если это уменьшает сумму расстояний, и центроиды кластера пересчитываются после каждого переназначения. Каждая итерация на этой фазе состоит из одного прохода, хотя и всех точек. Эта фаза сходится к локальному минимуму, хотя могут быть и другие локальные минимумы с меньшей общей суммой расстояний. В целом нахождение глобального минимума решается исчерпывающим выбором начальных точек, но использование нескольких повторений со случайными начальными точками обычно приводит к решению, которое является глобальным минимумом.

  • Если Replicates = r > 1 и Start является plus (по умолчанию), затем программное обеспечение выбирает r возможно, различные наборы начальных чисел согласно k -means + + алгоритму.

  • Если вы включите UseParallel опция в Options и Replicates > 1, затем каждый рабочий выбирает семена и кластеры параллельно.

Ссылки

[1] Артур, Давид и Серги Васильвицкие. «K-средних значений + +: Преимущества тщательного посева». SODA "07: Материалы восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. 2007, стр 1027–1035.

[2] Ллойд, Стюарт П. «Квантование методом наименьших квадратов в PCM». Транзакции IEEE по теории информации. Том 28, 1982, стр. 129-137.

[3] Себер, Г. А. Ф. Многомерные наблюдения. Hoboken, NJ: John Wiley & Sons, Inc., 1984.

[4] Spath, H. Cluster Dissection and Analysis: Theory, FORTRAN Programms, примеры. Перевод Я. Гольдшмидта. Нью-Йорк: Halsted Press, 1985.

Расширенные возможности

.
Представлено до R2006a