實驗二 分類挖掘算法

1、實驗二 分類挖掘算法(ID3)一、實驗?zāi)康?、理解分類2、掌握分類挖掘算法ID33、為改進ID3打下基礎(chǔ)二、實驗內(nèi)容1、選定一個數(shù)據(jù)集(可以參考教學(xué)中使用的數(shù)據(jù)集)2、選擇合適的實現(xiàn)環(huán)境和工具實現(xiàn)算法ID33、給出分類規(guī)則三、實驗原理決策樹是一種最常見的分類算法，它包含有很多不同的變種，ID3算法是其中最簡單的 一種。ID3算法中最主要的部分就是信息熵和信息增益的計算。信息熵的計算公式如下。而玦的可)= -云F1理汽婦信息增益的計算公式為：Gai 威 S. J) = E* 叮(5)一 三 U&igpj其中P(ui)為類別ui在樣本S中出現(xiàn)的概率，A是樣本的屬性，Value(A)是屬性A所有 取

2、值的集合，v是A得其中一個屬性值。Sv是S中A的值為v的樣例集合。ID3算法的流程就是在屬性集A中尋找信息增益值最大的屬性，作為根節(jié)點，按照根節(jié) 點屬性的取值將樣本集合分成幾個子集，將此屬性從屬性集中去掉，在每個子集中選擇信息 增益值最大的屬性，作為當(dāng)前子集的根節(jié)點，上層集合的根節(jié)點的子節(jié)點，如此循環(huán)遞歸， 如果得到的子集中所有的樣本屬于一個類別，則遞歸停止。四、實驗要求1、數(shù)據(jù)集具有一定的代表性，可以使用數(shù)據(jù)庫技術(shù)管理2、實現(xiàn)界面友好3、提交實驗報告：實驗題目、目的、數(shù)據(jù)集描述、實驗環(huán)境、過程、結(jié)果和分析等。五、實驗步驟1、所采用的數(shù)據(jù)集，如圖1所示：收入范圍煌險促帶信川曰呆隆q齡40-50

3、K否453040K是仲k404J-50K杏杏yj423O-4OK是w43506晾fik382CI-3OKfi有女5530-40K是EJJ*20-3OK否w27否43Ka杏44(1- 50K是4320-30k否女29M-WK是女39而一 5OK行55a是192、具體步驟構(gòu)造決策樹的方法是采用自上而下的遞歸構(gòu)造，其思路是：1）以代表訓(xùn)練樣本的單個結(jié)點開始建樹（步驟1）。2）如果樣本都在同一類，則該結(jié)點成為樹葉，并用該類標(biāo)記（步驟2和3）。3）否則，算法使用稱為信息增益的機遇熵的度量為啟發(fā)信息，選擇能最好地將樣本分類 的屬性（步驟6）。該屬性成為該結(jié)點的“測試”或“判定”屬性（步驟7）。值得注意的是

4、，在 這類算法中，所有的屬性都是分類的，即取離散值的。連續(xù)值的屬性必須離散化。4）對測試屬性的每個已知的值，創(chuàng)建一個分支，并據(jù)此劃分樣本（步驟810）。5）算法使用同樣的過程，遞歸地形成每個劃分上的樣本決策樹。一旦一個屬性出現(xiàn)在一 個結(jié)點上，就不必考慮該結(jié)點的任何后代（步驟13）。6）遞歸劃分步驟，當(dāng)下列條件之一成立時停止：給定結(jié)點的所有樣本屬于同一類（步驟2和3）。沒有剩余屬性可以用來進一步劃分樣本（步驟4）。在此情況下，采用多數(shù)表決（步 驟5）。這涉及將給定的結(jié)點轉(zhuǎn)換成樹葉，并用samples中的多數(shù)所在類別標(biāo)記它。換一種方 式，可以存放結(jié)點樣本的類分布。分支test_attribute=

5、ai沒有樣本。在這種情況下，以samples中的多數(shù)類創(chuàng)建一個樹葉 （步驟12）。Decision_Tree（samples,attribute_list）輸入由離散值屬性描述的訓(xùn)練樣本集samples;候選屬性集合attribute_list。輸出一棵決策樹。1）創(chuàng)建節(jié)點N；2）if samples 都在同一類 C 中 then3）返回N作為葉節(jié)點，以類C標(biāo)記；4）if attribute_list 為空 then5）返回N作為葉節(jié)點，以samples中最普遍的類標(biāo)記；多數(shù)表決6）選擇attribute list中具有最高信息增益的屬性test attribute;以 test_attrib

6、ute 標(biāo)記節(jié)點 N；for each test_attribute 的已知值 v劃分 samples由節(jié)點N分出一個對應(yīng)test_attribute=v的分支；令Sv為samples中test_attribute=v的樣本集合；一個劃分塊if Sv 為空 then加上一個葉節(jié)點，以samples中最普遍的類標(biāo)記；else 加入一個由 Decision_Tree(Sv,attribute_list-test_attribute)返回節(jié)點值六、實驗結(jié)果1、具體輸出結(jié)果如圖1、2所示：(termiitated TestDecisi onTree Java Appli cation C : Frc

7、請輸入候選屬性 age income stucient. crediating請輸入訓(xùn)練數(shù)據(jù) yout.li high no fair nc yout.li high no excellent. no inidd 1 e_aged high noyessenior inediiim no fair yea senior low yes fair yes senior low yes excel lent, no inidd 1 eaged low yes exceHeinz yes yout.h rtiedituti no fair no yout.li lotij yes fair yes

8、senior inediiim yes fair yes yo ut-li rned i tun ye a excel le nt. ye a inidd 1 e_aged rnediinn nc excel lent yes inidd 1 e_aged high yes fair yes senior inediiiiri no excel lent, no圖1n；5iiie : agenude rules : youth iniddle_agecl senior siz已 of childr已n:3child 1 of no cl 已 目g已： n；3iri 已：st. nd 已 ntn

9、ude cules: ( no yes size of childrenschild 1 f nocie st.uclent: n；5Ltne : nonude rules : 已盤 node !child 2 of no de student: n；zune : yesnode rules: leaf node!child 2 of nocle age : n；3itie : yesnocl已 rul已 已盤 node !child 3 u f no de age : n；sitie : crecli t_rat i ngnode rules: ralr exce1 lent )size of childrenschild 1 f no cl 已 c