首页 > 搜索 > 贪心算法决策树,决策树基本概念及算法优缺点

贪心算法决策树,决策树基本概念及算法优缺点

互联网 2020-10-24 16:28:34
在线算命,八字测算命理
1. 什么是决策树

分类决策树模型是一种描述对实例进行分类的树形结构. 决策树由结点和有向边组成. 结点有两种类型: 内部结点和叶节点. 内部节点表示一个特征或属性, 叶节点表示一个类.决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型.

通过把实例从根节点排列到某个叶子节点来分类实例叶子节点为实例所属的分类树上每个节点说明了对实例的某个属性的测试, 节点的每个后继分支对应于该属性的一个可能值2.决策树结构决策树结构.png3.决策树种类

分类树--对离散变量做决策树

回归树--对连续变量做决策树

4.决策树算法(贪心算法)

有监督的学习

非参数学习算法

自顶向下递归方式构造决策树

在每一步选择中都采取在当前状态下最好/优的选择

决策树学习的算法通常是一个递归地选择最优特征, 并根据该特征对训练数据进行分割, 使得各个子数据集有一个最好的分类的过程.在决策树算法中,ID3基于信息增益作为属性选择的度量, C4.5基于信息增益作为属性选择的度量, CART基于基尼指数作为属性选择的度量

5.决策树学习过程特征选择决策树生成: 递归结构, 对应于模型的局部最优决策树剪枝: 缩小树结构规模, 缓解过拟合, 对应于模型的全局选择6.决策树优缺点

优点:(1)速度快: 计算量相对较小, 且容易转化成分类规则. 只要沿着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词.(2)准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则.(3)可以处理连续和种类字段(4)不需要任何领域知识和参数假设(5)适合高维数据缺点:(1)对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征(2)容易过拟合(3)忽略属性之间的相关性

5.2 决策树数学知识1.信息论:

若一事假有k种结果, 对应概率为P_i, 则此事件发生后所得到的信息量I为:\begin{split} I &= -(p_1*log_2(p_1) + p_2*log_2(p_2) + ... + p_k*log_2(p_k)) \\ &= - \sum_{i=1}^k{p_ilog_2p_i} \end{split}

2.熵:

给定包含关于某个目标概念的正反样例的样例集S, 那么S相对这个布尔型分类的熵为:Entropy(S) \equiv -(p_{\oplus} * log_2p_{\oplus}) - (p_{\ominus} * log_2p_{\ominus})其中p_{\oplus}代表正样例, p_{\ominus}代表反样例

3.条件熵:

假设随机变量(X,Y), 其联合分布概率为P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m则条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性, 其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望H(X|Y) = \sum_{i-1}^n p_iH(Y|X=x_i)

5.3 决策树算法Hunt

在Hunt算法中, 通过递归的方式建立决策树.

如果数据集D种所有的数据都属于一个类, 那么将该节点标记为节点.如果数据集D中包含属于多个类的训练数据, 那么选择一个属性将训练数据划分为较小的子集, 对于测试条件的每个输出, 创建一个子节点, 并根据测试结果将D种的记录分布到子节点中, 然后对每一个子节点重复1,2过程, 对子节点的子节点依然是递归地调用该算法, 直至最后停止.5.4 决策树算法ID31.分类系统信息熵

H(C) = \sum_{i=1}^n P(C_i)*log_2P(C_i)

2.条件熵3.信息增益Gain(S, A) 定义4.属性选择度量

使用信息增益, 选择最高信息增益的属性作为当前节点的测试属性

5.算法不足使用ID3算法构建决策树时, 若出现各属性值取值数分布偏差大的情况, 分类精度会大打折扣ID3算法本身并未给出处理连续数据的方法ID3算法不能处理带有缺失值的数据集, 故在算法挖掘之前需要对数据集中的缺失值进行预处理ID3算法只有树的生成, 所以该算法生成的树容易产生过拟合6.算法流程

ID3(Examples,Target_attribute,Attributes)

Examples即训练样例集. Target_attribute是这棵树要预测的目标属性. Attributes是除目标属性外供学习到的决策树测试的属性列表. 返回能正确分类给定Examples的决策树.

创建树的Root结点如果Examples都为正, 那么返回label=+的单节点树Root如果Examples都为负, 那么返回label=-的单节点树Root如果Attributes为空, 那么返回单节点树Root, label=Examples中最普通的Target_attribute值否则A ← Attributes中分类Examples能力最好*的属性7.算法Python实现Python实现熵的计算from math import logdef calcShanNonEnt(dataSet):numEntries = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1]if currentLabel not in labelCounts.keys():labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key])/numEntriesshannonEnt -= prob*log(prob,2)return shannonEnt# exampledataset = [[1],[2],[3],[3],]sne = calcShanNonEnt(dataset)print(sne)Sklearn.tree参数介绍及使用建议

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

# Examplesfrom sklearn.datasets import load_irisfrom sklearn.model_selection import cross_val_scorefrom sklearn.tree import DecisionTreeClassifierclf = DecisionTreeClassifier(random_state=0)iris = load_iris()cross_val_score(clf, iris.data, iris.target, cv=10)from sklearn.model_selection import train_test_splitX_train,X_test, y_train, y_test = train_test_split(iris.data,iris.target,test_size=0.3) res = clf.fit(X_train,y_train)pre = clf.predict(X_test)sco = clf.score(X_test, y_test)print(y_test)print(pre)print(sco)clf.apply(X_train)clf.apply(X_test)clf.decision_path(X_train)type(clf.decision_path(X_train))X_train.shapeclf.feature_importances_from sklearn.tree import DecisionTreeClassifierclf = DecisionTreeClassifier()clf.fit(X_train, y_train)clf.feature_importances_clf.get_params()clf.predict_log_proba(X_test)clf.predict_proba(X_test)DecisionTreeClassifier实例

限制决策树层数为4的DecisionTreeClassifier实例

from itertools import productimport numpy as npimport matplotlib.pyplot as pltfrom sklearn import datasetsfrom sklearn.tree import DecisionTreeClassifier# 使用iris数据iris = datasets.load_iris()X = iris.data[:, [0, 2]]y = iris.target# 训练模型, 限制树的最大深度为4clf = DecisionTreeClassifier(max_depth=4)clf.fit(X,y)# Plotx_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1xx, yy = np.meshgrid(np.arange(x_min, x_max, .1),np.arange(y_min, y_max, .1))Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])Z = Z.reshape(xx.shape)plt.contourf(xx, yy, Z, alpha=.4)plt.scatter(X[:, 0], X[:, 1], c=y, alpha=.8)plt.show()output_12_0.pngPlot the decision surfaces of ensembles of trees on the iris dataset

This plot compares the decision surfaces learned by a dcision tree classifier(first column), by a random forest classifier(second column), by an extra-trees classifier(third column) and by an AdaBoost classifier(fouth column).

print(__doc__)import numpy as npimport matplotlib.pyplot as pltfrom matplotlib.colors import ListedColormapfrom sklearn import clonefrom sklearn.datasets import load_irisfrom sklearn.ensemble import (RandomForestClassifier, ExtraTreesClassifier, AdaBoostClassifier)from sklearn.tree import DecisionTreeClassifier# Parametersn_classes = 3n_estimators = 30cmap = plt.cm.RdYlBuplot_step = 0.02plot_step_coarser = 0.5RANDOM_SEED = 13# Load datairis = load_iris()plot_idx = 1models = [DecisionTreeClassifier(max_depth=None), RandomForestClassifier(n_estimators=n_estimators), ExtraTreesClassifier(n_estimators=n_estimators), AdaBoostClassifier(DecisionTreeClassifier(max_depth=3), n_estimators=n_estimators)]for pair in ([0,1], [0,2], [2,3]):for model in models:# print(pair, model)# only take the two correspoding featuresX = iris.data[:, pair]y = iris.target# Shuffleidx = np.arange(X.shape[0])np.random.seed(RANDOM_SEED)np.random.shuffle(idx)X = X[idx]y = y[idx]# Standardizemean = X.mean(axis=0)std = X.std(axis=0)X = (X - mean) / std# Trainclf = clone(model)clf = model.fit(X, y)scores = clf.score(X, y)# Create a title for each column and the console by using str() and# slicing away useless parts of the stringmodel_title = str(type(model)).split(".")[-1][:-2][:-len('Classifier')]model_details = model_titleif hasattr(model, "estimators_"):model_details +=" with {} estimators".format(len(model.estimators_))print(model_details + " with features", pair, "has a score of", scores)plt.subplot(3, 4, plot_idx)if plot_idx
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多