Pull to refresh

Алгоритм кластеризации данных FTCA

Reading time 4 min
Views 13K

Предисловие


Гуляя по англоязычным просторам интернета в поисках решения одной из наболевших тем на работе, наткнулся на очень интересный алгоритм под названием «Fast Threshold Clustering Algorithm». Данный алгоритм кластеризации, что примечательно, появился сравнительно недавно, а именно в ноябре этого года и автором является Дэвид Варади. Ссылка на первоисточник будет доступна в конце статьи.

Для начала, что такое кластеризатор?

image
Кластеризатор это программа, которая позволяет создать из определенного множества объектов — группы (в дальнейшем — кластеры), сформированные по смыслу или содержанию, количество этих групп, при этом, заранее может быть и не известно. Этими объектами могут быть, как документы, так и числа, в зависимости от того, что требуется сгруппировать.
Существует множество разнообразнейших алгоритмов кластеризации начиная от обычного K-means в разнообразных реализациях и интерпретациях, и заканчивая более сложными для понимания алгоритмами, которые могут включать суффиксные деревья (STC) или высшую математику (Lingo, SVD и т.п.). Часто встречающаяся проблема, которая настигает определенный алгоритм это ошибка. Ошибка всегда имеет место быть, особенно, когда мы говорим о документах в которых содержится реальная речь человека. Ведь, машине не всегда понятно, куда засунуть сказку про Царя Салтана: к политике, к истории древней Руси или создать кластер? Объекты могут иметь много связей с другими объектами по разным свойствам. С этой задачей бьются до сих пор.

А как избегать этой ошибки?

Избегать ошибки можно разными способами. Можно явно выделять ключевые свойства у объекта, которые ну никак не могут быть в одном кластере, но идеально могут подходить к другому. Например, в примере выше можно поискать наличие слов «жили-были», «царстве-государстве» и тому подобное и не включать этот документ в определенные кластера. А можно составлять граф зависимостей между объектами и уже смотря на этот граф делать дальнейшие умозаключения (Таким методом работает, например SCT и Lingo). Решений много, даже костыльное условие удовлетворения свойству на определенных наборах данных может существенно повысить точность кластеризации в целом.

А что за алгоритм, о котором Вы говорили в начале?

Алгоритм описанный Дэвидом, привлек мое внимание не своей асимптотикой или применимостью на практике, а своей простотой. Он построен на обычной человеческой логике и очень схож с остальными алгоритмами.

Для начала, представим, что у нас есть набор объектов, которые мы хотим сгруппировать и функция, которая говорит насколько два объекта похожи друг на друга в процентном соотношении:
F(x,y) = F(y,x) = ...%
— функция корреляции двух объектов.
(Собственно это все, чем, обычно, пользуется человеческий мозг при группировании объектов.)

Далее, введем понятие средней похожести:
G(x, y1, y2, ..., yn) = SUM(F(x,yk))/n
— эта функция показывает насколько объект похож на группу других объектов.

Алгоритм


На самом первом (и длительном) шаге требуется, для удобства, отсортировать все наши объекты по их средней корреляции с остальными объектами в порядке возрастания. То есть мы получим список первым элементом которого будет являться элемент с наименьшей средней корреляцией, а последним, наоборот, с наибольшей.
Далее нам следует решить, сколько создавать кластеров и по какому принципу. Что за принцип? А это наш Treshold — та самая граница выше которой объекты считаются похожими достаточно, чтобы быть вместе, в одной группе.

Создаются кластера по следующему алгоритму:
1) Сортируем объекты.
2) Берем первый и последний объект из нашего отсортированного списка.
• Если их корреляция больше нашей границы схожести — создаем один кластер первыми элементами которого будут эти два объекта и находим все объекты из оставшихся, средняя корреляция которых со всем кластером будет больше трешхолда.
• Если их корреляция меньше границы схожести — создаем два кластера элементы в которые будут попадать по тому же принципу, что описано выше.
3) Если остался один объект — создаем отдельный кластер и пихаем его туда. В противном случае возвращаемся на шаг 1.

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

Итоги


Подводя итоги хочу сказать, что даже я до сих пор не понял почему Дэвид начал название со слова «Fast», что в переводе «Быстрый». Быстрым этот алгоритм, конечно, не назовешь, если не использовать огромную матрицу корреляции каждого объекта с каждым + средние значения для каждого объекта, но вычисление всего этого — очень сложная операция, ввиду возможной сложности самой функции корреляции. Теоретически идея очень хорошая, практически же — она может обрабатывать небольшие объемы данных.
Обычная асимптотическая сложность алгоритма равна O(n^3) от, возможно, сложной функции F(x,y). При использовании матрицы корреляции мы получим O(n^2) по скорости и O(n^2) по памяти, что выбьет все пробки у оперативной памяти. Вот такие пироги, дорогие Хабрачане.

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

Источник: cssanalytics.wordpress.com/2013/11/26/fast-threshold-clustering-algorithm-ftca
Tags:
Hubs:
+13
Comments 9
Comments Comments 9

Articles