Как построить дендрограмму в python

Кластерный анализ на Python

Замечательная книга «Программируем коллективный разум» вдохновила меня на написание этого поста по ее мотивам на тему кластерного анализа.

Возникло желание в одном посте рассмотреть кластерный анализ, его красивую реализацию на языке Python, и, особенно, визуальное представление кластеров – дендрограммы.

Код примера основан на коде примеров из книги.

Основная идея кластерного анализа – выделение среди множества данных групп, внутри которых элементы в определенной мере схожи. В рамках такого анализа, по сути, происходит определенная классификация исследуемых данных за счет распределения их по группам. Группы эти упорядочены иерархически и структуру получившихся после анализа кластеров можно представить в виде дерева – дендрограммы («дендро», как известно, по-гречески «дерево»).

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

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

Алгоритм построения кластеров, в принципе, прост и логичен.

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

Пример: элементы — блоги, 2 «координаты» — количество слов «php» и «xml» в содержимом блогов.
У блога №1 – 7 раз встречается слово «php» и 5 раз «xml». Тогда «координаты» блога №1 в пространстве количества этих слов — (7;5).
У блога №2 — 6 раз встречается слово «php» и 4 раза «xml». Тогда «координаты» блога №2 в пространстве количества этих слов — (6;4).
Схожесть определим с помощью функции — евклидова расстояния.
d(blog1, blog2) = sqrt( (7-6)^2 + (5-4)^2) = 1.414

На выходе мы получаем дерево из кластеров (иерархию кластеров).

Работает алгоритм так:
1) Шаг 1: Считать каждый элемент исходного списка кластером и добавить их в список объединения
2) Шаг 2 – N: Найти самые близкие кластеры и объединить их в новый («координаты» нового – полусумма «координат» объединяемых). Новый добавить в список объединения, а исходные кластеры – удалить из списка. Таким образом, на каждом шаге в списке объединения все меньше элементов.

Критерий останова: наличие в списке объединения лишь одного кластера, который уже не с чем объединять (получение одного, «корневого» кластера)

Реализует этот алгоритм функция hcluster:

1. def hcluster(rows,distance=pearson):
2. distances=<>
3. currentclustid=-1
4. # Clusters are initially just the rows
5. clust=[bicluster(rows[i],id=i) for i in range(len(rows))]
6. while len(clust)>1:
7. lowestpair=(0,1)
8. closest=distance(clust[0].vec,clust[1].vec)
9. # loop through every pair looking for the smallest distance
10. for i in range(len(clust)):
11. for j in range(i+1,len(clust)):
12. # distances is the cache of distance calculations
13. if (clust[i].id,clust[j].id) not in distances:
14. distances[(clust[i].id,clust[j].id)]=distance(clust[i].vec,clust[j].vec)
15. d=distances[(clust[i].id,clust[j].id)]
16. if d<closest:
17. closest=d
18. lowestpair=(i,j)
19. # calculate the average of the two clusters
20. mergevec=[
21. (clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0
22. for i in range(len(clust[0].vec))]
23. # create the new cluster
24. newcluster=bicluster(mergevec,left=clust[lowestpair[0]],
25. right=clust[lowestpair[1]],
26. distance=closest,id=currentclustid)
27. # cluster ids that weren’t in the original set are negative
28. currentclustid-=1
29. del clust[lowestpair[1]]
30. del clust[lowestpair[0]]
31. clust.append(newcluster)
32. return clust[0]

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

Иерархическая кластеризация с помощью Python и Scikit-Learn

Иерархическая кластеризация-это тип неконтролируемого алгоритма машинного обучения, используемого для кластеризации немаркированных точек данных. Подобно K-means clustering , иерархическая кластеризация также группирует вместе точки данных с аналогичными характеристиками. В некоторых случаях результат иерархической кластеризации и кластеризации K-средних может быть сходным. Прежде чем реализовать иерархическую кластеризацию с помощью Scikit-Learn , давайте сначала разберемся в теории иерархической кластеризации.

Теория иерархической кластеризации

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

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

Шаги для выполнения иерархической кластеризации

Ниже приведены шаги, связанные с агломеративной кластеризацией:

1. Вначале рассматривайте каждую точку данных как один кластер. Таким образом, число кластеров в начале будет равно K, а K-целое число, представляющее количество точек данных.
2. Сформируйте кластер, соединив две ближайшие точки данных, в результате чего получатся кластеры K-1.
3. Сформируйте больше кластеров, соединив два ближайших кластера, что приведет к кластерам K-2.
4. Повторяйте описанные выше три шага, пока не образуется один большой кластер.
5. Как только один кластер сформирован, дендрограммы используются для разделения на несколько кластеров в зависимости от проблемы. Мы подробно рассмотрим концепцию дендрограммы в следующем разделе.

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

1. Измерьте расстояние между точками закрытия двух кластеров.
2. Измерьте расстояние между самыми дальними точками двух кластеров.
3. Измерьте расстояние между центроидами двух кластеров.
4. Измерьте расстояние между всеми возможными комбинациями точек между двумя кластерами и возьмите среднее.

Роль дендрограмм в иерархической кластеризации

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

Предположим, что у нас есть набор точек данных, представленных массивом numpy следующим образом:

Давайте построим график приведенных выше точек данных. Для этого выполните следующий код:

Приведенный выше скрипт рисует точки данных в массиве X | numpy и помечает точки данных от 1 до 10. На рисунке ниже вы увидите, что график, который генерируется из этого кода:

Давайте назовем вышеприведенный график графиком 1. Невооруженным глазом видно, что точки данных образуют два кластера: первый в левом нижнем углу, состоящий из точек 1-5, а второй в правом верхнем углу, состоящий из точек 6-10.

Однако в реальном мире мы можем иметь тысячи точек данных во многих более чем 2-х измерениях. В этом случае было бы невозможно обнаружить скопления невооруженным глазом. Именно поэтому были разработаны алгоритмы кластеризации.

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

Выходной график выглядит так, как показано ниже. Давайте назовем этот график Graph2.

Алгоритм начинается с нахождения двух ближайших друг к другу точек на основе евклидова расстояния. Если мы оглянемся на график 1, то увидим, что точки 2 и 3 находятся ближе всего друг к другу, а точки 7 и 8-ближе друг к другу. Поэтому сначала между этими двумя точками образуется кластер. На графике 2 вы можете видеть, что дендрограммы были созданы, соединяя точки 2 с 3 и 8 с 7. Вертикальная высота дендограммы показывает евклидовы расстояния между точками. Из графика 2 видно, что евклидово расстояние между точками 8 и 7 больше, чем расстояние между точками 2 и 3.

Следующий шаг состоит в том, чтобы присоединиться к кластеру, образованному путем присоединения двух точек к следующему ближайшему кластеру или точке, которая, в свою очередь, приводит к другому кластеру. Если посмотреть на график 1, то точка 4 ближе всего к кластеру точек 2 и 3, поэтому в графе 2 дендрограмма генерируется путем соединения точки 4 с дендрограммой точек 2 и 3. Этот процесс продолжается до тех пор, пока все точки не соединятся вместе, образуя один большой кластер.

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

Мы видим, что наибольшее вертикальное расстояние без какой-либо горизонтальной линии, проходящей через него, представлено синей линией. Таким образом, мы рисуем новую горизонтальную красную линию, которая проходит через синюю линию. Поскольку он пересекает синюю линию в двух точках, следовательно, число кластеров будет равно 2.

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

На приведенном выше графике горизонтальная линия проходит через четыре вертикальные линии, в результате чего образуются четыре кластера: кластер точек 6,7,8 и 10, кластер точек 3,2,4 и точки 9 и 5 будут рассматриваться как одноточечные кластеры.

Иерархическая кластеризация с помощью Scikit-Learn

Достаточно теории, теперь давайте реализуем иерархическую кластеризацию с помощью библиотеки Scikit-Learn Python.

Пример 1

В нашем первом примере мы будем кластер X | numpy массив точек данных, которые мы создали в предыдущем разделе.

Процесс кластеризации аналогичен любому другому неконтролируемому алгоритму машинного обучения. Начнем с импорта необходимых библиотек:

Следующим шагом является импорт или создание набора данных. В этом примере мы будем использовать следующие данные:

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

Взгляните на следующий сценарий:

В приведенном выше коде мы импортируем класс Agglomerative Clustering из библиотеки “sklearn.cluster”. Число параметров устанавливается равным 2 с помощью параметра n_clusters , а affinity – “евклидово” (расстояние между точками данных). Наконец, параметр linkage имеет значение “ward”, что минимизирует вариант между кластерами.

Далее мы вызываем метод fit_predict из Агломеративной кластеризации переменной класса cluster . Этот метод возвращает имена кластеров, к которым принадлежит каждая точка данных. Выполните следующий сценарий, чтобы увидеть, как были кластеризованы точки данных.

Выход представляет собой одномерный массив из 10 элементов, соответствующих кластерам, назначенным нашим 10 точкам данных.

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

Наконец, давайте построим наши кластеры. Для этого выполните следующий код:

Вы можете видеть точки в двух кластерах, где первые пять точек сгруппированы вместе, а последние пять точек сгруппированы вместе.

Пример 2

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

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

Набор данных для этой задачи можно загрузить по следующей ссылке:

Набор данных для этой задачи можно загрузить по следующей ссылке:

Поместите загруженный файл “shopping-data.csv” в папку “Datasets” каталога “D”. Чтобы сгруппировать эти данные в группы, мы выполним те же действия, что и в предыдущем разделе.

Выполните следующий сценарий для импорта нужных библиотек:

Затем, чтобы импортировать набор данных для этого примера, выполните следующий код:

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

Приведенный выше скрипт вернет (200, 5) , что означает, что набор данных содержит 200 записей и 5 атрибутов.

Чтобы просмотреть набор данных, выполните функцию head() фрейма данных. Взгляните на следующий сценарий:

Результат будет выглядеть следующим образом:

19	Мужчина	1	0	15	39
21	Мужчина	2	1	15	81
20	Женский	3	2	16	6
23	Женский	4	3	16	77
31	Женский	5	4	17	40

Наш набор данных состоит из пяти столбцов: CustomerID, Жанр, Возраст, Годовой доход и Оценка расходов. Для просмотра результатов в двумерном пространстве признаков мы сохраним только два из этих пяти столбцов. Мы можем удалить столбец CustomerID, Жанр и Возраст. Мы сохраним столбцы Годовой доход (в тысячах долларов) и Оценка расходов (1-100). Столбец “Оценка расходов” показывает, как часто человек тратит деньги в торговом центре по шкале от 1 до 100, причем 100-это самый высокий показатель траты. Выполните следующий сценарий, чтобы отфильтровать первые три столбца из нашего набора данных:

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

В приведенном выше скрипте мы импортируем класс иерархии библиотеки scipy.cluster как shc . Класс иерархии имеет метод dendrogram , который принимает значение, возвращаемое методом linkage того же класса. Метод linkage принимает набор данных и метод минимизации расстояний в качестве параметров. Мы используем “ward” в качестве метода , поскольку он минимизирует варианты расстояний между кластерами.

Вывод приведенного выше скрипта выглядит следующим образом:

Если мы нарисуем горизонтальную линию, которая проходит через самое длинное расстояние без горизонтальной линии, мы получим 5 кластеров, как показано на следующем рисунке:

Теперь, когда мы знаем количество кластеров для нашего набора данных, следующий шаг-сгруппировать точки данных в эти пять кластеров. Для этого мы снова будем использовать класс Agglomerative Clustering библиотеки sklearn.cluster . Взгляните на следующий сценарий:

Вывод приведенного выше скрипта выглядит следующим образом:

Вы можете видеть метки кластеров из всех ваших точек данных. Поскольку у нас было пять кластеров, у нас есть пять меток на выходе, то есть от 0 до 4.

В качестве заключительного шага давайте построим кластеры, чтобы увидеть, как на самом деле наши данные были кластеризованы:

Вывод приведенного выше кода выглядит следующим образом:

Вы можете видеть точки данных в виде пяти кластеров. Точки данных в правом нижнем углу принадлежат клиентам с высокими зарплатами, но низкими расходами. Это те клиенты, которые тщательно тратят свои деньги. Точно так же клиенты в правом верхнем углу (зеленые точки данных) – это клиенты с высокими зарплатами и высокими расходами. Это тип клиентов, на которых ориентируются компании. Клиенты в середине (синие точки данных) – это те, у кого средний доход и средняя зарплата. К этой категории относится наибольшее количество клиентов. Компании также могут ориентироваться на этих клиентов, учитывая тот факт, что их огромное количество и т. Д.

Ресурсы

Между всеми различными пакетами Python ( pandas , matplotlib , numpy и sklearn ) в этой статье есть много информации , которую может быть трудно понять, и по этой причине мы рекомендуем проверить некоторые более подробные ресурсы по выполнению задач data science с помощью Python, такие как онлайн-курс:

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

Вывод

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

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

Dendrograms in Python

Plotly is a free and open-source graphing library for Python. We recommend you read our Getting Started guide for the latest installation or upgrade instructions, then move on to our Plotly Fundamentals tutorials or dive straight in to some Basic Charts tutorials.

Basic Dendrogram¶

A dendrogram is a diagram representing a tree. The figure factory called create_dendrogram performs hierarchical clustering on data and represents the resulting tree. Values on the tree depth axis correspond to distances between clusters.

Dendrogram plots are commonly used in computational biology to show the clustering of genes or samples, sometimes in the margin of heatmaps.

Set Color Threshold¶

Set Orientation and Add Labels¶

Plot a Dendrogram with a Heatmap¶

Reference¶

For more info on ff.create_dendrogram() , see the full function reference

What About Dash?¶

Dash is an open-source framework for building analytical applications, with no Javascript required, and it is tightly integrated with the Plotly graphing library.

scipy.cluster.hierarchy.dendrogram#

The dendrogram illustrates how each cluster is composed by drawing a U-shaped link between a non-singleton cluster and its children. The top of the U-link indicates a cluster merge. The two legs of the U-link indicate which clusters were merged. The length of the two legs of the U-link represents the distance between the child clusters. It is also the cophenetic distance between original observations in the two children clusters.

Parameters : Z ndarray

The linkage matrix encoding the hierarchical clustering to render as a dendrogram. See the linkage function for more information on the format of Z .

p int, optional

The p parameter for truncate_mode .

truncate_mode str, optional

The dendrogram can be hard to read when the original observation matrix from which the linkage is derived is large. Truncation is used to condense the dendrogram. There are several modes:

No truncation is performed (default). Note: ‘none’ is an alias for None that’s kept for backward compatibility.

The last p non-singleton clusters formed in the linkage are the only non-leaf nodes in the linkage; they correspond to rows Z[n-p-2:end] in Z . All other non-singleton clusters are contracted into leaf nodes.

No more than p levels of the dendrogram tree are displayed. A “level” includes all nodes with p merges from the final merge.

Note: ‘mtica’ is an alias for ‘level’ that’s kept for backward compatibility.

color_threshold double, optional

For brevity, let \(t\) be the color_threshold . Colors all the descendent links below a cluster node \(k\) the same color if \(k\) is the first node below the cut threshold \(t\) . All links connecting nodes with distances greater than or equal to the threshold are colored with de default matplotlib color ‘C0’ . If \(t\) is less than or equal to zero, all nodes are colored ‘C0’ . If color_threshold is None or ‘default’, corresponding with MATLAB(TM) behavior, the threshold is set to 0.7*max(Z[:,2]) .

get_leaves bool, optional

Includes a list R[‘leaves’]=H in the result dictionary. For each \(i\) , H[i] == j , cluster node j appears in position i in the left-to-right traversal of the leaves, where \(j < 2n-1\) and \(i < n\) .

orientation str, optional

The direction to plot the dendrogram, which can be any of the following strings:

Plots the root at the top, and plot descendent links going downwards. (default).

Plots the root at the bottom, and plot descendent links going upwards.

Plots the root at the left, and plot descendent links going right.

Plots the root at the right, and plot descendent links going left.

labels ndarray, optional

By default, labels is None so the index of the original observation is used to label the leaf nodes. Otherwise, this is an \(n\) -sized sequence, with n == Z.shape[0] + 1 . The labels[i] value is the text to put under the \(i\) th leaf node only if it corresponds to an original observation and not a non-singleton cluster.

count_sort str or bool, optional

For each node n, the order (visually, from left-to-right) n’s two descendent links are plotted is determined by this parameter, which can be any of the following values:

Nothing is done.

‘ascending’ or True

The child with the minimum number of original objects in its cluster is plotted first.

The child with the maximum number of original objects in its cluster is plotted first.

Note, distance_sort and count_sort cannot both be True.

distance_sort str or bool, optional

For each node n, the order (visually, from left-to-right) n’s two descendent links are plotted is determined by this parameter, which can be any of the following values:

Nothing is done.

‘ascending’ or True

The child with the minimum distance between its direct descendents is plotted first.

The child with the maximum distance between its direct descendents is plotted first.

Note distance_sort and count_sort cannot both be True.

show_leaf_counts bool, optional

When True, leaf nodes representing \(k>1\) original observation are labeled with the number of observations they contain in parentheses.

no_plot bool, optional

When True, the final rendering is not performed. This is useful if only the data structures computed for the rendering are needed or if matplotlib is not available.

no_labels bool, optional

When True, no labels appear next to the leaf nodes in the rendering of the dendrogram.

leaf_rotation double, optional

Specifies the angle (in degrees) to rotate the leaf labels. When unspecified, the rotation is based on the number of nodes in the dendrogram (default is 0).

leaf_font_size int, optional

Specifies the font size (in points) of the leaf labels. When unspecified, the size based on the number of nodes in the dendrogram.

leaf_label_func lambda or function, optional

When leaf_label_func is a callable function, for each leaf with cluster index \(k < 2n-1\) . The function is expected to return a string with the label for the leaf.

Indices \(k < n\) correspond to original observations while indices \(k \geq n\) correspond to non-singleton clusters.

For example, to label singletons with their node id and non-singletons with their id, count, and inconsistency coefficient, simply do:

When True the heights of non-singleton nodes contracted into a leaf node are plotted as crosses along the link connecting that leaf node. This really is only useful when truncation is used (see truncate_mode parameter).

link_color_func callable, optional

If given, link_color_function is called with each non-singleton id corresponding to each U-shaped link it will paint. The function is expected to return the color to paint the link, encoded as a matplotlib color string code. For example:

colors the direct links below each untruncated non-singleton node k using colors[k] .

ax matplotlib Axes instance, optional

If None and no_plot is not True, the dendrogram will be plotted on the current axes. Otherwise if no_plot is not True the dendrogram will be plotted on the given Axes instance. This can be useful if the dendrogram is part of a more complex figure.

above_threshold_color str, optional

This matplotlib color string sets the color of the links above the color_threshold. The default is ‘C0’ .

Returns : R dict

A dictionary of data structures computed to render the dendrogram. Its has the following keys:

A list of color names. The k’th element represents the color of the k’th link.

‘icoord’ and ‘dcoord’

Each of them is a list of lists. Let icoord = [I1, I2, . Ip] where Ik = [xk1, xk2, xk3, xk4] and dcoord = [D1, D2, . Dp] where Dk = [yk1, yk2, yk3, yk4] , then the k’th link painted is (xk1, yk1) — (xk2, yk2) — (xk3, yk3) — (xk4, yk4) .

A list of labels corresponding to the leaf nodes.

For each i, H[i] == j , cluster node j appears in position i in the left-to-right traversal of the leaves, where \(j < 2n-1\) and \(i < n\) . If j is less than n , the i -th leaf node corresponds to an original observation. Otherwise, it corresponds to a non-singleton cluster.

A list of color names. The k’th element represents the color of the k’th leaf.

It is expected that the distances in Z[:,2] be monotonic, otherwise crossings appear in the dendrogram.

A very basic example:

Now, plot in given axes, improve the color scheme and use both vertical and horizontal orientations: