基于对象立方体结构的高层关联规则挖掘方法研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于对象立方体结构的高层关联规则挖掘方法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:在属性的高层概念上发现的关联规则为高层关联规则,对基于对象立方体结构的高层关联规则挖掘方法进行了研究.提出了一种挖掘高层关联规则的算法，并用算法进行了实验，得到的关联规则可以为用户提供一些常识性的知识，对高层决策有较大的帮助.

关键词:对象立方体；高层关联规则；Apriori算法

中图分类号:TP301

文献标识码:A文章编号:1672-8513(2010)01-0056-04

The Mining Method for the High-Level Association

Rule Based on the Object Cube

ZHAO Qinyi

(School of Mathematics and Computer Science, Dali University, Dali 671000, China)

Abstract:

The association rule which is found in the high-level conception of attributes is called high-level association rule. The mining method for the high-level association rule based on the object tube is studied and an algorithm is given. The experiment has proved that the association rule can provide the users some general knowledge which is helpful for the high-level policy-making.

Key words:

object cube; high-level association rule; Apriori algorithm

近年来,随着面向对象技术及面向对象数据库应用的日渐广泛,基于面向对象数据库的知识发现成为数据挖掘领域新的研究方向［1］.将对象和类进行泛化进而构造对象立方体,可以从中发现类描述规则、分类规则、高层关联规则、例外规则、聚类规则等.关联规则可以用于许多决策过程,如产品分布、分类设计和交叉销售,其中高层关联规则可以为用户提供一些常识性的知识,是面向对象数据库中用户较感兴趣的知识之一.

1 高层关联规则

关联规则挖掘是数据挖掘的典型方法,可以用来发现大量数据中数据项集之间有价值的关联或相关联系.关联规则是形如XY（s%,c%）的蕴含式,其中s%为规则的支持度,c%为规则的置信度,同时满足最小可信度阈值和最小支持度阈值的关联规则称为强关联规则.关联规则的挖掘是指在事务数据库T中找出满足用户给定的最小支持度和最小可信度阈值的关联规则,可以分解为2个子问题：(1)找出事务数据库T中所有大于等于用户指定最小支持度的项目集,即频繁项目集；(2)利用频繁项目集生成所需要的关联规则.

对于许多应用,由于数据的稀疏性,在底层或原始抽象层的数据项之间很难发现强关联规则.在较高的抽象层发现的强关联规则往往可以提供一些常识性的知识且易于获得［2］.在商品的高层概念上发现的关联规则称为高层关联规则.规则buys(X,“laptop computer”) buys(X,“HP printer”)［support=8%,confidence=70%］中的“loptop computer”及“HP printer”是用底层概念表示的商品,这样的规则被称之为底层关联规则.若将商品属性泛化到一定的高层概念,由此而发现的规则为用高层概念表示的规则,即高层关联规则.如规则buys(X,“computer”) buys(X,“printer”)［support=10%,confidence=80%］是一个高层关联规则,其中的“compuer”、“printer”均为高层概念.

面向对象数据库中的对象含有复杂的类/子类层次结构及属性和方法,在原始数据集上很难发现强关联规则,且发现的规则可能会过度适应,对高层决策帮助较小.若将对象泛化到较高的概念层次,则比较容易发现强关联规则,本文对基于对象立方体结构的高层关联规则挖掘方法进行了研究.

2 对象立方体

对象立方体是类似于数据立方体的n维数据模型,是一个建立在泛化类上的多维数据库,以泛化类的一组已泛化属性作为对象立方体的维,而立方体的度量(各维空间)则由1个或1组属性、聚集值或其它外延组成［3］.其它外延可能是一个对象标识符的汇集或泛化对象其它特征的汇集.使用对象泛化技术,可以把复杂对象的各种特征泛化成多个共享特征,构成多维数据库的共享维.面向对象数据库虽然含有大量具有复杂结构的对象、空间和多媒体数据以及类/子类层次结构和方法,但这些复杂结构可以泛化为简单和单一结构的数据,泛化后的结构和关系数据库结构非常相似.一个多维数据模型可以在泛化后的目标对象集上构造,故对象立方体可以通过基于维的对象类泛化方法构造得到.

例1：有图1所示类层次结构的object面向对象数据库,图2为其address属性的概念层次树.

赵秦怡：基于对象立方体结构的高层关联规则挖掘方法研究

有泛化任务集：40岁以上,有博士学位，在云南工作，开日产车；泛化任务：对该任务集中对象的姓名、住房面积、薪水、家庭地址进行泛化.对该任务用文献［3］中基于维的泛化算法进行处理,得到图3所示的对象立方体.

3 基于对象立方体结构的高层关联规则挖掘方法

3.1 算法思想

面向对象数据库含有丰富的类/子类层次结构,存储了大量属于不同类的对象［4］,在具有复杂的类所属关系的对象集上发现关联规则意义不大.面向对象数据库中的关联规则挖掘是指在任务相关的对象集中发现关联规则,依据挖掘任务在面向对象数据库中搜索任务相关对象集是算法的首要步骤.

例2:在上述例1中的object数据库中对象集（40岁以上,开日产车,有博士学位,在云南工作）中挖掘属性间在概念层上的高层关联规则,该任务可以表示为：

Mine association rules

From Person P

Where P.Age>=40 and P.Car.Maker=’Japan’

And ‘Ph.D’ in P.Education and P.Workplace.Name=’City’

With respect to P.Name, P.Home.House_Size, P.Salary, P.Home.Address

对任务相关对象集进行属性相关分析,可以去除与挖掘任务不相关或相关不大的属性,如职工号、姓名等.高层关联规则中的概念均为高层概念,故需对任务相关对象集中对象的属性进行泛化,属性泛化操作可将属性值由较低的概念层提升为较高的概念层［2］. HAN Jia-wei等人提出了一个在面向对象数据库中基于维的属性泛化算法［3］,该算法在泛化时最多2次扫描有关对象,第1次扫描汇集属性值的统计分布信息,并确定某个属性应当泛化到的值集,如果数据集很大,就进行采样(其开销小于全扫描).在确定了主类的概念层次后,第2次扫描将把初始工作类中对象的全部性质泛化到主类的概念层,合并相同维的值,从而高效率地导出主类,构造相应的对象立方体.为了避免过度泛化,该算法用属性阈值控制泛化过程.

关联规则挖掘的关键问题是求得频繁项集.在搜索频繁项集之前构造任务相关对象集的事务数据库,其中,每一个对象的属性取值序列构成一个事务,事务中的每一项对应了对象的某一属性取值,所有对象的事务集合构成事务数据库.本方法在搜索频繁项集时采用Apriori算法来实现,Apriori算法使用一种称作逐层搜索的迭代方法［5］,k项集用于搜索(k+1)项集.首先,通过扫描数据库,累计每个项的计数,并收集满足最小支持度的项,找出频繁1项集的集合,该集合记作L1.然后,L1用于找频繁2项集的集合L2,L2用于找L3,如此下去,直到不能再找到频繁k项集.找每个Lk需要一次数据库全扫描.为提高频繁项集逐层产生的效率,用Apriori性质压缩搜索空间［6］,即频繁项集的所有非空子集也必须是频繁的.求得频繁项集之后,计算可由频繁项集获得的关联规则的信任度,找出满足最小信任度阈值的强关联规则作为输出［7］.

3.2 算法描述

输入：挖掘任务、面向对象数据库、概念层次树、属性泛化阈值、最小支持度阈值、最小置信度阈值.

输出：频繁项集、强关联规则.

Step1：查询面向对象数据库,获得任务相关对象集;

Step2：对任务相关对象集中对象属性进行相关分析,去除与挖掘任务无关的属性;

Step3：对任务相关对象集用文献［3］中基于维的属性泛化方法进行泛化,构造相应的对象立方体;

Step4：查询对象立方体,构造任务相关对象集事务数据库;

Step5：用Apriori算法寻找满足最小支持度阈值的频繁项集;

Step6：计算关联规则的置信度,获得满足最小置信度阈值的强关联规则.

4 算法分析

用本方法实现例2中的关联规则挖掘任务,设定最小支持度阈值为0.15,最小信任度阈值为0.7.在图3所示的对象立方体中导出任务相关对象集的主类关系,构造相应的事务数据库.扫描事务数据库,生成满足最小支持度阈值的频繁1项集,如表1所示.对频繁1项集进行连接及剪枝后,得到满足最小支持度阈值的频繁2项集,由表2所示.在频繁2项集基础上获得频繁3项集,由表3所示.对频繁3项集进行连接,所得的4项集中没有满足最小支持度阈值0.15的项,频繁4项集为空,频繁项集的生成过程结束.

在上述步骤所得的频繁项集上根据关联规则的生成方法获得满足最小信任度阈值的强关联规则,如表4.

5 结语

基于面向对象数据库的数据挖掘是近年来新起的研究方向,由于面向对象数据库含有复杂的类/子类层次结构,存储了大量属于不同类的对象,故面向对象数据库中的数据挖掘一般针对任务相关对象集来实现.将任务相关对象集进行泛化生成对象立方体,可以在之上发现用户感兴趣的知识.关联规则挖掘可以发现大量数据中数据项集之间有价值的关联或相关联系,其中的高层关联规则可以为用户提供一些常识性的知识且易于发现,高层关联规则对高层决策帮助较大.基于对象立方体结构发现的规则为高层关联规则,本文对基于对象立方体结构的高层关联规则的挖掘方法及运用进行了研究.

参考文献:

［1］HAN J, SHIO S, KAWANO H. Knowledge discovery in object-oriented and active databases［C］//Knowledge Building and Knowledge Sharing. Tokyo:Ohmsha Ltd, IOS Press,1994.

［2］范明, 孟小峰.数据挖掘概念与技术［M］. 北京:机械工业出版社,2004.

［3］HAN Jiawei, NISHIO S, KAWANO H, et al. Generalization-based data mining in object-oriented databases using an object-cube model［J］. Data and Knowledge Engineering. 1998,25(1-2):55-97.

［4］王丽珍,周丽华,肖清. 基于数据仓库的动态异常点检测研究［C］// 第二十五届中国数据库学术会议.计算机研究与发展, 2008(10A):161-168.

［5］郭健美.基于Apriori算法的改进算法［J］.计算机工程与设计,2008(11)：2814-2816.

［6］钱雪忠,孔芳.关联规则挖掘中对Apriori算法的研究［J］.计算机工程与应用,2008,44（17）：138-141.

［7］张寒云,段鹏,丁钦华. 基于关联规则的课程拓扑排序研究［J］.云南民族大学学报：自然科学版,2009,18(2):177-179.