数据挖掘与知识发现(讲稿3---面向属性的归纳学习技术)

归纳学习旨在从大量的经验数据中归纳抽取出一般的规则和模式。归纳学习是一种非常重要的数据挖掘方法，但由于数据库中的数据量往往很大，影响了归纳效果，需要采取有效措施进行数据约简。面向属性的数据泛化和归纳学习技术是解决这一问题的有效途径。

面向属性的归纳学习（Attribute-Oriented Induction, AOI，亦称概念提升) 是一种面向关系数据库查询的、基于属性概化的、联机的数据分析处理技术（OLAP）的知识发现方法。最早于19年被提出，Jiawei Han等人对此作了比较全面的介绍。其主要思想是：首先使用关系数据库查询收集任务相关的数据；然后通过考察任务相关数据中每个属性的不同值的数量，进行属性概化。生成的结果广义关系可以映射到不同形式，如图表或规则，提供给用户。即通过归纳学习，使得属性域取值的抽象程度提高，从而得到较精练的数据集合，大大提高了规则的学习效率。这种方法可以有多种不同的应用，其中之一是它能够被运用到一个数据分类过程，以简化分类所要处理的事件空间。

3.1 概念层次

概念是语义描述的基本单位，也是数据库中各个描述对象的基本特征。概念可以分层，数据集中的数据通常包含原始层上的详细信息。

将一个数据集合归纳成高概念层信息的数据挖掘技术，称为概念分层。数据的属性以及概念依据抽象程度不同可构成一个层次结构。如，时间单位：年、季、月、周、日等。概念层次结构通常使用概念树表示。概念树是根据概念外延的包含关系定义的。

概念树一般由领域专家提供，与数据库中特定的属性有关，它将各个层次的概念按从一般到特殊的顺序分层排列。

在数据挖掘中，概念层次由于能够以层次的形式和偏序的关系组织数据和概念，能够把一组较低级概念映射到与它们相应的较高级概念的次序，以易于理解的高层概念表示数据库中数据的关系，因而在数据处理中往往起着举足轻重的作用。

3.1.1 概念层次的基本概念

定义1（概念层次）：一个概念层次H是一个偏序集（h,），其中 h是一个有限的概念集，是h上的一个偏序。

在概念树中，树的结点表示概念，树枝表示偏序，并且父结点到子结点的关系称为偏序。最一般的概念是没有具体特性的概念，用any表示；最特殊的概念(叶结点)对应数据库中具体的属性值；而处于概念树层次结构中间的概念是对该属性值归纳过程中产生的更宏观的(更广义的)概念。

如，在实际使用中， 反映了概念之间的“特殊---一般”关系，可以用树、格或有向无循环图等来表示。如，梨子水果食品。

定义2（正则概念层次）概念层次H=（h,）是正则的，如果h中有一个最大元素（最一般的概念），且有集合，，则

并且，若中某个概念的最近祖先在中，则中其他概念的最近祖先也都在中。

此外，描述概念的普遍化程度的另一个重术语是层次号。概念层次自上而下的层次号依次为。层次号为的概念称为层上的概念。具有相同层次号的概念必定在集合中，困此，可简单地把称作层次。

3.1.2 概念层次的类型

概念层次有四种：模式层次、集合分组层次、导出操作层次和基于规则的层次。

（1）模式层次

模式层次是在模式级上通过定义反映数据库属性之间联系的偏序关系而形成的。如，属性门牌号码、街道、城市、省份和国家形成模式层次为

        门牌号码街道城市省份国家

它表明，沿模式自左向右是泛化，自右向左是特化。因而，无须为每个数据记录指定泛化或特化的路径。

对数据挖掘任务而言，需要把模式层次泛化到数据库的有关数据上，从而得到该模式的具体值或实例层次。为此，需要同时存放模式层和实例层上的偏序。

（2）集合分组层次

这种概念层次是通过定义一组概念（或属性）值的子集之间的关系而形成的，反映了应用领域的语义联系特点。

[例1] Status是某大学数据库中的一个关系，见下表：

表1  Student数据库

则其集合分组层次如下：

        {一年级，二年级，三年级，四年级}大学生

        {理科硕士，文学硕士，博士}研究生

        {大学生，研究生}全部身份

        {生物，化学，计算机，…，物理}科学

        {文学，音乐，…，绘画}艺术

        {科学，艺术}全部专业

        {上海市，宝山，…，青浦}上海

        {南京，苏州，…，无锡}江苏省

        {上海，江苏省，…}中国

        {莫斯科，圣彼得堡，…}俄罗斯

        {东京，大阪，…}日本

        {俄罗斯，日本…}外国

        {中国，外国}所有地方

        0.0～1.99差

        2.0～2.99一般

        3.0～3.49良好

        3.5～4.0优秀

        {差，一般，良好，优秀}全部GPA

其中，属性Status的概念层次为

图1  属性Status的集合分组层次

（3）导出操作层次

     通过定义数据上的一组操作形成导出操作层次。如，根据数据值聚类和分布，导出大学生学习成绩的结构。导出操作层次常用于描述数字属性。

（4）基于规则的层次结构

     上述三种概念层次的特点是，每一个概念只有一个较高层的概念，因此，可以把一个概念无条件地泛化到它的较高层概念。但有时候，一个概念的泛化可能还涉及到该概念以外的其他条件。如，上例中，同样的3.6GPA，如果是研究生，则只能是“良好”；而若是大学生，则可能是“优秀”。

基于规则的层次结构可以将概念层次无条件泛化扩展到有条件的泛化，进一步完善了AOI方法。

若一个概念层次的各条路径具有相应的泛化规则，则称之为基于规则的概念层次，通常用格结构描述。一般有三种类型：

第一种，概念泛化与演绎规则有关。规则形式为

其中，是元组；A、B、C是概念（属性值）。若元组满足条件B，则把概念A提升到概念C。条件是一个简单谓词，或一个包含不同属性和关系的复杂逻辑公式。

第二种，概念泛化与计算规则有关。计算规则表示成条件表达式，其值可从属性、元组或数据库中计算出来。条件的真值决定一个概念是否可以通过路径泛化。

第三种，混合型。同时把演绎规则和计算规则结合起来确定泛化路径。

[例2] 对于上表1中的属性GPA，若有规则

规则1： {0.0～1.99}→差

规则2： {2.0～2.49}∧{研究生}→差

规则3： {2.0～2.49}∧{大学生}→一般

规则4： {2.5～2.99}→一般

规则5： {3.0～3.49}→良好

规则6： {3.5～3.79}∧{研究生}→良好

规则7： {3.5～3.79}∧{大学生}→优秀

规则8： {3.8～4.0}→优秀

规则9： {差}→能力弱

规则10：{一般}∧{四年级，研究生}→能力弱

规则11：{一般}∧{一年级，二年级，三年级}→能力强

规则12：{良好}→能力强

规则13：{优秀}→能力强

则得到如下的概念层次。

图2  属性GPA的基于规则的概念层次

3.1.3 概念层次的作用

通常，数据库中的数据可以在不同的概念层次上进行抽象。数据库中的原始数据是最基础的概念，大多数统计分析都是根据原始数据进行的，其学习结果是一种基础知识。如果在较高概念层次上对原始数据进行抽象，并发现和表示知识，就可得到较高级的知识。

例如，如果在基础层上发现如下形式的规则：

      规则1：80%有技术专长的教授、资深工程师、医生和律师，工资在60000-100000美元之间。

      如果提高数据抽象层次，就得到下面的规则：

      规则2：一般来说，受过良好教育的人，可以获得较高的工资。

显然，规则2比规则1包含更多的信息。这说明，概念层次可用于数据挖掘。

总之，概念层次可用于各种挖掘任务，如生成数据立方体结构；把原始数据泛化到某个较高抽象层；多层规则挖掘等。

3.2 面向属性归纳

面向属性法通过概念提升实现对某一属性概念的泛化，在泛化概念的基础上，通过归纳技术获取知识。

其基本思想是：

●首先，一个属性的较具体的值被该属性的概念树中的父概念所代替（即提升或泛化概念）；

●然后对相同的元组进行合并，构成更宏观的元组（称为宏元组），并计算宏元组所覆盖的元组数目（权重）；

●如果生成的宏元组数目仍然很大，那么用该属性的概念树中的父概念去代替或者根据另一个属性进行概念树的提升操作，最后生成覆盖面更广、数量更少的宏元组。

面向属性归纳方法把机器学习，特别是示例学习技术，与面向集合的数据库操作结合起来，大大提高了数据挖掘的功能和效率。这种方法不但用于关系数据库挖掘，而且可用于嵌套关系数据库和演绎数据库中的知识发现。

AOI与统计方法相结合，还可以对含有噪声的数据进行数据挖掘。

3.2.1 基本的面向属性归纳方法

    1. 面向属性归纳的基本策略（步骤）

[例3] 对于上表1数据库和图1概念层次，可按学习任务（用类SQL语言表示）：

         In relation Student

         Learn characteristic rule for Status=”graduate”

         In relevance to Name,Major,Birth-Place,GPA

建立面向属性的初始关系表如下：

表2 一个用于归纳的初始数据关系

首先，按条件“graduate”查询得到集合{M.S.,M.A.,Ph.D.}，然后检索graduate元组，并对属性Name,Major,Birth-Place,GPA进行投影，得到一个初始关系表。表中有一特殊属性Vote（覆盖度），表示该元组由多个元组综合而成，其初始值为1。

1991年，Cai和Han提出了面向属性归纳的七种策略：

（1）策略1（面向属性泛化）

      属性是关系的原子单位，泛化时一个属性一个属性地进行。通过移去不可泛化的属性和概念树提升，对属性进行泛化。

（2）策略2（移去不可泛化的属性）

      若一个属性尽管有很多个不同的值，但没有更一般意义上的高层概念来归纳它（即没有对应的概念树），则认为该属性在泛化过程中是没有意义的，可将它移去。如，Name属性

（3）策略3（概念树提升）

       对于某一元组的属性值，若概念树中存在一个更高层次的概念，就用该概念替换属性值，从而把这个元组泛化。泛化时，每次提升一层，以控制泛化速度，避免过泛化。

（4）策略4（累计覆盖值）

       当一个元组被泛化时，应将该元组的覆盖度值带到它的泛化元组中；当合并相同元组或去掉冗余元组时，应把覆盖度累计起来。

通过概念提升，逐步将数据库浓缩，使每条元组能覆盖原始数据库中的多个元组，形成所谓的宏元组。由宏元组组成的表称为知识表，或简称知识基。

经过概念提升后，原本不同的元组可能变得完全一样，这就要去掉冗余元组，并根据策略5判定是否进一步提升。如，根据策略2，将表2中的属性Name移去，泛化剩下的三个属性得到表3。

表3  表1的泛化关系

（5）策略5（指定泛化阈值、控制概念提升）

   用户指定的泛化阈值，其实就是把知识基表进一步浓缩，最后得到的宏元组的最大数量。对于知识基表中的某个属性，如果它的不同值的个数大于用户指定的泛化阈值，就要把这个属性进一步泛化。

（6）策略6（指定阈值、控制已泛化关系）

    如果已泛化关系的元组数仍大于用户指定的泛化阈值，则应对该关系继续泛化。如对表3中的“Birth-Place”继续泛化得

Major

Major

       将泛化关系中的一个宏元组转换成一条合取规则，多个宏元组可以转换成多条规则的析取。如，假设“艺术”和科学覆盖了所有的专业领域，则可把艺术、科学泛化到ANY，并从表中移去。最后的泛化关系等同于规则：

表示：一个graduate学生要么是成绩优秀的中国人（75%可能），要么是成绩较好、专业是科学的外国学生（25%可能）。

    2. 面向属性归纳的基本算法

其基本思路是：首先，一个属性的较具体的值被该属性的概念树中的父概念所替代；然后，对知识基表中出现的相同元组进行合并，构成更宏观的元组,并计算宏元组所覆盖的元组数目；如果数据库记录生成的宏元组数目仍然很大，那么用这个属性的概念树中更一般的父概念去替代，或者根据另一个属性进行概念树的提升操作,最终生成覆盖面更广、数量更少的宏元组；最后，将归纳所得的最后结果转换成逻辑规则。

输入：

1关系数据库；

2学习任务；

3概念层次；

4简化泛化关系；

5把最后的关系转化成为逻辑规则。

上述算法，均能从关系数据库中正确地学习特征规则。

    3. 面向属性归纳方法学习的其他知识规则

面向属性归纳方法也可以用于学习辨识规则和数据演变规律等知识，以及发现扩充关系数据库中的规则。

（1）学习辨识规则

     辨识规则用于区分目标类概念和对比类概念，所以在泛化时应首先找出目标类中与对比类中重复的条件，并从辨识规则中删除这些条件。通过同步泛化目标类和对比类，可以提取辨识规则。针对这些特点，相应地修改基本的面向属性归纳算法。

   [例4] 对表1中的研究生与大学生分开，提取一个辨识规则。

表4  一个泛化的关系

如果在目标类和对比类中有重复元组，则在该元组上做一个标记，表示在最后的辨识规则中不考虑这些元组。如，上表标记后，目标类还有3个元组未标记，表明结果规则是3条规则的析取。

如果设泛化阈值为2，进一步泛化Birth-Place属性，则结果为

该规则不包括重复析取。（即没考虑重复元组情况）

然而，在许多情况下，重复元组有益于从最终的泛化关系中导出定量规则，它们把每个析取与一个定量度量（称为d权）联系起来，表示规则的辨识能力。

定义：设是一个泛化概念（元组），是目标类。在类中的权为

其中，表示覆盖的目标类中初始元组的个数；表示覆盖的目标类和对比类中元组的总数；。权越大，表明概念主要是从目标类中推导出来的；权越小，表明概念主要是从对比类中推导出来的。

如，上例表中，目标类中的第一元组的

第二元组的d权=40/（40+50）=44.44%；第三元组的d权=100%。则graduate的定量辨识规则为

定性的辨识规则仅仅表示一个元组属于目标类的充分条件，不是必要条件。即满足条件的元组一定在目标类中，但目标类中的元组不一定都满足这些条件。

定量的辨识规则相对于对比类性质，定量地度量了目标类的性质。如果一个定量规则的权=100%，表明目标类中只有一个泛化元组。否则，权表示一个泛化元组属于目标类的概率。

（2）在扩充的关系数据库中发现知识

面向属性归纳也可以用于嵌套关系数据库和演绎数据库这两种典型的扩充关系系统。对于嵌套关系模型允许其属性值域是非原子的或又是关系的。

对非原子值域进行归纳有两种策略；

●解除嵌套关系，即把嵌套关系转化成扁平关系，从而可使用一般关系系统上的面向属性归纳方法；

●把非原子值域作为集合型值域处理，从而可对嵌套关系直接进行归纳。这种策略比前一种更为有效。

[例5] 设Student关系数据库中还包含属性“hobby”，存放每个学生的业余爱好。学习任务是研究计算科学的graduate学生的GPA与其业余爱好之间的关系。

现按第二种方法：把集合{棒球，口琴}泛化为一个新的集合{运动，音乐}。这样就不需要把初始元组分解为多个元组，概念树提升时可直接累计覆盖度。

对于演绎数据库，在泛化过程中把演绎规则和完整性约束结合起来，就可以进行面向属性的归纳。但要考虑两种情况：

●如何在由演绎规则定义的关系上分析知识规则；

●如何根据现有规则发现新的知识规则。

对于第一种情况，首先通过一个演绎查询从数据库中检索任务相关数据，然后在演绎数据集上进行归纳。

[例6] 根据大学生关系数据库构造演绎数据库，其奖学金候选人（award-candiate）由下列规则定义：

假设学习任务是发现计算机科学系中奖学金候选人的一般特征。则发现过程分两个阶段：①汇集任务相关数据；②进行面向属性的归纳。

第一阶段使用演绎数据库技术通过演绎查询找出计算机科学系中所有奖学金候选人；第二阶段从这些候选人中提取知识，这与学习特征规则的面向属性归纳是一样的。

第二种情况是从现有规则中发现新的规则。现有规则可以是归纳规则或部分归纳规则。如果现有规则表示所有外延数据的泛化，则可以直接对规则本身进一步归纳；如果现有规则与某些外延数据一起确定了演绎数据库中的所有相关信息，则知识发现过程首先对外延数据进行归纳，把数据泛化到与现有规则相同的概念层次上，同时把现有规则作为中间泛化关系的一部分，与已泛化的关系合并。然后通过面向属性归纳对合并后的关系作进一步泛化。

3.2.2 基于规则的面向属性归纳学习方法

采用基于规则的概念层次可以有效地提高面向属性泛化的表示和归纳能力。下面结合基于演绎规则的概念层次，介绍基于规则的面向属性归纳。其基本原理为：

将基于规则的面向属性归纳定义为一个七元组：

        （EDB，RCH，DS，TS，KRS，ATh，RTh）

其中，EDB是扩充的关系数据库；

      RCH是一组基于演绎规则的概念层次，每个属性都有一个RCH；

DS是支持概念泛化的一个演绎系统，包括RCH中的所有演绎规则和一组支撑规则；

TS是一组任务规格说明；

KRS是用一阶谓词表示的知识模式；

Ath和RTh分别是期望的属性阈值和元组阈值（控制过泛化）。

归纳的目标是EDB数据库中提取满足TS任务说明的一般知识，在DS支持下，沿RCH提供的方向进行泛化，学习结果由KRS定义的模式表示。

[例如] 在例2中，假定TS中的学习任务是发现计算机科学系学生的特征规则；属性GPA在RCH中的概念层次如图2所示，与之有关的演绎规则同例2。则基于规则的面向属性归纳过程分为两个阶段：归纳阶段一；归纳阶段二。

① 归纳阶段一：使用两遍扫描算法，把初始关系约简（或泛化）到主关系。

   第一遍扫描：使用演绎系统找出每个属性A的最小期望层次。（从底向上）

   第二遍扫描：元组泛化和合并。DS将它的每个元组及其属性泛化到层。同时比较泛化后的元组，合并相同元组，最后得到主关系。

例如，将两遍扫描算法用于例2，并按图2归纳，最后得到如下的主从关系：

表4  基于规则泛化的主关系

注：在把主关系归纳到结果关系时，信息丢失问题是非常重要的。这些被丢失的信息在下列情况下可能是至关重要的：

●规则可能依赖于已被移去的属性；

●规则可能依赖于这样的属性，该属性在主关系中的概念层次上被泛化得太高，无法与规则条件相匹配；

●规则可能依赖于一个只能相对于初始关系求值的条件。

如，上表中的第一个元组，就无法确定能否根据规则将其泛化到“能力弱”，或按规则把它泛化到“能力强”，因为属性Status的信息已经丢失。实际上，合并成该元组的那些元组可能基于完全不同的Status值。

解决信息丢失问题，可用回溯算法。

定义：一个泛化元组是初始关系中一组元组的合并，称这一组元组为泛化元组的源集；而把泛化元组称为源集的覆盖。

如上表中，当要把GPA属性进一步泛化到“能力弱”或“能力强”时，可用的规则有几条。对于第一个元组，规则和都可以用于其源集中的不同元组。因此，有可能把源集中的元组分别泛化到两个不同的概念“能力弱”和“能力强”。为此，必须将覆盖元组退回到源集中。

回溯算法的基本原理为：

1把基本关系中的覆盖元组退回到它们的源集。实现方法是，在初始关系中增加一个虚拟属性Covering-tuple-id（覆盖-元组-标识），记录与源集中元组相对应的覆盖元组的身份；

2选择几个属性，进一步将它们泛化到更高的层次。与基本面向属性归纳算法不同的是，这一泛化必须由演绎系统DS根据初始关系而不是主关系完成；

3比较且合并泛化后的元组。比较是在具有相同Covering-tuple-id的元组中进行的，并且只与被选作进一步泛化属性有关。结果产生一个增强型主关系。

4把合并过的元组往回映到主关系，并在主关系中将元组分解。把增强型主关系中具有相同Covering-tuple-id的所有元组，映射到与之相对应的主关系的覆盖元组中。然后按照这种映射把主关系中的元组分成几个元组，并调整覆盖度。最后，根据所选择的属性，将分开的元组泛化到增强型主关系中的相应值。

5在分解后的基本关系中合并泛化元组。如果合并元组后的关系规模仍大于泛化阈值，则重复泛化过程，直到泛化后关系的规模在阈值之内。

[例如] 对于上表，将属性GPA进一步泛化到能力弱或能力强。设带有虚拟属性的初始关系如下表5所示。

表5  经过扩充的带有属性Covering-tuple-id的初始关系