Ищу алгоритм деления неравномерных данных

[Igors]

Добрый день

Столкнулся с проблемой деления неравномерно распределенных данных. Пример для одномерного случая. Пусть есть N точек отсортированных по их значениям (допустим от 0 до 200). "Неравномерность" выглядит так

интервал значений                кол-во точек в интервале
-------------------------------------------------------------
0..1                                      1
1..2                                      0
2..3                                      0
3..4                                      1
4..5                                      1
..
100..101                                  0               // и.т.д - интервалы почти пустые
101..102                                  10000           // бум!
102..103                                  1               // опять пошли почти пустые интервалы
103..104                                  1                  
...
199..200                                  0

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

Если Вы знаете формулировку в теории - подскажите, буду благодарен

[spectre71]

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

По длине чего? Общего интервала(0..200 в данном примере)?

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

Что значит глубина разбиения. Кол-во интервалов?

Делить по числу точек - нехорошо из др. соображений.

Не понятно что нужно делить, требует пояснения.

[Igors]

Задача построить дерево, конкретно BSP дерево (да, то самое что мы обсуждали в др. нитке). У дерева есть ветки и листья. Ветка хранит 2 указателя на children, каждый из которых может быть веткой или листом. Также ветка хранит divider - значение как делить (по расстоянию). Листья хранят указатели на конечные данные - для простоты пусть это одномерные значения. Пример: найти все точки в интервале [10..11].

- проверяем пересекает ли интервал общий (0..200)
- смотрим корень, это ветка разбивающая на 2 интервала (0..100) и (100..200). Значит идем по первой ветке.
- продолжаем спуск пока не оказались в листе. Здесь просто перебираем все точки принадлежащие листу

Глубина деления есть число шагов спуска. Деление останавливается если число данных в листе достаточно мало. Однако есть точки которые полностью совпадают (напр. 100 точек в 1 месте). Такое можно делить бесконечно но безуспешно. Поэтому глубина деления ограничена.

Одномерный случай приведен просто для простоты изложения - конечно для него проще сделать двоичный поиск по сортированному массиву. Но это не проходит для 2 и более измерений.

[vaprele07]

"Стремящийся поиск" что-то в этом роде.

[spectre71]

Опять не совсем понятно.
Для начала приведи пример чисто для 1-мерного случая. Пример данных, процесс деления.
Затем уже будем разбирать многомерный(сколько измерений, есть ограничение?)
======

Если все же я правильно понял, то для одномерного случая:

интервал значений                кол-во точек в интервале
-------------------------------------------------------------
0..1                                      1
1..2                                      0
2..3                                      0
3..4                                      1
4..5                                      1
..
100..101                                  0               // и.т.д - интервалы почти пустые
101..102                                  10000           // бум!
102..103                                  1               // опять пошли почти пустые интервалы
103..104                                  1                 
...
199..200                                  0

Указываем не кол-во точек в интервале, а накопленные суммы:

интервал значений                кол-во точек в интервале
-------------------------------------------------------------
0..1                                      1
1..2                                      1
2..3                                      1
3..4                                      2
4..5                                      3
..
100..101                                  3               // и.т.д - интервалы почти пустые
101..102                                  10003           // бум!
102..103                                  10004               // опять пошли почти пустые интервалы
103..104                                  10005                 
...
199..200                                  10005

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

[Igors]

У меня всегда 3 измерения (x. y. z). Но задача столь же актуальна для 2-х. Представим напр огромную карту местности, почти пустую, но с маленьким участком "город". Там и сосредоточено 99.99% всех данных, остальное огромная "пустыня". В этом случае деление пополам (кстати так делает и Qt) плохо - мы будем лупить и лупить большие площади, не останется памяти/ресурсов на город

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

Делал, получается неважно. Во-первых для 2-х и более измерений нужно все время сортировать точки при смене оси деления - не смертельно но неприятно. А главное - резко нарастает глубина спуска, такое "теоретически правильное" дерево работает медленно. Пример: ищем точку 1.5 (для данных описанных выше). Спуск будет выглядеть так:

1) (0 - 101.5)(101.5 - 200)
2) (0 - 101.25)(101.25 - 101.5)
3) (0 - 101.125)(101.123 - 101.25)
4) (0 - 101.120)..
5) (0 - 101.115)..
6) (0 - 101.110)..
... и.т.д

В 2-х и 3-х измерениях это становится невыносимым - нужно добираться по каждой из осей. Поэтому хотелось бы "локализовать" области с большой плотностью данных и заниматься ими отдельно.

[SimpleSunny]

Области с большей плотностью данных можно выделить кластерным анализом.

Конечная задача какая? Найти все точки в заданном интервале?

[spectre71]

Пока рассмотрим только одномерный случай.
Диапазон 0-99
Имеем 12 точек  {0, 0, 4, 15, 15, 15, 15, 33, 33, 48, 75, 76}

1) Имеем равномерные интервалы размером 10 с полной разбивкой, тогда получаем
===
интервал   точек  суммы
===
1                3         3
2                4         7
3                0         7
4                2         9
5                1         10
6                0         10
7                0         10
8                2         12
9                0         12
10              0          12
===
Бинарным поиском по суммам легко сделать разбиение  на два под-интервала.
Например 50/50 - ищем сумму 12/2 = 6 :
[0-19] - 7 точек;
[20-99] - 5 точек;

2) Имеем равномерные интервалы размером 10 с не полной разбивкой - выкинуты вернее не внесены пустые.
получаем
===
интервал   точек  суммы
===
1                3         3
2                4         7
4                2         9
5                1         10
8                2         12
===
Все точно так же, только меньше мусора

3) Имеем неравномерные интервалы например минимум 2 точки с минимальным размером 10 и кратным 10
получаем

===
интервал   точек  суммы
===
0  - 9              3         3
10-19              4         7
30-39              2         9
40-80              3         12
===

[Igors]

Конечная задача какая? Найти все точки в заданном интервале?

Конечная задача с помощью построенного дерева находить полигоны на пути луча. Чтобы не вдаваться в предметную область, проще сказать что нужны:

а) хорошо сбалансированное дерево
б) быстрый спуск по нему

Как я пытался объяснить выше, при неравномерном распределении данных "а" и "б" конфликтуют

Области с большей плотностью данных можно выделить кластерным анализом.

Так я об этом и спрашиваю 

Бинарным поиском по суммам легко сделать разбиение  на два под-интервала.
Например 50/50 - ищем сумму 12/2 = 6 :
[0-19] - 7 точек;
[20-99] - 5 точек;

Если у меня точки отсортированы по значению, то проще взять среднее между точками N/2 и N/2 + 1. Это проверялось, такое дерево работает медленно (и строится тоже). Хотелось бы вот так (* большая плотность, - маленькая)

    1             2                         3
             |*****|
---------|*****|-----------------------------------
             |*****|

Заметим, что интервалы не равны ни по расстоянию, ни по числу данных

[SimpleSunny]

Нужен алгоритм кластер-анализа?
Можно почитать тут (http://www.nsu.ru/matlab/MatLab_RU/fuzzylogic/book2/1/subclust.asp.htm) изложен кратко кластер анализ с удалением. Центры кластеров с его окрестностями и будут искомыми скоплениями. Если надо могу исходник из Matlab скинуть.

А можно ли дробить и\или объединять интервалы? Чтобы можно было оперировать сбалансированными (по количеству точек) интервалами.

[spectre71]

Нужен алгоритм кластер-анализа?
Можно почитать тут (http://www.nsu.ru/matlab/MatLab_RU/fuzzylogic/book2/1/subclust.asp.htm) изложен кратко кластер анализ с удалением. Центры кластеров с его окрестностями и будут искомыми скоплениями. Если надо могу исходник из Matlab скинуть.

А можно ли дробить и\или объединять интервалы? Чтобы можно было оперировать сбалансированными (по количеству точек) интервалами.

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

[spectre71]

Бинарным поиском по суммам легко сделать разбиение  на два под-интервала.
Например 50/50 - ищем сумму 12/2 = 6 :
[0-19] - 7 точек;
[20-99] - 5 точек;

Если у меня точки отсортированы по значению, то проще взять среднее между точками N/2 и N/2 + 1. Это проверялось, такое дерево работает медленно (и строится тоже). Хотелось бы вот так (* большая плотность, - маленькая)

    1             2                         3
             |*****|
---------|*****|-----------------------------------
             |*****|

Заметим, что интервалы не равны ни по расстоянию, ни по числу данных

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

а) хорошо сбалансированное дерево
б) быстрый спуск по нему

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

[ieroglif]

мне кажется, что хоть тема и хорошая, но более подробно она обсуждалась (обсуждается и будет обсуждаться) на gamedev.ru

[Igors]

Нужен алгоритм кластер-анализа?
Можно почитать тут (http://www.nsu.ru/matlab/MatLab_RU/fuzzylogic/book2/1/subclust.asp.htm) изложен кратко кластер анализ с удалением. Центры кластеров с его окрестностями и будут искомыми скоплениями. Если надо могу исходник из Matlab скинуть.

Спасибо, изучаю/вникаю

А можно ли дробить и\или объединять интервалы? Чтобы можно было оперировать сбалансированными (по количеству точек) интервалами.

Ограничений нет, все данные на руках, можно оперировать чем угодно - но нужны идеи что делать (или теория)

[Igors]

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

а) хорошо сбалансированное дерево
б) быстрый спуск по нему

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

Хорошо, давайте попробуем сформулировать кратко, не беда если повторюсь

1) Данные распределены неравномерно, в относительно маленьких участках (от общего пространства) может быть сконцентрирована их подавляющая масса. К слову сказать, достигается это очень просто: напр сделал пользователь какую-то модель вазы. 100 тысяч точек и она влазит в кубик 1х1х1. А потом сделал пол для нее - вот в нем аж 10 точек, зато размер 1000x1000 - готово!

2) Делить по размеру (расстоянию) плохо, вся сила дерева уходит на деление больших площадей

3) Делить по числу точек - тогда "дерево сбалансировано" но другая беда - медленный спуск (и медленное построение)

4) Возникает мысль разделить области с большой и малой плотностью.

3-й вариант и был с неравными интервалами.

Не очень понятно

>> Имеем неравномерные интервалы например минимум 2 точки с минимальным размером 10 и кратным 10
получаем

Да, я могу строить любые гистограммы (если я правильно употребляю этот термин), ну и что с ними делать? Напр. получил что-то такое (число данных в интервалах)

1, 5, 10, 100, 1, 200, 1, 2. 1000, 500, и.т.д

Как выбрать место деления? Из каких соображений выбирать длину интервалов?