还剩51页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第9章分类规则挖掘与预测主要内容•分类与预测的基本概念•决策树方法•分类规则挖掘的ID3算法•其他分类规则挖掘算法•分类规则的评估•微软决策树及其应用第9章分类规则挖掘与预测step
2.用这棵树来对训练数据集进行分类,如果一个叶结点的所有实例都属于同一类,则以该类为标记标识此叶结点;如果所有的叶结点都有类标记,则算法终止;step
3.否则,选取一个从该结点到根路径中没有出现过的属性为标记标识该结点,然后就这个属性所有的取值继续创建树的分支;重复算法步骤step2;这个算法一定可以创建一棵基于训练数据集的正确的决策树,然而,这棵决策树不一定是简单的显然,不同的属性选取顺序将生成不同的决策树因此,适当地选取属性将生成一棵简单的决策树在ID3算法中,采用了一种基于信息的启发式的方法来决定如何选取属性启发式方法选取具有最高信息量的属性,也就是说,生成最少分支决策树的那个属性
2.ID3算法的描述算法Generate_decision_tree由给定的训练数据产生一棵决策树输入训练数据集samples,用离散值属性表示;候选属性的集合attribute」ist输出一棵决策树方法1创建结点N;2if samples都在同一个类C thenio3返回N作为叶结点,用类C标记;4if attribute_list为空then5返回N作为叶结点,标记samples中最普通的类;〃多数表决6选择attributejist中具有最高信息增益的属性test_attribute;〃用信息增益作为属性选择度量7标记结点N为test_attribute;8for eachtest_attribute中的已知值ai〃划分samples9由结点N生长出一个条件为test_attribute=ai的分枝;10设si为samples中test_attribute=ai的样本集合;〃一个划分11if si为空then12加上一个叶结点,标记为标记samples中最普通的类;〃多数表决13else力口上一个由Generate_decision_tree si,attribute_list-test_attribute返回的结点;
2.属性选择度量在Generate_decision_tree算法的Step6,算法需选择attributejist中具有最高信息增益的属性第9章分类规则挖掘与预测test_attributeo ID3算法在树的每个结点上以信息增量information gain作为度量来选择测试属性这种度量称为属性选择度量或分裂的优良性度量选择具有最高信息增益或最大嫌压缩的属性作为当前结点的测试属性该属性使得对结果划分中的样本分类所需要的信息量最小,并确保找到一棵简单的但不一定是最简单的决策树Information Gain指标的原理来自于信息论1948年,香农C.E.Shannon提出了信息论其中给出了关于信息量Information和瑞Entropy的定义,燧实际上是系统信息量的加权平均,也就是系统的平均信息量设S是有s个训练样本数据的集合,类标号属性具有m个不同值,定义m个不同类Ci i=l,2,…,m,si是类Ci中的样本数,则对一个给定的训练样本分类所需要的期望信息为IS1,S2,...,Sm=一工i=i pilog2pi i其中pi是任意样本属于Ci的概率,可用si/s来估计设属性A具有k个不同值{al,a2,…,ak},则可用属性A将S划分为k个子集{S1,S2,…,Sk},Sj中包含的样本在属性A上具有值aj如果选择A作为测试属性,则这些子集对应于由包含集合S的结点生长出来的分枝设时是子集Sj中类Ci的样本数,则按照A划分成子集的嫡为E A=2i=l Slj+S2j+...+Smj/sij*ISl,S2,...,Sm信息增益Information Gain,表示系统由于分类获得的信息量由系统燧的减少值定量描述用属性A分类后的信息增益为12GainA=I si,S2,...,sm-EA端是一个衡量系统混乱程度的统计量端越大,表示系统越混乱分类的目的是提取系统信息,使系统向更加有序、有规则组织的方向发展所以自然而然的,最佳的分裂方案是使燧减少量最大的分裂方案燧减少量就是Information Gain,所以,最佳分裂就是使GainA最大的分裂方案通常,这个最佳方案是用“贪心算法+深度优先搜索”得到的因为这是一个递归过程,所以仅仅需要讨论对某个特定结点N的分裂方法1分裂前设指向N的训练集为S,其中包含m个不同的类,它们区分了不同的类Ci fori=l,…,m设多是S中属于类Ci的记录的个数那么分裂之前,系统的总牖ISl,S2,...,Sm=-E i=l Pi10g2Pi容易看出,总皤是属于各个类的记录的信息量的加权平均2分裂后现在属性A是带有k个不同值的属性{ai,a%…ak},A可以把S分成k个子集{Si,S2,…,Sk}其中$={x|x£Sx.A=aj}如果A被选为测试属性,那么那些子集表示从代表集合S的出发的所有树枝设Sij表示在中类为C的记录个数那么,这时按A的每个属性值更一般的是取A的一个子集进行分裂后的信息量,也就是系统总燧为EA=E kj=l Slj+S2j+..+Smj/s*ISlj+S2j+..+Smj®j+S2j+.・+Smj/S表示第j个子集的权重,S=I SI子集Sj的信息量子集的总埔ISlj+S2j+..+Sm j=-Z Mi=l Pij10g2Pij第9章分类规则挖掘与预测总烯EA是各个子集信息量的加权平均算法计算每个属性的信息增益,具有最高信息增益的属性选择作为给定训练数据集合S的测试属性创建一个结点,并以该属性为标记,对属性的每一个值创建分枝,并据此划分样本K例》顾客数据库训练数据集如下表所示RID ageincome studentcredit_rating Class:Buys_computer1=30high no fair no2=30high noexcellent no331…40high nofair yes440medium nofair yes540low yes fair yes640low yes excellent no731…40low yesexcellent yes8=30medium nofair no9=30low yesfair yes1040medium yesfair yes11=30medium yesexcellent yes
1231...40medium noexcellent yes
1331...40high yesfair yes1440medium noexcellent no计算每一个属性的信息增益Gain age=1s2,s2—E age=
0.24614Gain income=
0.029Gain student=
0.151Gain credit_rating=
0.048由于属性age在所有属性中具有最高的信息增益,因此它被选择为测试属性创建一个以age为标记的结点,并对每一个属性值引出一个分枝落在分枝age=31…40”的样本都属于同一类“yes”,该分枝的端点应该创建一个叶结点----;——
31...40income studentcr缚仙一Class>40high no_fa ri ar ting nohigh noexcellent…no mediumnofairno lowyesfairyes mediumyesexcellentyes
3.剪枝剪枝常常利用统计学方法,去掉最不可靠、可能是噪音的一些枝条剪枝方法主要有两类同步修剪和迟滞修剪第9章分类规则挖掘与预测1先剪枝pre-pruning在建树的过程中,当满足一定条件,例如Information Gain或者某些有效统计量达到某个预先设定的阈值时,结点不再继续分裂,内部结点成为一个叶结点叶结点取子集中频率最大的类作为自己的标识,或者可能仅仅存储这些实例的概率分布函数2后剪枝pos-pruning与建树时的训练集独立的训练数据进入决策树并到达叶结点时,训练数据的class label与叶结点的class label不同,这时称为发生了分类错误当树建好之后,对每个内部结点,算法通过每个枝条的出错率进行加权平均,计算如果不剪枝该结点的错误率如果裁减能够降低错误率,那么该结点的所有儿子就被剪掉,而该结点成为一片叶出错率用与训练集数据独立的测试数据校验最终形成一棵错误率尽可能小的决策树如果在测试集中出现了类交叉的情况,也就是说,在待挖掘的数据中出现矛盾和不一致的情况则在算法步骤3中将出现这样一种情况在一个树结点中,所有的实例并不属于一个类却找不到可以继续分支的属性ID3使用以下两种方案解决这个问题
①选择在该结点中所占比例最大的类为标记标识该结点;
②根据该结点中不同类的概率分布为标记一一标识该结点如果在测试集中出现了某些错误的实例,也就是说,在待挖掘的数据中,本来应该属于同一结点的数据因为某些错误的属性取值而继续分支则在最终生成的决策树中可能出现分支过细和错误分类的现象ID3设置了一个阈值来解决这个问题只有属性的信息量超过这个阈值时才创建分支,16否则以类标志标识该结点该阈值的选取对决策树的正确创建具有相当的重要性如果阈值过小,可能没有发挥应有的作用;如果阈值过大,又可能删除了应该创建的分支
4.由决策树提取分类规则可以提取由决策树表示的分类规则,并以IF—THEN的形式表示具体方法是从根结点到叶结点的每一条路径创建一条分类规则,路径上的每一个“属性一值”对为规则的前件(即IF部分)的一个合取项,叶结点为规则的后件(即THEN部分)K例X对于buys_computer的决策树可提取以下分类规则IF age=v=30AND student=no THEN buys_computer=no IFage=v=30AND student=yes THEN buys_computer=yes IFage=
30...40THENbuys_computer=yes IFage=40AND credit_rating=excellent第9章分类规则挖掘与预测THENbuys_computer=no IFage=40AND credit_rating=fair THENbuys_computer=yes
5.ID3算法的改进
(1)离散化ID3算法对符号性属性的知识挖掘比较简单,也就是说,该算法对离散性属性的挖掘更为直观算法将针对属性的所有符号创建决策树分支但是,如果属性值是连续性的,如一个人的身高,体重等,如果针对属性的所有不同的值创建决策数,则将由于决策树过于庞大而使该算法失效为了解决该问题,在用ID3算法挖掘具有连续性属性的知识时,应该首先把该连续性属性离散化最简单的方法就是把属性值分成A和A,N两段如身高可以分为1米以下,1米以上或者分为L5米以下,
1.5米以上如何选择最佳的分段值呢?对任何一个属性,其所有的取值在一个数据集中是有限的假设该属性取值为(匕,岭,…,匕则在这个集合中,一共存在m・l个分段值,ID3算法采用计算信18息量的方法计算最佳的分段值,然后进一步构建决策树2属性选择度量ID3算法中采用信息增量作为属性选择度量,但它仅适合于具有许多值的属性已经提出了一些其他的属性选择度量方法,如增益率,它考虑了每个属性的概率3空缺值处理常用的空缺值处理方法有若属性A有空缺值,则可用A的最常见值、平均值、样本平均值等填充4碎片、重复和复制处理通过反复地将数据划分为越来越小的部分,决策树归纳可能面临碎片、重复和复制等问题所谓碎片是指在一个给定的分枝中的样本数太少,从而失去统计意义解决的方法是将分类属性值分组,决策树结点可以测试一个属性值是否属于给定的集合另一种方法是创建二叉判定树,在树的结点上进行属性的布尔测试,从而可以减少碎片当一个属性沿树的一个给定的分枝重复测试时,将出现重复复制是拷贝树中已经存在的子树通过由给定的属性构造新的属性即属性构造,可以防止以上问题的发生5可伸缩性ID3算法对于相对较小的训练数据集是有效的,但对于现实世界中数据量很大的数据挖掘,有效性和可伸缩性将成为必须关注的问题面临数以百万计的训练数据集,需要频繁地将训练数据在主存和高速缓存换进换出,从而使算法的性能变得低下第9章分类规则挖掘与预测
9.1分类与预测的基本概念
1.什么是分类第9章分类规则挖掘与预测解决的方法是将训练数据集划分为子集,使得每个子集能够放在内存;然后由每个子集构造一棵决策树;最后,将每个子集得到的分类规则组合起来,得到输出的分类规则最近,已经提出了一些强调可伸缩性的决策树算法,如SLIQ、SPRINT等这两种算法都使用了预排序技术,并采用了新的数据结构,以利于构造决策树ID3算法对大部分数据集有效,但它不能挖掘域知识同时,决策树在计算机中存储的方式决定了该分类规则相对于其他形式的分类规则(如公式)而言更晦涩难懂因此,一般在算法结束后,需要把决策树以用户可视的方法显示出来K例』以下表所示的训练数据集为例,其中Salary为工资,Education为教育程度,Class为信用级别假设以20,000作为Salwy的分段值,则创建的决策树如图外3所示;假设以16,000作为Salary的分段值,则创建的决策树如图9・4所示Salary EducationClass10,000高中一般2040,000学士较好15,000学士一般75,000硕士较好18,000硕士较好训练数据集T第9章分类规则挖掘与预测图
9.3分段值为20,000的决策树图
9.4分段值为16,000的决策树由图
9.3和图
9.4可以看出,Salary的分段值不一样,构建的决策树也不一样
6.决策树方法的评价22与其他分类算法相比,决策树有如下优点
(1)速度快计算量相对较小,且容易转化成分类规则只要沿着树根向下一直走到叶,沿途的分裂条件就能够唯一确定一条分类的谓词例如,沿着结点Age・Credit Rating.110走下来就能得到一条谓词if thereis aperson(age40)and(credit ratingis excellent)then hewill notbuy acomputer.
(2)准确性高挖掘出的分类规则准确性高,便于理解一般决策树的劣势
(1)缺乏伸缩性由于进行深度优先搜索,所以算法受内存大小限制,难于处理大训练集一个例子在Irvine机器学习知识库中,最大可以允许的数据集仅仅为700KB,2000条记录而现代的数据仓库动辄存储几个G-Bytes的海量数据用以前的方法是显然不行的
(2)为了处理大数据集或连续量的种种改进算法(离散化、取样)不仅增加了分类算法的额外开销,而且降低了分类的准确性
9.4分类规则挖掘的其他算法
9.
4.1分类规则挖掘的C
4.5算法
1.C
4.5算法概述C
4.5算法是ID3算法的扩展,但是它比ID3算法改进的部分是它能够处理连续型的属性首先将连续型属性离散化,把连续型属性的值分成不同的区间,依据是比较各个属性Gian值的大小
2.离散化的方法把连续型属性值离散化”的具体方法是第9章分类规则挖掘与预测1寻找该连续型属性的最小值,并把它赋值给MIN,寻找该连续型属性的最大值,并把它赋值给MAX;2设置区间[MIN,MAX]中的N个等分断点Ai,它们分别是Ai=MIN+MAX-MIN/N*i其中,i=l,2,・・・,N3分别计算把[MIN,Ai]和Ai,MAX i=1,2,…,N作为区间值时的Gain值,并进行比较4选取Gain值最大的Ak做为该连续型属性的断点,把属性值设置为[MIN,Ak]和Ak,MAX两个区间值
3.Gain函数决策树是建立在信息理论Information Theory的基础上的,决策树的方法循环地寻找某一标准,它能够带来与本次分类相关的最大信息构造好的决策树的关键在于如何选择好的属性对于同样一组记录集,可以有很多决策树能符合这组记录集人们研究出,一般情况下,树越小则树的预测能力越强要构造尽可能小的决策树,关键在于选择恰当属性属性选择依赖于各种对例子子集的不纯度impurity度量方法不纯度度量方法包括信息增益informatin gain、信息增益比gain ratio、Gini-index^距离度量distance measureJ-measure G统计、x2统计、证据权重weight ofevidence、最小描述长MLP、正交法ortogonality measure相关度relevance和Reliefo不同的度量有不同的效果,特别是对于多值属性C
4.5算法使用信息增益information gain的概念来构造决策树,其中每个分类的决定都与前面所选择的目标分类有关241信息理论Information Theory和埔Entropy考虑一个任意的变量,它有两个不同的值A和B假设已知这个变量不同值的概率分配,将估测该概率分配的不纯度情况
1.如果P A=1和P B=0,那么知道这个变量的值一定为A,不存在不纯度,因此已知变量结果值不会带来任何的信息情况
2.如果P A=P B=
0.5,那么它的不纯度明显地高于P A=
0.1和P B=
0.9的情况在这种情况下,已知变量的结果值就会携带信息不纯度的最佳评估方法是平均信息量,也就是信息烯EntropyS=-2pi*logPi在上面的例子中,情况1和情况2的信息燧分别是S1=-1*log1+0*log0=0S2=-
0.5*log
0.5+
0.5*log
0.5=
0.3012信息增益information gain信息增益是指信息燧的有效减少量通常用“字节”衡量,根据它能够确定在什么样的层次上选择什么样的变量来分类
4.C
4.5算法描述Function C
4.5R:a setof non-goal attributessome ofwhich withcontinuous values,C:the goal attribute,S:a trainingset returnsa decisiontree;begin If S is empty then第9章分类规则挖掘与预测return a single node with valueFailure;IfSconsists ofrecords allwith thesame valuefor thegoal attributethen returna singlenode withthat value;If Risemptythen returnasinglenodewithas valuethe mostfrequent of the values ofthegoalattributethat arefound inrecords ofS;[note thatthen therewill beerrors,that is,records thatwill beimproperly classiHed];for allattributes ofR Rido ifvalues of Ri arecontinuous thenbegin Let Al be the minimumof Ri;Let Ambe themaximum ofRi;{m值手工设置}for jfrom2to m-1do Aj=Al+j*Al-Am/m;LetAbe thevalue pointofRiwith largestGainRi,S basedon{=Aj,Aj};end;Let Dbe theattribute withlargest GainD,S amongattributes inR;Let{dj|j=l,2,・.,m}be thevaluesofattribute D;26Let{Sj|j=l,2,m}bethesubsets ofS consistingrespectively ofrecords withvalue djfor attributeD;Return atree withroot labeledD andarcs labeleddl9d2,・・,dm goingrespectively tothe treesC
4.5R-{D},C,SI,C
4.5R-{D},C,S2,・・,C
4.5R-{D},C,Sm;end C
4.5o但是,所用的基于分类挖掘的决策树算法没有考虑噪声问题,生成的决策树很完美,这只不过是理论上的,在实际应用过程中,大量的现实世界中的数据都不是以的意愿来定的,可能某些字段上缺值missing values;可能数据不准确含有噪声或者是错误的;可能是缺少必须的数据造成了数据的不完整另外决策树技术本身也存在一些不足的地方,例如当类别很多的时候,它的错误就可能出现甚至很多而且它对连续性的字段比较难作出准确的预测而且一般算法在分类的时候,只是根据一个属性来分类的在有噪声的情况下,完全拟合将导致过分拟合overfitting,即对训练数据的完全拟合反而不具有很好的预测性能剪枝是一种克服噪声的技术,同时它也能使树得到简化而变得更容易理解另外,决策树技术也可能产生子树复制和碎片问题在算法具体实现时必须考虑以上这些问题
9.
4.2DBlearn算法
1.DBlearn算法概述DBlearn算法用域知识生成基于关系数据库的预定义子集的描述DBlearn算法采用自底向上的搜索策略,使用以属性层次形式的域知识,同时该算法使用了关系代数该算法的事务集是一个关系第9章分类规则挖掘与预测表,即一个具有若干个属性的n元组系统采用关系表作为知识结构对每一类,它构建一个关系表这个关系表的属性是实例集属性的子集一个元组可以看作是一个属性值关联的逻辑公式搜索空间的开始是整个实例集,而最终目的是为了生成一个类描述的表类描述表的大小不能超过用户定义的阈值阈值的大小决定了类描述表的大小如果阈值太小,则生成的规则更简单,但同时也可以能丢失了一些有用的信息从而产生过度一般化的问题;如果阈值太大,则生成的规则比较详细,但同时也可能产生没有完全一般化和规则复杂的问题一些属性域被局部排序从而构成一个层次结构,每一个值都是该值所在层次下面全部值的一般化在从关系表中生成分类规则时,DBlearn算法使用了两个基本的算子
(1)删除如果在关系表中有属性之间存在着关联关系,则删除直到只剩下彼此互不关联的属性如年龄和出生年月这两个属性存在着年龄=现在时间一出生年月的关联关系,因此必须删除其中一个属性,保留另一个属性
(2)一般化属性的值被一般化为层次在它之上的值从而生成规则如就年龄这个属性而言,5岁以下都可以一般化为幼年,5・12岁可以一般化为童年等28在一个关系表上运行以上两个算子有可能产生完全一样的元组,DBlearn算法通过删除多余的元组来缩减关系表的大小从而得到类描述表
2.DBlearn算法描述DBlearn算法创建一个完全但不一定一致的分类规则,即该分类规则覆盖所有的实例集(包括那些错误的实例)DBlearn算法描述如下stepl.从数据库中选择和任务相关的数据,如一个包含且只包含一类数据的数据表step
2.在该数据表上执行一般化操作如果在某个属性上存在很多不同的值同时提供了一个更高级别的值,则该属性被一般化为更高级别的值;如果在某个属性上存在很多不同的值而不能提供一个更高级别的值,则该属性被删除删除重复的元组直到表的大小达到用户定义的阈值step
3.简化结果例如,如果该数据表上的一些元组除了一个属性不一样,其他的属性值都是一模一样的,而这个不一样的属性的取值可以一般化为一个更高层次的符号且这个属性的取值范围包含了该更高层次符号所代表的全部数据则这些元组可以用一个元组代替,这个元组的属性就是那个不一样的属性,它的值用那个符号表示step
4.把这个数据表转换成公式DBlearn算法是一个相对比较简单的分类规则挖掘算法,通过对属性取值不断进行一般化操作从而最终获得规则在数据挖掘的过程中,该算法是域知识挖掘的一个典型例子该算法经过改进可以挖掘那些包含噪声数据的不纯净数据,同时可以做增量学习数据分类dataclassfication是数据挖掘的主要内容之一,主要是通过分析训练数据样本,产生关于类别的精确描述这种类别通常由分类规则组成,可以用来对未来的数据进行分类和预测数据分类data classfication是一个两个步骤的过程•第1步建立一个模型,描述给定的数据类集或概念集简称训练集通过分析由属性描述的数据库元组来构造模型每个元组属于一个预定义的类,由类标号属性确定用于建立模型的元组集称为训练数据集,其中每个元组称为训练样本由于给出了类标号属性,因此该步骤又称为有指导的学习如果训练样本的类标号是未知的,则称为无指导的学习聚类学习模型可用分类规则、决策树和数学公式的形式给出•第2步使用模型对数据进行分类包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类训练数二>分类算法L\分类规则-V模型评估厂___________一二1新数据分测试数u一新数__J第9章分类规则挖掘与预测943分类规则挖掘的OC1算法LOCI算法概述OC1算法是Oblique Classifier1的缩写,即斜面分类1算法它基于线性规划的理论,以斜面超平面的思想为基础,采用自顶向下的方法在条件属性都是正实数类型的搜索空间创建斜面决策树在执行OC1决策树算法前,首先需要对搜索空间做净化和清理工作以消除条件属性间的函数依赖关系净化后的搜索空间中的每一个元组(记录)可以看作是一个m+1维向量(匕,彩,…,匕,),其中匕(lim)对应于第i个实数类型的条件属性,c对应于决策属性(元组的类)所有的条件属性可以看作是一个m维向量(匕,匕,…,匕)K定义X R”是一个n维欧几里得空间,设pwR且pwO,beR,则集合{x|p,x=4xw/T}称为R中的一个超平面(*4)(当n=2时,集合确定一条直线;当n=3时,集合确定一个平面)(定义』一个超平面将R〃分成两个半空间,记为“+
(41)=(|4源)和”-(AM=(U|AUW)其中H+(A,b)是中满足A U泊的向量U构成的半空间,/(A与是R中满足4UWA的向量U构成的半空间R定义》一组单位向量(1,0,0,…,0),(0,1,0,…,0),…,(0,0,0,…,1)是R〃中的一组30基,用符号配,…我来表示该组单位向量K定义X设「是一个超平面,如果“二5(1W),则「是一个轴平行超平面,否则「是一个斜面超平面R引理』ID3决策树的每一个结点等价于一个轴平行超平面(证明略)大部分决策树都是在每一个结点检查某个属性的值,或者对该数值属性进行分段检查因此,称这种决策树为“轴平行”决策树K定理》用超平面把一组n个的d维向量分成两个半空间,如果nd+l则存在2*ZL(*))种方法;如果nd+l则存在2〃种方法(证明略)
2.0C1算法的基本思想根据以上定理,最多存在有限种不同的决策树从理论上可以采用一种穷举的方法来寻找一棵最优决策树,但在实际中这是不可行的算法如前所述,寻找一棵最优决策树是一个NP完全问题寻找一棵斜面超平面决策树也是一个NP完全问题因此,用OC1算法只能找到一棵比较小的决策树,但不一定找到一棵最小的决策树OC1算法构建一棵斜面超平面决策树,其基本思想是采用自顶向下的方法从条件属性都是正实数类型的搜索空间开始创建斜面决策树如果搜索空间都属于同一类,则算法终止,否则,在搜索空间中寻找一个“最佳”划分搜索空间的斜面超平面,以此斜面超平面标识当前结点,把搜索空间分第9章分类规则挖掘与预测成两个半空间搜索空间(左子树和右子树)反复在每个半空间搜索空间继续寻找“最佳”斜面超平面直至算法终止
3.OC1算法描述step1,就当前搜索空间创建决策树的根结点,该结点的斜面超平面把搜索空间分为左半空间和右半空间;step
2.用这棵树来对搜索空间进行分类,如果一个半空间的所有实例都属于同一类,则以该类为标记标识此半空间;如果所有的半空间都有类标记,则算法终止;step
3.否则,分别以左半空间和右半空间为搜索空间,继续创建根结点的左子树和右子树;重复算法步骤step loOC1算法在每一个决策树结点处的算法描述如下/*寻找当前搜索空间的“最佳”斜面超平面参数刃stepl.寻找当前搜索空间的“最佳”轴平行超平面%,计算该轴平行超平面区的纯洁度小step
2.随机选择一个斜面超平面名,令“最佳”斜面超平面也等于该斜面超平面/,计算该斜面超平面”的纯洁度小step
3.重复R次以下步骤32step
3.1重复执行{依次振荡斜面超平面”的系数;}直到纯洁度没有进一步改进;step
3.2重复最多1次{选择一个随机方向,以该随机方向改变斜面超平面4;如果改变后的斜面超平面纯洁度/得到改进,转到步骤1;}step
3.3如果斜面超平面”的纯洁度/〃小于“最佳”轴平行超平面乩的纯洁度小令上小否则令1=1;step
4.输出纯洁度I对应的超平面根据OC1算法描述可以看出,最重要的算法实现方式包括⑴在决策数的每一个结点处如何生成一个斜面超平面⑵计算超平面纯洁度的方法;
4.OC1算法的改进10C1算法改进的基本思想第9章分类规则挖掘与预测OC1算法采用自顶向下的方法在条件属性都是正实数类型的搜索空间创建斜面决策树,如果条件属性是符号型则不能适用该算法关于符号型条件属性的问题,很容易想到的解决办法就是将其对应到正实数类型上,再在其上采用OC1算法挖掘分类规则如对条件属性“性别”,符号“男”对应“1”,符号“女”对应“2”针对不同的条件属性,可以创建不同的编码表,从而使OC1算法适用于符号型条件属性的分类规则挖掘但是这样创建的编码表具有很强的随意性和主观性,不能真正反应数据的真实状况如在搜索空间T中,条件属性“性别”为“男”的实例占了97%,而为“女”的实例只有3%假设在编码表中符号“男”对应的编码为“1000”,符号“女”对应的编码为“2000”,根据斜面超平面方程EQ”,把实例7;代入方程皿”,可以得到表达式匕显然,尽管性别为“女”的实例在搜索空间的比例很小,但由于其对应的编码远远大于性别为“男”的实例,因此〃性别的取值只能在很小的范围振荡,从而影响进一步选择“最佳”斜面超平面为了解决这个问题,可采用了一种基于分布的编码方式首先,扫描整个搜索空间实例集,得到所有条件属性为符号型的离散数据,创建编码表,计算每个离散数据在该搜索空间出现的频率根据每个符号对应的概率创建编码表,可以有效地解决上文中所提出的问题2OC1改进算法的描述34该部分的算法描述如下step
1.扫描搜索空间;step2,统计每一个符号属性出现的次数;step
3.计算每一个符号属性的概率分布值;step
4.生成编码表;
(3)结果分析下表给出了OC1算法和改进的OC1算法在同一个搜索空间,同样的随机改进系数(随机跳跃次数45),同样的振荡次数
(420)下搜索的正确率比较分析该搜索空间是基于塔斯马尼亚州大学计算机科学系捐赠的塔斯马尼亚州(澳大利亚州名)基础工业渔业部的鲍鱼数据库的数据仓库的一个采样切片由根据表可以看出,改进的OC1算法在同样的搜索空间和一样的搜索系数情况下,决策树的正确度无论是从平均值、最大值还是最小值进行比较,都远远高于原算法,大大增强了决策树(分类规则)的正确性和可预测性次数OC1算法OC1改进算法第一次
0.
760.84第9章分类规则挖掘与预测第二次
0.
700.77第三次
0.
660.80第四次
0.
730.78第五次
0.
690.78平均值
0.
7080.794最大值
0.
760.84最小值
0.
660.77表OC1算法和OC1改进算法的比较
9.
4.4分类规则挖掘的SLIQ算法
1.SLIQ算法概述SLIQ快速可伸缩算法(Supervised LearningIn Quest,其中Quest是IBM Almaden研究中心的数据挖掘项目)是IBM AlmadenResearch Center于1996年提出的一种高速可调节的数据挖掘分类算法该算法通过预排序技术,着重解决当训练集数据量巨大,无法全部放入内存时,如何高速准确地生成决策树能同时处理离散字段和连续字段36SLIQ的优点1运算速度快,对属性值只作一次排序2利用整个训练集的所有数据,不做取样处理,不丧失精确度3轻松处理磁盘常驻的大型训练集,适合处理数据仓库的海量历史数据4更快的,更小的目标树5低代价的MDL剪枝算法
2.SLIQ算法的关键技术1可伸缩性指标一般决策树中,使用信息量作为评价结点分裂质量的参数SLIQ算法中,使用gini指标gini index代替信息量Information,gini指标比信息量性能更好,且计算方便对数据集包含n个类的数据集S,gini S定义为giniS=1-Ep^pj Pj是S中第j类数据的频率gini越小,Information Gain越大2属性的分裂方法区别于一般的决策树,SLIQ采用二分查找树结构对每个结点都需要先计算最佳分裂方案,然后执行分裂对于数值型连续字段numeric attribute分裂的形式Av=v所以,可以先对数值型字段排序,假设排序后的结果为V1,V2,…,Vn,因为分裂只会发生在两个结点之间,所以有种可能性通常取中点Vi+Vi+l/2作为分裂点从小到大依次取不同的split point,取Information Gain指标最大gini最小的一个就是分裂点因为每个结点都需要排序,所以这项操作的代价极大,降低排序成本成为一个重要的问题,SLIQ算法对排序有很好的解决方案,在后面对算法的描述中,将很详细的看到这一点对于离散型字段categorical attribute,设S A为A的所有可能的值,分裂测试将要取遍S的所有子集S\寻找当分裂成和SS两块时的gini指标,取到gini最小的时候,就是最佳分裂方法显然,这是一第9章分类规则挖掘与预测个对集合S的所有子集进行遍历的过程,共需要计算2⑸次,代价也是很大的SLIQ算法对此也有一定程度的优化3剪枝SLIQ的剪枝算法MDL属于后剪枝5§少「111111加8[
3.
1.
1.2]算法通常的后剪枝的数据源采用一个Training Set的一个子集或者与Training Set独立的数据集进行操作
3.算法描述输入数据训练集,配置信息决策树大小;输出数据用线性表方式表示的二叉决策树算法Create noderoot;Prepare fordata ofattribute listand classlist;〃数据准备Enter queueroot;〃算法的控制结构是一个队列,该队列存放当前的所有叶结点While notempty queuedo EvaluateSplits;〃计算最佳分裂for allthe leaf nodes inthe queuedo UpdateLabels;〃升级结点创建子结点、执行结点分裂Clean thenew internal node andthe pureleafnodeout ofthe queue;〃对应该分裂的类表进行更改Let thenew leafnode enterthe queue;38MDL pruningroot;〃利用MDL算法进行剪枝CISIKS ListSalary L.ist图9・3计算分裂指标的例子一一当前待分裂属性Salari右边为class histogram的变化过程属性表从上往Update classhistograms and下扫描,叶队列里面的结点有®2$N3晋fir»t splatfor nodeN3salary v-40B GB GN3转为内Age ListSalary ListClass List第9章分类规则挖掘与预测b分类图9-1数据分类过程
2.常用的分类规则挖掘方法分类规则挖掘有着广泛的应用前景对于分类规则的挖掘通常有以下几种方法,不同的方法适用于不同特点的数据•决策树方法•贝叶斯方法•人工神经网络方法•约略集方法•遗传算法典型的分类规则挖掘算法有•ID3•C
4.5•DBlearn等第9章分类规则挖掘与预测部结点
9.
4.5CART算法
1.CART算法概述CART算法可用来自动探测出高度复杂数据的潜在结构,重要模式和关系.这种探测出的知识又可用来构造精确和可靠的预测模型,应用于分类客户、准确直邮、侦测通信卡及信用卡诈骗和管理信用风险技术上讲,CART技术可称为二元回归分化技术.因为根结点总是被分为两个子结点并不断分化,故称为二元回归CART分析的技术要点包括一系列规则,可用于
(1)分裂树点
(2)确定何时结束分裂
(3)为每一叶结点指定类型或预测值
2.CART算法的分裂规则的选择将一个结点分化成两个子结点,CART总是问些“是”或“非”的问题来分化根结点成二个子结点,以“是”为回答的案例归入左子树结点,而“否“为回答的案例归为右子树结点K例X贷款申请中风险分析有训练集包含100个高风险和100个低风险的测试案例,构造一棵二叉树如图1所示图9-8贷款风险分析对于上图中所得到的二叉树,CART算法先检验分析中所有变量可生出的所有分裂,再选其优者如上图中有200个案例,假设每个案例都有10个相关的数据变量,那么CART算法要比较200X10即2000种分裂的可能接下来需要根据分裂质量标准来评估每一个分化最常用的一个标准是GINI标准,基本原则是根据该分化是否有效地分隔几个类别除了GINI标准外,还可以用Twoing标准和规则Twoing标准其中GINI标准在树成长时明显地包括费用信息,而Twoing标准和规则Twoing标准则在计算风险和结点分配时使用费用,或者把费用信息合并入先验以应用到模型为了更有效地处理数据类型的选择,也可以运用连续自变变量的线性组合来作为分化的基础通过质量标准评估每一个分化后,要选取一个最佳分化来构建决策树,并继续对每一个子结点重复进行“搜索和分化”的过程,直到进一步的分化不可能继续不能继续的情况如某个树点包含完全一致的案例,则无法进一步分化;一个结点包含太少案例时,也会停止分化(一般取10为标准,少于10即为太少)第9章分类规则挖掘与预测当决策树构建完成后,需要要对决策树的终结点的案例进行分类一种最简单的分类方法就是对数原则,即用数量最多的种类来确定分类如上图的决策树,假设它已经构建完成,那么按多数原则,就确定左结点为低风险类,右结点为高风险类
3.CART算法的实现I以贷款申请中的风险分析为例,先确定一个训练集,如以100个高风险和100个低风险的数据集为训练集假设每条客户记录有字段姓名Char、年收入Money、工龄Int、籍贯Char、是否为高负债Bool为了举例字段的典型性,所以列举了上述这些字段,实际情况肯定不止这些字段,不过这些字段基本覆盖了在规则分化中要考虑的情况2根据训练集中的字段及每个案例在该字段上的取值,按顺序扫描训练集,并记录结果a.对于类型为数字型的字段,如DateTime、Int.Float.Money等,只要依次取每条记录的该字段的取值,然后按是否大于该值来扫描训练集建立一个表来记录结果,基于数据库中的数据一致性、减少数据冗余及方便后面对这个记录的操作,可以建立如下的表格tb_Result来存放结果序号Resultl intResult!int1234其中序号字段每次从1开始编号,添加一条记录,则序号加lo Resultl用来记录扫描时判断为“是”的高风险的案例数,如在扫描数字型字段时就记录大于扫描值的高风险案例的数目;在扫描字符型数据时就用来记录在该字段上的字符串与扫42描字符串相同的高风险的记录数;在扫描布尔型数据时,用来记录取值为“是”的高风险案例数目Result2用来记录扫描时判断为“是”的低风险的案例数用序号字段,而不直接用扫描字段来记录,是为了实现表的重用,节省数据库开支,这样在扫描所有的字段的时候都可以共用这个表来记录结果,而不必因为字段不同及字段类型的不同而要设计不同的表来记录结果由于每次使用tb.Result的时候,序号都是从1开始编号的,所以tb_Result中的记录结果是与训练集中的记录一一对应的,只要根据序号的对应关系,能够很方便的获得tb_Result表中的某条记录对应分化规则如下图tb_Result序号Result1Result2332765训练集:序号姓名年收入工龄籍贯高负债高风险••♦♦♦♦••♦♦♦♦•♦♦♦♦・♦••••♦33张三120008上海否否•••••♦假设现在的扫描字段为工龄字段,那么表tb_Result中对应的扫描规则即为工龄>8年,表tb_Rcsult中Resultl字段的值27表示工龄>8年且为高风险的案例数;Result2字段的值65表示工龄>8且为低风险的案例数;而用总的高风险案例数100—27=73即为工龄<8年且为高风险的案例数;用总的低风险案例数100—65=35即为工龄<8年且为低风险的案例数可见这样设计表tb_Result能降低数据冗余度,保持数据一致性,降低数据库开销(不用设计多个表来保存扫描结果),而且操作方便).对于类型为字符串型的字段,只要依次取每条记录的该字段的取值,然后扫描训练集进行字符串的匹配,对于完第9章分类规则挖掘与预测全匹配的记录以回答为“是”的情况进行记录C.对于类型为布尔型的字段,处理就更简单,只要对训练集扫描一次,把所有在该字段取值为“是”且为高风险的案例数记录下来,以及记录在该字段取值为“是”且为低风险的案例数而不必像其他类型的字段那样根据每条记录在该字段的取值来多次扫描数据库,记录在不同的分化规则下的分化结果3根据tb_Result表中的记录结果扫描训练集,构建决策树获得合理的分化规则d.取tb_Result表中的Resultl字段和Result!字段差值最大的前25%项,如例子中就取前50项这样取的目的1Resultl字段和Result!字段的差值,其实表示当前分化规则可以把高风险和低风险案例分化开来的程度2取差值最大的25%项,对应了分化强度强的25%条分化规则,以后在对子结点进一步分化的时候,只要在这些分化规则中取,而不用像刚开始那样,每个字段的每个取值都测试一遍,这样大幅度减少了分化所用的时间,因为在对整棵决策树不断分化的过程中,分化规则是以组合的形式出现的,所以现在取25%的分化规则,可以大大降低分化所需的工作量而且这样做,也不会带来多大的错误,因为取的就是强度大的分化规则如果时间允许,当然也可以取30%,50%等的分化规则这样做虽然带来一些错误,但是可以通过这个方法,在相同的操作时间内,通过选取更大的训练集来得到最后的分化规则,这样不但能够弥补上面带来的一些错误,而且更有可能找到比原来更好的分化规则e.把取得的分化规则按顺序写入数据表tb_Rule中,在此表中只要记录分化规则所对应的字段及在该字段上的取值就可以了如可以建表tb_Rule如下规则序号字段序号字段取值••••••・•・・・•・・・・・•1832873044此表中的这条记录就表示这是第18条分化规则,“3”代表当前分化规则使用训练集集中的第三个字段,即“年收入”字段,“28730”代表年收入为28730,整条分化规则即为“年收入28730”f.从tb_Rule表中组合分化规则,构建决策树,即为一棵二叉树可以用下面的数据结构来记录这棵二叉树struct node{int RuleNo;/*表示产生该结点时引用的分化规则号,根结点默认为一1;intHighNum;/*表示在该结点时,高风险的案例数;int LowNum;/*表示在该结点时,低风险的案例数;struct node*lchild;/*记录左结点;struct node*rchild;/*记录右结点;)直接用存储结构来记录决策树,而不用数据库来记录决策树,可以减少与数据库的交互时间,提高程序的效率在构建二叉树的过程中,可以限制它的深度值来避免二叉树深度过大而造成最后没有案例可以继续分化,或可分化的案例过少二叉树构建完成后,要对这棵二叉树进行修剪,去掉那些案例过少的枝条遍历这棵二叉树的所有叶结点,使用如下公式来评估每个分化规则的强度分化高风险强度=m8111111111+100;(其中100为训练集中高风险的案例数)分化低风险强度=1^^山11+100;(其中100为训练集中低风险的案例数)分别找出这棵二叉树中,高风险强度最大和低风险强度最大的两个叶结点,通过回溯这两个叶结点,就能获得这棵二叉树中最好分化高风险的和分化低风险的两个分化规则,把这两个分化规则记录下来,用于以后的比较g.根据前一步的过程,不断组合分化规则,构建二叉树来获取分化高风险和分化低风险的分化规则,通过各个规则之间的规则强度比较获得最终的合理的分化高风险和分化低风险的分化规则
4.CART算法的改进对于上面所描述的CART算法的实现还可以做如下的改经第9章分类规则挖掘与预测
1.可以设定一个训练集和一个测试集,通过训练集获得分化规则,通过测试集来进一步确定分化规则的强度,通过调节分化规则来获得更可靠的分化规则;
2.每次扩展一个子结点时,可以组合两条规则或更多条规则进行扩展,这样可以加快程序的速度;
3.在构建二叉树的过程中,可以通过一定的算法来获取好的规则组合,而舍弃一些差的规则组合,如可以加入一些先验概率这样能在同样获得好的分化规则的前提下,加快程序的效率附录资料不需要的可以自行删除如何构建银行数据仓库数据仓库技术作为一项数据管理领域的新技术,其精髓在于针对联机分析处理OLAP提出了一种综合的解决方案,与以往很多技术不同的是,它主要是一种概念,在此概念指导下完成系统的构造既没有可以直接购买到的现成产品,也没有具体的分析规范和实现方法,也就是说没有成熟、可靠且被广泛接受的数据仓库标准在以往关系数据库的设计和实现中,不仅有详细的理论推导,还有无数的设计实例,无论你使用的是什么公司的数据库产品、开发工具,只要按照规范做,那么实现同一业务需求的方案都会很相似而现有数据仓库的实现中,出现了MOLAP方案和ROLAP方案的区别,出现了形形色色的数据仓库建模工具、表现工具,而设计人员的个人经验和素质也会在其中扮演很重要的角色数据仓库技术的实现方式46目前在数据仓库技术的实际应用中主要包括如下几种具体实现方式工、在关系数据库上建立数据仓库ROLAP
2、在多维数据库上建立数据仓库MOLAP MOLAP方案是以多维方式来组织数据,以多维方式来存储数据;ROLAP方案则以二维关系表为核心表达多维概念,通过将多维结构划分为两类表:维表和事实表,使关系型结构能较好地适应多维数据的表示和存储在多维数据模型的表达方面,多维矩阵比关系表更清晰且占用的存储更少,而通过关系表间的连接来查询数据的ROLAP系统,系统性能成为最大问题MOLAP方案比ROLAP方案要简明,索引及数据聚合可以自动进行并自动管理,但同时丧失了一定的灵活性ROLAP方案的实现较为复杂,但灵活性较好,用户可以动态定义统计和计算方式,另外能保护在已有关系数据库上的投资由于两种方案各有优劣,因此在实际应用中,往往将MOLAP和ROLAP结合使用,即所谓的混合模型利用关系数据库存储历史数据、细节数据或非数值型数据,发挥关系数据库技术成熟的优势,减少花费,而在多维数据库中存储当前数据和常用统计数据,以提高操作性能
3、在原有关系库上建立逻辑上的数据仓库由于目前正在运行的OLTP系统中已经积累了海量数据,如何从中提取出决策所需的有用信息就成为用户最迫切的需要新建数据仓库固然能从功能、性能各方面给出一个完整的解决方案,但需要投入大量的人力、物力,并且数据仓库的建设和分析数据的积累需要一段时间,无法及时满足用户对信息分析的迫切需要因此在筹建数据仓库的前期,可以采用一些合适的表现工具,在原有OLTP系统上建立起一个逻辑的数据仓库系统尽管由于原有OLTP系统设计上的局限性,这样的系统可能无法实现很多分析功能,但这样一个系统中数据结构固定、信息分析需求相对稳定成熟,因此数据仓库的建模、实现过程会相对容易、便捷;同时,这样的系统也会成为将来真正数据仓库建设的原型信息系统与数据仓库的关系第9章分类规则挖掘与预测由于数据量大、数据来源多样化,在商业银行构建管理信息系统时,不可避免地会遇上如何管理这些浩如烟海的数据,以及如何从中提取有用的信息的问题;而数据仓库的最大优点在于它能把企业网络中不同信息岛上的商业数据集中到一起,存储在一个单一的集成的数据库中,并提供各种手段对数据进行统计、分析因此可以说,在银行使用数据仓库构建管理信息系统,既有压力,又有数据基础,它们之间的联系是必然的,难以割舍的数据仓库在商业银行的应用范围包括存款分析、贷款分析、客户市场分析、相关金融业分析决策(证券、外汇买卖)、风险预测、效益分析等在银行信息系统构建时,由于历史情况和现实需求的不同,存在两种途径1>建设新系统由于目前国内商业银行对银行内部运营的监管,缺乏很好的数据搜集机制,因此可以在构建管理信息系统时,分数据收集录入和数据汇总分析两部分来考虑这样的系统中由于不需考虑大量历史数据的处理问题,同时考虑到搜集过程中可能存在多个数据来源,因此可以在系统建设的同时构建数据仓库,将搜集来的各种数据通过数据抽取整合到数据仓库中
2、完善原有系统而对于已经存在OLTP系统,其中沉淀了大量历史数据,则可以先在原有系统上建立逻辑数据仓库,即使用数据分析的表现工具,在关系模型上构建一个虚拟的多维模型当系统需求稳定后,再建立物理数据仓库,这样既节省投资,又缩短开发工期实现中需要注意的问题48
一、模型设计中的问题模型设计(包括逻辑模型设计和物理模型设计)是系统的基础和成败的关键,在实际操作中,视实现技术的不同应分别对下列问题引起注意
1、直接构建数据仓库直接构建数据仓库时,必须按业务分析的要求重组OLTP系统中的数据,并要按不同侧重点分别组织,使之便于使用*主题的确定主题是一个逻辑概念,它应该能够完整、统一地刻画出分析对象所涉及的各项数据以及相互联系划分主题的根据主要来源于两方面:对原有固定报表的分析和对业务人员的访谈原有固定报表能较好地反映出以往工作对数据分析的需求,而且数据含义和格式相对成熟、稳定,在模型设计中需要大量借鉴但仅仅满足于替代目前的手工报表还远远不应是构建管理信息系统的目标,还应该通过业务访谈,进一步挖掘出日常工作中潜在的更广、更深的分析需求只有这样,才能真正了解构建数据仓库模型所需的主题划分*分析内容的细化主题的划分实际上是与分析内容的范围直接相关的,一旦主题划分清楚了,下一步就是细化分析的具体内容以及根据分析内容的性质确定它在数据仓库中的位置通常维元素对应的是分析角度,而度量对应的是分析关心的具体指标一个指标究竟是作为维元素、度量还是维属性,取决于具体的业务需求,但从实际操作中可以总结出如下的概念性经验:作为维元素或维属性的通常是离散型的数据,只允许有限的取值;作为度量的是连续型数据,取值无限如果一定要用连续型数据作为维元素,则必须对其按取值进行分段,以分段值作为实际的维元素判断分析指标是作为维元素还是维属性时,则需要综合考虑这个指标占用的存储空间与相关查询的使用频度需要特别强调的是,在细化分析内容的过程中,务必解决指标的歧义问题在不同报表中以及在业务访谈中同一名称的指标,是否是在同样条件限定下,通过同样方法提取或计算得到的,它们之间的相互关系是什么,这些问题都必须从熟悉业务的分析人员那里得到准确、清晰的答案,否则将会影响到模型设计、数据提取、
3.什么是预测预测prediction是构造和使用模型评估无标号样本类,或评估给定的样本可能具有的属性或区间值分类和回归是两类主要的预测问题分类是预测离散值,回归用于预测连续或有序值
4.分类和预测数据的预处理•数据清理使用平滑技术消除或减少噪声;处理空缺值•相关性分析删除与分类或预测无关的属性;删除冗余属性•数据变换使用概念分层将数据概化到高的层次;连续值属性概化为离散区间;数据规范化,即将某一属性的所有值按比例缩放,使其落入指定的区间
5.分类方法的评估标准•准确率模型正确预测新数据类标号的能力•速度产生和使用模型花费的时间•健壮性有噪声数据或空缺值数据时模型正确分类或预测的能力•伸缩性对于给定的大量数据,有效地构造模型的能力•可解释性学习模型提供的理解和观察的层次第9章分类规则挖掘与预测数据展现等多个方面*粒度的设计数据仓库模型中所存储的数据的粒度将对信息系统的多方面产生影响事实表中以各种维度的什么层次作为最细粒度,将决定存储的数据能否满足信息分析的功能需求,而粒度的层次划分、以及聚合表中粒度的选择将直接影响查询的响应时间如果同一个信息系统要在大范围、多层次上同时运行,如部门级和企业级,还应考虑不同层次的数据仓库采用不同的粒度*模型设计中的技巧复合指标尤其是比率类指标的定义,必须注意累加时是先加减后乘除,还是反之户数、笔数的计算,这类指标在分析或报表中经常出现,但不需要作为单独的指标物理存在于数据库中,但定义分析模型时一定应该准备度量的时间特性,针对分析指标在时间维上的不同表现,可分为可累加指标、半可累加指标和不可累加指标
2、在原有数据基础上构建逻辑数据仓库如果直接使用OLTP系统中的数据进行数据分析处理,会遇到许多麻烦,有时甚至是不可能实现的这并不是说关系数据库不好,而是因为其设计思路不适应较大规模数据分析因此在使用这种方法时,需要注意下列问题的处理*不同的时间单位这是实现过程中最常遇到的问题,也往往是最难解决的问题OLTP系统中存储的时间往往采用与实际业务发生相同的时间单位,如帐务数据单位为日期,财务报表单位为月或半年而面向分析时,往往要将不同时间单位的数据统一到同一个结果中,这样就必须存在适当的转换机制才能实现50*冗余信^息、所除除信息,就是指不同关系表中存在的同一含义的字段,而同一含义不仅指这些字段的取得或计算方式一样,还指它们成立的条件一样,例如截止某一时间同一地区的同一贷种的贷款余额在OLTP系统中,这样的字段往往是基于性能考虑而设计的,而在面向分析设计模型时,为了保证结果的唯一性和准确性,就必须用且只用其中之一的数据产生分析结果*表间连接由于OLTP系统中表的设计面向业务处理,既要保证数据的完整性、一致性,又要考虑响应时间,因此表与表之间既相对独立,又相互依赖在设计数据仓库逻辑模型时,对表间的连接必须做出相应取舍,既要保证分析数据能通过连接取得或计算出,又要避免出现环路,造成分析数据的歧义另外,不同的连接途径还会出现不同的查询速度,影响数据分析的响应性能*统计表的设计如果上述问题不能在原有数据库基础上得到很好的解决,那么权益之计就是构建统计表,即简单化的数据仓库,形式类似数据仓库的事实表,定时计算统计数据放入,将时间、冗余、连接等问题排除,进行简单分析
二、数据抽取中的问题数据抽取是一件技术含量不高,但非常烦琐的工作,必须有专人负责数据抽取的工作在对其进行设计时,要注意的问题有工、数据抽取的规则要作为元数据进行规范和管理,抽取过程中的源表、源字段、目的表、目的字段、转换规则以及转换条件都要作好详细记录这样不仅便于编程人员实现,而且在抽取规则或逻辑模型发生变化时也便于修改
2、如何记录业务数据库中的变动情况是数据抽取中一个重要的环节由于数据仓库中按时间保存数据,因此不同时间点之间数据的差异就成为一个关键性因素通常可以利用数据库管理系统提供的手段在数据库级产生数据变动日志,根据日志再判断数据的变动情况完成抽取,这样是一个从性能、可操作性以及对原业务系统的影响等多方面综合考虑都比较理想的方法第9章分类规则挖掘与预测
3、当数据仓库中同一表中的数据来自于原有系统中不同的表,甚至不同的库时,抽取时务必保证这些数据单位一致,而且都满足同一时间条件
4、数据抽取不仅要考虑数据的提取,还要考虑抽取的时间安排和执行方式,这样才是一个完整的数据抽取方案,也才能保证抽取出来的数据准确、可用
三、后期维护、优化中的问题数据仓库的建设是一个长期工作,它同其他系统一样需要在运行的过程中不断进行调整、完善这其中包括两方面的工作工、性能数据仓库涉及海量数据的查询,数据的大量写入读出,不仅对数据库系统的要求很高,而且与OLTP系统的要求极为不同,因此在系统设计、实施和维护的过程中,数据仓库系统的性能都是一个不可忽视的问题尤其是在运行期间,要密切关注应用对系统资源的消耗情况,针对应用的特点及时对系统进行调整,包括调整数据库参数、数据分片放置、创建特殊索引乃至提高系统配置等
2、模型应用与需求是相互促进、不断发展的,随着信息系统建成运行,用户在对系统了解不断加深的过程中,也会对系统提出更新更高的要求如何在最小投入的前提下满足用户的需求,也是一个值得注意和潜心研究的问题首先要尽可能挖掘现有系统的潜力,其次考虑,对主题的增加或可在现有系统上增加少量指标就可解决的需求,对系统进行适当调整,最后才考虑对系统进行重构,尽可能减小系统建设中的投入数据仓库应用的深化按照上述方法实现的应用中,主要完成了报表的生成和日常业务的分析,这并不能给企业带来真正的效益,52也远远没有发挥出数据仓库的应用价值随着应用的深入,可以由企业的技术人员与业务人员紧密配合,规划出对企业有实际价值的应用模型,并根据实际业务的发展不断调整模型自身的参数,以期找出企业运作过程中的规律,即在数据仓库上进行数据挖掘,构建DSS系统,这样才能充分体现构建数据仓库的意义,从而最终为企业带来效益尽管数据仓库技术还需要不断发展、完善,但只要企业能认识到信息分析的重要性,业务人员和技术人员能真正配合起来,相信不久的将来会有更多的实用成果出现第9章分类规则挖掘与预测
9.2决策树方法决策树方法的起源是概念学习系统CLS,然后发展到由Quiulan研制ID3方法,然后到著名的C
4.5算法,C
4.5算法的一个优点是它能够处理连续属性还有CART算法和Assistant算法也是比较有名的决策树方法
1.什么是决策树决策树Decision Tree又称为判定树,是运用于分类的一种树结构其中的每个内部结点internalnode代表对某个属性的一次测试,每条边代表一个测试结果,叶结点leaf代表某个类class或者类的分布class distribution,最上面的结点是根结点决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法下例是为了解决这个问题而建立的一棵决策树,从中可以看到决策树的基本组成部分决策结点、分支和叶结点K例力图9-2给出了一个商业上使用的决策树的例子它表示了一个关心电子产品的用户是否会购买PC buys_computer的知识,用它可以预测某条记录某个人的购买意向图9-2buys_computer的决策树这棵决策树对销售记录进行分类,指出一个电子产品消费者是否会购买一台计算机%uys_computer\每个内部结点方形框代表对某个属性的一次检测每个叶结点椭圆框代表一个类buys_computers=yes或者buys_computers=no在这个例子中,样本向量为age,student,credit_rating;buys_computers被决策数据的格式为age,student,credit_rating第9章分类规则挖掘与预测输入新的被决策的记录,可以预测该记录隶属于哪个类
2.使用决策树进行分类构造决策树是采用自上而下的递归构造方法以多叉树为例,如果一个训练数据集中的数据有几种属性值,则按照属性的各种取值把这个训练数据集再划分为对应的几个子集(分支),然后再依次递归处理各个子集反之,则作为叶结点决策树构造的结果是一棵二叉或多叉树,它的输入是一组带有类别标记的训练数据二叉树的内部结点(非叶结点)一般表示为一个逻辑判断,如形式为(a=b)的逻辑判断,其中a是属性,b是该属性的某个属性值;树的边是逻辑判断的分支结果多叉树(ID3)的内部结点是属性,边是该属性的所有取值,有几个属性值,就有几条边树的叶结点都是类别标记使用决策树进行分类分为两步•第1步利用训练集建立并精化一棵决策树,建立决策树模型这个过程实际上是一个从数据中获取知识,进行机器学习的过程•第2步利用生成完毕的决策树对输入数据进行分类对输入的记录,从根结点依次测试记录的属性值,直到到达某个叶结点,从而找到该记录所在的类问题的关键是建立一棵决策树这个过程通常分为两个阶段•建树(Tree Building)决策树建树算法见下,可以看得出,这是一个递归的过程,最终将得到一棵树•剪枝Tree Priming剪枝是目的是降低由于训练集存在噪声而产生的起伏
9.3分类规则挖掘的ID3算法由Quinlan在80年代中期提出的ID3算法是分类规则挖掘算法中最有影响的算法ID3即决策树归纳Induction ofDecision Tree早期的ID算法只能就两类数据进行挖掘如正类和反类;经过改进后,现在ID算法可以挖掘多类数据待挖掘的数据必须是不矛盾的、一致的,也就是说,对具有相同属性的数据,其对应的类必须是唯一的在ID3算法挖掘后,分类规则由决策树来表示LID3算法的基本思想由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间,该搜索空间是针对某一特定问题而提出的系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的评价函数一般依据分类的准确度和树的大小来决定决策树的质量如果两棵决策树都能准确地在测试集进行分类,则选择较简单的那棵相对而言,决策树越简单,则它对未知数据的预测性能越佳寻找一棵“最好”的决策树是一个NP完全问题ID3使用一种自顶向下的方法在部分搜索空间创建决策树,同时保证找到一棵简单的决策树一可能不是最简单的ID3算法的基本思想描述如下step L任意选取一个属性作为决策树的根结点,然后就这个属性所有的取值创建树的分支;。