当前位置:   article > 正文

『机器学习』 —— 决策树算法(Decision Tree)_决策树模型 实现颜色分类的方法

决策树模型 实现颜色分类的方法

文章首发地址见个人博客

决策树(Decision Tree)


1、机器学习算法中分类和预测算法的评估

  • 准确率
  • 速度
  • 强壮性
  • 可规模性
  • 可解释性

2、什么是决策树(Decision Tree)?
决策树是一种类似流程图的树形结构,每个结点表示一个属性测试,每条边表示一个属性输出,每个树叶结点表示类或者类分布。决策树的决策过程需要从决策树的根节点开始,待测数据与决策树中的特征节点进行比较,并按照比较结果选择选择下一比较分支,直到叶子节点作为最终的决策结果。
cmd-markdown-logo

3、决策树的学习过程

  • 特征选择:从训练数据的特征中选择一个特征作为当前节点的分裂标准(如上图中,“颜色”为上述决策树的一个特征),特征选择的标准不同产生了不同的特征决策算法
  • 决策树生成:根据所选特征峰评估标准,从上至下递归生成子节点,知道数据集不可分则停止决策树生成
  • 剪 枝:决策树容易过拟合,需要剪枝来缩小树的结构和规模(包括预剪枝和后剪枝)。

实现决策树的算法包括ID3、C4.5算法等
4、ID3算法
ID3算法是由Ross Quinlan提出的决策树的一种算法实现,以信息论为基础,以信息熵和信息增益为衡量标准,从而实现对数据的归纳分类。
ID3算法是建立在奥卡姆剃刀的基础上:越是小型的决策树越优于大的决策树(be simple简单理论)。

  • 信息熵:用来衡量一个随机变量出现的期望值,如果信息的不确定性越大,熵的值也就越大,出现的各种情况也就越多。信息熵的计算公式为:
    E n t r o p y ( S ) = ∑ i = 1 n − P i l o g 2 P i Entropy(S)=\sum_{i=1}^n-P_ilog_2P_i Entropy(S)=i=1nPilog2Pi
    其中 S S S为所有事件的集合, P i P_i Pi为事件 i i i发生的概率, n n n为特征总数
  • 信息增益:是指信息划分前后信息熵的变化,也就是说由于使用了某个特征划分,使得信息熵发生变化,而两者之间的差值就是信息增益,其计算公式如下:
    G a i n ( S , A ) = E n t r o p y ( S ) − ∑ v ∈ V a l u e ( A ) ∣ S v ∣ s E n t r o p y ( S y ) Gain(S,A) = Entropy(S) - \sum_{v∈Value(A)}\frac{|S_v|}{s}Entropy(S_y) Gain(S,A)=Entropy(S)vValue(A)sSvEntropy(Sy)
    其中——号后面的部分表示为属性A对S划分的期望值(划分后的信息熵)

算法实现:

  • 初始化属性集合和数据集合
  • 计算数据集合信息熵S和所有属性的信息熵,选择信息增益最大的属性作为当前决策节点
  • 更新数据集合和属性集合(删除掉上一步中使用的属性,并按照属性值来划分不同分支的数据集合)
  • 依次对每种取值情况下的子集重复第二步
  • 若子集只包含单一属性,则为分支为叶子节点,根据其属性值标记。
  • 完成所有属性集合的划分

5、案例实现
通过决策树算法根据一个人的信息来判断他是否会购买电脑。数据如下:
|RID|age|income|student|credit_rating | Class:buys_computer|
|-------|------|-------|------------|--------|
|1|youth|high|no|fair|no|
|2|youth|high|no|excellent|no|
|3|middle_aged|high|no|fair|yes|
|4|senior|medium|no|fair|yes|
|5|senior|low|yes|fair|yes|
|6|senior|low|yes|excellent|no|
|7|middle_aged|low|yes|excellent|yes|
|8|youth|medium|no|fair|no|
|9|youth|low|yes|fair|yes|
|10|senior|medium|yes|fair|yes|
|11|youth|medium|yes|excellent|yes|
|12|middle_aged|medium|no|excellent|yes|
|13|middle_aged|high|yes|fair|yes|
|14|senior|medium|no|excellent|no|
整体数据集合的信息熵:
I n f o ( D ) = ∑ i = 1 n − P i l o g 2 P i = − 5 14 l o g 2 ( 9 14 ) − 5 14 l o g 2 ( 5 14 ) = 0.940 b i t s Info(D) = \sum_{i=1}^n-P_ilog_2P_i = -\frac{5}{14}log_2(\frac{9}{14})-\frac{5}{14}log_2(\frac{5}{14})=0.940bits Info(D)=i=1nPilog2Pi=145log2(149)145log2(145)=0.940bits
通过年龄划分后的信息熵:
I n f o a g e ( D ) = 5 14 × ( − 2 5 l o g 2 2 5 − 3 5 l o g 2 3 5 ) + 4 14 × ( − 4 4 l o g 2 4 4 − 0 4 l o g 2 0 4 ) + 5 14 × ( − 3 5 l o g 2 3 5 − 2 5 l o g 2 2 5 ) = 0.694 b i t s Info_{age}(D) = \frac{5}{14}\times(-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5})+\frac{4}{14}\times(-\frac{4}{4}log_2\frac{4}{4}-\frac{0}{4}log_2\frac{0}{4})+\frac{5}{14}\times(-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5})=0.694bits Infoage(D)=145×(52log25253log253)+144×(44log24440log240)+145×(53log25352log252)=0.694bits
通年龄划分的信息增益:
G a i n ( a g e ) = I n f o ( D ) − I n f o a g e ( D ) = 0.940 − 0.694 = 0.246 b i t s Gain(age) = Info(D)-Info_{age}(D)=0.940-0.694=0.246bits Gain(age)=Info(D)Infoage(D)=0.9400.694=0.246bits
同上可以计算出
G a i n ( i n c o m e ) = 0.029 Gain(income)=0.029 Gain(income)=0.029
G a i n ( s t u d e n t ) = 0.151 Gain(student)=0.151 Gain(student)=0.151
G a i n ( c r e d i t r a t i n g ) = 0.048 Gain(credit_rating)=0.048 Gain(creditrating)=0.048
根据算法的原来选择age为第一个结点,当age确定为根节点时,此时的决策树为下图所示:
插图
当第一个结点确定后删除age属性,继续之前的操作,计算出整体数据的信息熵和通过剩余属性划分的信息熵,作差计算出每个属性的信息增益从而决定下一个结点,如此迭代直至所有结点确定。
代码实现(Python)

数据文件下载:AllElectronics.csv ----->Download

from sklearn.feature_extraction import DictVectorizer
import csv
from sklearn import tree
from sklearn import preprocessing
from sklearn.externals.six import StringIO

# Read in the csv file and put features into list of dict and list of class label
allElectronicsData = open(r'AllElectronics.csv的文件路径', 'rt')
reader = csv.reader(allElectronicsData)
#headers = reader.next()   python3.0已经不支持
headers = next(reader)

print(headers)

featureList = []
labelList = []

for row in reader:
    labelList.append(row[len(row)-1])
    rowDict = {}
    for i in range(1, len(row)-1):
        rowDict[headers[i]] = row[i]
    featureList.append(rowDict)

print(featureList)

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

print("dummyX: " + str(dummyX))
print(vec.get_feature_names())

print("labelList: " + str(labelList))

# vectorize class labels
lb = preprocessing.LabelBinarizer()
dummyY = lb.fit_transform(labelList)
print("dummyY: " + str(dummyY))

# Using decision tree for classification
# clf = tree.DecisionTreeClassifier()
clf = tree.DecisionTreeClassifier(criterion='entropy')
clf = clf.fit(dummyX, dummyY)
print("clf: " + str(clf))


# Visualize model
with open("allElectronicInformationGainOri.dot", 'w') as f:
    f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f)

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))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

说明
运行程序之后会生成一个.dot的文件(在本案例中生成的文件为allElectronicInformationGainOri.dot)
通过安装Graphviz可以将.dot文件转换为可视化的决策树,具体操作方法为

  • 下载Graphviz可视化工具选择graphviz-2.38.zip文件下载解压到安装目录
  • Window系统PC右键我的电脑,点击属性–>高级系统设置–>环境变量–>选择系统变量中的Path点击编辑–>右侧新建–>填入Graphviz安装目录下bin文件夹的目录(eg:C:\Users\Peter\Desktop\graphviz-2.38\release\bin)
  • 设置好环境变量后打开cmd窗口输入dot -Tpng dot文件路径 -o 输出文件.png

本案例输出的决策树为
决策树

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/901543
推荐阅读
相关标签
  

闽ICP备14008679号