kmeans
k- кластеризация
Синтаксис
Описание
idx = kmeans(X,k)X в k кластеры, и возвращают n-by-1 вектор (idx) содержа кластерные индексы каждого наблюдения. Строки X соответствуйте точкам, и столбцы соответствуют переменным.
По умолчанию, kmeans использует Евклидову метрику расстояния в квадрате и k - средние значения ++ алгоритм для кластерной центральной инициализации.
idx = kmeans(X,k,Name,Value)Name,Value парные аргументы.
Например, задайте расстояние косинуса, число раз, чтобы повторить кластеризацию с помощью новых начальных значений или использовать параллельные вычисления.
Примеры
Обучите k-средних значений, Кластеризирующих Алгоритм
Кластерные данные с помощью кластеризации 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 вектор предсказанных кластерных индексов, соответствующих наблюдениям в 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 centroidkmeans выводит предупреждение, утверждая, что алгоритм не сходился, который необходимо ожидать, поскольку программное обеспечение только реализовало одну итерацию.
Постройте кластерные области.
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 timerElapsed time is 61.915955 seconds.
Командное окно указывает, что шесть рабочих доступны. Количество рабочих может варьироваться в вашей системе. Командное окно отображает количество итераций, и терминальное значение целевой функции для каждого реплицируют. Выходные аргументы содержат результаты, реплицируют 9, потому что это имеет самую низкую полную сумму расстояний.
Присвойте новые данные существующим кластерам и сгенерируйте код C/C++
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).
Входные параметры
Выходные аргументы
Больше о
Алгоритмы
kmeansиспользует двухфазный итеративный алгоритм, чтобы минимизировать сумму расстояний точки к центроиду, суммированных по всемуkкластеры.Эта первая фаза использует batch updates, где каждая итерация состоит из переприсвоения точек к их самому близкому кластерному центроиду, целиком, сопровождаемый перерасчетом кластерных центроидов. Эта фаза иногда не сходится к решению, которое является локальным минимумом. Таким образом, раздел данных, где перемещение любой одной точки к различному кластеру увеличивает полную сумму расстояний. Это более вероятно для небольших наборов данных. Пакетная фаза быстра, но потенциально только аппроксимирует решение как начальную точку для второй фазы.
Эта вторая фаза использует online updates, где точки индивидуально повторно присвоены, если выполнение так уменьшает сумму расстояний, и кластерные центроиды повторно вычисляются после каждого переназначения. Каждая итерация во время этой фазы состоит из одной передачи хотя все точки. Эта фаза сходится к локальному минимуму, несмотря на то, что могут быть другие локальные минимумы с более низкой полной суммой расстояний. В общем случае нахождение глобального минимума решено исчерпывающим выбором начальных точек, но использование нескольких реплицирует со случайными начальными точками, обычно приводит к решению, которое является глобальным минимумом.
Если
Replicates= r> 1 иStartplus(значение по умолчанию), затем программное обеспечение выбирает 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.
Расширенные возможности
Смотрите также
clusterdata | gmdistribution | kmedoids | linkage | parpool | silhouette | statset