Pull to refresh

Кластеризация. Алгоритм а-квазиэквивалентности

Algorithms *
Странно, но статей о извлечение знаний (data mining) и кластеризации (как одном из основных инструментом, которие используются для извлечения знаний) на Хабре совсем немного. А если говорить говорить о конкретных алгоритмах, то рассматривались только hard/soft k-means.

В статье ниже описывается теория и реализация (Python + matplotlib) не очень известного, но крайне интересного иерархического метода который можно назвать алгоритмом а-квазиэквивалентности.


Извлечения знаний и кластеризация


К сожалению, чукча не писатель (тем более не русскоязычный), поэтому тем, кто не знаком с терминами в подзаголовке, рекомендую ознакомится с Обзор алгоритмов кластеризации данных и Извлечение данных или знаний? (статьи на родном Хабре) или посмотреть в Вики (1, 2).

Задание


Будем разделять и властвовать точки в двухмерном пространстве. Характеристиками точек будут только их координаты. Поскольку метод у нас иерархический, то результатом будет дерево\список возможных делений на кластера.
Для затравки — пример. Хотим разделить на кластера точки на изображении:

circle

Как же должен поделить эти точки ИИ? Посмотрим, что придумает наш алгоритм.

Теория


Математика, изложенная ниже, взята из книги А. А. Барсегян, М. С. Куприянов, В. В. Степаненко, И. И. Холод — Методы и модели анализа данных OLAP и Data Mining (если быть точним — глава 7.4. Кластеризация данных при помощи нечетких отношений).

Большинство алгоритмов кластеризации (будем рассматривать k-means как эталон) для оценки схожести образцов использует расстояние между ними. Довольно логично, но думаем шире — образцы так же похожи, если похожи оценки расстояния от каждого из них ко всем остальным образцам. Что нам это даст? — Мы сможем решить и поставленную задачу, и остальные примеры, с которыми справляется k-means.

И так, как же реализованная описанная стратегия?
  • Имеем множество X, количество элементов в множестве — Q.
    Построим матрицу оценок расстояний между элементами (назовем эти оценки нормальными мерами сходства) с помощью формулы
    matrix1
    где d(x, y) — расстояние Евклида.
  • Построим относительные меры сходства с помощью формулы
    matrix2
    Полученная трехмерная матрица покажет, насколько похожа пара данных элементов относительно все остальных.

  • Построим матрицу мер сходства элементов множества по формуле
    image
    С трехмерной матрицы получили двухмерную, которая содержит худшие оценки мер сходства для каждой пары точек.
  • Для полученной матрицы R построим её замыкание, используя следующие формулы:
    closure1
    Определение для операции замыкания:
    closure2
    closure3
    В нашем случае S = max, T = min.

В конце работы алгоритма для четырех точек мы получим матрицу типа
1 2 3 4
1 1 0.5 0.3 0.3
2 0.5 1 0.3 0.3
3 0.3 0.3 1 0.6
4 0.3 0.3 0.6 1

Числа в матрице показывают, принадлежит ли пара точек отношению R, их называют уровнями квазиэквивалентности. Выбор конкретного уровня (a) разбивает множество на классы эквивалентности, которые соответствуют отделенным кластерам. То есть, если мы выберем уровень a = 0.4, то пары (1,4), (2,4), (1,3) и (2,3) уже не будут принадлежать отношению (их уровень альфа меньше, чем заданный). По сути, данную матрицу можно представлять как матрицу графа, и в случае уровня a=0.4 начальный граф разобьется на два — (1, 2) и (3, 4).

В некоторых научных работах вместе с описанием алгоритма также демонстрируют «блок-схемку»:

schema

Попробуем её разобрать. С буквами «мю», «эпсилон» и Т-нормой все понятно — они есть у нас в формулах. а-толерантность и а-квазиэквивалентность — это свойства отношения, которые оно получает после применения Т-нормы и описанного замыкания. Дальше у нас разбиение на кластера, которое и вовсе можно провести эвристически (например, использовать теорию графов).

Внимательный читатель спросит — а где здесь нечеткие отношения из названия главы в книге? Именно они используются для доказательства того, что описанные шаги приведут нас к решению.

Практика


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

circle3

Согласитесь, довольно неожиданно, но и в тоже время — логично.
Ну и для случайных данных:

rand1

rand2

rand3

Исходный код: алгоритм, рисовалка.
Код исключительно демонстрационный и не претендует ни на эффективность, ни на соответствие PEP8.

Заключение


Есть идеи использовать описанный алгоритм для решения реальной задачи анализа предложений недвижимости. Если будут интересные результаты — поделюсь.

Ссылки:
— собственно книга, теория из которой использовалась — Методы и модели анализа данных OLAP и Data Mining;
— еще одна книга по data mining от тех же авторов — Технологии анализа данных. Data Mining, Visual Mining, Text Mining, OLAP
— интереснейшая статья, в которой на похожем примере решается задача классификации — Классификация данных методом опорных векторов.

Буду признателен за замечания в личку.
Tags: кластеризацияквазиэквивалентностьизвлечение знанийdata miningclustering
Hubs: Algorithms
Total votes 35: ↑31 and ↓4 +27
Comments 18
Comments Comments 18

Popular right now