1、使用ID3算法實現(xiàn)決策樹決策樹基本介紹：決策樹通過把數(shù)據(jù)樣本分配到某個葉子結點來確定數(shù)據(jù)集中樣本所屬的分類。決策樹由決策結點，分支和葉子結點組成。決策結點表示在樣本的一個屬性上進行的劃分；分支表示對于決策結點進行劃分的輸出；葉子節(jié)點代表經(jīng)過分支到達的類。從決策樹根據(jù)節(jié)點出發(fā)，自頂向下移動，在每個決策結點都會進行次劃分，通過劃分的結果將樣本進行分類，導致不同的分支，最后到達個葉子結點，這個過程就是利用決策樹進行分類的過程。ID3算法原理ID3算法是在每個結點處選取能獲得最高信息增益的分支屬性進行分裂。在每個決策結點處劃分分支，選取分支屬性的目的就是將整個決策樹的樣本純度提高。衡量樣本集合純的指標

2、則是熵(熵越大，所含有用信息就越少，不確定性就越大，在決策樹中，熵指的是純度，熵越小，純度越高)，設S為數(shù)量為n的樣本集，其分支屬性有m個取值用來定義m個不同分類Ci(i=1,2,3,，m)那么熵為：1illEntropy二-ptlog7仙）魯計算分支屬性對于樣本集分類好壞程度的度量一一信息增益。由于分裂后樣本集的純度提高，則樣本集的熵降低，熵降低的值即為該分裂方法的信息增益:1.第一步，創(chuàng)建數(shù)據(jù)和標簽。rommathimportlogmportoperator用于函數(shù)操作defcreate_data():構建數(shù)據(jù)和標簽dataSet=short,longhair,thin,female,hi

3、gh,shorthair,thin,male,short,longhair,fat,female,high,longhair,thin,female,short,shorthair,fat,male,short,shorthair,thin,female,high,shorthair,fat,male,high,longhair,fat,male,short,shorthair,thin,male,high,shorthair,thin,female,short,longhair,fat,femalelabels=stature,hair,weight,genderreturndataSet,

4、labels2使用ID3算法需計算信息熵，所以第二步創(chuàng)建cal_entropy方法來計算信息熵。defcal_entropy(dataSet):num=len(dataSet)總共有多少行數(shù)據(jù)label_count=forfeaindataSet:遍歷整個數(shù)據(jù)集，每次取一行current_label=fea-1統(tǒng)計每條數(shù)據(jù)的類，取該行最后一列的值，即標簽ifcurrent_labelnotinlabel_count.keys():判斷在字典中標簽是否存在label_countcurrent_label=0label_countcurrent_label+=1計算每個類中有多少數(shù)據(jù)entropy

5、=0.0初始化信息熵foriinlabel_count:計算經(jīng)驗熵Pi=float(label_counti)/numentropy-=Pi*log(Pi,2)returnentropy返回信息熵第三步，創(chuàng)建remove_feature方法來去除某個特征，對數(shù)據(jù)集進行分割。defremoveeature(dataSet,axis,feature):去除某個特征retdataset=forfeatVecindataSet:iffeatVecaxis=feature:reducedata=featVec:axis某個特征前數(shù)據(jù)reducedata.extend(featVecaxis+1:)某個特

6、征后數(shù)據(jù)去掉Taxisretdataset.append(reducedata)returnretdataset第四步，通過信息熵計算信息增益率來求出劃分數(shù)據(jù)集的最優(yōu)信息增益比。defchoose_best_feature(dataSet):entropy=cal_entropy(dataSet)feature_num=len(dataSet0)-1獲取當前數(shù)據(jù)集的特征個數(shù)，最后一列是分類標簽max_mutualnfo=0best_feature=-1初始化最優(yōu)特征foriinrange(feature_num):feature_list=exampleiforexampleindataSet

7、獲取數(shù)據(jù)集中當前特征下的所有值feature_class=set(feature_list)得到該特征的所有可能取值conditional_entropy=0forvalueinfeature_class:retdataset=remove_feature(dataSet,i,value)去處某一特征，方便計算Pi=len(retdataset)/float(len(dataSet)conditional_entropy+=Pi*cal_entropy(retdataset)求條件熵mutual_info=entropy-conditional_entropy互信息量if(mutualnfom

8、ax_mutualnfo):比較每個特征的信息增益比，只要最好的信息增益比max_mutualnfo=mutualnfobest_feature=ireturnbeslature創(chuàng)建一個majority_vote方法將傳入的數(shù)據(jù)按出現(xiàn)的頻率進行降序排列，并返回第一個鍵名。defmajority_vote(class_list):class_count=存各種分類出現(xiàn)的頻率forvoteinclass_list:ifvotenotinclass_count.keys():class_counlvote=0class_countvote+=1對字典進行排序sort_class_count=sort

9、ed(class_count.items(),key=operator.itemgetter(1),reverse=True)排序來決定該節(jié)點的類returnsortclasscount00最后一步，根據(jù)得到的最優(yōu)信息增益比生成決策樹。生成決策樹defcreate_tree(dataSet,labels):class_list=example-1forexampleindataSet終止條件1:class_list是否純凈(純凈就是數(shù)據(jù)中所有特征都相等)ifclass_list.count(class_list0)=len(class_list):當整個數(shù)據(jù)中的類別完全相同時類別已經(jīng)純凈了，則

10、停止繼續(xù)劃分，直接返回該類的標簽returnclass_list0iflen(dataSet0)=1:節(jié)點已沒有特征可以繼續(xù)分解returnmajority_vote(class_list)best_feature=choose_best_feature(dataSet)選擇最好的分類特征索引best_feature_label=labelsbest_feature獲得該特征的名字直接使用字典變量來存儲樹信息my_tree=best_feature_label:當前數(shù)據(jù)集選取最好的特征存儲iSest_feature中del(labelsbest_feature)刪掉已選擇的特征feature=

11、examplebest_featureforexampleindataSet取出最優(yōu)列的值feature_class=set(feature)根據(jù)這個列的這個eature_class值來切分樹的節(jié)點forvalueinfeature_class:sublabels=labels:my_treebest_feature_labelvalue=create_tree(remove_feature(dataSet,best_feature,value),sublabels)迭代生成決策樹returnmytree運行結果為:hair1:1Longhair1:statura:short1:female1,high1:weight:fat1:male1,thin1:femalesho