2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Кластеризация вектора
Сообщение23.02.2019, 12:52 


13/02/18
13
Всем привет.

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

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

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

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

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

Изображение

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение23.02.2019, 13:20 


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

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение23.02.2019, 13:21 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение23.02.2019, 16:57 


13/02/18
13
Цитата:
По одному кластеру на ячейку массива? Прямолинейно, но удовлетворяет всем вашим требованиям.


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


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


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

Изображение

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

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение23.02.2019, 20:34 


27/08/16
9426
monst92 в сообщении #1377962 писал(а):
Каждая i-я ячейка Output массива должна содержать номер кластера, к которому относится можно отнести i-ю ячейку Input массива.
Ну и пропишите в i-ю ячейку i.

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

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение25.02.2019, 00:36 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Народ, видимо, понял, что значат эта картинка. А я так нет. Что откладывается по высоте?

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

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение25.02.2019, 07:16 


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

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение25.02.2019, 11:46 
Заслуженный участник


09/05/12
25179
monst92 в сообщении #1378237 писал(а):
При наличии локального максимума (который аналитически определить довольно трудно в силу п.2 условий) я полагаю, что можно идентифицировать сформировавшийся кластер.
Его не надо определять аналитически, и определить его более чем легко. Другое дело, что вас такой кластер может по каким-то критериям не устраивать, но тогда надо сформулировать критерии, по которым один максимум считается центром кластера, а другой - нет. Из картинки пока что следует, что вам не нравятся единичные случайные отскоки, но они убираются медианным сглаживанием.

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение16.05.2019, 18:33 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Кластеризация вектора
Сообщение17.05.2019, 01:10 
Заслуженный участник
Аватара пользователя


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

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

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

Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group