exponenta event banner

kmeans

k-означает кластеризацию

Описание

пример

idx = kmeans(X,k) выполняет кластеризацию k-средств для разделения наблюдений матрицы данных 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-по-1 вектору sumd.

пример

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

Примеры

свернуть все

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

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

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-means + +.

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

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-means кластеризации. Укажите, что в данных имеется 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. kmeans функция поддерживает генерацию кода C/C + +, поэтому можно создать код, который принимает обучающие данные и возвращает результаты кластеризации, а затем развернуть код на устройстве. В этом потоке операций необходимо передать данные обучения, которые могут иметь значительный размер. Чтобы сохранить память на устройстве, можно разделить обучение и прогнозирование с помощью kmeans и pdist2соответственно.

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

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

Выполнить кластеризацию k-Means

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

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/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). Поскольку 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 функция, findNearestCentroid функция, и функция MEX возвращает тот же самый индекс.

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

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

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

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

свернуть все

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

Если X является числовым вектором, то kmeans обрабатывает его как матрицу данных n-by-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 - центроид (вектор строки).

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

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

d (x, c) = (x c) (x − c) ′

'cityblock'

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

d (x, c) =∑j=1p'xj−cj|

'cosine'

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

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

'correlation'

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

d (x, c) = 1 (x−x¯→) (c−c¯→) (x−x¯→) (x−x¯→) (c−c¯→) (c−c¯→) ′,

где

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

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

  • 1→p - вектор строки из p единиц.

'hamming'

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

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

d (x, y) =1p∑j=1pI{xj≠yj},

где 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. Поддерживаемые поля массива структуры определяют параметры управления итеративным алгоритмом.

В этой таблице представлены поддерживаемые поля. Обратите внимание, что поддерживаемые поля требуют 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(Панель инструментов параллельных вычислений) и явно создайте параллельный пул перед вызовом kmeans и настройка 'Options',statset('UseParallel',1).

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

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

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

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

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

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

Метод выбора исходных положений центроида кластера (или начальных значений), определяемый как разделенная запятыми пара, состоящая из '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-на-1 вектор, где элемент j - сумма расстояний от точки до центроида в кластере j. По умолчанию kmeans использует квадрат евклидова расстояния (см. 'Distance' метрики).

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

Подробнее

свернуть все

k-означает кластеризацию

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

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

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

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

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

    • Пакетное обновление - назначьте каждое наблюдение кластеру с ближайшим центроидом.

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

    Дополнительные сведения см. в разделе Алгоритмы.

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

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

k-means + + Алгоритм

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

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

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

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

  3. Выберите следующий центроид, c2 случайным образом из 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;xh∈Cp}d2 (xh, cp),

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

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

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

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

Алгоритмы

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

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

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

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

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

Ссылки

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

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

[3] Себер, Г. А. Ф. Многомерные наблюдения. Хобокен, Нью-Джерси: John Wiley & Sons, Inc., 1984.

[4] Spath, H. Cluster Discection and Analysis: Theory, FORTRAN Programs, примеры. В переводе Дж. Гольдшмидта. Нью-Йорк: Халстед Пресс, 1985.

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

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