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

1、近年来数据库技术不断成熟，面对大量数据，人们没有完全分析这些数据的能力，同时迫切需要将这些数据转化成有用的信息，KDD技术随之产生。在工程领域，数据挖掘是KDD过程的核心部分，它是从已有数据中发掘出隐含的、未知的、潜在的、有用的信息并预测数据发展趋势的过程。然而目前的KDD过程并未有效的利用领域知识，所谓领域知识是数据库中没有明确表示，但可以引导知识发现过程，搜索有用的知识、摒弃对用户没有价值的发现结果的信息。计算机中它表现的存储结构主要有比较简单的树型结构，以及更为接近现实的图的结构形式。本课题主要是研究学习基于树型领域知识的AOI算法，它是应用已有的领域知识对原始数据进行属性概化，以提取出

2、有意义的规则。本系统用VC+6.0,设计系统界面，采用SQLServer2000做后台数据库，实现了基于树型领域知识AOI算法以发掘一系列规则，如特征规则、分类规则、区分规则、量化规则等等。通过对整个AOI方法实现，加深了对数据概化、属性删除、属性概化、领域知识、阈值控制等面向属性归纳法相关知识的了解，并进一步的熟悉了VC+6.0与SQLServer2000的使用。关键词：数据挖掘，领域知识，概念层次，数据概化，阈值控制第二章领域知识的基本理论本章介绍本次毕业设计的理论依据，包括领域知识的作用，数据归纳法的介绍，基于领域知识的面向属性归纳法，其中着重介绍设计实现的基于树型领域知识的AOI算法并

3、且简要对比各种算法，最后是系统实现构想部分，对AOI各个步骤的实现提出构想。2.1领域知识的应用和作用在前一章的介绍中阐述的领域知识的各种定义，这里我们做自己的诠释，将领域知识定义为在数据库中没有明确表示，但可以引导知识发现过程搜索有趣的知识、摒弃对用户没有价值的发现结果的信息它是本次课题的背景知识。它是本次设计的背景知识，是用概念层次描述的用于控制概化过程的必要依据。用概念层次这一术语描述时,通常把概念层次的不同层组织成一种概念拓扑结构。这种概念拓扑结构根据“一般-至-特殊(general-to-specific)的序列形成了一种偏序关系。最高度泛化的概念是空概念(用保留字”Any”描述)对

4、应于概念层次树中的根结点，对应于数据库中具体的属性值是概念层次中最高度特化的概念，在概念层次树中它表现为叶子结点。图2.1和图2.2是一个典型的大学生数据库中领域知识的两种不同表示方法。用树的形式来表示领域知识，层次分明，但更为复杂的情况是用图来表示各个概念之间的关系，图的形式接近实际，层次性却不是那么明显。本次设计着重针对树型的领域知识进行讨论。freshman,sophomore,junior,seniorcundergraduateMS.,MA.,PhD.czgraduateundergraduate,graduateuANY(status)图2.1大学数据库的概念层次图2.1为一个典型

5、的大学数据库的概念层次表示。其中，AuB表明B是A的概化层(generalization)；概念层次可由概念树呈现出来。如图2.2图2.2树型概念层次ANYundergraduategraduateM.A.M.S.Ph.D.freshmansophomorejuniorsenior2.2数据归纳法介绍一般而言，数据库里存放的数据通常都是在原始概念等级的细部信息。在层次概念中表现为叶子结点，例如，在一个销售数据库中会有产品名称、品牌、类别、供货商、产地及价格等等。若能把其归纳至较高较一般化的层级，即层次概念中的非叶子结点。比如，若我们将圣诞节的热门商品的一般化特征找出来，这对销售及行销经理人将会

6、有很大的帮助。要达成这个任务就需要用到数据挖掘里的一个重要功能一一数据归纳。数据归纳主要有两种方法：(1)数据立方体法(DataCubeApproach),(2)面向属性归纳法(Attribute-OrientedInductionApproach)o2.2.1数据立方体法数据立方体有许多其它的名称，例如：多重维度数据库(MultidimensionalDatabases)>具体化景观(MaterializedViews)>在线分析处理(OLAP,On-LineAnalyticalProcessing)o数据立方体的一般概念为具体化一些经常被要求的高成本计算，尤其是计数(count

7、)、总计(sum)>求平均数(average)>取最大值(max)等形式的归纳函数，将具体化后的具体化景观储存在一个多重维度数据库(数据方块)，可供决策支持、知识发现及其它应用做参考。By2维(点、线、RWBS1维(点、3维(数据立ByAggrega图2.3数据方块的操作是总计函数的N维度归纳，。维度资料方块是一个点；1维数据方块是一条线及一个点；2维数据方块是一个交叉表格、一个平面、两条线及一个点；3维方块是一个有三个交叉的2维交叉表格的方块。如2.3图所示。数据方块的方法，我们针对不同维度作计算，例如用制造商和年份这两个维度便可以求出90年代Ford汽车的年平均销售量。索引多重

8、维度数据方块的技术和增加资料方块的更新也己经被研究。但数据方块可能是相当地疏稀，因为不是在每一维度中的格子(Cell)都会有相关的资料，所以如何能够有效率地处理疏稀方块的技术是必须被发展出来的。2.2.2面向属性归纳法本节介绍面向属性归纳法的概念和它的一般过程。面向属性归法概念面向属性归纳法是一种以归纳为基础的数据分析技术，其技术核心在于数据归纳方法，对于关系数据集合(RelationalDataset)中的每一个属性，检查其分布，判断应归纳到那个相关的更高的层次。学者对面向属性归纳法也做过不少相关的研究：当某一个属性的概念层次(ConceptHierarchy)不止只有一种分类

9、法的时候，又提出多属性归纳图(Multi-attributeGeneralizationGraph)的方法来解决。本次设计主要研究基于树型领域知识，对于基于多属性归纳图的方法不做过多介绍。在面向属性归纳概念层次是必不可少的背景知识。在存储结构上概念层次通常表现为树或图的形式，这里只对树型进行讨论，在其中所有结点称作概念。它们有不用的分类，一个概念层次有“一般-至-特殊(General-to-Specific)的顺序性，最一般化的概念(概念树的根结点)，是以“ANY”来表示之，最特殊的概念(概念树的叶子结点)，则对应到数据库中某一特定的属性值。面向属性归纳的一般过程面向属性归纳法是

10、利用一些归纳技术来完成数据库中相关数据的属归纳，这些归纳技术包括属性删除(Attribute-Removal)、属性概化也叫概念树爬升(Concept-TreeClimbing)>属性阈值控制(Attribute-ThresholdControl)等。首先是属性删除，假如在一个属性中存在着许多不同的属性值，且没有较高的概念层级可以表示它的话，或者它的更高级的概念层次用其它概念表示，则在归纳的过程，必须将这个属性删除。接着再做属性概化，若某一属性在概念层次中存在着一个更高层次的概念，则该属性值就以其更高层级的值来取代。属性概化后，若产生相同的元组，则将相同的元组合并为一组一般化元组，并将储

11、存相同元组个数的vote值累加后写到新的元组中。然而概化过程要做到什么地步停止以防止过度概化，如果所有属性均概化至“ANY”,这样的概化过程是没意义的。为此我们利用阈值(threshold)来控制以防止过度概化。阈值控制有两个方面：属性阈值控制和元组阈值控制。如果属性中不同属性值的数目超过预先设定的阈值，则必须再进一步针对这个属性进行概化。生成一个新归纳后的relation,其元组数目超过预先设定的阈值，则必须做再进一步的归纳。反复进行直到属性个数以及元组个数小于或等于预先设定的阈值。最后需要做的工作是规则转换，即将最终数据表格中的元组，转换成规则。经过这些步骤之后，数据库中原始概念层级的数据

12、就可以被归纳成层级较高、较一般性的规则了。利用面向属性归纳法对多属性数据做归纳可以产生许的关联规则，但面对这么多的规则有一个很重要的问题，“哪些规则是有用的？。也就是规则兴趣度的衡量问题。如何找出真正有用处的规则，避免我们陷在茫茫的规则海中，也是一个很有意义研究的课题。2.3基于领域知识的面向属性归纳法在数据挖掘过程中，使用了各种不同的算法，下面介绍几种比较有代表性的基于不同领域知识的数据挖掘算法。2.3.1基于树型领域知识的AOI目前的许多知识发现大多是“从零开始”的，即没有领域知识前提下的独立发现，既没有发挥已有知识的作用，找出已有知识隐含的特性，也没有对以后的发现提供必要的积累，对数据可

13、能的发展趋向做出预测。越来越深入的研究发现，领域知识在数据挖掘中具有至关重要的地位，它的应用不仅让已有的知识在新的发现过程中的发挥新作用，并可以对数据可能的发展方向做出预测。本节涉及的AOI是基于领域知识的面向属性归纳，强调领域知识的应用。基于树型领域知识的AOI算法介绍前面介绍了面向属性归纳法的一般过程，下面具体介绍下该算法。算法：面向属性归纳法。根据用户的数据挖掘请求，在关系数据库上挖掘概化特征。赣8辙输入：(i)关系数据库DB；(ii)数据挖掘查询DMQuery；(iii)属性表a_list(包含属性ai)；(iv)属性ai上的概念分层或概化操作符的集合gen(ai)；(v

14、)每个属性ai的概化阈值a_gen_thresh(ai)。输出：主概化关系P。方法：方法描述如下。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的步同值,而。是其在层Li上的概化值。3P<-gener

15、azation(W)。通过用其在映射中对应的发寸替换W中的每个值v,累计计数并计算所有的聚集值，导出主概化关系Po这一步可以用下面两种方法有效地实现：(a) 对于每个概化原则，通过二分检索将它插入主关系P中。如果元组已在P中，则简单地增加它地计算值并响应地处理其他聚集值；否则，将它插入P。(b) 在大部分情况下，由于主关系层步同值地个数很少，可以将主关系编码，作为m-维数组，其中m是P中的属性数，而每个维包含对应的概化属性值。数组的每个原色存放对应的计数和其他聚集值(如果有的话)。概化元组的插入通对应的数组元素上的度量聚集进行。2.33.2基于多属性概化图AOI算法-All_Gen算法介绍给定

16、一个关系和一个n个属性集合的n个DGGs,如图2.3所示的All_Gen算法，建立了该DGGs所有可能的概化属性。在AlLGen算法中，概化函数返回一个概化关系,其中目标关系中具有;Di的属性i概化成Dik并且程序输出保存一个概化关系。结点Dil是Di中的极小元。初始化函数AlLGen(relation,l,n,s),其中relation(关系)是概化的目标关系，1是本次迭代中目标属性的的个数，n是迭代中目标属性的总数目，s是用来初始化SoAlLGen算法对n个属性采用递归的方法反复迭代。输出的是n个属性的DGGs中各个结点所有联结。对于具有m个属性的n元组数据库，概化算法为O(n),则其计算

17、复杂度为O(nim=l|Di|),|Di|是DGGDi的结点的数目。1. procedureAll_Gen(relation,i,m,S)2. begin3. fork=lto|Di|dobeigin4. ifk>lthen5. gen_relationGeneralize(relation,Dik)6. else7. gen_relation-relation8. end9. ifi<mthen10. All_Gen(gen_relation,i+l,m,SUDik)11. else12. Output(gen_relation,SUDik)13. end14. end15. e

18、nd图2.3多属性概化算法2.3.2AOI思想方法讲解及其实现构想面向属性归纳的基本思想是：首先使用关系数据库查询收集任务相关的数据；然后，通过考察任务相关数据中每个属性的不同值的个数，进行面向属性归纳，或者通过属性删除，或者通过属性概化进行。聚集通过合并相等的广义元组，并累计它们的计数值进行，这就压缩了概化后的数据集合。结果广义关系可以映射到不同形式，如图表或规则，提供用户。 属性删除(attributeremoval)如果原始数据中某个属性有大量的不同的值，但是(1)在此属性上没有概化操作符(例如，对该属性没有定义概念层次)，或者(2)它的较高层概念用其他属性表示，则该属性应

19、当从工作关系中删除。 属性概化(attributegeneralization)如果初始工作关系的某个属性有大量的不同值，并且该属性上存在概化操作，则应当选择概化操作，即对于该属性中每个值使用其概念层次中父结点来替换，这个过程是概念层次中属性值沿概念树上升的过程，也可以形象称为沿概念树爬升(concept-treeclimbing)。阈值控制阈值是为了防止过度概化，在面向属性归纳中由用户设定或缺省设置的值，一般情况下，数据挖掘中对属性概化阈值控制有一个缺省的属性阈值(取值范围一般为2到8),对概化关系阈值控制，数据挖掘也可以预先设定(通常取值范围为10到30)。这里

20、涉及到的阈值控制有以下两个方面的含义：A属性概化阈值控制可以对所有的属性设置同一个概化阈值，或者对每个属性设置一个阈值。如果属性的不同值个数大于属性概化阈值，则应当进行进一步的属性删除或者属性概化，反之则结束概化过程。B概化关系阈值控制为概化关系设置一个阈值，使得概化结果以更简洁的形式呈现给用户。如果概化关系中不同原组的个数超过该阈值，则应当进一步概化；否则，进行下一步操作。3.3.2A阈值控制经过以上各个步骤，数据库中原始数据已经从概念层次的最低层，爬升到一定的层次,面向属性归纳的最后一个一个步骤是把从原始数据库中抽取出来，根据一定的领域知识概化操作后的数据以一定的规则显示给用户，这也是整个

21、数据概化的目的所在。2.3.3算法比较本章最后简单对比下本文中提到的两种算法，前面提到的AOI是针对树型领域知识的，在概化阶段情况比较单一，不存在考虑概化路径的选择问题，沿概念树一步步爬升就可以达到预期效果，对于AlLGen算法它是针对多属性概化图的面向属性归纳法,在预处理和属性删除阶段与AOI一致，但它在概化过程中必须涉及路径选择问题，而且它的层次性不是太明显，概化过程中可能出现概化到更低层次的情况，对于同一的原始数据，即使是各控制阈值相同也会由于不同的路径选择而出现不同的规则，这就不可避免的要涉及兴趣度衡量的问题。基于树型领域知识的AOI算法，实现起来比较简单但脱离现实情况的复杂性和多样性

22、，适用于算法学习和验证，而对于多属性概化图的算法更接近实际情况，在实际应用中也更有价值，可以预见它是未来面向属性归纳法的发展方向，但系统实现起来也比较困难。2.3.4系统实现构想针对以上AOI的各个步骤，本次设计将对于各个步骤设计一个模块，独立完成各项任务。特别的添加一个数据预处理和领域知识添加模块，前者主要是对原始数据库中每个元给增加一个vote值，用来统计概化关系中相同元组的个数，以方便规则转换并且提供数据的录入功能。领域知识添加模块是为出于系统通用性和完备性考虑，用户可以自行添加原始概念层次中不存在的概化关系。对于兴趣度衡量问题，由于规则数量少，本次设计没有涉及相关内容。第三章系统设计及

23、实现说明本章是面向属性的归纳法的系统设计及实现部分。包括系统实现总体目标和要求，程序流程图，模块划分及实现过程中不同模块解决方案，及数据的存储。3.1程序的总体目标本次设计是在Windows环境下采用Microsoft公司的VisualC+6.0实现程序界面以及与此有关操作，利用SQLServer2000作为后台数据库存储原始数据表、概念层次以及程序运行过程中生成的临时数据表。系统实现的总体要求是对关系数据库中的最低层的原始数据，按照已经存在的领域知识进行沿概念层次爬升，用更一般的泛化概念来代替特化的概念，最终对生成的新的数据表进行规则转换操作，得到的规则最终以元组间析取范式的形式呈现给用户。

24、3.2程序核心模块流程图系统实现过程中，对于整个程序也符合自顶向下的处理过程，在VC环境下采用MFC技术体现了面向对象的思想，整个系统的程序流程图如图3.1所示：3.3系统模块划分一般程序运行过程大体上分为如下三个部分：数据输入、数据处理以及结果输出。本次设计也按照如上三个处理过程划分系统模块。整个程序模块图如图3.2：图3.1程序3.3.1输入模块对于数据输入部分由于这次是对原始数据库的数据进行操作，所以输入模块比较简单，实现上就是从数据库中导入一张要处理的数据表，使用OBDC数据库连接技术，连接数据库，并使用ADOC和DataGrid控件来完成原始数据的显示。3.3.2数据处理模块该模块是

25、整个系统的主体，实际上对于大多数程序来说也是主要部分。该模块主要实现AOI算法的主体部分，具体包括如下分模块：数据预处理、属性删除、属性概化、元组合并、领域知识添加以及阈值控制，下面对各个部分进行单独介绍。数据预处理这个模块主要是对输入模块中导入的原始数据进行简单的处理，本次实现的是对每个元组添加一个记录元组数目的vote值初始值为1,在后续的操作中vote的值会随相同元组数目的增加而增加。而且这个模块增加了数据录入功能。属性删除针对初始化以后的数据，该模块对每个属性值的不同个数进行统计，当某属性有大量不同值的时候，做如下的判断，若该属性上没有概化操作或者再更高的层

26、次上它使用别的概念来代替，则删除该属性，若该属性虽有大量不同值则保留，以利于后面的操作。对于“有大量不同值”的判断使用了阈值控制技术。33.2.3属性概化本模块是面向属性归纳法的核心部分，真正体现沿概念树爬升这个过程。它是反复用领域知识中较高的层次来替换低层次的概念，直到其中各个属性的个数满足小于等于控制属性阈值，具体实现上把经过属性删除的数据各属性分别存储到一维字符串数组中，然后对各个数组中不同值的个数统计，若是大于控制属性阈值则用概念层次中较高的概念替换数组中各个元素，然后再对其中不同元素的个数作统计，反复以上过程直到数组中不同元素的个数符合要求。最后把符合要求的元组写到新的数据表中，以备

27、下一步使用。元组合并对于属性概化后的数据表格，一定会存在重复的元组，这个模块累计相同元组个数写到vote中作为一条记录。经过这步数据表中已经没有相同元组，并统计出元组个数，可以进行规则转换操作了。领域知识添加把领域知识添加作为一个独立的模块是为了考虑程序的通用性，对一个原始的数据库来说不一定有存储好的领域知识，所以系统使用者可以通过对数据库的学习自己提取出相关的领域知识，然后以表格的形式存储到数据库中，以备数据概化使用。对于阈值控制模块，由于不止一个模块涉及到它，本次设计过程中没有作为一个独立的模块来处理，而是将其分散到属性删除、属性概化及元组合并等模块中。各个模块

28、有三处涉及到阈值这个词，这里对它们的含义分别阐述。在属性删除和属性概化模块它是对于每个属性设置一个数值以控制删除和概化操作，属于控制属性阈值。在元组合并模块它的含义略有不同，是对经过属性删除、属性概化各个步骤操作后的数据，判断它的元组的个数是否符合要求，这里是控制关系阈值。3.3.3数据输出模块本系统输出模块包括提取出的规则输出，领域知识的输出以及属性删除和属性概化两个中间结果输出。3.4数据结构实现数据结构是数据在计算机中的存储形式，采用适当的数据结构可以节省内存空间，还可以提高运行效率，而且程序也会更加健壮。在本次毕业设计实现AOI算法过程中，赣14赣由于数据表中的数据要按照概念层次对原有

29、的数据进行数据概化，且进行数据概化的时候，涉及到广义元组，故采用字符串数组作为主要的存储结构。接收进来以及即将输出的数据表均存储在二维字符串数组中。中间运算所需要的还有一维字符串数组，如：概化过程每个属性值的存储和字符串，字符串主要是用于对数据库的各项操作，连接、添加、删除等。考虑程序的健壮性，整个程序实现过程中，尽量使用局部变量，使用较少的全局变量,不但节省了内存空间，对程序运行的安全性也有促进作用。3.5数据库设计数据库设计主要是进行数据库的逻辑设计，即将数据按一定的分类、分组系统和逻辑层次组织起来，是面向用户的。数据库设计时需要综合用户存档数据和数据需求，分析各个数据之间的关系，按照DB

30、MS提供的功能和描述工具，设计出规模适当、正确反映数据关系、数据冗余少、存取效率高、能满足多种查询要求的数据模型。对于一个常规的系统来说，数据库的设计应该占相当大的比例。不过本次设计算法较为特殊，它是对已有的关系数据库中原始数据进行操作，简化了数据库的设计过程。对于所完成的系统，设计数据库只涉及到两个原始数据表，一个是用于存储要进行概化数据的数据表，另一个是概化的依据领域知识的存储。当然在程序运行过程中为了操作上的方便，将其中一部分的中间结果也存储在数据表中。AbstractRecentyears,thetechniqueofdatabasehasbeencomingtomaturity.An

31、dthescaleofdatabaseismoreandmoresweeping.Peoplehavenofullabilitytoanalyzedatainthesedatabases.Meanwhileitisneededtodiscoverusefulinformationfromthem.Inthiscase,KDD(shortforknowledgediscoveryindatabases)hasbeendeveloped.Inthefieldofengineering,asthemainprocessofKDD,DM(shortfordatamining)isthenontrivi

32、alextractionofimplicit,previouslyunknown,andpotentiallyusefulinformationfromdata.Atthesametime,itcandopeoutthetrendofthedevelopmentofdata.Unfortunately,atpresentdomainknowledgehasn'tbeenusedeffectivelywhenpeopledoKDD.Sodomainknowledgeisimplicitindatabases.ButitcanmaketheprocessofKDDclear,andtell

33、usefulinformationfromtrashy.Incomputer,itcanbestoredasthestructureoftreewhichissimple,andtheotherapproachisstoreitasgraphwhichismorecomplexbutmuchnearertofact.ThispaperismainlytostudythealgorithmofAOIinwhichdomainknowledgeexistedisusedtogeneralizetheoriginaldataindatabases.Duringitwewilldiscoveraser

34、ialofrules,suchascharacteristicrule,classificationrule,discriminantrule,quantityruleandsoon.Duringthedesign,VC+6.0wasusedasthedevelopingenvironmentwiththeprogramlanguageofC+todesignthesysteminterface.Astothedatabasemanagement,SQLServer2000wasadoptedtomanagedataandrelationsamongthem.Intheprogram,itis

35、realizedthatAOIalgorithmbasedondomainknowledgeoftree.Theprogramistodiscoversomeimplicitandusefulrulesfromoriginaldata.ItmakesmelearnmoreconceptsaboutAOIsuchasdatageneralization,attributeremoval,attributegeneralization,domainknowledge,thresholdcontroletc.ItalsomakesmebemorefamiliarwiththeusageofVC+6.

36、0andSQLServer2000.Keywords:datamining,domainknowledge,concepthierarchy,datageneralization,thresholdcontro第四章系统使用方法简介本章主要是系统介绍章节，它包括如下内容，系统主要模块运行界面的介绍，系统使用方法说明以及系统在使用过程中的相关注意点。4.1系统主要模块运行界面针对上一章中系统设计中提到的各个模块，这一小节将给出程序主要界面的运行截图和各个模块的操作方法。图4.1程序运行主界面图4.1是程序运行的主界面，各个步骤的操作以菜单的形式体现，其中数据预处理下拉菜单包含“数据导入”、“属性

37、删除”、“属性概化”和“背景知识添加”几个子菜单,阈值确定菜单是针对属性删除的控制属性阈值以确定那些属性在下一步操作过程中予以保留，面向属性归纳菜单中，为了避免和数据预处理菜单重复，只设计了元组合并”和“规则转换”两个子菜单，结果显示有“属性删除”、“属性概化”和“规则显示”三个菜单用以查看各个处理结果，最后的退出系统没有子菜单，它只提供退出操作。图4.2数据导入模块图4.2是原始数据导入后的运行界面，为了方便操作，添加了一个数据记录添加操作,这也可以用于向本身空的数据表中录入数据，避免在SOLserver2000下进行直接操作,其中各个按键钮的作用如其自身的名称。赣16赣X图4.3属性删除这

38、个界面是经过初始化后的数据表的显示，删除了无关属性，并且增加了vote列，以便合并元组时使用，对于各个属性是否要保留提供了属性管制阈值然后可以选择输入不同的属性进行判断，属性判断会读取“已有概化字段表”以判断各个属性是否可以进行概化。“下一步”按钮则转到选择数据集的操作上。图4.4选择目标集这个模块没有提供太多的操作，是为了方便用户有针对的选择目标数据，以进行下一步的操作，对于本例提供两个选项：“graduate"和“undergraduate”。目标锻据集MaiorBirthPlaceGPAhistoryVancouver3.5phvsiceOttawa3.9mathBombay3

39、.3biologyShanghai3.4computingVictoria3.8statisticsNaniinq3.2属性阈值确认慨化上一步确认慨化上一步下一步退.出图4.4属性概化到了这个模块，就是进行属性概化工作，它接受用户控制属性阈值，程序自动判断,那些属性要进行概化，哪些属性跳过这个步骤。图4.6元组合并这个模块是对操作后的数据进行元组合并工作，为最后的规则输出做准备。请选择要显示的规则确土刷新|添加规则前驱（规则|3后继添加|确土刷新|添加规则前驱（规则|3后继添加|前驱sciencechemistryphysicscomputingliteraturesicenceartfres

40、hmansophomorejuniorseniorsciencesciencescienceartANY(major|ANY(major)undergraduateundergraduateundergraduateundergraduatenrstdaiMtR退出图4.7规则显示及添加图4.7是领域知识添加模块，主要提供显示已有领域知识，也可以由用户往数据库中自由添加，默认的是显示所有领域知识，当然用户可以选择不同的概念层次以显示清晰，就本次实现上有“Major”、“Birth_Place”和“Status”三个选项供用户选择。4.2使用方法说明本系统进入主界面之后，首先导入原始数据，先进行

41、数据初始化，然后按照用户自己的要求对原始数据做属性删除或者属性概化，或者先属性删除再属性概化，再在指定模块中进行背景知识的添加，即概念层次的构造。在预处理过程中，要求设定阈值，然后按照要求进行面向属性的归纳，最终输出规则（量化和特征规则）。将得到的结果（数据表格形式）导入知识规则的规则转换模块中，进行区别规则和量化规则的提取。4.3相关注意点在系统运行过程中，用户可以自由选择各个过程，而没有必要按照AOI算法的各个步骤依次执行，这是由于本系统实现过程中保留了各个中间结果，因此若是第一次运行,有必要按步骤依次执行，否则可能会出错。对于普通用户不建议直接在SOLserver2000环境下对表进行直

42、接增删，设计实现过程中，有表的不断创建与删除过程，因此不熟悉程序各个过程的情况下直接删除表格，会导致运行出错。第五章系统运行测试结果本章使用一组数据对系统进行测试，验证算法。主要内容有测试方法的简单介绍，数据的来源以及运行结果等。5.1系统测试原理及方法简介在软件工程领域，测试主要分为两种：黑盒和白盒两种绍下两种方法：白盒测试：着重程序逻辑结构和控制结构的测试，主要技术有，选择有代表性的程序通路，对其中的通路进行逻辑测试，或者是根据程序的控制结构设计测试数据。这种方法要求对程序有相当的了解，能够发现程序中逻辑和编码的错误，技术要求高，是测试的主要方法。黑盒测试：它是对白盒测试的补充，注重程序的

43、功能测试。针对程序的功能设计输入测试数据，对输出进行判断检测其是否符合要求。它不同于白盒测试主要用于后期测试，本次主要是采用黑盒测试的方法。5.2数据来源本次实验的软硬件环境是：Celeron(R)2.53GHz,512M内存，WindowsXP操作系统，VisualC+6.0,SQLServer2000数据库；数据来源于参考文献CaiY，CerconeN.，HanJ.Attribute-orientedinductioninrelationaldatabases.In:Piatetsky-Shapiro,FrawleyW.J.eds.KnowledgeDiscoveryinDatabases

44、.MenloPark,California:AAAIPress/TheMITPress,1991,213-228.。本次测试主要是先在SQLServer2000下建立数据库，输入大学学生关系数据库和概念层次。图5.1典型大学数据库NameStatusMajorBnthPlaceGPAAndersonMAhistory*ancouver3.5BachjximormathCalgary3.7CarltonjuniorliberalartsEdmonton2.6FraserM.S.physicsOttawa3.9GuptaPhD.mathBombay33HartsophomorechemistrvR

45、ichmond2.7JacksonseniorcomputingVictoria35LiuPhD.biologyShanshaiJ3.4-MeyersophomoremusicBurnaby3.0XfonkPhD-computingVictoria3.8WansM.S.statisticsNamms3.2宣立马区钢贝IJbiolog'y*Gsciencechemistryesciencephysicsesciencecomputing丘scienceliteratureeartsicenceAhlX(majorarteAhlY(major)freshmaneundergradtjate

46、sophomoreeundergraduatejunior丘undergraduateseniorICundergraduate图5.2概念层次存储表图5.1和5.2是本次测试的数据来源，5.1是典型的大学数据库，5.2是存储成表格的领域知识。5.3数据处理及运行结果裱20溯1、对原始数据关系初始化之后，表5.1首先进行属性删除操作，其中Name列符合属性删除的条件被删除，操作结果如图5.2显示。DataGridlNameStatusMajorBirthPlaceGPAvoteAndersonM.A.historyVancouver3.51BachjuniormathCalgary3.71|_

47、CarltonjuniorliteratureEdmonton2.61FraserM.S.physiceOttawa3.91GuptaPh.D.mathBombay3.31HartsophomorechemistryRichmond2.71JacksonseniorcomputingVictoria3.51LiuPh.D.biologyShanghai3.41MeyersophomoremusicBurnaby2.711r*irxcc图5.3预处理结果从表中可以看出在原表格上新增了属性列vote用以计数累加初始值均为1,同时选择数据操作集graduateo2、对提取出的数据操作集graduat

48、e由于其经过初始化和属性删除可以进行下一步操作属性概化一这是沿概念层次爬升的体现，同时进行元组合并，其运行结果如图5.4MajorBirthPlaceGAPvotescienceCalgaryexcellent1artEdmontonaverage1scienceRichmondaverage1scienceVictoriaexcellent1artBurnabyaverage1artTorontoexcellent1图5.4概化结果一3、对于表5.4还应该进行阈值控制测试，发现它不满足设定的阈值(阈值为3)要求,故需进一步进行属性阈值控制，所得结果如图5.5。MajorBirthPlaceG

49、APvotescienceCanadaexcellent3scienceforeigngood3图5.5概化结果二4>对表5.5它已经满足关系控制阈值则可进行规则转变，得到最终的规则如图5.5所/J'o规则显不：任意h)graduate->(Major(x)escienceABirth_Place(x)CanadaAGPA(x)eexcellent)50VMajor(x)scienceABirth_Place(x)foreignAGPA(x)good)50图5.6规则转换结果从图5.5和图5.6可以看出对于任意一个研究生，他的major是science并且Birth_Pla

50、ce是Canada,则他的GPA一定为excellent,这就是得出的一条特征规则。另外，图5.6还显示了一条量化规则，对于任意一个研究生它有50%的可能是major为science,Birth_Place为Canada,并且GPA为excellent,另外的50%可能是这样的情况，major为science,Birth_Place为foreign,并且GPA为goodo5、还可以对undergraduate进行面向属性归纳，提取出特征规则和量化规则。此外，还可以将graduate得出的结果作为目标类，undergraduate得出的结果作为对比类，提取出量化和区别规则，如图5.7所示。Maj

51、orBirthPlaceGPAvotemarkscienceCanadaexcellent3*scienceforeigngood3IMajorBirthPlaceGPAvotemarkscienceCanadaexcellent2artCanadaaverage1scienceCanadaaverage1artCanadagood1artCanadaexcellent1图5.7目标类graduate和对比类undergraduate从图5.7的两个表中，可以得到量化和区别规则，如图5.8,即对于一个学生如果他主修science,出生在Canada,而且GPA是excellent,则他有60%

52、的可能性是graduate,如果一个学生他主修science,出生在foreign,而且GPA是good,则他一定是graduate,以上两条规则是目标类graduate和对比类undergraduate比较出来的量化规则，因此叫做量化和区别规则。规则显示：任意的graduate->(majorscienceAbirth_place(x)UCanadaAGPA(x)Uexcellent)60三V(major(x)WscienceAbirth_place(x)UforeignAGPA(x)Wgood)100图5.8量化和区别规则第六章课题研究结论及工作展望本章总结本次毕业设计的整个过程。第

53、一部分是工作总结，包括我在整个毕业设计期间完成的主要工作和一些心得体会；第二部分为工作展望，对本次毕业设计中尚不完善部分也加以概括，并对未来今后的工作和学习方向加以规划。6.1工作总结数据挖掘是从大量的、模糊的、随机的、不完全的、有噪音的数据中，提取隐含在其中的、人们事先不知道的、但又是有用的潜在信息和知识的过程。近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是人们对于大量信息存在这样一种尴尬，即对于大量的信息却难以发现其中有用的知识。正是在这样的背景下数据挖掘领域近年来飞速发展。本文针对本次毕业设计做的对给定数据表进行面向属性的归纳的操作就是为了在数据库大量的数据（有冗余）中提取出一

54、定的规则，然后传递给用户，满足用户对数据隐含规则或是发展趋势预测的需求。主要完成的工作和收获：1. 为了完成算法实现不仅阅读了有关数据挖掘和面向属性的归纳方法的书籍还对程序设计和数据库相关的书本进行了有针对性的复习。熟悉了程序设计思想及数据库相关概念并了解了数据挖掘的一些基本概念和数据挖掘研究的大概内容及方向等；特别的对于面向属性归纳法部分，阅读了不少相关资料，较为系统地学习了整个算法，而且实现了基于树型领域知识的归纳算法。2. 在算法实现过程中，真切体会到数据挖掘的现实意义，对本科阶段的很多理论知识在实践应用上有了更为深刻的理解和认识，贯通了一些课堂没有消化完全的知识，提高了我实际动手能力。

55、3. 前文提到本次设计是基于Visual+6.0和SQLServer200。,因此对于C+编程语言和SQL也进一步熟悉，对于数据库的使用方法，特别是VC中关于数据库的使用方法，有深刻的体会。6.2工作展望本次设计虽然完成了AOI的基本算法，但对于本文所涉及的设计内容，还存在以下需要进一步研究的工作：面向属性归纳法在理论上同样可以适用于很多其它类型数据库，对于这种情况还需进一步验证。利用面向属性归纳法还可以提取更多的规则，如数据演化规律性、区别规则等，在本次设计中都没有体现。本次设计只对树型结构的领域知识进行处理。然而在现实情况中，更合理也更接近现实的应该是图型结构形式的领域知识，这就带来一系列

56、复杂的操作如背景知识如何输入、在计算机中如何存储、概化过程中如何对多个高层概念进行取舍而且不得不考虑兴趣度问题，这些对于实现更为复杂，更加实际的系统都是非常关键的问题，也有理由相信这才是AOI真正有价值的方面。控制概化过程的关键因素一一阈值的控制的取值上，在设计中只是作为已知条件使用，并没有从理论上论证对其合理性、有效性。而且整个程序的通用性是也存在欠缺,并没有使用其它的数据进行验证。在以后进一步的工作与学习中，对待程序设计过程中会更加全面的考虑各个方面的，希望能用自己的所学为IT的发展尽我绵薄的力量！谢辞主要参考文献1 H.J.Hamiltin,R.J.Hamilton,andN.Cercone.Attribute-orientedinduction