Как классифицировать числовой ряд?

Question

[alexdora]

Дано:
1. Ряд целых положительных чисел
2. Количество чисел неопределенно
3. Числа могут в ряду повторяться

Задача разбить числа на 3 группы. Примером проще:
1,2,7,8,30,100,500,667,900,3,4
Итого:
[1,2,3,4,7,8,30,100] [500,667] [900]

Вообщем-то задача предполагает разбить числа на три группы: маленькие, средние и большие.

Самое важно что в конкретном примере глазами, да и формулой от максимума в целом не сложно найти.
Но когда ряды идут а-ля: [1 1 1 1 1 2 2 2 2 3 5 10 20 20 25 35 45 96 97 97 98 99 100 100 101 102 103 999 1000 1001 9000 9500] что-то простые способы оказались бестолковые.

Очень долго копался в этой теме (хотя вышку знаю очень плохо ч.к совсем не знаю). Мне тут chatGPT предложил следующие варианты решения проблемы, кроме 7,8 он писал код. Я его правил в рамках своих возможностей, но так и не добился положительных результатов.

1. Логистическая регрессия.
2. Линейные модели.
3. Решающие деревья.
4. Метод ближайших соседей.
5. Наивный байесовский классификатор.
6. Метод опорных векторов.
7. Бустинг.
8. Нейронные сети.
9. Алгоритм K-средних.
10. Алгоритм адаптивного бустинга.

PS: Указал языки программирования т.к мне нужно сделать функцию, подойдет любой язык. Буду рад если хотя бы укажите направление. Заранее благодарю.

Answer 1

[Wataru]

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

Все-таки все эти методы кластеризации разработаны для более общего случая. А у вас тут данные одномерные и численные уже - так что все совсем просто.

Во-первых, данные надо отсортировать, если уже не. А дальше у вас тут 2 переменные - (i,j) - первый и последний элемент в средней группе.i>0,j<n-1.

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

Но вообще можно, наверно, просто взять 2 максимальных промежутка между соседними числами и по ним разделить. В примере выше этот метод отлично разбивает на 3 группы: 1-103, 999-1001, 9000-9500

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

Comments

[alexdora]

Спасибо больше за развернутый ответ, ссылку изучил. Но как сказал выше не так силен в математике.

Покрутил, все до чего додумался благодаря ответу:

сортируется вся числовая последовательность по возрастанию и с конца начинаешь делить на предыдущее число. Я разберу более короткую последовательность чисел:

1,2, 20, 30, 40, 60, 100

100/60 = 1.66 < 2 значит 100 похожа на 60
---
100/40 = 2.5 > 2, новая группа
Далее перепрыгиваем к 40
40/30
40/20 == <2
---
40/2 > 2 - открывается 3-я группа. И по-сути все что ниже 40 автоматом попадает в третью группу

Итого:

[1,2] [20,30,40] [60,100]

Единственное тут надо будет что если не получилось 3 группы запустить цикл заново, но уменьшить 2 например до 1.9. И уменьшать его пока не получится 3 группы. Придется еще конечно проверку нарисовать чтоб не искать группы если числа одинаковые. Но решение вроде очень близкое.

Если не затруднит – прокомментируйте в правильную сторону иду или нет.

[Wataru]

alexdora, Не надо циклов перезапускать. Посчитайте вот эти вот отношения (100/60, 60/40 и т.д), и найдите 2 максимума.

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

Еще можно не отношения элементов брать, а просто абсолютные разности.

[alexdora]

Wataru,
100/60 = 1.66
60/40 = 1.5

Максимум 1.66

2 итерация: 60/40 = 1.5, 40/30 = 1.33; Максимум 1.5
3 итерация 40/30 = 1.33, 30/20 = 1.5; Максимум 1.5

Только я не понимаю как в дальнейшем от этих значений сделать группы.

[Wataru]

alexdora, вот вы нашли 2 индекса отсортируйте их. До первого - первая группа, до второго - вторая. Со второго до конца - третья.

[alexdora]

Берем последовательность из поста:

103, 999 1000 1001 9000 9500

9500/9000 = 1.0555~
9000/1001 = 8,9910
1001/1000 = 1,001
1000/999 = 1,001~
999/103 = 9,69

Сортируем по первым двум делениям.
Первая группа x < 1.0555
Вторая группа 8.9910 >= x >= 1.05
Третья все остальное

Жирным я выделил первую группу, что не совсем верно или я неправильно вас понял.

[Wataru]

alexdora,

103, 999 1000 1001 9000 9500

9500/9000 = 1.0555~
9000/1001 = 8,9910
1001/1000 = 1,001
1000/999 = 1,001~
999/103 = 9,69

Я вижу тут явных 2 максимума: 999/103 и 9000/1001. Если взять их, то это индексы 1 и 4 (считая с нуля). Значит числа на индексах 0..0, 1..3 и 4..5 - вот три группы. 103, 999-1001 и 9000-9500.

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

[alexdora]

Wataru, это гениально спасибо большое что за ваше терпение и что потратили время на объяснение. Мне важно было именно понять, а не увидеть готовый код реализации.