机器学习之决策树(Decision Tree)及其Python代码实现

简介:   决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

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

  从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。


  例如,我们要对”是否要出去玩?“这样的问题进行决策的时候,通常会进行一系列的判断或者”子决策“:我们先看”OUTLOOK“,如果是天气是sunny,则我们再看空气湿度,如果是”humidity<70“(湿度小于70),那么就去玩,否则就不去玩;如果天气是overcast,那么就去玩,其他的节点可以不用判断;以此类推:

这里写图片描述

  一般地,一颗决策树包含一个根节点,若干个 内部节点;叶节点对应与决策结果,其他每个节点对应于一个属性测试;每个节点包含的样本集合根据属性测试的结果被划分到子节点中;根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树,其基本流程遵循简单且直观的”分而治之“的策略,如下所示:

这里写图片描述


  在建立决策树之前,我们必须先要学习一个非常重要的概念,那就是信息熵

  1948年,香农提出了 ”信息熵(entropy)“的概念。 一条信息的信息量大小和它的不确定性有直接的关系,要搞清楚一件非常非常不确定的事情,或者是我们一无所知的事情,需要了解大量信息==>信息量的度量就等于不确定性的多少。

  信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第K类样本所占的比例为[Math Processing Error],则D的信息熵的定义为:

这里写图片描述

  变量的不确定性越大,信息熵也就越大。


决策树归纳算法 (ID3)

  信息获取量(Information Gain):Gain(A) = Info(D) - Infor_A(D),其中 Info(D)代表没有加入A节点的所获取的信息量,Infor_A(D)代表加入A节点后所获取的信息量。
  一般而言,信息获取量越大,则意味着使用属性A来进行划分所获得的”纯度提升“越大。因此,我们可以用信息获取量来进行决策树的划分属性的选择,著名的ID3决策树学习算法就是以信息获取量为准则来选择划分属性的。

这里写图片描述

以上图中为例,

这里写图片描述
这里写图片描述

由上可得Gain(age) = Info(D) - Infor_A(D)=0.940-0.694=0.246。

类似,Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048;

因为Gain(age)> Gain(student)>Gain(credit_rating)>Gain(income),所以,选择age作为第一个根节点。

这里写图片描述

重复以上步骤即可得出结论。


示例Python代码如下:

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'/home/zhoumiao/MachineLearning/01decisiontree/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[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、C4.5: Quinlan
2、Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)

共同点:都是贪心算法,自上而下(Top-down approach)

区别:属性选择度量方法不同: C4.5 (gain ratio), CART(gini index), ID3 (Information Gain)

  划分数据集的最大原则是:使无序的数据变的有序。如果一个训练数据中有20个特征,那么选取哪个做划分依据?这就必须采用量化的方法来判断,量化划分方法有多重,其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法,其中C4.5和CART两种算法从ID3算法中衍生而来。

  CART和C4.5支持数据特征为连续分布时的处理,主要通过使用二元切分来处理连续型变量,即求一个特定的值-分裂值:特征值大于分裂值就走左子树,或者就走右子树。这个分裂值的选取的原则是使得划分后的子树中的“混乱程度”降低,具体到C4.5和CART算法则有不同的定义方式。

  ID3算法由Ross Quinlan发明,建立在“奥卡姆剃刀”的基础上:越是小型的决策树越优于大的决策树(be simple简单理论)。ID3算法中根据信息论的信息增益评估和选择特征,每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集,没有剪枝的过程,为了去除过度数据匹配的问题,可通过裁剪合并相邻的无法产生大量信息增益的叶子节点(例如设置信息增益阀值)。使用信息增益的话其实是有一个缺点,那就是它偏向于具有大量值的属性–就是说在训练集中,某个属性所取的不同值的个数越多,那么越有可能拿它来作为分裂属性,而这样做有时候是没有意义的,另外ID3不能处理连续分布的数据特征,于是就有了C4.5算法。CART算法也支持连续分布的数据特征。

  C4.5是ID3的一个改进算法,继承了ID3算法的优点。C4.5算法用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝;能够完成对连续属性的离散化处理;能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高;但效率低,因树构造过程中,需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描,C4.5只适合于能够驻留于内存的数据集。

这里写图片描述
这里写图片描述

  CART算法的全称是Classification And Regression Tree,采用的是Gini指数(选Gini指数最小的特征s)作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息,但其生成的决策树分支较大,规模较大。为了简化决策树的规模,提高生成决策树的效率,就出现了根据GINI系数来选择测试属性的决策树算法CART。


关于剪枝(避免过拟合(overfitting))

  在实际构造决策树时,通常要进行剪枝,这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:

先剪枝:在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。

后剪枝:先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。


决策树的优缺点

优点:直观,便于理解,小规模数据集有效

缺点:1.处理连续变量不好;
   2.类别较多时,错误增加的比较快;
   3.可规模性一般。


参考: 机器学习经典算法详解及Python实现–决策树(Decision Tree)

参考: <<统计学习方法— 李航>>


机器学习系列之机器学习之Validation(验证,模型选择)

机器学习系列之机器学习之Logistic回归(逻辑蒂斯回归)

相关文章
|
4月前
|
机器学习/深度学习 算法 Python
机器学习特征筛选:向后淘汰法原理与Python实现
向后淘汰法(Backward Elimination)是机器学习中一种重要的特征选择技术,通过系统性地移除对模型贡献较小的特征,以提高模型性能和可解释性。该方法从完整特征集出发,逐步剔除不重要的特征,最终保留最具影响力的变量子集。其优势包括提升模型简洁性和性能,减少过拟合,降低计算复杂度。然而,该方法在高维特征空间中计算成本较高,且可能陷入局部最优解。适用于线性回归、逻辑回归等统计学习模型。
174 7
|
2月前
|
机器学习/深度学习 人工智能 算法
Scikit-learn:Python机器学习的瑞士军刀
想要快速入门机器学习但被复杂算法吓退?本文详解Scikit-learn如何让您无需深厚数学背景也能构建强大AI模型。从数据预处理到模型评估,从垃圾邮件过滤到信用风险评估,通过实用案例和直观图表,带您掌握这把Python机器学习的'瑞士军刀'。无论您是AI新手还是经验丰富的数据科学家,都能从中获取将理论转化为实际应用的关键技巧。了解Scikit-learn与大语言模型的最新集成方式,抢先掌握机器学习的未来发展方向!
515 12
Scikit-learn:Python机器学习的瑞士军刀
|
4月前
|
机器学习/深度学习 数据可视化 TensorFlow
Python 高级编程与实战:深入理解数据科学与机器学习
本文深入探讨了Python在数据科学与机器学习中的应用,介绍了pandas、numpy、matplotlib等数据科学工具,以及scikit-learn、tensorflow、keras等机器学习库。通过实战项目,如数据可视化和鸢尾花数据集分类,帮助读者掌握这些技术。最后提供了进一步学习资源,助力提升Python编程技能。
|
4月前
|
机器学习/深度学习 数据可视化 算法
Python 高级编程与实战:深入理解数据科学与机器学习
在前几篇文章中,我们探讨了 Python 的基础语法、面向对象编程、函数式编程、元编程、性能优化和调试技巧。本文将深入探讨 Python 在数据科学和机器学习中的应用,并通过实战项目帮助你掌握这些技术。
|
5月前
|
机器学习/深度学习 数据可视化 算法
Python与机器学习:使用Scikit-learn进行数据建模
本文介绍如何使用Python和Scikit-learn进行机器学习数据建模。首先,通过鸢尾花数据集演示数据准备、可视化和预处理步骤。接着,构建并评估K近邻(KNN)模型,展示超参数调优方法。最后,比较KNN、随机森林和支持向量机(SVM)等模型的性能,帮助读者掌握基础的机器学习建模技巧,并展望未来结合深度学习框架的发展方向。
189 9
Python与机器学习:使用Scikit-learn进行数据建模
|
机器学习/深度学习 存储 搜索推荐
利用机器学习算法改善电商推荐系统的效率
电商行业日益竞争激烈,提升用户体验成为关键。本文将探讨如何利用机器学习算法优化电商推荐系统,通过分析用户行为数据和商品信息,实现个性化推荐,从而提高推荐效率和准确性。
377 14
|
机器学习/深度学习 算法 数据可视化
实现机器学习算法时,特征选择是非常重要的一步,你有哪些推荐的方法?
实现机器学习算法时,特征选择是非常重要的一步,你有哪些推荐的方法?
290 1
|
机器学习/深度学习 算法 搜索推荐
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
|
机器学习/深度学习 数据采集 算法
解码癌症预测的密码:可解释性机器学习算法SHAP揭示XGBoost模型的预测机制
解码癌症预测的密码:可解释性机器学习算法SHAP揭示XGBoost模型的预测机制
631 0
|
机器学习/深度学习 数据采集 监控
机器学习-特征选择:如何使用递归特征消除算法自动筛选出最优特征?
机器学习-特征选择:如何使用递归特征消除算法自动筛选出最优特征?
1431 0

热门文章

最新文章

推荐镜像

更多