机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表某个可能的属性值,而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术,可以用于分析数据,同样也可以用来作预测。

简介

决策论中 (如风险管理),决策树(Decision tree)由一个决策图和可能的结果(包括资源成本和风险)组成, 用来创建到达目标的规划。决策树建立并用来辅助决策,是一种特殊的树结构。决策树是一个利用像树一样的图形或决策模型的决策支持工具,包括随机事件结果,资源代价和实用性。它是一个算法显示的方法。决策树经常在运筹学中使用,特别是在决策分析中,它帮助确定一个能最可能达到目标的策略。如果在实际中,决策不得不在没有完备知识的情况下被在线采用,一个决策树应该平行概率模型作为最佳的选择模型或在线选择模型算法。决策树的另一个使用是作为计算条件概率的描述性手段。

信息论

克劳德·艾尔伍德·香农(Claude Elwood Shannon ,1916年4月30日—2001年2月24日)美国数学家、信息论的创始人。

信息量

信息量在是作为信息“多少”的度量,这里的信息就是你理解的信息,比如一条新闻,考试答案等等。假设我们听到了两件事,分别如下:

  • 事件A:巴西队进入了2018世界杯决赛圈。
  • 事件B:中国队进入了2018世界杯决赛圈。

仅凭直觉来说,事件B的信息量比事件A的信息量要大。究其原因,是因为事件A发生的概率很大,事件B发生的概率很小。所以当越不可能的事件发生了,我们获取到的信息量就越大。越可能发生的事件发生了,我们获取到的信息量就越小。那么:

  • 信息量和事件发生的概率相关,事件发生的概率越低,传递的信息量越大
  • 信息量应当是非负的,必然发生的事件的信息量为零(必然事件是必然发生的,所以没有信息量。几乎不可能事件一旦发生,具有近乎无穷大的信息量)
  • 两个事件的信息量可以相加,并且两个独立事件的联合信息量应该是他们各自信息量的和

如已知事件Xi已发生,则表示Xi所含有或所提供的信息量:

如果是以2为底数,单位是bit;如果以e为底数,单位是nat;如果以10为底数,单位是det

信息熵

信息熵(Entropy)是接受信息量的平均值,用于确定信息的不确定程度,是随机变量的均值。信息熵越大,信息就越凌乱或传输的信息越多, 信息熵的处理信息是一个让信息的熵减少的过程。

假设X是一个离散的随机变量,且它的取值范围为{x_1, x_1, …, x_n},每一种取到的概率分别是 {p_1,p_1,…,p_n},那么 X 的熵定义为:

信息增益

信息熵表示的是不确定度。均匀分布时,不确定度最大,此时熵就最大。当选择某个特征对数据集进行分类时,分类后的数据集信息熵会比分类前的小,其差值表示为信息增益。信息增益(Kullback-Leibler divergence)用于度量属性A对降低样本集合X熵的贡献大小。信息增益可以衡量某个特征对分类结果的影响大小。信息增益越大,越适用对X进行分析。

ID3算法实现

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
from math import log
import operator

#创建数据集
def createData():
dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [
1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
labels = ['no surfacing', 'flippers']
return dataSet, labels

#计算信息熵
def calcShannonEnt(dataSet):
dataSetLen = len(dataSet)
labelsCount = {}
for everydata in dataSet:
currentLabel = everydata[-1]
if currentLabel not in labelsCount.keys():
labelsCount[currentLabel] = 0
labelsCount[currentLabel] += 1
ShannonEnt = 0.0
for key in labelsCount:
prob = float(labelsCount[key])/dataSetLen
ShannonEnt -= prob*log(prob, 2)
return ShannonEnt

#切分数据集
#dataDat表示待划分的数据集,axis表示划分数据集的特征,value表示需要返回的特征的值
def spliDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet

#选择最佳特征切分数据集
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0])-1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0.0
for value in uniqueVals:
subDataSet = spliDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob*calcShannonEnt(subDataSet)
infoGain = baseEntropy-newEntropy
if(infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature

笔记

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
62
63
64
65
#python中的for循环
>>> for x, y in [(1, 1), (2, 4), (3, 9)]:
print(x,y)
1
4
9
>>> for x, y in enumerate(['a', 'b', 'c']):
print(x, y)
a
b
c
1.列出110的平方列表
L=[]
for x in range(1,11):
L.append(x*x)
print(L)
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
#python提供了更简便的方法处理这个需求

>>> [x*x for x in range(1,11)]
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
2.添加判断条件

只取列表中的偶数

>>> [x*x for x in range(1,11) if x%2==0]
[4, 16, 36, 64, 100]
3.多个for同时判断

>>> [m+n for m in 'ABC' for n in'abc']
['Aa', 'Ab', 'Ac', 'Ba', 'Bb', 'Bc', 'Ca', 'Cb', 'Cc']

#Python list 中的冒号
[m : ] 代表列表中的第m+1项到最后一项
[ : n] 代表列表中的第一项到第n项

m = 3
n = 6

aa = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a = aa[m : ]
b = aa[ : n]
c = aa[m : n]

print(a)
print(b)
print(c)

[3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5]
[3, 4, 5]
双冒号的情况
list[start:end:step]
start:起始位置 end:结束位置 step:步长
>>> range(100)[20:30:2]
[20, 22, 24, 26, 28]

#extend()与append()方法的不同
>>>a=[1,2,3]
>>>b=[4,5,6]
>>>a.append(b)
>>>a
[1,2,3,[4,5,6]]
>>>a.extend(b)
[1,2,3,4,5,6]

参考文档

sklearn决策树可视化

scikit-learn 中决策树的可视化需要安装 graphviz

请不要使用这种方式否则会有报错

1
sudo pip install graphviz

正确方式请到graphviz下载对应版本并解压包运行以下命令

1
2
3
./configure
make
make install

关于源代码编译安装程序的流程

方法一

export_graphviz 将树导出为 Graphviz 格式

1
2
3
4
5
6
7
8
9
from sklearn import tree
from sklearn.datasets import load_iris
#载入sklearn中自带的数据Iris,构造决策树
iris=load_iris()
clf=tree.DecisionTreeClassifier()
clf=clf.fit(iris.data,iris.target)
#训练完成后,我们可以用 export_graphviz 将树导出为 Graphviz 格式
with open("iris.dot", 'w') as f:
f = tree.export_graphviz(clf, out_file=f)

此时已经在本地生成了 iris.dot 文件,在命令行输入 dot -Tpdf iris.dot -o iris.pdf 生成决策树的PDF可视化文件,打开 iris.pdf就能够看到生成的图片

方法二

使用 pydotplus 直接生成 iris.pdf

1
2
3
4
import pydotplus
dot_data=tree.export_graphviz(clf,out_file=None)
graph=pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf('iris_2.pdf')

方法三

使用 pydotplus 直接生成 iris.pdf

1
2
3
4
5
6
7
8
9
10
11
from IPython.display import Image  
dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())
dot_data = tree.export_graphviz(clf, out_file=None,filled=True)
graph = pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())

相关链接

ywtail`s blog

sklearn决策树可视化

One-Hot Encoding

相关链接

https://blog.csdn.net/pipisorry/article/details/61193868

https://www.cnblogs.com/wxshi/p/8645600.html

one hot编码是将类别变量转换为机器学习算法易于利用的一种形式的过程。

one-hot编码是N位状态寄存器为N个状态进行编码的方式

使用one-hot编码,将离散特征的取值扩展到了欧式空间,离散特征的某个取值就对应欧式空间的某个点。特征之间距离的计算或相似度的计算是非常重要的,而我们常用的距离或相似度的计算都是在欧式空间的相似度计算

数据归一化

https://segmentfault.com/a/1190000010300976

相关链接

https://www.biaodianfu.com/decision-tree.html