数据挖掘实验指导书

《数据挖掘》实验指导书2011年3月1日长沙学院信息与计算科学系前言随着数据库技术的发展，特别是数据仓库以及Web等新型数据源的日益普及，形成了数据丰富，知识缺乏的严重局面。针对如何有效地利用这些海量的数据信息的挑战，数据挖掘技术应运而生，并显示出强大的生命力。数据挖掘技术使数据处理技术进入了一个更高级的阶段，是对未来人类产生重大影响的十大新兴技术之一。因此加强数据挖掘领域的理论与实践学习也已成为专业学生的必修内容。本实验指导书通过大量的实例，循序渐进地引导学生做好各章的实验。根据实验教学大纲，我们编排了五个实验，每个实验又分了五部分内容：实验目的、实验内容、实验步骤、实验报告要求、注意事项。在实验之前，由教师对实验作一定的讲解后，让学生明确实验目的，并对实验作好预习工作。在实验中，学生根据实验指导中的内容进行验证与总结，然后再去完成实验步骤中安排的任务。实验完成后，学生按要求完成实验报告。整个教学和实验中，我们强调学生切实培养动手实践能力，掌握数据挖掘的基本方法。长沙学院信息与计算科学系数据挖掘实验指导书第3页实验一K-Means聚类算法实现一、实验目的通过分析K-Means聚类算法的聚类原理，利用Vc编程工具编程实现K-Means聚类算法，并通过对样本数据的聚类过程，加深对该聚类算法的理解与应用过程。实验类型：验证计划课间：4学时二、实验内容1、分析K-Means聚类算法；2、分析距离计算方法；3、分析聚类的评价准则；4、编程完成K-Means聚类算法，并基于相关实验数据实现聚类过程；三、实验方法1、K-means聚类算法原理K-means聚类算法以k为参数，把n个对象分为k个簇，以使簇内的具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行。算法描述：输入：簇的数目k和包含n个对象的数据库输出：使平方误差准则最小的k个簇过程：任选k个对象作为初始的簇中心；Repeatforj=1tonDO根据簇中对象的平均值，将每个对象赋给最类似的簇fori=1tokDO更新簇的平均值计算EUnitlE不再发生变化按簇输出相应的对象2、聚类评价准则：E的计算为：kiCxiixxE12||长沙学院信息与计算科学系数据挖掘实验指导书第4页四、实验步骤4.1实验数据P192：154.2初始簇中心的选择选择k个样本作为簇中心For(i=0;ik;i++)For(j=0;jAttSetSize;j++)ClusterCenter[i][j]=DataBase[i][j]4.3数据对象的重新分配Sim=某一较大数；ClusterNo=-1;For(i=0;ik;i++)If(Distance(DataBase[j],ClusterCenter[i])Sim){Sim=Distance(DataBase[j],ClusterCenter[i]);ClusterNo=i;}ObjectCluster[j]=ClusterNo;4.4簇的更新For(i=0;ik;i++){Temp=0;Num=0;For(j=0;jn;j++)If(ObjectCluster[j]==i){Num++;Temp+=DataBase[j];}If(ClusterCenter[i]!=Temp)HasChanged=TRUE;ClusterCenter[i]=Temp;}4.5结果的输出For(i=0;ik;i++){Printf(“输出第%d个簇的对象:”，i);For(j=0;jn;j++)长沙学院信息与计算科学系数据挖掘实验指导书第5页If(ObjectCluster[j]==i)printf(“%d”,j);Printf(“\n”);Printf(“\t\t\t簇平均值为(%d,%d)\n”,ClusterCenter[i][0],ClusterCenter[i][1]);}五、注意事项1、距离函数的选择2、评价函数的计算长沙学院信息与计算科学系数据挖掘实验指导书第6页实验二DBSCAN算法实现一、实验目的要求掌握DBSCAN算法的聚类原理、了解DBSCAN算法的执行过程。在此基础上，利用DBSCAN算法对给定样本数据实现聚类过程。实验类型：综合计划课间：4学时二、实验内容1、了解DBSCAN算法的聚类原理；2、了解DBSCAN算法的执行过程；3、编程实现DBSCAN算法；4、对给定样本数据实现聚类过程三、实验方法3.1、DBSCAN算法的基本概念对象的ε-邻域：给定对象在半径ε内的区域；核心对象：若一个对象ε-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象；直接密度可达：给定一个对象集合D，若p是在q的ε-邻域内，而q是一个核心对象，则称对象p从对象q出发是直接密度可达的；密度可达：若存在一个对象链p1,p2,…,pn,p1=q,pn=p,对pi∈D,pi+1是从pi关于ε和MinPts直接密度可达的，则称对象p是从对象q关于ε和MinPts是密度可达的；密度相连：若对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts是密度可达的，则对象p和q是关于ε和MinPts密度相连的；噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合，不包含在任何簇中的对象被认为是噪声3.2、实现的基本思想通过检查数据集中每个对象的ε-邻域来寻找聚类。如一个点p的ε-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并，当没有新的点可以被添加到任何簇时，聚类过程结束。长沙学院信息与计算科学系数据挖掘实验指导书第7页3.3算法描述输入：包含n个对象的数据库，半径，最小数目MinPts;输出：所有生成的簇，达到密度要求过程：Repeat从数据库中抽取一个未处理的点；IF抽出的点是核心点THEN找出所有从该店密度可达的对象，形成一个簇；ELSE抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点；Until所有点都被处理四、实验步骤4.1数据结构的分析StructList{Intdata[TOTALPOINT];Inthead=0;Inttail=-1;}ListClusterList;StructNode{intAttribute1;intAttribute2}NodeDataBase[TOTALPOINT];BooleanNeighbor[TOTALPOINT][TOTALPOINT];IntClusterNo[TOTALPOINT];4.2实验数据P186表5-84.3计算临近For(i=0;iTOTALPOINT;i++)For(j=0;jTOTALPOINT;j++)If(dist(DataBase[i],DataBase[i])εthenNeighbor[i][j]=true;Neighbor[j][i]=true;长沙学院信息与计算科学系数据挖掘实验指导书第8页4.4聚类划分CurrentClusterNO=0;For(i=0;iTOTALPOINT;i++){NeighborPointsNum=0;for(j=0;jTOTALPOINT;j++)if(Neighbor[i][j]==true)NeighborPointsNum++;if(NeighborPointsNum)=MinPts{//记录邻居中已被划分的簇号ClusterList.tail=-1;ClusterList.head=0;For(j=0;jTOTALPOINT;j++)If(Neighbor[i][j]==true)&&(ClusterNo[j]0)Then{ClusterList.tail++;ClusterList.data[tail]=ClusterNo[j]}//当前核心对象的邻居对象划分为一簇For(j=0;jTOTALPOINT;j++)If(Neighbor[i][j]==true)thenClusterNo[j]=CurrentClusterNO;//将多个簇合并WhileClusterList.head=ClusterList.tail{for(j=0;jTOTALPOINT;j++)If(ClusterNo[j]==ClusterList.data[head])ClusterNo[j]=CurrentClusterNO;ClusterList.head++;}}}4.5聚类结果输出For(i=-1;iCurrentClusterNO;i++);长沙学院信息与计算科学系数据挖掘实验指导书第9页{Printf(“\n输出第%d簇的对象：”,i);For(j=0;jTOTALPOINT;j++)If(ClusterNo[j]=i)printf(“%d\t”,j);}五、注意事项5.1.噪声数据的处理5.2已划分的类存在直接密度可达时的相关类数据的合并长沙学院信息与计算科学系数据挖掘实验指导书第10页实验三ID3算法实现一、实验目的通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。加深对相关算法的理解过程。实验类型：验证计划课间：4学时二、实验内容1、分析决策树算法的实现流程；2、分析信息增益的计算、数据子集划分、决策树的构建过程；3、根据算法描述编程实现算法，调试运行；4、对课后P161的第10题进行验算，得到分析结果。三、实验方法算法描述：以代表训练样本的单个结点开始建树；若样本都在同一个类，则该结点成为树叶，并用该类标记；否则，算法使用信息增益作为启发信息，选择能够最好地将样本分类的属性；对测试属性的每个已知值，创建一个分支，并据此划分样本；算法使用同样的过程，递归形成每个划分上的样本决策树递归划分步骤，当下列条件之一成立时停止：给定结点的所有样本属于同一类；没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行四、实验步骤1、算法实现过程中需要使用的数据结构描述：Struct{intAttrib_Col;//当前节点对应属性intValue;//对应边值Tree_Node*Left_Node;//子树Tree_Node*Right_Node//同层其他节点BooleanIsLeaf;//是否叶子节点intClassNo;//对应分类标号}Tree_Node;长沙学院信息与计算科学系数据挖掘实验指导书第11页2、整体算法流程主程序：InputData();T=Build_ID3(Data,Record_No,Num_Attrib);OutputRule(T);释放内存;3、相关子函数：3.1、InputData(){输入属性集大小Num_Attrib;输入样本数Num_Record;分配内存Data[Num_Record][Num_Attrib];输入样本数据Data[Num_Record][Num_Attrib]；获取类别数C(从最后一列中得到);}3.2、Build_ID3(Data,Record_No,Num_Attrib){IntClass_Distribute[C];If(Record_No==0){returnNull}N=newtree_node();计算Data中各类的分布情况存入Class_DistributeTemp_Num_Attrib=0;For(i=0;iNum_Attrib;i++)If(Data[0][i]=0)Temp_Num_Attrib++;IfTemp_Num_Attrib==0{N-ClassNo=最多的类；N-IsLeaf=TRUE;N-Left_Node=NULL;N-Right_Node=NULL;ReturnN;}IfClass_Distribute中仅一类的分布大于0{N-ClassNo=该类；N-IsLeaf=TRUE;N-Left_Node=NULL;N-Right_Node=NULL;ReturnN;}InforGain=0;CurrentCol=