我要投搞

标签云

收藏小站

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

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

数据泛化是什么

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

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

  展开全部数据泛化是一个从相对低层概念到更高层概念且对数据库中与任务相关的大量数据进行抽象概述的一个分析过程。

  在线分类理想的数据环境应具备以下几个特点: (1)数据应包含丰富的属性信息,应具备可靠性和稳定性;

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

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

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

  数据准备是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由于它们是数值型的属性,所以概念层次可以自动提取出来,下面便是自动提取出来的概念层次:

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

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

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

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