Кластеризация с подобием косинуса

У меня есть большой набор данных, который я хотел бы скопировать. Размер моего пробного запуска - 2500 объектов; когда я запускаю его на "реальной сделке", мне нужно будет обрабатывать не менее 20 тыс. объектов.

Эти объекты имеют сходство косинусов между ними. Такое подобие косинуса не удовлетворяет требованиям математической метрики расстояния; он не удовлетворяет неравенству треугольника.

Я хотел бы сгруппировать их каким-то "естественным" способом, который объединяет аналогичные объекты, не указывая заранее количество ожидаемых кластеров.

Кто-нибудь знает об алгоритме, который это сделает? Действительно, я просто ищу любой алгоритм, который не требует a) метрики расстояния и b) заранее заданного количества кластеров.

Большое спасибо!

Этот вопрос задан здесь: Кластеризация из значений подобия косинуса (но это решение предлагает только кластеризацию K-сред), а здесь: Эффективная кластеризация матрицы подобия (но это решение было довольно расплывчатым)

Ответ 1

Apache mahout имеет ряд алгоритмов кластеризации, в том числе некоторые, которые не требуют указания N и которые позволяют указать метрику расстояния.

Средняя кластеризация сдвига похожа на k-средство, но без предварительно заданного числа кластеров https://cwiki.apache.org/confluence/display/MAHOUT/Mean+Shift+Clustering.

В более общем плане, если вы хотите попробовать множество алгоритмов, существует огромное количество сложных пакетов, доступных для R (включая несколько вариационных байесовских реализаций EM, которые будут выбирать лучшее количество кластеров), которые доказали очень полезно для некоторых моих исследований в прошлом: http://cran.r-project.org/web/views/Cluster.html.

Ответ 2

На самом деле большинство алгоритмов, требующих "функции расстояния", не имеют требования к тому, чтобы он был метрическим.

DBSCAN может быть обобщен (см. Википедию) на версию, где он даже отвлекается от расстояния, он просто должен иметь какое-то "плотное" понятие. (DBSCAN также не обязательно должен знать количество кластеров заранее)

Но даже для k-средних, которое имеет довольно строгие требования к расстоянию, даже вне метрического, существует вариант, называемый сферическими k-средствами.

В любом случае, в контексте базы данных полные требования "метрики" являются утопическими. В любых реальных данных могут быть две записи с одинаковыми координатами, поэтому в лучшем случае у вас будет псевдометрика. Треугольное неравенство в основном играет роль для оптимизации (например, с использованием индекса M-дерева, который имеет строгие требования к неравенству треугольника) или ускоренных k-средств, использующих это свойство.

Ответ 3

Вы также можете попробовать распространение Affinity (http://www.psi.toronto.edu/index.php?q=affinity%20propagation). Алгоритм принимает матрицу подобия как входной сигнал, а также, я полагаю, автоматически корректирует количество центроидов кластера.