领域知识在数据挖掘中的应用及实现

摘要

近年来数据库技术不断成熟，面对大量数据，人们没有完全分析这些数据的能力，同

时迫切需要将这些数据转化成有用的信息，KDD技术随之产生。在工程领域，数据挖

掘是KDD过程的核心部分，它是从已有数据中发掘出隐含的、未知的、潜在的、有

用的信息并预测数据发展趋势的过程c

然而目前的KDD过程并未有效的利用领域知识，所谓领域知识是数据库中没有明确

表示，但可以引导知识发现过程，搜索有用的知识、摒弃对用户没有价值的发现结果

的信息。计算机中它表现的存储结构主要有比较简单的树型结构，以及更为接近现实

的图的结构形式。本课题主要是研究学习基于树型领域知识的AOI算法，它是应用己

有的领域知识对原始数据进行属性概化，以提取出有意义的规则。

本系统用VC++6.0,设计系统界面，采用SQLServer2000做后台数据库，实现了基于

树型领域知识AOI算法以发掘一系列规则，如特征规则、分类规则、区分规则、量化

规则等等。通过对整个AOI方法实现，加深了对数据概化、属性删除、属性概化、领

域知识、阈值控制等面向属性归纳法相关知识的了解，并进一步的熟悉了VC++6.0与

SQLServer2000的使用。

关键词：数据挖掘，领域知识，概念层次，数据概化，阈值控制

Abstract

Recentyears,thetechniqueofdatabasehasbeencomingtomaturity.Andthescaleof

databaseismoreandmoresweeping.Peoplehavenofullabilitytoanalyzedatainthese

databases.Meanwhileitisneededtodiscoverusefulinformationfromthem.Inthiscase,

KDD(shortforknowledgediscoveryindatabases)hasbeendeveloped.Inthefieldof

engineering,asthemainprocessofKDD,DM(shortfordatamining)isthenontrivial

extractionofimplicit,previouslyunknown,andpotentiallyusefulinformationfromdata.At

thesametime,itcandopeoutthetrendofthedevelopmentofdata.

Unfortunately,atpresentdomainknowledgehasn'tbeenusedeffectivelywhenpeopledo

KDD.Sodomainknov/ledgeisimplicitindatabases.ButitcanmaketheprocessofKDD

clear,andtellusefulinformationfromtrashy.Incomputer,itcanbestoredasthestructure

oftreewhichissimple,andtheotherapproachisstoreitasgraphwhichismorecomplex

butmuchnearertofact.ThispaperismainlytostudythealgorithmofAOIinwhich

domainknowledgeexistedisusedtogeneralizetheoriginaldataindatabases.Duringitwe

willdiscoveraserialofrules,suchascharacteristicrule,classificationrule,discriminant

rule,quantityruleandsoon.

Duringthedesign,VC++6.0wasusedasthedevelopingenvironmentwiththeprogram

languageofC++todesignthesysteminterface.Astothedatabasemanagement,

SQLServer2000wasadoptedtomanagedataandrelationsamongthem.Intheprogram,it

isrealizedthatAOIalgorithmbasedondomainknowledgeoftree.Theprogramisto

discoversomeimplicitandusefulrulesfromoriginaldata.Itmakesmelearnmoreconcepts

aboutAOIsuchasdatageneralization,attributeremoval,attributegeneralization,domain

knowledge,thresholdcontroletc.Italsomakesmebemorefamiliarwiththeusageof

VC++6.0andSQLServer2000.

Keywords:datamining,domainknowledge,concepthierarchy,datageneralization,

thresholdcontro

轶n轶

目录

摘要I

AbstractII

领域知识在数据挖掘中的应用及实现1

前言I

第一章绪论2

1.1本课题的研究背景及意义2

1.1.1数据挖掘2

1.1.1.1知识发现过程2

1.1.1.2知识发现核心过程…数据挖掘3

1.1.1.3数据挖掘常用技术3

1.1.1.4数据挖掘实际应用3

1.1.2数据挖掘的发展与现状3

1.1.3领域知识的定义4

1.2开发工具及环境简介4

1.2.1VisualC++6.04

1.2.2SQLServer20004

1.3本文的组织结构5

第二章领域知识的基本理论6

2.1领域知识的应用和作用6

2.2数据归纳法介绍6

2.2.1数据立方体法7

2.2.2面向属性归纳法7

2.2.2.1面向属性归法概念7

2.2.2.2面向属性归纳的一般过程8

2.3基于领域知识的面向属性归纳法8

2.3.1基于树型领域知识的AOI8

2.3.1.1基于树型领域知识的AOI算法介绍8

233.2基于多属性概化图AOI算法一AlLGcn算法介绍9

2.3.2AOI思想方法讲解及其实现构想10

2.3.2.1属性删除(attributeremoval)10

23.2.2属性概化(attributegeneralization)10

232.3阈值控制10

33.2.4阈值控制10

2.3.3算法比较10

2.3.4系统实现构想11

第三章系统设计及实现说明12

3.1程序的总体目标12

3.2程序核心模块流程图12

3.3系统模块划分12

3.3.1输入模块14

3.3.2数据处理模块14

3.3.2.1数据预处理14

3.322属性删除14

3.323属性概化14

332.4元组合并14

3.325领域知识添加14

3.3.3数据输出模块14

3.4数据结构实现14

3.5数据库设计15

第四章系统使用方法简介16

4.1系统主要模块运行界面16

4.2使用方法说明19

4.3相关注意点19

第五章系统运行测试结果20

5.1系统测试原理及方法简介20

5.2数据来源20

5.3数据处理及运行结果20

第六章课题研究结论及工作展望23

6.1工作总结23

6.2工作展望23

谢辞24

主要参考文献24

附录主要源代码25

轶IV轶

领域知识在数据挖掘中的应用及实现

、/—1—

刖后

2()世纪60年代以来，随着数据库技术和信息技术的成熟及其应用的普及，人类积累

的数据量迅速增长。大量的数据远远超出了人仅学习分析它们的能力，而同时又迫切

需要将这些数据转换成有用的信息。数据库中的知识发现(KnowledgeDiscoveryin

Databases简称KDD)是近年来随着数据库和人工智能技术的发展而出现的一个新兴

的研究领域，是以数据挖掘任务为核心的发现新信息的认知过程。它主要是利用机器

学习的方法从数据库中提取出先前未知、隐含的、有用的知识。通过数据挖掘，有价

值的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取出来，并从不同

角度显示，从而使大型数据作为一个丰富、可靠的资源为知识的提取服务。

在现有领域知识的应用中，Han首先提出了面向属性的层次提升问题即面向属性归纳

法(Attribute-OrientedInduction,简称AOI),它是以领域知识为背景对原始数据的属性

进行研究，找出数据中隐含的有用的规则。根据领域知识间关系的不同，可分为基于

树和图两种不同的领域知识。AOI的关键技术和重要特征就是利用概念层次(即领域

知识间关系表示法，用图或树的表示方法，其中图的形式中概念层次不是太明显)表

示的领域知识对关系数据库中的属性值进行概化操作，或者提升为更高层次的概念，

或者将意义不大的属性删除。在对数据进行概化忖，使用了面向属性的概念爬升技术,

这实质上降低学习过程的数据库的计算的复杂性，因为它忽略虑概化路径选择、排除

重复的过程并且领域知识的处理上也更为简单。使用这种面向属性的方法，可有效的

发现不同种类的知识规则，包括特征规则，分类规则、区分规则、量化规则等。

第一章绪论

本章主要介绍这次毕业设计所做课题产生的背景、研究的目的和意义，数据挖掘的相

关知识，以及开发工具的相关介绍，最后介绍本次设计论文的组织结构和各章节的安

排。

1.1本课题的研究背景及意义

我们生活的时代信息高速度增长，面对浩瀚的数据任何人都会觉得：一是信息过量，

难以消化；第二是信息真假难以辨识；第三是信息安全难以保证；第四是信息形式不

一致，难以统一处理c这种情况下KDD技术应运而生，它有效的解决了“信息爆炸

而知识贫乏”的尴尬现状。

1.1.1数据挖掘

这一节简要介绍基于领域知识的数据挖掘的相关概念。

1.1.1.1知识发现过程

知识发现(KDD)一个比较公认的定义是:^thenontrivialprocessofidentifyingvalid,

novel,potentiallyuseful,andultimatelyunderstandablepalternsindata，\[14]即KDD是

从大量数据中提取出有效的、新颖的、有潜在作用的、可信的、并能最终被人理解的

模式的非平凡的处理过程，它是从数据中发现有用知识的整个过程。

学习某个应用领域、建立目标数据集、数据预处理、数据转换、选定数据挖掘能、选

定数据挖掘算法、数据挖掘、解释某个发现的模式、发现知识。KDD具体过程可用如

图1.1表不。

铁2轮

1.1.1.2知识发现核心过程一数据挖掘

由图1.1可以看到，数据挖掘(DM)是KDD过程中的一个特定步骤，是KDD的核

心部分，它用专门算法从数据中抽取模式(patterns)。该模式是新的、可能有用的和

最终可理解的。数据挖掘与传统分析工具不同的是数据挖掘使用的是基于发现的方

法，运用模式匹配和其它算法决定数据之间的重要联系。模式有很多种，按功能可分

为TT两大类：预测型(Predictive)模式和描述型(Descriplive)模式。

1.1.1.3数据挖掘常用技术

目前市面数据挖掘应用方面有着种类繁多的商品工具和软件，大致可以归纳为下列主

要类型：、传统主观导向系统、传统统计分析、神经元网络(NN)技术、决策树、进

化式程序设计(evolutionaryprogramming)：这种方法的独特思路是、基于事例的推理

方法(CBR—casebasedreasoning遗传算法(GA—geneticalgorithms)s非线性回归

方法。

需要说明的，上面所说的DM中的数据是指数据库中表格形式中的记录和条目，这种

数据称作结构型数据(structureddata)。在一个企业中，还有一类像文本和网页形式的

数据，称作非结构型数据(unstructureddata)。它来自不同的信息源，如文本图像影视

和音响等，当然文本是最主要的一种非结构数据。1995年分析家已预言，像文本这样

非结构型数据将是在线存贮方面占支配地位的数据形式。到1998年初，在internel上

的信息网页数，已超过5亿。随着inlernet的扩展和大量在线文本的出现，将标志这

巨大的非结构型数据海洋中，蕴藏着极其丰富的有用信息即知识。人们从书本中获取

知识方法是阅读和理解。开发一种工具能协助用户从非结构数据中抽取关键概念以及

快速而有效地检索到关心的信息，这将是一个非常引人入胜的研究领域。目前,基于

图书索引检索以及超文本技术的各类搜索引擎，能协助用户寻找所需信息，但要深入

发掘这类数据中的有用的信息，尚需要更高层次的技术支持，人工智能领域有关知识

表示及获取的方法(如语义网络概念映射等)，和自然语言理解的研究成果，可望被

采用。还可能要涉及到语言学心理学等领域。最近已出现针对文本的DM工具的报导。

如IBM公司的texminer,netquestion,wedcawler和megaputer公司的textanalyst等。

1.1.1.4数据挖掘实际应用

DM(KDD)工具和软件已在各个部门得到很好的应用，并收到明显的效益如，金融

方面、在客户关系管理方面、在零售业/市场营铛方面:、在过程控制/质量监督保证方

面、在远程通讯部门、化学/制药行'业、军事方面。

1.1.2数据挖掘的发展与现状

随着KDD在学术界和工业界的影响越来越大，国际KDD组委会于1995年把专题

讨论会更名为国际会议，在加拿大蒙特利尔市召开了第一届KDD国际学术会议，以

后每年召开一次。近年来，KDD在研究和应用方面发展迅速，尤其是在商业和银行领

域的应用比研究的发展速度还要快。

目前，国外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究进一步发

展，如近年来注重对Bayes(贝叶斯)方法以及Boosting方法的研究和提高；传统的

统计学回归法在KDD中的应用；KDD与数据库的紧密结合。在应用方面包括：KDD

商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。

用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多计算机公司非常

重视数据挖掘的开发应用，IBM和微软都成立了相应的研究中心进行这方面的工作，

此外，一些公司的相关软件也开始在国内销售，如Platinum、BO以及IBM。

国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉及的研究

领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论

方面的研究。目前进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、

863计划、“九五，九划等,但还没有关于国内数据挖掘产品的报道。

数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将会不停地

促进它的发展。每年都有新的数据挖掘方法和模型问世，人们对它的研究正日益广泛

和深入。尽管如此，数据挖掘技术仍然面临着许多问题和挑战：如数据挖掘方法的效

率亟待提高，尤其是超大规模数据集中数据挖掘的效率；动态数据和知识的数据挖掘；

网络与分布式环境下的数据挖掘等；另外，近年来多媒体数据库发展很快，面向多媒

体数据库的挖掘技术和软件今后将成为研究开发的热点。提高数据挖掘效率的重要方

法之一是有效的利用领域知识，下一小节将给出领域知识的定义。

1.1.3领域知识的定义

知识发现的重点之一在于有效运用领域知识。对于非常大型的数据库而言，彻底而详

尽的搜索数据库以发现新的关系是不切实际的。除非领域专家或一种自动的发现工具

能够引导数据分析和知识发现过程，否则难以成功发现有用的、新颖的信息。对于领

域知识的定义，众多研究学者根据各自的理解，给出了很多定义，但是较为常用的有

以下三种：

''additionalknowledgeareoftenusedtoguideandconstrainthesearchforinteresting

knowledge.Werefertothisformofinformationasdomainknowledgeorbackground

knowledge.-R,4］即在知识发现系统中，把加入的那些有关引导和限制搜索感兴趣知

识的知识称为背景知识或领域知识。

“Wedefinedomainknowledgetomeaninformationabouttheimportanttopicsorconcepts

inaparticulardomainandhowtheyrelatetoeachother.”［7］即将领域知识定义为一个专

门领域的重要问题或概念以及这些问题和概念之间的相互关系［15］。

“Domainorbackgroundknowledgecanbedefinedasanyinformationthatisnotexplicitly

presentedinthedatabase「［5,6］即领域知识被定义为还数据库中没有明确表达商信息

［I51o

1.2开发工具及环境简介

这一节简要介绍本次毕业设计过程中所用的开发工具：VisualC++6.0和SQL

Server2000

1.2.1VisualC++6.0

VisualC++6.0是微软公司推出的可视化开发环境，是计算机界公认的优秀的应用程序

开发工具之一，它不仅提供了控制台应用程序用来学习和掌握C++的内容，而且提供

“可视”的资源编辑器与MFC类以及应用程序向导，并为快速高效的开发出Windows

应用程序提供了极大的方便。MFC是微软基于Windows平台下的C++类库集，是在

MicrosoftWindows操作系统中编程的一个应用程序框架，它极大的方便了开发出

Windows介面应用程序的过程，体现了代码重用、继承、派生等面向对象思想。Visual

C++的集成开发环境DeveloperStudio提供了大量的实用工具以支持可视化编程特性，

它们包括：项目工作区、ClassWizard、AppWizard>WizardBar>ComponentGallery

等，DeveloperStudio采用标准的多窗口Windows用户界面，并增加了一些新特性，

使得开发环境更易于使用，用户很容易学会它的使用方法。事实上，还可以利用Visual

C++6.0进行Internet,数据库及多媒体方面程序的开发。本次课程设计主要用它作为

系统的开发环境，使用了MFC编程技术来简化系统介面的设计。

1.2.2SQLServer2000

SQL的诞生于IBM公司在加利福尼亚SanJose的试验室中，在七十年代SQL由这

里开发出来最初它们被称为结构化查询语言StructuredQueryLanguage并常常简称

为sequel开始时它们是为IBM公司的DB2系列数据管理系统RDBMS关系

型数据库管理系统而开发的您在今天仍可以买到在不同平台下运行的该系统事实

上是SQL造就了RDBMS它是一种非过程语言与第三代过程语言如C和

铁4轮

COBOL产生丁同一时代.。

SQLScrvcr2000是Microsoft公司推出的SQLServer数据库管理系统的最新版本该版本

继承了SQLServer.。版本的优点同时又比它增加了许多更先进的功能具有使用方便

可伸缩性好与相关软件集成程度高等优点可跨越从运行MicrosoftWindows98的膝上

型电脑到运行MicrosoftWindows2000的大型多处理器的服务器等多种平台使用，

SQLServer2000是用来建立和管理数据库的引擎。SQLServer2000不仅可以实现个人

数据库的管理，更适合于企业级的数据库应用。SQLServer2()00为数据库管理员提供

了许多管理数据库系统的工具，还可以设置多服务器配置。在本系统的开发中，采用

的就是该数据库作为后台的数据库管理工具。

1.3本文的组织结构

最后介绍一下本文的组织结构和各个章节的安排：

本文主要由以下各个部分组成：绪论，领域知识的基本理论，设计说明，系统使用方

法介绍，系统运行测试结果以及课题总结等六章组成。

第一章简单介绍知识发现、数据挖掘、领域知识以及开发工具的介绍。重点阐述了知

识发现过程，知识发现核心一数据挖掘，数据挖掘中常用技术，数据挖掘实际应用。

第二章介绍领域知识在数据挖掘中的作用，对不同形式的领域知识的阐述，数据归纳

法的介绍。由于本次设计主要完成的是基于树型领域知识的AOI算法，因比着重介绍

了面向属性归纳法的相关概念以及其核心算法。相关概念包括数据概化，属性删除，

属性概化，背景知识以及阈值控制等。该章与第三章系统实现是本文的重点。

第三章主要介绍了面向属性归纳方法实现过程。系统功能详细说明和程序结构设计说

明构成本章的重点。

第四章主要介绍系统使用方法以及用户在使用过程中应该注意的问题。

第五章以一个典型的大学数据学生档案为数据来源，通过系统对该数据的分析及运行

结果显示，来进一步验证本算法，测试本系统的运行状况。

第六章对本次毕业设计进行总结，介绍了在程序实现过程中所遇到的问题，以及解决

方法，并总结了本次设计中的不足，同时展望未来进一步的学习和研究。

第二章领域知识的基本理论

本章介绍本次毕业设计的理论依据，包括领域知识的作用，数据归纳法的介绍，基于

领域知识的面向属性归纳法，其中着重介绍设计实现的基于树型领域知识的AOI算法

并且简要对比各种算法，最后是系统实现构想部分，对AOI各个步骤的实现提出构想。

2.1领域知识的应用和作用

在前一章的介绍中阐述的领域知识的各种定义，这里我们做自己的诠释，将领域知识

定义为在数据库中没有明确表示，但可以引导知识发现过程搜索有趣的知识、摒弃对

用户没有价值的发现结果的信息它是本次课题的背景知识。它是本次设计的背景知

识，是用概念层次描述的用于控制概化过程的必要依据。用概念层次这一术语描述时,

通常把概念层次的不同层组织成一种概念拓扑结构。这种概念拓扑结构根据“一般-

至-特殊”(general-lo-specific)的序列形成了一种偏序关系。最高度泛化的概念是空概

念(用保留字“Any”描述)对应于概念层次树中的根结点，对应于数据库中具体的属

性值是概念层次中最高度特化的概念，在概念层次树中它表现为叶子结点，图2.1和

图2.2是一个典型的大学生数据库中领域知识的两种不同表示方法。用树的形式来表

示领域知识，层次分明，但更为复杂的情况是用图来表示各个概念之间的关系，图的

形式接近实际，层次性却不是那么明显。本次设计着重针对树型的领域知识进行讨论。

{freshman,sophomore,junior,senior)<zundergraduate

{M.S.,M.A.,Ph.D.)ugraduate

{undergraduate,graduate|czANY(status)

图2.1大学数据库的概念层次

图2.1为一个典型的大学数据库的概念层次表示。其中，AuB表明B是A的概化层

(generalization)；概念层次可由概念树呈现出来。如图2.2图2.2树型概念层次

ANY

undergraduategraduate

freshmansophomorejuniorseniorM.A.M.S.Ph.D.

2.2数据归纳法介绍

一般而言，数据库里存放的数据通常都是在原始概念等级的细部信息。在层次概念中

表现为叶子结点，例如，在一个销售数据库中会有产品名称、品牌、类别、供货商、

产地及价格等等。若能把其归纳至较高较一般化的层级，即层次概念中的非叶子结点。

比如，若我们将圣诞节的热门商品的一般化特征找出来，这对销售及行销经理人将会

有很大的帮助。要达成这个任务就需要用到数据挖掘里的一个重要功能——数据归

铁6器

纳。数据归纳主要有两种方法：⑴数据立方体法(DalaCubeApproach),(2)面向属性归

纳法(Attribute-OrientedInductionApproach)0

2.2.1数据立方体法

数据立方体有许多其它的名称，例如：多重维度数据库(MultidimensionalDatabases)>

具体化景观(MaterializedViews)、在线分析处理(OLAP,On-LineAnalyticalProcessing)o

数据立方体的一般概念为具体化一些经常被要求的高成本计算，尤其是计数(count)、

总计(sum)、求平均数(average)、取最大值(max)等形式的归纳函数，将具体化后的具

体化景观储存在一个多重维度数据库(数据方块)，可供决策支持、知识发现及其它应

用做参考。

Aggrega

S

0维

3维(数据立

数据方块的操作是总计函数的N维度归纳，0维度资料方块是一个点；1维数据方块

是一条线及一个点；2维数据方块是一个交叉表格、一个平面、两条线及一个点；3

维方块是一个有三个交叉的2维交叉表格的方块。如2.3图所示。

数据方块的方法，我们针对不同维度作计算，例如用制造商和年份这两个维度便可以

求出90年代Ford汽车的年平均销售量。索引多重维度数据方块的技术和增加资料方

块的更新也己经被研究。但数据方块可能是相当地疏稀，因为不是在每一维度中的格

子(Cell)都会有相关的资料，所以如何能够有效率地处理疏稀方块的技术是必须被

发展出来的。

2.2.2面向属性归纳法

本节介绍面向属性归纳法的概念和它的一般过程。

2.2.2.1面向属性归法概念

面向属性归纳法是一种以归纳为基础的数据分析技术，其技术核心在丁数据归纳方

法，对于关系数据集合(RelationalDataset)中的每一个属性，检查其分布，判断应归纳

到那个相关的更高的层次。学者对面向属性归纳法也做过不少相关的研究：当某一个

属性的概念层次(ConceptHierarchy)不止只有一种分类法的时候，又提出多属性归

纳图(Multi-attributeGeneralizationGr叩h)的方法来解决。本次设计主要研究基于树型领

域知识，对于基于多属性归纳图的方法不做过多介绍。在面向属性归纳概念层次是必

不可少的背景知识。在存储结构上概念层次通常表现为树或图的形式，这里只对树型

进行讨论，在其中所有结点称作概念。它们有不用的分类，一个概念层次有“一般-

至-特殊”(Gcneral-to-Specific)的顺序性，最一般化的概念(概念树的根结点)，是以

“ANY”来表示之，最特殊的概念(概念树的叶子结点)，则对应到数据库中某一特定

的属性值。

2.2.2.2面向属性归纳的一般过程

面向属性归纳法是利用一些归纳技术来完成数据库中相关数据的属归纳，这些归纳技

术包括属性删除(Attribute-Removal)属性概化也叫概念树爬升(Concept-Tree

Climbing)、属性阈值控制(Attribute-ThresholdControl)等。

首先是属性删除，假如在一个属性中存在着许多不同的属性值，且没有较高的概念层

级可以表示它的话，或者它的更高级的概念层次用其它概念表示，则在归纳的过程，

必须将这个属性删除，接着再做属性概化，若某一属性在概念层次中存在着一个更高

层次的概念，则该属性值就以其更高层级的值来取代。属性概化后，若产生相同的元

组，则将相同的元组合并为一组一般化元组，并将储存相同元组个数的vole值累加后

写到新的元组中。

然而概化过程要做到什么地步停止以防止过度概化，如果所有属性均概化至“ANY”,

这样的概化过程是没意义的。为此我们利用阈值(threshold)来控制以防止过度概化。阈

值控制有两个方面：属性阈值控制和元组阈值控制。如果属性中不同属性值的数目超

过预先设定的阈值，则必须再进一步针对这个属性进行概化。生成一个新归纳后的

relation,其元组数目超过预先设定的阈值，则必须做再进一步的归纳。反复进行直到

属性个数以及元组个数小于或等于预先设定的阈值。最后需要做的工作是规则转换，

即将最终数据表格中的元组，转换成规则。经过这些步骤之后，数据库中原始概念层

级的数据就可以被归纳成层级较高、较一般性的规则了。

利用面向属性归纳法对多属性数据做归纳可以产生许的关联规则，但面对这么多的规

则有一个很重要的问题，“哪些规则是有用的？"，也就是规则兴趣度的衡量问题。如何

找出真正有用处的规则，避免我们陷在茫茫的规则海中，也是一个很有意义研究的课

题。

2.3基于领域知识的面向属性归纳法

在数据挖掘过程中，使用了各种不同的算法，下面介绍几种比较有代表性的基于不同

领域知识的数据挖掘篁法。

2.3.1基于树型领域知识的AOI

目前的许多知识发现大多是“从零开始”的，即没有领域知识前提下的独立发现，既

没有发挥已有知识的作用，找出已有知识隐含的特性，也没有对以后的发现提供必要

的积累，对数据可能的发展趋向做出预测。越来越深入的研究发现，领域知识在数据

挖掘中具有至关重要的地位，它的应用不仅让已有的知识在新的发现过程中的发挥新

作用，并可以对数据可能的发展方向做出预测。

本节涉及的AOI是基于领域知识的面向属性归纳，强调领域知识的应用。

23.1.1基于树型领域知识的AOI算法介绍

前面介绍了面向属性归纳法的一般过程，下面具体介绍下该算法。

算法：面向属性归纳法。根据用户的数据挖掘请求，在关系数据库上挖掘概化特征。

铁8轮

输入：(i)关系数据库DB;(ii)数据挖掘查询DMQuery；(iii)属性表a」isl(包含属性ai);

(iv)属性ai上的概念分层或概化操作符的集合gcn(ai)；(v)每个属性ai的概化阈值

a_gen_thresh(ai)o

盗出：主概化关系P。

方法：方法描述如下V

1.W<-get_task_relevant_data(DMQuery,DB)；

〃工作关素W看放任务相关的数据。

2.Prepare_for_generalization(W)；

〃该步实现如下。

(a)扫描W,收集每个属性ai的不同值。(注意：如果W很大，可以通过考察W的样

本做。)

(b)对于每个属性ai,根据给定的或省缺的属性阈值，确定ai是否应当删除；如果不

删除，则计算它的最个期望层次Li,并确定映射对(v,v，)。其中v是W中ai的步同值,

而U是其在层Li上的概化值。

3.P<-generazation(W)o

通过用其在映射中对应的发V，替换W中的每个值v,累计计数并计算所有的聚集值，

导出主概化关系P。

这一步可以用下面两种方法有效地实现：

(a)对于每个概化原则，通过二分检索将它插入主关系P中。如果元组已在P中，则

简单地增加它地计算值并响应地处理其他聚集值；否则，将它插入P。

(b)在大部分情况下，由于主关系层步同值地个数很少，可以将主关系编码，作为m-

维数组，其中m是P中的属性数，而每个维包含对应的概化属性值。数组的每个原色

存放对应的计数和其他聚集值(如果有的话)。概化元组的插入通对应的数组元素上的

度量聚集进行。

2.332基于多属性概化图AOI算法--AlLGen算法介绍

给定一个关系和一个n个属性集合的n个DGGs,如图2.3所示的All.Gen算法，建

立了该DGGs所有可能的概化属性。在AlLGen算法中，概化函数返回一个概化关系,

其中目标关系中具有Di的属性i概化成Dik并且程序输出保存一个概化关系。结点

Dil是Di中的极小元。初始化函数AlLGen(relation1,n,其中relation(关系)是概

化的目标关系，1是本次迭代中目标属性的的个数，n是迭代中目标属性的总数目，

s是用来初始化SoAlLGen算法对n个属性采用递归的方法反复迭代。输出的是n

个属性的DGGs中各个结点所有联结。对于具有m个属性的n元组数据库，概化算法

为O(n),则其计算复杂度为O(nim=l|Di|),|Di|是DGGDi的结点的数目。

1.procedureAll_Gen(relation,i,m,S)

2.begin

3.fork=ltoIDi|dobeigin

4.ifk>lthen

5.gen_relation<-Generalize(relation,Dik)

6.else

7.gen_relation<-relation

8.end

9.ifi<mthen

10.All_Gen(gen_relation,i+l,m,SUDik)

11.else

12.Output(gen_relation,SUDik)

13.end

14.end

15.end

图2.3多属性概化算法

232Aoi思想方法讲解及其实现构想

面向属性归纳的基本思想是：首先使用关系数据库查询收集任务相关的数据；然后，

通过考察任务相关数据中每个属性的不同值的个数，进行面向属性归纳，或者通过属

性删除，或者通过属性概化进行。聚集通过合并相等的广义元组，并累计它们的计数

值进行，这就压缩了概化后的数据集合。结果广义关系可以映射到不同形式，如图表

或规则，提供用户。

2.3.2.1属性删除(attributeremoval)

如果原始数据中某个属性有大量的不同的值，但是⑴在此属性上没有概化操作符(例

如，对该属性没有定义概念层次)，或者(2)它的较高层概念用其他属性表示，则该属

性应当从工作关系中删除。

2.3.2.2属性概化(attributegeneralization)

如果初始工作关系的某个属性有大量的不同值，并且该属性上存在概化操作，则应当

选择概化操作，即对于该属性中每个值使用其概念层次中父结点来替换，这个过程是

概念层次中属性值沿概念树上升的过程，也可以形象称为沿概念树爬升(concept-tree

climbing)o

232.3阈值控制

阈值是为了防止过度概化，在面向属性归纳中由用户设定或缺省设置的值，一般情况

下，数据挖掘中对属性概化阈值控制有一个缺省的属性阈值(取值范围一般为2到8),

对概化关系阈值控制，数据挖掘也可以预先设定(通常取值范围为10到30)。

这里涉及到的阈值控制有以下两个方面的含义：

A属性概化阈值控制

可以对所有的属性设置同一个概化阈值，或者对每个属性设置一个阈值。如果属性的

不同值个数大于属性概化阈值，则应当进行进一步的属性删除或者属性概化，反之则

结束概化过程。

B概化关系阈值控制

为概化关系设置一个阈值，使得概化结果以更简洁的形式呈现给用户。如果概化关系

中不同原组的个数超过该阈值，则应当进一步概化；否则，进行下一步操作。

332.4阈值控制

经过以上各个步骤，数据库中原始数据已经从概念层次的最低层，爬升到一定的层次,

面向属性归纳的最后一个一个步骤是把从原始数据库中抽取出来，根据一定的领域知

识概化操作后的数据以一定的规则显示给用户，这也是整个数据概化的目的所在。

2.3.3算法比较

本章最后简单对比下本文中提到的两种算法，前面提到的AOI是针对树型领域知识

的，在概化阶段情况比较单一，不存在考虑概化路径的选择问题，沿概念树一步步爬

升就可以达到预期效果，对于AlLGen算法它是针对多属性概化图的面向属性归纳法,

在预处理和属性删除阶段与AOI一致，但它在概化过程中必须涉及路径选择问题，而

且它的层次性不是太明显，概化过程中可能出现概化到更低层次的情况，对于同一的

原始数据，即使是各控制阈值相同也会由于不同的路径选择而出现不同的规则，这就

不可避免的要涉及兴趣度衡量的问题。基于树型领域知识的A0I算法，实现起来比较

简单但脱离现实情况的复杂性和多样性，适用于算法学习和验证，而对于多属性概化

图的算法更接近实际情况，在实际应用中也更有价值，可以预见它是未来面向属性归

纳法的发展方向，但系统实现起来也比较困难。

轶10缺

2.3.4系统实现构想

针对以上AOI的各个步骤，本次设计将对于各个步骤设计一个模块，独立完成各项任

务。特别的添加一个数据预处理和领域知识添加模块，前者主要是对原始数据库中每

个元给增加一个vote值，用来统计概化关系中相同元组的个数，以方便规则转换并且

提供数据的录入功能,领域知识添加模块是为出于系统通用性和完备性考虑，用户可

以自行添加原始概念层次中不存在的概化关系。对于兴趣度衡量问题，由于规则数量

少，本次设计没有涉及相关内容。

第三章系统设计及实现说明

本章是面向属性的归纳法的系统设计及实现部分。包括系统实现总体目标和要求，程

序流程图，模块划分及实现过程中不同模块解决方案，及数据的存储。

3.1程序的总体目标

本次设计是在Windows环境下采用Microsoft公司的VisualC++6.0实现程序界面以及

与此有关操作，利用SQLServer2000作为后台数据库存储原始数据表、概念层次以及

程序运行过程中生成的临时数据表。系统实现的总体要求是对关系数据库中的最低层

的原始数据，按照已经存在的领域知识进行沿概念层次爬升，用更一般的泛化概念来

代替特化的概念，最终对生成的新的数据表进行规则转换操作，得到的规则最终以元

组间析取范式的形式呈现给用户。

3.2程序核心模块流程图

系统实现过程中，对于整个程序也符合自顶向下的处理过程，在VC环境下采用MFC

技术体现了面向对象的思想，整个系统的程序流程图如图3.1所示：

3.3系统模块划分

一般程序运行过程大体上分为如下三个部分：数据输入、数据处理以及结果输出。本

次设计也按照如上三个处理过程划分系统模块。整个程序模块图如图3.2：

和据-数据

性

结

属

艮

母

俞

仆

或R

图

中

上

直

示

既

无

犯

空

既

含

且

叫

nM含

云

轶12缺

图3.1程序

3.3.1输入模块

对于数据输入部分由于这次是对原始数据库的数据进行操作，所以输入模块比较简

单，实现上就是从数据库中导入一张要处理的数据表，使用OBDC数据库连接技术，

连接数据库，并使用ADOC和DataGrid控件来完成原始数据的显示。

3.3.2数据处理模块

该模块是整个系统的主体，实际上对于大多数程序来说也是主要部分。该模块主要实

现AOI算法的主体部分，具体包括如下分模块：数据预处理、属性删除、属性概化、

元组合并、领域知识添加以及阈值控制，下面对各个部分进行单独介绍。

332.1数据预处理

这个模块主要是对输入模块中导入的原始数据进行简单的处理，本次实现的是对每

个元组添加一个记录元组数目的vote值初始值为1,在后续的操作中vote的值会随相

同元组数目的增加而增加。而且这个模块增加了数据录入功能。

3.322属性删除

针对初始化以后的数据，该模块对每个属性值的不同个数进行统计，当某属性有大量

不同值的时候，做如下的判断，若该属性上没有概化操作或者再更高的层次上它使用

别的概念来代替，则删除该属性，若该属性虽有大量不同值则保留，以利于后面的操

作。对于“有大量不同值”的判断使用了阈值控制技术。

3.323属性概化

本模块是面向属性归纳法的核心部分，真正体现沿概念树爬升这个过程。它是反复用

领域知识中较高的层次来替换低层次的概念，直到其中各个属性的个数满足小于等于

控制属性阈值，具体实现上把经过属性删除的数据各属性分别存储到一维字符串数组

中，然后对各个数组中不同值的个数统计，若是大于控制属性阈值则用概念层次中较

高的概念替换数组中各个元素，然后再对其中不同元素的个数作统计，反复以上过程

直到数组中不同元素的个数符合要求。最后把符合要求的元组写到新的数据表中，以

备下一步使用。

3324元^绢合并^

对于属性戒忌后的数据表格，一定会存在重复的元组，这个模块累计相同元组个数写

到vote中作为一条记录。经过这步数据表中已经没有相同元组，并统计出元组个数，

可以进行规则转换操作了。

33.2.5领域知识添加

把领域知识添加作为一个独立的模块是为了考虑程序的通用性，对一个原始的数据库

来说不一定有存储好的领域知识，所以系统使用者可以通过对数据库的学习自己提取

出相关的领域知识，然后以表格的形式存储到数据库中，以备数据概化使用。

对于阈值控制模块，由于不止一个模块涉及到它，本次设计过程中没有作为一个独立

的模块来处理，而是将其分散到属性删除、属性概化及元组合并等模块中。各个模块

有三处涉及到阈值这个词，这里对它们的含义分别阐述。在属性删除和属性概化模块

它是对于每个属性设置一个数值以控制删除和概化操作，属于控制属性阈值。在元组

合并模块它的含义略有不同，是对经过属性删除、属性概化各个步骤操作后的数据，

判断它的元组的个数是否符合要求，这里是控制关系阈值。

3.3.3数据输出模块

本系统输出模块包括提取出的规则输出，领域知识的输出以及属性删除和属性概化两

个中间结果输出。

3.4数据结构实现

数据结构是数据在计算机中的存储形式，采用适当的数据结构可以节省内存空间，还

可以提高运行效率，而且程序也会更加健壮。在本次毕业设计实现AOI算法过程中，

轶14缺

由丁数据表中的数据要按照概念层次对原有的数据进行数据概化，且进行数据概化的

时候，涉及到广义元组，故采用字符串数组作为主要的存储结构。接收进来以及即将

输出的数据表均存储在二维字符串数组中。中恒运算所需要的还有一维字符串数组，

如：概化过程每个属性值的存储和字符串，字符串主要是用于对数据库的各项操作，

连接、添加、删除等V

考虑程序的健壮性，整个程序实现过程中，尽量使用局部变量，使用较少的全局变量,

不但节省了内存空间，对程序运行的安全性也有促进作用。

3.5数据库设计

数据库设计主要是进行数据库的逻辑设计，即将数据按一定的分类、分组系统和逻辑

层次组织起来，是面向用户的。数据库设计时需要综合用户存档数据和数据需求，分

析各个数据之间的关系，按照DBMS提供的功能和描述工具，设计出规模适当、正确

反映数据关系、数据冗余少、存取效率高、能满足多种查询要求的数据模型。

对于一个常规的系统来说，数据库的设计应该占相当大的比例。不过本次设计算法较

为特殊，它是对已有的关系数据库中原始数据进行操作，简化了数据库的设计过程。

对于所完成的系统，设计数据库只涉及到两个原始数据表，一个是用于存储要进行概

化数据的数据表，另一个是概化的依据领域知识的存储。当然在程序运行过程中为了

操作上的方便，将其中一部分的中间结果也存储在数据表中。

第四章系统使用方法简介

本章主要是系统介绍章节，它包括如下内容，系统主要模块运行界面的介绍，系统使

用方法说明以及系统在使用过程中的相关注意点。

4.1系统主要模块运行界面

针对上一章中系统设计中提到的各个模块，这一小节将给出程序主要界面的运行截图

和各个模块的操作方法。

图4.1程序运行主界面

图4.1是程序运行的主界面，各个步骤的操作以菜单的形式体现，其中数据预处理下

拉菜单包含“数据导入”、“属性删除”、“属性概化”和“背景知识添加”几个子菜单,

阈值确定菜单是针对属性删除的控制属性阈值以确定那些属性在下一步操作过程中

予以保留，面向属性归纳菜单中，为了避免和数据预处理菜单重复，只设计了元组合

并”和“规则转换”两个子菜单，结果显示有“属性删除”、“属性概化”和“规则显

示”三个菜单用以查看各个处理结果，最后的退出系统没有子菜单，它只提供退出操

作。

图4.2数据导入模块

图4.2是原始数据导入后的运行界面，为了方便操作，添加了一个数据记录添加操作,

这也可以用于向木身空的数据表中录入数据，避免在SOLserver2000下进行直接操作,

其中各个按键钮的作用如其自身的名称。

*16*

图4.3属性删除

这个界面是经过初始化后的数据表的显示，删除了无关属性，并且增加了vote歹IJ,以

便合并元组时使用，对于各个属性是否要保留提供了属性管制阈值然后可以选择输入

不同的属性进行判断，属性判断会读取“已有概化字段表”以判断各个属性是否可以

进行概化。“下一步”按钮则转到选择数据集的操作上。

属1X

尾1种隆后sQudent

▲

Status1MajorBirthPlaceIGPAvote

MAhistoryVancouver3.51

juniormathCalgary3.71

juniorliteratureEdmonton2.61

M.S.physiceOttawa3.91

Ph.D.mathBombay3.31

♦

请选择目标集graduateJ碉定

目标student

Major］而"hPlace

►historyVancouver

_physiceOttawa

mathBombay

biologyShanghai

computingVictoria

statisticsNanjing

图4.4选择目标集

这个模块没有提供太多的操作，是为了方便用户有针对的选择目标数据，以进行下一

步的操作，对于本例提供两个选项：“graduate”和“undergraduate”。

收性格化X

目标数据隼

Major1BirthPlaceGPA

►hintory_Vancouver3.5

physiceO