葉志偉數(shù)據(jù)挖掘?qū)嶒炛笇?算法編程部分)

1、數(shù)據(jù)挖掘與數(shù)據(jù)倉庫實驗指導書2013年 計算機學院計算應用實驗1 Apriori算法實現(xiàn)一、實驗目的1、掌握Apriori算法對于關聯(lián)規(guī)則挖掘中頻繁集的產(chǎn)生以及關聯(lián)規(guī)則集合的產(chǎn)生過程；2、根據(jù)算法描述編程實現(xiàn)算法，調(diào)試運行。并結合相關實驗數(shù)據(jù)進行應用，得到分析結果。數(shù)據(jù)和刪除數(shù)據(jù)的操作。實驗類型：綜合計劃課間：2學時二、實驗內(nèi)容1、頻繁項集的生成與Apriori算法實現(xiàn)；2、關聯(lián)規(guī)則的生成過程與Rule-generate算法實現(xiàn)；3、結合樣例對算法進行分析；三、實驗步驟編寫程序完成下列算法：1、Apriori算法輸入： 數(shù)據(jù)集D；最小支持數(shù)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) 候選集產(chǎn)生算法輸入： (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<q.itemk-1 thenbegin c=pq if has_infrequent_subset(c, Lk-1) then delete c else add c to CkEndReturn Ck3、has_infrequent_subset(c, Lk-1)功能：判斷候選集的元素輸入： 一個k-頻繁項目集Lk-1 ，(k-1)-頻繁項目集Lk-1輸出：c是否從候選集中刪除的布爾判斷For all (k

4、-1)-subsets of c doIf Not(SLk-1) THEN return TRUE;Return FALSE;4、Rule-generate(L,minconf)輸入：頻繁項目集；最小信任度輸出：強關聯(lián)規(guī)則算法：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 XBEGIN conf=su

5、pport(lk)/support(xm-1); IF (confminconf) THEN BEGIN 輸出規(guī)則:xm-1->(lk-xm-1),support,confidence; IF (m-1)>1) THEN genrules(lk,xm-1); END;END;結合相關樣例數(shù)據(jù)對算法進行調(diào)試，并根據(jù)相關實驗結果對數(shù)據(jù)進行分析，四、實驗報告要求1、用C語言或者其他語言實現(xiàn)上述相關算法。2、實驗操作步驟和實驗結果，實驗中出現(xiàn)的問題和解決方法。五、注意事項1、集合的表示及相關操作的實現(xiàn)；2、項目集的數(shù)據(jù)結構描述；參考核心代碼如下：（相關的測試main函數(shù)可以自己書寫。根據(jù)頻

6、繁k項集生成關聯(lián)規(guī)則相對簡單，只需要計算最小置信度即可從頻繁K項集中找到所有的滿足條件的關聯(lián)規(guī)則。）/對事物進行第一次掃描，生成頻繁一項集，并返回一項集中個數(shù)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;i<len;i+)int count=0;for(int j=0;j<len_t;j+)for(int k=0;k<len;k+)if(itemi=tranjk)count+;

7、break;break;t_sup=count*1.0/len;if(t_sup>=min_sup)res_itemnumber+0=itemi;return number-1;/生成候選K項集，返回k項集中事物的個數(shù)int candidate_gen(char ktranlenk,char kktranlenk+1)char tempk,temp1k,ktempk+1;int number=0;for(int i=0;i<len;i+)strcpy(temp,ktrani);bool flag;for(j=i+1;j<len;j+)strcpy(temp1,ktrani);

8、for(int m=0;m<k;m+)if(m<k-1 && tempm=temp1m)|m=k-1)continue;flag=true;else flag=false;break;if(flag)if(tempk-1>temp1k-1)strcpy(ktemp,temp1);ktempk=tempk-1;elsestrcpy(ktemp,temp);ktempk=temp1k-1break;flag=judge(kemp,ktranlenk);if(flag=true)strcpy(kktrannumber+,ktemp);return number-1;

9、/判斷子集是否在k項集中bool judge(char *srcstr,char desstrlenk)char tempk;int count=0;for(int i=0;i<k-1;i+)for(int j=0;j<i;j+)tempj=srcstrj;for(int j=i+1;j<k+1;j+)tempj=srcstrj;for(int p=0;p<len;p+)if(strcmp(temp,desstri)=0)count+;break;if(count=k-1)return true;return false;/apriori算法int apriori(ch

10、ar itemlen,char tranlengthlen,char res_tranlengthlen,float min_sup)char ttranlengthlen;int number,count,t_num;for(int i=0;i<length;i+)for(int j=0;j<len;j+)ttranij='0'number=init_pass(item,tranlengthlen,len,ttranlengthlen,min_sup);for(int i=0i<length;i+)res_trani0=ttrani0;for(int k=2

11、;number!=0;k+)t_num=number;number=candidate_gen(res_itemnumberk-1,ttrannumberk);if(k=2)continue;elsecount=0;for(int i=0;i<number;i+)char tempk;strcpy(temp,ttrani);bool t_flag=false;for(int j=0;j<length;j+)/求出候選K項集中每個事物的支持計數(shù)int t_k=0;for(int n=0;n<k;n+)bool m_flag=falsefor(int g=t_k;g<len

12、;g+)if(tempk=tranjg)m_flag=true;t_k=g;break;if(m_flag=true && n=k-1)t_flag=true;if(t_flag=true)count+;flag = false;if(count/length > min_sup)strcpy(res_itemi,temp);count=0;return t_num; 實驗2-1 ID3算法實現(xiàn)一、實驗目的通過編程實現(xiàn)決策樹算法，信息增益的計算、數(shù)據(jù)子集劃分、決策樹的構建過程。加深對相關算法的理解過程。實驗類型：綜合計劃課間：4學時二、實驗內(nèi)容1、分析決策樹算法的實現(xiàn)流程

13、；2、分析信息增益的計算、數(shù)據(jù)子集劃分、決策樹的構建過程；3、根據(jù)算法描述編程實現(xiàn)算法，調(diào)試運行； 三、實驗方法算法描述： 以代表訓練樣本的單個結點開始建樹；若樣本都在同一個類，則該結點成為樹葉，并用該類標記；否則，算法使用信息增益作為啟發(fā)信息，選擇能夠最好地將樣本分類的屬性；對測試屬性的每個已知值，創(chuàng)建一個分支，并據(jù)此劃分樣本；算法使用同樣的過程，遞歸形成每個劃分上的樣本決策樹遞歸劃分步驟，當下列條件之一成立時停止：給定結點的所有樣本屬于同一類；沒有剩余屬性可以進一步劃分樣本，在此情況下，采用多數(shù)表決進行四、實驗步驟1、算法實現(xiàn)過程中需要使用的數(shù)據(jù)結構描述： Structint Attrib

14、_Col; / 當前節(jié)點對應屬性int Value; / 對應邊值Tree_Node* Left_Node; / 子樹Tree_Node* Right_Node / 同層其他節(jié)點Boolean IsLeaf; / 是否葉子節(jié)點int ClassNo; / 對應分類標號Tree_Node;2、整體算法流程 主程序： InputData(); T=Build_ID3(Data,Record_No, Num_Attrib); OutputRule(T); 釋放內(nèi)存;3、相關子函數(shù)：3.1、 InputData()輸入屬性集大小Num_Attrib;輸入樣本數(shù)Num_Record;分配內(nèi)存DataNu

15、m_RecordNum_Attrib;輸入樣本數(shù)據(jù)DataNum_RecordNum_Attrib；獲取類別數(shù)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<Num_Attrib;i+) If (Data0i>=0) Temp_Num_Attrib+; If

16、Temp_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;i<Num_Attrib-1;i+) TempGain=Comp

17、ute_InforGain(Data,Record_No,I,Num_Attrib); If (InforGain<TempGain) InforGain=TempGain; CurrentCol=I;N->Attrib_Col=CurrentCol;/記錄CurrentCol所對應的不同值放入DiferentValue；I=0;Value_No=-1;While i<Record_No Flag=false; For (k=0;k<Value_No;k+) if (DiferentValuk=DataiCurrentCol) flag=true; if (flag=f

18、alse)Value_No+;DiferentValueValue_No=DataiCurrentCol I+;SubData=以Data大小申請內(nèi)存空間；For (i=0;i<Value_No;i+) k=-1; for (j=0;j<Record_No-1;j+) if (DatajCurrentCol=DiferentValui) k=k+;For(int i1=0;i1<Num_Attrib;i1+)If (i1<>CurrentCol)SubDataki1=Dataji1; Else SubDataki1=-1; N->Attrib_Col=Cur

19、rentCol; 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 DifferentValueMaxDifferentValue; Int Total_DifferentVa

20、lue; Int sClassNoMaxDifferentValue; s=0;/ 數(shù)組清0; Total_DifferentValue=-1; For (i=0;i<Record_No;i+) J=GetPosition(DifferentValue,Total_DifferentValue,DataiCol_no);If (j<0) Total_DifferentValue+;DifferentValueTotal_DifferentValue=DataiCol_no;J=Total_DifferentValue;SDataiNum_Attrib-1j+;Total_I=0;F

21、or (i=0;i<ClassNo;i+) Sum=0; For(j=0;j<Record_No;j+) if DatajNum_Attrib-1=i sum+; Total_I=Compute_PI(Sum/Record_No); EA=0;For (i=0;i<Total_DifferentValue;i+); temp=0;sj=0; /sj是數(shù)據(jù)子集中屬于類j的樣本個數(shù)； For (j=0;j<ClassNO;j+) sj+=sji; For (j=0;j<ClassNO;j+) EA+=sj/Record_No*Compute_PI(sji/sj); R

22、eturn total_I-EA;3.4、得到某數(shù)字在數(shù)組中的位置GetPosition(Data, DataSize,Value) For (i=0;i<DataSize;i+) if (Datai=value) return I; Return -1;3.5、計算Pi*LogPiFloat Compute_PI(float pi) If pi<=0 then return 0; If pi>=1 then return 0; Return 0-pi*log2(pi);五、實驗報告要求1、用C語言或者其他語言實現(xiàn)上述相關算法。2、實驗操作步驟和實驗結果，實驗中出現(xiàn)的問題和解

23、決方法。六、注意事項1、信息增益的計算；2、選擇相關字段后根據(jù)相關字段的取值對數(shù)據(jù)集合進行劃分。3、決策樹構建的終止條件 數(shù)據(jù)挖掘?qū)嶒炛笇鴮嶒?-2 貝葉斯算法實現(xiàn)一、實驗目的通過對貝葉斯算法的編程實現(xiàn)，加深對貝葉斯算法的理解，同時利用貝葉斯算法對簡單應用實現(xiàn)預測分類實驗類型：綜合計劃課間：2學時二、實驗內(nèi)容1、分析貝葉斯算法；2、計算條件概率；3、預測精度的計算與評估；4、編程實現(xiàn)貝葉斯分類算法，并對簡單應用樣本數(shù)據(jù)實現(xiàn)預測分類5. 參考實驗數(shù)據(jù)/ml/machine-learning-databases/wine/三、實驗方法1、實現(xiàn)貝葉

24、斯算法2、利用實驗數(shù)據(jù)對貝葉斯算法進行檢測3、求解精確度計算4、調(diào)試程序5、完成整個分類與評估的過程四、實驗步驟4.1 算法過程描述：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）輸出分類結果；4.2 數(shù)據(jù)處理A、實驗數(shù)據(jù)RIDageincomestudentCredit_ratingBuyComputer130HighNoF

25、airNo230HighNoExcellentNo33140HighNoFairYes4>40medNoFairYes5>40LowYesFairYes6>40LowYesExcellentNo73140LowYesExcellentYes830MedNoFairNo930LowYesFairYes10>40MedYesFairYes1130MedYesExcellentYes123140MedNoExcellentYes133140HighYesFairYes14>40medNoExcellentNo B、對數(shù)據(jù)中的枚舉類型數(shù)據(jù)進行轉(zhuǎn)換以便于數(shù)據(jù)處理：0123C

26、lassNo100000200010310001421001522101622110712111801000902101102110111011111211011131010114210104.3 計算訓練數(shù)據(jù)集數(shù)據(jù)中各屬性在各類中的概率分布情況如圖3-1所示4.4 利用測試數(shù)據(jù)計算貝葉斯算法的分類精度如圖3-2所示NoNoYesYes申請AttSetSize*MaxAttSize*ClassSize大小的空間àAttributeDistributei=0i<AttSetSizej<TrainSetSizeAttributeDistributeiDataBasejiDat

27、aBasejAttSetSize-1+AttributeDistributeß0For (i=0;i<AttSize;i+) For (j=0;j<MaxAttSize;j+) For(k=0;k<ClassSize;k+) AttributeDistributeijk=0;j=0i+Noi=AttSetSize-1YesAttributeDistributei0DataBasejAttSetSize-1+j+ 圖3-1 訓練數(shù)據(jù)集各屬性的概率分布計算申請ClassSize*ClassSize個空間àPrecisei<SetSizePresize&#

28、223;0 ; AttrClassDisß0For (i=0;i<ClassSize;i+) For (j=0;j<ClassSize;j+) Presizeij=0;i=TrainSetSize;i+j=0MaxP=0;ClassNo=0;Tempß計算屬于類j的概率For (k=0;k<AttSetSize-1)Temp*=AttributeDistributekDataBaseikj/AttributeDistributeAttSetSize-10jTemp*=AttributeDistributeAttSetSize-10j/TrainSetj&l

29、t;ClassSizeTemp>MaxPMaxP=Temp;ClassNo=jj+PreciseDataBaseiAttrSetSize-1ClassNo+圖3-2 貝葉斯算法的分類精度計算4.5 輸出分類結果For (i=0;i<ClassSize;i+) printf(“n”); For (j=0;j<ClassSize;j+) printf(“t%d”, Preciseij); TotalCorrect+=Preciseii; printf(“nnTotal Correct is%d”,TotalCorrect);五、注意事項注意單個樣例數(shù)據(jù)的概率計算與各字段的概率計算

30、的關系參考代碼 (對參考數(shù)據(jù)的代碼)BayesianClassifier.h#include <string>#include <vector>#include <set>#include <ctime> #include <algorithm>#include <cmath>#include <map>using namespace std;/ 1) Alcohol/ 2) Malic acid/ 3) Ash/ 4) Alcalinity of ash / 5) Magnesium/ 6) Total ph

31、enols/ 7) Flavanoids/ 8) Nonflavanoid phenols/ 9) Proanthocyanins/ 10)Color intensity/ 11)Hue/ 12)OD280/OD315 of diluted wines/ 13)Proline int TrainNum = 130;/所有訓練數(shù)據(jù)的范圍int TestNum = 48;struct OriginalDatadouble A1;double A2;double A3;double A4; double A5; double A6;double A7;double A8;double A9;doub

32、le A10;double A11;double A12;double A13;double A14;BayesianClassifier.cpp#include <iostream>#include <fstream>#include <sstream>#include "BayesianClassifier.h"using namespace std;const int Shuxing=13;/屬性總數(shù)ifstream f;vector<OriginalData> trainData; /存放訓練數(shù)據(jù)vector<O

33、riginalData> testData; /存放測試數(shù)據(jù)double A3; /先驗概率int m;/存放每一類型，每種屬性中某數(shù)值的概率map<double, double> C1_mapShuxing; map<double, double> C2_mapShuxing;map<double, double> C3_mapShuxing;/從文件中讀取數(shù)值void DataRead(vector<OriginalData> &data, const char* fileName)f.open(fileName);int ZH

34、jiang;if (fileName0 = 'w')ZHjiang = TrainNum;else ZHjiang = TestNum;string line;OriginalData wine;for (int i = 0; i < ZHjiang; i+)f >> line;while (line.find(',') > 0 && line.find(',') < line.length()lineline.find(',') = ' ' istringstream

35、 stream(line);stream >> 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

36、bayes()int count1 = 0, count2 = 0, count3 = 0;int i;for(i = 0; i < TrainNum ; i+)if(trainDatai.A1 = 1)count1 +;if(trainDatai.A1 = 2)count2 +;if(trainDatai.A1 = 3)count3 +;/統(tǒng)計三類數(shù)據(jù),各自求和A0 = (double)count1/(double)TrainNum; /求先驗概率A1 = (double)count2/(double)TrainNum;A2 = (double)count3/(double)Train

37、Num;map<double, double>:iterator pipei; for(i = 0 ; i < TrainNum; i+) if(trainDatai.A1 = 1) /求P(Xk|C1) 中Xk的個數(shù)int j=0;for(;j< 13 ;j+)double temp = *(&trainDatai.A2+j);pipei = C1_mapj.find(temp);if(pipei = C1_mapj.end()C1_mapj.insert(map<double, double>:value_type(temp,1);elsedou

38、ble j = pipei->second;pipei->second = j + 1;if(trainDatai.A1 = 2) /求P(Xk|C2) 中Xk的個數(shù)int j = 0;for(;j< 13 ;j+)double temp = *(&trainDatai.A2+j);pipei = C2_mapj.find(temp);if(pipei = C2_mapj.end()C2_mapj.insert(map<double, double>:value_type(temp,1);elsedouble j = pipei->second;pi

39、pei->second = j + 1;if(trainDatai.A1 = 3) /求P(Xk|C3) 中Xk的個數(shù)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<double, double>:value_type(temp,1);elsedouble j = pipei->second;pipei->second = j + 1;/概率f

40、or(i = 0; i < Shuxing; i+)for(pipei=C1_mapi.begin(); pipei!=C1_mapi.end(); +pipei) double num = pipei->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

41、(pipei=C3_mapi.begin(); pipei!=C3_mapi.end(); +pipei) double num = pipei->second; pipei->second = (double)num/(double)count3; void houyan()/計算后驗分布,找出最大值int i,j,k;double p3;for(i = 0; i<TestNum; i+)double pXC3=0,0,0;for(j = 0; j < 3; j+)map<double, double>:iterator pipei;/計算p(X|C1)f

42、or(k = 0; k < Shuxing; k+)pipei = C1_mapk.find(*(&testDatai.A2+k);if(pipei != C1_mapk.end()pXC0 =pXC0 + pipei->second;p0 = A0 * pXC0;/計算p(X|C2)for(k = 0; k < Shuxing; k+)pipei = C2_mapk.find(*(&testDatai.A2+k);if(pipei != C2_mapk.end()pXC1 =pXC1 + pipei->second;p1 = A1*pXC1;/計算p(

43、X|C3)for(k = 0; k < Shuxing; k+)pipei = C3_mapk.find(*(&testDatai.A2+k);if(pipei != C3_mapk.end()pXC2 =pXC2 + pipei->second;p2 = A2*pXC2;/找出最大值if(p0 > p1 && p0 >p2)cout<<p0<<" "<<1<<endl;if(testDatai.A1=1) m+;elseif(p1 > p2)cout<<p1&

44、lt;<" "<<2<<endl;if(testDatai.A1=2) m+;elsecout<<p2<<" "<<3<<endl;if(testDatai.A1=3) m+;void main()double tp,fp;cout<<"概率最大值 "<<"所屬類別"<<endl;DataRead(trainData,"wine.data");bayes();DataRead(tes

45、tData,"test.data");houyan();tp=(double)m/51;fp=1-tp;cout<<"正確率為："<<tp*100<<"%"<<endl; cout<<"錯誤率為："<<fp*100<<"%"<<endl;實驗3-1 C-Means聚類算法實現(xiàn)一、實驗目的通過分析C-Means聚類算法的聚類原理，利用Vc編程工具(或者其他編程工具)實現(xiàn)C-Means和FCM聚類算法，并

46、通過對樣本數(shù)據(jù)的聚類過程，加深對該聚類算法的理解與應用過程。實驗類型：綜合計劃課間：6學時二、實驗內(nèi)容1、分析C-Means聚類算法和FCM；2、分析距離計算方法；3、分析聚類的評價準則；4、編程完成C-Means聚類算法和FCM，并基于相關實驗數(shù)據(jù)實現(xiàn)聚類過程；三、實驗方法1、C-means聚類算法原理 C-means聚類算法以C為參數(shù)，把n個對象分為C個簇，以使簇內(nèi)的具有較高的相似度。相似度的計算根據(jù)一個簇中對象的平均值來進行。 算法描述： 輸入：簇的數(shù)目C和包含n個對象的數(shù)據(jù)庫輸出：使平方誤差準則最小的C個簇過程：任選C個對象作為初始的簇中心；Repeat for j=1 to n DO

47、 根據(jù)簇中對象的平均值，將每個對象賦給最類似的簇 for i=1 to C DO 更新簇的平均值 計算EUnitl E不再發(fā)生變化按簇輸出相應的對象2、聚類評價準則：E的計算為：四、實驗步驟4.1 實驗數(shù)據(jù)見實驗數(shù)據(jù)集Wine 和Iris數(shù)據(jù)4.2初始簇中心的選擇選擇k個樣本作為簇中心 For (i=0;i<k;i+) For (j=0;j<AttSetSize;j+)ClusterCenterij=DataBaseij4.3 數(shù)據(jù)對象的重新分配 Sim=某一較大數(shù)；ClusterNo=-1; For (i=0;i<k;i+) If (Distance(DataBasej,ClusterCenteri)<Sim) Sim=Distance(DataBasej,ClusterCenteri);ClusterNo=i;ObjectClusterj=ClusterNo;4.4 簇的更新 For (i=0;i<k;i+)Temp=0;Num=0; For (j=0;j<n;j+)If (ObjectClusterj=i)Num+; Temp+=DataBasej;If (ClusterCenteri!=Temp) HasChanged=TRUE;C