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

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 

alt text http://i40.tinypic.com/fd7xxu.jpg

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

• низшем (< 1000)
• LOW (1000 - 2500)
• MEDIUM (2501 - 7500)
• HIGH (7501 - 30000)
• HIGHEST (> 30000)

Answer 1

Может быть, вам нужен clustering алгоритм?

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

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

Answer 2

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

Я знаю, что Weka использует Fayyad & Метод MDL Ирана, а также метод MDL от Kononeko, я посмотрю, смогу ли я выкопать некоторые ссылки.

Answer 3

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

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

Answer 4

Genetic hierarchical clustering algorithm

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

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

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