2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Кластеризация вектора
Сообщение23.02.2019, 12:52 
Всем привет.

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

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

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

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

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

Изображение

 
 
 
 Re: Кластеризация вектора
Сообщение23.02.2019, 13:20 
monst92 в сообщении #1377911 писал(а):
1. Количество кластеров неизвестно.
2. Массив Input[N] недифференцируемый по определению (поиск extr - несостоятельно).
3. Кластеры не должны перекрываться (если такое возможно), возможно потребуется ввести доп. функцию для их сепарации.
По одному кластеру на ячейку массива? Прямолинейно, но удовлетворяет всем вашим требованиям.

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

Что сие значит:
monst92 в сообщении #1377911 писал(а):
2. Массив Input[N] недифференцируемый по определению (поиск extr - несостоятельно).
?

 
 
 
 Re: Кластеризация вектора
Сообщение23.02.2019, 16:57 
Цитата:
По одному кластеру на ячейку массива? Прямолинейно, но удовлетворяет всем вашим требованиям.


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


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


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

Изображение

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

 
 
 
 Re: Кластеризация вектора
Сообщение23.02.2019, 20:34 
monst92 в сообщении #1377962 писал(а):
Каждая i-я ячейка Output массива должна содержать номер кластера, к которому относится можно отнести i-ю ячейку Input массива.
Ну и пропишите в i-ю ячейку i.

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

 
 
 
 Re: Кластеризация вектора
Сообщение25.02.2019, 00:36 
Аватара пользователя
Народ, видимо, понял, что значат эта картинка. А я так нет. Что откладывается по высоте?

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

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

 
 
 
 Re: Кластеризация вектора
Сообщение25.02.2019, 11:46 
monst92 в сообщении #1378237 писал(а):
При наличии локального максимума (который аналитически определить довольно трудно в силу п.2 условий) я полагаю, что можно идентифицировать сформировавшийся кластер.
Его не надо определять аналитически, и определить его более чем легко. Другое дело, что вас такой кластер может по каким-то критериям не устраивать, но тогда надо сформулировать критерии, по которым один максимум считается центром кластера, а другой - нет. Из картинки пока что следует, что вам не нравятся единичные случайные отскоки, но они убираются медианным сглаживанием.

 
 
 
 Re: Кластеризация вектора
Сообщение16.05.2019, 18:33 
Аватара пользователя
Ищите по ключевому слову 1D K-means algorithm.

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

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

 
 
 
 Re: Кластеризация вектора
Сообщение17.05.2019, 01:10 
Аватара пользователя
Задача родственная Peak Calling. Там есть куча готовых реализаций, но насколько знаю, они все привязаны к биологии/генам.

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

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

Изображение

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group