Exponenta Banner
exponenta event banner

связь

Агломерирующее иерархическое дерево кластера

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

Синтаксис

Z = связь (X)
Z = связь (X, метод)
Z = связь (X, метод, метрика)
Z = связь (X, метод, метрика, 'savememory', значение)
Z = связь (X,method,pdist_inputs)
Z = связь (y)
Z = связь (y, метод)

Описание

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, в котором описывается, как измерять расстояние между кластерами.

Примеры

свернуть все

Открыть сценарий в реальном времени

Случайная генерация данных выборки с 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)

Figure contains an axes. The axes contains an object of type scatter.

cluster определяет четыре группы в данных.

Открыть сценарий в реальном времени

Найдите максимум три кластера в 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)

Figure contains an axes. The axes contains 29 objects of type line.

Отображение последних двух строк 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
Открыть сценарий в реальном времени

Загрузить 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.

Открыть сценарий в реальном времени

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

Взять матрицу разнородности 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)

Figure contains an axes. The axes contains 3 objects of type line.

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

свернуть все

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

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

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

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

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

'centroid'

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

'complete'

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

'median'

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

'single'

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

'ward'

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

'weighted'

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

Дополнительные сведения об этих методах см. в разделе Связи.

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

СтоимостьОписание
'euclidean'

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

'squaredeuclidean'

Квадрат евклидова расстояния. (Этот вариант предусмотрен только для эффективности. Он не удовлетворяет неравенству треугольника.)

'seuclidean'

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

'mahalanobis'

Расстояние Махаланобиса с использованием ковариации образца X, C = cov(X,'omitrows'). Использовать DistParameter чтобы указать другое значение для C, где матрица C является симметричным и положительным определенным.

'cityblock'

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

'minkowski'

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

'chebychev'

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

'cosine'

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

'correlation'

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

'hamming'

Расстояние хэмминга, которое представляет собой процент различающихся координат.

'jaccard'

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

'spearman'

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

@distfun

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

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

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

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

  • D2 является m2около-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 потребность в памяти пропорциональна N2, где N - количество наблюдений. Наилучшая (наименьшая) настройка для использования value зависит от размеров проблемы, количества наблюдений и доступной памяти. Дефолт value параметр представляет собой приблизительное приближение оптимального параметра.

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

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

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

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

  • Расстояния, расположенные в порядке (2,1), (3,1),..., (м, 1), (3,2),..., (м, 2),..., (м, м - 1)

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

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

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

свернуть все

Агломерирующее иерархическое дерево кластера, возвращаемое в виде числовой матрицы. Z - матрица (m-1) -by-3, где m - количество наблюдений в исходных данных. Столбцы 1 и 2 изZ содержат индексы кластера, связанные парами для формирования двоичного дерева. Листовые узлы пронумерованы от 1 до м. Листовые узлы - это одиночные кластеры, из которых построены все высшие кластеры. Каждый вновь сформированный кластер, соответствующий строке 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.

  • nr - количество объектов в кластере r.

  • xri - i-й объект в кластере r.

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

    d (r, s) = мин (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 _ fs - центроиды кластеров 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 вычисляют коэффициент кофенетической корреляции.

См. также

| | | | | | | |

Темы

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

Документация по инструментам для статистического и машинного обучения

Поддержка