LINUX.ORG.RU

Посоветуйте алгоритм кластеризации.

 ,


1

2

Основное требование - заранее не известно количество кластеров. Входные данные - одномерный список целых чисел. Вот пример входных данных - (5 1 3 5 7 3 50 30 45 32 1000 800 300 10000 8000) Желаемый результат(| - разделитель кластеров) - (5 1 3 5 7 3 | 50 30 45 32 | 1000 800 | 300 | 10000 8000). Простота, в плане понимания и реализации, приветствуется. Основная сложность, как мне кажется, в том, что есть большая разница в сосредоточенности точек различных(желаемых) кластерах. Спасибо.

affinity propagation - непараметрический, есть реализации на python, R, java (кажется). В качестве метрики авторы советуют отрицательную евклидову.

silw ★★★★★
()
Последнее исправление: silw (всего исправлений: 2)

Вот пример входных данных - (5 1 3 5 7 3 50 30 45 32 1000 800 300 10000 8000)

А в методе, на который я сослался, на вход ожидается монотонная последовательность. Твою последовательность x[k] можно превратить в монотонную y[k] следующим образом:

y[0]:=x[0]
y[k]:=y[k-1]+abs(x[k] - x[k-1])

Manhunt ★★★★★
()

Основная сложность, как мне кажется, в том, что есть большая разница в сосредоточенности точек различных(желаемых) кластерах.

Глядя на твой пример, может быть, кластеризировать не сами числа, а логарифмы от них?

Manhunt ★★★★★
()

Основное требование - заранее не известно количество кластеров.

Основное решение — человеческий волюнтаризм :)

Простота, в плане понимания и реализации, приветствуется.

Statistica: модуль «методы кластерного анализа» — полный набор стандартных методов. ©

P.S. Погугли ещё «непараметрическая кластеризация».

quickquest ★★★★★
()
Последнее исправление: quickquest (всего исправлений: 1)
Ответ на: комментарий от Quickern

Зачем для одномерного массива это все?

Для освоения стандартных методов, которые могут пригодится ТС'у в будущем.

P.S. Зачем 2-мерная таблица умножения, если можно складывать одномерный массив [1+1+... +1]? :)

quickquest ★★★★★
()
Ответ на: комментарий от silw

Вот посмотрите сколько их всяких

http://scikit-learn.org/stable/modules/clustering.html#clustering

Из непараметрических возможно лучший DBSCAN А из параметрических я бы взял старый добрый KMeans, простой и быстрый как пуля. Но требует количество кластеров.

Bell
()
Ответ на: комментарий от Quickern

а что использовать для одномерного массива?

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от silw

сделал его, только одно не понимаю, у меня, для других входных данных - не как в топике, матрица результатов(A+R) сходится к такому виду -

  a   b    c    d    e
a 12  -30  -30  -20  -25
b 10  -15  -26  -10  -15
c 12  -26  -16  -12  -15
d -4  -24  -26    0    0
e -4  -24  -24    0    0
не могу понять, интерпретировать ли это как два кластера - {a b c} и {d e} или в этом методе должны получаться равные оценки по столбцам для элементов одного кластера, то есть должно быть a=b=c и по строкам быть один максимум?

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

Там же, даже в примерах, есть процедура для соотнесения объект - номер кластера. Affinity propagation на выходе выдает плоские кластеры.

silw ★★★★★
()
Ответ на: комментарий от Bell

Спасибо кэп! Именно поэтому я и написал про реализацию на питоне. На моих данных только AP смог выдать разумные кластеры, для которых обнаруживалось биологическое объяснение.

А если еще почитать исходную статью с описанием (Science, между прочим) можно обнаружить сравнение качества и производительности с KMeans.

silw ★★★★★
()
Ответ на: комментарий от silw

KMeans конечно примитивный, но зависит от задач и данных. Для моих ничего другого не надо. И у него есть on-line разновидность для любого объема данных. Если бы задача была параметрическая, то для одномерного случая другого и не надо!

Bell
()
Ответ на: комментарий от silw

где там же? я делал по этой статье - http://www.cs.columbia.edu/~delbert/docs/DDueck-thesis_small.pdf и там процедура соотношения выбирает максимальное значение из строки матрицы C=A+R. Что значит плоский кластер? то что для всех элементов кластера значения в матрице C равны?

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от silw

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

Вот, про что я говорю. В данном примере выводятся центры кластеров и номера кластера для каждого элемента.

silw ★★★★★
()
Ответ на: комментарий от silw

там же просто вызов библиотечной функции и визуализация результатов. Меня интересует какая может быть матрица внутри самого алгоритма. Не могу нигде найти описания алгоритма, где было бы про это сказано, если вы не знаете, то прийдётся лезть внутрь этой питоновской библиотеки и добавить печать матрицы-результата чтобы сравнить со своими результатами. Но питон...

pseudo-cat ★★★
() автор топика

1й Подход, когда точки случайно перемешаны

В этой задаче надо получить метрику расстояния между точками. Функция dist() и далее над матрицей можно изгаляться любым известным методом. Если кластеры имеют «протяженный» вид надо использовать что то типа «спектральной» кластеризации из kernlab.

2й Подход, когда точки идут по порядку.

Берем любой метод который отслеживает «Структурные изменения» (или онлайн алгоритм делающий аналогичное, или марковский процесс со скрытыми состояниями)...

psv1967 ★★★★★
()

Можно попробовать копнуть тут:

-математическая статистика (курс ВТУЗ) - мультимодальные распределения, спектральный анализ

anonymous
()
Ответ на: комментарий от anonymous

бывает такое, что нужно решить небольшую задачу в составе более крупного и изучать для этого весь курс по тематике как-то нет времени.

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

Простейший стат-анализ не требует углублённого изучения полного курса - достаточно основ.

По-быстрому не напрягаясь это тогда из серии - можно рандомом...

... две конфеты куча? нет. а три? ну-у... что тогда считать кучей?

Формальный подход: методом дихотомии:

сколько конфет куча?

10 - да 5 - да 2 - нет 3 - нет 4 - почти...

Почему так? - это нечёткие множества

anonymous
()
Ответ на: комментарий от anonymous

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

pseudo-cat ★★★
() автор топика

Этот afinity propagation сводит меня с ума, на таких входных данных (при damping = 0.9) -

[
 [1]; [2]; [30]; [31]; [4]; [5]; [29]
] 
У меня получается на выходе такая матрица -
  -13,26   0,0175973  -623,801  -744,851   0,0179447  -13,0466  -628,854
-12,5769  0,00644317  -544,437  -663,487   !0,0287952!  -12,5785   -551,49
-569,856    -499,898   70,2865     -70,3      -391,9  -353,861     -70,3
-646,067    -574,109   70,2806  -70,5101    -462,111  -422,072  -70,2938
-12,5785  !0,0287952!   -436,44   -551,49  0,00644317  -12,5769  -447,493
-13,0466   0,0179447  -407,806  -520,857   0,0175973    -13,26  -420,859
 -530,07    -462,111   70,2806  -70,2938    -358,114  -322,075  -70,5101
из чего следует, что 2 - в кластере 5, а 5 в кластере 2. И ни в одной статье не могу найти, нормально ли такие циклические зависимости или нет!

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

хотя нет, просто надо увеличить количество итераций. Я взял это количество из питоновской библиотеки, там по дефолту 200, но матрица сходится у меня ближе к 1000. И это странно.

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

Да нет, это нормально. дампинг фактор 0.5 не очень хороший. В исходной статье советуют 0.9.

silw ★★★★★
()
Ответ на: комментарий от pseudo-cat

А, в этом смысле. Тогда лучше смотреть в код - процедура проверки сходимости и присвоения индексов там довольно проcто описана, хотя и с numpy специфичными фишками.

silw ★★★★★
()
Ответ на: комментарий от Bell

Не подходит, также как и affinity propagation. Они зависят от размеров кластеров, а в моих данных есть, обычно, 3-4 группы данных, сильно отличающихся по количеству элементов. То есть на выходе может быть один кластер с 10^3 элементами, а в другом 1 элемент.

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

В общем-то ничего из предложенного не подходит как есть. Думается, что в моём случае надо сначала выделять сильно отличающиеся показания, как случайные помехи, а затем отдельно делать 1)кластеризацию для них, добавляя средние шумы 2)кластеризацию для данных, не являющихся «помехами».

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

Вечерком выложу. Я сейчас бегло глянул, там, оказывается, была тонкость - мы вручную слили, кажется, 6 близких кластеров в 1, потому, что между ними совсем копеечные расстояния и это слияние никак не противоречило физическому смыслу данных. В сыром разбиении минимум - 1 объект в кластере, максимум - 146 объектов.

Плюс на количество, а следовательно размеры, кластеров влияет наложенная поправка на preference (продиктована физическим смыслом входных данных).

silw ★★★★★
()
Ответ на: комментарий от pseudo-cat

Не подходит, также как и affinity propagation. Они зависят от размеров кластеров, а в моих данных есть, обычно, 3-4 группы данных, сильно отличающихся по количеству элементов. То есть на выходе может быть один кластер с 10^3 элементами, а в другом 1 элемент.

Это не должно влиять, т.к. в DBSCAN ищет связные области, а связность задается параметром. affinity propagation я не знаю, но думаю, что и там не должно влиять. Вот K-means сильно зависит от инициализации, но он тебе в чистом виде равно не подходит. Хотя можешь и его посмотреть. У него есть модификации для правильной инициализации и для автоматического выбора числа кластеров, а главное что он очень быстрый. Но я бы взял DBSCAN как один из самых простых. Твоя задача очень простая, ничего городить не надо.

Bell
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.