葉志偉數(shù)據(jù)挖掘實驗指導書(算法編程部分)葉志偉數(shù)據(jù)挖掘實驗指導書(算法編程部分)葉志偉數(shù)據(jù)挖掘實驗指導書(算法編程部分)葉志偉數(shù)據(jù)挖掘實驗指導書(算法編程部分)編制僅供參考審核批準生效日期地址：電話：傳真:郵編:《數(shù)據(jù)挖掘與數(shù)據(jù)倉庫》實驗指導書2013年計算機學院計算應用實驗1Apriori算法實現(xiàn)一、實驗目的1、掌握Apriori算法對于關聯(lián)規(guī)則挖掘中頻繁集的產生以及關聯(lián)規(guī)則集合的產生過程；2、根據(jù)算法描述編程實現(xiàn)算法，調試運行。并結合相關實驗數(shù)據(jù)進行應用，得到分析結果。數(shù)據(jù)和刪除數(shù)據(jù)的操作。實驗類型：綜合計劃課間：2學時二、實驗內容1、頻繁項集的生成與Apriori算法實現(xiàn)；2、關聯(lián)規(guī)則的生成過程與Rule-generate算法實現(xiàn)；3、結合樣例對算法進行分析；三、實驗步驟編寫程序完成下列算法：1、Apriori算法輸入：數(shù)據(jù)集D；最小支持數(shù)minsup_count；輸出：頻繁項目集LL1={large1-itemsets}For(k=2;Lk-1≠Φ;k++)Ck=apriori-gen(Lk-1);-1in-1in參考實驗數(shù)據(jù)1、 實現(xiàn)貝葉斯算法2、 利用實驗數(shù)據(jù)對貝葉斯算法進行檢測3、 求解精確度計算4、 調試程序5、 完成整個分類與評估的過程四、實驗步驟算法過程描述：1）輸入訓練數(shù)據(jù)，將數(shù)據(jù)保存在DataBase二維數(shù)組中(數(shù)組的最后一個屬性對應類別標號)2）設定訓練數(shù)據(jù)集與測試數(shù)據(jù)集大小(指定從數(shù)組下標0開始到TrainSetSize-1所對應的數(shù)據(jù)為訓練數(shù)據(jù)，其余為測試數(shù)據(jù))；3）計算訓練數(shù)據(jù)集數(shù)據(jù)中各屬性在各類中的概率分布情況；4）利用測試數(shù)據(jù)計算貝葉斯算法的分類精度；5）輸出分類結果；數(shù)據(jù)處理A、實驗數(shù)據(jù)RIDageincomestudentCredit_ratingBuyComputer1≦30HighNoFairNo2≦30HighNoExcellentNo331~40HighNoFairYes4>40medNoFairYes5>40LowYesFairYes6>40LowYesExcellentNo731~40LowYesExcellentYes8≦30MedNoFairNo9≦30LowYesFairYes10>40MedYesFairYes11≦30MedYesExcellentYes1231~40MedNoExcellentYes1331~40HighYesFairYes14>40medNoExcellentNoB、對數(shù)據(jù)中的枚舉類型數(shù)據(jù)進行轉換以便于數(shù)據(jù)處理：0123ClassNo10000020001031000142100152210162211071211180100090210110211011101111121101113101011421010計算訓練數(shù)據(jù)集數(shù)據(jù)中各屬性在各類中的概率分布情況如圖3-1所示利用測試數(shù)據(jù)計算貝葉斯算法的分類精度如圖3-2所示NoNoNoYesYes申請AttSetSize*MaxAttSize*ClassSize大小的空間AttributeDistributei=0i<AttSetSizej<TrainSetSizeAttributeDistribute[i][DataBase[j][i]][DataBase[j][AttSetSize-1]]++AttributeDistribute0For(i=0;i<AttSize;i++)For(j=0;j<MaxAttSize;j++)For(k=0;k<ClassSize;k++)AttributeDistribute[i][j][k]=0;j=0i++Noi==AttSetSize-1YesAttributeDistribute[i][0][DataBase[j][AttSetSize-1]]++j++圖3-1訓練數(shù)據(jù)集各屬性的概率分布計算

申請ClassSize*ClassSize個空間申請ClassSize*ClassSize個空間Precisei<SetSizePresize0;AttrClassDis0For(i=0;i<ClassSize;i++)For(j=0;j<ClassSize;j++)Presize[i][j]=0;i=TrainSetSize;i++j=0MaxP=0;ClassNo=0;Temp計算屬于類j的概率For(k=0;k<AttSetSize-1)Temp*=AttributeDistribute[k][DataBase[i][k]][j]/AttributeDistribute[AttSetSize-1][0][j]Temp*=AttributeDistribute[AttSetSize-1][0][j]/TrainSetj<ClassSizeTemp>MaxPMaxP=Temp;ClassNo=jj++Precise[DataBase[i][AttrSetSize-1]][ClassNo]++圖3-2貝葉斯算法的分類精度計算輸出分類結果For(i=0;i<ClassSize;i++){printf(“\n”);For(j=0;j<ClassSize;j++)printf(“\t%d”,Precise[i][j]);TotalCorrect+=Precise[i][i];}printf(“\n\nTotalCorrectis%d”,TotalCorrect);五、注意事項注意單個樣例數(shù)據(jù)的概率計算與各字段的概率計算的關系參考代碼(對參考數(shù)據(jù)的代碼)#include<string>#include<vector>#include<set>#include<ctime>#include<algorithm>#include<cmath>#include<map>usingnamespacestd;1==1) { count1++; } if(trainData[i].A1==2) { count2++; } if(trainData[i].A1==3) { count3++; }1==1)2+j); pipei=C1_map[j].find(temp); if(pipei==C1_map[j].end()) { C1_map[j].insert(map<double,double>::value_type(temp,1)); } else { doublej=pipei->second; pipei->second=j+1; } } } if(trainData[i].A1==2)2+j); pipei=C2_map[j].find(temp); if(pipei==C2_map[j].end()) { C2_map[j].insert(map<double,double>::value_type(temp,1)); } else { doublej=pipei->second; pipei->second=j+1; } } } if(trainData[i].A1==3)2+j); pipei=C3_map[j].find(temp); if(pipei==C3_map[j].end()) { C3_map[j].insert(map<double,double>::value_type(temp,1)); } else { doublej=pipei->second; pipei->second=j+1; } } } } egin();pipei!=C1_map[i].end();++pipei) { doublenum=pipei->second; pipei->second=(double)num/(double)count1; } for(pipei=C2_map[i].begin();pipei!=C2_map[i].end();++pipei) { doublenum=pipei->second; pipei->second=(double)num/(double)count2; } for(pipei=C3_map[i].begin();pipei!=C3_map[i].end();++pipei) { doublenum=pipei->second; pipei->second=(double)num/(double)count3;} }}voidhouyan()ind(*(&testData[i].A2+k)); if(pipei!=C1_map[k].end()) { pXC[0]=pXC[0]+pipei->second; } } p[0]=A[0]*pXC[0]; ind(*(&testData[i].A2+k)); if(pipei!=C2_map[k].end()) { pXC[1]=pXC[1]+pipei->second; } } p[1]=A[1]*pXC[1]; ind(*(&testData[i].A2+k)); if(pipei!=C3_map[k].end()) { pXC[2]=pXC[2]+pipei->second; } } p[2]=A[2]*pXC[2]; } 1==1) m++; } else { if(p[1]>p[2]) { cout<<p[1]<<""<<2<<endl; if(testData[i].A1==2) m++; } else { cout<<p[2]<<""<<3<<endl; if(testData[i].A1==3) m++; } } }}voidmain(){ doubletp,fp; cout<<"概率最大值"<<"所屬類別"<<endl; DataRead(trainData,""); bayes(); DataRead(testData,""); houyan(); tp=(double)m/51; fp=1-tp; cout<<"正確率為："<<tp*100<<"%"<<endl;cout<<"錯誤率為："<<fp*100<<"%"<<endl;}實驗3-1一、實驗目的通過分析C-Means聚類算法的聚類原理，利用Vc編程工具(或者其他編程工具)實現(xiàn)C-Means和FCM聚類算法，并通過對樣本數(shù)據(jù)的聚類過程，加深對該聚類算法的理解與應用過程。實驗類型：綜合計劃課間：6學時二、實驗內容1、分析C-Means聚類算法和FCM；2、分析距離計算方法；3、分析聚類的評價準則；4、編程完成C-Means聚類算法和FCM，并基于相關實驗數(shù)據(jù)實現(xiàn)聚類過程；三、實驗方法1、C-means聚類算法原理C-means聚類算法以C為參數(shù)，把n個對象分為C個簇，以使簇內的具有較高的相似度。相似度的計算根據(jù)一個簇中對象的平均值來進行。算法描述：輸入：簇的數(shù)目C和包含n個對象的數(shù)據(jù)庫輸出：使平方誤差準則最小的C個簇過程：任選C個對象作為初始的簇中心；Repeatforj=1tonDO根據(jù)簇中對象的平均值，將每個對象賦給最類似的簇fori=1toCDO更新簇的平均值計算EUnitlE不再發(fā)生變化按簇輸出相應的對象2、聚類評價準則：E的計算為：四、實驗步驟實驗數(shù)據(jù)見實驗數(shù)據(jù)集Wine和Iris數(shù)據(jù)初始簇中心的選擇選擇k個樣本作為簇中心For(i=0;i<k;i++)For(j=0;j<AttSetSize;j++)ClusterCenter[i][j]=DataBase[i][j]數(shù)據(jù)對象的重新分配Sim=某一較大數(shù)；ClusterNo=-1;For(i=0;i<k;i++)If(Distance(DataBase[j],ClusterCenter[i])<Sim){Sim=Distance(DataBase[j],ClusterCenter[i]);ClusterNo=i;}ObjectCluster[j]=ClusterNo;簇的更新For(i=0;i<k;i++){Temp=0;Num=0;For(j=0;j<n;j++)If(ObjectCluster[j]==i){Num++;Temp+=DataBase[j];}If(ClusterCenter[i]!=Temp)HasChanged=TRUE;ClusterCenter[i]=Temp;}結果的輸出For(i=0;i<k;i++){Printf(“輸出第%d個簇的對象:”，i);For(j=0;j<n;j++)If(ObjectCluster[j]==i)printf(“%d”,j);Printf(“\n”);Printf(“\t\t\t簇平均值為(%d,%d)\n”,ClusterCenter[i][0],ClusterCenter[i][1]);}五、注意事項1、距離函數(shù)的選擇2、評價函數(shù)的計算算法描述模糊C均值聚類算法的步驟還是比較簡單的，模糊C均值聚類（FCM），即眾所周知的模糊ISODATA，是用隸屬度確定每個數(shù)據(jù)點屬于某個聚類的程度的一種聚類算法。1973年，Bezdek提出了該算法，作為早期硬C均值聚類（HCM）方法的一種改進。FCM把n個向量xi（i=1,2,…,n）分為c個模糊組，并求每組的聚類中心，使得非相似性指標的價值函數(shù)達到最小。FCM與HCM的主要區(qū)別在于FCM用模糊劃分，使得每個給定數(shù)據(jù)點用值在0，1間的隸屬度來確定其屬于各個組的程度。與引入模糊劃分相適應，隸屬矩陣U允許有取值在0，1間的元素。不過，加上歸一化規(guī)定，一個數(shù)據(jù)集的隸屬度的和總等于1：那么，F(xiàn)CM的價值函數(shù)（或目標函數(shù)）就是式（）的一般化形式：，這里uij介于0，1間；ci為模糊組I的聚類中心，dij=||ci-xj||為第I個聚類中心與第j個數(shù)據(jù)點間的歐幾里德距離；且是一個加權指數(shù)。 構造如下新的目標函數(shù)，可求得使（）式達到最小值的必要條件：這里j，j=1到n，是（）式的n個約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮?，使式（）達到最小的必要條件為：和由上述兩個必要條件，模糊C均值聚類算法是一個簡單的迭代過程。在批處理方式運行時，F(xiàn)CM用下列步驟確定聚類中心ci和隸屬矩陣U[1]：步驟1：用值在0，1間的隨機數(shù)初始化隸屬矩陣U，使其滿足式（）中的約束條件步驟2：用式（）計算c個聚類中心ci，i=1,…,c。步驟3：根據(jù)式（）計算價值函數(shù)。如果它小于某個確定的閥值，或它相對上次價值函數(shù)值的改變量小于某個閥值，則算法停止。步驟4：用（）計算新的U矩陣。返回步驟2。上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。由于不能確保FCM收斂于一個最優(yōu)解。算法的性能依賴于初始聚類中心。