文档介绍：数据挖掘之经典算法 1 决策树算法机器学****中, 决策树是一个预测模型; 它代表的是对象属性值与对象值之间的一种映射关系。树中每个节点表示某个对象, 每个分叉路径则代表的某个可能的属性值, 而每个叶结点则对应具有上述属性值的子对象。决策树仅有单一输出; 若需要多个输出, 可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学****技术叫做决策树学****通俗说就是决策树。决策树学****也是数据挖掘中一个普通的方法。在这里, 每个决策树都表述了一种树型结构, 它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时, 递归过程就完成了。另外, 随机森林分类器将许多决策树结合起来以提升分类的正确率。决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。决策树的工作原理决策树一般都是自上而下的来生成的。选择分割的方法有多种,但是目的都是一致的,即对目标类尝试进行最佳的分割。从根节点到叶子节点都有一条路径,这条路径就是一条“规则”。决策树可以是二叉的,也可以是多叉的。对每个节点的衡量: 1) 通过该节点的记录数; 2) 如果是叶子节点的话,分类的路径; 3) 对叶子节点正确分类的比例。有些规则的效果可以比其他的一些规则要好。 Y YY YN NN N w 1 Tx≥0w 4 Tx≥0 w 3 Tx≥0 w 2 Tx≥0 二叉决策树框图 ID3 算法概念提取算法 CLS 1) 初始化参数 C={E} ,E 包括所有的例子,为根; 2) 如果 C 中的任一元素 e 同属于同一个决策类则创建一个叶子节点 YES 终止; 否则依启发式标准, 选择特征 F i ={V 1,V 2,V 3, ……,V n} 并创建判定节点, 划分 C 为互不相交的 N个集合 C 1,C 2,C 3, ……,C n; 3) 对任一个 C i 递归。 ID3 算法 1) 随机选择 C 的一个子集 W( 窗口); 2) 调用 CLS 生成 W 的分类树 DT( 强调的启发式标准在后); 3) 顺序扫描 C 搜集 DT 的意外( 即由 DT 无法确定的例子); 4) 组合 W 与已发现的意外,形成新的 W; 5) 重复 2)到 4) ,直到无例外为止。启发式标准: 只跟本身与其子树有关,采取信息理论用熵来量度。熵是选择事件时选择自由度的量度,其计算方法为: P=freq(C j ,S)/|S| ; INFO(S)=-SUM(P*LOG(P)) ; SUM() 函数是求 j从1到n 的和。 Gain(X)=Info(X)-Infox(X) ; Infox(X)=SUM( (|T i |/|T|)*Info(X) ; 为保证生成的决策树最小, ID3 算法在生成子树时, 选取使生成的子树的熵(即 Gain(S)) 最小的特征来生成子树。 ID3 算法对数据的要求: 1) 所有属性必须为离散量; 2) 所有的训练例的所有属性必须有一个明确的值; 3) 相同的因素必须得到相同的结论且训练例必须唯一。算法由于 ID3 算法在实际应用中存在一些问题,于是 Quilan 提出了算法,严格上说只能是 ID3 的一个改进算法。算法继承了 ID3 算法的优点,并在以下几方面对 ID3 算法进行了改进: 1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; 2) 在树构造过程中进行剪枝; 3) 能够完成对连续属性的离散化处理; 4) 能够对不完整数据进行处理。算法有如下优点: 产生的分类规则易于理解,准确率较高。算法有如下缺点: 在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外, 只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。分类决策树算法: 算法是机器学****算法中的一种分类决策树算法,其核心算法是 ID3 算法。分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树。决策树的各部分是: 根:学****的事例集; 枝:分类的判定条件; 叶:分好的各个类。对 ID3 算法的改进 1) 熵的改进,加上了子树的信息。 Split_Infox(X)= - SUM( (|T|/|T i |)*LOG(|T i |/|T|)) ; Gain ratio(X)= Gain(X)/Split _ Infox(X); 2) 在输入数据上的改进①因素属性的值可以是连续量, 对其排序并分成不同的