Иерархический алгоритм [Кластерный анализ и Python]

Наконец собрался написать о некоторых алгоритмах кластерного анализа и их реализации на Python. В большинстве своём это будет краткое описание алгоритма и разбор готового решения, без глубокого объяснения "что это и как работает". Как следствие, если Вы ещё не знакомы с теорией по кластерному анализу, лучше начать с неё (ссылки на хорошие источники будут предоставлены) иначе сложно будет понять зачём делается тот или иной шаг.

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

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

Для тех, кто не знаком с кластерным анализом вообще, посоветую следующие источники (гуглятся легко):

1. Воронцов К. В. Лекции по алгоритмам кластеризации и многомерного шкалирования.
2. Kaufman L., Rousseeuw P. J. Finding Groups in Data: An Introduction to Cluster Analysis. — John Wiley & Sons, 1990.
3. Jain A. K., Murty M. N., Flynn P. J. Data Clustering: A Review. (http://www.csee.umbc.edu/nicholas/clustering/p264-jain.pdf)
4. Нейский И. М. Классификация и сравнение методов кластеризации
5. Сегаран Т. Programming Collective Intelligence.
6. Kogan J., Nicholas C., Teboulle M. Clustering Large and High Dimensional data. (http://www.csee.umbc.edu/~nicholas/clustering/ )
7. J. C. Gower and G. J. S. Ross «Minimum Spanning Trees and Single Linkage Cluster Analysis»
8. Мандель И. Д. Кластерный анализ.
9. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008. (http://nlp.stanford.edu/IR-book/)

Итак, тема данного поста Иерархические алгоритмы кластерного анализа и их реализация на Python. Поехали =)

Теория
Иерархические алгоритмы (также называемые алгоритмами таксономии) разделяют на дивизивные (DIANA) и агломеративные (AGNES).

• Дивизимные или нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры.
• Агломеративные или восходящие алгоритмы, напротив, в начале работы помещают каждый объект в отдельный кластер, а затем объединяют сходные кластеры во все более крупные.

Результаты работы иерархических алгоритмов обычно представляются в виде графа, называемого дендрограммой. Для выделения кластеров её обрезают как виноградную кисть на определённом уровне (т.н. пороговом).

Практика

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

• Pycluster
• sciPy
• FastCluster

Для себя я выбрал sciPy, как старое и надёжное решение, несмотря на обещания FastCluster работать быстрее.

Заглянув в доку находим функции linkage(y[, method, metric]) и dendrogram(Z[, p, truncate_mode, ...]) реализующие сам алгоритм (с различными методами объединений кластеров) и отображение дендрограммы соответсвенно. Для рассчёта расстояния между кластерами нам также пригодится функция pdist(X[, metric, p, w, V, VI]).

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

import numpy as np

def get_data():
    """Возвращает списки идентификаторов объектов и матрицу значений"""
    source = [row.strip().split(';') for row in file('products.csv')]
    names = [row[ 0].decode('UTF-8') for row in source[1:]]
    data = [map(float, row[1:]) for row in source[1:]]
    return names, norm(data)

def norm(data):
    """Нормирование данных"""
    matrix = np.array(data, 'f')
    len_val = len(matrix[1, :])
    for i in range(len_val):
        local_min = matrix[:, i].min()
        if local_min !=  0. 0:
            matrix[:, i] -= local_min
        local_max = matrix[:, i].max()
        if local_max !=  0. 0:
            matrix[:, i] /= local_max
    return matrix.tolist()

Теперь у нас есть список названий продуктов (пригодится при отображении дендрограммы) и значения переменных каждого продукта. Приведение названий к юникоду необходимо для корректного отображения кириллицы библиотекой matplotlib. Вспомогательная функция norm() обеспечивает нормирование показателей на диапазон [0,1].

Функция linkage требует на вход матрицу попарных расстояний между нашими объектами. В этом нам поможет функция pdist(). В качестве меры расстояния было взято обычное расстояние Эвклида.

from scipy.spatial.distance import pdist
dist = pdist(data, 'euclidean')

Наглядно посмотреть распределение расстояний между продуктами нам поможет следующий код:

import matplotlib.pyplot as plt
plt.hist(dist, 500, color='green', alpha= 0.5)

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

from scipy.cluster import hierarchy
Z = hierarchy.linkage( dist, method='average' )

В переменной Z содержится полученное в результате иерархической кластеризации дерево полного разбиения. Осталось немного - отобразить дендрограмму и обрезать её. Функция dendrogram() берёт на себя почти все типовые заботы, кроме сохранения полученного рисунка (что странно), так что обернём её сами.

def hierarchy_draw(Z, labels, level):
    """Рисуем дендрограмму и сохраняем её"""
    plt.figure()
    hierarchy.dendrogram(Z, labels=labels, color_threshold=level, leaf_font_size=5, count_sort=True)
    plt.show()

Используя эту функцию с пороговым уровнем 0,35 получаем красивую дендрограмму с выделенными разными цветами кластерами.

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