Предположим , что мы имеем множество элементов Е и сходство ( не расстояние ) функция сим (е, Ej) между двумя элементами Ei, Ej ∈ E .
Как мы можем (эффективно) кластеризовать элементы E , используя sim ?
к -средних, например, требует заданных к , Навес Кластеризация требует два пороговых значений. Что если мы не хотим таких предопределенных параметров?
Обратите внимание, что сим не обязательно является метрикой (то есть неравенство треугольника может или не может иметь место). Более того, не имеет значения, являются ли кластеры непересекающимися (разбиениями E ).
clustering
algorithms
similarity
vefthym
источник
источник
1-sim(ei, ej) = Distance. С метрикой расстояния вы можете применять, например, иерархическую кластеризацию. Спустившись от корня, вы увидите, на каком уровне кластеров гранулярности будет иметь смысл для вашей конкретной проблемы.Ответы:
Я думаю, что ряд алгоритмов кластеризации, которые обычно используют метрику, на самом деле не полагаются на свойства метрики (кроме коммутативности, но я думаю, что у вас это будет здесь). Например, DBSCAN использует эпсилон-окрестности вокруг точки; там нет ничего, что конкретно говорит о неравенстве треугольника. Таким образом, вы, вероятно, можете использовать DBSCAN, хотя вам, возможно, придется сделать какой-то нестандартный пространственный индекс для эффективного поиска в вашем случае. Ваша версия epsilon-окрестности скорее всего будет sim> 1 / epsilon, а не наоборот. Та же история с k-means и родственными алгоритмами.
Можете ли вы построить метрику из вашего сходства? Одна возможность: dist (ei, ej) = min (sim (ei, ek) + sim (ek, ej)) для всех k ... В качестве альтернативы, вы можете указать верхнюю границу, чтобы sim (ei, ej) <sim (ei, ek) + sim (ek, ej) + d, для всех k и некоторой положительной постоянной d? Интуитивно понятно, что большие значения симов означают сближение: 1 / сим метрическая? Как насчет 1 / (сим + константа)? Как насчет min (1 / sim (ei, ek) + 1 / sim (ek, ej)) для всех k? (этот последний гарантированно будет метрикой, кстати)
Альтернативное построение метрики - сделать вложение. В качестве первого шага вы можете попытаться отобразить ваши точки ei -> xi так, чтобы xi минимизировала сумму (abs (sim (ei, ej) - f (dist (xi, xj))) для некоторой подходящей функции f и метрики. dist. Функция f преобразует расстояние при внедрении в значение, похожее на подобие, вам придется немного поэкспериментировать, но 1 / dist или exp ^ -dist являются хорошими отправными точками. Вы также должны поэкспериментировать на лучших размерность для xi. Отсюда вы можете использовать обычную кластеризацию для xi. Идея здесь в том, что вы можете почти (в лучшем смысле) преобразовать ваши расстояния при внедрении в значения подобия, чтобы они правильно кластеризовались.
При использовании предопределенных параметров все алгоритмы имеют некоторую настройку. DBSCAN может найти количество кластеров, но вам все еще нужно указать некоторые параметры. В общем случае для настройки требуется несколько прогонов алгоритма с различными значениями настраиваемых параметров, а также некоторая функция, которая оценивает степень кластеризации (либо рассчитывается отдельно, предоставленным самим алгоритмом кластеризации, либо просто с глазком :) Если символ ваши данные не меняются, вы можете настроить один раз, а затем использовать эти фиксированные параметры; если он меняется, то вы должны настраиваться для каждого запуска. Это можно выяснить, настроив каждый прогон и сравнив, насколько хорошо параметры одного прогона работают с другим, с параметрами, специально настроенными для этого.
источник
Алекс сделал несколько хороших замечаний, хотя мне, возможно, придется немного отодвинуть его предположение, что DBSCAN - лучший алгоритм кластеризации, который можно использовать здесь. В зависимости от вашей реализации и от того, используете ли вы ускоренные индексы (многие реализации этого не делают), сложность времени и пространства будет и вами
O(n2), что далеко от идеала.Лично мои алгоритмы кластеризации переходят на OpenOrd для кластера, который выигрывает все, и FLAME для нечеткой кластеризации. Оба метода безразличны к тому, являются ли используемые метрики сходством или расстоянием (в частности, FLAME практически идентичен в обеих конструкциях). Реализация OpenOrd в Gephi является
O(nlogn)и, как известно, более масштабируемой, чем любой из других алгоритмов кластеризации, представленных в пакете Gephi.С другой стороны, FLAME отлично подходит, если вы ищете нечеткий метод кластеризации. Хотя сложность FLAME немного сложнее определить, так как это итеративный процесс, было показано, что он является субквадратичным и по скорости выполнения похож на knn.
источник
DBSCAN (см. Также: Обобщенный DBSCAN) не требует расстояния. Все, что ему нужно - это двоичное решение . Обычно можно использовать «расстояние <эпсилон», но ничто не говорит, что вы не можете использовать «подобие> эпсилон» вместо этого. Не требуется неравенство треугольника и т. Д.
Распространение сходства, как следует из названия, использует сходства.
Иерархическая кластеризация, за исключением, возможно, связи Уорда, не делает никаких предположений. Во многих реализациях вы можете просто использовать отрицательные расстояния, когда у вас есть сходства, и это будет работать просто отлично. Потому что все, что нужно, это min, max и <.
Ядро k-means может работать, если ваше сходство - хорошая функция ядра. Думайте об этом как о вычислении k-средних в другом векторном пространстве, где евклидово расстояние соответствует вашей функции подобия. Но тогда вам нужно знать k.
PAM (K-medoids) должен работать. Присвойте каждый объект наиболее похожему медоиду, затем выберите объект с наибольшим средним сходством в качестве нового медоида ... неравенства треугольника не требуется.
... и, вероятно, многое, многое другое. Существуют буквально сотни алгоритмов кластеризации. Большинство должно работать ИМХО. Очень немногие, кажется, на самом деле требуют метрических свойств. К-средним, вероятно, предъявляют самые строгие требования: он сводит к минимуму дисперсию (не расстояние или сходство), и вы должны иметь возможность вычислять средние значения.
источник
Анализ топологических данных - это метод, явно разработанный для описываемого вами параметра. Вместо глобальной метрики расстояния она опирается только на локальную метрику близости или соседства. См .: Топология и данные и Извлечение идей из формы сложных данных с использованием топологии . Вы можете найти дополнительные ресурсы на сайте для Ayasdi.
источник