Algoritmo de agrupamiento basado en
patrones utilizando árboles de decisión no
supervisados
Andres Eduardo Gutierrez Rodríguez, Milton García Borroto,
José Francisco Martínez Trinidad
Reporte Técnico No. CCC-12-002
21 de noviembre de 2012
© Coordinación de Ciencias Computacionales
INAOE
Luis Enrique Erro 1
Sta. Ma. Tonantzintla,
72840, Puebla, México.
Algoritmo de agrupamiento basado en patrones utilizando árboles de
decisión no supervisados
Andres Eduardo Gutierrez Rodríguez, Milton García Borroto, José Francisco Martínez
Trinidad
Coordinación de Ciencias Computacionales,
Instituto Nacional de Astrofísica, Óptica y Electrónica,
Luis Enrique Erro 1, Sta. Ma. Tonantzintla,
72840, Puebla, México
E-mail:
[email protected]; {ariel,fmartine}@inaoep.mx
Resumen. En la clasificación no supervisada muchas veces se desea explicar los resultados
obtenidos, más allá de solo enumerar los objetos que pertenecen a cada agrupamiento. Los
algoritmos de agrupamiento basado en patrones permiten explicar los resultados a partir de
propiedades (patrones) que cumplen los objetos de cada grupo. Una estrategia comúnmente
utilizada consiste en encontrar primero los patrones y después utilizarlos para agrupar los
objetos, sin embargo, los algoritmos que siguen esta estrategia presentan algunas
limitaciones, como por ejemplo que utilizan un proceso de discretización para poder
trabajar con datos numéricos; además, inicialmente se obtienen todos los patrones
frecuentes y después se aplica algún proceso de filtrado. Posteriormente, en la fase de
agrupamiento usando
costosas
computacionalmente para construir los agrupamientos. En esta propuesta de investigación
doctoral se plantea desarrollar un algoritmo para la extracción de un subconjunto reducido
de patrones adecuados para agrupar, sin discretizar previamente los datos numéricos.
Basado en esos patrones se pretende desarrollar un algoritmo de agrupamiento eficiente y
eficaz que sea capaz de trabajar con datos mezclados e incompletos. Como resultado
preliminar, se desarrolló un nuevo algoritmo de extracción de patrones a partir de un
bosque de árboles de decisión no supervisados. Adicionalmente, se definió una medida para
evaluar la calidad de los grupos de patrones obtenidos. Las comparaciones experimentales
muestran el buen desempeño del algoritmo propuesto al agrupar con los nuevos patrones
extraídos, comparado contra la alternativa convencional de calcular todos los patrones
frecuentes.
estrategias muy
estos patrones
se utilizan
Palabras clave. Clasificación no supervisada, extracción de patrones, agrupamiento basado en
patrones.
1 Introducción
La clasificación no supervisada [39] es un área dentro del reconocimiento de patrones [3] que se ha
aplicado en múltiples disciplinas como aprendizaje automático [2], procesamiento de textos [4],
procesamiento digital de imágenes [5], entre otras. Los algoritmos de clasificación no supervisada
también se conocen como algoritmos de agrupamiento, durante la investigación doctoral
emplearemos este segundo término.
El proceso de agrupamiento consiste en, dado un conjunto de objetos sin etiquetar, formar grupos
de objetos siguiendo un determinado criterio [22]. En la literatura se han definido diferentes
criterios de agrupamiento:
para Everitt en 1974 [34] los grupos deben tener una densidad de puntos relativamente alta,
para Jain y Dubes en 1988 [35] el análisis de grupos consiste en encontrar la estructura
intrínseca en los datos ya sea como grupos de individuos o como jerarquía de grupos,
Pal y Bezdek en 1995 [36] afirman que en un conjunto de objetos se pueden identificar un
número determinado de subgrupos naturales,
en 2001, Halkidi et al. [29] expresaron que los objetos de un grupo se parecen más entre sí
que a objetos de otros grupos,
Bezdek y Hathaway en 2003 [37] establecen que el proceso de agrupamiento consiste en
particionar un conjunto de objetos en grupos de objetos similares.
No obstante la diversidad de criterios de agrupamiento, el más utilizado es el basado en el parecido
entre los objetos, de manera que los objetos de un grupo se parezcan más entre sí que a objetos de
otros grupos [23]. Por lo general, el parecido entre los objetos se determina a partir de una función
de comparación.
Debido a la diversidad de los criterios de agrupamiento seguidos por diferentes autores, validar los
resultados obtenidos es un proceso subjetivo, que depende del criterio establecido y de la manera en
que se mide el cumplimiento de ese criterio. Además, en áreas de aplicación como agricultura [8],
bioinformática [9] y procesamiento de textos [10] es necesario explicar el resultado del
agrupamiento, más allá de solo evaluar el parecido entre los objetos según la función de
comparación. En estos casos los enfoques tradicionales de agrupamiento no brindan una solución
adecuada.
Un enfoque diferente para el agrupamiento se basa en describir los agrupamientos a partir de
conceptos o patrones que relacionan a los objetos [6, 7]. Este enfoque es conocido como
agrupamiento basado en patrones. En la literatura encontramos tres estrategias fundamentales para
este enfoque, las que presentan las siguientes limitaciones:
Construir los patrones a la vez que se agrupan los objetos [2, 11]
o Los algoritmos son costosos computacionalmente y no obtienen buenos resultados.
Agrupar primero los objetos y luego encontrar patrones [21, 26]
o Debido a que los objetos se agrupan usando una función de comparación, puede
haber incompatibilidad con los patrones que se extraen en un siguiente paso, los
cuales pueden caracterizar a objetos de grupos diferentes, aun cuando éstos no sean
1
parecidos de acuerdo a la función de comparación que se usó para formar el
agrupamiento.
Extraer todos los patrones frecuentes y a partir de ellos agrupar los objetos [7, 10, 13, 14,
16]
o Esto hace que el proceso de agrupamiento sea ineficiente y que se tomen en cuenta
patrones que pueden no ser adecuados para agrupar.
Adicionalmente, una característica importante en la mayoría de los algoritmos pertenecientes a las
tres estrategias antes descritas es que no permiten trabajar con datos mezclados.
1.1 Problema a resolver
La presente investigación doctoral se enfoca en la tercera estrategia, con la cual se han reportado
buenos resultados [7, 10, 13, 14, 16], en comparación con las otras dos estrategias. Sin embargo,
esta tercera estrategia tiene como una de sus limitaciones importantes la cantidad de patrones
extraídos. Es por eso que el problema que se plantea resolver es utilizar patrones para agrupar
objetos, extrayendo solo un subconjunto reducido de patrones que sean adecuados para agrupar, en
problemas con datos mezclados e incompletos; sin realizar discretización previa de los datos
numéricos, la cual puede producir pérdida de información. Asimismo, es importante desarrollar
algoritmos de agrupamiento eficientes a partir de los patrones encontrados, ya que los algoritmos
actuales son de un alto costo computacional.
2 Conceptos básicos
2.1 Representación de objetos
Sea
un conjunto de objetos. Cada objeto
es descrito por un conjunto de
atributos
. Cada atributo
toma valores en un conjunto admisible de valores
,
, siendo
el valor del atributo
en el objeto
. Los
atributos pueden ser de diferentes tipos dependiendo de la naturaleza del conjunto
,
.
Los tipos de valores pueden ser categóricos, numéricos e incluso ausencia de información; es por
eso que consideramos al conjunto de objetos DS como mezclado e incompleto.
2.2 Comparación entre objetos
Una función de comparación de objetos se define como
un conjunto
completamente ordenado. Una función de comparación de objetos se dice que es de similaridad si al
comparar un objeto con sigo mismo devuelve el máximo valor dentro de
. Se dice que es de
disimilaridad en caso contrario.
, siendo
2.3 Patrones
Un patrón
está compuesto por una conjunción de propiedades
es una expresión que describe o caracteriza a un subconjunto de objetos. Un patrón
es un operador
, donde
relacional; por simplicidad consideramos solo
un conjunto de jóvenes talentos de baloncesto puede ser [(Edad
, >, =. Por ejemplo, una expresión que caracterice a
20)
(Estatura > 190)].
Decimos que un objeto es "caracterizado" por un patrón si el objeto cumple todas las propiedades
del patrón; en este caso se dice que el patrón "cubre" al objeto. El "soporte" de un patrón es la
fracción de objetos que son caracterizados por él. Un patrón es frecuente si su "soporte" es mayor
que un umbral dado.
2
},...,{1nOODSiO},...,{1mxxXjxjVnimjVvOxjjkij,...,1,,...,1,)()(ijOxjxiOjVmj,...,1SX2:SSP) (jkjvopxpop 2.4 Algoritmos de agrupamiento
El principal objetivo de los algoritmos de agrupamiento es, dado una colección de objetos, formar
siguiendo un determinado criterio [22]. Uno de los algoritmos de
grupos de objetos
agrupamiento (no basado en patrones) más populares es el K-Means [29].
para cada grupo
Por otra parte, los algoritmos de agrupamiento basado en patrones generan un conjunto de patrones
, de manera que cada conjunto de patrones describe cada grupo. Por
ejemplo, en la Tabla 1 se muestran los datos de 10 jugadores de baloncesto; un buen agrupamie
Comentarios de: Algoritmo de agrupamiento basado en patrones utilizando árboles de decisión no supervisados (0)
No hay comentarios