Предисловие
Гуляя по англоязычным просторам интернета в поисках решения одной из наболевших тем на работе, наткнулся на очень интересный алгоритм под названием «Fast Threshold Clustering Algorithm». Данный алгоритм кластеризации, что примечательно, появился сравнительно недавно, а именно в ноябре этого года и автором является Дэвид Варади. Ссылка на первоисточник будет доступна в конце статьи.
Для начала, что такое кластеризатор?
Кластеризатор это программа, которая позволяет создать из определенного множества объектов — группы (в дальнейшем — кластеры), сформированные по смыслу или содержанию, количество этих групп, при этом, заранее может быть и не известно. Этими объектами могут быть, как документы, так и числа, в зависимости от того, что требуется сгруппировать.
Существует множество разнообразнейших алгоритмов кластеризации начиная от обычного 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/
Автор: eocron
