K-средства и иерархическая кластеризация

Инструментарий статистики и машинного обучения включает функции для кластеризации K-средств и иерархической кластеризации.

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

Иерархическая кластеризация - это способ исследовать группирование данных одновременно в различных масштабах расстояния путем создания дерева кластера. Дерево не является единственным набором кластеров, как в K-Means, а скорее многоуровневой иерархией, где кластеры на одном уровне соединяются как кластеры на следующем более высоком уровне. Это позволяет определить, какой масштаб или уровень кластеризации наиболее подходит для приложения.

Некоторые функции, используемые в этом примере, вызывают встроенные функции генерации случайных чисел MATLAB ®. Для дублирования точных результатов, показанных в этом примере, необходимо выполнить приведенную ниже команду, чтобы установить генератор случайных чисел в известное состояние. Если состояние не задано, результаты могут отличаться тривиальными способами, например, кластеры могут быть пронумерованы в другом порядке. Существует также вероятность того, что в результате может получиться неоптимальное кластерное решение (пример включает обсуждение неоптимальных решений, включая способы их предотвращения).

rng(6,'twister')

Данные Айрис Фишера

В 1920-х годах ботаники собрали измерения длины чашелистика, ширины чашелистика, длины лепестка и ширины лепестка 150 экземпляров радужки, по 50 от каждого из трёх видов. Измерения стали известны как набор данных радужки Фишера.

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

Кластеризация данных Iris Фишера с использованием кластеризации K-Means

Функция kmeans выполняет кластеризацию K-Means, используя итеративный алгоритм, который назначает объекты кластерам так, чтобы сумма расстояний от каждого объекта до его центроида кластера, по всем кластерам, была минимальной. Используя данные радужки Фишера, он найдет естественные группировки среди образцов радужки, основываясь на измерениях их чашелистики и лепестков. При кластеризации K-means необходимо указать количество кластеров, которые требуется создать.

Сначала загрузите данные и вызовите kmeans с требуемым числом кластеров, равным 2, и используя квадрат евклидова расстояния. Чтобы получить представление о том, насколько хорошо разделены полученные кластеры, можно сделать силуэтный график. График силуэта показывает меру того, насколько близка каждая точка в одном кластере к точкам в соседних кластерах.

load fisheriris
[cidx2,cmeans2] = kmeans(meas,2,'dist','sqeuclidean');
[silh2,h] = silhouette(meas,cidx2,'sqeuclidean');

Из силуэтного графика видно, что большинство точек в обоих кластерах имеют большое значение силуэта, большее 0,8, указывающее на то, что эти точки хорошо отделены от соседних кластеров. Однако каждый кластер также содержит несколько точек с низкими значениями силуэта, указывая, что они находятся рядом с точками из других кластеров.

Оказывается, что четвёртое измерение в этих данных, ширина лепестка, сильно коррелирует с третьим измерением, длиной лепестка, и поэтому 3-D график первых трёх измерений даёт хорошее представление данных, не прибегая к четырём измерениям. При печати данных используются различные символы для каждого кластера, созданного kmeansможно определить точки с небольшими значениями силуэта как точки, близкие к точкам из других кластеров.

ptsymb = {'bs','r^','md','go','c+'};
for i = 1:2
    clust = find(cidx2==i);
    plot3(meas(clust,1),meas(clust,2),meas(clust,3),ptsymb{i});
    hold on
end
plot3(cmeans2(:,1),cmeans2(:,2),cmeans2(:,3),'ko');
plot3(cmeans2(:,1),cmeans2(:,2),cmeans2(:,3),'kx');
hold off
xlabel('Sepal Length');
ylabel('Sepal Width');
zlabel('Petal Length');
view(-137,10);
grid on

Центроиды каждого кластера строятся с использованием окружных X's. Три точки из нижнего скопления (нанесены треугольниками) очень близки к точкам из верхнего скопления (нанесены квадратами). Поскольку верхний кластер так разбросан, эти три точки ближе к центроиду нижнего кластера, чем к центроиду верхнего кластера, даже если точки отделены от основной части точек в их собственном кластере промежутком. Поскольку кластеризация K-средств учитывает только расстояния, а не плотности, такой результат может иметь место.

Можно увеличить число кластеров, чтобы увидеть, kmeans может найти дополнительную структуру группирования в данных. На этот раз используйте опциональный 'Display' аргумент пары имя-значение для печати информации о каждой итерации в алгоритме кластеризации.

[cidx3,cmeans3] = kmeans(meas,3,'Display','iter');

  iter	 phase	     num	         sum
     1	     1	     150	     146.424
     2	     1	       5	     144.333
     3	     1	       4	     143.924
     4	     1	       3	      143.61
     5	     1	       1	     143.542
     6	     1	       2	     143.414
     7	     1	       2	     143.023
     8	     1	       2	     142.823
     9	     1	       1	     142.786
    10	     1	       1	     142.754
Best total sum of distances = 142.754

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

По умолчанию kmeans начинает процесс кластеризации с использованием случайно выбранного набора начальных местоположений центроидов. kmeans алгоритм может сходиться к решению, которое является локальным минимумом; то есть kmeans может разделять данные таким образом, что перемещение любой отдельной точки в другой кластер увеличивает общую сумму расстояний. Однако, как и во многих других типах численных минимизаций, решение заключается в том, что kmeans достижения иногда зависят от исходных точек. Поэтому для данных могут существовать другие решения (локальные минимумы), которые имеют меньшую общую сумму расстояний. Вы можете использовать дополнительный 'Replicates' аргумент пары имя-значение для проверки различных решений. При указании нескольких копий kmeans повторяет процесс кластеризации, начиная с различных случайно выбранных центроидов для каждой копии. kmeans затем возвращает решение с наименьшей общей суммой расстояний между всеми репликациями.

[cidx3,cmeans3,sumd3] = kmeans(meas,3,'replicates',5,'display','final');

Replicate 1, 9 iterations, total sum of distances = 78.8557.
Replicate 2, 10 iterations, total sum of distances = 78.8557.
Replicate 3, 8 iterations, total sum of distances = 78.8557.
Replicate 4, 8 iterations, total sum of distances = 78.8557.
Replicate 5, 1 iterations, total sum of distances = 78.8514.
Best total sum of distances = 78.8514

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

sum(sumd3)

ans =

   78.8514

График силуэта для этого решения из трех кластеров показывает, что существует один кластер, который хорошо разделен, но что два других кластера не очень отличаются.

[silh3,h] = silhouette(meas,cidx3,'sqeuclidean');

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

for i = 1:3
    clust = find(cidx3==i);
    plot3(meas(clust,1),meas(clust,2),meas(clust,3),ptsymb{i});
    hold on
end
plot3(cmeans3(:,1),cmeans3(:,2),cmeans3(:,3),'ko');
plot3(cmeans3(:,1),cmeans3(:,2),cmeans3(:,3),'kx');
hold off
xlabel('Sepal Length');
ylabel('Sepal Width');
zlabel('Petal Length');
view(-137,10);
grid on

Вы можете видеть, что kmeans разделил верхний кластер от двухкластерного решения, и эти два кластера находятся очень близко друг к другу. В зависимости от того, что вы собираетесь делать с этими данными после кластеризации, это решение из трех кластеров может быть более или менее полезным, чем предыдущее решение из двух кластеров. Первый выходной аргумент из silhouette содержит значения силуэта для каждой точки, которые можно использовать для количественного сравнения двух решений. Среднее значение силуэта было больше для двухкластерного решения, указывая, что это лучший ответ чисто с точки зрения создания отдельных кластеров.

[mean(silh2) mean(silh3)]

ans =

    0.8504    0.7357

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

[cidxCos,cmeansCos] = kmeans(meas,3,'dist','cos');

Из силуэтного графика эти кластеры, по-видимому, отделены лишь немного лучше, чем те, которые были найдены с использованием квадратного евклидова расстояния.

[silhCos,h] = silhouette(meas,cidxCos,'cos');
[mean(silh2) mean(silh3) mean(silhCos)]

ans =

    0.8504    0.7357    0.7491

Обратите внимание, что порядок кластеров отличается от предыдущего силуэтного графика. Это потому, что kmeans выбирает начальные назначения кластеров случайным образом.

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

for i = 1:3
    clust = find(cidxCos==i);
    plot3(meas(clust,1),meas(clust,2),meas(clust,3),ptsymb{i});
    hold on
end
hold off
xlabel('Sepal Length');
ylabel('Sepal Width');
zlabel('Petal Length');
view(-137,10);
grid on

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

lnsymb = {'b-','r-','m-'};
names = {'SL','SW','PL','PW'};
meas0 = meas ./ repmat(sqrt(sum(meas.^2,2)),1,4);
ymin = min(min(meas0));
ymax = max(max(meas0));
for i = 1:3
    subplot(1,3,i);
    plot(meas0(cidxCos==i,:)',lnsymb{i});
    hold on;
    plot(cmeansCos(i,:)','k-','LineWidth',2);
    hold off;
    title(sprintf('Cluster %d',i));
    xlim([.9, 4.1]);
    ylim([ymin, ymax]);
    h_gca = gca;
    h_gca.XTick = 1:4;
    h_gca.XTickLabel = names;
end

Из этого сюжета ясно, что экземпляры из каждого из трёх скоплений имеют отчётливо различные относительные размеры лепестков и чашелистиков в среднем. Первое скопление имеет лепестки, которые строго меньше их чашелистиков. Лепестки и чашелистики вторых двух кластеров перекрываются по размеру, однако лепестки из третьего кластера перекрываются больше, чем второго. Вы также можете видеть, что второй и третий кластеры включают некоторые экземпляры, которые очень похожи друг на друга.

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

subplot(1,1,1);
for i = 1:3
    clust = find(cidxCos==i);
    plot3(meas(clust,1),meas(clust,2),meas(clust,3),ptsymb{i});
    hold on
end
xlabel('Sepal Length');
ylabel('Sepal Width');
zlabel('Petal Length');
view(-137,10);
grid on
sidx = grp2idx(species);
miss = find(cidxCos ~= sidx);
plot3(meas(miss,1),meas(miss,2),meas(miss,3),'k*');
legend({'setosa','versicolor','virginica'});
hold off

Кластеризация данных Iris Фишера с использованием иерархической кластеризации

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

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

eucD = pdist(meas,'euclidean');
clustTreeEuc = linkage(eucD,'average');

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

cophenet(clustTreeEuc,eucD)

ans =

    0.8770

Для визуализации иерархии кластеров можно построить график дендрограммы.

[h,nodes] = dendrogram(clustTreeEuc,0);
h_gca = gca;
h_gca.TickDir = 'out';
h_gca.TickLength = [.002 0];
h_gca.XTickLabel = [];

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

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

cosD = pdist(meas,'cosine');
clustTreeCos = linkage(cosD,'average');
cophenet(clustTreeCos,cosD)

ans =

    0.9360

[h,nodes] = dendrogram(clustTreeCos,0);
h_gca = gca;
h_gca.TickDir = 'out';
h_gca.TickLength = [.002 0];
h_gca.XTickLabel = [];

Самый высокий уровень этого дерева разделяет экземпляры радужки на две очень разные группы. Дендрограмма показывает, что по отношению к косинусному расстоянию внутригрупповые различия значительно меньше по сравнению с межгрупповыми различиями, чем это было для евклидова расстояния. Это именно то, что вы ожидали бы для этих данных, так как расстояние косинуса вычисляет нулевое попарное расстояние для объектов, которые находятся в том же «направлении» от начала координат.

При 150 наблюдениях сюжет загромождён, но можно сделать упрощённую дендрограмму, отображающую не самые низкие уровни дерева.

[h,nodes] = dendrogram(clustTreeCos,12);

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

[sum(ismember(nodes,[11 12 9 10])) sum(ismember(nodes,[6 7 8])) ...
                  sum(ismember(nodes,[1 2 4 3])) sum(nodes==5)]

ans =

    54    46    49     1

Для многих целей дендрограмма может быть достаточным результатом. Тем не менее, вы можете пойти на один шаг дальше, и использовать cluster функция для разрезания дерева и явного разбиения наблюдений на конкретные кластеры, как в случае с K-Means. Используя иерархию от расстояния косинуса для создания кластеров, укажите высоту связи, которая будет резать дерево ниже трех самых высоких узлов, и создайте четыре кластера, а затем постройте график кластеризованных необработанных данных.

hidx = cluster(clustTreeCos,'criterion','distance','cutoff',.006);
for i = 1:5
    clust = find(hidx==i);
    plot3(meas(clust,1),meas(clust,2),meas(clust,3),ptsymb{i});
    hold on
end
hold off
xlabel('Sepal Length');
ylabel('Sepal Width');
zlabel('Petal Length');
view(-137,10);
grid on

Этот график показывает, что результаты иерархической кластеризации с косинусным расстоянием качественно похожи на результаты K-Means, используя три кластера. Однако создание иерархического дерева кластера позволяет одновременно визуализировать то, что потребовало бы значительных экспериментов с различными значениями для K в кластеризации K-Means.

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

clustTreeSng = linkage(eucD,'single');
[h,nodes] = dendrogram(clustTreeSng,0);
h_gca = gca;
h_gca.TickDir = 'out';
h_gca.TickLength = [.002 0];
h_gca.XTickLabel = [];