Как найти наибольший общий делитель с округлением?

Question

[Сергей Соколов]

Пользователь настукивает короткий ритмический рисунок из нот всего двух длительностей: x или 2x. Примерно как азбука Морзе, только музыкально, в темпе. В итоге получен массив длительностей нот в миллисекундах, например:
[145,160,112,170,281,292,258,305,257]

график

Как эти длительности классифицировать в ноты кратных длительностей? Как заменить на "1" для коротких x и на "2" для длинных 2x, чтобы для примера выше получилось
[1,1,1,1,2,2,2,2,2]

Наивный способ не работает

const a = [145,160,112,170,281,292,258,305,257];
const min = Math.min(...a); // 112
a.map(n => Math.round(n / min)) // [ 1, 1, 1, 2, 3, 3, 2, 3, 2 ]

Этот вопрос только про бинарную классификацию x || 2x.

Далеко потом, уже другим способом, может быть будет интересно суметь разбирать «мелодию» без самых коротких нот, состоящуя только из кратных 2x и 3x. Или ещё сложнее – полиритмия с рациональными дробями: 4/4 затем в этом же темпе 6/4 или 5/4. Но это не сейчас.

Upd. реализация решения Владимир Олохтонов на JS

spoiler

const AB = data => {
  
  const A = [Math.min(...data)];
  const B = [Math.max(...data)];
  
  const mean = arr => arr.reduce((a,b) => a + b, 0) / arr.length;

  data.forEach(n => {
    if (Math.abs(mean(A) - n) <= Math.abs(mean(B) - n))
      A.push(n);
    else B.push(n);
  });
  
  return [A.slice(1), B.slice(1)];
}
 
AB([145,160,112,170,281,292,258,305,257])

/*
[[145,160,112,170],[281,292,258,305,257]]
*/

Answer 1

[Andrey Dugin]

Можно воспользоваться одним из алгоритмов кластеризации в scikit-learn, например KMeans:

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> notes = [145, 160, 112, 170, 281, 292, 258, 305, 257]
>>> notes = np.array(notes).reshape(-1, 1)
>>> KMeans(n_clusters=2).fit_predict(notes)
array([0, 0, 0, 0, 1, 1, 1, 1, 1], dtype=int32)

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

>>> KMeans(n_clusters=2).fit_predict(notes)
array([1, 1, 1, 1, 0, 0, 0, 0, 0], dtype=int32)

Answer 2

[Владимир Олохтонов]

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

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

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

Comments

[Сергей Соколов]

как думаете, Фурье тут нет места?

[Сергей Соколов]

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

[Владимир Олохтонов]

Сергей Соколов, kmeans — это очень простой алгоритм, там кода на 10 строк.

times = [...]
first_cluster, second_cluster = [min(times)], [max(times)]

for t in times:
    if abs(mean(first_cluster) - t) <= abs(mean(second_cluster) - t):
        first_cluster.append(t)
    else:
        second_cluster.append(t)

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

[Владимир Олохтонов]

Сергей Соколов, про преобразование Фурье ничего не могу сказать, зияющая дыра в моём образовании даёт о себе знать :)

Вот разве что симпатичный гайд: www.jezzamon.com/fourier

Answer 3

[EVGENY T.]

Мне кажется, тут нужен кластер-анализ.

Comments

[Сергей Соколов]

Это оверкилл, кмк, и надо задать ожидаемое количество кластеров – можно получить как 2, так и больше при желании.

Предположим, точно известно, что кластеров всего 2. Азбука Морзе: точка или тире. Как решить задачу, не усложняя излишне?

[EVGENY T.]

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