Algorithme pour générer une hiérarchie de concepts numériques

Question

J'ai quelques ensembles de données numériques dont j'ai besoin pour créer une hiérarchie de concepts. Pour l'instant, je l'ai fait manuellement en observant les données (et un graphique linéaire correspondant). Basé sur mon intuition, j'ai créé des hiérarchies acceptables.

Cela semble être une tâche qui peut être automatisée. Est-ce que quelqu'un sait s'il existe un algorithme pour générer une hiérarchie conceptuelle pour les données numériques?

---

Pour donner un exemple, je l'ensemble de données suivantes:

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

pour lequel j'ai créé la hiérarchie suivante:

• PLUS BAS (< 1000)
• LOW (1000-2500)
• MOYEN (2501-7500)
• HIGH (7501-30000)
• PLUS HAUT (> 30000)

Answer 1

Peut-être que vous avez besoin d'un algorithme clustering?

Je cite le lien: Analyse

de cluster ou cluster est l'attribution d'un ensemble d'observations en sous-ensembles (clusters appelés) de telle sorte que observations dans le même groupe sont similaires dans un certain sens. Clustering est une méthode d'apprentissage non supervisé, et une technique commune pour l'analyse des données statistiques utilisées dans de nombreux domaines

Answer 2

Je pense que vous cherchez quelque chose de semblable à data discretization qui est assez courant dans AI pour convertir les données en continu (ou des données discrètes avec un si grand nombre de classes pour être lourdes) en classes discrètes.

Je sais que Weka utilise Fayyad & La méthode MDL d'Irani ainsi que la méthode MDL de Kononeko, je vais voir si je peux trouver des références.

Answer 3

Jenks Coupures naturelles est un système de classification de dimension unique très efficace: http://www.spatialanalysisonline.com/OUTPUT/html/Univariateclassificationschemes.html#_Ref116892931

Comme commentaires ont noté, ce qui est très similaire à k-means. Cependant, je l'ai trouvé encore plus facile à mettre en œuvre, en particulier la variation trouvée dans la Cartographie de Borden Dent: http://www.amazon.com/Cartography-Thematic-Borden-D-Dent/dp/0697384950

Answer 4

Genetic hierarchical clustering algorithm

Answer 5

Je me demandais.

Apparemment, ce que vous cherchez sont des pauses propres. Donc, avant de vous lancer dans des algorithmes complexes, vous pouvez peut-être envisager une approche différentielle.

[1, 1.2, 4, 5, 10] 

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

maintenant en fonction du nombre de ruptures que nous recherchons, il est question de les sélectionner:

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

Je ne sais pas vous, mais il ne se sent naturel à mon avis, et vous pouvez même utiliser une approche treshold en disant qu'une variation inférieure à x% ne vaut pas la peine d'envisager une coupe.

Par exemple, ici 4 categories ne semble pas avoir beaucoup de sens.

Answer 6

Ceci est seulement un problème à 1 dimension, donc il peut y avoir une solution de programmation dynamique. Supposons qu'il est logique de prendre les points dans l'ordre trié et de faire ensuite des coupes n-1 pour générer n clusters. Supposons que vous pouvez écrire une fonction de pénalité f() pour chaque grappe, telle que la variance dans le cluster ou la distance entre min et max dans le cluster. Vous pouvez ensuite réduire la somme de f() évaluée sur chaque cluster. Travailler d'un point à la fois, de gauche à droite. A chaque point, pour 1 .. # clusters - 1, calculez la meilleure façon de diviser les points jusqu'ici en autant de groupes, et stockez le coût de cette réponse et l'emplacement de sa division la plus à droite. Vous pouvez calculer ceci pour le point P et la taille de cluster c comme suit: considérer toutes les coupes possibles à gauche de P. Pour chaque coupure, ajouter f() évalué sur le groupe de points à droite de la coupure au coût (stocké) de la meilleure solution pour la taille de cluster c-1 au point juste à gauche de la coupe. Une fois que vous avez progressé vers l'extrême droite, répétez la même opération pour déterminer la meilleure réponse pour la taille de cluster c et utilisez les emplacements stockés des partitions les plus à droite pour récupérer tous les groupes qui offrent la meilleure réponse.

Cela peut en fait être plus cher qu'une variante k-means, mais a l'avantage de garantir une meilleure réponse globale (pour votre f() choisi selon ces hypothèses).