Por favor, use este identificador para citar o enlazar este ítem:
http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/829| Descubrimiento de conjuntos frecuentes de ítems en datos estáticos y dinámicos | |
| RAUDEL HERNANDEZ LEON | |
| JESUS ARIEL CARRAZCO OCHOA | |
| Acceso Abierto | |
| Atribución-NoComercial-SinDerivadas | |
| Data mining Association rules Dynamic data sets | |
| Currently the amount of data generated in any knowledge area is too big for being
processed by a human. Among the more used data mining techniques are the mining or
discovery of frequent item sets.
In this thesis, two algorithms for frequent item sets (FI) mining on big sparse datasets
are presented.
The first algorithm named Compressed Arrays (CA) processes static data, i.e. dataset
which do not change. Therefore, if the dataset is updated CA needs to process all the
dataset to mine the new FI. CA performs a breadth first search through equivalence
classes and introduces compressed arrays to accumulate the prefix class supports. CA is
compared against the best algorithms reported in the literature. In our experiments, the
best performance of CA algorithm was obtained for big sparse datasets.
The second algorithm named Incremental Compressed Arrays (ICA) processes dynamic
data, i.e. data in which a set of transactions can be added, deleted or modified. In
order to mine the new FI after an updating, ICA does not need to process all the data
but the current FI are used to obtain the new FI. Unlike previous algorithms, ICA does
not suppose that the data fit in memory but it stores the mined FI in binary files. The
experimentation shows than after adding, deleting or modifying a set of transactions, it
is more efficient to use the FI previously mined than to process all the dataset from the
beginning. La cantidad de datos que se genera hoy en día en cualquier área de conocimiento rebasa la capacidad de asimilación de cualquier ser humano. Entre las técnicas de minería de datos más utilizadas se encuentra el descubrimiento o minado de conjuntos frecuentes de ítems (FI). El minado de FI ha sido aplicado en clasificación y agrupamiento de documentos, en análisis de información de ventas, en telecomunicaciones, etc. En esta tesis se presentan dos algoritmos para minar todos los conjuntos frecuentes de ítems en grandes volúmenes de datos. El primero de los algoritmos (CA) procesa conjuntos de datos estáticos, es decir, que no cambian. Por lo tanto, si se actualiza el conjunto de datos CA necesita procesar todo el conjunto desde el inicio para minar los nuevos FI. El algoritmo CA utiliza una representación binaria de los datos. Este tipo de representación, por su alto consumo de memoria, ha sido desechada por los algoritmos más recientes. CA combina la representación binaria con una estructuración del espacio de búsqueda en clases de equivalencia para reducir el consumo de memoria y realizar un rápido cálculo de los FI. En los experimentos realizados se muestra que el algoritmo CA obtiene mejores resultados que los mejores algoritmos reportados en la literatura para calcular FI. El algoritmo CA alcanza un mejor desempeño en conjuntos de datos grandes y dispersos. El segundo algoritmo presentado en esta tesis se denomina ICA y procesa conjuntos de datos dinámicos, datos en los que se puede adicionar, eliminar o modificar la información existente. Para minar los FI después de una actualización, ICA no necesita procesar los datos desde el inicio, sino que reutiliza los FI previamente minados para obtener los nuevos FI. A diferencia de los algoritmos existentes, ICA no supone que los datos caben en memoria y almacena los FI previamente minados en ficheros binarios. Los experimentos realizados muestran que, después de adicionar o eliminar información en el conjunto de datos, resulta más eficiente reutilizar los FI previamente minados que procesar todo el conjunto de datos desde el inicio. El algoritmo ICA resulta más eficiente cuando se elimina información que cuando se adiciona. | |
| Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| 2008-07 | |
| Tesis de maestría | |
| Español | |
| Estudiantes Investigadores Público en general | |
| Hernandez-Leon R. | |
| CIENCIA DE LOS ORDENADORES | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Maestría en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| HernandezLR.pdf | 478.87 kB | Adobe PDF | Visualizar/Abrir |