数据仓库与数据挖掘实验数据挖掘实验指导书.docx

数据仓库与数据挖掘实验数据挖掘实验指导书《数据挖掘》实验指导书XX年3月1日长沙学院信息与计算科学系_、八 、，前言随着数据库技术的发展，特别是数据仓库以及Web等新型数据源 的日益普及，形成了数据丰富，知识缺乏的严重局面针对如何有效 地利用这些海量的数据信息的挑战，数据挖掘技术应运而生，并显示 出强大的生命力数据挖掘技术使数据处理技术进入了一个更高级的 阶段，是对未来人类产生重大影响的十大新兴技术之一因此加强数 据挖掘领域的理论与实践学习也已成为专业学生的必修内容本实验指导书通过大量的实例，循序渐进地引导学生做好各章的 实验根据实验教学大纲，我们编排了五个实验，每个实验又分了五 部分内容：实验目的、实验内容、实验步骤、实验报告要求、注意事 项在实验之前，由教师对实验作一定的讲解后，让学生明确实验目 的，并对实验作好预习工作在实验中，学生根据实验指导中的内容 进行验证与，然后再去完成实验步骤中安排的任务实验完成后，学 生按要求完成实验报告整个教学和实验中，我们强调学生切实培养 动手实践能力，掌握数据挖掘的基本方法实验一 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个对象作为初始的簇中心；Repeatfor j=1 to n DO根据簇中对象的平均值，将每个对象赋给最类似的簇 for i=1 tok DO更新簇的平均值计算EUnitl E不再发生变化按簇输出相应的对象2、聚类评价准则：E的计算为：E =工工x -xi =1x EC iki|2四、实验步骤 4.1 实验数据P192：154.2初始簇中心的选择 选择k个样本作为簇中心For (i=0;iFor (j=0;jClusterCenter[i][j]=DataBase[i][j]4. 3数据对象的重新分配Sim二某一较大数；ClusterNo=T;For (i=0;iIf (Distance(DataBase[j],ClusterCenter[i])ClusterNo=i;}ObjectCluster[j]=ClusterNo;4.4簇的更新For (i=0;i{Temp=0;Num=0; For (j=0;jIf (ObjectCluster[j]==i){Num++; Temp+=DataBase[j];} If(ClusterCenter[i]!=Temp) HasChanged=TRUE;ClusterCenter[i]=Temp; }4.5结果的输出 For (i=0;iPrin tf（“输出第 %d 个簇的对象：”，i）; For （j=0;jIf (ObjectCluster[j]==i) printf(“%d ”,j); Printf(“\n”);Printf“\t\t\t 簇平均值为（％d,%d）\n”，ClusterCenter[i][0],ClusterCenter[i][l]）; }五、注意事项1、距离函数的选择2、评价函数的计算实验二DBSCAN算法实现一、 实验目的要求掌握DBSCAN算法的聚类原理、了解DBSCAN算法的执行过程。

在此基础上，利用DBSCAN算法对给定样本数据实现聚类过程实验类型：综合计划课间：4学时二、 实验内容1、了解DBSCAN算法的聚类原理；2、了解DBSCAN算法的执行过程；3、编程实现DBSCAN算法；4、对给定样本数据实现聚类过 程三、实验方法3.1、DBSCAN 算法的基本概念•对象的£-邻域：给定对象在半径£内的区域；•核心对象：若一个对象£-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象；•直接密度可达：给定一个对象集合D，若p是在q的£-邻域内，而q是一个核心对象，则称对象p从对象q出发是直接密度可达的；•密度可达：若存在一个对象链pl,p2, ?, pn,p1=q,pn=p,对 piWD,pi+l 是从 pi关于£和MinPts直接密度可达的，则称对象p是从对象q关于£和MinPts是密度可达的；•密度相连：若对象集合D中存在一个对象o ,使得对象p和 q是从o关于£和MinPts是密度可达的，则对象p和q是关于£和MinPts密度 相连的； •噪声：一个基于密度的簇是基于密度可达性的最大的密 度相连对象的集合，不包含在任何簇中的对象被认为是噪声3.2、实现的基本通过检查数据集中每个对象的£-邻域来寻找聚类。

如一个点p的 £-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新 簇然后，DBSCAN寻找从这些核心对象直接密度可达的对象，这个 过程可能涉及一些密度可达簇的合并，当没有新的点可以被添加到任 何簇时，聚类过程结束3.3算法描述输入：包含n个对象的数据库，半径，最小数目MinPts;输出： 所有生成的簇，达到密度要求过程： Repeat从数据库中抽取一个未处理的点；IF 抽出的点是核心点 THEN 找出所有从该店密度可达的对象，形成一个簇；ELSE抽出的点是边缘点（非核心对象），跳出本次循环，寻找下一点； Until 所有点都被处理四、实验步骤 4.1 数据结构的分析 Struct List{Int data[TOTALPOINT]; Int head=0; Int tail=-1;} ListClusterList; Struct Node{ int Attribute1; int Attribute2} NodeDataBase[TOTALPOINT];Boolean Neighbor[TOTALPOINT][TOTALPOINT]; IntClusterNo[TOTALPOINT];4.2实验数据 P186 表5-84.3计算临近For （i=0;iFor (j=0;jIf (dist(DataBase[i],DataBase[i])4.4聚类划分 CurrentClusterNO=0; For (i=0;iNeighborPointsNum=0;for (j=0;jif (Neighbor[i][j]==true)NeighborPointsNum++; if (NeighborPointsNum)>=MinPts {// 记录邻居中已被划分的簇号 ClusterList.tail=-1;ClusterList.head=0; For (j=0;jIf (Neighbor[i][j]==true) &&(ClusterNo[j]>0)Then {ClusterList.tail++;ClusterList.data[tail]=ClusterNo[j]} //当前核心对象的邻 居对象划分为一簇 For (j=0;jClusterNo[j]=CurrentClusterNO;// 将多个簇合并While ClusterList.headIf (ClusterNo[j]==ClusterList.data[head])ClusterNo[j]=CurrentClusterNO;ClusterList.head++; } } }4.5聚类结果输出For (i=-1;iPrintf(“\n 输出第%d 簇的对象：”，i); For (j=0;jIf (ClusterNo[j]=i) printf(“%d\t”,j); }五、注意事项 5.1. 噪声数据的处理5.2已划分的类存在直接密度可达时的相关类数据的合并实验三ID3算法实现一、 实验目的通过编程实现决策树算法，信息增益的计算、数据子集划分、决 策树的构建过程。

加深对相关算法的理解过程实验类型：验证计 划课间：4学时二、 实验内容1、 分析决策树算法的实现流程；2、 分析信息增益的计算、数据子集划分、决策树的构建过程； 3、 根据算法描述编程实现算法，调试运行；4、对课后P161的第10题 进行验算，得到分析结果三、实验方法算法描述：以代表训练样本的单个结点开始建树；若样本都在同一个类，则该结点成为树叶，并用该类标记；否则，算法使用信息增益作为启发信息，选择能够最好地将样本 分类的属性；对测试属性的每个已知值，创建一个分支，并据此划 分样本；算法使用同样的过程，递归形成每个划分上的样本决策树 递归划分步骤，当下列条件之一成立时停止：给定结点的所有样本 属于同一类；没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行四、实验步骤1、算法实现过程中需要使用的数据结构描述： Struct{int Attrib_Col; //当前节点对应属性 int Value; //对应边 值 Tree_Node* Left_Node; //子树Tree_Node* Right_Node //同层其他节点 Boolean IsLeaf; // 是否叶子节点 int ClassNo; //对应分类标号 }Tree_Node;2、整体算法流程主程序：InputData();T=Build_ID3(Data,Record_No, Num_Attrib); OutputRule(T);释放内存; 3、相关子函数： 3.1、 InputData(){输入属性集大小Num_Attrib;输入样本数Num_Record;分配内存 Dat a[Num_Record][Num_A tt rib];输入样本数据Data[Num_Record][Num_Attrib]；获取类别数C(从最后一列中得到)；}3.2、Build_ID3(Data,Record_No, Num_Attrib)Int Class_Distribute[C];If (Record_No==0) { return Null }N=new tree_node();计算Data中各类的分布情况存入Class_DistributeTemp_Num_Attrib=0;For (i=0;iIf (Data[0][i]>=0) Temp_Num_Attrib++; IfTemp_Num_Attrib==0 {N-〉ClassNo二最多的类；N-〉IsLeaf二TRUE;N->Left_Node=NULL;N->Right_Node=NULL; Return N;}If Class_Distribute中仅一类的分布大于0 {N-〉ClassNo 二该类；N-〉IsLeaf二TRUE;N->Left_Node=NULL;N->Right_Node=NULL; Return N; }InforGain=0;CurrentCol=-1;For i=0;iTempGain=Compute_InforGain(Dat。