1、监督学习--分类--决策树
0、
监督学习Supervised Learning;分类:Classification
1、什么是决策树/判定树(decision tree)?
判定树是一个类似于流程图的树结构:其中,每个内部结点表示在一个属性上的测试,每个分支代表一个属性输出,而每个叶子结点代表类或类分布。树的最顶点是根结点。
e.g.
2、构造决策树的基本算法
2.1 熵(entrogy)
1948年,香农提出“信息熵”概念来度量信息和抽象:一条信息的信息量的大小和它的不确定性有直接的关系,即想要搞清楚一件不确定的事情 or 一无所知的事情,那么是需要了解大量信息的 < === > 信息量的度量等于不确定性的多少
e.g.
在对球队一无所知的情况下,猜测世界杯冠军,需要猜测多少次? 每支球队的夺冠几率是不相等的
设可发生事件的概率为P(x)
那么信息熵就等于 H(X)=-\sum_x P(x)log_2 [P(x)]
表达的含义就是:变量的不确定性越大,熵也就越大
PS:采用比特作为单位
2.2 决策树归纳算法
2.2.1 ID3算法
ID3算法是由J.Ross.Quinlan在1970-1980间提出的
选择属性判断结点有多种度量标准,其中一种叫信息获取量(information gain):Gain(A) = Info(D) - Info_A(D),假设属性A,其信息获取量等于没有A的原始信息量与使用A划分的信息量的差值,即通过属性A来作为节点分类获取多少信息。
e.g.
Info(D) = -买电脑的概率 - 不买电脑的概率 = - 9/14*log_2(9/14) - 5/14*log_2(5/14) = 0.940 bits
采用age作为属性A,那么:
Info_age(D) = Info_age=youth(D) + Info_age=middle_aged(D) + Info_age=senior(D)
= 5/14 * ( - 2/5*log_2(2/5) - 3/5*log_2(3/5) ) + 4/14 * ( - 4/4*log_2(4/4) - 0/4*log_2(0/4) ) + 5/14 * ( - 3/5*log_2(3/5) - 2/5*log_2(2/5) )
=0.694 bits
Gain(age) = Info(D) - Info_age(D) = 0.940 - 0.694 = 0.246 bits
同样地,
Gain(income) = 0.029
Gain(student) = 0.151
Gain(credit_rating) = 0.048
比较所有信息获取量,选取最大的作为树的根结点,该示例中Gain(age)最大,age作为根结点;
以此类推,直到树构建完毕(新的根结点需要对Gain进行重新计算)
算法步骤:
- 树以代表训练样本的单个结点开始(步骤1)。
- 如果样本都在同一个类,则该结点成为树叶,并用该类标号(步骤2 和3)。
- 否则,算法使用称为信息增益的基于熵的度量作为启发信息,选择能够最好地将样本分类的属性(步骤6)。该属性成为该结点的“测试”或“判定”属性(步骤7)。在算法的该版本中,
- 所有的属性都是分类的,即离散值。连续属性必须离散化。
- 对测试属性的每个已知的值,创建一个分枝,并据此划分样本(步骤8-10)。
- 算法使用同样的过程,递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上,就不必该结点的任何后代上考虑它(步骤13)。
- 递归划分步骤仅当下列条件之一成立停止:
- (a) 给定结点的所有样本属于同一类(步骤2 和3)。
- (b) 没有剩余属性可以用来进一步划分样本(步骤4)。在此情况下,使用多数表决(步骤5)。
- 这涉及将给定的结点转换成树叶,并用样本中的多数所在的类标记它。替换地,可以存放结
- 点样本的类分布。
- (c) 分枝
- test_attribute = a i 没有样本(步骤11)。在这种情况下,以 samples 中的多数类
- 创建一个树叶(步骤12)
2.2.2 其他算法
C4.5:也是由J.Ross.Quinlan提出
CART:Classification and Regression Trees,由L. Breiman,J. Friedman,R. Olshen,C. Stone等人提出
共同点:都是贪心算法,自上而下(Top-down approach)
区别:属性选择度量方法不同。C4.5 采用gain ratio,CART采用gini index,ID3采用informatica gain
2.3 如果处理连续性变量的属性?
可以将连续性变量变成离散化的属性,比如age分为70<=,>70两类
3、剪枝(避免overfitting)
overfitting:树的叶子太多太大,那么就可能会导致在训练集上表现很好(因为情况分的很细致),测试集上可能表现的不佳
3.1 先剪枝:分类分到给定阈值(类的纯度),就不在往下增长树的高度
3.2 后剪枝:先把树完全构建好,然后根据提前设定好的标准(比如类之间的纯度),将不符合要求的叶子去除
4、决策树的优缺点
4.1 优点:直观,便于理解,小规模数据集有效
4.2 缺点: 处理连续变量不好;类别较多时,错误增加的比较快;可规模性一般
5、Python应用
5.1 机器学习库:scikit-learn,基于Numpy, SciPy和matplotlib
5.2 库覆盖问题领域:分类(classification), 回归(regression), 聚类(clustering), 降维(dimensionality reduction), 模型选择(model selection), 预处理(preprocessing)
5.3 必要包安装:numpy, sciPy和matplotlib
5.4 银行信用自动评估系统--示例代码:针对之前买电脑的示例
# DictVectorizer将类类型的数据转换为整型数据
from sklearn.featrue_extraction import DictVectorizer
# 使用csv文件
from csv
from sklearn import preprocessing
# tree中包含decision tree函数
from sklearn import tree
# 文件读写流
from sklearn.externals.six import StringIO
# 打开训练集,读取第一行类型标签
# Read in the csv file and put feature in a list of dict and list of class label
allElectronicsData = open(r'D:/datasets/AllElectronics.csv','rb')
reader = csv.reader(allElectronicsData)
headers = reader.next()
print(headers)
featureList = []
labelList = []
# 循环读取样本
for row in reader:
labelList.append(row[len(row) - 1])
rowDict = {}
for i in range(1, len(row) - 1):
rowDict[header[i]] = row[i]
featureList.append(rowDict)
print(featureList)
# sklearn只处理数值型数据,因此要将其他类型的数据进行转换
# Vectorize feature
vec = DictVectorizer()
dummyX = vec.fit_transform(featureList).toarray()
print("dummyX: " + str(dummyX))
print(vec.get_feature_names())
# Vectorize class feature
lb = preprocessing.Labelbinarizer()
dummyY = lb.fit_transform(labelList)
print("dummyY: " + str(dummyY))
# Using decision tree fro classification
# clf = tree.DecisionTreeClassifier()
clf = tree.DecisionTreeClassifier(criterion='entropy')
clf = clf.fit(dummyX, dummyY)
print("clf: " + str(clf))
# Visulize model
# with open("allElectronicGiniOri.dot", 'w') as f:
with open("allElectronicInformationGainOri,dot.dot", 'w') as f:
# f = tree.export_graphviz(clf, out_file = 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
PS:材料学习自麦子学院,如有雷同,纯属学习