评价网 > 科教论文 > 工学毕业论文 > 计算机应用论文 > 正文

一种基于数据立方体的数据泛化算法(1)

2013-12-05 01:04 摘要 为了更有效的进行在线分类挖掘，提出了一种泛化算法。该算法结合了数据立方体技术和面向属性归纳方法中的泛化策略，有效降低了聚合运算的运算量，提高了运算效率，将数据库中的原始数据泛化成用户感兴趣的概念层次上的、聚合的、具有统计意义的元数据,为在线分类提供了良好的数据环境。 关键词 数据挖掘 数据泛化 数据立方体1 引言 数据准备是KDD过程中一个很重要的过程，良好的数据准备过程能够为数据挖掘提供清洁、可靠、稳定的数据环境，以保证挖掘算法的有效实施。在线分类理想的数据环境应具备以下几个特点： （1）数据应包含丰富的属性信息，应具备可靠性和稳定性；（2）数据的属性应具有对于分类任务的相关性。大多数的分类任务只与数据库中部分属性有关，多余的、无关的属性介入分类，常会减慢甚至错误引导分类过程，应此必须去掉无关属性。（3）数据应具有高层数据信息，以发现清晰的、高层的、具有统计意义的分类规则。在本文的研究中，为了使数据环境达到上述要求，在数据准备阶段采用了数据泛化的策略，这个策略用概念层次作为背景，结合了OLAP技术与Jiawei Han等人的面向属性归纳的方法，明显提高了工作效率。2 面向属性归纳中的基本泛化策略和算法 随着KDD研究的逐步深入， Jiawei Han等人提出了一种基于归纳的知识发现方法——面向属性的归纳方法[1][2][3]，这方法的特点是能够根据概念层次将低概念层的数据泛化到相应的高层次的概念层，以发现多层的或高层的规则。面向属性归纳方法是一种有效的、完整的知识发现算法，该算法将机器学习中示例学习方法与数据库的操作技术相结合[1]。算法的一个关键就是攀升属性所对应的概念层次树以泛化原始数据集的数据到用户感兴趣的概念层上，减少数据集的大小，从而降低知识发现过程的计算复杂度。面向属性归纳方法的进行，必须有两个前提：（1）必须由用户提出明确的知识发现任务。在Jiawei Han等人的研究中，采用了一种类似SQL语句的知识发现语句DMQL[4]用来让用户定义发现任务，下面便是一个分类任务的语句描述：要说明的是在本文的研究中采用了一个可视化的向导来引导用户定义发现任务，但为了文章描述方便，在本文的描述中，借用了DMQL来描述发现任务（2）与发现任务相关的属性应有概念层次，如上文所述，数值型的概念层次可以自动提取，给定的概念层次可以用户的兴趣和发现任务的不同而进行动态调整。在具备以上两个前提时，面向属性归纳采用了以下一些泛化策略。 ● 泛化策略 策略1 在最小分解单位上泛化 一般而言，泛化都是在数据集的单个属性上进行的。因为单个属性常常是数据集中的最小分解单位。在最小分解单位上进行泛化，更能确定泛化过程中的细微变化，从而达到适度泛化的目的，避免过度泛化。 策略2 属性去除 如果一个属性在相关数据集中有大量不同的值，但是在其对应的概念层次树上，没有比该属性更高的概念层，则该属性将被从发现任务中去除。因为这样的属性是不可能被泛化到更高的概念层的，这是符合示例学习理论的。 策略3 概念树攀升如果一个属性在概念层次树上有更高层次的概念，那么在泛化后的数据集中将所有记录的该属性值以高层次的属性值替代。 策略4 增加属性CNT 作为策略3的执行结果，必然会有许多不同的纪录由于属性值完全相同而合并成一条纪录。为了反应这一变化，引入属性CNT来纪录最初的表中不同纪录被概括成泛化表中相同纪录的个数。属性CNT在泛化的过程中保存了最初的计数，该值在知识发现的过程中起到了重要作用。策略5 设立阈值利用策略2中的CNT可以定义规则的正确率P，P=（符合规则的CNT值）/（符合规则左边属性条件的CNT值）。这样可以定义一阈值L用于取舍规则，若P>L则规则有效，否则丢弃该规则。另外，对一个属性A而言，为了将数据集概括到一定层次，必须沿着A的概念层次向上爬行几次。为了控制这个过程，有必要设置一归纳阈值，若A的取值个数达到这一阈值，则无需进一步概括，否则必须进行进一步的概括。除此之外，我们还可以对泛化表设置一个归纳阈值，如果泛化表的记录树大于该归纳阈值，则进行进一步的泛化直到满足这个归纳阈值为止。以上策略可以总结成算法如下： 算法1 (基本泛化算法) 输入条件：1.一个关系数据集，2 一个学习任务，3 一套相关属性的概念层次，4 每个属性归纳阈值t[i](i=1 to n，于属性相对应)、一个泛化表归纳阈值t2。输出：一个用户期望的泛化后的数据集。 步骤：本算法可以分为两大步： Step1. 根据用户提交的学习任务，从原始的关系数据集中收集与任务相关的属性与数据。生成初始泛化集GR；Step2. 运行基本的泛化算法产生泛化数据集。注意，step2可以细化成如下算法：begin for GR中的每一个属性Ai do begin while Ai的不同值的数目>t[i] do begin if Ai在概念层次中有高层次的概念 THEN 将Ai的所有值以高层次的概念值取代else 在GR中移去Ai; 合并同样的记录； end; end； while GR中的记录数>t2 do begin 选择泛化属性进一步泛化； 合并相同的记录。 end; end.3 基于数据立方体的泛化算法上述泛化算法是针对关系表的，其生成的结果也是关系数据表。对泛化后关系数据表进行分类规则挖掘时仍要进行大量的聚合运算，如计数、求和等。有没有办法降低聚合运算的运算量呢？有，那就是数据立方体。我们知道数据立方体的方格内存放的就是一些聚合值，而且对数据立方体进行聚合运算，其效率远高于对关系数据库进行聚合运算。基于此，本文提出了一种基于数据立方体的算法。 ●基于数据立方体的泛化算法 本算法共分为四步：第一步，初始化。首先，根据用户提出的发现任务，收集相关数据。（这里需说明的一点是此处用户提出的发现任务的相关属性实际上是一个维的概念，它可能对应于数据库中一个或几个有层次关系的实际属性。在下面的例子中我们将看到这一点。）然后确定每维的概念层次（自动提取数值型概念层次或动态调整已有概念层次）。第二步，构造基本立方体（Basecube）。这一步中首先根据数据库的数据分布特性（对于离散属性确定不同值的个数，连续值则确定数值间的最小间隔）确定每维的最初泛化层次，然后进行聚合计算来构造基本立方体。第三步，按照基本泛化策略对每维进行泛化造作，以确定每维理想的泛化层次。第四步，在新的泛化层次上对Basecube进行再计算，以构造最终的泛化立方体Primecube。这一步中将大量使用数据立方体的操作。该算法的形式描述如下： 算法2 基于数据立方体的泛化算法输入： 1 一个待挖掘的关系数据集； 2 一个学习任务； 3 一个概念层次集合Gen(Ai)，Ai是任意维； 4 Ti，任意维Ai的泛化阈值。输出：一个最终泛化的数据立方体。方法： ⑴始化： ① 根据用户的学习任务，确定每一维对应的属性，并从初始关系数据集中收集相关的数据。 ② for 每一维Ai dobeginif Ai是数值型 and Ai没有概念层次 then 自动生成概念层次（算法2.1） else 动态调整概念层次以适应当前学习任务；end; ⑵造Basecube： ① 对于每一维的属性计算其在数据库中对应的不同值的个数，如果是数值型则计算数值间的最小间隔，根据不同值的个数或最小间隔确定每一维的最初泛化层次。 ② 按最初泛化层次确定每维的维成员，并进行COUNT，SUM等聚合运算。用文[26]中算法构造基本立方体。 ⑶ 确定每维的泛化层次。 ① 根据每一维的泛化阈值，进行基本泛化（算法2.5）找到最终理想的层次Li。 ② 找出每一维Ai的映射