Exponenta Banner
exponenta event banner

связь

Агломерационное иерархическое кластерное дерево

свернуть все на странице

Синтаксис

Z = linkage(X)
Z = linkage(X,method)
Z = linkage(X,method,metric)
Z = linkage(X,method,metric,'savememory',value)
Z = linkage(X,method,pdist_inputs)
Z = linkage(y)
Z = linkage(y,method)

Описание

Z = linkage(X) возвращает матричный Z, который кодирует дерево, содержащее иерархические кластеры строк матрицы входных данных X.

пример

Z = linkage(X,method) создает дерево с помощью заданного method, который описывает, как измерить расстояние между кластерами. Для получения дополнительной информации смотрите Связи.

пример

Z = linkage(X,method,metric) выполняет кластеризацию путем передачи metric функции pdist, которая вычисляет расстояние между строками X.

пример

Z = linkage(X,method,metric,'savememory',value) использует сохраняющий память алгоритм, когда value является 'on' и использует стандартный алгоритм, когда value является 'off'.

пример

Z = linkage(X,method,pdist_inputs) pdist_inputs передач к функции pdist, которая вычисляет расстояние между строками X. Аргумент pdist_inputs состоит из 'seuclidean', 'minkowski', или метрики 'mahalanobis' и дополнительной метрической опции расстояния.

Z = linkage(y) использует векторное представление y матрицы расстояния. y или вычисляется pdist или является более общей матрицей несходства, соответствующей выходному формату pdist.

пример

Z = linkage(y,method) создает дерево с помощью заданного method, который описывает, как измерить расстояние между кластерами.

Примеры

свернуть все

Скрипт Open Live Script

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

rng('default') % For reproducibility
X = rand(20000,3);

Создайте иерархическое кластерное дерево с помощью метода связи ward. В этом случае опция 'SaveMemory' функции clusterdata установлена в 'on' по умолчанию. В целом задайте оптимальное значение для 'SaveMemory' на основе размерностей X и доступной памяти.

Z = linkage(X,'ward');

Кластеризируйте данные максимум в четырех групп и постройте результат.

c = cluster(Z,'Maxclust',4);
scatter3(X(:,1),X(:,2),X(:,3),10,c)

cluster идентифицирует четыре группы в данных.

Скрипт Open Live Script

Найдите максимум трех кластеров в наборе данных fisheriris и сравните кластерные присвоения цветов к их известной классификации.

Загрузите выборочные данные.

load fisheriris

Создайте иерархическое кластерное дерево с помощью метода 'average' и метрики 'chebychev'.

Z = linkage(meas,'average','chebychev');

Найдите максимум трех кластеров в данных.

T = cluster(Z,'maxclust',3);

Создайте график древовидной схемы Z. Чтобы видеть эти три кластера, используйте 'ColorThreshold' с сокращением на полпути между третьими последними и предпредпоследними связями.

cutoff = median([Z(end-2,3) Z(end-1,3)]);
dendrogram(Z,'ColorThreshold',cutoff)

Отобразите последние две строки Z, чтобы видеть, как эти три кластера объединены в один. linkage комбинирует 293-й (синий) кластер с 297-м (красным) кластером, чтобы сформировать 298-й кластер со связью 1.7583. linkage затем комбинирует 296-й (зеленый) кластер с 298-м кластером.

lastTwo = Z(end-1:end,:)
lastTwo = 2×3

  293.0000  297.0000    1.7583
  296.0000  298.0000    3.4445

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

crosstab(T,species)
ans = 3×3

     0     0    10
     0    50    40
    50     0     0
Скрипт Open Live Script

Загрузите набор данных examgrades.

load examgrades

Создайте иерархическое дерево с помощью linkage. Используйте метод 'single' и метрику Минковскего с экспонентой 3.

Z = linkage(grades,'single',{'minkowski',3});

Наблюдайте 25-й шаг кластеризации.

Z(25,:)
ans = 1×3

   86.0000  137.0000    4.5307

linkage комбинирует 86-е наблюдение и 137-й кластер, чтобы сформировать кластер индекса 120+25=145, где 120 общее количество наблюдений в grades, и 25 номер строки в Z. Кратчайшим расстоянием между 86-м наблюдением и любой из точек в 137-м кластере является 4.5307.

Скрипт Open Live Script

Создайте агломерационное иерархическое кластерное дерево с помощью матрицы несходства.

Возьмите матрицу несходства X и преобразуйте его в векторную форму, которую linkage принимает при помощи squareform.

X = [0 1 2 3; 1 0 4 5; 2 4 0 6; 3 5 6 0];
y = squareform(X);

Создайте кластерное дерево с помощью linkage с методом 'complete' вычисления расстояния между кластерами. Первые два столбца Z показывают, как linkage комбинирует кластеры. Третий столбец Z дает расстояние между кластерами.

Z = linkage(y,'complete')
Z = 3×3

     1     2     1
     3     5     4
     4     6     6

Создайте график древовидной схемы Z. Ось X соответствует вершинам дерева, и ось Y соответствует расстояниям связи между кластерами.

dendrogram(Z)

Входные параметры

свернуть все

Входные данные, заданные как числовая матрица с двумя или больше строками. Строки представляют наблюдения, и столбцы представляют категории или размерности.

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

Алгоритм для вычисления расстояния между кластерами, заданными как одно из значений в этой таблице.

МетодОписание
'average'

Невзвешенное среднее расстояние (UPGMA)

'centroid'

Центроидное расстояние (UPGMC), подходящий для Евклидовых расстояний только

'complete'

Самое дальнее расстояние

'median'

Взвешенный центр массового расстояния (WPGMC), подходящий для Евклидовых расстояний только

'single'

Кратчайшее расстояние

'ward'

Внутренний квадрат расстояния (минимальный алгоритм отклонения), подходящий для Евклидовых расстояний только

'weighted'

Средневзвешенное расстояние (WPGMA)

Для получения дополнительной информации об этих методах смотрите Связи.

Метрика расстояния, заданная как любая метрика, принята функцией pdist. Эти метрики описаны в следующей таблице.

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

Евклидово расстояние (значение по умолчанию).

'squaredeuclidean'

Придал Евклидову расстоянию квадратную форму. (Эта возможность предоставляется для эффективности только. Это не удовлетворяет треугольное неравенство.)

'seuclidean'

Стандартизированное Евклидово расстояние. Каждое координатное различие между наблюдениями масштабируется путем деления на соответствующий элемент стандартного отклонения, S = nanstd(X). Используйте DistParameter, чтобы задать другое значение для S.

'mahalanobis'

Расстояние Mahalanobis с помощью выборочной ковариации X, C = nancov(X). Используйте DistParameter, чтобы задать другое значение для C, где матричный C симметричен и положительный определенный.

'cityblock'

Расстояние городского квартала.

'minkowski'

Расстояние Минковскего. Экспонента по умолчанию равняется 2. Используйте DistParameter, чтобы задать различную экспоненту P, где P является значением положительной скалярной величины экспоненты.

'chebychev'

Расстояние Чебычева (максимум координируют различие).

'cosine'

Один минус косинус включенного угла между точками (обработанный как векторы).

'correlation'

Один минус корреляция выборки между точками (обработанный как последовательности значений).

'hamming'

Расстояние Хемминга, которое является процентом координат, которые отличаются.

'jaccard'

Один минус коэффициент Jaccard, который является процентом ненулевых координат, которые отличаются.

'spearman'

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

@distfun

Пользовательский указатель на функцию расстояния. Функция расстояния имеет форму

function D2 = distfun(ZI,ZJ)
% calculation of distance
...
где

  • ZI является 1-by-n вектор, содержащий одно наблюдение.

  • ZJ является m2-by-n матрица, содержащая несколько наблюдений. distfun должен принять матричный ZJ с произвольным числом наблюдений.

  • D2 является m2-by-1 вектор расстояний, и D2(k) является расстоянием между наблюдениями ZI и ZJ(k,:).

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

Для получения дополнительной информации смотрите Метрики Расстояния.

Используйте pdist_inputs вместо metric, чтобы задать дополнительный входной параметр DistParameter pdist для 'seuclidean', 'minkowski' или 'mahalanobis'.

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

Метрика расстояния и метрическая опция расстояния, заданная как массив ячеек пары, разделенной запятой, состоящей из этих двух входных параметров Distance и DistParameter функционального pdist. Этот аргумент допустим только для определения 'seuclidean', 'minkowski' или 'mahalanobis'.

Пример: {'minkowski',5}

Типы данных: cell

Отметьте для опции 'savememory', заданной или как 'on' или как 'off'. Установка 'on' заставляет linkage создавать кластеры, не вычисляя матрицу расстояния. Установка 'on' доступна только, когда method является 'centroid', 'median', или 'ward' и metric является 'euclidean'.

Когда value является 'on', время выполнения linkage пропорционально количеству размерностей (количество столбцов X). Когда value является 'off', требования к памяти linkage пропорциональны N 2, где N является количеством наблюдений. Лучшее (наименее разовый) устанавливающий, чтобы использовать для value зависит от проблемных размерностей, количества наблюдений и доступной памяти. Установка value по умолчанию является грубым приближением оптимальной установки.

Значением по умолчанию является 'on', когда X имеет 20 столбцов или меньше, или компьютер не имеет достаточной памяти, чтобы сохранить матрицу расстояния. В противном случае значением по умолчанию является 'off'.

Пример: 'savememory','on'

Расстояния, заданные как числовой вектор с тем же форматом как вывод функции pdist:

  • Вектор - строка из длины m (m – 1)/2, соответствуя парам наблюдений в матрице со строками m

  • Расстояния располагаются в порядке (2,1), (3,1)..., (m, 1), (3,2)..., (m, 2)..., (m, m – 1)),

y может быть более общей матрицей несходства, соответствующей выходному формату pdist.

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

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

свернуть все

Агломерационное иерархическое кластерное дерево, возвращенное как числовая матрица. Z (m – 1)-by-3 матрица, где m является количеством наблюдений в исходных данных. Столбцы 1 и 2 Z содержат кластерные индексы, соединенные в парах, чтобы сформировать двоичное дерево. Вершины пронумерованы от 1 до m. Вершины являются одноэлементными кластерами, из которых создаются все более высокие кластеры. Каждый недавно сформированный кластер, соответствуя строке Z(I,:), присвоен индекс m + I. Z(I,1) записей и Z(I,2) содержат индексы двух кластеров компонента, которые формируют кластерный m + I. m – 1 более высокий кластер соответствует внутренним узлам кластеризирующегося дерева. Z(I,3) содержит расстояние связи между этими двумя кластерами, объединенными в строке Z(I,:).

Например, рассмотрите создание дерева с 30 начальными узлами. Предположим, что кластер 5 и кластер 7 объединены на шаге 12, и что расстояние между ними на том шаге 1.5. Затем Z(12,:) является [5 7 1.5]. Недавно сформированный кластер имеет индекс 12 + 30 = 42. Если кластер 42 появляется в более поздней строке, то функция комбинирует кластер, созданный на шаге 12 в больший кластер.

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

Больше о

свернуть все

Связи

Связь является расстоянием между двумя кластерами.

Следующее обозначение описывает связи, используемые различными методами:

  • Кластерный r формируется из кластеров p и q.

  • n r является количеством объектов в кластерном r.

  • x ri является i th объект в кластерном r.

  • Одна связь, также названная самым близким соседом, использует наименьшее расстояние между объектами в этих двух кластерах.

    d(r,s)=min(dist(xri,xsj)),i∈(i,...,nr),j∈(1,...,ns)

  • Полная связь, также названная дальше всего, граничит, использует самое большое расстояние между объектами в этих двух кластерах.

    d(r,s)=max (dist(xri,xsj)),i∈(1,...,nr),j∈(1,...,ns)

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

    d(r,s)=1nrns∑i=1nr∑j=1nsdist(xri,xsj)

  • Центроидная связь использует Евклидово расстояние между центроидами этих двух кластеров.

    d(r,s)=‖x¯r−x¯s‖2,

    где

    x¯r=1nr∑i=1nrxri

  • Средняя связь использует Евклидово расстояние между взвешенными центроидами этих двух кластеров.

    d(r,s)=‖x˜r−x˜s‖2,

    где x˜r и x˜s взвешенные центроиды для кластеров r и s. Если кластерный r был создан путем объединения кластеров p и q, x˜r задан рекурсивно как

    x˜r=12(x˜p+x˜q)

  • Связь опеки использует инкрементную сумму квадратов, то есть, увеличение общей суммы квадратов в кластере в результате присоединения двух кластеров. Сумма квадратов в кластере задана как сумма квадратов расстояний между всеми объектами в кластере и центроиде кластера. Метрика суммы квадратов эквивалентна следующей метрике расстояния d (r, s), который является формулой использование linkage.

    d(r,s)=2nrns(nr+ns)‖x¯r−x¯s‖2,

    где

    • ‖‖2 Евклидово расстояние.

    • x¯r и x¯s центроиды кластеров r и s.

    • nr и ns являются числом элементов в кластерах r и s.

    В некоторых ссылках связь Уорда не использует фактор 2 умножающихся nrns. Функция linkage использует этот фактор так, чтобы расстояние между двумя одноэлементными кластерами совпало с Евклидовым расстоянием.

  • Средневзвешенная связь использует рекурсивное определение для расстояния между двумя кластерами. Если кластерный r был создан путем объединения кластеров, p и q, расстояние между r и другим кластерным s заданы как среднее значение расстояния между p и s и расстояния между q и s.

    d(r,s)=(d(p,s)+d(q,s))2

Советы

  • Вычисление linkage(y) может быть медленным, когда y является векторным представлением матрицы расстояния. Для 'centroid', 'median' и методов 'ward', linkage проверяет, является ли y Евклидовым расстоянием. Избегайте этой длительной проверки путем передачи в X вместо y.

  • 'centroid' и методы 'median' могут произвести кластерное дерево, которое не является монотонным. Этот результат происходит, когда расстояние от объединения двух кластеров, r и s, к третьему кластеру является меньше, чем расстояние между r и s. В этом случае, в древовидной схеме, чертившей с ориентацией по умолчанию, путь от листа до корневого узла делает некоторые нисходящие шаги. Чтобы избежать этого результата, используйте другой метод. Эти данные показывают немонотонное кластерное дерево.

    В этом случае к кластеру 1 и кластеру 3 соединяют в новый кластер, и расстояние между этим новым кластером и кластером 2 является меньше, чем расстояние между кластером 1 и кластером 3. Результатом является немонотонное дерево.

  • Можно предоставить вывод Z другим функциям включая dendrogram, чтобы отобразить дерево, cluster, чтобы присвоить точки кластерам, inconsistent, чтобы вычислить противоречивые меры и cophenet, чтобы вычислить cophenetic коэффициент корреляции.

Смотрите также

| | | | | | | |

Темы

Представлено до R2006a

Документация Statistics and Machine Learning Toolbox
Поддержка