机器学习--决策树(ID3)算法及案例

机器学习--决策树(ID3)算法及案例

1基本原理

决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一般情况下，决策树由决策结点、分支路径和叶结点组成。在选择哪个属性作为结点的时候，采用信息论原理，计算信息增益，获得最大信息增益的属性就是最好的选择。信息增益是指原有数据集的熵减去按某个属性分类后数据集的熵所得的差值。然后采用递归的原则处理数据集，并得到了我们需要的决策树。

2算法流程

检测数据集中的每个子项是否属于同一分类：

If 是，则返回类别标签；

Else

计算信息增益，寻找划分数据集的最好特征

划分数据数据集

创建分支节点（叶结点或决策结点）

for 每个划分的子集

递归调用，并增加返回结果到分支节点中

return 分支结点

算法的基本思想可以概括为：

1）树以代表训练样本的根结点开始。

2）如果样本都在同一个类．则该结点成为树叶，并记录该类。

3）否则，算法选择最有分类能力的属性作为决策树的当前结点．

4 ）根据当前决策结点属性取值的不同，将训练样本根据该属性的值分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。一旦一个属性只出现在一个结点上，就不必在该结点的任何后代考虑它，直接标记类别。

5）递归划分步骤仅当下列条件之一成立时停止：

①给定结点的所有样本属于同一类。

②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布[这个主要可以用来剪枝]。

③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类生成叶子节点。

算法中2)步所指的最优分类能力的属性。这个属性的选择是本算法种的关键点，分裂属性的选择直接关系到此算法的优劣。

一般来说可以用比较信息增益和信息增益率的方式来进行。

其中信息增益的概念又会牵扯出熵的概念。熵的概念是香农在研究信息量方面的提出的。它的计算公式是：

Info(D)=-p1log(p1)/log(2.0)-p2log(p2)/log(2.0)-p3log(p3)/log(2.0)+...-pNlog(pN) /log(2.0) (其中N表示所有的不同类别)

而信息增益为：

Gain(A)=Info(D)-Info(Da) 其中Info(Da)数据集在属性A的情况下的信息量(熵)。

3算法的特点

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。

缺点：可能会产生过度匹配问题

适用数据范围：数值型和标称型。

4python代码实现

1、创建初始数据集，用于测试

######################################

#功能：创建数据集

#输入变量：空

#输出变量：data_set, labels 数据集，标签

######################################

def create_data_set():

data_set = [[1, 1, 'yes'],

[1, 1, 'yes'],

[1, 0, 'no'],

[0, 1, 'no'],

[0, 1, 'no']] # 数据集最后一列表示叶结点，也称类别标签labels = ['no surfacing', 'flippers'] # 表示决策结点，也称特征标签return data_set, labels

2、计算给定数据集的信息熵

#############################

#功能：计算信息熵

#输入变量：data_set 数据集

#输出变量：shannon_ent 信息熵

#############################

def calc_shannon_ent(data_set):

num_entries = len(data_set)

label_counts = {}

for feat_vec in data_set:

current_label = feat_vec[-1]

# get相当于一条if...else...语句

# 如果参数current_label不在字典中则返回参数0，

# 如果current_label在字典中则返回current_label对应的value值label_counts[current_label] = label_counts.get(current_label, 0) + 1 shannon_ent = 0.0

for key in label_counts:

prob = float(label_counts[key])/num_entries

shannon_ent -= prob*log(prob, 2)

return shannon_ent

3、按照给定特征划分数据集。分类算法除了需要测量信息熵，还需要划分数据集，这就需要对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

#################################

#功能：划分数据集

#输入变量：data_set, axis, value

# 数据集，数据集的特征，特征的值

#输出变量：ret_data_set, 划分后的数据集

#################################

def split_data_set(data_set, axis, value):

ret_data_set = []

for feat_vec in data_set:

if feat_vec[axis] == value:

# 把axis特征位置之前和之后的特征值切出来

# 没有使用del函数的原因是，del会改变原始数据

reduced_feat_vec = feat_vec[:axis]

reduced_feat_vec.extend(feat_vec[axis+1:])

ret_data_set.append(reduced_feat_vec)

return ret_data_set

4、遍历整个数据集，循环划分数据并计算信息熵，通过计算最大信息增益来找到最好的特征划分方式。

具体做法是，遍历当前特征中的所有唯一属性值，对每个特征划分一次数据集，然后计算数据集的新熵值，并对所有唯一特征值得到的熵求和。最后用所求的和值与原始信息熵相减，计算寻找最大信息增益。

######################################

#功能：选择最好的数据集划分方式

#输入变量：data_set 待划分的数据集

#输出变量：best_feature 计算得出最好的划分数据集的特征

######################################

def choose_best_feature_to_split(data_set):

num_features = len(data_set[0]) - 1 # 最后一个是类别标签，所以特征属性长度为总长度减1

base_entropy = calc_shannon_ent(data_set) # 计算数据集原始信息熵best_info_gain = 0.0

best_feature = -1

for i in xrange(num_features):

# feat_vec[i]代表第i列的特征值，在for循环获取这一列的所有值feat_list = [feat_vec[i] for feat_vec in data_set]

unique_vals = set(feat_list) # set函数得到的是一个无序不重复数

据集

new_entropy = 0.0

# 计算每种划分方式的信息熵

for value in unique_vals:

sub_data_set = split_data_set(data_set, i, value)

prob = len(sub_data_set)/float(len(data_set))

new_entropy += prob*calc_shannon_ent(sub_data_set)

info_gain = base_entropy - new_entropy

if info_gain > best_info_gain:

best_info_gain = info_gain

best_feature = i

return best_feature

5递归构建决策树

工作原理：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

递归结束条件是：第一、所有的类别标签（叶结点）完全相同。第二、使用完了所有的特征，仍然不能将数据集划分成仅包含唯一类别的分组，则挑选出次数最多的类别作为返回值。

######################################

#功能：多数表决分类

#输入变量：class_list 所有数据的标签数组

#输出变量：sorted_class_count[0][0] 出现次数最多的分类名称

######################################

def majority_vote_sort(class_list):

class_count = {}

for vote in class_list:

class_count[vote] = class_count.get(vote, 0) + 1

# items以列表方式返回字典中的键值对，iteritems以迭代器对象返回键值对，而键值对以元组方式存储，即这种方式[(), ()]

# operator.itemgetter(0)获取对象的第0个域的值，即返回的是key值# operator.itemgetter(1)获取对象的第1个域的值，即返回的是value 值

# operator.itemgetter定义了一个函数，通过该函数作用到对象上才能获取值

# reverse=True是按降序排序

sorted_class_count = sorted(class_count.iteritems(),

key=operator.itemgetter(1), reverse=True)

return sorted_class_count[0][0]

######################################

#功能：创建数

#输入变量：data_set, labels 待分类数据集，标签

#输出变量：my_tree 决策树

######################################

def create_tree(data_set, labels):

class_list = [example[-1] for example in data_set]

# 判断类别标签是否完全相同

# count()是列表内置的方法，可以统计某个元素在列表中出现的次数if class_list.count(class_list[0]) == len(class_list):

return class_list[0]

# 遍历完所有特征时返回出现次数最多的

if len(data_set[0]) == 1:

return majority_vote_sort(class_list)

best_feat = choose_best_feature_to_split(data_set)

best_feat_label = labels[best_feat]

my_tree = {best_feat_label: {}}

del(labels[best_feat])

# 得到列表包含的所有属性值

feat_values = [example[best_feat] for example in data_set]

unique_vals = set(feat_values)

for value in unique_vals:

sub_labels = labels[:] # :复制特征标签，为了保证循环调用函数create_tree()不改变原始的内容

ret_data_set = split_data_set(data_set, best_feat, value)

my_tree[best_feat_label][value] = create_tree(ret_data_set, sub_labels) return my_tree

6测试代码

def main():

my_data, my_labels = create_data_set()

#my_data[0][-1] = 'maybe'

print 'my_data=', my_data

print 'my_labels=', my_labels

shannon_ent = calc_shannon_ent(my_data)

print 'shannon_ent=', shannon_ent

ret_data_set = split_data_set(my_data, 1, 1) # 由第1个特征且特征值为1的数据集划分出来

print 'ret_data_set=', ret_data_set

best_feature = choose_best_feature_to_split(my_data)

print 'best_feature=', best_feature

my_tree = create_tree(my_data, my_labels)

print 'my_tree=', my_tree

if __name__ == '__main__':

main()

在进行案例分析前，先对决策树算法的分类函数进行测试。考虑到构造决策树非常耗时，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。这就需要利用python模块pickle序列化对象将决策树分类算法保存在磁盘中，并在需要的时候读取出来。

1、测试决策树分类算法性能

######################################

#功能：决策树的分类函数

#输入变量：input_tree, feat_labels, test_vec

# 决策树，分类标签，测试数据

#输出变量：class_label 类标签

######################################

def classify(input_tree, feat_labels, test_vec):

first_str = input_tree.keys()[0]

second_dict = input_tree[first_str]

class_label = -1

# index方法用于查找当前列表中第一个匹配first_str变量的索引feat_index = feat_labels.index(first_str)

for key in second_dict.keys():

if test_vec[feat_index] == key:

if type(second_dict[key]).__name__ == 'dict':

class_label = classify(second_dict[key], feat_labels, test_vec)

else:

class_label = second_dict[key]

return class_label

2、对决策树算法进行存储

######################################

#功能：将决策树存储到磁盘中

#输入变量：input_tree, filename 决策树，存储的文件名

######################################

def store_tree(input_tree, filename):

import pickle

fw = open(filename, 'w')

pickle.dump(input_tree, fw) # 序列化，将数据写入到文件中fw.close()

3、对决策树算法进行读取

######################################

#功能：从磁盘中读取决策树信息

#输入变量：filename 存储的文件名

######################################

def grab_tree(filename):

import pickle

fr = open(filename, 'r')

return pickle.load(fr) # 反序列化

4、代码测试

def main():

my_data, my_labels = create_data_set()

print 'my_data=', my_data

print 'my_labels=', my_labels

class_label = classify(my_tree, my_labels, [1, 1])

print 'class_label=', class_label

store_tree(my_tree, 'classifierStorage.txt')

tree = grab_tree('classifierStorage.txt')

print 'tree=', tree

if __name__ == '__main__':

main()

案例分析：使用决策树预测隐形眼镜类型

隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。而眼科医生需要从age、prescript、astigmatic和tearRate这四个方面对患者进行询问，以此来判断患者佩戴的镜片类型。利用决策树算法，我们甚至也可以帮助人们判断需要佩戴的镜片类型。

在构造决策树前，我们需要获取隐形眼镜数据集，从lenses.txt 文件读取。还需要获取特征属性（或者说决策树的决策结点），从代码输入。将数据集和特征属性代入决策树分类算法，就能构造出隐形眼镜决策树，沿着不同分支，我们可以得到不同患者需要的眼镜类型。

代码如下：

fr = open('lenses.txt', 'r')

lenses = [line.strip().split('\t') for line in fr.readlines()] lenses_labels = ['age', 'prescript', 'astigmatic', 'tearRate']

lenses_tree = create_tree(lenses, lenses_labels)

print 'lenses_tree=', lenses_tree

决策树算法研究及应用概要

决策树算法研究及应用? 王桂芹黄道 华东理工大学实验十五楼206室 摘要:信息论是数据挖掘技术的重要指导理论之一,是决策树算法实现的理论依据。决 策树算法是一种逼近离散值目标函数的方法,其实质是在学习的基础上,得到分类规则。本文简要介绍了信息论的基本原理,重点阐述基于信息论的决策树算法,分析了它们目前 主要的代表理论以及存在的问题,并用具体的事例来验证。 关键词:决策树算法分类应用 Study and Application in Decision Tree Algorithm WANG Guiqin HUANG Dao College of Information Science and Engineering, East China University of Science and Technology Abstract:The information theory is one of the basic theories of Data Mining,and also is the theoretical foundation of the Decision Tree Algorithm.Decision Tree Algorithm is a method to approach the discrete-valued objective function.The essential of the method is to obtain a clas-sification rule on the basis of example-based learning.An example is used to sustain the theory. Keywords:Decision Tree; Algorithm; Classification; Application 1 引言 决策树分类算法起源于概念学习系统CLS(Concept Learning System,然后发展 到ID3

人工智能之机器学习常见算法

人工智能之机器学习常见算法 摘要机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。这里小编为您总结一下常见的机器学习算法，以供您在工作和学习中参考。 机器学习的算法很多。很多时候困惑人们都是，很多算法是一类算法，而有些算法又是从其他算法中延伸出来的。这里，我们从两个方面来给大家介绍，第一个方面是学习的方式，第二个方面是算法的类似性。 学习方式 根据数据类型的不同，对一个问题的建模有不同的方式。在机器学习或者人工智能领域，人们首先会考虑算法的学习方式。在机器学习领域，有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法，这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。 监督式学习： 在监督式学习下，输入数据被称为训练数据，每组训练数据有一个明确的标识或结果，如对防垃圾邮件系统中垃圾邮件非垃圾邮件，对手写数字识别中的1，2，3，4等。在建立预测模型的时候，监督式学习建立一个学习过程，将预测结果与训练数据的实际结果进行比较，不断的调整预测模型，直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归（LogisTIc Regression）和反向传递神经网络（Back PropagaTIon Neural Network） 非监督式学习： 在非监督式学习中，数据并不被特别标识，学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means 算法。 半监督式学习： 在此学习方式下，输入数据部分被标识，部分没有被标识，这种学习模型可以用来进行预

决策树算法介绍(DOC)

3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，

数据挖掘决策树算法Java实现

import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.Iterator; //调试过程中发现4个错误，感谢宇宙无敌的调试工具——print //1、selectAtrribute中的一个数组下标出错 2、两个字符串相等的判断 //3、输入的数据有一个错误 4、selectAtrribute中最后一个循环忘记了i++ //决策树的树结点类 class TreeNode { String element; //该值为数据的属性名称 String value; //上一个分裂属性在此结点的值 LinkedHashSet childs; //结点的子结点，以有顺序的链式哈希集存储 public TreeNode() { this.element = null; this.value = null; this.childs = null; } public TreeNode(String value) { this.element = null; this.value = value; this.childs = null; } public String getElement() { return this.element; } public void setElement(String e) { this.element = e; } public String getValue() { return this.value; } public void setValue(String v) { this.value = v; } public LinkedHashSet getChilds() { return this.childs;

R语言与机器学习(2)决策树算法

算法二：决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于2.4cm 的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是virginica(图中黑色的分类)

我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的内在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。

数据挖掘——决策树分类算法 (1)

决策树分类算法 学号：20120311139 学生所在学院：软件工程学院学生姓名：葛强强 任课教师：汤亮 教师所在学院：软件工程学院2015年11月

12软件1班 决策树分类算法 葛强强 12软件1班 摘要：决策树方法是数据挖掘中一种重要的分类方法，决策树是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性的测试，其分支代表测试的结果，而树的每个 叶结点代表一个类别。通过决策树模型对一条记录进行分类，就是通过按照模型中属 性测试结果从根到叶找到一条路径，最后叶节点的属性值就是该记录的分类结果。 关键词：数据挖掘，分类，决策树 近年来，随着数据库和数据仓库技术的广泛应用以及计算机技术的快速发展，人们利用信息技术搜集数据的能力大幅度提高，大量数据库被用于商业管理、政府办公、科学研究和工程开发等。面对海量的存储数据，如何从中有效地发现有价值的信息或知识，是一项非常艰巨的任务。数据挖掘就是为了应对这种要求而产生并迅速发展起来的。数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用的信息，提取的知识表示为概念、规则、规律、模式等形式。 分类在数据挖掘中是一项非常重要的任务。 分类的目的是学会一个分类函数或分类模型，把数据库中的数据项映射到给定类别中的某个类别。分类可用于预测，预测的目的是从历史数据记录中自动推导出对给定数据的趋势描述，从而能对未来数据进行预测。分类算法最知名的是决策树方法，决策树是用于分类的一种树结构。 1决策树介绍 决策树（decisiontree）技术是用于分类和预测 的主要技术，决策树学习是一种典型的以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性判断从该节点向下的分支，在决策树的叶节点得到结论。所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。 把决策树当成一个布尔函数。函数的输入为物体或情况的一切属性（property），输出为”是”或“否”的决策值。在决策树中，每个树枝节点对应着一个有关某项属性的测试，每个树叶节点对应着一个布尔函数值，树中的每个分支，代表测试属性其中一个可能的值。 最为典型的决策树学习系统是ID3，它起源于概念学习系统CLS，最后又演化为能处理连续属性的C4．5（C5．0）等。它是一种指导的学习方法，该方法先根据训练子集形成决策树。如果该树不能对所有给出的训练子集正确分类，那么选择一些其它的训练子集加入到原来的子集中，重复该过程一直到时形成正确的决策集。当经过一批训练实例集的训练产生一棵决策树，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进行分类的时候，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。 决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3，C4．5，PUBLIC，

数据挖掘决策树算法概述

决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。本文以决策树为研究对象，主要研究内容有：首先介绍了数据挖掘的历史、现状、理论和过程，然后详细介绍了三种决策树算法，包括其概念、形式模型和优略性，并通过实例对其进行了分析研究 目录 一、引言 (1) 二、数据挖掘 (2) (一)概念 (2) (二)数据挖掘的起源 (2) (三)数据挖掘的对象 (3) (四)数据挖掘的任务 (3) (五)数据挖掘的过程 (3) (六)数据挖掘的常用方法 (3) (七)数据挖掘的应用 (5) 三、决策树算法介绍 (5) (一)归纳学习 (5) (二)分类算法概述 (5) (三)决策树学习算法 (6) 1、决策树描述 (7) 2、决策树的类型 (8) 3、递归方式 (8) 4、决策树的构造算法 (8) 5、决策树的简化方法 (9) 6、决策树算法的讨论 (10) 四、ID3、C4.5和CART算法介绍 (10) (一)ID3学习算法 (11) 1、基本原理 (11) 2、ID3算法的形式化模型 (13) （二）C4.5算法 (14) （三）CART算法 (17) 1、CART算法理论 (17) 2、CART树的分支过程 (17) （四）算法比较 (19) 五、结论 (24) 参考文献...................................................................................... 错误！未定义书签。 致谢.............................................................................................. 错误！未定义书签。

机器学习 决策树(ID3)算法及案例

机器学习--决策树(ID3)算法及案例 1基本原理 决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一般情况下，决策树由决策结点、分支路径和叶结点组成。在选择哪个属性作为结点的时候，采用信息论原理，计算信息增益，获得最大信息增益的属性就是最好的选择。信息增益是指原有数据集的熵减去按某个属性分类后数据集的熵所得的差值。然后采用递归的原则处理数据集，并得到了我们需要的决策树。 2算法流程 检测数据集中的每个子项是否属于同一分类： If是，则返回类别标签； Else 计算信息增益，寻找划分数据集的最好特 征 划分数据数据集 创建分支节点（叶结点或决策结点）

for每个划分的子集 递归调用，并增加返回结果 到分支节点中 return分支结点 算法的基本思想可以概括为： 1）树以代表训练样本的根结点开始。 2）如果样本都在同一个类．则该结点成为树叶，并记录该类。 3）否则，算法选择最有分类能力的属性作为决策树的当前结点． 4）根据当前决策结点属性取值的不同，将训练样本根据该属性的值分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。一旦一个属性只出现在一个结点上，就不必在该结点的任何后代考虑它，直接标记类别。 5）递归划分步骤仅当下列条件之一成立时停止： ①给定结点的所有样本属于同一类。 ②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布[这个主要可以用来剪枝]。 ③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类生成叶子节点。 算法中2)步所指的最优分类能力的属性。这个属性的选择是本算法种的关键点，分裂属性的选择直接关系到此算法的优劣。 一般来说可以用比较信息增益和信息增益率的方式来进行。 其中信息增益的概念又会牵扯出熵的概念。熵的概念是香农在研究信息量方面的提出的。它的计算公式是：

生物数据挖掘-决策树实验报告

实验四决策树 一、实验目的 1.了解典型决策树算法 2.熟悉决策树算法的思路与步骤 3.掌握运用Matlab对数据集做决策树分析的方法 二、实验内容 1.运用Matlab对数据集做决策树分析 三、实验步骤 1.写出对决策树算法的理解 决策树方法是数据挖掘的重要方法之一，它是利用树形结构的特性来对数据进行分类的一种方法。决策树学习从一组无规则、无次序的事例中推理出有用的分类规则，是一种实例为基础的归纳学习算法。决策树首先利用训练数据集合生成一个测试函数，根据不同的权值建立树的分支，即叶子结点，在每个叶子节点下又建立层次结点和分支，如此重利生成决策树，然后对决策树进行剪树处理，最后把决策树转换成规则。决策树的最大优点是直观，以树状图的形式表现预测结果，而且这个结果可以进行解释。决策树主要用于聚类和分类方面的应用。 决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下分而治之的过程。 2.启动Matlab，运用Matlab对数据集进行决策树分析，写出算法名称、数据集名称、关键代码，记录实验过程，实验结果，并分析实验结果 (1)算法名称: ID3算法 ID3算法是最经典的决策树分类算法。ID3算法基于信息熵来选择最佳的测试属性，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少个不同的取值就将样本集划分为多少个子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。ID3算法根据信息论的理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的决策树。 ID3算法的具体流程如下： 1）对当前样本集合，计算所有属性的信息增益； 2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集； 3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。 (2)数据集名称：鸢尾花卉Iris数据集 选择了部分数据集来区分Iris Setosa（山鸢尾）及Iris Versicolour（杂色鸢尾）两个种类。

小晨精品06-机器学习_(决策树分类算法与应用)(优秀)

机器学习算法day04_决策树分类算法及应用课程大纲 课程目标： 1、理解决策树算法的核心思想 2、理解决策树算法的代码实现 3、掌握决策树算法的应用步骤：数据处理、建模、运算和结果判定

1. 决策树分类算法原理 1.1 概述 决策树（decision tree）——是一种被广泛使用的分类算法。 相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置 在实际应用中，对于探测式的知识发现，决策树更加适用 1.2 算法思想 通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话： 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 这个女孩的决策过程就是典型的分类树决策。 实质：通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见 假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑

上图完整表达了这个女孩决定是否见一个约会对象的策略，其中： ◆绿色节点表示判断条件 ◆橙色节点表示决策结果 ◆箭头表示在一个判断条件在不同情况下的决策路径 图中红色箭头表示了上面例子中女孩的决策过程。 这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。 决策树分类算法的关键就是根据“先验数据”构造一棵最佳的决策树，用以预测未知数据的类别 决策树：是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

完整word版,决策树算法总结

决策树研发二部

目录 1. 算法介绍 (1) 1.1.分支节点选取 (1) 1.2.构建树 (3) 1.3.剪枝 (10) 2. sk-learn中的使用 (12) 3. sk-learn中源码分析 (13)

1.算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1.分支节点选取 2.构建树 3.剪枝 1.1.分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 基尼系数：同上，也可以作为信息混乱程度的衡量指标。

有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。 #计算熵值 def entropy(dataSet): tNum = len(dataSet) print(tNum) #用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] #获取标签 if curL not in labels.keys(): labels[curL] = 0 #如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 #将标签记录个数加1 #此时labels中保存了所有标签和对应的个数 res = 0 #计算公式为-p*logp，p为标签出现概率 for node in labels: p = float(labels[node]) / tNum res -= p * log(p, 2) return res #计算基尼系数 def gini(dataSet): tNum = len(dataSet) print(tNum) # 用来保存标签对应的个数的，比如,男：6，女：5 labels = {} for node in dataSet: curL = node[-1] # 获取标签 if curL not in labels.keys(): labels[curL] = 0 # 如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 # 将标签记录个数加1 # 此时labels中保存了所有标签和对应的个数 res = 1

决策树算法总结

决策树决策树研发二部

目录 1. 算法介绍 (1) 1.1. 分支节点选取 (1) 1.2. 构建树 (3) 1.3. 剪枝 (10) 2. sk-learn 中的使用 (12) 3. sk-learn中源码分析 (13)

1. 算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作 为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对 ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1. 分支节点选取 2. 构建树 3. 剪枝 1.1. 分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 Entropy = -V p ” 基尼系数：同上，也可以作为信息混乱程度的衡量指标。 Gini = 1 - p： l-L

机器学习十大算法的每个算法的核心思想、工作原理、适用情况及优缺点

5-1简述机器学习十大算法的每个算法的核心思想、工作原理、适用情况及优缺点等。 1）C4.5算法： ID3算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定的测试属性。 C4.5算法核心思想是ID3算法，是ID3算法的改进，改进方面有： 1）用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2）在树构造过程中进行剪枝 3）能处理非离散的数据 4）能处理不完整的数据 C4.5算法优点：产生的分类规则易于理解，准确率较高。 缺点： 1)在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算 法的低效。 2)C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程 序无法运行。 2）K means 算法： 是一个简单的聚类算法，把n的对象根据他们的属性分为k个分割，k < n。算法的核心就是要优化失真函数J,使其收敛到局部最小值但不是全局最小值。 ，其中N为样本数，K是簇数，r nk b表示n属于第k个 簇，u k是第k个中心点的值。

然后求出最优的u k 优点：算法速度很快 缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。 3）朴素贝叶斯算法： 朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。算法的基础是概率问题，分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。朴素贝叶斯假设是约束性很强的假设，假设特征条件独立，但朴素贝叶斯算法简单，快速，具有较小的出错率。 在朴素贝叶斯的应用中，主要研究了电子邮件过滤以及文本分类研究。 4)K最近邻分类算法（KNN） 分类思想比较简单，从训练样本中找出K个与其最相近的样本，然后看这k个样本中哪个类别的样本多，则待判定的值（或说抽样）就属于这个类别。 缺点： 1）K值需要预先设定，而不能自适应 2）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法适用于对样本容量比较大的类域进行自动分类。 5)EM最大期望算法 EM算法是基于模型的聚类方法，是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。E步估计隐含变量，M步估计其他参数，交替将极值推向最大。 EM算法比K-means算法计算复杂，收敛也较慢，不适于大规模数据集和高维数据，但比K-means算法计算结果稳定、准确。EM经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。 6）PageRank算法 是google的页面排序算法，是基于从许多优质的网页链接过来的网页，必定还是优质网页的回归关系，来判定所有网页的重要性。（也就是说，一个人有着越多牛X朋友的人，他是牛X的概率就越大。） 优点： 完全独立于查询，只依赖于网页链接结构，可以离线计算。 缺点： 1）PageRank算法忽略了网页搜索的时效性。 2）旧网页排序很高，存在时间长，积累了大量的in-links，拥有最新资讯的新网页排名却很低，因为它们几乎没有in-links。

机器学习实验报告

决策树算法 一、决策树算法简介： 决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。其中决策树（Decision Tree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。 决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除、 决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan 提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。 本节将就ID3算法展开分析和实现。 ID3算法： ID3算法最早是由罗斯昆（J. Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。

机器学习算法总结_决策树(含代码)

第六章 提升算法 6.1 引言 当做重要决定时，大家可能都会考虑吸取多个专家而不是一个人的意见。机器学习处理问题时也是如此，这就是提升算法背后的思路，提升算法是对其它算法进行组合的一种方式，接下来我们将对提升算法，以及提升算法中最流行的一个算法AdaBoost 算法进行介绍，并对提升树以及简单的基于单层决策树的Adaboost 算法进行讨论。 提升方法是一种常用的统计学习方法，应用广泛且有效，在分类问题上，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。一个分类器在训练数据上能够获得比其他分类器更好的拟合，但是在训练数据外的数据集上却不能很好的拟合数据，这时就称为该分类器出现了过拟合（overfitting ）。提升算法能够有效地防止过拟合现象的发生。 图1 过拟合现象示意图 提升算法是一种为了拟合自适应基函数模型（adaptive basis-function models, ABM ）的贪心算法，自适应基函数模型可表达为： ()()01M m m m f X w w X φ==+∑ （6-1） 其中，m φ是一种分类算法或者回归算法，被称为弱分类器（weak learner ）或者基分类器（base learner ）。也可以表达为如下形式： 1()(;)M m m m f X b X βγ==∑ （6-2） 提升算法的目的是对以下公式的优化：

1 min (,())N i i f i L y f x =∑ （6-3） 其中，?(,)L y y 称为损失函数（loss function ），f 是ABM 模型。不同的损失函数有着不同 的性质，对应不同的提升算法，如表1所示。 将(2)式代入(3)式可得如下表达式： ,11min ,(;)m m N M i m i m i m L y x βγβφγ==?? ??? ∑∑ （6-4） 因为学习的是加法模型，如果能够从前向后，每一步只学习一个基分类器及其系数，那 么就可以简化优化的复杂度，具体推导过程如下所示： (),1 min ,(;)m m N i m i m i L y x βγβφγ=∑ （6-5） 表1 常见损失函数以及相应提升算法 名称 损失函数 导数 *f 算法 平方误差 21 (())2 i i y f x - ()i i y f x - []|i y x E L2Boosting 绝对误差 ()i i y f x - sgn(()) i i y f x - (|)i median y x Gradient boosting 指数损失 () exp ()i i y f x - () exp ()i i i y y f x -- 1 log 21i i ππ- AdaBoost 对数损失 ()log 1i i y f e -+ i i y π- 1 log 21i i ππ- LogitBoost 01 ()arg min (,(;))N i i i f X L y f x γ γ==∑ （6-6） 1,1 (,)argmin (,()(;))N m m i m i i i L y f x x βγ βγβφγ-==+∑ （6-7） 1()()(;)m m m m f X f X X βφγ-=+ （6-8） 算法不进行回溯对参数进行修改，因此该算法称为前向分步算法。 6.2 AdaBoost 算法 AdaBoost （Adaptive boosting ）算法，也称为自适应提升算法。训练数据中的每个样本，并赋予其一个权重，这些权重构成向量D 。一开始，这些权重都初始化为相等值，首先 在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。再次训练分类器的过程中，将会重新调整每个样本的权重，其中上一次分对的样本权重会降低，而上一次分错的样本权重会提高。

R语言-决策树算法

决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于2.4cm的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是virginica(图中黑色的分类) 我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的内在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 问题：我们如何确定起决定作用的划分变量。 我还是用鸢尾花的例子来说这个问题思考的必要性。使用不同的思考方式，我们不难发现下面的决策树也是可以把鸢尾花分成3类的。 为了找到决定性特征，划分出最佳结果，我们必须认真评估每个特征。通常划分的办法为信息增益和基尼不纯指数，对应的算法为C4.5和CART。 关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。 直接给出计算熵与信息增益的R代码： 1、计算给定数据集的熵 calcent<-function(data){ nument<-length(data[,1])