機器學習--決策樹(ID3)算法及案例

1、機器學習-決策樹(ID3)算法及案例1基本原理    決策樹是一個預測模型。它代表的是對象屬性與對象值之間的一種映射關系。樹中每個節(jié)點表示某個對象，每個分支路徑代表某個可能的屬性值，每個葉結點則對應從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。一般情況下，決策樹由決策結點、分支路徑和葉結點組成。在選擇哪個屬性作為結點的時候，采用信息論原理，計算信息增益，獲得最大信息增益的屬性就是最好的選擇。信息增益是指原有數(shù)據(jù)集的熵減去按某個屬性分類后數(shù)據(jù)集的熵所得的差值。然后采用遞歸的原則處理數(shù)據(jù)集，并得到了我們需要的決策樹。   2算法流程  

2、  檢測數(shù)據(jù)集中的每個子項是否屬于同一分類：        If 是，則返回類別標簽；        Else                        計算信息增益，尋找劃分數(shù)據(jù)集的最好特征&#

3、160;                    劃分數(shù)據(jù)數(shù)據(jù)集           創(chuàng)建分支節(jié)點（葉結點或決策結點）               for 每個劃分的子集&

4、#160;                  遞歸調用，并增加返回結果到分支節(jié)點中           return 分支結點算法的基本思想可以概括為：    1）樹以代表訓練樣本的根結點開始。    2）如果樣本都在同一個類則該結點成為樹葉，并記錄該類。 

5、  3）否則，算法選擇最有分類能力的屬性作為決策樹的當前結點    4 ）根據(jù)當前決策結點屬性取值的不同，將訓練樣本根據(jù)該屬性的值分為若干子集，每個取值形成一個分枝，有幾個取值形成幾個分枝。勻針對上一步得到的一個子集，重復進行先前步驟，遞歸形成每個劃分樣本上的決策樹。一旦一個屬性只出現(xiàn)在一個結點上，就不必在該結點的任何后代考慮它，直接標記類別。    5）遞歸劃分步驟僅當下列條件之一成立時停止：    給定結點的所有樣本屬于同一類。    沒有剩余屬性可以用來進一步劃分樣本在這種情況下使用多數(shù)表決，將給定

6、的結點轉換成樹葉，并以樣本中元組個數(shù)最多的類別作為類別標記，同時也可以存放該結點樣本的類別分布這個主要可以用來剪枝。    如果某一分枝tc，沒有滿足該分支中已有分類的樣本，則以樣本的多數(shù)類生成葉子節(jié)點。  算法中2)步所指的最優(yōu)分類能力的屬性。這個屬性的選擇是本算法種的關鍵點，分裂屬性的選擇直接關系到此算法的優(yōu)劣。   一般來說可以用比較信息增益和信息增益率的方式來進行。  其中信息增益的概念又會牽扯出熵的概念。熵的概念是香農(nóng)在研究信息量方面的提出的。它的計算公式是：    Info(D)=-p1log(p1)/

7、log(2.0)-p2log(p2)/log(2.0)-p3log(p3)/log(2.0)+.-pNlog(pN)/log(2.0)    (其中N表示所有的不同類別)  而信息增益為：            Gain(A)=Info(D)-Info(Da)             其中Info(Da)數(shù)據(jù)集在屬性A的情況下的信息量(熵)。3算法的特點    優(yōu)點：計算復雜度不高，輸出結果易于理解，對中間

8、值的缺失不敏感，可以處理不相關特征數(shù)據(jù)。    缺點：可能會產(chǎn)生過度匹配問題    適用數(shù)據(jù)范圍：數(shù)值型和標稱型。4python代碼實現(xiàn)1、創(chuàng)建初始數(shù)據(jù)集，用于測試#功能：創(chuàng)建數(shù)據(jù)集#輸入變量：空#輸出變量：data_set, labels 數(shù)據(jù)集，標簽#def create_data_set():    data_set = 1, 1, 'yes',           

9、;       1, 1, 'yes',                1, 0, 'no',                0, 1, 'no',   

10、0;            0, 1, 'no'    #  數(shù)據(jù)集最后一列表示葉結點，也稱類別標簽    labels = 'no surfacing', 'flippers'   # 表示決策結點，也稱特征標簽    return data_set, labels2、計算給定數(shù)據(jù)集的信息熵#功能：計算信息熵#輸入變量：data

11、_set 數(shù)據(jù)集#輸出變量：shannon_ent 信息熵#def calc_shannon_ent(data_set):    num_entries = len(data_set)    label_counts =     for feat_vec in data_set:        current_label = feat_vec-1        # g

12、et相當于一條if.else.語句        # 如果參數(shù)current_label不在字典中則返回參數(shù)0，        # 如果current_label在字典中則返回current_label對應的value值        label_countscurrent_label = label_counts.get(current_label, 0) + 1  

13、;  shannon_ent = 0.0    for key in label_counts:        prob = float(label_countskey)/num_entries        shannon_ent -= prob*log(prob, 2)    return shannon_ent3、按照給定特征劃分數(shù)據(jù)集。分類算法除了需要測量信息熵，還需要劃分數(shù)據(jù)集

14、，這就需要對每個特征劃分數(shù)據(jù)集的結果計算一次信息熵，然后判斷按照哪個特征劃分數(shù)據(jù)集是最好的劃分方式。#功能：劃分數(shù)據(jù)集#輸入變量：data_set, axis, value# 數(shù)據(jù)集，數(shù)據(jù)集的特征，特征的值#輸出變量：ret_data_set, 劃分后的數(shù)據(jù)集#def split_data_set(data_set, axis, value):    ret_data_set =     for feat_vec in data_set:        i

15、f feat_vecaxis = value:            # 把axis特征位置之前和之后的特征值切出來            # 沒有使用del函數(shù)的原因是，del會改變原始數(shù)據(jù)            reduced_feat_vec = feat_vec

16、:axis            reduced_feat_vec.extend(feat_vecaxis+1:)            ret_data_set.append(reduced_feat_vec)    return ret_data_set4、遍歷整個數(shù)據(jù)集，循環(huán)劃分數(shù)據(jù)并計算信息熵，通過計算最大信息增益來找到最好的特征劃分方式。

17、具體做法是，遍歷當前特征中的所有唯一屬性值，對每個特征劃分一次數(shù)據(jù)集，然后計算數(shù)據(jù)集的新熵值，并對所有唯一特征值得到的熵求和。最后用所求的和值與原始信息熵相減，計算尋找最大信息增益。#功能：選擇最好的數(shù)據(jù)集劃分方式#輸入變量：data_set 待劃分的數(shù)據(jù)集#輸出變量：best_feature 計算得出最好的劃分數(shù)據(jù)集的特征#def choose_best_feature_to_split(data_set):    num_features = len(data_set0) - 1  # 最后一個是類別標簽，所以特征屬性長度為總長度減1 &#

18、160;  base_entropy = calc_shannon_ent(data_set)  # 計算數(shù)據(jù)集原始信息熵    best_info_gain = 0.0    best_feature = -1    for i in xrange(num_features):        # feat_veci代表第i列的特征值，在for循環(huán)獲取這一列的所有值    &#

19、160;   feat_list = feat_veci for feat_vec in data_set        unique_vals = set(feat_list)  # set函數(shù)得到的是一個無序不重復數(shù)據(jù)集        new_entropy = 0.0        # 計算每種劃分方式的信息熵   

20、60;    for value in unique_vals:            sub_data_set = split_data_set(data_set, i, value)            prob = len(sub_data_set)/float(len(data_set)    &#

21、160;       new_entropy += prob*calc_shannon_ent(sub_data_set)        info_gain = base_entropy - new_entropy        if info_gain > best_info_gain:        

22、0;   best_info_gain = info_gain            best_feature = i    return best_feature5遞歸構建決策樹工作原理：得到原始數(shù)據(jù)集，然后基于最好的屬性值劃分數(shù)據(jù)集，由于特征值可能多于兩個，因此可能存在大于兩個分支的數(shù)據(jù)集劃分。第一次劃分之后，數(shù)據(jù)將被向下傳遞到樹分支的下一個節(jié)點，在這個節(jié)點上，我們可以再次劃分數(shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集。遞歸結束條件

23、是：第一、所有的類別標簽（葉結點）完全相同。第二、使用完了所有的特征，仍然不能將數(shù)據(jù)集劃分成僅包含唯一類別的分組，則挑選出次數(shù)最多的類別作為返回值。#功能：多數(shù)表決分類#輸入變量：class_list 所有數(shù)據(jù)的標簽數(shù)組#輸出變量：sorted_class_count00 出現(xiàn)次數(shù)最多的分類名稱#def majority_vote_sort(class_list):    class_count =     for vote in class_list:       

24、; class_countvote = class_count.get(vote, 0) + 1    # items以列表方式返回字典中的鍵值對，iteritems以迭代器對象返回鍵值對，而鍵值對以元組方式存儲，即這種方式(), ()    # operator.itemgetter(0)獲取對象的第0個域的值，即返回的是key值    # operator.itemgetter(1)獲取對象的第1個域的值，即返回的是value值    # operator.itemget

25、ter定義了一個函數(shù)，通過該函數(shù)作用到對象上才能獲取值    # reverse=True是按降序排序    sorted_class_count = sorted(class_count.iteritems(), key=operator.itemgetter(1), reverse=True)    return sorted_class_count00#功能：創(chuàng)建數(shù)#輸入變量：data_set, labels 待分類數(shù)據(jù)集，標簽#輸出變量：my_tree 決策樹#def create_tree(da

26、ta_set, labels):    class_list = example-1 for example in data_set    # 判斷類別標簽是否完全相同    # count()是列表內置的方法，可以統(tǒng)計某個元素在列表中出現(xiàn)的次數(shù)    if class_list.count(class_list0) = len(class_list):        return class_list0&

27、#160;   # 遍歷完所有特征時返回出現(xiàn)次數(shù)最多的    if len(data_set0) = 1:        return majority_vote_sort(class_list)    best_feat = choose_best_feature_to_split(data_set)    best_feat_label = labelsbest_feat    my

28、_tree = best_feat_label:     del(labelsbest_feat)    # 得到列表包含的所有屬性值    feat_values = examplebest_feat for example in data_set    unique_vals = set(feat_values)    for value in unique_vals:      &

29、#160; sub_labels = labels:  # :復制特征標簽，為了保證循環(huán)調用函數(shù)create_tree()不改變原始的內容        ret_data_set = split_data_set(data_set, best_feat, value)        my_treebest_feat_labelvalue = create_tree(ret_data_set, sub_labels)  

30、0; return my_tree6測試代碼def main():    my_data, my_labels = create_data_set()    #my_data0-1 = 'maybe'    print 'my_data=', my_data    print 'my_labels=', my_labels    shannon_ent = calc_shannon_ent(my_d

31、ata)    print 'shannon_ent=', shannon_ent    ret_data_set = split_data_set(my_data, 1, 1)  # 由第1個特征且特征值為1的數(shù)據(jù)集劃分出來    print 'ret_data_set=', ret_data_set    best_feature = choose_best_feature_to_split(my_data)  

32、;  print 'best_feature=', best_feature    my_tree = create_tree(my_data, my_labels)    print 'my_tree=', my_treeif _name_ = '_main_':    main()在進行案例分析前，先對決策樹算法的分類函數(shù)進行測試?？紤]到構造決策樹非常耗時，為了節(jié)省計算時間，最好能夠在每次執(zhí)行分類時調用已經(jīng)構造好的決策樹。這就需要利用pytho

33、n模塊pickle序列化對象將決策樹分類算法保存在磁盤中，并在需要的時候讀取出來。1、測試決策樹分類算法性能#功能：決策樹的分類函數(shù)#輸入變量：input_tree, feat_labels, test_vec# 決策樹，分類標簽，測試數(shù)據(jù)#輸出變量：class_label 類標簽#def classify(input_tree, feat_labels, test_vec):    first_str = input_tree.keys()0    second_dict = input_treefirst_str 

34、60;  class_label = -1    # index方法用于查找當前列表中第一個匹配first_str變量的索引    feat_index = feat_labels.index(first_str)    for key in second_dict.keys():        if test_vecfeat_index = key:      &#

35、160;     if type(second_dictkey)._name_ = 'dict':                class_label = classify(second_dictkey, feat_labels, test_vec)            else

36、:                class_label = second_dictkey    return class_label2、對決策樹算法進行存儲#功能：將決策樹存儲到磁盤中#輸入變量：input_tree, filename 決策樹，存儲的文件名#def store_tree(input_tree, filename):    import pickle    fw = open(filename, 'w')    pickle.dump(input_tree, fw)  # 序列化，將數(shù)據(jù)寫入到文件中    fw.close()3、對決策樹算法進行讀取#功能：從磁盤中讀取決策樹信息#輸入變量：filename 存儲的文件名#def grab_tree(filename):    import pickle