Proyecto 2 Clasificacion Jerarquica Descendente
Páginas: 6 (1326 palabras)
Publicado: 8 de noviembre de 2015
PROYECTO #2. ESTRUCTURA DE DATOS
Universidad Nacional
Estructura de Datos
Segundo proyecto programando
Modalidad: máximo en parejas
Lenguaje de programación: Java o C++
Fecha de entrega: Sábado 14 de noviembre 2015
Temas a ser evaluados:
1. Árboles binarios
2. Cola de prioridad
3. Matrices
4. Ordenamientos
5. Eficiencia algorítmica
Introducción al problema:
La minería de datos es fundamentalpara la toma de decisiones en las empresas, buscar formas alternativas de procesar grandes volúmenes de datos es tarea de lo que se conoce como BigData (Villalobos & Brenes, 2015). Muchos negocios tienen su éxito gracias al pronóstico como es el caso de Amazon, cuyos algoritmos permiten predecir los productos que un cliente pueda llegar a comprar con base a sus compras anteriores y las compras deotros clientes con gustos similares.
En este proyecto de Estructura de Datos, se desarrollará la implementación de un algoritmo de minería de datos llamado “Clasificación Ascendente Jerárquica (CAJ )” el cual tiene por finalidad la generación de Agrupaciones (clusters), como se ve en la figura 1, donde cada punto del mismo color indica que ese individuo se parece a los otros individuos del mismocolor (sus distancias son mínimas), pero entre dos individuos de distinto color son individuos muy diferentes.
Figura 1. Ejemplo de tres agrupaciones
El algoritmo CAJ NO es el único en realizar clustering, por ejemplo existen otros algoritmos como K-means. Sin embargo son menos precisos, es decir el CAJ genera mejores resultados (el costo es computacional mayor). Como un resultado de ejecutar elalgoritmo de CAJ es la generación de un Dendograma, ver figura 2.
Figura 2. Ejemplo de Dendograma
Sobre el algoritmo:
La idea del algoritmo es realizar una clasificación automática, en ese sentido “La clasificación automática tienen por objetivo reconocer grupos de individuos homogéneos, de tal forma que los grupos queden bien separados y bien diferenciados”.
Definición 1. Matriz de datos
SeaX la matriz de datos con n filas y p columnas, conformada por observaciones simples de la forma:
A nivel de implementación, el programa debe solicitar la ruta de un archivo separado por comas (.csv) como el que se adjunta al proyecto, además del archivo de individuos, el programa debe cargar un archivo de parámetros (también adjuntado a este documento). A continuación se muestra un ejemplo deuna tabla de datos de muestras de exámenes de un determinado grupo de colegio.
Tabla 1. Ejemplo de tabla de notas escolares
Matemáticas
Ciencias
Español
Historia
EdFísica
Katherine
7.0
6.5
9.2
8.6
8.0
Pedro
7.5
9.4
7.3
7.0
7.0
Inés
8.6
9.2
8.0
8.0
7.5
Luis
5.0
6.5
6.5
7.0
9.0
Andrés
6.0
6.0
7.8
8.9
7.3
Susana
7.8
9.6
7.7
8.0
6.5
Carlos
6.3
6.4
8.2
9.0
7.2
José
7.9
9.7
7.5
8.0
6.0
Sonia
6.0
6.06.5
5.5
8.7
Gabriela
9.4
7.2
8.7
9.0
7.0
El algoritmo CAJ utiliza una variación del algoritmo de Huffman, en vez de balancear frecuencias este algoritmo trata de balancear distancias entre individuos (distancia de disimilitud) y distancias conjunto de individuos (distancias de agregaciones).
Definición 2 Índice de disimilitud
Un índice de disimilitud entre un conjunto de objetos I (filas de unamatriz de observaciones) es una función d tal que:
Y debe cumplir con la simetría:
Además de cumplir la reflexividad:
Definición 3 Matriz de distancias
Una matriz de distancias es aquella matriz donde cada entrada está determinada por la distancia de disimilitud , de esta forma se genera la matriz:
El presente proyecto debe poder calcular las siguientes distancias:
1. Distancia EuclideaClásica: supongamos que se cuentan con dos vectores y la distancia Euclidea entonces se define como:
2. Distancia Euclidea de las varianzas: supongamos que se cuentan con dos vectores y la distancia Euclidea entonces se define como:
Con la varianza de las muestras, esto permite normalizar valores cuando las muestras están en distinta escala.
Definición 4 Funciones de agregación
Un índice de...
Universidad Nacional
Estructura de Datos
Segundo proyecto programando
Modalidad: máximo en parejas
Lenguaje de programación: Java o C++
Fecha de entrega: Sábado 14 de noviembre 2015
Temas a ser evaluados:
1. Árboles binarios
2. Cola de prioridad
3. Matrices
4. Ordenamientos
5. Eficiencia algorítmica
Introducción al problema:
La minería de datos es fundamentalpara la toma de decisiones en las empresas, buscar formas alternativas de procesar grandes volúmenes de datos es tarea de lo que se conoce como BigData (Villalobos & Brenes, 2015). Muchos negocios tienen su éxito gracias al pronóstico como es el caso de Amazon, cuyos algoritmos permiten predecir los productos que un cliente pueda llegar a comprar con base a sus compras anteriores y las compras deotros clientes con gustos similares.
En este proyecto de Estructura de Datos, se desarrollará la implementación de un algoritmo de minería de datos llamado “Clasificación Ascendente Jerárquica (CAJ )” el cual tiene por finalidad la generación de Agrupaciones (clusters), como se ve en la figura 1, donde cada punto del mismo color indica que ese individuo se parece a los otros individuos del mismocolor (sus distancias son mínimas), pero entre dos individuos de distinto color son individuos muy diferentes.
Figura 1. Ejemplo de tres agrupaciones
El algoritmo CAJ NO es el único en realizar clustering, por ejemplo existen otros algoritmos como K-means. Sin embargo son menos precisos, es decir el CAJ genera mejores resultados (el costo es computacional mayor). Como un resultado de ejecutar elalgoritmo de CAJ es la generación de un Dendograma, ver figura 2.
Figura 2. Ejemplo de Dendograma
Sobre el algoritmo:
La idea del algoritmo es realizar una clasificación automática, en ese sentido “La clasificación automática tienen por objetivo reconocer grupos de individuos homogéneos, de tal forma que los grupos queden bien separados y bien diferenciados”.
Definición 1. Matriz de datos
SeaX la matriz de datos con n filas y p columnas, conformada por observaciones simples de la forma:
A nivel de implementación, el programa debe solicitar la ruta de un archivo separado por comas (.csv) como el que se adjunta al proyecto, además del archivo de individuos, el programa debe cargar un archivo de parámetros (también adjuntado a este documento). A continuación se muestra un ejemplo deuna tabla de datos de muestras de exámenes de un determinado grupo de colegio.
Tabla 1. Ejemplo de tabla de notas escolares
Matemáticas
Ciencias
Español
Historia
EdFísica
Katherine
7.0
6.5
9.2
8.6
8.0
Pedro
7.5
9.4
7.3
7.0
7.0
Inés
8.6
9.2
8.0
8.0
7.5
Luis
5.0
6.5
6.5
7.0
9.0
Andrés
6.0
6.0
7.8
8.9
7.3
Susana
7.8
9.6
7.7
8.0
6.5
Carlos
6.3
6.4
8.2
9.0
7.2
José
7.9
9.7
7.5
8.0
6.0
Sonia
6.0
6.06.5
5.5
8.7
Gabriela
9.4
7.2
8.7
9.0
7.0
El algoritmo CAJ utiliza una variación del algoritmo de Huffman, en vez de balancear frecuencias este algoritmo trata de balancear distancias entre individuos (distancia de disimilitud) y distancias conjunto de individuos (distancias de agregaciones).
Definición 2 Índice de disimilitud
Un índice de disimilitud entre un conjunto de objetos I (filas de unamatriz de observaciones) es una función d tal que:
Y debe cumplir con la simetría:
Además de cumplir la reflexividad:
Definición 3 Matriz de distancias
Una matriz de distancias es aquella matriz donde cada entrada está determinada por la distancia de disimilitud , de esta forma se genera la matriz:
El presente proyecto debe poder calcular las siguientes distancias:
1. Distancia EuclideaClásica: supongamos que se cuentan con dos vectores y la distancia Euclidea entonces se define como:
2. Distancia Euclidea de las varianzas: supongamos que se cuentan con dos vectores y la distancia Euclidea entonces se define como:
Con la varianza de las muestras, esto permite normalizar valores cuando las muestras están en distinta escala.
Definición 4 Funciones de agregación
Un índice de...
Leer documento completo
Regístrate para leer el documento completo.