weranda
@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]

Числа могут быть любыми.
  • Вопрос задан
  • 96 просмотров
Пригласить эксперта
Ответы на вопрос 3
@Mercury13
Программист на «си с крестами» и не только
Это называется кластеризация, и самый ходовой метод для неё — K-means.
Ответ написан
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Надо ввести какую-то метрику - какая-то числовая оценка, которая говорила бы вам, почему [[1,2],[3,4],[5,6]] лучше чем [[1,2,3,4],[5],[6]]. Например, можно взять максимальную разность двух чисел в любой группе. Или сумму квадратов расстояний от всех чисел до среднего в их группе. Или минимальное расстояние между числами в разных группах (это надо максимизировать).

Потом можно применять какой-то из известных методов кластеризации, в зависимости от выбранной метрики. В случае одного измерения, как у вас (просто числа) можно еще применить и динамическое программирование. Этот метод работает для практически любой вменяемой метрики. Считайте функцию F(n,k) - лучшая возможная метрика если первые n чисел разбить на k групп. Для пересчета надо перебрать, сколько чисел идет в последнюю группу (i), и пересчитать метрику на основе F(n-i, k-1). из всех вариантов выбрать лучший.
Ответ написан
@AlexSku
Программист по автоматике
Пример из MatLab (через двоичные деревья) (кластерный анализ)
PD = pdist(Data);             % (Data,'cityblock');
Z = linkage(PD,'average');   % (PD);
dendrogram(Z)

6151d125e46d7282319022.png
c = cophenet(Z,PD)
%I = inconsistent(Z);

T = cluster(Z,'cutoff',cut);
% или T = cluster(Z,'maxclust',nClust);
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы