我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 知识发现 >

什么是数据立方体

归档日期:07-23       文本归类:知识发现      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  摘要 为了更有效的进行在线分类挖掘,提出了一种泛化算法。该算法结合了数据立方体技术和面向属性归纳方法中的泛化策略,有效降低了聚合运算的运算量,提高了运算效率,将数据库中的原始数据泛化成用户感兴趣的概念层次上的、聚合的、具有统计意义的元数据,为在线分类提供了良好的数据环境。

  数据准备是KDD过程中一个很重要的过程,良好的数据准备过程能够为数据挖掘提供清洁、可靠、稳定的数据环境,以保证挖掘算法的有效实施。在线分类理想的数据环境应具备以下几个特点: (1)数据应包含丰富的属性信息,应具备可靠性和稳定性;

  (2)数据的属性应具有对于分类任务的相关性。大多数的分类任务只与数据库中部分属性有关,多余的、无关的属性介入分类,常会减慢甚至错误引导分类过程,应此必须去掉无关属性。

  (3)数据应具有高层数据信息,以发现清晰的、高层的、具有统计意义的分类规则。在本文的研究中,为了使数据环境达到上述要求,在数据准备阶段采用了数据泛化的策略,这个策略用概念层次作为背景,结合了OLAP技术与Jiawei Han等人的面向属性归纳的方法,明显提高了工作效率。

  随着KDD研究的逐步深入, Jiawei Han等人提出了一种基于归纳的知识发现方法——面向属性的归纳方法[1][2][3],这方法的特点是能够根据概念层次将低概念层的数据泛化到相应的高层次的概念层,以发现多层的或高层的规则。面向属性归纳方法是一种有效的、完整的知识发现算法,该算法将机器学习中示例学习方法与数据库的操作技术相结合[1]。算法的一个关键就是攀升属性所对应的概念层次树以泛化原始数据集的数据到用户感兴趣的概念层上,减少数据集的大小,从而降低知识发现过程的计算复杂度。面向属性归纳方法的进行,必须有两个前提:

  (1)必须由用户提出明确的知识发现任务。在Jiawei Han等人的研究中,采用了一种类似SQL语句的知识发现语句DMQL[4]用来让用户定义发现任务,下面便是一个分类任务的语句描述:

  要说明的是在本文的研究中采用了一个可视化的向导来引导用户定义发现任务,但为了文章描述方便,在本文的描述中,借用了DMQL来描述发现任务

  (2)与发现任务相关的属性应有概念层次,如上文所述,数值型的概念层次可以自动提取,给定的概念层次可以用户的兴趣和发现任务的不同而进行动态调整。

  一般而言,泛化都是在数据集的单个属性上进行的。因为单个属性常常是数据集中的最小分解单位。在最小分解单位上进行泛化,更能确定泛化过程中的细微变化,从而达到适度泛化的目的,避免过度泛化。

  如果一个属性在相关数据集中有大量不同的值,但是在其对应的概念层次树上,没有比该属性更高的概念层,则该属性将被从发现任务中去除。因为这样的属性是不可能被泛化到更高的概念层的,这是符合示例学习理论的。

  如果一个属性在概念层次树上有更高层次的概念,那么在泛化后的数据集中将所有记录的该属性值以高层次的属性值替代。

  作为策略3的执行结果,必然会有许多不同的纪录由于属性值完全相同而合并成一条纪录。为了反应这一变化,引入属性CNT来纪录最初的表中不同纪录被概括成泛化表中相同纪录的个数。属性CNT在泛化的过程中保存了最初的计数,该值在知识发现的过程中起到了重要作用。

  利用策略2中的CNT可以定义规则的正确率P,P=(符合规则的CNT值)/(符合规则左边属性条件的CNT值)。这样可以定义一阈值L用于取舍规则,若PL则规则有效,否则丢弃该规则。另外,对一个属性A而言,为了将数据集概括到一定层次,必须沿着A的概念层次向上爬行几次。为了控制这个过程,有必要设置一归纳阈值,若A的取值个数达到这一阈值,则无需进一步概括,否则必须进行进一步的概括。除此之外,我们还可以对泛化表设置一个归纳阈值,如果泛化表的记录树大于该归纳阈值,则进行进一步的泛化直到满足这个归纳阈值为止。以上策略可以总结成算法如下:

  输入条件:1.一个关系数据集,2 一个学习任务,3 一套相关属性的概念层次,4 每个属性归纳阈值t[i](i=1 to n,于属性相对应)、一个泛化表归纳阈值t2。

  Step1. 根据用户提交的学习任务,从原始的关系数据集中收集与任务相关的属性与数据。生成初始泛化集GR;

  上述泛化算法是针对关系表的,其生成的结果也是关系数据表。对泛化后关系数据表进行分类规则挖掘时仍要进行大量的聚合运算,如计数、求和等。有没有办法降低聚合运算的运算量呢?有,那就是数据立方体。我们知道数据立方体的方格内存放的就是一些聚合值,而且对数据立方体进行聚合运算,其效率远高于对关系数据库进行聚合运算。基于此,本文提出了一种基于数据立方体的算法。

  本算法共分为四步:第一步,初始化。首先,根据用户提出的发现任务,收集相关数据。(这里需说明的一点是此处用户提出的发现任务的相关属性实际上是一个维的概念,它可能对应于数据库中一个或几个有层次关系的实际属性。在下面的例子中我们将看到这一点。)然后确定每维的概念层次(自动提取数值型概念层次或动态调整已有概念层次)。第二步,构造基本立方体(Basecube)。这一步中首先根据数据库的数据分布特性(对于离散属性确定不同值的个数,连续值则确定数值间的最小间隔)确定每维的最初泛化层次,然后进行聚合计算来构造基本立方体。第三步,按照基本泛化策略对每维进行泛化造作,以确定每维理想的泛化层次。第四步,在新的泛化层次上对Basecube进行再计算,以构造最终的泛化立方体Primecube。这一步中将大量使用数据立方体的操作。该算法的形式描述如下:

  ① 根据用户的学习任务,确定每一维对应的属性,并从初始关系数据集中收集相关的数据。

  if Ai是数值型 and Ai没有概念层次 then 自动生成概念层次(算法2.1)

  ① 对于每一维的属性计算其在数据库中对应的不同值的个数,如果是数值型则计算数值间的最小间隔,根据不同值的个数或最小间隔确定每一维的最初泛化层次。

  ② 按最初泛化层次确定每维的维成员,并进行COUNT,SUM等聚合运算。用文[26]中算法构造基本立方体。

  ① 根据每一维的泛化阈值,进行基本泛化(算法2.5)找到最终理想的层次Li。

  ② 找出每一维Ai的映射v,v’,其中v是维成员值,v’是v在泛化层上对应的概念值。

  本算法中,第一步的时间复杂度主要依赖于特定数据库的操作和提取或调整概念层次的算法的效率。第二步的主要操作在于立方体的构造上,复杂度为 。第三步和第四步都只对基本立方体进行一次扫描,加上计算量,复杂度也为 。所以本算法中二到四步总的时间复杂度应为 。

  例1:从网上下了一个数据库CITYDATA,该数据库记录了美国地区城市的情况。其中有三个表,如下:

  根据算法,我们首先作初始化,对family income,poverty pct,crime_rate,bachelor_pct由于它们是数值型的属性,所以概念层次可以自动提取出来,下面便是自动提取出来的概念层次:

  运行算法二、三、四步,得到六维的基本立方体和泛化立方体,为方便起见本文给出其中三维的立方体图。

  数据泛化在线分类研究中占有重要地位,它是在线分类规则挖掘算法的基础。在线分类任务的一个重要特征就是数据量庞大,且数据中含有一定量的异常信息,这样的数据是不适合直接分类的。通过数据泛化,可以将数据整理、清洁,为分类提供较好的数据环境。另外数据泛化采用了概念层次技术,可以发现高层的分类规则,从而使分类结果更易理解。

  本文结合基本的面向属性归纳技术,提出了一种数据立方体的数据泛化算法,给在线分类提供了较好的数据预处理技术。

  黄建国(1974年10月-- ) ,男,安徽省合肥市人,合肥幼儿师范学校讲师,中国科技大学计算机应用工程硕士。

  定义:数据立方体是一类多维矩阵,让用户从多个角度探索和分析数据集,通常是一次同时考虑三个因素(维度)。

  当我们试图从一堆数据中提取信息时,我们需要工具来帮助我们找到那些有关联的和重要的信息,以及探讨不同的情景。一份报告,不管是印在纸上的还是出现在屏幕上,都是数据的二维表示,是行和列构成的表格。在我们只有两个因素要考虑时,这就足矣,但在真实世界中我们需要更强的工具。

  数据立方体是二维表格的多维扩展,如同几何学中立方体是正方形的三维扩展一样。 “立方体”这个词让我们想起三维的物体,我们也可以把三维的数据立方体看作是一组类似的互相叠加起来的二维表格。

  但是数据立方体不局限于三个维度。大多数在线分析处理( OLAP)系统能用很多个维度构建数据立方体,例如,微软的SQL Server 2000 Analysis Services工具允许维度数高达64个(虽然在空间或几何范畴想像更高维度的实体还是个问题)。

  在实际中,我们常常用很多个维度来构建数据立方体,但我们倾向于一次只看三个维度。数据立方体之所以有价值,是因为我们能在一个或多个维度上给立方体做索引。

  由于数据立方体是一个非常有用的解释工具,所以大多数 OLAP产品都围绕着按多维阵列建立立方模型这样一个结构编制。这些多维的OLAP产品,即MOLAP产品,运行速度通常比其他方法更快,这是因为能直接把索引做进数据立方的结构,方便收集数据子集。

  然而,对于非常大的多维数据集, MOLAP方案并不总是有效的。随着维度数目的增加,立方体变得更稀疏,即表示某些属性组合的多个单元是空的,没有集合的数据。相对于其他类型的稀疏数据库,数据立方体往往会增加存储需求,有时会达到不能接受的程度。压缩技术能有些帮助,但利用这些技术往往会破坏MOLAP的自然索引。

  数据立方体还可以用其他的方法构建。关系 OLAP就利用了关系数据库模型。ROLAP数据立方体是按关系表格的集合实现的(最多可达维度数目的两倍),来代替多维阵列。其中的表格叫做立方单元,代表特定的视图。

  由于立方单元是一个常规的数据库表格,所以我们能用传统的 RDBMS技术(如索引和连接)来处理和查询它们。这种形式对大量的数据集合可能是有效的,因为这些表格必须只能包含实际有数据的数据立方单元。

  但是 ROLAP缺少了用MOLAP实现时所具有的内在索引功能。相反,给定表格中的每个记录必须包括所有的属性值而任何集合的或摘要的数据。这种额外的开销可能会抵消掉一些节省出来的空间,而隐性索引的缺少意味着我们必须提供显性的索引。

  从结构角度看,数据立方体由两个单元构成:维度和测度。维度已经解释过了,测度就是实际的数据值。

  记住这点是很重要的:数据立方体中的数据是已经过处理并聚合成立方形式。因此,通常不需要在数据立方体中进行计算。这也意味着我们看到数据立方体中的数据并不是实时的、动态的数据。

本文链接:http://weblodge.net/zhishifaxian/388.html