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

《2023年数据仓库与数据挖掘实验_数据挖掘实验指导书.docx》由会员分享，可在线阅读，更多相关《2023年数据仓库与数据挖掘实验_数据挖掘实验指导书.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、 更新簇的平均值 计算E Unitl E不再发生改变 按簇输出相应的对象 2、聚类评价准则： E 的计算为：E = |x -x i =1x C i k i |2 四、试验步骤 4.1 试验数据 P192：15 4.2初始簇中心的选择 选择k 个样本作为簇中心 For (i=0;i For (j=0;j ClusterCenterij=DataBaseij 4.3 数据对象的重新安排 Sim=某一较大数；ClusterNo=-1; For (i=0;i If (Distance(DataBasej,ClusterCenteri) ClusterNo=i; ObjectClusterj=Clust

5、erNo; 4.4 簇的更新 For (i=0;i Temp=0;Num=0; For (j=0;j If (ObjectClusterj=i)Num+; Temp+=DataBasej; If (ClusterCenteri!=Temp) HasChanged=TRUE; ClusterCenteri=Temp; 4.5 结果的输出 For (i=0;i Printf(“输出第%d个簇的对象:”，i); For (j=0;j If (ObjectClusterj=i) printf(“%d ”,j); Printf(“n”); Printf(“ttt 簇平均值为(%d,%d)n”, Clus

6、terCenteri0, ClusterCenteri1); 五、留意事项 1、距离函数的选择 2、评价函数的计算 试验二 DBSCAN算法实现 一、试验目的 要求驾驭DBSCAN 算法的聚类原理、了解DBSCAN 算法的执行过程。在此基础上，利用DBSCAN 算法对给定样本数据实现聚类过程。 试验类型：综合 安排课间：4学时 二、试验内容 1、了解DBSCAN 算法的聚类原理； 2、了解DBSCAN 算法的执行过程； 3、编程实现DBSCAN 算法； 4、对给定样本数据实现聚类过程 三、试验方法 3.1、DBSCAN 算法的基本概念 对象的-邻域：给定对象在半径内的区域； 核心对象：若一个对

7、象-邻域至少包含最小数目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 密度相连的； 噪声：一个基于密度的簇是基于密度可达性的最大

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

9、 ELSE 抽出的点是边缘点(非核心对象) ，跳出本次循环，找寻下一点； Until 全部点都被处理 四、试验步骤 4.1 数据结构的分析 Struct List Int dataTOTALPOINT; Int head=0; Int tail=-1; List ClusterList; Struct Node int Attribute1; int Attribute2 Node DataBaseTOTALPOINT; Boolean NeighborTOTALPOINTTOTALPOINT; Int ClusterNoTOTALPOINT; 4.2 试验数据 P186 表5-8 4.3 计

10、算接近 For (i=0;i For (j=0;j If (dist(DataBasei,DataBasei) 4.4 聚类划分 CurrentClusterNO=0; For (i=0;i NeighborPointsNum=0; for (j=0;j if (Neighborij=true)NeighborPointsNum+; if (NeighborPointsNum)>=MinPts / 记录邻居中已被划分的簇号 ClusterList.tail=-1; ClusterList.head=0; For (j=0;j If (Neighborij=true) &&

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

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

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

14、 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; 安排内存DataNum_RecordNum_Attrib; 输入样本数据DataNum_RecordNum_Attri

15、b； 获得类别数C(从最终一列中得到); 3.2、Build_ID3(Data,Record_No, Num_Attrib) Int Class_DistributeC; If (Record_No=0) return Null N=new tree_node(); 计算Data 中各类的分布状况存入Class_Distribute Temp_Num_Attrib=0; For (i=0;i If (Data0i>=0) Temp_Num_Attrib+; If Temp_Num_Attrib=0 N->ClassNo=最多的类； N->IsLeaf=TRUE; N->

16、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;i TempGain=Compute_InforGain(Data,Record_No,I,Num_Attrib); If (InforGain InforGain=TempGain; Cur

17、rentCol=I; N->Attrib_Col=CurrentCol; /记录CurrentCol 所对应的不同值放入DiferentValue； I=0;Value_No=-1; While i For (k=0;k if (DiferentValuk=DataiCurrentCol) flag=true; if (flag=false) Value_No+;DiferentValueValue_No=DataiCurrentCol I+; SubData=以Data 大小申请内存空间； For (i=0;i k=-1; for (j=0;j if (DatajCurrentCol=

18、DiferentValui) k=k+; For(int i1=0;i1 If (i1CurrentCol)SubDataki1=Dataji1; Else SubDataki1=-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; 3.3、计算信息增

19、益 Compute_InforGain(Data,Record_No, Col_No, Num_Attrib) Int DifferentValueMaxDifferentValue; Int Total_DifferentValue; Int sClassNoMaxDifferentValue; s=0;/ 数组清0; Total_DifferentValue=-1; For (i=0;i J=GetPosition(DifferentValue, Total_DifferentValue,DataiCol_no); If (j DifferentValueTotal_DifferentVa

20、lue=DataiCol_no; J=Total_DifferentValue; SDataiNum_Attrib-1j+; Total_I=0; For (i=0;i Sum=0; For(j=0;j For (i=0;i temp=0;sj=0; /sj是数据子集中属于类j 的样本个数； For (j=0;j For (j=0;j EA+=sj/Record_No*Compute_PI(sji/sj); Return total_I-EA; 3.4、得到某数字在数组中的位置 GetPosition(Data, DataSize,Value) For (i=0;i 3.5、计算Pi*LogP

21、i Float Compute_PI(float pi) If pi=1 then return 0; Return 0-pi*log2(pi); 五、试验报告要求 1、用C 语言实现上述相关算法。 2、试验操作步骤和试验结果，试验中出现的问题和解决方法。 六、留意事项 1、信息增益的计算； 2、选择相关字段后依据相关字段的取值对数据集合进行划分。 3、决策树构建的终止条件 试验四 贝叶斯算法实现 一、试验目的 通过对贝叶斯算法的编程实现，加深对贝叶斯算法的理解，同时利用贝叶斯算法对简洁应用实现预料分类 试验类型：验证 安排课间：4学时 二、试验内容 1、分析贝叶斯算法； 2、计算条件概率；

22、3、预料精度的计算与评估； 4、编程实现贝叶斯分类算法，并对简洁应用样本数据实现预料分类 三、试验方法 1、 实现贝叶斯算法 2、 利用试验数据对贝叶斯算法进行检测 3、 求解精确度计算 4、 调试程序 5、 完成整个分类与评估的过程 四、试验步骤 4.1 算法过程描述： 1）输入训练数据，将数据保存在DataBase 二维数组中(数组的最终一个属性对应类别标号) 2）设定训练数据集与测试数据集大小(指定从数组下标0起先到TrainSetSize-1所对应的数据为训练数据，其余为测试数据) ； 3）计算训练数据集数据中各属性在各类中的概率分布状况； 4）利用测试数据计算贝叶斯算法的分类精度；

23、5）输出分类结果； 4.2 数据处理 B、对数据中的枚举类型数据进行转换以便于数据处理： 4.3 计算训练数据集数据中各属性在各类中的概率分布状况如图3-1所示 4.4 利用测试数据计算贝叶斯算法的分类精度如图3-2所示 图3-1 训练数据集各属性的概率分布计算 图3-2 贝叶斯算法的分类精度计算 4.5 输出分类结果 For (i=0;i For (j=0;j printf(“nnTotal Correct is%d”,TotalCorrect); 五、留意事项 留意单个样例数据的概率计算与各字段的概率计算的关系 试验五 Apriori算法实现 一、试验目的 1、驾驭Apriori 算法对于

24、关联规则挖掘中频繁集的产生以及关联规则集合的产生过程； 2、依据算法描述编程实现算法，调试运行。并结合相关试验数据进行应用，得到分析结果。 数据和删除数据的操作。 试验类型：验证 安排课间：2学时 二、试验内容 1、频繁项集的生成与Apriori 算法实现； 2、关联规则的生成过程与Rule-generate 算法实现； 3、结合样例对算法进行分析； 三、试验步骤 编写程序完成下列算法： 1、Apriori 算法 输入： 数据集D ；最小支持数minsup_count； 输出： 频繁项目集L L1=large 1-itemsets For (k=2; Lk-1; k+) Ck=apriori-

25、gen (Lk-1); / Ck是k 个元素的候选集 For all transactions tD do begin Ct=subset(Ck,t); /Ct是全部t 包含的候选集元素 for all candidates c Ct do c.count+; end Lk=c Ck| c.count minsup_count End L=Lk; 2、apriori-gen (Lk-1) 候选集产生算法 输入： (k-1)-频繁项目集Lk-1 输出： k-频繁项目集Ck For all itemset pLk-1 do For all itemset qLk-1 do If p.item1=q

26、.item1, p.item2=q.item2, ,p.itemk-2=q.itemk-2, p.itemk-1 if has_infrequent_subset(c, Lk-1) then delete c else add c to Ck End Return Ck 3、has_infrequent_subset(c, Lk-1) 功能：推断候选集的元素 输入： 一个k-频繁项目集Lk-1 ，(k-1)-频繁项目集Lk-1 输出：c 是否从候选集中删除的布尔推断 For all (k-1)-subsets of c do If Not(SLk-1) THEN return TRUE; Re

27、turn FALSE; 4、Rule-generate(L,minconf) 输入：频繁项目集；最小信任度 输出：强关联规则 算法： FOR each frequent itemset lk in L generules(lk,lk); 5、Genrules 递归算法： Genrules(lk:frequent k-itemset, xm:frequent m-itemset) X=(m-1)-itemsets xm-1 | xm-1 in xm; For each xm-1 in X BEGIN conf=support(lk)/support(xm-1); IF (confminconf) THEN 长沙学院信息与计算科学系 数据挖掘试验指导书 BEGIN 输出规则:xm-1->(lk-xm-1),support,confidence; IF (m-1)>1) THEN genrules(lk,xm-1); END; END; 结合相关样例数据对算法进行调试，并依据相关试验结果对数据进行分析， 四、试验报告要求 1、用C 语言实现上述相关算法。 2、试验操作步骤和试验结果，试验中出现的问题和解决方法。 五、留意事项 1、集合的表示及相关操作的实现； 2、项目集的数据结构描述； 第21页