kmeans

Описание

пример

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

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

пример

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

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

пример

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

пример

[idx,C,sumd] = kmeans(___) возвращает суммы в кластере расстояний точки к центроиду в k- 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)';

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

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

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

idx вектор из предсказанных кластерных индексов, соответствующих наблюдениям в XC 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;

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

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';

В данных, кажется, существует два кластера.

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

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

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

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

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

Выполните Кластеризацию 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')

Присвойте новые данные существующим кластерам

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

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')

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

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

Задайте функцию с именем точки входа 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}

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 возвращает логическую единицу (true), что означает, что все входные параметры равны. Сравнение подтверждает что pdist2 функция, findNearestCentroid функция и MEX-функция возвращают тот же индекс.

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

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

Для получения дополнительной информации о генерации кода смотрите Общий Рабочий процесс Генерации кода. Для получения дополнительной информации о Кодере GPU смотрите Начало работы с GPU Coder (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'Корреляция, или 'hamming'.

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

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

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

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

'cityblock'

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

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 - средний алгоритм на каждом реплицирует параллельно.

  • Если 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'плюс, 'sample', 'uniform', числовая матрица или числовой массив. Эта таблица суммирует доступные параметры для выбора seed.

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

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

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

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

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

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

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

свернуть все

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

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

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

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

Больше о

свернуть все

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

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

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

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

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

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

    • Пакетное обновление — Присвоение каждое наблюдение к кластеру с самым близким центроидом.

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

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

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

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

k- ++ алгоритм

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

k - средние значения ++ алгоритм выбирает seed можно следующим образом, принимая, что количеством кластеров является 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 - средние значения ++ достигают более быстрой сходимости к более низкой сумме в кластере, точки суммы квадратов к кластерным центроидным расстояниям, чем алгоритм Lloyd's.

Алгоритмы

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

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

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

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

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

Ссылки

[1] Артур, Дэвид и Серджи Вэссильвитский. “K-средних значений ++: Преимущества Тщательного Отбора”. SODA ‘07: Продолжения Восемнадцатого Ежегодного Симпозиума ACM-SIAM по Дискретным Алгоритмам. 2007, стр 1027–1035.

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

[3] Seber, G. A. F. Многомерные наблюдения. Хобокен, NJ: John Wiley & Sons, Inc., 1984.

[4] Spath, H. Кластерное рассечение и анализ: теория, программы ФОРТРАНА, примеры. Переведенный Дж. Голдшмидтом. Нью-Йорк: нажатие Halsted, 1985.

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

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