Кажется, что для K-средних и других связанных алгоритмов кластеризация основана на расчете расстояния между точками. Есть ли тот, который работает без него?
machine-learning
clustering
data-mining
k-means
user154510
источник
источник
Ответы:
Одним примером такого метода являются модели конечных смесей (например, здесь или здесь ), используемые для кластеризации. В FMM вы считаете распределение ( ) вашей переменной X в виде смеси K распределений ( F 1 , . . . , Е к ):f X K f1,...,fk
где представляет собой вектор параметров θ = ( П ' , & thetas ' 1 , . . . , θ ' к ) ' и π к является доля к «го распределения в смеси и & thetas ; к является параметром (или параметры) распределения f k .ϑ ϑ=(π′,ϑ′1,...,ϑ′k)′ πk k ϑk fk
Конкретным случаем для дискретных данных является анализ скрытого класса (например, здесь ), определяемый как:
где - вероятность наблюдения скрытого класса k (то есть π k ), P ( x ) - вероятность наблюдения значения x, а P ( x | k ) - вероятность того, что x находится в классе k .P(k) k πk P(x) x P(x|k) x k
Обычно для FMM и LCA EM алгоритм используется для оценки, но Байесовский подход также возможен, но немного более требовательный из-за таких проблем, как идентификация модели и переключение меток (например , блог Сианя ).
Таким образом, здесь нет меры расстояния, а есть статистическая модель, определяющая структуру (распределение) ваших данных. Из-за этого другое название этого метода - «кластеризация на основе модели».
Проверьте две книги по FMM:
Одним из наиболее популярных пакетов кластеризации , который использует ФММЫ являются
mclust(проверьте здесь или здесь ) , что реализуются в R . Однако возможны и более сложные FMM, проверьте, например,flexmixпакет и его документацию . Для LCA существует пакет R poLCA .источник
K-средства не основаны на «действительно» расстоянии. Это минимизирует дисперсию . (Но дисперсия квадрат евклидова расстояния, так что каждая точка будет назначена на ближайший центроид евклидова расстояния, тоже).∼
Существует множество подходов кластеризации на основе сетки . Они не вычисляют расстояния, потому что это часто приводит к квадратичному времени выполнения. Вместо этого они разбивают данные и объединяют их в ячейки сетки. Но интуиция, лежащая в основе таких подходов, обычно очень тесно связана с расстояниями.
Существует ряд алгоритмов кластеризации для категориальных данных, таких как COOLCAT и STUCCO. Расстояния нелегко использовать с такими данными (одноразовое кодирование - это взлом, и оно не дает особо значимых расстояний). Но я не слышал, чтобы кто-нибудь использовал эти алгоритмы ...
Существуют кластерные подходы для графов. Но либо они сводятся к классическим задачам графа, таким как поиск клики или околосклики и раскраска графа, либо они тесно связаны с кластеризацией на основе расстояний (если у вас есть взвешенный граф).
Кластеры на основе плотности, такие как DBSCAN, имеют другое имя и не ориентированы на минимизацию расстояний; но «плотность» обычно указывается относительно расстояния, поэтому технически эти алгоритмы основаны либо на расстоянии, либо на сетке.
Основная часть вашего вопроса, которую вы оставили, - это ваши данные ?
источник
В дополнение к предыдущим хорошим ответам, я бы предложил рассмотреть модели смеси Дирихле и иерархические модели процессов Дирихле на основе байесовской модели . Для довольно полного и общего обзора подходов и методов определения оптимального количества кластеров , пожалуйста, посмотрите этот отличный ответ на StackOverflow : /programming//a/15376462/2872891 .
источник
Чисто дискриминационный подход «регуляризованная максимизация информации» по Gomes et al . В нем вообще нет понятия сходства / расстояния.
Идея состоит в том, чтобы иметь модель, подобную логистической регрессии, которая ставит точки в мусорные ведра. Но вместо того, чтобы обучать его максимизировать некоторую форму логарифмического правдоподобия меток классов, целевой функцией является та, которая ставит точки в разные кластеры.
Для управления количеством кластеров, используемых моделью, дополнительный член регуляризации, взвешенный по гиперпараметруλ используется. Это сводится к обратной дисперсии гауссовского априора по весам.
Расширение методов ядра или нейронных сетей для нелинейной кластеризации является простым.
источник