决策树分类器
本文关键词:决策树分类,由笔耕文化传播整理发布。
算法总结2—决策树分类器
数学基础:
树:树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
每个结点有零个或多个子结点;
每一个子结点只有一个父结点;
没有前驱的结点为根结点;
除了根结点外,每个子结点可以分为m个不相交的子树;
没有子节点的节点称为叶节点。
决策树分类器原理:
决策树是一颗树,要分类的样本从树根进入,在树的每个节点通过对样本的某种属性的判断选择不同的路径逐步下降到底,得出其所属类别。
例图:
为了建立一棵决策树,我们首先应向程序输入大量训练数据(包含所属类别的数据),程序将根据训练数据按某一算法自动生成决策树。
决策树生成算法:
为了构造决策树,算法首先创建一个根节点,然后通过分析训练数据,逐步选出适合的变量对数据进行拆分(即逐步构造上图中的非叶子节点。)
为了选择适合的变量对数据进行拆分,我们需要一个方法来评估一种拆分方案的好坏,其评估方法包括:
1) 基尼不纯度:
定义:基尼不存度是指来自集合的某种结果随机应用于集合中某一数据的预期误差。(如果集合中所有结果属于同一类,则误差为0)
使用:利用这一思想,我们可以将集合中每种类别的数据出现的次数除以数据总数计算相应概率,再将这些概率的乘积相加(所有概率两两相乘后在相加),,这样就会得到某一数据被随机分配到错误结果的总概率。
伪代码:
imp=0
for k1 in kinds
p1=count(k1) / total
for k2 in counts
if (k1==k2)continue
p2=count(k2) / total
imp+=p1*p2
ans=imp
(p1*p2是一个p1类别的数据被当作p2的概率)
2) 熵:在信息论中,熵代表的是集合的无序程度-----基本上就相当于我们在此处所说的集合的混杂程度。
熵的值是遍历所有结果后得到的pi*log2(pi)的和的绝对值
伪代码:
ent=0.0
for k in kinds
p=count(k) / total
ent=ent – p*log2(p) // 因为0
本文关键词:决策树分类,由笔耕文化传播整理发布。
本文编号:47204
本文链接:https://www.wllwen.com/wenshubaike/shangbiaozhuanli/47204.html