python實現決策樹

1.決策樹的簡介

　　http://www.cnblogs.com/lufangtao/archive/2013/05/30/3103588.html

2.決策是實現的偽代碼

“讀入訓練數據”
“找出每個屬性的可能取值”

“遞歸調用建立決策樹的函數”
    “para:節點，剩餘樣例，剩餘屬性”

    if “剩餘屬性個數為0"
        return most_of_result
    else if “剩餘樣例都屬於同一個分類(yes/no)"    
        return yes/no
    else：
           ”對於每一個剩餘屬性，計算該屬性的熵增“，並找到熵增最大的對應的屬性，即為最佳分類屬性”
    　　　　“按照最佳分類屬性分類，對於每個分支，遞歸調用建立函數，最終得到整個決策樹”

3.python數據結構設計

　　1.數據集：用於存儲二維的訓練數據training_data

　　　　二維的list數組,對於二維的list要取得某一列的數據，可以用zip(*dataset)[num]

　　2.屬性集合：用於存儲屬性的名稱attri_name_set

　　　　一維的list

　　3.屬性的可能取值：存儲各個屬性的可能取值狀態

　　　　dict+set:dict的key是屬性的名稱，value是set類型，這樣可以保證不會有重覆
　　　　新建set類型：attri[i] = set()

　　4.

4.code

# -*- coding: utf-8 -*-
from __future__ import division
import  math

__author__ = 'Jiayin'
#date:2016-3-28
#決策樹的實現，從test.txt中讀入訓練數據，




#全局變數
training_data = [] #數據集（二維list表）
attri = {}  #屬性集（dict+set）
attri_name_set = []

class Dtree_node(object):
    def __init__(self):
        self.attriname = None
        self.sub_node = {} #子節點為dict類型

root = Dtree_node()


#輸入數據
def  get_input():
    #屬性集合 屬性是dict結構，key為屬性名(str)，value是該屬性可以取到的值類型為set
    #第一個屬性通常為編號，最後一個屬性通常為決策結果，取值只有yes/no
    global attri
    global attri_name_set
    file_read = open("test.txt")
    line = file_read.readline().split()
    attri_name_set = line[:]
    #print line
    for i in line:
        attri[i] = set()

    line = file_read.readline().split()
    #讀入數據,並計算每個屬性的可能取值
    while line:
            training_data.append(line)
            for i in range(1,len(line)-1):
                attri[attri_name_set[i]].add(line[i])
            line = file_read.readline().split()

#取most_of _result
def getmost(dataset_result):
    p = 0
    n = 0
    for i in dataset_result:
        if i == 'yes':
            p+=1
        else:
            n+=1
    return  'yes' if p>n else 'no'


#計算熵
def cal_entropy(dataset_result):
    num_yes = 0
    num_no = 0
    for i in dataset_result:
        if i == 'yes':
            num_yes +=1
        else:
            num_no += 1
    if num_no == 0 or num_yes == 0:
        return 0
    total_num = num_no +num_yes
    per_yes = num_yes/total_num
    per_no = num_no/total_num
    return   -per_yes*math.log(per_yes,2)-per_no*math.log(per_no,2)

#計算某個屬性的熵增
#參數 ：數據集和屬性名,初始熵
def cal_incr_entr_attri(data_set,attriname,init_entropy):
    global attri
    global attri_name_set
    incr_entr = init_entropy
    attri_index = attri_name_set.index(attriname)

    #將該屬性的不同取值提取出來，並分別計算熵，求出熵增
    for i in attri[attriname]:
        #new_data = data_set[:]
        new_data = filter(lambda  x: True if x[attri_index] == i else False ,data_set)
        if len(new_data)==0:
            continue
        num = cal_entropy(zip(*new_data)[-1])
        incr_entr -= len(new_data)/len(data_set)*num

    return incr_entr



#判斷是否剩餘數據集都是一個結果
def if_all_label(dataset_result, result):
    #result = dataset_result[0]
    for i in range(0,len(dataset_result)):
        if dataset_result[i] <> result:
            break
    return False if dataset_result[i]<>result else True



#建立決策樹
#參數：root:節點     dataset:剩下的數據集      attriset:剩下的屬性集
def create_Dtree(root_node , data_set , attri_set):
    global attri
    global attri_name_set
    '''
    #如果當前數據集為空，應該返回上一層的most_of_result,此處要修改
    if len(data_set)==0:
        return None'''
    #考慮如果剩餘屬性集為空，則返回most_of_result
    if len(attri_set) == 0:
        print zip(*data_set)
        root_node.attriname = getmost(zip(*data_set)[-1]) #zip（*dataset)[-1]表示取出最後一列，也就是yes/no那一列
        return None
    #考慮如果剩餘的數據集都是一個結果的話，返回這個結果
    elif if_all_label(zip(*data_set)[-1],'yes'):
        root_node.attriname = 'yes'
        return None
    elif if_all_label(zip(*data_set)[-1],'no'):
        root_node.attriname = 'no'
        return None

    #print zip(*data_set)
    init_entropy = cal_entropy(zip(*data_set)[-1])#計算初始熵
    max_entropy  = 0
    for i in attri_set:
        entropy = cal_incr_entr_attri(data_set,i,init_entropy)
        if entropy > max_entropy:
            max_entropy = entropy
            best_attri = i

    new_attri = attri_set[:]
    root_node.attriname = best_attri
    attri_index = attri_name_set.index(best_attri)
    for attri_value in attri[best_attri]:
        #new_data = data_set[:]
        new_data = filter(lambda  x: True if x[attri_index] == attri_value else False ,data_set)
        root_node.sub_node[attri_value] = Dtree_node()
        #如果該分支下麵的數據集個數為0，則採用父節點的most_of_result
        if len(new_data)==0:
            root_node.sub_node[attri_value].attriname = getmost(zip(*data_set)[-1])
        else:
            create_Dtree(root_node.sub_node[attri_value],new_data,new_attri)

def print_Dtree(Root_node,layer):
    print Root_node.attriname
    count = 1
    if len(Root_node.sub_node) > 0:
        for sub in Root_node.sub_node.keys():
            for i in range(layer):
                print "|                 ",
            print "|----%10s---"%sub,
            assert isinstance(layer, object)
            print_Dtree(Root_node.sub_node[sub] , layer+1)
            #count += 1

def main():
    global root
    global attri_name_set
    get_input()#輸入
    attri_set = attri_name_set[1:-1]#提取出要分類的屬性
    create_Dtree(root,training_data,attri_set)#創建決策樹
    print_Dtree(root,0)#列印決策樹



main()