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

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

http://www.ehdp.com/vitalnet/breaks-1.htm

http://wiki.objectvision.nl/index.php/Fisher's_Natural_Breaks_Classification

Вот пример входных данных - (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])

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сделал его, только одно не понимаю, у меня, для других входных данных - не как в топике, матрица результатов(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

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

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

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

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

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

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

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

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

а ещё ТС может поприседать :)

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

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

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

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

http://www.machinelearning.ru - хороший сайт по тематике, ещё есть лекции в школе анализа данных от яндекса.

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

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

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

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

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

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

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

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

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

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

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

Этот 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

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

Посмотри еще DBSCAN. Очень простой

http://en.wikipedia.org/wiki/DBSCAN#Algorithm

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

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

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

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

AP нормально справляется с такими ситуациями. Вот пример моего аутпута. Размеры кластеров указаны после :.

А вашу similitary матрицу можно посмотреть?

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

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

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

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