决策树算法实现（scikit-learn）

title: 决策树算法实现（scikit-learn）
date: 2017-03-04 00:22:41
tags: 机器学习

参考：

sk-learn的决策树文档
 决策树的算法介绍

在 Mac OS X 中安裝與使用 Graphviz 圖形視覺化工具

决策树归纳算法（ID3）

优先选择信息获取量最大的属性作为属性判断结点

信息获取量(Information Gain)：Gain(A) = Info(D) - Infor_A(D)

age属性信息获取量的计算过程如下所示：

算法步骤：

树以代表训练样本的单个结点开始。
如果样本都在同一个类，则该结点成为树叶，并用该类标号。
否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性。该属性成为该结点的“测试”或“判定”属性。在算法的该版本中，所有的属性都是分类的，即离散值。连续属性必须离散化。
对测试属性的每个已知的值，创建一个分枝，并据此划分样本。
算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不在该结点的任何后代上考虑它。
递归划分步骤仅当下列条件之一成立停止：

(a) 给定结点的所有样本属于同一类。

(b) 没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决。这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可以存放结点样本的类分布。

决策树的优缺点

优：直观，便于理解，小规模数据集有效

缺：处理连续变量不好
类别较多时，错误增加的比较快
可规模性一般

代码实现

数据转换为 sklearn需要的格式

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Created by xuehz on 2017/3/3


from sklearn.feature_extraction import DictVectorizer # 将字典 转化为 sklearn 用的数据形式 数据型 矩阵
import csv
from sklearn import preprocessing
from sklearn import tree
from sklearn.externals.six import StringIO


allElectronicsData = open('AllElectronics.csv','rb')
reader = csv.reader(allElectronicsData)

header = reader.next() #['RID', 'age', 'income', 'student', 'credit_rating', 'class_buys_computer']

## 数据预处理

featureList = [] #[{'credit_rating': 'fair', 'age': 'youth', 'student': 'no', 'income': 'high'}, {'credit_rating': 'excellent',
labelList = [] #['no', 'no', 'yes', 'yes', 'yes', 'no', 'yes', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']

for row in reader:
    labelList.append(row[-1])
    # 下面这几步的目的是为了让特征值转化成一种字典的形式，就可以调用sk-learn里面的DictVectorizer，直接将特征的类别值转化成0,1值
    rowDict = {}
    for i in range(1, len(row) - 1):
        rowDict[header[i]] = row[i]
    featureList.append(rowDict)

# Vectorize features
vec = DictVectorizer()
dummyX = vec.fit_transform(featureList).toarray()

print("dummyX:"+str(dummyX))

print(vec.get_feature_names())
"""
[[ 0.  0.  1.  0.  1.  1.  0.  0.  1.  0.]
 [ 0.  0.  1.  1.  0.  1.  0.  0.  1.  0.]

 ['age=middle_aged', 'age=senior', 'age=youth', 'credit_rating=excellent', 'credit_rating=fair', 'income=high', 'income=low', 'income=medium', 'student=no', 'student=yes']
"""


# label的转化，直接用preprocessing的LabelBinarizer方法
lb = preprocessing.LabelBinarizer()
dummyY = lb.fit_transform(labelList)
print("dummyY:"+str(dummyY))
print("labelList:"+str(labelList))
"""
dummyY:[[0]
 [0]
 [1]
 [1]
 [1]

 labelList:['no', 'no', 'yes', 'yes', 'yes', 'no', 'yes', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']
"""


#criterion是选择决策树节点的 标准 ，这里是按照“熵”为标准，即ID3算法；默认标准是gini index，即CART算法。

clf = tree.DecisionTreeClassifier(criterion='entropy')
clf = clf.fit(dummyX,dummyY)

print("clf:"+str(clf))
"""
clf:DecisionTreeClassifier(class_weight=None, criterion='entropy', max_depth=None,
            max_features=None, max_leaf_nodes=None, min_samples_leaf=1,
            min_samples_split=2, min_weight_fraction_leaf=0.0,
            presort=False, random_state=None, splitter='best')
"""

#生成dot文件
with open("allElectronicInformationGainOri.dot",'w') as f:
    f = tree.export_graphviz(clf, feature_names= vec.get_feature_names(),out_file= f)

#测试代码，取第1个实例数据，将001->100，即age：youth->middle_aged
oneRowX = dummyX[0,:]
print("oneRowX:"+str(oneRowX))
newRowX = oneRowX
newRowX[0] = 1
newRowX[2] = 0
print("newRowX:"+str(newRowX))

#预测代码
predictedY = clf.predict(newRowX)
print("predictedY:"+str(predictedY))

生成的 .dot 文件

digraph Tree {
node [shape=box] ;
0 [label="age=middle_aged <= 0.5
entropy = 0.9403
samples = 14
value = [5, 9]"] ;
1 [label="student=no <= 0.5
entropy = 1.0
samples = 10
value = [5, 5]"] ;
0 -> 1 [labeldistance=2.5, labelangle=45, headlabel="True"] ;
2 [label="credit_rating=fair <= 0.5
entropy = 0.7219
samples = 5
value = [1, 4]"] ;
1 -> 2 ;
3 [label="income=medium <= 0.5
entropy = 1.0
samples = 2
value = [1, 1]"] ;
2 -> 3 ;
4 [label="entropy = 0.0
samples = 1
value = [1, 0]"] ;
3 -> 4 ;
5 [label="entropy = 0.0
samples = 1
value = [0, 1]"] ;
3 -> 5 ;
6 [label="entropy = 0.0
samples = 3
value = [0, 3]"] ;
2 -> 6 ;
7 [label="age=senior <= 0.5
entropy = 0.7219
samples = 5
value = [4, 1]"] ;
1 -> 7 ;
8 [label="entropy = 0.0
samples = 3
value = [3, 0]"] ;
7 -> 8 ;
9 [label="credit_rating=excellent <= 0.5
entropy = 1.0
samples = 2
value = [1, 1]"] ;
7 -> 9 ;
10 [label="entropy = 0.0
samples = 1
value = [0, 1]"] ;
9 -> 10 ;
11 [label="entropy = 0.0
samples = 1
value = [1, 0]"] ;
9 -> 11 ;
12 [label="entropy = 0.0
samples = 4
value = [0, 4]"] ;
0 -> 12 [labeldistance=2.5, labelangle=-45, headlabel="False"] ;
}

将dot文件用graphviz转换为pdf文件

在命令行下，cd到你的dot文件的路径下，输入

dot -Tpdf filename.dot -o output.pdf
（filename以dot文件名为准）

文件和源码

https://github.com/xuehanzhe0526/python--Kaggle/tree/master/机器学习算法/决策树

不足之处请指出
个人博客：http://haozhe.site/