叶志伟数据挖掘实验指导书(算法编程部分)

《叶志伟数据挖掘实验指导书(算法编程部分)》由会员分享，可在线阅读，更多相关《叶志伟数据挖掘实验指导书(算法编程部分)（40页珍藏版）》请在装配图网上搜索。

1、数据挖掘与数据仓库实验指导书2013年 计算机学院计算应用实验1 Apriori算法实现一、实验目的1、掌握Apriori算法对于关联规则挖掘中频繁集的产生以及关联规则集合的产生过程；2、根据算法描述编程实现算法，调试运行。并结合相关实验数据进行应用，得到分析结果。数据和删除数据的操作。实验类型：综合计划课间：2学时二、实验内容1、频繁项集的生成与Apriori算法实现；2、关联规则的生成过程与Rule-generate算法实现；3、结合样例对算法进行分析；三、实验步骤编写程序完成下列算法：1、Apriori算法输入： 数据集D；最小支持数minsup_count；输出： 频繁项目集LL1=l

2、arge 1-itemsetsFor (k=2; Lk-1; k+)Ck=apriori-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+; endLk=c Ck| c.count minsup_count EndL=Lk;2、apriori-gen (Lk-1) 候选集产生算法输入： (k-1)-频繁项目集Lk-1输出： k-频繁项目集CkFor all itemset pLk-1 doFo

3、r all itemset qLk-1 doIf p.item1=q.item1, p.item2=q.item2, ,p.itemk-2=q.itemk-2, p.itemk-1(lk-xm-1),support,confidence; IF (m-1)1) THEN genrules(lk,xm-1); END;END;结合相关样例数据对算法进行调试，并根据相关实验结果对数据进行分析，四、实验报告要求1、用C语言或者其他语言实现上述相关算法。2、实验操作步骤和实验结果，实验中出现的问题和解决方法。五、注意事项1、集合的表示及相关操作的实现；2、项目集的数据结构描述；参考核心代码如下：（相关

4、的测试main函数可以自己书写。根据频繁k项集生成关联规则相对简单，只需要计算最小置信度即可从频繁K项集中找到所有的满足条件的关联规则。）/对事物进行第一次扫描，生成频繁一项集，并返回一项集中个数int init_pass(char *item,char tranlen_tlen,int len,char res_itemlen_tlen,float min_sup)float t_sup;int number=0;for(int i=0;ilen;i+)int count=0;for(int j=0;jlen_t;j+)for(int k=0;k=min_sup)res_itemnumber

5、+0=itemi;return number-1;/生成候选K项集，返回k项集中事物的个数int candidate_gen(char ktranlenk,char kktranlenk+1)char tempk,temp1k,ktempk+1;int number=0;for(int i=0;ilen;i+)strcpy(temp,ktrani);bool flag;for(j=i+1;jlen;j+)strcpy(temp1,ktrani);for(int m=0;mk;m+)if(mtemp1k-1)strcpy(ktemp,temp1);ktempk=tempk-1;elsestrcp

6、y(ktemp,temp);ktempk=temp1k-1break;flag=judge(kemp,ktranlenk);if(flag=true)strcpy(kktrannumber+,ktemp);return number-1;/判断子集是否在k项集中bool judge(char *srcstr,char desstrlenk)char tempk;int count=0;for(int i=0;ik-1;i+)for(int j=0;ji;j+)tempj=srcstrj;for(int j=i+1;jk+1;j+)tempj=srcstrj;for(int p=0;plen;p

7、+)if(strcmp(temp,desstri)=0)count+;break;if(count=k-1)return true;return false;/apriori算法int apriori(char itemlen,char tranlengthlen,char res_tranlengthlen,float min_sup)char ttranlengthlen;int number,count,t_num;for(int i=0;ilength;i+)for(int j=0;jlen;j+)ttranij=0;number=init_pass(item,tranlengthle

8、n,len,ttranlengthlen,min_sup);for(int i=0ilength;i+)res_trani0=ttrani0;for(int k=2;number!=0;k+)t_num=number;number=candidate_gen(res_itemnumberk-1,ttrannumberk);if(k=2)continue;elsecount=0;for(int i=0;inumber;i+)char tempk;strcpy(temp,ttrani);bool t_flag=false;for(int j=0;jlength;j+)/求出候选K项集中每个事物的支

9、持计数int t_k=0;for(int n=0;nk;n+)bool m_flag=falsefor(int g=t_k;g min_sup)strcpy(res_itemi,temp);count=0;return t_num; 实验2-1 ID3算法实现一、实验目的通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。加深对相关算法的理解过程。实验类型：综合计划课间：4学时二、实验内容1、分析决策树算法的实现流程；2、分析信息增益的计算、数据子集划分、决策树的构建过程；3、根据算法描述编程实现算法，调试运行； 三、实验方法算法描述： 以代表训练样本的单个结点开始建树；若

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

11、 / 同层其他节点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.2、Build_ID3

12、(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=0) Temp_Num_Attrib+; If Temp_Num_Attrib=0 N-ClassNo=最多的类； N-IsLeaf=TRUE; N-Left_Node=NULL;N-Right_Node=NULL; Return N;If Class_Distribute

13、中仅一类的分布大于0 N-ClassNo=该类； N-IsLeaf=TRUE; N-Left_Node=NULL;N-Right_Node=NULL; Return N; InforGain=0;CurrentCol=-1;For i=0;iNum_Attrib-1;i+) TempGain=Compute_InforGain(Data,Record_No,I,Num_Attrib); If (InforGainAttrib_Col=CurrentCol;/记录CurrentCol所对应的不同值放入DiferentValue；I=0;Value_No=-1;While iRecord_No F

14、lag=false; For (k=0;kValue_No;k+) if (DiferentValuk=DataiCurrentCol) flag=true; if (flag=false)Value_No+;DiferentValueValue_No=DataiCurrentCol I+;SubData=以Data大小申请内存空间；For (i=0;iValue_No;i+) k=-1; for (j=0;jRecord_No-1;j+) if (DatajCurrentCol=DiferentValui) k=k+;For(int i1=0;i1Num_Attrib;i1+)If (i1C

15、urrentCol)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、计算信息增益 Compute_InforGain(Data,Record_No, Col_No, Num_Attrib) Int DifferentVal

16、ueMaxDifferentValue; Int Total_DifferentValue; Int sClassNoMaxDifferentValue; s=0;/ 数组清0; Total_DifferentValue=-1; For (i=0;iRecord_No;i+) J=GetPosition(DifferentValue,Total_DifferentValue,DataiCol_no);If (j0) Total_DifferentValue+;DifferentValueTotal_DifferentValue=DataiCol_no;J=Total_DifferentValu

17、e;SDataiNum_Attrib-1j+;Total_I=0;For (i=0;iClassNo;i+) Sum=0; For(j=0;jRecord_No;j+) if DatajNum_Attrib-1=i sum+; Total_I=Compute_PI(Sum/Record_No); EA=0;For (i=0;iTotal_DifferentValue;i+); temp=0;sj=0; /sj是数据子集中属于类j的样本个数； For (j=0;jClassNO;j+) sj+=sji; For (j=0;jClassNO;j+) EA+=sj/Record_No*Compute

18、_PI(sji/sj); Return total_I-EA;3.4、得到某数字在数组中的位置GetPosition(Data, DataSize,Value) For (i=0;iDataSize;i+) if (Datai=value) return I; Return -1;3.5、计算Pi*LogPiFloat Compute_PI(float pi) If pi=1 then return 0; Return 0-pi*log2(pi);五、实验报告要求1、用C语言或者其他语言实现上述相关算法。2、实验操作步骤和实验结果，实验中出现的问题和解决方法。六、注意事项1、信息增益的计算；2

19、、选择相关字段后根据相关字段的取值对数据集合进行划分。3、决策树构建的终止条件实验2-2 贝叶斯算法实现一、实验目的通过对贝叶斯算法的编程实现，加深对贝叶斯算法的理解，同时利用贝叶斯算法对简单应用实现预测分类实验类型：综合计划课间：2学时二、实验内容1、分析贝叶斯算法；2、计算条件概率；3、预测精度的计算与评估；4、编程实现贝叶斯分类算法，并对简单应用样本数据实现预测分类5. 参考实验数据http:/archive.ics.uci.edu/ml/machine-learning-databases/wine/三、实验方法1、实现贝叶斯算法2、利用实验数据对贝叶斯算法进行检测3、求解精确度计算4

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

21、ighNoFairYes440medNoFairYes540LowYesFairYes640LowYesExcellentNo73140LowYesExcellentYes830MedNoFairNo930LowYesFairYes1040MedYesFairYes1130MedYesExcellentYes123140MedNoExcellentYes133140HighYesFairYes1440medNoExcellentNo B、对数据中的枚举类型数据进行转换以便于数据处理：0123ClassNo100000200010310001421001522101622110712111801

22、000902101102110111011111211011131010114210104.3 计算训练数据集数据中各属性在各类中的概率分布情况如图3-1所示4.4 利用测试数据计算贝叶斯算法的分类精度如图3-2所示NoNoYesYes申请AttSetSize*MaxAttSize*ClassSize大小的空间AttributeDistributei=0iAttSetSizejTrainSetSizeAttributeDistributeiDataBasejiDataBasejAttSetSize-1+AttributeDistribute0For (i=0;iAttSize;i+) For

23、(j=0;jMaxAttSize;j+) For(k=0;kClassSize;k+) AttributeDistributeijk=0;j=0i+Noi=AttSetSize-1YesAttributeDistributei0DataBasejAttSetSize-1+j+ 图3-1 训练数据集各属性的概率分布计算申请ClassSize*ClassSize个空间PreciseiSetSizePresize0 ; AttrClassDis0For (i=0;iClassSize;i+) For (j=0;jClassSize;j+) Presizeij=0;i=TrainSetSize;i+j

24、=0MaxP=0;ClassNo=0;Temp计算属于类j的概率For (k=0;kAttSetSize-1)Temp*=AttributeDistributekDataBaseikj/AttributeDistributeAttSetSize-10jTemp*=AttributeDistributeAttSetSize-10j/TrainSetjMaxPMaxP=Temp;ClassNo=jj+PreciseDataBaseiAttrSetSize-1ClassNo+图3-2 贝叶斯算法的分类精度计算4.5 输出分类结果For (i=0;iClassSize;i+) printf(“n”);

25、 For (j=0;jClassSize;j+) printf(“t%d”, Preciseij); TotalCorrect+=Preciseii; printf(“nnTotal Correct is%d”,TotalCorrect);五、注意事项注意单个样例数据的概率计算与各字段的概率计算的关系参考代码 (对参考数据的代码)BayesianClassifier.h#include #include #include #include #include #include #include using namespace std;/ 1) Alcohol/ 2) Malic acid/ 3)

26、 Ash/ 4) Alcalinity of ash / 5) Magnesium/ 6) Total phenols/ 7) Flavanoids/ 8) Nonflavanoid phenols/ 9) Proanthocyanins/ 10)Color intensity/ 11)Hue/ 12)OD280/OD315 of diluted wines/ 13)Proline int TrainNum = 130;/所有训练数据的范围int TestNum = 48;struct OriginalDatadouble A1;double A2;double A3;double A4; d

27、ouble A5; double A6;double A7;double A8;double A9;double A10;double A11;double A12;double A13;double A14;BayesianClassifier.cpp#include #include #include #include BayesianClassifier.husing namespace std;const int Shuxing=13;/属性总数ifstream f;vector trainData; /存放训练数据vector testData; /存放测试数据double A3;

28、/先验概率int m;/存放每一类型，每种属性中某数值的概率map C1_mapShuxing; map C2_mapShuxing;map C3_mapShuxing;/从文件中读取数值void DataRead(vector &data, const char* fileName)f.open(fileName);int ZHjiang;if (fileName0 = w)ZHjiang = TrainNum;else ZHjiang = TestNum;string line;OriginalData wine;for (int i = 0; i line;while (line.fin

29、d(,) 0 & line.find(,) wine.A1 wine.A2 wine.A3 wine.A4 wine.A5 wine.A6 wine.A7 wine.A8 wine.A9 wine.A10 wine.A11 wine.A12 wine.A13 wine.A14;data.push_back(wine);f.close();void bayes()int count1 = 0, count2 = 0, count3 = 0;int i;for(i = 0; i TrainNum ; i+)if(trainDatai.A1 = 1)count1 +;if(trainDatai.A1

30、 = 2)count2 +;if(trainDatai.A1 = 3)count3 +;/统计三类数据,各自求和A0 = (double)count1/(double)TrainNum; /求先验概率A1 = (double)count2/(double)TrainNum;A2 = (double)count3/(double)TrainNum;map:iterator pipei; for(i = 0 ; i TrainNum; i+) if(trainDatai.A1 = 1) /求P(Xk|C1) 中Xk的个数int j=0;for(;j 13 ;j+)double temp = *(&

31、trainDatai.A2+j);pipei = C1_mapj.find(temp);if(pipei = C1_mapj.end()C1_mapj.insert(map:value_type(temp,1);elsedouble j = pipei-second;pipei-second = j + 1;if(trainDatai.A1 = 2) /求P(Xk|C2) 中Xk的个数int j = 0;for(;j 13 ;j+)double temp = *(&trainDatai.A2+j);pipei = C2_mapj.find(temp);if(pipei = C2_mapj.en

32、d()C2_mapj.insert(map:value_type(temp,1);elsedouble j = pipei-second;pipei-second = j + 1;if(trainDatai.A1 = 3) /求P(Xk|C3) 中Xk的个数int j = 0;for(;j 13 ;j+)double temp = *(&trainDatai.A2+j);pipei = C3_mapj.find(temp);if(pipei = C3_mapj.end()C3_mapj.insert(map:value_type(temp,1);elsedouble j = pipei-sec

33、ond;pipei-second = j + 1;/概率for(i = 0; i second; pipei-second = (double)num/(double)count1;for(pipei=C2_mapi.begin(); pipei!=C2_mapi.end(); +pipei) double num = pipei-second; pipei-second = (double)num/(double)count2;for(pipei=C3_mapi.begin(); pipei!=C3_mapi.end(); +pipei) double num = pipei-second;

34、 pipei-second = (double)num/(double)count3; void houyan()/计算后验分布,找出最大值int i,j,k;double p3;for(i = 0; iTestNum; i+)double pXC3=0,0,0;for(j = 0; j 3; j+)map:iterator pipei;/计算p(X|C1)for(k = 0; k second;p0 = A0 * pXC0;/计算p(X|C2)for(k = 0; k second;p1 = A1*pXC1;/计算p(X|C3)for(k = 0; k second;p2 = A2*pXC2

35、;/找出最大值if(p0 p1 & p0 p2)coutp0 1 p2)coutp1 2endl;if(testDatai.A1=2) m+;elsecoutp2 3endl;if(testDatai.A1=3) m+;void main()double tp,fp;cout概率最大值 所属类别endl;DataRead(trainData,wine.data);bayes();DataRead(testData,test.data);houyan();tp=(double)m/51;fp=1-tp;cout正确率为：tp*100%endl; cout错误率为：fp*100%endl;实验3-

36、1 C-Means聚类算法实现一、实验目的通过分析C-Means聚类算法的聚类原理，利用Vc编程工具(或者其他编程工具)实现C-Means和FCM聚类算法，并通过对样本数据的聚类过程，加深对该聚类算法的理解与应用过程。实验类型：综合计划课间：6学时二、实验内容1、分析C-Means聚类算法和FCM；2、分析距离计算方法；3、分析聚类的评价准则；4、编程完成C-Means聚类算法和FCM，并基于相关实验数据实现聚类过程；三、实验方法1、C-means聚类算法原理 C-means聚类算法以C为参数，把n个对象分为C个簇，以使簇内的具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行。 算法

37、描述： 输入：簇的数目C和包含n个对象的数据库输出：使平方误差准则最小的C个簇过程：任选C个对象作为初始的簇中心；Repeat for j=1 to n DO 根据簇中对象的平均值，将每个对象赋给最类似的簇 for i=1 to C DO 更新簇的平均值 计算EUnitl E不再发生变化按簇输出相应的对象2、聚类评价准则：E的计算为：四、实验步骤4.1 实验数据见实验数据集Wine 和Iris数据4.2初始簇中心的选择选择k个样本作为簇中心 For (i=0;ik;i+) For (j=0;jAttSetSize;j+)ClusterCenterij=DataBaseij4.3 数据对象的重新

38、分配 Sim=某一较大数；ClusterNo=-1; For (i=0;ik;i+) If (Distance(DataBasej,ClusterCenteri)Sim) Sim=Distance(DataBasej,ClusterCenteri);ClusterNo=i;ObjectClusterj=ClusterNo;4.4 簇的更新 For (i=0;ik;i+)Temp=0;Num=0; For (j=0;jn;j+)If (ObjectClusterj=i)Num+; Temp+=DataBasej;If (ClusterCenteri!=Temp) HasChanged=TRUE;

39、ClusterCenteri=Temp;4.5 结果的输出 For (i=0;ik;i+) Printf(“输出第%d个簇的对象:”，i);For (j=0;jn;j+) If (ObjectClusterj=i) printf(“%d ”,j);Printf(“n”);Printf(“ttt 簇平均值为(%d,%d)n”, ClusterCenteri0, ClusterCenteri1);五、注意事项1、距离函数的选择2、评价函数的计算算法描述模糊C均值聚类算法的步骤还是比较简单的，模糊C均值聚类（FCM），即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚

40、类算法。1973年，Bezdek提出了该算法，作为早期硬C均值聚类（HCM）方法的一种改进。FCM把n个向量xi（i=1,2,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1： (6.9)那么，FCM的价值函数（或目标函数）就是式（6.2）的一般化形式：， (6.10)这里uij介于0，1间；ci为模糊组I的聚类中心，dij=|ci-xj|为第I

41、个聚类中心与第j个数据点间的欧几里德距离；且是一个加权指数。构造如下新的目标函数，可求得使（6.10）式达到最小值的必要条件： (6.11)这里lj，j=1到n，是（6.9）式的n个约束式的拉格朗日乘子。对所有输入参量求导，使式（6.10）达到最小的必要条件为： (6.12)和 (6.13)由上述两个必要条件，模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCM用下列步骤确定聚类中心ci和隶属矩阵U1：步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（6.9）中的约束条件步骤2：用式（6.12）计算c个聚类中心ci，i=1,c。步骤3：根据式（6.10）计算价值函数。如

42、果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。步骤4：用（6.13）计算新的U矩阵。返回步骤2。上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。模糊c均值聚类算法如下：Reapeat for l=1 2 3.Step 1:compute the cluseter prototypes(means):Step 2:compete the distance:Step 3:Update the

43、partition matrix:算法实现采用VC+进行编写文档的读取#include data.h/函数定义double *DataRead(char*name,int row,int col)double *p=new double* row;ifstream infile;infile.open(name,ios:in);for(int i=0;irow;i+)pi=new doublecol;for(int j=0;jpij;infile.close();cout成功读取数据文件:name!n;return p;/释放内存for(i=0;irow;i+)deletepi;deletep;文档的保存#include