多值背景的属性约简及其上的函数依赖提取

孟志刚,曲开社,康向平

多值背景的属性约简及其上的函数依赖提取

孟志刚,曲开社,康向平

(山西大学计算机与信息技术学院,山西太原030006)

提出了一种多值背景的属性约简及其上的函数依赖提取算法.该算法分为两部分:(1)对属性进行约简,进而可以去掉一些不重要的属性;(2)将多值背景转换为单值背景,然后基于形式概念分析理论来获取原多值背景中的函数依赖.最后通过实例验证了该算法的有效性.

多值背景;属性约简;函数依赖

0 引言

函数依赖在知识发现领域是一个很重要的概念,它反映了现实世界数据中属性之间的关联性.利用函数依赖可以进行数据约简、查询优化、规则一致性的判定.现实中数据库里往往存在大量的冗余数据,因此在多值背景上获取函数依赖是一项非常有意义的工作.

形式概念分析(formal concept analysis)是德国学者Wille[1]提出的一种从形式背景(formal context)建立概念格来进行数据分析和规则提取的强有力工具,已被广泛地研究[2-8],并应用到软件工程[6]和信息获取[4-8]等领域.

1 形式概念分析理论中的基本概念

定义1[2]一个多值背景是一个四元组S=(G,M,W,J),其中G为对象集,M为属性集,W为属性值域,J⊆G×M×W为三元关系序偶,满足当(g,m,w)∈J且(g,m,v)∈J时有w=v成立.

定义2[2]一个形式背景K是一个三元组K=(G,M,I),其中G为所有对象的集合,M为所有属性的集合,I⊆G×M为G和M中元素之间的关系序偶对集合.对于g∈G,m∈M,用gIm或(g,m)∈I表示“对象g具有属性m”.

定义3[2]设K=(G,M,I)为一形式背景.对于集合A⊆G,记:

相应地,对于集合B⊆M,记:B′={g∈G|(g,m)∈I,∀m∈B}.

定义4[2]设K=(G,M,I)为一形式背景,A⊆G,B⊆M,称C=(A,B)为K的一个概念,如果A′=B且B′=A.此时称A为C的外延,B为C的内涵.我们用B(K)记K的所有概念组成的集合.

引理1[2]设K=(G,M,I)为一形式背景,A,A1,A2⊆G为对象子集,B,B1,B2⊆M为属性子集,下列结论成立:(1)A1⊆A2⇒A′2⊆A′1;(2)B1⊆B2⇒B′2⊆B′1;(3)A⊆A″;B⊆B″;(4)A′=A‴;B′=B‴.

2 多值背景的属性约简

多值背景中属性主要是表征对象特征的,用以区分不同的对象.在实际应用中,人们并不太关心多值背景中全部属性而是对能够区分对象贡献大的属性比较感兴趣.因此我们从实用的角度出发,给出了一种基于属性重要性的属性约简方法.

定义5 在多值背景S=(G,M,W,J)中,设∀o∈G,∀d∈M,称

为属性d的重要性程度,其中f(o,d)为对象o在属性d下的值,且G≠Ø,M≠Ø.

λd反映了对象在属性d下的发散程度,即λd越大,对象在属性d下的取值与均值σd的偏离程度就越大,而论域G在属性d下的取值差别就越大.另外,当不同对象在属性d下的取值差别越大,属性d越能区分论域中的对象,这说明该属性的重要性越大.因此λd可以代表属性d在多值背景S中的重要性程度.

在下文中我们将依据λd对多值背景S=(G,M,W,J)中的属性进行约简,去掉那些对论域分类贡献小的属性.在多值背景S=(G,M,W,J)中,设阈值0≤α≤1,约简后的属性集为:Mα=d∈M|λd≥α,其中,α可以根据经验设定.当α=0时,约简后的属性集就退化到原属性集,相当于没有对任何属性约简.当α=1时,由于多值背景经过量纲处理后的属性值都不大于1,而根据定义5求得的λd都不大于1,所以约简后的属性集就变为空,相当于约简了全部属性.

3 应用形式概念分析理论对多值背景中的函数依赖进行提取

由于形式概念分析理论通常用来处理单值形式背景,为了更好地应用该理论,我们将多值背景S=(G, M,W,J)转化成单值形式背景KS,下面我们给出KS的形式化定义.

定义6 设S=(G,M,W,J)为一个多值背景,a∈M,x,y∈G,通过下面的规则:

将其转化为三元组KS=(～P2(G),M,IS),其中～P2(G)={{x,y}|x,y∈G,x≠y},称KS为S生成的单值形式背景.

定义7[2]设S=(G,M,W,J)为一多值背景,B,C⊆M,任取x,y∈G,如果下式都成立,

则称属性集C函数依赖于属性集B.

定义8 已知由多值背景S生成的单值形式背景KS=(～P2(G),M,IS)中,设B,C⊆M,若满足:

则称B属性蕴含C,记作B→C.

定理1 已知多值背景S和它生成的单值形式背景KS=(～P2(G),M,IS),设B,C⊆M,则

证明:对于任意的B,C⊆M,设B→C,由定义8,有∀{x,y}∈～P2(G),∀m∈B,({x,y},m)∈IS⇒∀n∈C,({x,y},n)∈IS,由定义6,显然有∀{x,y}∈～P2(G),(∀m∈B (x,m,v)=(y,m,v))⇒(∀n∈C (x,n, v)=(y,n,v)).因此,由定义7可知C函数依赖B.

同理,可以证明如果C函数依赖B则有B→C.证毕

显然,由定理1可知,单值形式背景KS中的属性蕴含就是多值背景S中的函数依赖.

引理2[2]已知形式背景K=(G,M,I),设A,B⊆M,则A→B成立,当且仅当B⊆A″.

应用引理2的结论,我们可以得到单值形式背景KS=(～P2(G),M,IS)中的所有属性蕴涵,进而由定理1可知,我们得到了原多值背景S=(G,M,W,J)中的所有函数依赖.

4 多值背景约简及其上的函数依赖提取算法

依据上面的讨论,我们提出了多值背景约简及其上的函数依赖提取算法,算法的具体过程如下所述.

1)消除量纲的影响

由于属性下取值的度量单位不同,因此,各属性下取值变化幅度就不同.我们将通过预处理消除量纲对属性约简的影响.具体做法:在多值背景S=(G,M,W,J)中,任取o∈G,d∈M,找出属性d下对象取值的最大值max(Vd),用对象o在属性d下的取值f(o,d)除以max(Vd)得到处理后的属性值.通过该方法对多值背景中各属性进行处理.

2)进行属性约简

设阈值0≤α≤1,进而依据定义5中的λd对多值背景S=(G,M,W,J)中的属性进行约简,即去掉那些对论域分类贡献小的属性.

3)对象集的处理

为了减少计算量,对多值背景中的对象集G进行处理,使得处理后的多值背景S=(GR,M,W,J)只含有每个等价类中的一个元素,这里GR⊆G.

4)背景转换

将多值背景转化为单值背景.

5)函数依赖的提取

依据引理2,可以判断任意属性A,B⊆M之间是否具有属性蕴含关系.这样我们可以根据定理1逐个求出多值背景上的全部函数依赖.结束.

下面我们通过一个例子来说明算法的有效性.给出一个多值背景如表1.

表1 多值背景S=(G,M,W,J)Table 1 Many-valued contextS=(G,M,W,J)

首先依据算法第一步对多值背景进行预处理,然后按照定义5中的公式分别计算得到各个属性的均值和重要性程度如表2所示.

表2 进行属性约简的一些重要实验数据Table 2 Important experimental data to attributes reduction

依据算法进行属性约简,其中α设定为0.003,根据表2中的属性重要性程度显然可以约去属性d、f、g然后进行对象约简,求得对象的等价类划分为G/R={1,2,{3,5},4},按照算法取G/R中每个等价类中的一个元素,得到处理后的对象集为GR={1,2,3,4}.约简后的多值背景如表3所示.

表3 经过约简后的多值背景Table 3 Many-valued context after reduction

依据定义6,将表3所示的多值背景转换为表4所示的单值形式背景.

表4 由表3所示的多值背景转换后的单值形式背景Table 4 Binary formal context after transforming many-valued context in table 3

利用引理2,在表4中由{a,c,h}″={a,c,h,j}可以得到形式背景KS的一条属性蕴含{a,c,h}→{j}.又由定义7,在表1中属性a,c,h下(1,a,ν)=(4,a,ν)(3,a,ν)=(5,a,ν),(1,c,ν)=(4,c,ν)(3,c,ν)=(5,c,ν), (1,h,ν)=(4,h,ν)(3,h,ν)=(5,h,ν)成立,对应的(1,j,ν)=(4,j,ν)(3,j,ν)=(5,j,ν)也总成立,所以{a,c, h}→{j}也是原多值背景S的一条函数依赖.这说明我们在转化后单值背景中得到的属性蕴涵与原多值背景中的函数依赖是一致的.

5 结论

本文在多值背景中,提出了一种多值背景约简及其上的函数依赖提取算法.并在实例中说明我们在转化后单值背景中得到的属性蕴涵与原多值背景中的函数依赖是一致的.这为在多值背景中提取函数依赖提供了一种较有效的方法.

[1] WILL E R.Restructuring Lattice Theory:an Approach Based on Hierarchies of Concepts[C]//Rival I Ordered Sets.Dordrecht:Reidel,1982:445-470.

[2] GANTER B,WILL E R.Formal concept analysis:mathematical foundations[M].Berlin:Springer-Verlag,1999.

[3] 曲开社,翟岩慧,梁吉业,李德玉.形式概念分析对粗糙集理论的表示及扩展[J].软件学报,2007,18(9):214-218.

[4] QU K S,ZHAI Y H.Generating Complete of Implications for Formal Contexts[J].Knowledge-based S ystems,2008(21): 429-433.

[5] 梁吉业,王俊红.基于概念格的规则产生集挖掘算法[J].计算机研究与发展,2004,41(8):1339-1344.

[6] DEKEL U.Revealing Java Class Structure with Concept Lattices[D].Technion-Israel Institute ofTechnology,2003.

[7] 曲开社,阎俊霞,翟岩慧.GM偏序图的构建和基于GM偏序图的规则提取[J].计算机工程与应用,2007,43(36):51-54.

[8] QU K S,ZHAI Y H,LIANGJ Y,CHEN M.Study of Decision Implications Based on Formal Concept Analysis[J].International J ournal of General S ystems,2007,36(2):147-156.

Attributes Reduction and Function Dependencies Acquisition in Many-Valued Context

MENG Zhi-gang,QU Kai-she,KAN G Xiang-ping
(School of Computer and Inf ormation Technology,Shanxi University,Taiyuan030006,China)

A kind of algorithm to attributes reduction and function dependencies acquisition is introduced in many-valued context.This algorithm was divided into two parts.First,the attributes were reduced to remove some unimportant ones.Second,the many-valued context was transformed into a binary formal context,and then the function dependencies in many-valued context were got based on the theory of formal concept analysis.The examples are provided to illustrate the validity of the algorithm.

many-valued context;attributes reduction;function dependencies

TP181

A

0253-2395(2010)02-0190-04

2009-09-21;

2009-10-30

国家自然科学基金(70471003;60275019);山西省自然科学基金(2007011040)

孟志刚(1982-),男,山西朔州人,硕士研究生,主要研究领域为概念格、粗糙集.E-mail:mzg421@163.com