Experimento de minería de datos y almacén de datos_guía de experimento de minería de datos

Instrucciones para el experimento de "minería de datos"

1 de marzo de 2011

Departamento de Ciencias de la Información y la Computación, Universidad de Changsha

Prólogo

p>

Con el desarrollo de la tecnología de bases de datos, especialmente la creciente popularidad de nuevas fuentes de datos como los almacenes de datos y la Web, se ha formado una situación grave de abundancia de datos y falta de conocimiento. En respuesta al desafío de cómo utilizar eficazmente estas cantidades masivas de información, la tecnología de minería de datos surgió según lo requieren los tiempos y ha demostrado una gran vitalidad. La tecnología de minería de datos ha llevado la tecnología de procesamiento de datos a una etapa más avanzada y es una de las diez tecnologías emergentes que tendrán un impacto significativo en los seres humanos en el futuro. Por lo tanto, fortalecer el aprendizaje teórico y práctico en el campo de la minería de datos se ha convertido en un contenido requerido para los estudiantes profesionales.

Esta guía experimental utiliza una gran cantidad de ejemplos para guiar a los estudiantes paso a paso para completar los experimentos de cada capítulo. De acuerdo con el programa experimental, hemos organizado cinco experimentos y cada experimento se divide en cinco partes: propósito experimental, contenido experimental, procedimientos experimentales, requisitos del informe experimental y precauciones. Antes del experimento, el maestro dará una cierta explicación del experimento, permitirá que los estudiantes aclaren el propósito del experimento y se preparen para el experimento. En el experimento, los estudiantes verifican y resumen de acuerdo con el contenido de la guía experimental y luego completan las tareas organizadas en los pasos experimentales. Una vez completado el experimento, los estudiantes completarán el informe del experimento según sea necesario. A lo largo de la enseñanza y los experimentos, enfatizamos que los estudiantes cultiven efectivamente sus habilidades prácticas y dominen los métodos básicos de minería de datos.

Experimento 1 Implementación del algoritmo de agrupamiento de K-Means

1. Propósito del experimento

Analizando el principio de agrupamiento del algoritmo de agrupamiento de K-Means, utilizando la herramienta de programación Vc La programación implementa el algoritmo de agrupación K-Means y, a través del proceso de agrupación de datos de muestra, profundiza la comprensión y el proceso de aplicación del algoritmo de agrupación. Tipo de experimento: Plan de verificación Tiempo de clase: 4 horas

2. Contenido del experimento

1. Analizar el algoritmo de agrupación de K-Means 2. Analizar el método de cálculo de la distancia 3. Analizar la agrupación Criterios de evaluación; ;

4. Programe el algoritmo de agrupamiento K-Means e implemente el proceso de agrupamiento basado en datos experimentales relevantes;

3. Métodos experimentales

1. Principio de Algoritmo de agrupamiento de K-medias

El algoritmo de agrupamiento de K-medias toma k como parámetro y divide n objetos en k grupos para que los objetos dentro de los grupos tengan un alto grado de similitud. La similitud se calcula en función del valor promedio de los objetos en un grupo.

Descripción del algoritmo:

Entrada: número de clusters k y una base de datos que contiene n objetos

Salida: k proceso de cluster que minimiza el criterio de error al cuadrado:

Seleccione cualquiera k objetos como centro del clúster inicial; repetir

para j=1 an DO

De acuerdo con el valor promedio de los objetos en el clúster, asigne cada objeto al clúster más similar para i=1 a k DO Actualice el valor promedio del clúster E

Unitl E ya no cambiará y generará los objetos correspondientes de acuerdo con el clúster

2. Criterios de evaluación de agrupación: E Calculado como: E =

∑∑|x -x

i =1x ∈C i

k

i

|2

4. Pasos experimentales 4.1 Datos experimentales

P192: 15

4.2 Selección de centros de conglomerados iniciales Seleccione k muestras como centros de conglomerados Para (i=0; i

Para (j=0; j

ClusterCenter[i][j]=DataBase[i][j]

4.3 Reasignación de objetos de datos

Sim=un número grande determinado; ClusterNo=-1

For (i=0; i

If (Distancia (Base de datos; [j], ClusterCenter[i])

ClusterNo=i;}

ObjectCluster[j]=ClusterNo;

4.4 Actualización del clúster

p >

Para (i=0; i

{Temp=0; Num=0; Para (j=0; j

Si (ObjectCluster[j]== i ){Num; Temp =DataBase[j];} If (ClusterCenter[i]!=Temp) HasChanged=TRUE; ClusterCenter[i]=Temp }

4.5 Salida del resultado para (i= 0; i

Printf("Envíe el objeto del clúster dth:", i); For (j=0; j

If (ObjectCluster[j]==i) printf( "d",j); Printf("\n");

Printf("\t\t\tEl promedio del clúster es (d,d)\n", ClusterCenter[i] [0] , ClusterCenter[i][1]); }

5. Notas 1. Selección de la función de distancia 2. Cálculo de la función de evaluación

Experimento 2 Implementación del algoritmo DBSCAN

1. Propósito del experimento

Se requiere dominar el principio de agrupamiento del algoritmo DBSCAN y comprender el proceso de ejecución del algoritmo DBSCAN. Sobre esta base, se utiliza el algoritmo DBSCAN para implementar el proceso de agrupación de los datos de muestra dados.

Tipo de experimento: Plan integral Clase: 4 horas

2. Contenido del experimento

1. Comprender el principio de agrupamiento del algoritmo DBSCAN 2. Comprender el algoritmo DBSCAN; proceso de ejecución; 3. Programación para implementar el algoritmo DBSCAN; 4. Implementación del proceso de agrupamiento para los datos de muestra dados

3. Métodos experimentales

Conceptos básicos del algoritmo DBSCAN<. /p >

● ε-vecindad de un objeto: el área dentro del radio ε de un objeto dado;

● Objeto central: si la ε-vecindad de un objeto contiene al menos un número mínimo de los objetos MinPts, se llama Este objeto

es el objeto central;

● Accesibilidad de densidad directa: dado un conjunto de objetos D, si p está dentro del vecindario ε de q, y q es un objeto central

, entonces se dice que el objeto p es directamente alcanzable en densidad a partir del objeto q

● Densidad alcanzable: si hay una cadena de objetos p1, p2; , ?, pn, p1=q, pn=p, para pi ∈D, pi 1 es directamente alcanzable en densidad desde pi

con respecto a ε y MinPts, entonces se dice que el objeto p es alcanzable en densidad desde el objeto q con respecto a ε y MinPts alcanzables;

● Densidad conectada: si hay un objeto o en el conjunto de objetos D, de modo que los objetos p y q sean alcanzables desde o con respecto a ε. y

MinPts, entonces los objetos p y q están conectados por densidad con respecto a ε y MinPts ● Ruido: un grupo basado en densidad es el conjunto más grande de objetos conectados por densidad según la accesibilidad de la densidad,

p>

no incluido en ningún grupo Los objetos se consideran ruido

3.2 Idea básica de implementación

Los grupos se encuentran examinando la vecindad ε de cada objeto en el. conjunto de datos. Si el vecindario ε de un punto p contiene más de objetos MinPts, cree un nuevo grupo con p como objeto principal. Luego, DBSCAN busca objetos a los que se pueda alcanzar la densidad directamente desde estos objetos centrales. Este proceso puede implicar la fusión de algunos grupos alcanzables por densidad. El proceso de agrupación finaliza cuando no se pueden agregar nuevos puntos a ningún grupo.

3.3 Descripción del algoritmo

Entrada: base de datos que contiene n objetos, radio, número mínimo de MinPts; Salida: todos los clústeres generados, alcanzando los requisitos de densidad. Proceso: Repetir

Extraiga un punto sin procesar de la base de datos;

SI El punto extraído es el punto central ENTONCES Encuentre todos los objetos con densidad accesible desde la tienda para formar un grupo. DE LO CONTRARIO El punto extraído es el punto de borde (no central; objeto), salte de este bucle y busque el siguiente punto Hasta que se procesen todos los puntos

4. Paso experimental 4.1 Análisis de la estructura de datos Struct List

{Int data[ TOTALPOINT] ; Int head=0; Int tail=-1; Lista de nodos de estructura

{ int Atributo1; int Atributo2} Base de datos de nodo[TOTALPOINT]; [TOTALPOINT]; Int ClusterNo[TOTALPOINT];

4.2 Datos experimentales P186 Tabla 5-8

4.3 Calcular la proximidad

Para (i=0; i

For (j=0; j

If (dist(DataBase[i], DataBase[i])

4.4 Agrupación en clusters CurrentClusterNO=0 ; For (i =0; i

NúmPuntosVecinos=0;

for (j=0; j

if (Vecino[i][j]= =true)NúmPuntos Vecinos ; if (NeighborPointsNum)gt; =MinPts {

// Registre el número de clúster que se ha dividido en el vecino ClusterList.tail=-1;

Si (Vecino[i][j]==true) amp;amp;(ClusterNo[j]gt;0)

Entonces {ClusterList.tail;

p>

ClusterList.data[tail]=ClusterNo[j]} // Los objetos vecinos del objeto principal actual se dividen en un clúster For (j=0; j

ClusterNo[j] =CurrentClusterNO;

// Fusionar varios clústeres

Mientras que ClusterList.head

If (ClusterNo[j]==ClusterList.data[head]) ClusterNo[ j ]=CurrentClusterNO;

ClusterList.head; } } }

4.5 Salida del resultado de agrupación

Para (i=-1; i

Printf("\nSalida del objeto del cluster d:", i); For (j=0; j

If (ClusterNo[j]=i) printf("d\t", j ); }

5. Notas 5.1. Procesamiento de datos de ruido

5.2 Fusión de datos de clases relacionadas cuando las clases divididas tienen accesibilidad de densidad directa

>

Experimento 3 Implementación del algoritmo ID3

1. Propósito experimental

Implementar el algoritmo del árbol de decisión a través de la programación, el cálculo de la ganancia de información, la división del subconjunto de datos y el proceso de construcción de el árbol de decisión. Profundizar la comprensión de los algoritmos relacionados. Tipo de experimento: Plan de verificación Tiempo de clase: 4 horas

2. Contenido del experimento

1. Analizar el proceso de implementación del algoritmo del árbol de decisión

2. Analizar; ganancia de información El proceso de cálculo, división de subconjuntos de datos y construcción del árbol de decisión 3. Programe e implemente el algoritmo de acuerdo con la descripción del algoritmo, depure y ejecute 4. Verifique el cálculo de la pregunta 10 de P161 después de la clase y obtenga los resultados del análisis; .

3. Método experimental

Descripción del algoritmo:

Comience a construir el árbol con un solo nodo que represente la muestra de entrenamiento

Si el; todas las muestras son de la misma clase, el nodo se convierte en una hoja y se marca con esa clase;

De lo contrario, el algoritmo utiliza la ganancia de información como información heurística para seleccionar el atributo que mejor puede clasificar la muestra para cada una; atributo de prueba Dado el valor, cree una rama y divida las muestras en consecuencia; el algoritmo utiliza el mismo proceso para formar recursivamente un árbol de decisión de muestra en cada división. El paso de división recursiva se detiene cuando se cumple una de las siguientes condiciones: Todas las muestras de un. el nodo dado pertenece a la misma categoría;

No quedan atributos para dividir aún más la muestra. En este caso, se utiliza la votación por mayoría

Pasos experimentales

<. p> 1. Implementación del algoritmo Descripción de la estructura de datos que debe usarse en el proceso: Struct

{int Attrib_Col; // El atributo correspondiente del nodo actual es int // El borde correspondiente; value Tree_Node* Left_Node; // Subtree

Tree_Node* Right_Node // Otros nodos en la misma capa Boolean IsLeaf // Si es un nodo hoja int ClassNo; p>

2. Programa principal del proceso general del algoritmo:

InputData();

T=Build_ID3(Data, Record_No, Num_Attrib(T); memoria; 3. Subfunciones relacionadas: 3.1, InputData()

{

Ingrese el tamaño del conjunto de atributos Num_Attrib ]; ; }

3.2. Build_ID3(Data, Record_No, Num_Attrib)

{

Int Class_Distribute[ C];

Si (Record_No ==0) { return Null }

N=new tree_node();

Calcular la distribución de varios tipos en Data Save Class_Distribute Temp_Num_Attrib=0; For (i=0; i

If (Data[0][i]gt;=0) Temp_Num_Attrib; If Temp_Num_Attrib==0 {

N-gt; ClassNo=most clases; N-gt; IsLeaf=TRUE;

N-gt; Izquierda_Nodo=NULL; Derecha_Nodo=NULL;

}

Si la distribución de una sola clase en Class_Distribute es mayor que 0 {

N-gt; esta clase N-gt;

N-gt; Nodo_izquierdo=NULL; Nodo_derecho=NULL; Devuelve N }

InforGain=0; p>

TempGain=Compute_InforGain(Data, Record_No, I, Num_Attrib); If (InforGain

{ InforGain=TempGain; CurrentCol=I; } }

N-gt; Attrib_Col=CurrentCol;

//Registra los diferentes valores correspondientes a CurrentCol y colócalos en DiferentValue[]; I=0; Value_No=-1;

if (DiferentValu[k]=Data[i][CurrentCol]) flag=true; if (flag==false)

{DiferentValue[Value_No]=Data[ i][CurrentCol ] } I; }

SubData=Aplicar espacio de memoria con tamaño de datos para (i=0; i

k=-1;

for (j =0;j

if (Data[j][CurrentCol]==DiferentValu[i]) {k=k;

For(int i1=0; i1

If (i1CurrentCol)SubData[k][i1]=Data[j][i1]; Else SubData[k][i1]=-1 }

N- gt; Attrib_Col= N-gt; Valor=DiferentValu[i]; N-gt=false; N-gt; k 1, Num_Attrib); N-gt; Right_Node=new Tree_Node; N=N-gt; Right_Node; } }

Calcular la ganancia de información

Compute_InforGain(Data, Record_No, Col_No, Num_Attrib)

Int DifferentValue[MaxDifferentValue]; Int Total_DifferentValue;

Int s[ClassNo][MaxDifferentValue]

s=0; la matriz a 0

Total_DifferentValue=-1; For (i=0; i

J=GetPosition(DifferentValue,

Total_DifferentValue, Data[i] [Col_no]); ]][j]; }

Total_I=0;

Para (i=0; i

Suma=0;

Para (j=0; j

Para (i=0; i

{ te

mp=0; sj=0; //sj es el número de muestras que pertenecen a la clase j en el subconjunto de datos For (j=0; j

For (j=0; j

EA =sj/Record_No*Compute_PI(s[j][i]/sj); }

Devuelve total_I-EA; cierto número en la matriz Posición GetPosition(Data, DataSize, Value) {

For (i=0; i

3.5. Calcular Pi*LogPi

Flotante Compute_PI(float pi) {

Si pi=1 entonces devuelve 0; Devuelve 0-pi*log2(pi }

5. Requisitos del informe del experimento

1. Utilice lenguaje C para implementar los algoritmos relacionados anteriormente

2. Procedimientos experimentales y resultados experimentales, problemas y soluciones durante el experimento

6. Notas

1. , Cálculo de la ganancia de información;

2. Después de seleccionar los campos relevantes, divida el conjunto de datos de acuerdo con los valores de los campos relevantes.

3. Condiciones de terminación para la construcción del árbol de decisión

Experimento 4 Implementación del algoritmo bayesiano

1. Propósito del experimento

Al programar el algoritmo bayesiano, profundizar la comprensión del algoritmo bayesiano algoritmo y utilice el algoritmo bayesiano para implementar predicción y clasificación para aplicaciones simples. Tipo de experimento: Plan de verificación Tiempo de clase: 4 horas

2. Contenido del experimento

1, Analizar el algoritmo bayesiano. 2. Calcular la probabilidad condicional; 3. Cálculo y evaluación de la precisión de la predicción;

4. Programa para implementar el algoritmo de clasificación bayesiano e implementar la clasificación de predicción para datos de muestra de aplicaciones simples.

p>

3. Método experimental

1. Implementar el algoritmo bayesiano

2. Utilizar datos experimentales para probar el algoritmo bayesiano 3. Calcular la precisión de la solución 4. Programa de depuración

5. Completar todo el proceso de clasificación y evaluación

4. Pasos experimentales

4.1 Descripción del proceso del algoritmo:

1) Ingrese los datos de entrenamiento y guarde los datos en la matriz bidimensional de la base de datos (el último atributo de la matriz corresponde a la etiqueta de categoría) 2) Establezca el tamaño del conjunto de datos de entrenamiento y del conjunto de datos de prueba (especifique comenzando desde el índice de matriz 0 hasta TrainSetSize-1 correspondiente a Los datos son datos de entrenamiento y el resto son datos de prueba);

3) Calcule la distribución de probabilidad de cada atributo en el conjunto de datos de entrenamiento entre varias categorías; 4) Utilice los datos de prueba para calcular la precisión de la clasificación; del algoritmo bayesiano 5) Generar los resultados de la clasificación; 4.2 Procesamiento de datos

B. Convertir los datos del tipo de enumeración en los datos para facilitar el procesamiento de datos:

4.3 Calcular cada atributo en el conjunto de datos de entrenamiento La distribución de probabilidad entre varias categorías se muestra en la Figura 3-1. 4.4 El uso de datos de prueba para calcular la precisión de clasificación del algoritmo bayesiano se muestra en la Figura 3-2

Figura 3-1 Cada atributo. del conjunto de datos de entrenamiento Cálculo de la distribución de probabilidad

Figura 3-2 Cálculo de la precisión de clasificación del algoritmo bayesiano

4.5 Resultados de clasificación de salida

Para (i=0 ; i

p>

For (j=0; j

printf(“\n\nTotal Correct isd”, TotalCorrect);

5. Precauciones

Preste atención a la relación entre el cálculo de probabilidad de los datos de una sola muestra y el cálculo de probabilidad de cada campo

Experimento 5 Implementación del algoritmo a priori

1. Propósito del experimento

1. Dominar el algoritmo Apriori genera conjuntos frecuentes en la minería de reglas de asociación y el proceso de generación de conjuntos de reglas de asociación 2. Programe e implemente el algoritmo de acuerdo con la descripción del algoritmo, depurelo, ejecútelo y aplíquelo; junto con datos experimentales relevantes para obtener resultados de análisis de datos y operaciones de eliminación de datos.

Tipo de experimento: Plan de verificación Tiempo de clase: 2 horas

2. Contenido del experimento

1. Generación de conjuntos de elementos frecuentes e implementación del algoritmo Apriori;

2. Asociación El proceso de generación de reglas y la implementación del algoritmo de generación de reglas; 3. Analizar el algoritmo con ejemplos

3. Pasos experimentales

Escriba un programa para completar los siguientes algoritmos: 1; Algoritmo a priori

Entrada: Conjunto de datos D; número mínimo de soporte minsup_count; Salida: Conjunto de elementos frecuentes L L1={conjuntos de 1 elemento grande} Para (k=2; Lk-1≠Φ; k)<. /p>

Ck=apriori-gen (Lk-1); // Ck es un conjunto candidato de k elementos Para todas las transacciones t∈D

comenzar Ct=subset(Ck, t) ; //Ct es el elemento del conjunto de candidatos contenido en todos los t para todos los candidatos c ∈Ct do c.count; end

Lk={c ∈Ck c.count ≧ minsup_count } End L=∪Lk| ;

2. algoritmo de generación de conjuntos candidatos apriori-gen (Lk-1) entrada: (k-1)-conjunto de elementos frecuentes Lk-1 salida: k-conjunto de elementos frecuentes Ck

Para todo el conjunto de elementos p ∈Lk-1 hacer Para todo el conjunto de elementos q∈Lk-1 hacer

Si p.item1=q.item1, p.item2=q.item2, …, p.itemk-2=q .itemk- 2. p.itemk-1

si has_infrequent_subset(c, Lk-1) entonces elimina c, de lo contrario agrega c a Ck End Return Ck

3. has_infrequent_subset(c, Lk-1 ) Función: Determinar los elementos del conjunto candidato

Entrada: Un conjunto de elementos frecuentes k Lk-1, conjunto de elementos frecuentes (k-1) Lk-1 Salida: Juicio booleano de si c es eliminado del conjunto de candidatos Para todos los subconjuntos (k-1) de c, si no (S∈Lk-1) ENTONCES devuelve VERDADERO; Devuelve FALSO

4. Generación de reglas (L, minconf) Entrada: conjunto de elementos frecuentes; Salida de confianza mínima: Algoritmo de regla de asociación fuerte:

PARA cada conjunto de elementos frecuentes lk en L generules(lk, lk

5. Algoritmo recursivo de reglas:

Genrules(lk: conjunto de elementos k frecuente, xm: conjunto de elementos m frecuente) X={(m-1)-conjuntos de elementos xm-1 | xm-1 en xm};

BEGIN conf=support(lk)/support(xm-1); IF (conf≧minconf) THEN

Instrucciones para el experimento de minería de datos del Departamento de Ciencias de la Información y la Computación de la Universidad de Changsha

COMENZAR

Reglas de salida: xm-1-gt; (lk-xm-1), soporte, confianza

e;

IF (m-1)gt; 1) ENTONCES genrules(lk, xm-1);

FINAL; >

Depurar el algoritmo en función de datos de muestra relevantes y analizar los datos en función de resultados experimentales relevantes.

IV. Requisitos del informe del experimento

1. Utilice el lenguaje C para implementar. algoritmos relacionados anteriores.

2. Pasos de la operación experimental y resultados experimentales, problemas ocurridos durante el experimento y sus soluciones.

5. Notas

1. Representación de conjuntos e implementación de operaciones relacionadas

2. Descripción de la estructura de datos del conjunto de elementos

Página 21