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

[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

Кластеризация ирисовых данных Фишера Используя иерархическую кластеризацию

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

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

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

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

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 = [];