分类决策树分类1 .基本思想2 .决策树的特征3 .两股决策树算法和分类规则的生成4 .决策树分类算法5 .决策树属性的选择
决策树分类
数据分类的基本流程:
两步:
)1)针对确定了类别的数据集创建模型。 现在,用于创建模型的数据称为训练集,而训练集中的单个元组称为训练样本。
)2)使用创建的模型,将类未知的元组划分为某个类或几个类。
评价分类模型的标准:预测精度模型的建立速度和使用速度强壮性; 伸缩性; 可以说明。
1 .基本思想其基本算法为“贪婪”算法,采用自上而下的方式。 最初,所有数据都在根节点上,用所选属性递归分裂元组集合,分割成同一节点的数据属于同一类别,继续分裂节点数据,直到没有属性选择为止,形成决策树。
属性选择基于启发式规则或信息熵等统计度量。 对于每个选定的属性,所形成的数据组之间的差异必须最大。 一般选择的属性是分类属性,属性连续时需要离散化处理。
2 .决策树特征伸缩性好
分类速度比较快;
分类精度高
具有较快的学习速度
能够转换为容易理解的分类规则;
擅长处理非数值型数据
数据挖掘查询可以很容易地用于描述增强的决策树方法。
3 .生成二叉树决策树算法和分类规则二叉树CART算法的基本过程:
)1)开始将训练数据汇总到某个节点上。
)2)选择训练数据最佳分类的一个检测特征值进行数据分裂,进入下一节点。
当满足以下条件之一时,递归分裂停止: 没有能再分裂的特征,没有样品分裂的检测特征。
4 .决策树分类算法I D3算法
基本步骤:
输入:由离散值属性表示的训练样本samples; 候选属性的集合attribute_list。
输出:一棵决策树。
(1)创建节点n
)2) If samples都在同一个c类中,所以将n作为叶节点返回,用c类标记。
)3)如果If attribute_list为空,则将n作为叶节点返回,标记为samples中最常见的类。
(4)在attribute_list中选择具有最高信息增益的属性test_attribute; 标记节点n是test_attribute;
)5) For各test_attribute中的已知值ai形成从节点n到test_attribute=ai的条件的分支;
(6)将si作为samples中test_attribute=ai的样本的集合。
If si是空的Then和叶节点,被标记为samples中最常见的类;
Else将添加由gen_des_tree(si,attribute_list_test_attribute ) )返回的节点。
Quinlan在ID3算法的基础上发展出C4.5算法。
基本步骤:
)1)假设t为训练事例集。
)2)选择最能区分t中实例的属性。
)3)创建具有所选属性值的树节点。 创建节点的子链。 每个子链表示所选属性的唯一值。 使用子链中的值将实例进一步细分为子类。
(4)对于在步骤(3)中创建的每个子类,如果子类中的实例满足预定义标准,或者树中此路径的其馀可选属性集为空,则该子类将归类为沿着此决策路径的新实例如果子类不满足预定义标准,并且至少一个属性可以进一步细分树的路径,则将t作为当前子类的实例集合,然后返回步骤(2)。
该算法的终结树的一个路径的两种可能是:
)1)沿某个分支实例满足预定义标准的。
)2)没有继续树分裂过程的属性。
CART算法和C4.5算法的区别:
)1)无论属性是分类的还是数值的,CART总是执行数据的二元分裂。
)2) CART调用检测数据,支持生成的二叉树的修剪和泛化。 另一方面,C4.5算法只使用训练数据制作最终的树结构。
5 .决策树属性选择C4.5算法属性选择方法:
增益值最大的属性用于进一步细分树结构。
的信息增益计算方法:
将s作为训练样本的集合,其中每个样本的类标签是已知的。 假设有m个类,则集合s中c类的记录数为个、i=1、…、m。 指定样本分类所需的预期信息如下:
a的信息增益是
在实际应用中,首先计算每个属性的信息增益,并用得到的信息增益值对属性进行排序。