Как разбить числа по группам так, чтобы в группах находились близкие по значению числа?

Question

[weranda]

Приветствую.

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

Пример (разбиваем список на три группы):

[исходные числа] >>> [разбитые по группам числа]

[1,2,3] >>> [1][2][3]
[1,2,3,4,5,6] >>> [1,2][3,4][5,6]
[10,30,60,90,150] >>> [10,30][60,90][150]
[10,30,30,35] >>> [10][30,30][35]
[1,50,250,350] >>> [1][50][250,350]
[1,2,3,500,550,650,650] >>> [1,2,3][500,550][650,650]

Числа могут быть любыми.

Comments

[Adamos]

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

[weranda]

Adamos, Не, это не то.

[Adamos]

Чуть посложнее: найти (кол-во групп - 1) самых больших расстояний между цифрами и поделить по ним.

Answer 1

[Mercury13]

Это называется кластеризация, и самый ходовой метод для неё — K-means.

Comments

[weranda]

Как я понял, это метод нужен для кластеризации данных минимум с двумя точками/числами (многомерные данные). Можно этот метод применить к одномерному списку?

[Александр Скуснов]

Ничего подобного. Есть понятие точки. Это может быть число, а если несколько - то это многомерный вектор.
В любом случае считается расстояние (норма) между точками.

Answer 2

[Wataru]

Надо ввести какую-то метрику - какая-то числовая оценка, которая говорила бы вам, почему [[1,2],[3,4],[5,6]] лучше чем [[1,2,3,4],[5],[6]]. Например, можно взять максимальную разность двух чисел в любой группе. Или сумму квадратов расстояний от всех чисел до среднего в их группе. Или минимальное расстояние между числами в разных группах (это надо максимизировать).

Потом можно применять какой-то из известных методов кластеризации, в зависимости от выбранной метрики. В случае одного измерения, как у вас (просто числа) можно еще применить и динамическое программирование. Этот метод работает для практически любой вменяемой метрики. Считайте функцию F(n,k) - лучшая возможная метрика если первые n чисел разбить на k групп. Для пересчета надо перебрать, сколько чисел идет в последнюю группу (i), и пересчитать метрику на основе F(n-i, k-1). из всех вариантов выбрать лучший.

Answer 3

[Александр Скуснов]

Пример из MatLab (через двоичные деревья) (кластерный анализ)

PD = pdist(Data);             % (Data,'cityblock');
Z = linkage(PD,'average');   % (PD);
dendrogram(Z)

c = cophenet(Z,PD)
%I = inconsistent(Z);

T = cluster(Z,'cutoff',cut);
% или T = cluster(Z,'maxclust',nClust);