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

1、数据仓库与数据挖掘实验数据挖掘实验指导书数据挖掘实验指导书xx 年 3 月 1 日长沙学院信息与计算科学系前言随着数据库技术的发展，特别是数据仓库以及Web等新型数据源的日益普及，形成了数据丰富，知识缺乏的严重局面。针对如何有效地利用这些海量的数据信息的挑战， 数据挖掘技术应运而生， 并显示出强大的生命力。 数据挖掘技术使数据处理技术进入了一个更高级的阶段， 是对未来人类产生重大影响的十大新兴技术之一。 因此加强数据挖掘领域的理论与实践学习也已成为专业学生的必修内容。本实验指导书通过大量的实例，循序渐进地引导学生做好各章的实验。根据实验教学大纲， 我们编排了五个实验，每个实验又分了五部分内容：

2、实验目的、实验内容、实验步骤、实验报告要求、注意事项。在实验之前，由教师对实验作一定的讲解后，让学生明确实验目的，并对实验作好预习工作。在实验中，学生根据实验指导中的内容进行验证与，然后再去完成实验步骤中安排的任务。实验完成后，学生按要求完成实验报告。整个教学和实验中， 我们强调学生切实培养动手实践能力，掌握数据挖掘的基本方法。实验一 K-Means 聚类算法实现一、实验目的通过分析 K-Means 聚类算法的聚类原理，利用 Vc 编程工具编程实现 K-Means 聚类算法，并通过对样本数据的聚类过程，加深对该聚类算法的理解与应用过程。 实验类型：验证计划课间： 4 学时二、实验内容1 、分析

3、 K-Means 聚类算法； 2 、分析距离计算方法； 3 、分析聚类的评价准则；4 、编程完成K-Means 聚类算法，并基于相关实验数据实现聚类过程；三、实验方法1.1 、 K-means 聚类算法原理K-means 聚类算法以 k 为参数， 把 n 个对象分为 k 个簇， 以使簇内的具有较高的相似度。 相似度的计算根据一个簇中对象的平均值来进行。 算法描述：输入：簇的数目 k 和包含 n 个对象的数据库输出：使平方误差准则最小的 k 个簇 过程：任选 k 个对象作为初始的簇中心； Repeatfor j=1 to n DO根据簇中对象的平均值，将每个对象赋给最类似的簇for i=1 to

4、k DO 更新簇的平均值计算 EUnitl E 不再发生变化 按簇输出相应的对象1.2 、聚类评价准则：E 的计算为：E =EE|x -xi =1x C iki|2四、实验步骤 4.1 实验数据P192 ： 151.3 初始簇中心的选择 选择 k 个样本作为簇中心For (i=0;iFor (j=0;jClusterCenterij=DataBaseij1.4 数据对象的重新分配Sim= 某一较大数； ClusterNo=-1;For (i=0;iIf (Distance(DataBasej,ClusterCenteri)ClusterNo=i;ObjectClusterj=ClusterNo

5、;1.5 簇的更新For (i=0;iTemp=0;Num=0; For (j=0;jIf (ObjectClusterj=i)Num+; Temp+=DataBasej; If (ClusterCenteri!=Temp) HasChanged=TRUE;ClusterCenteri=Temp; 1.6 结果的输出 For (i=0;iPrintf(“输出第m簇的对象:i); For (j=0;jIf (ObjectClusterj=i) printf( “%d ” ,j); Printf(“n ” );Printf(“ttt簇平均值为 (%d,%d)n” , ClusterCenteri0

6、,ClusterCenteri1); 五、注意事项 1 、距离函数的选择2 、评价函数的计算实验二DBSCANI法实现一、实验目的要求掌握DBSCANT法的聚类原理、了解DBSCANT法的执行过程 在此基础上，利用DBSCANT法对给定样本数据实现聚类过程。实验类型：综合计划课间： 4 学时二、实验内容1 、了解DBSCANT法的聚类原理；2、了解DBSCANT法的执行 过程；3、编程实现DBSCANT法；4、对给定样本数据实现聚类过 程三、实验方法3.1 、DBSCANI：法的基本概念 对象的£-邻域：给定对象在半径£内的区域； 核心对象：若一个对象e -邻域至少包含最小

7、数目 MinPts个 对象，则称该对象为核心对象； 直接密度可达：给定一个对象集合 D ,若p是在q的e -邻 域内，而 q 是一个核心对象，则称对象p 从对象 q 出发是直接密度可达的； 密度可达：若存在一个对象链p1,p2, ?,pn,p1=q,pn=p, 对 pi6 D,pi+1 是从 pi关于e和MinPts直接密度可达的，则称对象p是从对象q关于 e和MinPts是密度可达的； 密度相连：若对象集合D 中存在一个对象o ，使得对象p 和q是从o关于&和MinPts是密度可达的，则对象p和q是关于e和MinPts密度相连的； 噪声： 一个基于密度的簇是基于密度可达性的最大的密度

8、相连对象的集合，不包含在任何簇中的对象被认为是噪声3.2 、实现的基本通过检查数据集中每个对象的e -邻域来寻找聚类。如一个点p的 e-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新 簇。然后，DBSCA用我从这些核心对象直接密度可达的对象，这个 过程可能涉及一些密度可达簇的合并， 当没有新的点可以被添加到任何簇时，聚类过程结束。3.3 算法描述输入：包含 n 个对象的数据库，半径，最小数目 MinPts; 输出： 所有生成的簇，达到密度要求 过程： Repeat从数据库中抽取一个未处理的点；IF 抽出的点是核心点 THEN 找出所有从该店密度可达的对象， 形成一个簇； ELSE

9、 抽出的点是边缘点 （非核心对象） ， 跳出本次循环，寻找下一点； Until 所有点都被处理四、实验步骤 4.1 数据结构的分析 Struct ListInt dataTOTALPOINT; Int head=0; Int tail=-1; ListClusterList; Struct Node1.1 int Attribute1; int Attribute2 NodeDataBaseTOTALPOINT;Boolean NeighborTOTALPOINTTOTALPOINT; IntClusterNoTOTALPOINT;1.2 实验数据 P186 表 5-81.3 计算临近For

10、（i=0;iFor (j=0;jIf (dist(DataBasei,DataBasei)1.4 聚类划分 CurrentClusterNO=0; For (i=0;iNeighborPointsNum=0;for (j=0;jif (Neighborij=true)NeighborPointsNum+; if (NeighborPointsNum)>=MinPts 1.5 记录邻居中已被划分的簇号ClusterList.tail=-1;ClusterList.head=0; For (j=0;jIf (Neighborij=true) &&(ClusterNoj>

11、0)Then ClusterList.tail+;当前核心对象的邻ClusterList.datatail=ClusterNoj /居对象划分为一簇For (j=0;jClusterNoj=CurrentClusterNO;/ 将多个簇合并While ClusterList.headIf (ClusterNoj=ClusterList.datahead)ClusterNoj=CurrentClusterNO;ClusterList.head+; 4.5 聚类结果输出For (i=-1;iPrintf( "n 输出第 曦的对象：" ，i); For (j=0;j%dt ” ,

12、j); If (ClusterNoj=i) printf(五、注意事项 5.1. 噪声数据的处理5.2 已划分的类存在直接密度可达时的相关类数据的合并实验三 ID3 算法实现一、实验目的通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。加深对相关算法的理解过程。 实验类型：验证计划课间： 4 学时二、实验内容1 、分析决策树算法的实现流程；2 、 分析信息增益的计算、 数据子集划分、 决策树的构建过程； 3 、 根据算法描述编程实现算法，调试运行； 4 、对课后 P161 的第 10题 进行验算，得到分析结果。三、实验方法算法描述：以代表训练样本的单个结点开始建树；若样本

13、都在同一个类，则该结点成为树叶，并用该类标记；否则，算法使用信息增益作为启发信息，选择能够最好地将样本分类的属性； 对测试属性的每个已知值，创建一个分支，并据此划分样本； 算法使用同样的过程，递归形成每个划分上的样本决策树递归划分步骤，当下列条件之一成立时停止： 给定结点的所有样本属于同一类；没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行四、实验步骤1 、算法实现过程中需要使用的数据结构描述： Structint Attrib_Col; / 当前节点对应属性 int Value; / 对应边值 Tree_Node* Left_Node; / 子树Tree_Node* Right_

14、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;分配内存 DataNum_RecordNum_Attrib;输入样本数据DataNum_RecordNum_Attrib ； 获取类别数C(从最后一列中得到)；3

15、 .2 、 Build_ID3(Data,Record_No, Num_Attrib)Int Class_DistributeC;If (Record_No=0) return Null N=new tree_node();计算 Data 中各类的分布情况存入 Class_DistributeTemp_Num_Attrib=0;For (i=0;iIf (Data0i>=0) Temp_Num_Attrib+; IfTemp_Num_Attrib=0 N->ClassNo= 最多的类； N->IsLeaf=TRUE;N->Left_Node=NULL;N->Rig

16、ht_Node=NULL; Return N;If Class_DistributeN->ClassNo= 该类； N->IsLeaf=TRUE;N->Left_Node=NULL;N->Right_Node=NULL; Return N; InforGain=0;CurrentCol=-1;For i=0;iTempGain=Compute_InforGain(Data,Record_No,I,Num_Attrib);If (InforGain InforGain=TempGain; CurrentCol=I; N->Attrib_Col=CurrentCol;

17、/ 记录 CurrentCol 所对应的不同值放入 DiferentValue ；I=0;Value_No=-1; While iFor (k=0;kif (DiferentValuk=DataiCurrentCol) flag=true; if (flag=false)Value_No+;DiferentValueValue_No=DataiCurrentColI+; SubData= 以 Data 大小内存空间； For (i=0;ik=-1;for (j=0;jif (DatajCurrentCol=DiferentValui) k=k+;For(int i1=0;i1If (i1Cur

18、rentCol)SubDataki1=Dataji1; ElseSubDataki1=-1; N->Attrib_Col=CurrentCol; N->Value=DiferentValui;N->Isleaf=false; N->ClassNo=0;N->Left_Node=Build_ID3(SubData,k+1, Num_Attrib);N->Right_Node=new Tree_Node; N=N->Right_Node; 4 .3 、计算增益Compute_InforGain(Data,Record_No, Col_No, Num_Att

19、rib)Int DifferentValueMaxDifferentValue; IntTotal_DifferentValue;Int sClassNoMaxDifferentValue;s=0;/ 数组清 0;Total_DifferentValue=-1; For (i=0;iJ=GetPosition(DifferentValue,Total_DifferentValue,DataiCol_no); If (jDifferentValueTotal_DifferentValue=DataiCol_no;J=Total_DifferentValue;SDataiNum_Attrib-1j

20、+; Total_I=0;For (i=0;iSum=0;For(j=0;jFor (i=0;i temp=0;sj=0; /sj 是数据子集中属于类j 的样本个数； For(j=0;jFor (j=0;jEA+=sj/Record_No*Compute_PI(sji/sj); Return total_I-EA; 3.4 、得到某数字在数组中的位置GetPosition(Data,DataSize,Value) For (i=0;i3.5 、计算 Pi*LogPiFloat Compute_PI(float pi) If pi=1 then return 0; Return 0-pi*log

21、2(pi); 五、实验报告要求1 、用 C 语言实现上述相关算法。2 、实验操作步骤和实验结果，实验中出现的问题和解决方法。六、注意事项1 、信息增益的计算；3、2 、 选择相关字段后根据相关字段的取值对数据集合进行划分。决策树构建的终止条件实验四 贝叶斯算法实现一、实验目的通过对贝叶斯算法的编程实现，加深对贝叶斯算法的理解，同时利用贝叶斯算法对简单应用实现预测分类 实验类型：验证 课间： 4学时二、实验内容1 、分析贝叶斯算法； 2 、计算条件概率； 3 、预测精度的计算与评估；4 、 编程实现贝叶斯分类算法， 并对简单应用样本数据实现预测分类三、实验方法1 、 实现贝叶斯算法2 、 利用实

22、验数据对贝叶斯算法进行检测 3 、 求解精确度计算4 、调试程序5 、 完成整个分类与评估的过程四、实验步骤4.1 算法过程描述：1 ）输入训练数据，将数据保存在DataBase 二维数组中 （数组的最后一个属性对应类别标号） 2 ）设定训练数据集与测试数据集大小（ 指定从数组下标 0 开始到 TrainSetSize-1 所对应的数据为训练数据，其余为测试数据） ；3 ）计算训练数据集数据中各属性在各类中的概率分布情况； 4 ）利用测试数据计算贝叶斯算法的分类精度； 5 ）输出分类结果； 4.2数据处理B 、对数据中的枚举类型数据进行转换以便于数据处理：4.3 计算训练数据集数据中各属性在各

23、类中的概率分布情况如图3-1 所示 4.4 利用测试数据计算贝叶斯算法的分类精度如图 3-2 所示图 3-1 训练数据集各属性的概率分布计算图 3-2 贝叶斯算法的分类精度计算4.5 输出分类结果For (i=0;iFor (j=0;jprintf( “nnTotal Correct is%d ” ,TotalCorrect);五、注意事项注意单个样例数据的概率计算与各字段的概率计算的关系实验五 Apriori 算法实现、实验目的1 、掌握 Apriori 算法对于关联规则挖掘中频繁集的产生以及关联规则集合的产生过程； 2 、 根据算法描述编程实现算法， 调试运行。并结合相关实验数据进行应用，

24、得到分析结果。 数据和删除数据的操作。 实验类型：验证计划课间： 2 学时二、实验内容2 、频繁项集的生成与Apriori 算法实现；3 、关联规则的生成过程与Rule-generate 算法实现； 3 、结合样例对算法进行分析；三、实验步骤编写程序完成下列算法： 1 、 Apriori 算法输入： 数据集 D ；最小支持数minsup_count ； 输出： 频繁项; k+)L L1=large 1-itemsets For (k=2; Lk-1Ck=apriori-gen (Lk-1); / Ck是 k 个元素的候选集For alltransactions t 6 D dobegin Ct=subset(Ck,t); /Ct 是所有 t 包含的候选集元素 for all candidates c 6 Ct do c.count+; endLk=c Ck| c.count m minsup_count End L= U Lk;2 、 apriori-gen (Lk-1) 候选集产生算法输入： (k-1)- 频繁项目集 Lk-1 输出： k- 频繁项目集CkFor all itemset p Lk-1 do For all itemset q Lk-1 doIf p.item1=q.item1, p.item2=q.item2, ，p.