Кластеризация вектора

[monst92]

Всем привет.

Итак, нужно кластеризовать одномерный массив.

Для наглядности, я нарисовал в ручную в excel что имею ввиду.
Дана первая строчка - Input[N]
Сформировать вторую строчку - Output[N]

INPUT: одномерный массив из N элементов, в него передана абстрактная int-последовательность.
OUTPUT: одномерный массив из N элементов, элементы которого указывают на принадлежность к какому-либо кластеру исходного массива.

Ограничения:
1. Количество кластеров неизвестно.
2. Массив Input[N] недифференцируемый по определению (поиск extr - несостоятельно).
3. Кластеры не должны перекрываться (если такое возможно), возможно потребуется ввести доп. функцию для их сепарации.

Просьба оказать содействие в формализации задачи (а если ткнете носом на литературу, алгоритм или готовую реализацию - супер).

[realeugene]

monst92 в сообщении #1377911 писал(а):

1. Количество кластеров неизвестно.
2. Массив Input[N] недифференцируемый по определению (поиск extr - несостоятельно).
3. Кластеры не должны перекрываться (если такое возможно), возможно потребуется ввести доп. функцию для их сепарации.

По одному кластеру на ячейку массива? Прямолинейно, но удовлетворяет всем вашим требованиям.

[Pphantom]

Из картинки, пожалуй, сразу же следует, что можно искать либо локальные максимумы (и считать их центрами кластеров), либо локальные минимумы (и считать их границами). При желании получить только "выдающиеся" кластеры - предварительно сделать медианное сглаживание данных.

Что сие значит:

monst92 в сообщении #1377911 писал(а):

2. Массив Input[N] недифференцируемый по определению (поиск extr - несостоятельно).

?

[monst92]

Цитата:

По одному кластеру на ячейку массива? Прямолинейно, но удовлетворяет всем вашим требованиям.

Каждая i-я ячейка Output массива должна содержать номер кластера, к которому относится можно отнести i-ю ячейку Input массива.

Цитата:

Что сие значит:

Функция негладкая. Локальные максимумы могут содержать шум и сильные относительные выбросы, например:



Связываться с аппроксимацией пока нет желания, м.б. существует более простой способ. Учитывая сильный разброс области значений исходной функции (5 порядков), интуитивно кажется целесообразным подсчитать "плотность" центров кластеров. Вопрос как это формализовать.

[realeugene]

monst92 в сообщении #1377962 писал(а):

Каждая i-я ячейка Output массива должна содержать номер кластера, к которому относится можно отнести i-ю ячейку Input массива.

Ну и пропишите в i-ю ячейку i.

monst92 в сообщении #1377962 писал(а):

Функция негладкая. Локальные максимумы могут содержать шум и сильные относительные выбросы, например:

У вас должны быть некоторые модели кластера и шума.

[provincialka]

Народ, видимо, понял, что значат эта картинка. А я так нет. Что откладывается по высоте?

И ещё: кластер должен быть отрезком числового ряда или может содержать элементы "вперемешку"?

[monst92]

По $\mathbf{Y}$ - безразмерная величина.
При наличии локального максимума (который аналитически определить довольно трудно в силу п.2 условий) я полагаю, что можно идентифицировать сформировавшийся кластер.
Если я Вас правильно понял - да, отрезок (или точка) числового ряда и "вперемешку" идти не могут (после того как кластер $\boldsymbol{N}$ сформировался - номер следующего кластера не может быть меньше $\boldsymbol{N+1}$ и межкластерные расстояния будут рассчитываться по оси $\mathbf{X}$).

[Pphantom]

monst92 в сообщении #1378237 писал(а):

При наличии локального максимума (который аналитически определить довольно трудно в силу п.2 условий) я полагаю, что можно идентифицировать сформировавшийся кластер.

Его не надо определять аналитически, и определить его более чем легко. Другое дело, что вас такой кластер может по каким-то критериям не устраивать, но тогда надо сформулировать критерии, по которым один максимум считается центром кластера, а другой - нет. Из картинки пока что следует, что вам не нравятся единичные случайные отскоки, но они убираются медианным сглаживанием.

[MGM]

Ищите по ключевому слову 1D K-means algorithm.

Алгоритм очень древний.

При выбре числа кластеров К можете сформулировать какие-то дополнительные условия или ограничения.
Через энтропию или чего-то еще. Но в принципе, такие задачи так не ставятся. Нужна "сверх задача" вашей кластеризации. То есть для чего вы такую задачу собираетесь использовать.
Даже если вы считаете, что всего лишб хотите сдать курсовую.

[Dan B-Yallay]

Задача родственная Peak Calling. Там есть куча готовых реализаций, но насколько знаю, они все привязаны к биологии/генам.

https://en.wikipedia.org/wiki/Peak_calling

Поиск пиков в данных ChiP-Seq