Алгоритм генерации числовой концепции иерархии

Question

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

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

---

Чтобы привести пример, у меня есть следующий набор данных:

Bangladesh     521
Brazil         8295
Burma          446
China          3259
Congo          2952
Egypt          2162
Ethiopia       333
France         46037
Germany        44729
India          1017
Indonesia      2239
Iran           4600
Italy          38996
Japan          38457
Mexico         10200
Nigeria        1401
Pakistan       1022
Philippines    1845
Russia         11807
South Africa   5685
Thailand       4116
Turkey         10479
UK             43734
US             47440
Vietnam        1042

альтернативный текст http://i40.tinypic.com/fd7xxu.jpg

, для которого я создал следующую иерархию:

• НИЗКИЙ (<1000) </li>
• НИЗКИЙ (1000 - 2500)
• СРЕДНИЙ (2501 - 7500)
• ВЫСОКИЙ (7501 - 30000)
• HIGHEST (> 30000)

Answer 1

Может быть, вам нужен алгоритм кластеризации ?

Цитирование по ссылке:

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

Answer 2

Jenks Natural Breaks - очень эффективная одномерная схема кластеризации: http://www.spatialanalysisonline.com/OUTPUT/html/Univariateclassificationschemes.html#_Ref116892931

Как отмечалось в комментариях, это очень похоже на k-средних. Тем не менее, я обнаружил, что это еще проще реализовать, в частности вариацию, найденную в картографии Бордена Дента: http://www.amazon.com/Cartography-Thematic-Borden-D-Dent/dp/0697384950

Answer 3

Я думаю, что вы ищете что-то похожее на дискретизацию данных , которое довольно распространено в ИИ для преобразования непрерывных данных (или дискретных данных с таким большим количеством классов, чтобы быть громоздкими) в дискретные классы.

Я знаю, что Weka использует метод MDL Файяда и Ирана, а также метод MDL Кононеко, я посмотрю, смогу ли я найти некоторые ссылки.

Answer 4

Это только одномерная задача, поэтому может быть решение с динамическим программированием. Предположим, что имеет смысл брать точки в отсортированном порядке, а затем делать n-1 разрезы для генерации n кластеров. Предположим, что вы можете записать штрафную функцию f () для каждого кластера, например, дисперсию внутри кластера или расстояние между минимальным и максимальным в кластере. Затем вы можете минимизировать сумму f (), вычисленную в каждом кластере. Работайте из одной точки за раз, слева направо. В каждой точке, для кластеров 1 .. # - 1, найдите наилучший способ разбить точки до такого количества кластеров и сохранить стоимость этого ответа и местоположение его самого правого разбиения. Вы можете решить эту проблему для точки P и размера кластера c следующим образом: рассмотрите все возможные разрезы слева от P. Для каждого разреза добавьте f (), оцененную по группе точек справа от разреза, к (сохраненной) стоимости лучшего решения для размера кластера c-1 в точке слева от разреза. Как только вы проделали свой путь к крайнему правому краю, сделайте тот же трюк еще раз, чтобы найти лучший ответ для размера кластера c, и используйте сохраненные местоположения крайних правых разбиений, чтобы восстановить все разбиения, которые дают этот лучший ответ.

Это может быть на самом деле дороже, чем вариант с k-средних, но имеет преимущество в том, что дает возможность найти лучший глобальный ответ (для выбранного вами f () согласно этим предположениям).

Answer 5

Мне было интересно.

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

[1, 1.2, 4, 5, 10]

[20%, 333%, 25%, 100%]

Теперь, в зависимости от количества искомых перерывов, нужно выбрать их:

2 categories: [1, 1.2] + [4, 5, 10]
3 categories: [1, 1.2] + [4, 5] + [10]

Я не знаю о вас, но, на мой взгляд, это кажется естественным, и вы даже можете использовать пороговый подход, говоря, что изменение меньше x% не стоит рассматривать сокращение.

Например, здесь 4 categories, кажется, не имеет особого смысла.

Answer 6

Алгоритм генетической иерархической кластеризации