Алгоритм для генерации числовой иерархии понятия
У меня есть несколько числовых наборов данных, для которых я должен создать иерархию понятия. На данный момент я делал это вручную путем наблюдения данных (и соответствующая линейная диаграмма). На основе моей интуиции я создал некоторые приемлемые иерархии.
Это походит на задачу, которая может быть автоматизирована. Кто-либо знает, существует ли алгоритм для генерации иерархии понятия для числовых данных?
Для предоставления примера у меня есть следующий набор данных:
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
для которого я создал следующую иерархию:
- САМЫЙ НИЗКИЙ (<1000)
- НИЗКО (1000 - 2500)
- НОСИТЕЛЬ (2501 - 7500)
- ВЫСОКО (7501 - 30000)
- САМЫЙ ВЫСОКИЙ (> 30000)
6 ответов
Может быть, вам нужен алгоритм кластеризации ?
Цитата из ссылки:
Кластерный анализ или кластеризация - это назначение набор наблюдений в подмножества (называемые кластерами), так что наблюдения в одном и том же кластере в некотором смысле похожи. Кластеризация - это метод обучения без учителя и общий метод анализа статистических данных , используемый во многих областях
Jenks Natural Breaks - очень эффективная схема одномерной кластеризации: http://www.spatialanalysisonline.com/OUTPUT/html/Univariateclassificationschemes.html # _Ref116892931
Как уже отмечалось в комментариях, это очень похоже на k-means. Однако мне показалось, что это еще проще реализовать, особенно вариант, найденный в Картографии Бордена Дента: http://www.amazon.com/Cartography-Thematic-Borden-D-Dent/dp/0697384950
Я думаю, вы ищете что-то вроде дискретизации данных , которое довольно распространено в ИИ для преобразования непрерывных данных (или дискретных данных с таким большим количеством классов, что они могут быть громоздкими) в дискретные классы.
Я знаю, что Weka использует метод MDL Файяда и Ирани, а также метод MDL Кононеко, я посмотрю, смогу ли я откопать некоторые ссылки.
Мне было интересно.
Очевидно, то, что вы ищете, - это чистый перерыв.Итак, прежде чем приступить к изучению сложных алгоритмов, вы, возможно, можете представить себе дифференциальный подход.
[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 категории , похоже, не имеют большого смысла.
Это всего лишь одномерная проблема, поэтому может быть решение динамического программирования. Предположим, что имеет смысл взять точки в отсортированном порядке, а затем сделать n-1 разрезов для создания n кластеров. Предположим, что вы можете записать штрафную функцию f () для каждого кластера, такую как дисперсия внутри кластера или расстояние между min и max в кластере. Затем вы можете минимизировать сумму f (), оцениваемую в каждом кластере. Работайте с одной точки слева направо. В каждой точке для 1 .. # кластеров - 1 найдите лучший способ разбить точки на данное количество кластеров и сохранить стоимость этого ответа и местоположение его самого правого разбиения. Вы можете решить это для точки P и размера кластера c следующим образом: рассмотрите все возможные разрезы слева от P. Для каждого разреза добавьте f (), оцененное на группе точек справа от разреза, к (сохраненной) стоимости лучшего решения для размера кластера c-1 в точке слева от разреза.После того, как вы проложили свой путь к крайнему правому краю, проделайте тот же трюк еще раз, чтобы выработать лучший ответ для размера кластера c, и используйте сохраненные местоположения крайних правых разделений, чтобы восстановить все разделения, которые дают этот лучший ответ.
На самом деле это может быть дороже, чем вариант с k-средними, но имеет то преимущество, что гарантирует поиск лучшего глобального ответа (для выбранной вами функции f () при этих предположениях).