實驗二 分類挖掘算法

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

2、值的集合，v是A得其中一個屬性值。Sv是S中A的值為v的樣例集合。ID3算法的流程就是在屬性集A中尋找信息增益值最大的屬性，作為根節(jié)點，按照根節(jié) 點屬性的取值將樣本集合分成幾個子集，將此屬性從屬性集中去掉，在每個子集中選擇信息 增益值最大的屬性，作為當前子集的根節(jié)點，上層集合的根節(jié)點的子節(jié)點，如此循環(huán)遞歸， 如果得到的子集中所有的樣本屬于一個類別，則遞歸停止。四、實驗要求1、數據集具有一定的代表性，可以使用數據庫技術管理2、實現界面友好3、提交實驗報告：實驗題目、目的、數據集描述、實驗環(huán)境、過程、結果和分析等。五、實驗步驟1、所采用的數據集，如圖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、具體步驟構造決策樹的方法是采用自上而下的遞歸構造，其思路是：1）以代表訓練樣本的單個結點開始建樹（步驟1）。2）如果樣本都在同一類，則該結點成為樹葉，并用該類標記（步驟2和3）。3）否則，算法使用稱為信息增益的機遇熵的度量為啟發(fā)信息，選擇能最好地將樣本分類 的屬性（步驟6）。該屬性成為該結點的“測試”或“判定”屬性（步驟7）。值得注意的是

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

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

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

7、請輸入候選屬性 age income stucient. crediating請輸入訓練數據 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