kmeans

Синтаксис

idx = kmeans(X,k)
idx = kmeans(X,k,Name,Value)
[idx,C] = kmeans(___)
[idx,C,sumd] = kmeans(___)
[idx,C,sumd,D] = 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-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)';

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

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

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

kmeans использует k-средние-значения ++ алгоритм для центроидной инициализации и придает Евклидову расстоянию квадратную форму по умолчанию. Это - хорошая практика, чтобы искать более низкие, локальные минимумы путем установки аргумента пары "имя-значение" 'Replicates'.

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;

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

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. Поскольку 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 матрица данных, независимо от ее ориентации.

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

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

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

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

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (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)=(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'

Объектный массив 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 и явным образом создайте параллельный пул прежде, чем вызов 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', числовой матрицы или числового массива. Эта таблица суммирует доступные параметры для выбора seed.

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

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

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

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

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

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

Примечание

Программное обеспечение обрабатывает NaN s как недостающие данные и удаляет любую строку X, содержащего по крайней мере один NaN. Удаление строк X уменьшает объем выборки.

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

свернуть все

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

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

Суммы в кластере расстояний точки к центроиду, возвращенных как числовой вектор-столбец. sumd является k-by-1 вектор, где элемент j является суммой расстояний точки к центроиду в кластерном j.

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

Больше о

свернуть все

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

Для просмотра документации необходимо авторизоваться на сайте