看完書后鹊汛，我參考了機(jī)器學(xué)習(xí)實(shí)戰(zhàn)里面的一些函數(shù)，自己用Python實(shí)現(xiàn)了決策樹算芯。我在實(shí)現(xiàn)過程中并沒有很好地利用好數(shù)據(jù)結(jié)構(gòu)中樹的概念，代碼還有很多需要改進(jìn)的地方凳宙。接下來我就簡單總結(jié)下我的代碼實(shí)現(xiàn)熙揍。
代碼整體的算法參考課本的74-80頁。我是先實(shí)現(xiàn)基于信息熵進(jìn)行劃分選擇的決策樹算法氏涩，先完整生成一棵決策樹届囚，再逐步修改代碼，實(shí)現(xiàn)預(yù)剪枝等是尖。
數(shù)據(jù)集如下：
假設(shè)訓(xùn)練集為D意系，屬性集為A，決策的實(shí)現(xiàn)在于從屬性集A中挑選出最優(yōu)屬性a饺汹，根據(jù)屬性a劃分?jǐn)?shù)據(jù)集蛔添，然后再繼續(xù)在劃分好的數(shù)據(jù)集中繼續(xù)尋找最優(yōu)屬性，多次迭代兜辞，生成一棵樹迎瞧。迭代的終止條件為：（1）當(dāng)前數(shù)據(jù)集同屬一類別，例如劃分好的數(shù)據(jù)集全為好瓜（2）當(dāng)前屬性集A為空逸吵，或者數(shù)據(jù)集在所有屬性上的取值相同（3）當(dāng)前數(shù)據(jù)集為空
決策算法的關(guān)鍵在于如何選擇最優(yōu)屬性（包括如何選擇最優(yōu)屬性（基于信息熵凶硅，基于基尼指數(shù)等）進(jìn)行劃分，是否進(jìn)行劃分（預(yù)剪枝扫皱，后剪枝等））
下面用基于信息熵的算法實(shí)現(xiàn)決策樹：
1.對數(shù)據(jù)進(jìn)行讀取
數(shù)據(jù)文件名為waterMelonData.txt,編碼格式為utf-8足绅，用全局變量dataset存儲所有數(shù)據(jù)，continusAttr存儲連續(xù)屬性名集? ? 合韩脑，attrAll存儲數(shù)據(jù)的第一行
2.計(jì)算信息熵：
計(jì)算信息熵：要統(tǒng)計(jì)數(shù)據(jù)dataset里的類別氢妈，用resultDict存儲類別（好瓜，壞瓜）段多，再計(jì)算各類別的概率允懂，最后算出信息熵
3.計(jì)算信息增益
屬性為不連續(xù)屬性時(shí)：
函數(shù)：
getAxis(attrChoose,attrAll)
attrChoose表示屬性，通過getAxis函數(shù)獲得數(shù)據(jù)文件的第幾列數(shù)據(jù)表示屬性attrChoose的描述衩匣，例如
attrChoose = “色澤”
得到axis = 1
splitDataSet(dataset,axis,key)
根據(jù)屬性的位置axis蕾总，找出屬性值為key的所有數(shù)據(jù)
連續(xù)性屬性：
a.要先對該屬性的所有取值排序
b.計(jì)算候選劃分點(diǎn)集合
c.分別計(jì)算候選劃分點(diǎn)的信息增益
d.得到最大信息增益粥航，得到最優(yōu)劃分點(diǎn)
連續(xù)屬性的數(shù)據(jù)只需要根據(jù)最優(yōu)劃分點(diǎn)，劃分為兩部分（data_small,data_large）即可
到這里已經(jīng)能分別算出每個(gè)屬性的信息增益了递雀，接下來就是遍歷未被使用過的屬性缀程，選出信息增益最大的屬性，進(jìn)行數(shù)? ? ? ? ? ? 據(jù)劃分
4.根據(jù)最優(yōu)屬性劃分
5.最后一步撩满，整合所有函數(shù)伺帘，迭代生成樹
補(bǔ)充：countAttrKey(dataset,attr,axis)函數(shù)
6.運(yùn)行結(jié)果：
運(yùn)行結(jié)果我只截取了部分
下面是根據(jù)運(yùn)行結(jié)果手動畫的樹：
7.代碼修改张咳，實(shí)現(xiàn)預(yù)剪枝晶伦，后剪枝等總結(jié)
a.個(gè)人覺得整體代碼處于較混亂狀態(tài)婚陪，在修改為預(yù)剪枝的時(shí)候频祝，總覺得部分函數(shù)有重合，或者是函數(shù)的劃分不太合理沽一。
b.書本中是將數(shù)據(jù)集認(rèn)為劃分為訓(xùn)練集和測試集,未思考如何劃分訓(xùn)練集合測試集
c.尷尬的是铣缠，在每個(gè)生成結(jié)點(diǎn)后，并沒有將每個(gè)結(jié)點(diǎn)存儲蝇庭，以致于在后剪枝時(shí)出現(xiàn)了一定的問題∽尘拢考慮用樹的思想喷屋，修改代碼
