Algoritmo para generar una jerarquía de conceptos numéricos

Question

Tengo un par de conjuntos de datos numéricos para los que necesito crear una jerarquía de conceptos. Por ahora, he estado haciendo esto manualmente al observar los datos (y un diagrama de líneas correspondiente). Basado en mi intuición, creé algunas jerarquías aceptables.

Esto parece una tarea que se puede automatizar. ¿Alguien sabe si existe un algoritmo para generar una jerarquía de conceptos para datos numéricos?

---

Para dar un ejemplo, tengo el siguiente conjunto de datos:

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

para que creé la siguiente jerarquía:

• más baja (< 1000)
• BAJA (1000-2500)
• MEDIA (2501 - 7500)
• ALTA (7501 - 30000)
• más alta (> 30000)

Answer 1

Tal vez se necesita un algoritmo de clustering?

citando el enlace: análisis

Cluster o agrupación es la asignación de un conjunto de observaciones en subconjuntos (llamados cúmulos) para que observaciones en el mismo grupo son similar en algún sentido. La agrupación es un método de aprendizaje no supervisado, y una técnica común de datos estadísticos análisis utilizado en muchos campos

Answer 2

Creo que usted está buscando algo parecido a data discretization que es bastante común en la IA para convertir los datos continuos (o datos discretos con una cantidad tan grande de clases que sean difíciles de manejar) en clases discretas.

Sé que Weka usa Fayyad & Método MDL de Irani, así como el método MDL de Kononeko, veré si puedo encontrar algunas referencias.

Answer 3

rompe Jenks natural es un esquema muy eficiente sola dimensión agrupación: http://www.spatialanalysisonline.com/OUTPUT/html/Univariateclassificationschemes.html#_Ref116892931

Como han señalado los comentarios, esto es muy similar a la de k-medias. Sin embargo, he encontrado que es aún más fácil de poner en práctica, en particular la variación encontrada en la cartografía de Borden Dent: http://www.amazon.com/Cartography-Thematic-Borden-D-Dent/dp/0697384950

Answer 4

Genetic hierarchical clustering algorithm

Answer 5

Me preguntaba.

Aparentemente, lo que está buscando son descansos limpios. Entonces, antes de lanzarte a algoritmos complicados, quizás puedas imaginar un enfoque diferencial.

[1, 1.2, 4, 5, 10] 

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

Ahora dependiendo del número de roturas que estamos buscando, que es una cuestión de la selección de ellos:

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

Yo no sé ustedes, pero lo hace sentir natural en mi opinión, y incluso puede usar un enfoque de tres puntos diciendo que una variación inferior a x% no vale la pena considerar un recorte. Por ejemplo, 4 categories no parece tener mucho sentido.

Answer 6

Esto es solo un problema unidimensional, por lo que puede haber una solución de programación dinámica. Supongamos que tiene sentido tomar los puntos en orden y luego hacer n-1 cortes para generar n clusters. Supongamos que puede escribir una función de penalización f() para cada grupo, como la varianza dentro del grupo o la distancia entre el mínimo y el máximo en el grupo. A continuación, puede minimizar la suma de f() evaluada en cada grupo. Trabaje de un punto a la vez, de izquierda a derecha. En cada punto, para 1 .. # clusters - 1, encuentre la mejor manera de dividir los puntos hasta ese momento en tantos clústeres y almacene el costo de esa respuesta y la ubicación de su división más a la derecha. Puede resolver esto para el punto P y el tamaño del grupo c de la siguiente manera: considere todos los cortes posibles a la izquierda de P. Para cada corte agregue f() evaluado en el grupo de puntos a la derecha del corte al costo (almacenado) de la mejor solución para el tamaño de conglomerado c-1 en el punto justo a la izquierda del corte. Una vez que hayas trabajado hacia la extrema derecha, haz el mismo truco una vez más para encontrar la mejor respuesta para el tamaño de conglomerado c, y usa las ubicaciones almacenadas de las divisiones del extremo derecho para recuperar todas las divisiones que dan la mejor respuesta.

Esto en realidad podría ser más costoso que una variante k-means, pero tiene la ventaja de garantizar encontrar una mejor respuesta global (para su f() elegida bajo estas suposiciones).