PDF de programación - Algoritmo de agrupamiento basado en patrones utilizando árboles de decisión no supervisados

Imágen de pdf Algoritmo de agrupamiento basado en patrones utilizando árboles de decisión no supervisados

Algoritmo de agrupamiento basado en patrones utilizando árboles de decisión no supervisadosgráfica de visualizaciones

Publicado el 31 de Marzo del 2018
612 visualizaciones desde el 31 de Marzo del 2018
718,8 KB
23 paginas
Creado hace 11a (21/11/2012)
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

},...,{1nOODSiO},...,{1mxxXjxjVnimjVvOxjjkij,...,1,,...,1,)()(ijOxjxiOjVmj,...,1SX2:SSP) (jkjvopxpop 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
  • Links de descarga
http://lwp-l.com/pdf10057

Comentarios de: Algoritmo de agrupamiento basado en patrones utilizando árboles de decisión no supervisados (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad