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 enormes cantidades 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 K-Means
1. Propósito del experimento
Analizando el principio de agrupamiento del algoritmo de agrupamiento 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 For (i=0;i
For (j=0;j
ClusterCenter[i][j]=DataBase[i][j]
4.3 Reasignación de objetos de datos
Sim=un cierto número grande; 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\tLa media 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 experimental
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 Tiempo de clase: 4 horas
2. Contenido del experimento
1. Comprender el principio de agrupamiento del algoritmo DBSCAN 2. Comprender el; Algoritmo DBSCAN El 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
3.1. Algoritmo DBSCAN
● ε-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 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 densidad directamente alcanzable desde pi
con respecto a ε y MinPts, entonces el objeto p se dice ser 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 en densidad 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 densidad; accesibilidad,
no está incluido en ningún clúster Los objetos se consideran ruido
3.2 Idea básica de implementación
Los clústeres se encuentran examinando el vecindario ε. 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];
Vecino booleano[ 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
NeighborPointsNum=0;
for (j=0;j
if (Neighbor[i][j]= =true)NeighborPointsNum++ ; if (NeighborPointsNum)>=MinPts {
// Registre los números de clúster que se han dividido en el vecino ClusterList.tail=-1; /p>
Si (Vecino[i][j]==true) &&(ClusterNo[j]>0)
Entonces {ClusterList.tail++;
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;< / p>
ClusterList.head++; } } }
4.5 Salida del resultado de agrupación
For (i=-1;i
Printf(“ \nSalida el 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 tres 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 del á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 int Valor; Tree_Node* Left_Node; // Subtree
Tree_Node* Right_Node // Otros nodos en la misma capa Boolean IsLeaf; // Si es un nodo hoja int ClassNo; // Etiqueta de clasificación correspondiente}Tree_Node;
2. Programa principal del proceso general del algoritmo:
InputData();
T=Build_ID3(Data,Record_No, Num_Attrib(T); 3. Subfunciones relacionadas: 3.1, InputData()
{
Tamaño del conjunto de atributos de entrada Num_Attrib; Número de muestra de entrada Num_Record;
Asignar datos de memoria[; Num_Record][Num_Attrib];
Ingrese datos de muestra Data[Num_Record][Num_Attrib ]; Obtenga el número de categoría C (obtenido de la última columna)
3.2. ,Record_No, Num_Attrib)
{
Int Class_Distribute[ C];
If (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]>=0) Temp_Num_Attrib++; If Temp_Num_Attrib==0 {
N->ClassNo=la mayor cantidad de clases;
N->Left_Node=NULL; N->Right_Node=NULL; Devuelve N;
}
Si la distribución de una sola clase en Class_Distribute es mayor que 0 {
N->ClassNo=esta clase; N->IsLeaf=TRUE;
N->Left_Node=NULL;N->Right_Node=NULL Devuelve N; > InforGain=0;CurrentCol=-1;
For i=0;i
TempGain=Compute_InforGain(Data,Record_No,I,Num_Attrib If (InforGain
);{ InformaciónGain=
TempGain; CurrentCol=I;} }
N->Attrib_Col=CurrentCol;
//Registra los diferentes valores correspondientes a CurrentCol y colócalos en DiferentValue[]; 0;Value_No= -1; Mientras que
For (k=0;k
if (DiferentValu[k]=Data[i][CurrentCol]) flag=true; if (flag== false)
{Value_No++;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->Attrib_Col=CurrentCol; N->Value=DiferentValu[i]; 0;
N->Left_Node=Build_ID3(SubData,k+1, Num_Attrib); N->Right_Node=new Tree_Node; Calcular la ganancia de información
Compute_InforGain(Data,Record_No, Col_No, Num_Attrib)
Int DifferentValue[MaxDifferentValue];
Int s[ClassNo][. MaxDifferentValue];
s=0;// Borrar la matriz a 0;
Total_DifferentValue=-1; For (i=0;i
J= GetPosition(DifferentValue,
p>Total_DifferentValue,Data[i][Col_no]); If (j
DifferentValue[Total_DifferentValue]=Datos[i][Col_no]; J=Total_DifferentValue ;}
S[Data[i][Num_Attrib-1]][j]++ }
Total_I=0;
Para (i= 0;i
Suma=0;
For(j=0;j
For (i=0;i
{ temp=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 }
3.4. número en la matriz GetPosition(Data, D
ataSize,Value) {
For (i=0;i
3.5. Calcular Pi*LogPi
Float Compute_PI(float pi) {
Si pi=1 entonces devuelve 0; Devuelve 0-pi*log2(pi); }
5. Requisitos del informe del experimento
1. Utilice el lenguaje C para implementar lo anterior. algoritmos relacionados.
2. Procedimientos experimentales y resultados experimentales, problemas y soluciones durante el experimento
6. Notas
1. Cálculo de la ganancia de información ;<. /p>
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<. /p> p>
1. Propósito del experimento
Profundizar la comprensión del algoritmo bayesiano a través de la programación del algoritmo bayesiano y, al mismo tiempo, utilizar el algoritmo bayesiano para implementar la predicción y tipos de experimentos de clasificación para aplicaciones simples: Período del plan de verificación: 4 horas
2. Contenido del experimento
1. Análisis del algoritmo bayesiano 2. Cálculo de probabilidad condicional 3. Cálculo y evaluación; de precisión de predicción;
p>4. Programa para implementar el algoritmo de clasificación bayesiano e implementar clasificación predictiva para datos de muestra de aplicaciones simples
3. Métodos experimentales
1 Implementar el algoritmo bayesiano
2. Utilizar datos experimentales para probar el algoritmo bayesiano 3. Calcular la precisión de la solución 4. Depurar el programa
5. Completar todo el proceso de clasificación y evaluación<. /p>
4. Pasos experimentales
4.1 Descripción del proceso del algoritmo:
1) Ingrese los datos de entrenamiento y guarde los datos en una 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 el conjunto de datos de prueba (especifique los datos correspondientes al índice de matriz 0 en TrainSetSize-1 como datos de entrenamiento y el resto como datos de prueba)
3) Calcule el conjunto de datos de entrenamiento La distribución de probabilidad de cada atributo en los datos entre varias categorías 4) Utilice los datos de prueba para calcular la precisión de la clasificación del algoritmo bayesiano; 4.2 Procesamiento de datos
B. Convierta el tipo de datos para facilitar el procesamiento de datos:
4.3 Calcule la distribución de probabilidad de cada atributo en el conjunto de datos de entrenamiento en cada categoría, como se muestra en Figura 3-1 4.4 Utilice los datos de prueba para calcular el algoritmo bayesiano. La precisión de la clasificación se muestra en la Figura 3-2
Figura 3-1 Cálculo de la distribución de probabilidad de cada atributo del conjunto de datos de entrenamiento
Figura 3-2 Cálculo de la precisión de clasificación del algoritmo bayesiano
4.5 Resultados de clasificación de salida
For (i=0;i
For (j =0;j
printf(“\n \nTotal Correct is%d”,TotalCorrect);
5. Notas
Preste atención a la relación entre el cálculo de probabilidad de 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. Maestro el algoritmo a priori para generar 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. Según la descripción, programación, implementación, depuración y ejecución del algoritmo; Y aplíquelo junto con datos experimentales relevantes para obtener resultados de análisis. Datos y operaciones para eliminar 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 elementos grandes} 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| ;
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->(lk-xm-1),apoyo,confianza
SI (m-1)>1) ENTONCES; genrules(lk, xm-1);
END;
END
Combina el algoritmo con datos de muestra relevantes.
Lleve a cabo la depuración y analice los datos en función de los resultados experimentales relevantes.
IV. Requisitos del informe del experimento
1. Utilice el lenguaje C para implementar los algoritmos relacionados anteriormente.
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 de conjuntos de elementos
> Página 21