Неизвестный библейский алгоритм кластеризации

Инструменты кластеризации

Кластеризация — это поиск групп о которых ничего не известно (не путать с классификацией, т. е. с назначением класса элементам). Неизвестность разрешается перебором параметров.

Если известно k количество искомых групп, то можно применить метод k-средних (k-means). Такой алгоритм подбирает центры. Работает для сферических групп.

Если перед вами вытянулись колбаски, то можно применить плотностный алгоритм DBSCAN(ε, k) — задать размер области ε и сколько точек k должна содержать область. Если две точки касаются друг друга такими областями, тогда эти точки принадлежат одному кластеру.

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

В поисках универсалий

Поступай с другими так, как хочешь, чтобы поступали с тобой.

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

Но позвольте! У нас же данные, а не человеки! Поэтому нам предстоит очеловечить точки, закрыть их от окружающего мира и тем самым превратить в субъектов.

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

Рассмотрим отношение между A и B:

• Для A: A, B, C, E. Ранг AB = 2.
Расстояние d.

• Для B: B, C, D, A. Ранг BA = 4. Расстояние d.

Оба шара имеют одинаковый радиус d = d(AB) = d(BA), но ранги отличаются. В жизни так же, вы стоите напротив человека, а он напротив вас. Объективно между вами равное расстояние, мерь хоть от него, хоть от вас, но есть маленький субъектный нюанс. Два нюанса, его и ваш. Учтём их. Сотворим из точек субъектов и оценим чужое качество.

Итак, у нас две независимые точки A и B. И явная разница в окружении: у А 2 точки, а у B 4 точки. Из "глаз" A оценим чужое отношение так, как будто у B столько же точек. То есть посчитаем BA в единицах A: поделим d на 4 и умножим на 2. И наоборот, из "глаз" B — оценка AB = 4/2·d.

Второй способ оценки — через перенос и натягивание чужого шара.

Перенесём голубой шар в систему координат A, сохраняя количественные свойства шара (внутри должно быть 4 точки). Тогда шар увеличится, чтобы вместить A, B, C, E!

Для B тоже всё поменяется — только наоборот шар уменьшится до точек B, C (белым пунктиром).

Итого получены по две оценки чужого отношения каждым субъектом. Сравним эти оценки с изначальным радиусом AB=d.

• Для A: количественная оценка уменьшилась до 2/4·d; качественная оценка увеличилась до AE, т. е. до четвёртого ранга d(A₄);

• Для B наоборот: количественная оценка увеличилась до 4/2·d; качественная оценка уменьшилась до второго ранга d(B₂).

Каждая точка стала субъектом, у неё нет доступа к чужим радиусам, к качественным сторонам отношений других. Но при этом у них появились две оценки происходящего r/R·d(r) и d(R). Заметим, что если бы ранги совпадали r=R, то обе оценки были бы равны d. Выбрав наибольшую оценку, станет возможным отделить подобные от неподобных

Самое близкое из таких отношений и кристаллизуется в ребро. Образуется деревце, и поиск наиближайшего запустится снова. Так будет продолжаться до тех пор, пока все точки не соединятся.

Без всяких зацепок-параметров нам удалось создать формулу диалектического расстояния, отражающую суть отношений точек в пространстве. Объективность пространства перешла в субъектность точек и вывернулась обратно в объект-ребро. Пройдя двойное отрицание, абстрактное стало конкретным.

ДРУГ (druhg)

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

Алгоритм идеален для первичного исследования данных (EDA) и для поиска глобальных выбросов.

Глобальный порядок, локальный расчёт

Создаётся видимость глобального порядка соединений. Но это не так.

Ребро a значительно меньше ребра b, но они не влияют друг друга. Главное чтобы они случились до ребра c.

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

Сложность вычислений

Может также показаться, что сравнение всех точек со всеми — это вычислительно затратная задача с квадратичной сложностью O(n²). А повторный запуск процесса поиска ближайшего соединения усложняет вычисление до O(n³). Но это не так.

Поиск глобального ближайшего заменяется на поиск субъектных ближайших и хранение этих оптимумов. Структура данных k-ближайших соседей упрощает алгоритмическую сложность до O(n logn).

Точность vs производительность

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

При ограничении от 6 до 63 ближайших соседей достигается хороший результат. После 64 соседей результат сходится и впустую тратится время обработки (возможно алгоритмически решится через поиск лучшего для дерева, а не точки).

Запуск и исследование вложенности

# pip install druhg

from druhg import DRUHG
import matplotlib.pyplot as plt
import pandas as pd, numpy as np

XX = pd.read_csv('chameleon.csv', sep='t', header=None)
XX = np.array(XX)
clusterer = DRUHG(max_ranking=200, do_edges=True)
clusterer.fit(XX)

# research tool with silders
clusterer.plot()

# manual labels 
labels = clusterer.relabel(exclude=[], 
                           size_range=[0.2, 2242], 
                           fix_outliers=1)

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

• Разбить кластер по его лейблу. exclude=[7749] разобьёт красный огурец

• Не выводить слишком маленькие или слишком большие кластеры. size_range=[0.2,2242] от 20% размера выборки до конкретных 2242. Слайдер Qty справа.

• Покрасить выбросы по соединённости. fix_outliers=1.

Или запустить clusterer.plot():

Инструмент позволяет выбрать нужную разбивку по размеру кластеров — почему-то такой инструмент не предоставляется в стандартных инструментах. Позволяет выявлять глобальные выбросы. Получать общую информацию по кластеру. Наигравшись, можно сохранить результат через relabel().

P.S. о секретном соусе, превращающем деревья в кластеры, и о диалектике целостности расскажу в следующей статье.