数据流分类算法分析（精选7篇）
数据流分类算法分析 篇1
数据挖掘(Data Mining),又称为数据库中的知识发现(Knowledge Discovery in Database,KDD),就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程,简单的说,数据挖掘就是从大量数据中提取或“挖掘”知识[1]。数据挖掘利用了来自如下一些领域的思想:1)来自统计学的抽样、估计和假设检验;2)人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。数据挖掘也迅速地接纳了来自其他领域的思想,这些领域包括最优化、进化计算、信息论、信号处理、可视化和信息检索。一些其他领域也起到重要的支撑作用。特别地,需要数据库系统提供有效的存储、索引和查询处理支持。源于高性能(并行)计算的技术在处理海量数据集方面常常是重要的。分布式技术也能帮助处理海量数据,并且当数据不能集中到一起处理时更是至关重要。数据挖掘包含的内容很多,其中很重要的一个方面是分类规则挖掘。
分类技术在很多领域都有应用,其中比较典型的应用就是在客户关系管理系统中,可以将客户分成不同的类别,比如呼叫中心设计时可以分为:呼叫频繁的客户、偶然大量呼叫的客户、稳定呼叫的客户、其他,帮助呼叫中心寻找出这些不同种类客户之间的特征,这样的分类模型可以让用户了解不同行为类别客户的分布特征;其他分类应用如文献检索和搜索引擎中的自动文本分类技术;安全领域有基于分类技术的入侵检测等等。机器学习、专家系统、统计学和神经网络等领域的研究人员已经提出了许多具体的分类预测方法。下面对几种主要的分类方法作简要的研究与探讨:
1 基于判定树的归纳分类
判定树是一个类似流程图的树结构,其中每个内部节点表示在一个属性上的测试,每个分支代表一个测试输出,而每个树叶节点代表类或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“IF-THEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径,路径上的每个属性-值对形成“IF”部分的一个合取项,树叶节点包含类预测,形成“THEN”部分。一条路径创建一个规则。判定树归纳的基本算法是贪心算法。
算法描述如下:判定树归纳分类[2]是一种从训练样本集中推理出判定树表示形式的分类规则的方法。它采用自顶向下的递归方式,判定树的最顶节点是根结点,树的内部结点表示在一个属性上的测试,从该结点向下的每个分支代表一个测试输出,在树的叶结点得到分类预测。从根到叶结点的一条路径就对应着一条合取规则,整棵判定树就对应着一组析取表达式规则。判定树的优点在于它的直观性和易理解性,判定树方法不仅能做出分类和预测,而且它的生成过程、分类、预测以及从判定树所提取的分类规则都具有很强的可理解性。
算法策略如下:(1)判定树以代表训练样本的单个节点开始;(2)如果样本都在同一个类,则该节点成为树叶,并用该类标记;(3)否则,基于启发式或统计式策略选择能够最好地将样本分类的属性,将样本分类;(4)对测试属性的每个已知的值,创建一个分枝,并以此为根据划分样本;(5)使用同样的过程,递归地形成每个划分上的样本判定树。
停止划分的条件:给定节点的所有样本属于同一类:没有剩余属性可以用来进一步划分样本,此时使用多数表决(用训练集中的多数所在的类标记它);没有样本剩余。
2 KNN法(K-Nearest Neighbor)
KNN(K Nearest Neighbors)算法[3]又叫K最临近方法,总体来说KNN算法是相对比较容易理解的算法之一,假设每一个类包含多个样本数据,而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类,KNN就是计算每个样本数据到待分类数据的距离,取和待分类数据最近的K各样本数据,那么这个K个样本数据中哪个类别的样本数据占多数,则待分类数据就属于该类别。
KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。因此,采用这种方法可以较好地避免样本的不平衡问题。另外,由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
该方法的不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。另外还有一种Reverse KNN法,能降低KNN算法的计算复杂度,提高分类的效率。
该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
3 VSM法
VSM法即向量空间模型(Vector Space Model)法,由Salton等人于60年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量:D=D(T1,W1;T2,W2;…;Tn,Wn),然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候,文本的相似度就可以借助特征向量之间的内积来表示。
在实际应用中,VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间。当需要对一篇待分样本进行分类的时候,只需要计算待分样本和每一个类别向量的相似度即内积,然后选取相似度最大的类别作为该待分样本所对应的类别。
由于VSM法中需要事先计算类别的空间向量,而该空间向量的建立又很大程度的依赖于该类别向量中所包含的特征项。根据研究发现,类别中所包含的非零特征项越多,其包含的每个特征项对于类别的表达能力越弱。因此,VSM法相对其他分类方法而言,更适合于专业文献的分类。
4 Bayes法
Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法,待分样本的分类结果取决于各类域中样本的全体。
设训练样本集分为M类,记为C={c1,…,ci,…c M},每类的先验概率为P(ci),i=1,2,…,M。当样本集非常大时,可以认为P(ci)=c类样本数/总样本数。对于一个待分样本X,其归于cj类的类条件概率是P(X/ci),则根据Bayes定理,可得到cj类的后验概率P(ci/X):
P(ci/x)=P(x/ci)·P(ci)/P(x)(1)
若P(ci/X)=Maxj P(cj/X),i=1,2,…,M,j=1,2,…,M,则有x∈ci(2)
(2)式是最大后验概率判决准则,将(1)式代入(2)式,则有:
若P(x/ci)P(ci)=Maxj[P(x/cj)P(cj)],i=1,2,…,M,j=1,2,…,M,则x∈ci,这就是常用到的Bayes分类判决准则。经过长期的研究,Bayes分类方法在理论上论证得比较充分,在应用上也是非常广泛的。
Bayes方法的薄弱环节在于实际情况下,类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的。为了获得它们,就要求样本足够大。另外,Bayes法要求表达文本的主题词相互独立,这样的条件在实际文本中一般很难满足,因此该方法往往在效果上难以达到理论上的最大值。
5 神经网络
人工神经网络的研究至今已有60多年的历史。1943年,心理学家Mc Culloch和数学家Pitts合作,提出了形式神经元的数学模型,即MP模型[4],从此,神经网络引起了许多科学家的兴趣。但随着对感知机为代表的神经网络的功能和局限性的深入分析等原因,使神经网络的研究陷入低潮。但是仍有一些学者坚持研究,并取得了一些成果,出现了Grossberg的ART模型和Kohonen的SOM模型。1982年,通过引入能量函数的概念,Hopfied研究了网络的动力学性质,并用电子线路设计出相应的网络,进而掀起了神经网络新的研究高潮。1986年,Rumellhart和Mc Cllel-land等提出了PDP理论,尤其是发展了多层前向网络的BP算法,成为迄今应用最普遍的学习算法。
神经网络可解决目前数据挖掘存在几个方面的问题:
1)数据的量度和维度,面对大量复杂、非线性、时序性与噪音普遍存在的数据;
2)数据分析的目标具有多样性,使其在表述和处理上都涉及到领域知识;
3)在复杂目标下,对海量数据集的分析,目前还没有现成的且满足可计算条件的一般性理论的方法。然而,神经网络在对噪声数据的高承受能力以及对未经训练的数据分类模式的能力方面有很大优势。因此设计出基于神经网络的数据挖掘方法,并将其用于真实世界问题,是可行且也是必要的。
人工神经网络可用于数据挖掘的分类、聚类、特征挖掘、预测和模式识别等方面,因此,人工神经网络在数据挖掘中占有举足轻重的作用。
总之,数据挖掘技术是一个年轻且充满希望的研究领域,商业利益的强大驱动力将会不停地促进它的发展。每年都有新的数据挖掘方法和模型问世,人们对它的研究正日益广泛和深入。尽管如此,数据挖掘技术仍然面临着许多问题和挑战:如数据挖掘方法的效率亟待提高,尤其是超大规模数据集中数据挖掘的效率;开发适应多数据类型、容噪的挖掘方法,以解决异质数据集的数据挖掘问题;动态数据和知识的数据挖掘;网络与分布式环境下的数据挖掘等;另外,近年来多媒体数据库发展很快,面向多媒体数据库的挖掘技术和软件今后将成为研究开发的热点。
摘要：数据挖掘技术是一个崭新研究领域,随着信息技术日新月异的发展,数据库技术在不同行业领域的大规模应用,数据库的规模急剧膨胀。在诸多商业需求的驱动下,数据挖掘已成为当今研究的热点,每年都有新的数据挖掘方法和模型问世,特别是其中的分类问题,引起了越来越多的关注,本文对数据挖掘中的分类算法就行了归纳研究。
关键词：数据挖掘,分类,算法
参考文献
[1]范明,孟小峰.数据挖掘:概念与技术[M].北京:机械工业出版社,2001.
[2]王旅,彭宏,胡劲松.基于判定树归纳分类的土质分类定名方法[J].计算机工程与设计,2006,27(11):1929-1931.
[3]王燕,李睿,李明.数据挖掘技术应用研究[J].甘肃科技,2001,17(1):49-50.
[4]毛国君,段立娟,王实,等.数据挖掘原理与算法[M].北京:清华大学出版社,2007.
数据流分类算法分析 篇2
关键词：数据挖掘,分类算法,训练样本,Margin曲线
我国是全世界最大的烟草生产国与消费国, 不同地域下不同种类的烟草销售情况又有不同之处。因此, 通过计算机智能算法进行分类进而辅助企业决策, 这样对烟草企业的销售有很大提升作用。一个好的分类算法在这里十分重要。分类算法是数据挖掘中最重要的技术之一, 它的目标是从数据集中提取能够描述类基本特征的模型, 并利用这些模型把数据集中的每个对象都归入到其中某个已知的数据类中[1]。分类和预测是在理论方法上基本一致, 其主要区别是分类的输出是离散的类标识, 而预测的输出是连续值。本文重点讨论面向烟草企业的分类算法。
分类算法分为两个阶段:一、通过训练构造分类模型; 二、分类模型应用于测试样本得到样本分类信息[2];主要的难点是构造准确、高效的分类模型。训练样本T中, 所有样本将被分类到m个类标识 { C1, C2, … , Cm}, T形式化的表示为{ a1, a2, … , av:Ci}, Ci (i=1, 2, …, m) , aj (j =1, 2, …, v) 表示样本属性。分类算法的计算代价也主要集中于分类模型的构造。
分类方法的评价主要基于以下5项标准:
预测的准确性:指样本数据中正确分类所占的比例;速度:指产生模型和使用模型进行分类的时间代价, 由于产生模型所需要的时间占总时间的绝大部分, 所以实验中主要以模型产生时间作为分类方法速度衡量标准;鲁棒性: 指对噪声数据或有空值得数据, 模型正确预测的能力;可处理数据量:指对大量数据有效构造模型的能力, 主要是指解决驻留磁盘数据的能力;可理解性:指模型提供的理解的层次。
数据挖掘分类模型的构造方法目前包括:决策树方法、统计方法、机器学习方法、神经网络方法、类比学习方法、遗传算法、粗糙集方法、模糊集方法、基于案例的推理方法等。本文以决策树方法中的C4.5算法, 统计方法中的Bayesian置信网络, 机器学习方法中SMO方法为重点, 详细分析在数据挖掘系统中使用最为广泛的三种分类算法的综合性能。
一、算法介绍
1、C4.5 算法
C4.5算法是对著名的决策树归纳算法ID3的改进版本, 结合了剪枝算法去除了不可能分支和过拟合 (overfitting) 分支, 以此避免了过拟合问题, 并大幅度提高了计算速度。
C4.5算法通过训练样本集构造一个决策树。设训练样本为T, 样本共分为m个不同的类Ci (i=1, 2, …, m) 。设S是任意样本集, 具有|S|个数据样本, freq (Ci, S) 代表S中属于类Ci的样本数量, 则对一个给定的样本分类所需的数学期望信息为:
对训练样本集递归的应用树构造函数, 使得训练样本及其子集Ti建立决策树的分枝。假设我们要选择有n个输出 (有n个属性) 的检验, 也就意味这生成的决策树中需要有n个节点 (包括内部节点和叶节点) 。节点所在的层次决定于其代表的属性所还有的信息熵的大小。信息熵越大, 表示分裂属性越好, 越适合作为高层节点。
设属性A具有v个不同的值{ a1, a2, … , av}, 用属性A将S划分为v个子集{ s1, s2, … , sv}, 其中任意sj表示它在A上具有值aj, sij是sj中类Ci的样本数。则A划分的子集的信息熵为:
对训练样本集T中的n个属性都计算其信息熵的值, 找出其中有最大信息熵的属性, 作为当前的分裂属性和决策树当前节点[3]。这是一个递归的过程, 每一个节点的确定都意味这一个新的训练样本的产生, 直到这个样本集中的所有样本都属于一个分类, 或样本集为空。
如果A为的信息熵最大, 则选为分裂属性, 在进行下一次递归之前需要求出A分支上的编码信息:
将A分支上的编码信息作为新训练样本集的数学期望信息。
C4.5算法的主要特点是准确性高, 分类模型构建速度较快, 但对训练样本数量和质量要求较高, 对空值的适应性较差;C4.5算法由于以决策树为基本形式, 因而理解性较好。在下一节中本文将对这些特点进行量化分析[4]。
2、Bayesian 置信网络
Bayesian分类的理论基础是统计学中的Bayesian定理:
该方法可以由Bayesian定理得到的后验概率计算类成员关系的可能性, 如给定样本属于一个特定类的概率。在计算过程中, 如果假设样本的属性对给定类的影响是独立于其他属性的, 则可以使用朴素Bayesian分类方法, 这一假设条件称为类条件独立。这种看似简单的朴素Bayesian分类算法在满足类条件独立假设的前提下, 其精度和计算速度可以达到, 有时甚至超过前面提到的C4.5决策树算法和一些神经网络分类算法[5]。
但在实践过程中, 分类结果与属性之间的关系无法保持独立, 为了是Bayesian分类方法有更广泛的适用性, 产生了Bayesian置信网络。Bayesian网络近年成为数据采掘引人注目的研究方向。与其它分类方法相比, Bayesian网络的优点是可以综合先验信息和样本信息, 这在样本量稀少时特别有用;可以发现数据之间的因果关系, 适合于处理不完整数据集。这是其它模型难以做到的。其缺点是计算开销较大;确定合理的选验密度比较困难; 如何判定实际问题是否满足所要求的假设, 没有现成的规则。
Bayesian置信网络的训练过程主要目的是为每一个属性生成一张条件概率表 (CPT) 。网络以梯度下降法训练置信网络, 以克服不完整数据问题。设S是s个训练样本X1, X2, …, Xs的集合, wijk是具有父节点Ui=uik的变量Y=yij的CPT表项。训练过程中寻找的最大概率值。
搜索最大概率值的过程按照梯度方式进行, 对于每一个属性i, 有父节点k, 其及其相应的属性变量取值j, 进行计算:
Bayesian置信网络的主要特点是模型构建速度快, 对训练样本数量和质量的要求较C4.5算法为低, 有着较好的适用性, 但预测精度在同等条件下较C4.5算法和SMO方法为低。
3、SMO
机器学习方法在今年来有了长足的进步, 应用也日益广泛, 其中代表性的一类方法是支持向量机 (Support Vector Machines, 简称SVM) 。SVM以统计学习理论为基础, 具有简洁的数学形式、直观的几何解释和良好的泛化能力, 是一种解决分类、回归、概率密度估计等问题的有力工具, 在手写数字识别、图像识别、时间序列动作预测等许多实际应用中取得了成功。
Platt于1999年提出的序贯最小优化 (Sequential Minimal Optimization, 简称SMO) 算法经过不断的改进, 成为目前较为有效的SVM训练方法, 但是确定工作集的可行方向策略会降低缓存的效率[6,7]。
SMO方法的优势:可以解决小样本情况下的机器学习问题;可以提高泛化性能;可以解决高维问题;由于采用了凸优化算法, 避免了神经网络结构选择和局部极小点的问题。
SMO的不足之处:构建和训练分类模型的时间较长, 超过C4.5算法和Bayesian置信网络方法一个数量级。
二、实验分析
面对烟草行业的大背景, 我们使用来自真实烟草企业的销售数据对上面提到的分类算法进行验证以及分析。实验数据:segment.csv;数据收集人:Carla Brodley, 马萨诸塞州大学。实验数据中包含1500条记录, 每条记录有19项属性, 共28500个数值;数据中包含部分空值;分类目标是将1500条记录划分为7个指定类 (设7个类标识符为a b c d e f g) 。计算平台:CPU AMD3000+;内存2G;操作系统Windows XP SP2;采用10折交叉验证方法对分类模型进行评估。
1、C4.5 实验分析
C4.5决策树分类方法建立模型所花费的时间:0.38 seconds;在1500条记录中正确分类的有1436, 准确度达到95.7333%。表1-a表示每个属性被分类的情况, 其中对角线部分表示正确分类的样本数据, 横向表示该属性的所有记录被分类情况, 纵向表示分类结果中, 该属性包含的记录 (包含了错误分类结果) 。表1-b中TP_Rate计算该属性被正确分类的概率;而TP_Rate计算在所有被分配为该属性的记录中的错误率;Precision计算该属性的总体精度;Recall评估模型在该属性上的覆盖率。
图1中的Margin曲线表明:C4.5算法构建的模型在样本数大于300后, 分类趋于稳定, 计算代价也处于较低水平;但样本点在100以下时分类准确性偏低, 而且计算代价较高, 样本点超过100后准确性大幅度提高, 而且计算代价也大幅度下降了。
2、Bayesian 置信网络的实验分析
Bayesian置信网络分类方法建立模型所花费的时间: 0.27 seconds;在1500条记录中正确分类的有1356, 准确度90.4%。
图2的Margin曲线:同C4.5类似, 样本数大于300后, 分类趋于稳定, 计算代价大幅度下降;但整个收敛过程更加平缓, 说明贝叶斯置信网络对于样本的增加所带来的精度提高以及计算代价的下降没有明确的。
3、SMO 实验分析
Bayesian置信网络分类方法建立模型所花费的时间: 2.77 seconds;在1500条记录中正确分类的有1379, 准确率为91.9333 %。
图3的Margin曲线表明:SMO方法在小样本环境下表现了惊人的收敛速度, 精度迅速提高, 计算代价也大幅度下降;但在样本数据增加后, 其精度和计算代价都较上述两种算法表现得为差。
三、总结
通过在具体烟草企业销售数据上使用不同分类算法进行实验, 我们可以得出一些较为重要的结论。在模型构建速度方面, Bayesian置信网络花费的时间最短, SMO机器学习方法花费的时间最长, 是Bayesian置信网络的10倍;准确度方面C4.5算法精度最高, Bayesian置信网络在三种算法中最低;鲁棒性方面以SMO方法最佳, 在极小的训练样本下表现了极高的分类准确度, C4.5算法的鲁棒性最差, 在训练样本不足时准确性难以提高;在可理解性方面C4.5算法以其决策树的表达形式表现最好。
实验证明烟草企业通过分类算法进行实际应用时, 如果拥有质量较高、数量比较充足的训练样本, C4.5是最佳选择;但实际中, 大多数情况能够获取的训练样本总是很有限, 数据中包含空值, 这也就是SMO方法在实践中经常被采用的原因;如果对计算速度、准确性、鲁棒性都有一定程度的要求时适合采用Bayesian置信网络。
参考文献
[1]Chen H, Chiang R H L, Storey V C.Business Intelligence and Analytics:From Big Data to Big Impact[J].MIS Quarterly, 2012, 36 (4) :1165-1188.
[2]Yi Penga, Guoxun Wanga, Gang Kou.An empirical study of classification algorithm evaluation for financial risk prediction[J].Applied Soft Computing Volume 11, Issue 2, March2011, Pages 2906–2915.
[3]V.Bolón-Canedo, N.Sánchez-Maro?o, A.Alonso-Betanzos.Feature selection and classification in multiple class datasets[J].An application to KDD Cup 99 dataset Expert Systems with Applications, 38 (5) (2011) .
[4]Amuthan Prabakar Muniyandia, R.Rajeswarib, R.Rajaram.Network Anomaly Detection by Cascading K-Means Clustering and C4.5 Decision Tree algorithm[J].Procedia Engineering Volume 30, 2012, Pages 174–182.
[5]Jao-Hong Chenga, Huei-Ping Chena, Yi-Min Linb.A hybrid forecast marketing timing model based on probabilistic neural network, rough set and C4.5[J].Expert Systems with Applications Volume 37, Issue 3, 15 March 2010, Pages 1814–1820.
[6]Zhaonan Sun, Nawanol Ampornpunt, Manik Varma.Multiple Kernel Learning and the SMO Algorithm[J].Advances in Neural Information Processing Systems 23 (NIPS 2010) .
[7]Dattola R T.A fast algorithm for automatic classification[J].Information Technology and Libraries, 2013, 2 (1) :31-48.
[8]Culotta Aron.Lightweight methods to estimate influenza rates and alcohol sales volume from Twitter messages[J].Language resources and evaluation, 2013, 47 (1) :217-238.
数据流分类算法分析 篇3
本文主要着重于数据分类分析的训练阶段,同时根据目前数据分类技术的情况,可以把数据分类技术分为决策树类、Bayes类、基于关联规则类以及利用数据库技术类等几类算法进行叙述。
1 决策树分类算法
在决策树分类算法中比较典型,提出时间也比较早的非C4.5算法莫属,但是随着计算机技术和信息技术的发展,C4.5算法已经满足不了越来越复杂的数据分类算法,因此为是适应大规模数据集的处理,C4.5在发展过程中又不断演变,在发展过程中又出现了多种基于C4.5算法的新技术,其中比较常用也比较典型的有SPRINT和SLIQ算法。
1.1 C4.5算法
1.1.1算法简介
由于C4.5算法比较抽象,为了简洁明了的对C4.5算法进行准确的描述,本文以集合为载体对C4.5算法进行描述。我们假设一个全集T,在对T构造决策树时,根据Information Gain值选择作为分裂结点的属性及标准,可以把集合T分成n个子集。并规定Ti表示集合T的第i个子集,若子集内的元素具有某一相同的特性,则该结点就成为决策树的叶子结点而停止分裂。对于剩下的子集,重复上述步骤,直至所有的元素都被集合在相应的类别中。
1.1.2算法分析
相比传统的数据分类算法如统计方法、神经网络方法相比较,决策树分类算法有许多明显的优点。比如,决策树分类算法的数据分类规则简单明了,比较容易理解,在实际操作中不易出错。
尽管决策树数据分类算法有着诸多优点,但是决策树数据分类算法也有诸多缺点。由于决策树对数据的分析过程决定了,在数据分类过程中,特别是在构造树的过程中,不可避免的需要对数据进行多次顺序扫描和排序,这势必会导致整个数据分析过程变得缓慢。同时由于C4.5的特点,使得C4.5算法的适用范围也有限,只适合于能够驻留于内存的数据集使用,当训练集大得无法在内存容纳时程序无法运行。
1.2 SLIQ沿算法
所谓的SLIQ算法实际是基于C4.5算法演变而来,对C4.5算法进行了多处改进,同时在数据分类分析过程中采用了预排序和广度优先两种技术。接下来,下文将对预排序技术和广度优先技术进行简单的介绍。
1.2.1算法描述
(1)预排序
在前文中讲到,在进行大量数据分类分析时,需要对每一个数据的特性进行分析,并按照相应的规则对每个数据分析,由于数据量比较大,使得数据的分析排序过程比较慢,造成了数据分类过程效率低下,为了解决上述问题,便引入了预排序的技术,以便能够消除在决策树的每个结点对数据集进行排序的需要。所谓预排序,就是以数据的共同特点为依据,从而快速对数据进行排序。
(2)广度优先策略
由于C4.5算法的特点,决策树的结构是按照深度优先策略完成的,所以在数据分类分析过程中必须对每一个关键节点进行分析,效率极其低下。但是采用广度优先策略技术之后,仅仅需要对每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶子结点找到最优分裂标准。
(3)SLIQ算法分析
SLIQ算法基于C4.5算法技术在很多方面进行了完善,并且也采用了与排序技术和广度优先策略技术,使得SLIQ算法技术在一定程度上具有良好的记录个数和属性个数增长的可扩展性。但是在实际数据分类过程中,仍然存在下述问题需要解决:又在数据分析过程中,数据全部暂时存放于内存中,与此同时数据特性列表的长度和数据训练集的长度一样,上述情况使得SLIQ算法实际可以处理数据集的大小收到了一定程度上的限制。同时由于采用了预排序技术,使得SLIQ算法不可能达到随记录数目增长的线性可扩展性。
1.3 SPRINT算法
正如前文所讲,又在SLIQ算法中,所有的数据都储存在内存中,使得SLIQ算法处理数据集的大小有限,为了解决上述问题,SPRINT算法便应运而生。为了尽可能的避免大量需要处理的数据存储在内存中,SPRINT算法对决策树算法的数据分析结构做出了相应的改变,特别是删除了SLIQ算法中需要存储在内存中的数据类别列表,取而代之的是把数据类列表融合到每个数据数的属性列表中,采用这种方法的好处是,在进行大量数据分析时,在遍历每个属性列表寻找当前结点的最优分裂标准时,可以避免反复的数据分析。数据的相关属性分别存放属于各个结点的记录,使得数据的分类分析变得比较简单。但是SPRIT算法也不是万能的,其使用范围受到了限制,对于非分裂属性的属性列表进行分裂就显得不适用,使得这种算法的拓展性不够强。
2 Bayes分类算法
Bayes分类算法是目前数据分类算法中比较重要的一类数据分类算法,与概率统计学知识有着密不可分的关系,由于贝叶斯定理的特点,使得该算法在对数据的特性进行分析的过程中,需要做出相应的假设性前提,而在实际的数据分类分析过程中,这种前提性假设往往过于理想化,在实际情况中并不成立,使得数据分类准确性就会下降。基于上述原因,TAN算法便应运而生。
2.1 TAN算法
TAN算法的提出是为了降低NB中任意属性之间独立的假设。TAB算法在NB网络结构中的结构示意图如1所示。
上述示意图中的每一个顶点代表一个随机变量,每一边表示每个随机变量之间特有的关系。其中虚线表示NB所需的边,而实线代表是新增的边。
3 基于关联规则的分类算法
3.1 CBA 算法描述
所谓的CBA分类数据算法与关联规则密不可为,通常而言,在该种算法中同样需要数据构造分类器,在构造CBA算法中的数据构造器是需要如下两个步骤,首先发现所有的右部为类别的类别关联规则,通常称为CAR。其次是从第一个步骤中的CAR中,选择合适的数据集。
3.2算法分析
在CBA算法中主要用到的是Apriori算法技术,通过Apriori算法技术可以使不易发现的数据关联规则显现出来。通常而言,为了确保该算法在对数据进行分类时不发生漏缺情况,需要把最小支持度取值为0,但是这样又使得该算法不能充分发挥其优化作用,最终使得该算法运行效率低下。
4 基于数据库技术的分类算法
基于数据库技术的分类算法是数据分类算法技术的发展方向,该算法首先是由研究数据库的人员发现并提出的,虽然基于数据库技术的分类算法已经出现很长时间,但是在实际数据分类算法的应用中,并没有用到与数据库相关的技术。之所以出现上述问题是由于数据挖掘应用很难与数据库系统集成,为了解决上述问题, MIND和GAC-RDB算法应运而生。
4.1 MIND 算法
4.1.1算法描述
MIND算法在构造数据分类器时与决策树算法相似,数据分析的过程也与SLIQ有相同之处。但是MIND在数据分类算法中采用了与数据库相关的UDF方法和SQL语句。
4.1.2算法分析
决策树分类算法在分析数据时需要对每个节点的数据特性进行分析,既费时又费力,但是在MIND算法中,上述过程主要通过UDF实现。使得分类算法易于与数据库系统集成。但是MIND算法并不能直接利用数据库的查询功能,同时该算法的维护也比较复杂。
4.2 GAR-RDB算法
4.2.1算法描述
GAR-RDB算法充分利用了关系数据库系统提供的聚集运算功能,在数据分析过程中主要用到的是SQL语句。通过对数据集的属性进行分析从而选择一个最好的分裂属性,并进行相应的排序。
4.2.2算法分析
该算法与其他方法相比分类准确迅速,执行速度有较大提高,同时可拓展性也比较好,也可以充分利用数据库提供的查询功能,从而避免对数据集重复地进行扫描,也不需要对训练集转换成交易型数据库格式。但是该种算法在自动地确定参数的取值等方面还需要改进。
5 结束语
浅析数据挖掘中的分类算法 篇4
1 数据挖掘中的不同分类算法
1.1 分类训练算法
针对分类算法中,分类训练算法就是针对训练样本多的样本,其中大多为非支持数据信息 , 占用了计算和内存上的大量资源 , 在每次的优化过程中 , 通过迭代方式排除非支持数据信息,只保留当前支持数据信息 , 节省计算时间与内存空间。数据挖掘中,采用分类算法,可以随机选择较少样本作初始样本集,在问题求解后从结果内去掉非支持数据信息 , 再根据训练结果对剩余样本数据进行检验 , 然后再将不符合优化条件的一部分样本与数据合并,使其成为新的训练样本集 , 重新训练,直到获得最优训练结果。
1.2分类决策算法
分类决策算法中,应用决策树作为预测模型,决策树代表的是对象属性同对象值间映射关系。决策树中每个节点表示某个对象,而决策树每个分叉路径,则代表决策树中的某个可能属性值,而决策树中的每个叶结点,则对应从决策树根节点到该叶节点中,所有经历的路径对象值。在决策树中不仅有单一输出,还包含有复数输出,可以建立独立决策树,这样就可以处理不同输出。
1.3 SLIQ分类算法
SLIQ分类算法对分类决策树算法进行改进,采用“预排序”、“广度优先”两种技术。可以在决策树的每个结点上,都对数据集进行排序,并且为需要进行训练集的数据,在每个的属性上创建出一个属性列表,给每个元组类别上创建类别列表,利用数据库保存类别列表,有效提升算法计算速度。
2分类算法在数据挖掘中的应用实例分析
2.1应用分类算法实例一
应用分类算法可以挖掘出有用的煤矿瓦斯控制信息,对改善企业的发展进度产生积极影响。首先可以先建立决策树,然后再根据在瓦斯监测中的数据特点 , 将状态维作为本次的分类类别。取正常状态维是P类 ( 正例 ) , 报警状态维是Q类 ( 反例 ) ,然后建立相应的决策树进行数据挖掘。如下图1中所示 :
在本次所建立的决策树中,包括甲烷传感器、传感器以及风速传感器,对每个维成员的数据信息进行增益率计算 , 将传感器最大信息增益率维当做一个决策属性的节点 , 在通过为属性的取值来建立本节点的分支。要求分类面能将两类样本点分开,并且保证两分类空隙最大。对于其d维空间中的线性判别函数,若是一般形式为,则分类面方程就是,然后在将判别函数进行归一化,确保两类样本满足,分类面样本都正确分类
两类样本的分类空隙间隔大小为 :
最优分类面表示成约束优化问题,求函数最小值
可以定义函数Lagrange :
基于决策树的数据挖掘里面瓦斯浓度维,计算出信息的增益率 , 以此来作为决策树中的根结点,提高数据挖掘的效益。
2.2应用分类算法实例二
针对校园教学系统,对其数据进行数据挖掘,应用分类算法进行数据挖掘,首先,就是应该确定出需要解决的一些目标问题,并设置数据挖掘模型。对于其数据挖掘步骤如下图2所示 :
分类是已知一共有多少类 , 并明确知道该类的特点 , 然后把未知的按一定规则分到某一个类中 ;分类可以多可以少 , 当然数据量大才能很好地说明分类算法的优异 . 但实际上分类算法在确定某些规则后 , 你可以只有一个未知的数据也可以把它分到某一个类别当中。
在分类算法中,还可以可以应用模糊分类的 方法,对U之中国的 单因素Ui(i=1,2,…,m),可以对其进行单因素的评价,然后可以根据因素ui来确定处事物的评价等级,计算出隶属度,可以得到向量,从而得到评价矩阵 :
R作为因素集U以及评价集V的模糊关系,可以用 (ui,vj)=rij来表示因素u。还可以进行模糊变换实现综合评价 :
3结语
综上所述,针对数据挖掘中,应用分类算法,不仅可以提升数据挖掘中算法运行效率,还可以在数据挖掘中动态调用不同分类算法,使数据挖掘工作可以在稳定、高效环境中进行,对数据进行分类,大大提高数据挖掘中算法的性能与效率,发挥实际应用价值。
摘要：分类算法在数据挖掘中的应用,可以避免出现传统数据挖掘弊端,同时提高挖掘数据的应用有效性。本文结合具体实例,分析数据挖掘中的分裂算法。
数据流分类算法分析 篇5
随着社会的进步和经济的发展,社会各领域活动中会不断产生大量的数据,人们把这些按照一定的数据模型保存在数据库中。数据库中隐藏着许多可以为商业和科研等活动的决策提供所需要的知识,如何有效地获取这些知识,数据挖掘技术中的分类方法正是解决这个问题的可行而有效的方法。
分类方法是一种重要的数据挖掘技术,分类的目的是根据数据集的特点构造一个分类函数或分类模型,该模型能把未知类别的数据映射到给定类别的某一个中。该方法通常用于预测数据对象的离散类别。目前分类方法已被广泛应用于各行各业,如银行信用评估、医疗诊断、高等教育评估和市场营销等实际应用领域。本文将对数据挖掘分类方法中的决策树算法加以分析。
二、数据分类技术概述
数据分类过程主要包含两个步骤:第一步建立一个描述已知数据集类别或概念的模型;该模型是通过对数据库中各数据行内容的分析而获得的。每一数据行都可以认为是属于一个确定的数据类别,其类别值是由一个属性描述(即类别属性)。分类学习方法所使用的数据集称为训练样本集和,因此分类学习又称为监督学习,它是在已知训练样本类别情况下,通过学习建立相应模型;而无监督学习则是训练样本的类别与类别个数均未知的情况下进行的。通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学形式。
第二步就是利用所获得的模型进行分类操作,首先对模型分类准确率进行估计,holdout方法就是一种简单的估计方法。它利用一组带有类别的样本进行分类测试(测试样本随机获得且与训练样本相互独立)。对于一个给定数据集所构造出模型的准确性可以通过由该模型所正确分类的数据样本各书所占总测试样本比例得到。
为了提高分类的准确性、效率和可扩展性,在进行分类之前,通常要对数据进行以下预处理。
1. 数据清理。主要帮助出去数据中的噪声,并妥善解决遗失数据的问题。
2. 相关性分析。其目的是删除那些与分类任务不相关的或冗余的属性。
3.数据转换。利用概念层次树,数据能够被泛化到更高的层次。例如属性“收入”的数值就可以被泛化为“低、中等、高”的离散区间。
以数据库为研究对象,数据挖掘分类模型的构造算法主要有决策树、贝叶斯、神经网络、基于关联和基于数据库技术的方法等。
三、决策树(decision tree)分类算法
所谓决策树就是一个类似流程图的树型结构,决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部节点进行属性值的比较,并根据不同的属性值从该结点向下分支,其中树的每个内部节点代表对一个属性的测试,叶结点是要学习划分的类。从根节点到叶结点的一条路径就对应着一条分类规则,整个决策树就对应着一组析取表达式规则。树的最高层点就是根节点。
决策树的生成分为学习和测试两个阶段。决策树学习阶段采用自顶向下的递归方式。决策树算法分两个步骤:一是树的生成,开始时所有数据都在根节点,然后递归地进行数据划分,直至生成叶结点。二是树枝修剪,在一个决策树刚刚建立起来的时候,它其中的许多分支都是根据训练样本集合中的异常数据(由于噪声等原因)构造出来的。树枝修剪就是去掉一些可能是噪声或异常的数据。决策树停止分割的条件是一个节点上的数据都是属于同一个类别;没有属性可以再用于对数据进行分割。决策树模型可以建立得很快,并适合应用到大量的数据上。
目前已经形成的决策树算法有:I D 3、C 4.5、S L I Q、SPRINT、Rain Forest、CLS、CHAID、CART、FACT、GINT、SEE5等。其中比较有著名的是Quinlan提出的ID3算法,以及在ID3算法基础上提出的C4.5算法。
1. ID3算法原理
基本决策树构造算法就是一个贪心算法,它采用自顶向下递归的方法构造决策树。著名的决策树算法ID3算法的基本策略如下:
(1)树以代表训练样本的单个节点开始。
(2)如果样本都在同一个类中,则这个节点成为树叶结点并标记为该类别。
(3)否则算法使用信息熵(称为信息增益)作为启发知识来帮助选择合适的将样本分类的属性,以便将样本集划分为若干子集。该属性就是相应节点的“测试”或“判定”属性。同时所有属性应当是离散值。
(4)对测试属性的每个已知的离散值创建一个分支,并据此划分样本。
(5)算法使用类似的方法,递归地形成每个划分上的样本决策树。一个属性一旦出现在某个结点上,那么它就不能再出现在该结点之后所产生的子树结点中。
(6)整个递归过程在下列条件之一成立时停止。
给定结点的所有样本属于同一类。
没有剩余属性可以用来进一步划分样本,这时候该结点作为树叶,并用剩余样本中所出现最多的类型作为叶子结点的类型。
某一分枝没有样本,在这种情况下以训练样本集中占多数的类创建一个树叶。
ID3算法的核心是在决策树各级结点上选择属性时,用信息增益作为属性的选择标准,以使得在每一个非结点进行测试时,能获得关于被测试记录最大的类别信息。某属性的信息增益按下列方法计算,通过计算得到每个属性的信息增益,比较它们的大小,就可以获得最大信息增益的属性。
设S是s个数据样本的集合。假设类标号属性具有m个不同值,定义m个不同类别。设Si是类别Ci中的样本个数,那么要对一个给定数据对象进行分类所需要的信息量为:
其中是任意一个数据对象属于类别的概率。其中log函数是以2为底,其原因是信息使用二进制编码。
设属性A具有v个不同的值。利用属性A可以将集合S划分为v个子集,其中Sj包含了S集合中属性A取值的数据样本。若属性A被选为测试属性,设Sij为子集中属于Ci类别的样本数。由A划分成子集的熵或信息期望可以计算如下:
熵值越小,子集划分的纯度越高。对于给定的子集Si,其信息期望计算为,其中是Sj中样本属于类别Ci的概率。
这样利用属性A对当前分支结点进行相应样本集合划分所获得的信息增益就是:
决策树归纳算法计算每个属性的信息增益,并从中挑选出信息增益最大的属性作为给定集合的测试属性并由此产生相应的分支结点。所产生的结点被标记为相应的属性,并根据这一属性的不同取值分别产生相应的分支,每个分支代表一个被划分的样本子集。
ID3算法的优点是理论清晰,方法简单,学习能力较强。其缺点是:
只能处理值是离散的属性,不能处理连续值的属性。
计算信息增益时偏向于选择取值较多的属性,不太合理。
对训练集合众属性值或类别给错的数据(即噪声)比较敏感。
在构造树的过程中需要多次扫描数据集,因而导致算法的低效。
只适合驻留于内存中的数据集使用,对训练集合大得无法在内存容纳的数据集无法运行。
2. 树枝修剪
在一个决策刚刚建立起来的时候,由于许多分支是由训练样本集和中的异常数据(由于噪声等原因)构造出来的,决策树过于“枝繁叶茂”,这样既降低了树的可理解和可用性,同时也使决策树本身对历史数据的依赖性增大,也就是说这是这棵决策树对此历史数据可能非常准确,一旦应用到新的数据时准确性却急剧下降,这种情况被称为训练过度。为了使得到的决策树所蕴含的规则具有普遍意义,必须对决策树进行修剪。树枝修剪的任务主要是删去一个或更多的树枝,并用叶子替换这些树枝,使决策树简单化,以提高今后分类识别的速度和分类识别新数据的能力。
通常采用两种方法进行树枝的修剪,它们分别是:
(1)事前修剪方法。该方法通过提前停止分支生成过程,即通过在当前节点上就判断是否需要继续划分该节点所含训练样本寄来实现。一旦停止分支,当前节点就成为一个叶节点。该叶节点中可能包含多个不同类别的训练样本。由于该修剪是在分支之前做出的,所以称之为事前修剪。
(2)事后修剪方法。该方法是从另一个角度解决训练过度的问题。它在允许决策树得到最充分生长的基础上,再根据一定的规则,剪去决策树中的那些不具有一般代表性的叶节点或分支。修剪后,被修剪的分支节点就成为一个叶节点,并将其标记为它所包含样本中类别个数最多的类别。
3. C4.5算法
C4.5算法在ID3算法的基础上,在以下几个方面进行了改进:
(1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性不足。
(2)在树构造过程中进行剪枝。
(3)能够完成对连续属性的离散化处理。
(4)能够对不完整数据进行处理。
C4.5算法产生的分类规则易于理解,准确率较高。但是和ID3算法一样在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,导致算法低效;此外,C4.5也只适合于驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。
4. 其他决策树算法
ID3算法和C4.5算法的有效性已经通过对许多小数据集的学习归纳得到了验证。但当应用这些算法对大规模现实世界数据库进行数据挖掘时,算法的有效性和可扩展性就成为应用的关键。近年来,数据挖掘领域中又提出了许多有关决策树可扩展问题的解决方法。其中比较有代表性的算法有SLIQ方法和SPRINT方法。
SLIQ算法对C4.5决策树算法的实现方法进行了改进,在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序,以消除在决策树的每个结点对数据集进行的排序。集体实现时,需要为训练数据集的每个属性创建一个属性列表,为类别属性创建一个类别表。广度优先策略构造决策树,即在决策树的每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶结点找到最优分裂标准。SLIQ算法由于采用了上述两种技术,使得该算法能够比C4.5大得多的训练集,在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。
SPRINT算法去掉了SLIQ中需要驻留于内存的类别列表,将其合并到每个属性列表中。这样,在寻找当前结点的最优分裂标准时,遍历每个属性列表就不必参照其他信息。但是,对非分裂属性的属性列表进行分裂变得很困难,需要用哈希表记录下每个记录属于个孩子结点。SPRINT算法具备以下优点:(1)训练样本量不受内存限制。(2)具有优秀的伸缩性、加速性和扩容性。(3)并行实现容易,效率高。SPRINT算法具备以下缺点:(1)使用属性列表,存储代价是原来的三倍。(2)节点分割要创建哈希表,加大系统负担。(3)节点分割处理相对复杂。
此外,Rain Forest也是一个基于决策树归纳的数据挖掘系统。Rain Forest可根据当前可用内存的大小,自适应地安排决策树归纳算法的具体操作过程。它保持一个AVC集合(属性—值,类别),用以描述每个属性的类别分布。Rain Forest的归纳速度要高于SPRINT方法。
四、结束语
以上是几种常用的基于决策树的分类算法,随着算法研究的进行,出现了许多其他基于决策树的算法,它们与神经网络、遗传算法等技术结合,从不同的方面对算法进行了改进和提高。我们也可以相信未来还会出现更多、更好、效率更高的分类算法。
参考文献
[1]Jiawei Han&Micheline Kambr.Data Mining:Concepts and Techniqyes[M].高等教育出版社,2001.
[2]毛国君段立娟:数据挖掘原理与算法[M].清华大学出版社,2005.7
数据流分类算法分析 篇6
1 决策树算法概述
数据挖掘就是从模糊地、不完全地、大量地、有噪声的、随机的以及原始数据中提取隐藏在那里面的潜在的、我们预先不知道的有用信息知识的挖掘过程。作为数据挖掘分类法中一个分支的决策树算法起源于概念学习系统。决策树算法就是使用树的结构对数据进行分类, 每个条件下的记录集就好比一棵树的叶节点, 人们根据字段数据取值的不同, 可以对决策树进行分支, 在决策树各个分支的子集中再重复建立分支和决策树各下层节点, 这样一棵决策树就形成了。
决策树算法最早是由Hunt等人提出来的, 目前最有影响的是ID3和C4.5[1]。ID3主要是选择运用信息最大属性的增益值来进行样本训练划分的, 其目的是能够使商在分裂系统时达到最小, 以此来提高决策树算法的精确度和运算速度。当然ID3算法也有其自身的缺陷, 例如可以运用信息增益作为分裂属性的标准, 但是这种行为在取值时会不自然地偏向于取值较多属性, 然而在大部分情况下, 这种属性都不能为我们提供许多有价值的信息。C4.5是在改进ID3的中得到的一种新算法, 这种算法不但能够对连续值的属性进行处理, 而且可以对离散值的属性进行很好的处理, C4.5选择测试的标准主要是采用信息增益比, 这在很大程度上弥补了ID3的一些不足, 除此之外, 我们还可以采用其他的一些决策树算法进行计算, 例如CART、QUEST、OC1、CAL5等。
2 决策树算法中遇到的问题
2.1 取值问题
一个决策树的建立, 必须要根据字段对不同取值的记录来建立对决策树进行分支, 并且在每个决策树的子集分支中反复建立下层的分支与节叶点, 构建决策树的关键在于对不同取值的分支阶段进行选择。选择不同的字段值, 也会使得子集计录的划分值各不相同, 不同的字段值还会对决策树结构的好坏和生长的快慢造成一定影响, 从而影响到信息规则寻找的优劣。因此, 构建一个好的决策树最主要的难点在于对分支取值进行良好的选择。好的分支取值的利用, 不仅能够对决策树的结构产生良好的作用, 还能够使决策树的生长速度起到良好的加快作用, 从而使人们找到一个较好的规则信息[2]。相反, 如果对决策树的分支仅仅只是依据一个比较差的取值来来决定, 不但会影响决策树的生长的速度, 还会导致结构性差和对决策树的分支过细这类不良现象的发生, 因而难以发现那些本就可以得到有用规则的信息。
2.2 数据过分近似问题
在决策树的运算过程中产生数据过分近似的原因主要有两点。 (1) 在寻找测试属性时各个属性在选择自己算法上都有自己的偏好, 因而非常有可能会找到算法的偏好, 可这并不是和种类真正相关的属性。想要在选择决策树时避免选到不相关属性是不容易确定的, 所以要从决策树中把相关的属性删除, 这种技巧也就是决策树的修剪法[3], 修剪法可以分为后修剪方法和前修剪方法。后修剪方法是当决策树生长完成以后进行剪枝, 前修剪方法主要是指在树的生长完成前就先进行剪枝。 (2) 由于物体本身的属性太多, 其中有些和种类不相关, 决策树算法很容易选到和自身种类不相关的属性。
3 决策树算法现状
可以采用决策树的算法共同对处理数据挖掘任务进行处理以得到有价值的模式和规则, 但以前使用的大多数决策树算法都是针对小数据的, 要求必须有常驻内存存在与训练集中, 这就导致了决策树算法在效率、精确度以及可伸缩性等方面受到很大的限制。在实际应用中的数据挖掘中, 我们所面临的大部分都是容量巨大的数据仓库或者数据库等一些数据集, 但是不能完全把这些数据集放入主存中, 在决策树的建构时需要把在缓存和主存中的数据进行导出或者导入, 这样可以极大地降低运算效果。针对以上的这些问题, 许多学者都提出了自己在挖掘数据分类法中利用决策树算法处理大型数据集的一些意见[4]。
3.1 抽样方法
在数据挖掘分类方法的实际运用中时可以利用抽样方法来提高决策树的效率, 当我们对这种数据算法的要求越高时, 往往这种算法也更加有效。在构建一棵决策树时我们可以抽样分析其中的数据集, 抽样分析还可以在产生节点的过程对进行, 利用抽样统计法来对整个数据库中的一个子集进行样本抽取分析就是抽样分析, 再用这个抽取的子集样本建构一个决策树, 继而从中抽取分类规则或者对未知样本进行分类。但是抽样分析法有其自身的缺点, 主要是, 决策通过抽样子集而产生只能获得大致的整个数据集信息, 这就很有可能把数据集中一些非常有价值的数据模式给漏掉。但是, 这种以牺牲精度对为代价从而提高运算效率的做法, 并不可取。
3.2 综合其他算法
模拟自然界在工程进化中的优胜劣汰原则进行计算的模型是遗传算法, 遗传算法是一种全局最优化的算法。在对数据进行求解的过程中, 通过变异、选择以及交叉等操作使不断优化群体, 从而寻求最优解。传统的决策树算法在决策树的构造过程中可能并不一定能够得到最优化的决策树, 将遗传算法和决策树算法二者结合起来可能会的得到一个精确度更高的决策树。根据上面的方法对决策树进行构建可以分为两种:一种方法是对决策树不进行编码, 而对决策树直接进行变异、操作、交叉以及选择[5]。智能的CAIT决策树算法可以把遗传算法、抽样算法以及决策树算法三者相互结合起来, 这能够在一定程度弥补以子集方法为基础的缺陷。另一种方法是将决策树进行编码, 例如CALTROT这种算法, CALTROT算法可以通过遗传算法来建构一个二叉决策树。在这个二叉决策树系统中, 遗传的染色体被当成决策树来看待, 在这个染色体中又包含了若干个二叉决策树的子集树, 每个决策子集树都是由两个分支和一个节点组成。通过对些染色体顺序排列的改变, 一组初始群体就能够我们建构出来, 通过再选择, 加之变异和交叉的共同运用, 从而就可以产生一棵最优秀的决策树。但是每个子集所产生决策树节点的个数和形状都是不同的, 因此, 在有些时候使用固定的长度位串来表示决策树是不合适的。
4 决策树算法发展趋势
除去一些科学的研究之外, 比如SAS、Spss[6]、MS Miner等商用软件中也都或多或少的设计到了也把决策树算法, 并且得到了广泛的应用。虽然数据挖掘中的决策树算法在现代发展中取得了一些成就, 但是在还存在着一定的不足需要我们进一步改善, 笔者认为决策树算法为来的发展有以下几个方面:
4.1 精确度的提高
具有较高的方差也是决策树算法中的一个主要问题, 通常, 一个完全不同系列都可能因为一个很小的数据变化而造成分裂。过程的分层本性是形成这种不稳定的主要因素, 决策树可能会因为顶层分裂中的一个失误而造成传播到下面各个分层的分裂。在建构决策树的过程中可以使用相对稳定的分裂准则进行建构尝试, 我们能够在某些程度较好的缓解这种情况, 但是在决策树是中不可能消除这种固有稳定性的, 因此, 我们需要进一步解决的问题就是要努力提高决策树的精确度。
4.2 处理复杂数据
我们目前所面临的一些数据大多复杂多样化的, 所以, 决策树算法除了能够有效地处理结构和数据外, 还应该对各种数据库、结构化、半结构化等方面进行挖掘和挑战。
5 结束语
数据挖掘的方法有很多种, 其中一个重要方法就是决策树算法, 决策树算法是目前多种算法中使用最多的数据挖掘技术之一, 该文在分析了决策树算法实际中遇到的一些问题和发展现状作了一个简单分析和发展预测。决策树算法在运行的过程中还有一些不足之处, 决策树算法虽然已经有了广泛的应用, 也产生了大量成熟的系统, 但是, 解决一个复杂的数据挖掘问题时决策树还面临着很多的问题。研究表明, 决策树算法还存在这很多缺陷, 其中还有很多问题值得我们去开发和研究。
参考文献
[1]滕明鑫, 高占国, 杨秀清.数据挖掘中决策树算法优化研究[J].重庆通信学院学报, 2011 (15) .
[2]韩慧, 毛锋, 王文渊.数据挖掘中决策树算法的最新进展[J].技术机运用, 2013 (28) .
[3]刘慧巍, 张雷, 翟军昌.数据挖掘中决策树算法的研究及其改造[J].辽宁师专学报2011 (486) .
[4]卢东标.数据挖掘中决策树算法的研究和常见问题的解决[J].算法与语言, 2010 (321) .
[5]唐华松, 姚耀文.数据挖掘中决策树算法的探讨[J].华南理工大学技算机学院报, 2013 (12) .
[6]林巧.数据挖掘中决策树算法的探讨[J].伊犁师范学院学报, 2011 (785) .
数据流分类算法分析 篇7
许多人把数据挖掘视为另一个常用的术语:数据中的知识发现。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的, 但又是潜在的、有用的信息和知识的过程。
本文利用数据挖掘中的朴素贝叶斯分类技术来研究鸢尾花数据集中有关于鸢尾花分类问题。以鸢尾花数据集为对象, 尝试通过数据挖掘中的朴素贝叶斯分类技术对数据进行分析, 实现对鸢尾花所属分类进行预测, 发现鸢尾花所属分类与鸢尾花各项数据之间的联系, 有助于对鸢尾花的培养进行管理。
2朴素贝叶斯分类算法
假设每个数据样本用一个n维特征向量来描述n个属性的值, 即X={x1, x2, ..., xn}, 假设有m个类, 分别用C1, C2, ..., Cm表示。给定的一个未知的数据样本X (没有标明属于哪个类) , 根据贝叶斯定理得:
undefined
由于P (X) 对于所有类为常数, 所以, 最大后验概率P (ci|X) P (|X) 可以转化为从最大先验概率 P (X|ci) *P (ci) 计算得到。如果训练数据集有很多元组和属性, 计算 P (X|ci) 的开销可能非常大, 为此, 通常假设各属性的取值是相互独立的, 这样先验概率P (x1|Ci) , P (x2|Ci) , ...,
P (xn|Ci) 都可以从训练数据集求得。
根据此方法, 对于类别未知的样本X, 可以先分别计算X属于每一个类别ci的概率。
P (X|ci) *P (ci) , 然后选择概率最大的类别作为其类别。
若朴素贝叶斯分类算法将未知数的数据样本X分配给Ci, 则需要满足:
P (|X) > P (|X) , P (ci| X) >P (cj|X) , 1≤j≤m, i≠j
从理论上来讲, 朴素贝叶斯分类算法与其他算法相比有着最小的错误率, 在实践中朴素贝叶斯分类算法还可以和神经网络算法和判定树等分类算法相媲美, 并且它的适应性也很强, 执行效率高, 在给定的N个属性的M个训练集, 学习时间的复杂度为O (N*M) , 这使得它在现实中有着广泛的应用。
3实例
鸢尾花数据集中数据属性分为花萼长、花萼宽、花瓣长、花瓣宽和所属分类5项。为了编程方便, 使用calyx_length表示花萼长、calyx_width表示花萼宽、petal_length表示花瓣长、petal_width表示花瓣宽、category表示所属分类如表1所示。
鸢尾花的类别分为3种:Iris-setosa、Iris-versicolor、Iris-virginica, 我们从鸢尾花数据集中选取60个数据样本作为训练数据集 (可随机选取, 这里为了实验计算方便, 每种类别均选取了20个样本) , 预测一个未知的数据所在分类。
若从预测数据集中读出如下数据 (5.4, 3.7, 1.5, 0.2) , 其中对应的4个属性类别分别为花萼长 (calyx_length) 、花萼宽 (calyx_width) 、花瓣长 (petal_length) 、花瓣宽 (petal_width) 。3个分类类别分别为setosa (用C1表示) , versicolor (用C2表示) , virginica (用C3表示) 。
朴素贝叶斯分类算法的步骤如下:
(1) 计算训练数据集中每个种类所占的比例。
因为60个训练数据集中每个种类均选取了20个样本, 所以在训练数据集中对于鸢尾花的3个种类出现的概率为:
P (setosa) =P (versicolor) =P (virginica) =1/3。
(2) 计算每个属性在训练数据集中的条件概率P (X|ci) , (i=1, 2, 3)
从每个预测属性值可以得到如下数据:
(3) 求最大后验概率P (Ci|X) 。
根据贝叶斯定理后验概率可以通过求先验概率来得到, 即P (X|ci) *P (ci) , 这里可以得到如下数据:
(4) 判断P1, P2, P3的大小:Max (P1, P2, P3) 。
在这里Max (P1, P2, P3) =P1, 所以我们把预测数据分类在P1类, 即Iris-setosa类别。实际上预测数据的类别就是Iris-setosa。如果Max (P1, P2, P3) =P2, 那么分在versicolor类, 如果Max (P1, P2, P3) =P3那么分在virginical类。我们通过这个过程说明如何使用朴素贝叶斯分类算法对未知数据进行分类, 达到了数据挖掘的目的。
4结束语
随着计算机技术的发展, 数据挖掘越来越受到研究人员的关注, 而分类算法中的朴素贝叶斯分类算法以其简单的算法思想、较高的精确度等优点成为挖掘领域热门的研究方向。朴素贝叶斯分类算法是建立在各个属性之间的相互独立性假设的前提下进行的, 这种假设在现实中是很少出现的。朴素贝叶斯分类算法在属性之间没有那么严格的条件下也能发挥比较好的性能, 所以朴素贝叶斯分类算法在证券、消费、教育、银行等行业中占有一席之地。
参考文献
[1]李志刚, 马刚.数据仓库与数据挖掘的原理及应用[M].北京:高等教育出版社, 2008.
[2][美]PANG-NING TAN, MICHAEL STEINBACH, VIPIN KU-MAR.Introduction to Data Mining[M]北京:人民邮电出版社, 2006.
[3][美]WALTER SAVITCH, Absolute Java[M], 北京:清华大学出版社, 2008.
[4]李艳, 刘信杰, 胡学刚.数据挖掘中朴素贝叶斯分类的应用[J].潍坊学院学报, 2007 (4) .