模糊决策树范文
模糊决策树范文（精选8篇）
模糊决策树 第1篇
数据挖掘是从大量数据中“挖掘”知识, 旨在从大量数据中提取隐藏的预测性信息, 发掘数据间潜在的模式, 找出某些被忽略的信息, 作为决策的依据。在网络的许多应用中数据是以流形式存在的[1]。传统的数据挖掘方法是基于静态数据库的频繁模式, 挖掘算法可以对数据库进行多次扫描, 多次查找等。然而, 数据流是大量连续到达、潜在无限的数据集合, 其特点是:数据高速到达, 数据流无法再现, 实时性要求高以及数据量无限增长等。因此, 传统的数据挖掘不适合对数据流的挖掘。在数据流挖掘研究中, 有许多经典算法, 譬如:Manku提出的Lossy Counting算法[2], Han提出基于FP-growth的FP-stream[3] 算法等。数据流常用的处理与分析方法可归纳为数据流频繁项集挖掘算法、分类挖掘算法和聚类挖掘算法[4]。但这些算法在处理数据流时不同程度地产生概念漂移现象[5], 在分类挖掘数据流时, 必须考虑数据流的变化特征, 要及时删除过时的类定义模式。 在聚类算法中, 数据流随着时间在不断地变化, 其隐含的聚类可能随时间的动态变化而导致聚类质量的降低。本文提出一种改进的基于概念自适应模糊决策树算法, 以解决数据挖掘中的概念漂移问题。
1 快速决策树算法及其性能分析
快速决策树算法[6] (very fast decision tree, VFDT) 的目标是通过已有的训练样本得出一个分类模型y=f (x) , 对新测试样本进行正确分类。VFDT是一种基于Hoeffding不等式[7], 并针对数据流挖掘环境建立分类决策树的方法, 它通过不断地将叶节点替换为分支节点, 而生成决策树, 其所研究的样本属性为离散属性。
1.1 快速决策树算法的过程
快速决策树算法过程如下:
(1) 快速决策树 (VFDT) 的构建是从根节点开始的, 根节点即为最初的叶节点。若s为一数据流序列, 包含潜在无限多的样本数据, 则误差参数δ由用户在初始时刻给出。样本的不同属性字段由属性集合{X1, X2, …, Xk}表示, k表示属性的个数。
(2) 当样本数据依次流入VFDT系统时, 起初所有的样本数据都聚集在决策树的根节点。随着根节点样本数据的增多, 信息增益不断增长。用nt表示从零时刻到t时刻流入的样本总数。
(3) 以信息增益为属性选择度量, 当t时刻聚集在根节点的样本数量为nt时, 可以计算各属性的信息增益。若属性Xa的平均信息增益
若
(4) 决策树生长。若式 (1) 得到满足, 则根节点将根据最佳分裂属性Xa生长出子节点, 并在其子节点中的备选属性集中删除属性Xa, 此过程递归进行。由于数据流的潜在无限性, 如果不加限制, 决策树将无限制增长下去, 若确定了树的最大深度或其他度量指标后, VFDT将通过最新到来的样本数据对决策树进行增量更新, 以保持其判断的准确性。
(5) 对内存进行优化。在Hoeffding树算法的基础上, 通过VFDT在内存的优化方面做出改进, 在当前数据占满内存空间时, VFDT系统将暂时解除对分类决策影响最小的子节点所使用的空间。对于暂时失去活性的子节点, 若后来其分类准确率较之当前的活跃节点高, 将再次恢复其活性。
(6) 打破平局。当最佳分裂属性与次佳分裂属性的平均信息增益之差很小时, 传统的Hoeffding树算法将在属性选择上花费大量的时间。VFDT算法引入了一个界限参数τ (由用户提供) , 若
(7) 处理速度优化, 在步骤 (3) 中, 传统的Hoeffding树算法会在每一个样本到达时进行一次分裂属性测试, 这将极大地影响系统的计算效率。VFDT系统引入了一个分裂属性最小样本数nmin (由用户提供) , 当到达节点的样本数为nmin的整数倍时才进行测试。
1.2 快速决策树算法分析
VFDT算法利用Hoeffding界, 以高概率确定在1个节点选择分裂属性时需要的样本最小数量, 这个属性将与使用无限样本得到的属性一样。由于快速决策树算法的分类精度与单纯样本数量无关, 其需要维护的惟一统计量是具有类标号yk属性Ai值vj的计数nijk。因此, 若d是属性的个数, v是属性值的最大个数, c是类的个数, l是树的最大深度, 则内存总需求为O (ldvc) 。与其他决策树算法相比, 这一内存需求是适度的, 因此可实现对实时增量数据流的处理。
但是, 由于VFDT算法没有考虑概念漂移问题, 因此将VFDT算法直接对广泛存在概念漂移的网络数据流进行分类时, 会出现很大偏差。另外, 随着时间的推移和概念漂移的产生, VFDT树中将积累大量过时的样例, 使得VFDT树变得非常臃肿。
2 快速决策树算法优化方法
对于概念漂移问题, 可在原决策树的生长过程中予以解决, 即若有节点出现分类不准, 则在相应节点旁派生出一颗替代子树 (Talt) 。当替代子树生长到足以对新到样本进行准确分类时, 将替代原树中相应的子树。
2.1 优化后算法的执行过程
(1) 优化后的算法核心决策树仍然是Hoeffding树。其原因是Hoeffding决策树能够依靠Hoeffding界原理, 以小样本替换无限样本, 构建高效增量决策树, 并只需对数据流进行一次扫描, 这符合应用需求。
(2) 优化后的算法保持了VFDT系统的处理速度和准确度, 并引入了对新到样本发生概念漂移时的响应机制。在算法中, 加入了滑动窗口W, 当新样本到达时, 将其加入滑动窗口。滑动窗口的任务是当有新样本到达时, 靠增加决策树相应节点中的计数来回应新样本特性。与此同时, 减少旧样本或过时样本中相应的计数来维持一个最新的分类模型, 而不是一有新样本到达就创建一个新模型[8]。
(3) 优化后的算法中对滑动窗口进行了改进, 对每个数据流样本引入1个影响因子β∈[0, 1]。β值的作用是用来判断决策树的分类效用, 并根据其取值的不同来影响滑动窗口中样本的计数值, 进而对滑动窗口的大小进行动态调整[9]。在改进的滑动窗口中, 对流过样本的计数则基于影响因子的计数nijkβ。当决策树中, 某个样本分类出现偏差时, 该样本在滑动窗口中的影响因子β将在0≤β<1的范围内, β趋于0的程度正比于偏差节点与根节点的距离, 可以用树深l (出现偏差的层数) 来表示, 即β∝l。相反, 当实际分类为正确分类时, β=1。在滑动窗口中设定1个阈值ζ (如0.5) , 设|W|为滑动窗口中的样本计数, |W|∈[0, nijk], 并规定当满足:
说明发生明显概念漂移, 锁定出错节点, 构造替代子树, 并缩小滑动窗口的大小, 直到下式成立;
当:
成立, 并至少在T (人为界定) 个窗口周期内保持稳定, 此时以|W|/2增量递归扩大滑动窗口的大小, 直到到达式 (2) 的临界点时停止。
(4) 优化后的算法将根据滑动窗口中有效样本的数量来判断分裂的有效性, 即:若式 (2) 满足, 将重新计算在滑动窗口出现严重分裂偏差的节点中各属性的模糊信息增益。若当内部某节点在向下分类且滑动窗口中相应样本点的影响因子β较前一样本点快速趋于0时, 说明在对该样本点进行分类时发生了概念漂移。这说明该节点的属性测试出现了偏差, 此时将有1棵替代子树产生。若一新样本属性Xnew的模糊信息增益高于当前的分裂属性Xcurr, 则优化后的算法将在相应节点处以属性Xnew为根节点生成1棵替代子树。
(5) 对属性分裂效用的判断, 将改进VFDT算法中的方法。使用模糊信息增益的方法可周期性地检测最佳分裂属性。由于现实网络数据流中存在大量的噪声数据或非确定信息, 即便是对于某些离散属性字段, 采用传统的陡峭属性分裂方法也会导致分类界限不清晰。因此, 改进后的算法, 对于离散属性和连续属性都采用模糊信息增益作为属性选择度量。
(6) 替代子树生长过程控制。为提高内存利用率, 替代子树也需要控制其规模, 并进行适当剪枝。剪枝的判断标准以原子树与替代子树间分类的准确度增量大小为依据。优化后的算法规定, 若替代子树满足式 (5) , 将对其保留;否则, 将删除该替代子树。
式中:i为原树和替代树中的节点编号;λ为替代子树保留的阈值。
式 (5) 中, 准确度可用该节点正确分类样本数与流经该节点总样本之比来定义, 即:
2.2 优化流程如图
优化流程如图1所示。
3 优化算法验证
由于本文研究的是数据流环境下的挖掘算法, 为了验证算法的有效性, 必须对静态数据集进行动态化处理。根据流数据区别于静态数据的潜在无限、动态变化, 以及对流数据的处理单遍扫描、实时处理等特点及要求进行动态处理。另外, 由于在网络传输过程中传输数据将受到自然环境和电磁环境的干扰, 因此在实验中将向每组实验数据加入5%的噪声数据。
在实际操作中, 从数据集中随机顺序抽取100万条样本作为测试数据, 初始属性数为5, 每增加10个属性检测1次结果, 经Matlab[10]仿真后的效果图如图2所示, 图中标出了随着用于分类的属性增多, 概念漂移的变化情况。
4 结 语
改进算法引入了滑动窗口技术, 滑动窗口中的所有样本都可以全部放入内存, 并通过窗口机制来实时判断系统对外围数据的分类效果。因此, 其效率与样本总数无关。另外, 滑动窗口的引入也使得改进系统所生成的分类模型始终与当前情况相适应, 改善了概念漂移对前面分类模型的影响。另一方面, 通过构建属性二叉树的方法使得当新样本插入时算法只需更新一个节点, 时间复杂度为O (nlog n) , 比VFDT的O (n2) 要好 (其中n为当前节点上所观察到连续属性i的不同取值数目) 。从仿真图可以看出, 由于改进后的算法是基于数据挖掘的动态增量决策树算法, 随着流入样本的增多, 规则将被逐条建立, 而且分类决策树会随着分类属性字段的增多而变得更精确。随着分类属性的增多, 发生概念漂移的样本数会增加, 这才显示出解决概念漂移的能力强。
参考文献
[1]徐国爱.网络安全[M].北京:北京邮电大学出版社, 2004.
[2]MANKU G S, MOTWANI R.Approximate frequencycounts over streaming data[C]//The 28th InternationalConference on Very Large Databases.Santiago:[s.n.], 2002:93-101.
[3]GIANNELLA C, HAN J, PEI J.Mining frequent patternsin data streams at multiple time granularities[J].Next Ge-neration Data Mining, 2003, 45 (17) :217-221.
[4]史金成, 胡学刚.数据流挖掘研究[J].计算机技术与发展, 2007, 17 (1) :11-14.
[5]王建涛, 蔡淮.流数据惯例若干关键问题的研究[J].成都信息工程学院学报, 2008, 23 (3) :269-274.
[6]DOMINGOS P, HULTEN G.Mining high-speed datastreams[C]//International Conference on Knowledge Dis-covery and Data Mining, [S.l.]:[s.n.], 2000:37-42.
[7]HULTEN G, SPENCER L, DOMINGOS P.Mining time-changing data stream[C]//International Conference onKnowledge Discovery and Data Mining.[S.l.]:[s.n.], 2001:216-219.
[8][美]HOROWITZ Ellis, SAHNI Sartaj.计算机算法 (C++版) [M].冯博琴, 叶茂, 译.北京:机械工业出版社, 2006.
[9]李国徽, 陈辉.挖掘数据流任意滑动时间窗口内频繁模式[J].软件学报, 2008, 19 (10) :13-15.
模糊决策树 第2篇
属性值和权重都是直觉模糊集的多属性决策问题不同于一般的`多属性决策问题,不能运用现有的决策方法求解.本文给出了直觉模糊正、负理想方案的定义及其与每个方案的欧氏距离,进而建立了每个方案与直觉模糊正理想方案的相对贴近度计算方法,从此产生所有方案的优序排序,即拓展了TOPSIS法.数值实例说明了该方法的有效性和实用性,可为解决直觉模糊多属性决策提供新途径.
作 者：南江霞 李登峰 张茂军 NAN Jiang-Xia LI Deng-Feng Zhang Mao-Jun 作者单位：南江霞,NAN Jiang-Xia(大连理工大学,应用数学系,辽宁,大连,116024;大连大学,信息工程学院,辽宁,大连,116622)
李登峰,LI Deng-Feng(海军大连舰艇学院,作战指挥系,辽宁,大连,116018)
张茂军,Zhang Mao-Jun(大连理工大学,经济系,辽宁,大连,116024)
模糊决策树 第3篇
关键词：模糊决策树,遗传算法优化,10-fold,cross-validation软件估算
软件估算的两大目标是进度与成本, 而这两大目标永远不会是一门精确的科学, 人员、技术、环境、策略等等对软件最终成本与开发所需工作量都有严重影响。估算有风险, 越来越多的人在研究软件估算的方法。现在世界上比较流行的软件估算方法有:“模糊逻辑”法, 功能点法, 标准构件法, 修改法, 基于代码行 (LOC) 的估算方法, 基于功能点 (FP) 的估算方法, 基于过程的估算方法, 基于COCOMO模型的估算方法, 基于软件方程式的估算方法。各种方法各有优缺点, 为使软件估算更精确, 提高软件可靠性, 本文将通过某项目实例使用遗传算法和模糊决策树结合的方法进行软件估算。遗传算法优化的模糊决策树软件工作量估算模型是基于遗传算法优化的模糊决策树算法, 输入的数据为原始化数据。
遗传算法 (Genetic Algorithm, GA) , 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型, 它是由美国Michigan大学的J.Holland教授于1975年首先提出的。遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表, 把问题的解用染色体代表 (在计算机里用二进制码表示) , 从而得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生存竞争, 适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征, 并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境, 不断进化, 最后收敛到一族最适应环境的类似个体, 即得到问题最优的解。
随机给出两个参数的初始值, 它们的范围分别是0、1。用遗传算法每一代优化得到的参数都进行启发式算法的诱导, 即选择、交叉、变异;循环执行上述步骤, 直到评价函数达到要求。当循环一定代数以后, 模糊决策树的分类准确率和叶子总数达到满意结果且较稳定。
在构建模型中本文采用10-折交叉验证 (10-fold crossvalidation) , 它用来测试算法准确性。是常用的测试方法。将数据集分成十份, 轮流将其中9份作为训练数据, 1份作为测试数据, 进行试验。每次试验都会得出相应的正确率 (或差错率) 。10次结果的正确率 (或差错率) 的平均值作为对算法精度的估计, 一般还需要进行多次10折交叉验证 (例如10次10折交叉验证) , 再求其均值, 作为对算法准确性的估计。之所以选择将数据集分为10份, 是因为通过利用大量数据集、使用不同学习技术进行的大量试验, 表明10折是获得最好误差估计的恰当选择。
软件开发是一项非常复杂的工程, 不仅包含需求分析、设计 (概要设计、详细设计) 、编码、测试、实施维护等完整的过程, 还涉及到开发工具、开发人员技术水平、项目范围、项目沟通等众多因素。这里我以Desharnais数据集为基础数据, 开展软件估算工作。Desharnais数据集最初由Desharnais在1989年使用, 来自一个加拿大软件公司。它是在软件工作量估算领域中最著名的公开数据集之一。把数据集划分为样本数大致相等的子集, 10个项目属性分别是实际工作量、项目进度、开发人员技术水平、项目管理经验、业务、调整前功能点数、调整因子、调整后功能点数、开发环境、完成年份、系统数据模型的实体数。软件项目的进度和属性实际工作量一样, 因此不予考虑。在这10个属性中, 属性开发环境为类别属性, 其它的属性为数值属性。
软件开发语言环境, 有三种开发语言环境 (开发语言环境1, 开发语言环境2, 开发语言环境3) 模糊化后, 模糊变量开发有三个模糊集, 分别是开发环境1、开发环境2、开发环境3, 在模糊化中可使用对类别属性的处理方法进行模糊化处理。假设样本的属性a是类别型属性, 该属性有n个类别值, 分别为n1, n2, n3, …, ni, 则属性a的模糊化后, 可得到i个模糊集合, 其隶属函数为:
即, 对于类别型属性, 每一类就是一个模糊集合, 某模糊集合的隶属函数是分段二值函数, 当属性值是该类时, 隶属函数为1, 当属性值不是该类时, 隶属度值为0。例如, 某项目的开发语言环境为1, 则其在三个语言值语言1、语言2和语言3上的隶属度分别为1、0、0。
开发人员对设备的熟悉程度和项目管理经验两个属性是根据工作经验来确定的, 在实际生活中, 我们用新手、有一定经验、经验丰富等语言来说明人们对工作的熟练程度, 我们可以用工作年限来进行处理。这样的话, 属性开发人员技术水平和属性项目管理经验的模糊化就是要解决工作年数与相应语言值之间的映射关系。使用三角隶属函数对这两个属性进行模糊化, 工作年限最小为0。
下面对以上属性进行模糊化处理。当子集实际工作量为测试样本、其余子集样本为训练集时, 模糊化处理过程如表1。
采用半开口式对于属性系统数据模型的实体数 (31, 149.3, 267.7) 三个模糊集合的隶属函数参数见表2。根据由此产生的隶属函数对训练集合和测试集进行模糊化。其它几个属性相同的方法进行模糊化。
按照以上的方法, 在其它子集作为验证集时, 先确定模糊集合和相应的隶属函数, 然后对样本数据进行模糊化处理, 为构建模糊决策树、验证模型性能做好数据准备。
参考文献
[1]张朝杰.一种基于模糊决策树的软件工作量估算方法[D].国防科学技术大学, 2010.
[2]Steve Mc Connell.软件估算黑匣子揭秘[M].电子工业出版社, 2007.
[3]阎魏.基于决策树的软件工作量估算方法[J].计算机工程与科学, 2009 (08) .
[4]冯楠, 李敏强, 寇纪淞, 等.一种基于模糊决策树的软件成本估计模型[J].计算机工程与应用, 2007, 43 (026) :21-23.
决策树决策方法的探讨 第4篇
如:某企业为生产一种新产品, 设计了两个基本建设方案;第一方案是投资300万元建大厂, 第二方案是投资140万元建小厂。经市场调查预测后, 两个方案的有效期为10年, 前3年产品销路好的概率为0.7, 销路差的概率为0.3, 在前三年销路好的基础上后7年销路好的概率为0.9, 销路差的概率为0.1, 前3年销路差, 后7年仍差。两方案如投资后, 其年损益值分别为:建大厂, 销路好每年收益100万元, 销路差则亏损20万元;建小厂销路好每年收益40万元, 销路差仍收益20万元;以收益最大为决策目标, 问哪个方案最佳?这样的问题我们常用决策树决策法来解决;其过程如下:
1、根据题意画出决策树:
2、计算期望值 (用E表示)
小厂方案收益为330.2-140=190.2 (万元)
3、决策根据收益最大目标决策
剪去小厂方案, 保留大厂方案, 以上方法我们在决策树中常用。
然而企业在市场经营的过程中, 面临的市场环境的变化多种多样。有如以上的企业前阶段好, 后阶段差些。也会有企业经营的情况前阶段差, 后阶段好。如某企业为生产一种新产品, 设计了两个基本建设方案;第一方案是投资300万元建大厂, 第二方案是投资140万元建小厂。经市场调查预测后, 前三年由于知名度不高, 初入市场销路好的概率为0.7、销路差的概率为0.3, 后七年由于进入成长期, 其市场销路好的概率为0.82、销路差的概率为0.18, 两方案如投资后, 其年损益值分别为:建大厂, 销路好每年收益100万元, 销路差则亏损20万元;建小厂销路好每年收益40万元, 销路差仍收益20万元;以收益最大为决策目标, 问哪个方案最佳?这种情况是否也能用决策树方法表现出来呢?我个人认为也可以。
因为根据前面的题意, 前三年销路好的概率为0.7、销路差的概率为0.3;后七年实际市场销路好的概率为0.63、销路差的概率为0.37, 就好象一棵果树, 下部分长得好、上部分长得差了一样。
那么变化的这种市场就如发现前部分的果树长势不好, 后来采用各种有效方法改变其长势, 使得果树本来好枝上的果实顺势长好, 也就是前三年销路好的概率为0.7的枝, 后七年仍然保持这样好趋势, 销路好的概率为1, 而差枝上的果实通过科学方法, 使得本来长势不好的枝上部分果实变得长好。也就是前三年销路差的概率为0.3的枝, 后七年40%的部分果实变得长好了, 但是仍然有60%的部分果实长得不好。
其决策过程如下:
1、根据题意画出决策树
2、计算期望值 (用E表示)
大厂方案收益为740.8-300=440.8 (万元)
3、决策根据收益最大目标决策
剪去小厂方案, 保留大厂方案。
决策树的这种变化会使其应用领域更加广泛, 企业的经营投资决策、市场营销生命周期各阶段的投入决策都能使用。
此变化是本人对决策树决策方法的探讨。个人认为在决策树决策方法理论和实际操作上都还是可行的, 但是在果树的实际栽培过程中很可能还会有一定的难度。那么就先让它为企业的经营决策服务。
摘要：决策树决策方法是企业在市场经营遇到风险型决策问题时常用的方法之一。由于它在决策过程中具有层次清晰、简单明了、生动、形象等特点。特别是决策问题处在多阶段、多层次中, 它能方便地表达出各阶段决策与整体决策的前后关联与相互影响。怎样将此方法运用到更宽的市场营销风险型决策领域, 以下是本人对决策树决策方法变化的探讨。
关键词：决策树,决策方法,变化,探讨
参考文献
[1]、车礼, 胡玉立主编《市场调查与预测》, 武汉大学出版社1993年版
决策树算法综述 第5篇
随着数据库技术的发展,人们搜集数据的能力大幅度提高,可以非常方便地获取和存储大量的数据,但却无法从这些数据中发现潜在的规律,无法预测未来的发展趋势。如何有效的利用这些数据为人类服务,已成为人们研究的热点之一。数据挖掘技术能自动和智能地从大型数据库中提取隐含的、未知的信息和知识［１－３］。
分类是数据挖掘的重要分支,可用于提取、描述重要数据类的模型或预测未来的数据趋势［４］。通过分类和预测,能够对各个行业提供良好的决策支持,对整个社会的发展产生重要而深远的影响［５］。决策树算法是数据挖掘分类算法中常见的一种方法。它以树状结构表现,叶子结点代表一个结论,内部结点描述一个属性,从上到下的一条路径,确定一条分类规则。与其它技术相比,决策树算法结构简单直观,容易理解,有较高的分类精度,在数据挖掘、机器学习、人工智能等领域等都有广泛的应用。所以研究并提出高效、适用的决策树算法对整个社会的发展意义重大。
本文对几种经典的决策树分类算法进行了分析,指出不同算法的优点和不足,并讨论了决策树算法今后的研究方向。
1几种决策树分类算法介绍
决策树算法是一种逼近离散值目标函数的方法,它将分类规则以树状结构表示［６］。
1.1 ID3算法
机器学习研究者J.Ross Quinlan在1986年把Shan- non的信息论引入到了决策树算法中,提出了ID3算法［７］。ID3算法的概念如下［８－９］:
设样本集E共有C类样本训练集,每类样本数为pｉ, i=1,2,...C 。如果以属性A作为测试属性,属性A的v个不同的值为{v１,v２,...,vｖ},可以用属性A将E划分成v个子集{E１,E２,...,Eｖ},假定Eｉ中含有第j类样本的个数为pｉｊ,j=1,2,...C ,那么子集Eｉ的熵为［１０］:
属性A的信息熵为:
将Infor_Entropy(Eｉ)代入公式(2)后可得:
一棵决策树对一样例作出正确类别判断所需的信息为:
信息增益:
ID3算法存在着属性偏向、对噪声敏感等问题[10,11]。
1983年,T.Niblett和A.Patterson在ID3算法的基础上提出了ACLS Algorithm。该算法可以使属性取任意的整数值,这扩大了决策树算法的应用范围[12]。
1984年,I.Kononenko、E.Roskar和I.Bratko在ID3算法的基础上提出了ASSISTANT Algorithm,它允许类别的取值之间有交集［１２］。
1984年,A.Hart提出了Chi—Square统计算法,该算法采用了一种基于属性与类别关联程度的统计量［１３］。
L.Breiman、C.Ttone、R.Olshen和J.Freidman在1984年提出了决策树剪枝概念,极大地改善了决策树的性能［１４］。
1986年,T.Niblett提出了Minimum-Error Pruning Algorithm［１５］。1987年,J.R.Quinlan提出了Reduced Er- ror Pruning Algorithm［１６］。1987年,J.Mingers提出了Critical Value Pruning Algorithm［１７］。1992年,K.Kira和L.Rendell提出了RELIEF Algorithm,该算法是决策树算法发展史上一座里程碑［１８］。
1.2 C4.5算法
在ID3算法的基础上,Quinlan在1993年又提出了一种改进算法,即C4.5算法［１９］。
信息增益率计算如下［１０］:
C4.5算法克服了ID3算法属性偏向的问题,增加了对连续属性的处理,通过剪枝,在一定程度上避免了“过度适合”现象［２０］。但是该算法将连续属性离散化时,需要遍历该属性的所有值,降低了效率;要求训练样本集驻留在内存,不适合处理大规模数据集。
1.3 CART算法
CART算法是描述给定预测向量X 、条件分布变量Y的一个灵活方法,最早是由Breman等人提出,已经在许多领域得到了应用。
CART算法可以处理无序的数据。采用基尼系数作为测试属性的选择标准。
基尼系数计算如下:
其中|T|,|T1|,|T2|分别是样本集T、T1和T2中的样本个数。
其中pｉ是类别j在T中出现的概率。
CART算法生成的决策树精确度较高,但是当其生成的决策树复杂度超过一定程度后,随着复杂度的提高,分类精确度会降低。因此,用该算法建立的决策树不宜太复杂［２０］。
1.4 SLIQ算法
决策树分类算法研究一直朝着处理大数据集的方向进行,但大部分方法在减少了运算时间的同时也降低了算法的精度。SLIQ的分类精度与其它决策树算法不相上下,但其执行的速度比其它决策树算法快。SLIQ算法对训练样本集的样本数量以及属性的数量没有限制。SLIQ提高了分类的精确度［２１］。
SLIQ算法能够处理大规模的训练样本集,具有较好的伸缩性;执行速度快而且能生成较小的二叉决策树; SLIQ算法允许多个处理器同时处理属性表,从而实现了并行性［２１］。但是SLIQ算法依然不能摆脱主存容量的限制。
1.5 SPRINT算法
SLIQ算法要求类表驻留内存,当训练集大到类表放不进内存时,SLIQ算法就无法执行。为此,IBM研究人员提出SPRINT算法,它处理速度快、不受内存的限制。
SPRINT算法可以处理超大规模训练样本集,数据样本集数量越大,SPRINT的执行效率越高,并且可伸缩性更好。但是,SPRINT算法存在着一些缺陷:在SLIQ的类表可以存进内存时,SPRINT算法的执行速度比SLIQ算法慢;该算法由于使用了属性表,增加了存储代价。
1.6 PUBLIC算法
上述含有剪枝的算法都是分成两步进行,即先建树再剪枝。然而,这种方法将已生成的分枝再剪去是一种效率较低的重复劳动,于是Rajeev RaSto等人在2000年提出了PUBLIC算法(Pruning and Building Integrated in Clas- sification)［２３］。由于PUBLIC算法是对尚未完全生成的决策树进行剪枝,因而提高了效率。近几年,模糊决策树也得到了蓬勃发展［２４－２５］。
上述算法未考虑属性间的相关性。因此,后来人们又提出了分层回归算法、约束分层归纳算法和功能树算法。
分层回归算法、约束分层归纳算法和功能树算法都是基于多分类器组合的决策树算法,它们对属性间可能存在的相关性进行了部分实验和研究,但是这些研究并没有从总体上阐述属性间的相关性是如何影响决策树性能的［２６－２８］。
基于粗糙集的决策树方法也是典型的决策树算法。 文献[29]提出了基于粗糙集的优化算法,并且分析了各自的优缺点。文献[30]通过设计特殊的Hashtable减少了每次读取I/O的开销,这种方法很大程度上降低了时间复杂度,但是并没有考虑到精确度的改进,而且由于数据量大时,哈希表也会很占内存。文献[31]提出了基于极端学习树的模型,也是能够降低时间复杂度,但是不易实现并行化计算和设计。
1.7经典决策树算法比较
基于决策树的分类算法自提出至今,种类不下几十种。各种算法在执行速度、可扩展性、输出结果的可理解性、分类预测的准确性等方面各有所长。表1是几种经典的决策树算法比较［３２］。
2结论及展望
决策树虽然在理论研究和实际应用方面都取得了很多进展,但还存在不少问题亟待解决,这正是今后的研究方向,主要有:
(1)实验证明:要找到最优的决策树是NP问题［３３］, 必须寻找更好的方法,将决策树技术和其它新兴技术相结合,取长补短,提高决策树的抗噪声能力和准确性。
(2)研究属性间的相关性对决策树产生的影响,以及如何利用或者消除这些相关性来构造决策树,值得关注。
(3)决策树技术中如何处理时间复杂度和分类准确性之间的矛盾,一直以来都是一个令人感兴趣的问题。怎样在提高准确度的前提下降低时间复杂度,是今后研究的一个重点及难点。
决策树算法及其应用 第6篇
1 决策树生产过程
决策树进行传统的数据分类包含两个步骤:
第一步:利用训练集进行创建模型阶段, 找到映射函数表示模型, 从指定的训练集中获取知识, 这是一个学习的过程。
第二步:利用生成的决策树预测数据的类别, 使用上一步训练完成的函数模型进行预测, 对输入的记录, 从根结点开始一直到叶结点进行测试属性值, 然后对数据集中的每一类数据进行描述, 生成分类规则。
具体工作过程如图1所示。
2 决策树算法的优点
(1) 学习该算法, 不要求使用者的知识背景丰厚, 就能够在训练事例中用属性→结论的方式来进行表达。
(2) 训练集数据量较大的情况下, 决策树模型效率较高。
(3) 决策树是一种树状结构, 它是最简单直观的, 因此在分类模型中经常被应用的方法之一, 通过从根结点一直到达叶子结点的路径转换, 最终能够生成分类规则以IF→THEN形式进行表示, 这样更能够让人容易理解。
(4) 决策树方法对于分类而言, 精确度较高。
3 决策树的评价指标
(1) 准确的预测性。决策人员最关心的就是预测的准确性, 分类模型具有对未知新数据进行准确预测的能力、也能对未知的数据类的预测能力。
(2) 描述的简洁性.分类发现模型对问题的描述方式提出的分类发现模型只有越简洁越容易理解才能够方便决策人员使用。
(3) 计算复杂性。在数据挖掘的过程中, 操作的数据对象是海量信息的数据库, 所以空间和时间的复杂性将直接影响模型的计算成本, 计算的复杂度是在海量数据库中具体实现的细节决定的。
(4) 处理规模性。
(5) 模型强健性。
4 决策树算法在学生就业工作中应用
4.1 设计方案
利用决策树C4.5算法分析哪些因素对学生就业有影响。
选取计算机系10届、11届、12届计算机科学与技术专业学生为研究对象, 学生人数为200人。
4.2 数据采集
(1) 学生基本信息库。数据结构如下:姓名、学号、性别、班级、籍贯。
(2) 学生就业信息库。内容包括学号、姓名、参加公司培训、是否优质就业 (工资在3000元以上为优质就业) 等。
(3) 成绩表。成绩数据库中包括了学生的课程总成绩平均分和综合测评成绩平均分, 这个数据库由教师在教学过程中和辅导员对学生表现评定产生。
4.3 数据项处理
数据集成。根据给出的数据文件, 将三个数据源的数据利用数据库技术生成学生就业分析表。
数据清理。生成学生就业分析表工作要进行填补遗漏的数据值。
数据转换。数据转换中离散值属性要占大多数, 连续值属性并不多, 只有个别的需进行离散化处理。现将上述综合成绩属性的属性值化分为4类:成绩从0~60分属于“及格”, 60~80分属于“中”, 80~90分属于“良好”, 90~100分属于“优”, 性别两类:男或女;参加公司培训分为两类:是或否;就业分为三类:工资在3000元以上为优质就业, 2000-3000元为普通就业, 2000元以下为一般就业, 无工作为待就业。增加参加公司培训可以判断优质就业的可信度。
数据消减。由于学生基本信息表和学生就业信息表中的属性比较多, 笔者为了便于分类挖掘, 将籍贯、班级这两个属性进行删除, 原因是这两个属性与就业相关性不大, 为了能够保护学生的隐私, 笔者将学生姓名属性也删除掉, 从而生成新的学生就业分析表与转换数据表。
参考文献
[1]郭佳, 陈春燕.数据挖掘技术在高校毕业生就业工作中的应用[J].中国科技信息, 2008, 14:67-69
决策树技术研究综述 第7篇
决策树是一种重要的数据挖掘技术,常用于分类预测以及规则提取等诸多领域[1,2,3,4,5,6,7,8]。决策树采用贪婪策略,通过递归方式自顶向下进行构造。从发展脉络上看,目前丰富的决策树算法均起源于Hunt,Marin和Stone在1966 年提出的单概念学习系统[9]。
1979 年,Quinlan提出ID3 算法,并于1983 年和1986 年对其进行进一步的完善和发展。通过不懈的努力,Quinlan不但使ID3成为经典的决策树算法,还通过开办公司的方式使之成功走向应用。1986 年,Schlimmer和Fisher在ID3 的基础上,通过创建缓冲区,提出可伸缩的递增式决策树算法ID4。1988年,Utgoff在ID4基础上又提出效率更高的ID5算法。1993年,Quinlan提出C4.5 算法,突破了ID3 算法只能处理布尔函数样例的束缚。
为进一步提高缩效率,研究者在ID4的基础上又提出了一批可伸缩的决策树算法,代表性的有SLIQ、SPRINT、Rain For-est、BOAT算法。目前来看,综合指标最佳的算法是BOAT,不但可伸缩而且效率更高(仅需扫描训练样例集两遍),并且是增量式学习算法[10]。
目前对决策树技术的研究主要集中在已下几个方面[11]:1)与其他技术相结合,如与神经网络[12,13]、模糊集[14,15]、遗传算法及遗传编程[16,17,18,19,20]、多智能体[21,22,23]等原理和技术相结合;2)寻找可视化的交互式决策树构造方法[24];3)寻找更好的剪枝算法[25];4)寻找训练样本集、检验样本集特性与生成树特性之间的联系[26,27];5)包括半监督学习在内的非确定环境下的决策树研究[28];6)时间复杂度与分类准确性的折衷研究[29]。
相对而言,国内对决策树技术的研究尚不够活跃,但值得关注的是朱鸣和陈文伟提出的决策规则树方法——IBLE方法。IBLE方法采用信道容量作为衡量样例的目标属性的标准,是一个不依赖正、反例比例的量。而且,该方法迥异ID3算法的一个重要区别是每次遴选一组相对重要的属性,依其建立的规则作为决策树的非叶子结点,更富有效率并更准确[30]。
2 决策树技术概览
由ID3、ID4.5等算法生成的决策树是一种类似二叉树和多叉树的树形结构。决策树中的非叶子结点代表一个目标属性,每个叶子结点表示一个分类,从根结点到叶子结点的所有结点表示一个分类规则。
2.1 决策树与归纳学习
决策树的本质是归纳学习,是一种从部分数据中归纳出整体数据特征完备描述的技术。归纳学习是人类知识增长的一种重要方式。例如,看到乌鸦、喜鹊、黄鹂、燕子、大雁等鸟类具备飞行的能力,在未对所有鸟类都进行观察的情况下,归纳出以下的规则:鸟类都具备飞行的能力。于是,按此规则可以进一步预测云雀、百灵、鹦鹉都具备飞行的能力。虽然此规则未必适用所有鸟类,如鸵鸟,但其基本是准确的,准确率可以达到百分之九十以上。决策树的分类预测能力,完全来自于它能够从部分数据归纳和概括出整体数据特征描述(决策树技术通过测试和筛选训练样本集合的属性集合,并生成新的属性子集的方式实现这种描述)的能力。
2.2决策树应用步骤
利用决策树应用大致可以分为以下四大步骤:
1)对训练样本集进行数据补齐、数据清洗、离散化、规范化等预处理;
2)使用ID3、ID4等具体算法,利用训练样本集训练(构建)一棵决策树,并对决策树进行前剪枝或后剪枝处理。
3)对经过训练的决策树输入检验样本集进行检验:如果对分类结果不满意,则转(1)。
4)应用训练好的决策树对需要预测分类的样本进行分类。
2.3决策树的特点
目前存着许多分类方法和技术,如贝叶斯信念网络、BP网络、支持向量机、关联分类、近邻学习、粗糙集方法、模糊集方法等,决策树之所以能够如此流行并得到高度关注,一个重要原因是它具备一些区别于其他分类方法的鲜明特点:
1)从理论上说,决策树技术可以处理任意高维的数据;
2)决策树算法虽然简单,但比较高效;
3)决策树技术具有较高的分类预测准确率;
4)在决策树的构造过程中,无需任何的先验知识,也无需以交互方式设定参数;
5)获取的知识用树形结构表示,既直观又易于理解。
2.4 ID3决策树建立算法
在决策树技术的发展历程中,先后经历了从不可伸缩到可伸缩、布尔函数分类预测到多值函数预测等阶段,涌现了多个优秀的算法。以下以经典的ID3算法[31]说明决策树技术的基本原理。
输入:ID3(Examples,Target_attribute,Attributes),Examples即训练样例集,Target_attribute是决策树要预测的目标属性,Attributes是除去目标属性之外供学习到的决策树测试的属性列表。
输出:一棵能正确分类给定Examples的决策树Root。
1.创建树的Root结点
2.如果Examples都为正例,那么返回label = + 的单结点树Root
3.如果Examples都为反例,那么返回label = - 的单结点树Root
4. 如果Attributes为空,那么返回单结点树Root,label = Ex-amples中最普遍的Target_attribute值
5.否则开始
1)A←Attributes中分类Examples能力最好的属性
2)Root的决策属性←A
3)对于A的每个可能值vi
(1)在Root下加一个新的分支对应测试A=vi
(2)令Examplesvi为Examples中满足A属性值为vi的子集
(3)如果Examplesvi为空
1 在这个新分支下加一个叶子结点,结点的label = Exam-ples中最普遍的Target_attribute值
2 否则在这个新分支下加一个子树ID3(Examplesvi,Tar-get_attribute,Attributes - |A|)
6. 结束
7. 返回Root
在算法的(1)处所描述的分类能力最好的属性为具有最高信息增益的属性。
2.5 熵与信息增益
1)信息熵
ID3算法认为,对于一个拥有n个反例和p个正例的样例集合S来说,能对其正确分类的决策树的信息量为:
若以属性A作为当前样例集S的根,并设A有v个值v1,v2,…,vv,并将分S为对应的v个子集S1,S2,…,Sv,且某子集Si中含有Pi个正例和Ni个反例,规定Si的信息熵为:
又规定以属性A为根进行分类的信息熵为:
2)信息增益
ID3中规定,信息增益最大的属性A可评为分类最好属性,其定义式为:
综合公式(1)~( 4),可以推知在当前样例集下,属性A的信息增益最大时,其信息熵E(A)最小。
2.6 决策树建立举例
本小节以2.5中介绍的ID3算法为例,基于表1中描述的元组为训练样本集S,简述决策树建立过程。
首先,计算对S中元组分类所需的期望信息:
下一步,计算每个属性的期望信息需求。例如元组根据age属性进行划分,对S中的元组进行分类所需的期望信息为:
因此,以属性age进行划分的信息增益为
Gain(age)= 0.940 - 0.694 = 0.246bits
类似可求得
由于age属性具有最大的信息增益,所以被选作分裂属性。根结点用age标记,并对应于它的每个属性值长出一个分枝。然后,元组据此划分,如图1所示。
在每一个分枝所对应的训练子集上,重复前述步骤,即可得到最终的决策树。
3 未来研究方向
结合目前的研究[9,10,30,31,32,33],未来决策树技术的研究应该包括以下几个方面。
1)基于量子免疫克隆算法的决策树优化。
决策树本身的优化需要面对以下理论问题(洪家荣教授首次证明了这几个问题都是NP难问题):1最优覆盖问题,即决策树中叶子结点数目最少;2最简公式问题,即保证决策树的每个叶子深度最小;3最优示例学习问题,即决策树叶子最少且每个叶子的深度最小[33]。对于决策树的自身优化,学术界已经有了一些研究成果,提出了一些近似或启发算法。但这些算法还存在一些不足,如易陷入局部最优、时间成本高、分类预测准确率较低等。
由于量子计算所拥有的量子相干特性,可以有效避免一些启发式算法陷于局部最优,免疫算法易实现数据的分布式存储,克隆算法具有强大的自适应能力,因此,决策树的优化还应结合量子计算、免疫算法、克隆算法等相关技术,以便实现优势互补。
2)基于IBLE方法和支持向量机相结合的决策规则树研究。
IBLE方法具有实现简单,学习正确性较高,所得知识在表示和内容上与专家知识有较高的一致性等优点,但在处理小样本的情况下性能较差。而支持向量机特别适于处理小样本的情况,将二者相结合,可以期望会有更好的表现。
3)不确定环境下的决策树研究。
不确定环境下的决策研究一直是一个热点。但如何比较科学地确定决策阈值,目前还是一个鲜有人涉足的课题。
4)连续属性值离散化问题的研究。
由于决策树技术要求属性值为离散值,因此连续值在使用前需要进行离散化处理。按惯常作法,一般将连续值离散为7个以内的离散值。离散值的个数及其具体数值直接影响到决策树的分类质量和效率,科学地取值以及科学地确定离散值数量,是一个值得深入研究的课题。
4 小结
本文介绍了决策树技术及其发展过程,综述了近几年决策树技术的国内外研究现状,展望了进一步的研究方向。
摘要：决策树是一种重要的数据挖掘技术,广泛应用于电子商务、医学、天文学和决策分析等多个领域。针对决策树技术研究越来越受到重视的现实情况,通过介绍决策树技术相关概念、理论及其发展过程,阐述决策树技术的国内外研究现状,指出决策树技术面临的困难和挑战,并展望其研究方向。
决策树算法分析与研究 第8篇
随着计算机技术的日益发展和数据量的不断增多, 人们选择了通过计算机和信息服务技术来处理数据, 很大程度上增强了企业“收、存、管”数据的功能。经验的累积造就了企业的大数据量, 数据越多对一个企业越有利。在数据达到某种程度时, 就会总结出一定的规律, 因此需要新的工具盒技术挖掘数据仓库, 获得有效的资料, 让企业获得指导, 使之快速、稳定的发展。一些新的技术和概念随着计算机和信息技术的逐渐发展也慢慢出现, 如因特网 (Internet) 、神经网络、数据仓库 (Databaye) 等等。在技术和市场需求共存的情况下, 就产生了数据挖掘技术KDD (Knowledge Diycovery in Databayey) 的概念[1]。
数据挖掘是指从许多不清楚的数据中, 找出隐藏在信息里面的有效的信息和资料。也可以用好像数据融合、策略支持还有数据分析等这些与它非常相似的专业术语。
数据挖掘它是受多个领域的影响的, 可以把它看做是一个互相重叠交错的学科领域, 因此也就有相异分类的数据挖掘系统。下面分别从数据挖掘的目标、数据挖掘的方法以及用途、数据仓库类别三个方面进行讲解。
(1) 按照数据挖掘的目标分类
数据挖掘是多目标的, 这些目标多种多样, 有多媒体的数据挖掘、web方式数据挖掘, 还有文本的数据掘, 除此之外, 还包含了其他目标。不同的数据挖掘目标使用的挖掘方法不同。
(2) 按照数据挖掘的做法和技能匪类
数据挖掘的方法多种多样, 其用途也不尽相同, 关年、聚类、分类、预测、偏差的数据挖掘分析等等都是数据挖掘常用的方法。
(3) 按照数据仓库的类别分类
按不同的标准我们可以将数据仓库系统进行分类。按解决数据的某些类型可以将数据仓库划分为文本的、空间的、时间的、WWW的, 或是多媒体的数据挖掘系统;按数据模型可以将数据仓库划分为事务的、对象关系的、面向对象的、数据仓库的数据挖掘系统[2]。
2、决策树基本概念
数据分类是一种高效的解析方法, 它是数据挖掘中的一个非常重要的环节。利用解析训练, 数据分类可以快速找到信息, 然后创建出分类模型, 接下来就通过该模型将数据库里的信息项反映到指定的类别中去[3]。
决策树可分为两种:回归树和分类树。前者在相对于连续变量的情况下产生了决策树;后者是在相对于离散数据集的情况下产生了决策树。图1展示的是决策树产生的步骤。
决策树的构造和流程图的构造大致是一样的, 利用事例, 决策树从根节点向某叶子节点依次将事例分类, 叶子的节点就是事例的所属分类。树上的节点即事例的某一属性检测, 且该属性的可能值与节点上的分支一一对应。
图2展示的是决策树的事例, 用于分析学生的成绩。通过该模型可以分析出影响学生成绩的原因。叶子节点大多用椭圆形表示, 中间节点则用长方形表示。
3、决策树算法
Apriori算法存在一个致命的弊端, 那就是当用它来解决大数量的候选项目集时需要耗费大量的时间, 并且在在对候选项目集进行合适的选择时需要对数据库进行多次扫描。鉴于Apriori算法存在以上弊端, Lee等在FP-Tree的关联规则算法的基础上, 发明了更为先进的FP-Growth算法。利用压缩的数据结构, 这种算法可以把所有关联规则搜索要求的数据资料一一记录下来;通过反复扫描源数据, 这种算法可以将数据资料记录到结构里, 避免了候选项集的产生, 这就是无候选项集产生算法 (Frequent Patterny Growth, FP-Growth) [4]。
1 FP-Growth算法原理与相关含义
这种算法通过下列三点创新, 避免了候选项集的产生, 开拓出新的挖掘思路。
(1) FP-Growth算法创建了FP-Tree。FP-Tree是一种新的扩张前缀树结构, 用于存储关于反复模式数量的主要信息。树中的叶节点长度均为1, 频度越高的叶节点与根节点的距离越短。这样就降低了频度低的项与频度高的项共享相同节点的概率。
(2) FP-Growth算法在FP-Tree的基础上, 研发出片断成长算法。以长度为1的模式为出发点, 查询目标只针对它的条件模式和创建的模式树, 采用递归的形式挖掘数据。在联合条件模式数产生扩展模式的基础之上, 模式的成长最终得以实现。革新之后, FP-Tree算法不用像Apriori算法一样要进行再测试, 因为在FP-Tree算法里, 事务处理频繁项要对着树里的节点进行编写, 就避免了再测试的过程。计算累加值、改变前缀树是挖掘的两项基本操作, 这种算法相对于Apriori算法可以节约一大笔开销。
(3) 在分区的基础上选用合适的搜索技术进行挖掘, 对数据进行分割后再处理。与FP-Growth算法不同, FP-Tree下有一个名为“null”的目录, 还有一个由频繁项组成的表。树中的所有节点共计有3个地址:项名、节点链接和计数。当中, 节点链接代表树里下一个相同的节点, 假如无相同节点就指向空;计数存储的是到达该节点的路径所代表的需要解决的数目。由频繁项组成的表里的媒体信息包含2个地址:item name和node-link的头。其中node-link的头指向树中第一个相同的节点。
FP-Tree中只记录了符合最小支持度的项的合集, 因此, 第一就要先了解哪些项满足要求, 这就是构造头表的内容。展开首次搜索获得符合最小支持度的项并按照从低到高的顺序把它们排列在表中。在获得表之后, 对其再一次展开搜索, 对这些事务解决中存在的频繁项遵循它在头表中的前后关联加到树中。插入到树中的事务解决的频繁项自然是树的一个节点, 单假如树里有其他与性节点完全一样或者是类似的节点, 就要把这两个节点合并:将事务解决插入到FP-Tree中的函数inyert-tree是步骤中一个必要的环节。
FP-Tree是一个高度压缩的结构, 它记录了频繁模式挖掘需要的所有资料, FP-Tree远远小于源数据与在关联规则挖掘步骤中生成的候选项集的大小。而且, 在频繁项集中的项按支持度从低到高的顺序来陈列, 支持度越低的项和FP-Tree的根离得越远, 所以有许多的项是共享的。
2 FP-Growth算法描述
和Apriori算法的不一样, FP-Growth算法中频繁项集的产生是通过两步展开的, 首先是构造FP-Tree, 其次是在FP-Tree的基础上对产生的树展开搜索来构造频繁项集。基本的方法如下:
步骤2.1:构造FP-Tree:
输入:一个交易数据库ZX和一个最小支持度y。
输出:它的FP-Tree。
步骤:
1) 搜索数据库ZX一次, 获得频繁项的合集F和所有频繁项的支持度。将F按支持度从高到低的顺序, 结果记为L。
2) 构造FP-Tree的根节点, 记做Q, 标记为null。然后对ZX里的所有因素Trany做下面的方法。按照Y中的安排, 找到Trany中的因素项。将Trany中已经排好的因素项列表记做[f], 其中f是第一个项, f是列表余下的部分。选择inyert_tree ([f], T) 。
函数inyert_tree ([f|f], T) 的步骤如下:
假如Q有一个子结点N, 当N.item-name=p.item-name, 那么把N的count域值增加1;要不然, 构造一个新节点M, 让它的计数为1, 让它的父节点为R, 而且让它的节点链接和那些有着同样项名域连接。假如P非空, 就递归调用inyert_tree (T, M) 。
步骤2.2:对FP-Tree展开搜索, 步骤如下:
FP-Growth方法把找到模式的因素改变成递归地找到一些短模式, 然后和扩展相连。它选择最不频繁的项作扩展, 供应了好的使用性。这个方法很大程度上减少了花费。在数据库非常大时, 创建在内存基础上的FP一树是不可能的。一种不可思议的换算是第一将数据库分为投影数据库的合集, 第二在所有投影数据库上创建FP一树而且搜索它。这个步骤能够递归地适用于投影数据库, 假如其FP-Tree还无法装入内存。相较于FP-Tree办法的用途开发说明:相较于挖掘长和短的模式, 它都是简单的和有序的, 而且比其他的方法快。它也比树-投影算法快。
FP-Growth算法开创了简单快速挖掘的新方法。但是, 它在时间和空间效率方面还存在不足, 还需要慢慢的进步。
参考文献
[1]鲁文伟。数据挖掘与最优化技术及其应用[M].天津科学出版, 2012.127-131
[2]陈之哲。数据挖掘在高校图书馆中的应用[J].学习出版社, 2010 (8) ;33-36
[3]王倩。基于数据仓库的数据挖掘技术[M].中国农业出版社, 207;136-138
