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

Statistics and Machine Learning Toolbox включает функции для выполнения кластеризации K-средних значений и иерархической кластеризации.

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

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

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

rng(6,'twister')

Данные ИРИС Фишера

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

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

Кластеризация данных ириса Фишера с помощью K-средних значений

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

Во-первых, загрузите данные и вызовите 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. Три точки из нижнего кластера (нанесенные треугольниками) очень близки к точкам из верхнего кластера (нанесены квадратами). Поскольку верхний кластер так расширен, эти три точки ближе к центроиду нижнего кластера, чем к центроиду верхнего кластера, даже если точки отделены от основной части точек в их собственном кластере разрывом. Поскольку 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 запускает процесс кластеризации с помощью случайным образом выбранного набора начальных местоположений центроида. The 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-средних значений произвела один раздел данных радужной оболочки глаза, но можно также захотеть исследовать различные шкалы группировок в данных. Иерархическая кластеризация позволяет вам сделать именно это, создав иерархическое дерево кластеров.

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

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-средних значений: существует две большие, отдельные группы наблюдений. В каждой из этих двух групп можно увидеть, что более низкие уровни групп появляются, так как вы рассматриваете меньшие и меньшие шкалы на расстоянии. Существует много различных уровней групп, разных размеров и в разных степенях отличия.

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

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-средних значений. Используя иерархию от косинусоидного расстояния для создания кластеров, задайте высоту редактирования, которая будет срезать дерево ниже трех самых высоких узлов, и создайте четыре кластера, затем постройте график кластеризованных необработанных данных.

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

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

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