多值背景的屬性約簡及其上的函數依賴提取

孟志剛,曲開社,康向平

多值背景的屬性約簡及其上的函數依賴提取

孟志剛,曲開社,康向平

(山西大學計算機與信息技術學院,山西太原030006)

提出了一種多值背景的屬性約簡及其上的函數依賴提取算法.該算法分為兩部分:(1)對屬性進行約簡,進而可以去掉一些不重要的屬性;(2)將多值背景轉換為單值背景,然后基于形式概念分析理論來獲取原多值背景中的函數依賴.最后通過實例驗證了該算法的有效性.

多值背景;屬性約簡;函數依賴

0 引言

函數依賴在知識發(fā)現(xiàn)領域是一個很重要的概念,它反映了現(xiàn)實世界數據中屬性之間的關聯(lián)性.利用函數依賴可以進行數據約簡、查詢優(yōu)化、規(guī)則一致性的判定.現(xiàn)實中數據庫里往往存在大量的冗余數據,因此在多值背景上獲取函數依賴是一項非常有意義的工作.

形式概念分析(formal concept analysis)是德國學者Wille[1]提出的一種從形式背景(formal context)建立概念格來進行數據分析和規(guī)則提取的強有力工具,已被廣泛地研究[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 多值背景的屬性約簡

多值背景中屬性主要是表征對象特征的,用以區(qū)分不同的對象.在實際應用中,人們并不太關心多值背景中全部屬性而是對能夠區(qū)分對象貢獻大的屬性比較感興趣.因此我們從實用的角度出發(fā),給出了一種基于屬性重要性的屬性約簡方法.

定義5 在多值背景S=(G,M,W,J)中,設?o∈G,?d∈M,稱

為屬性d的重要性程度,其中f(o,d)為對象o在屬性d下的值,且G≠?,M≠?.

λd反映了對象在屬性d下的發(fā)散程度,即λd越大,對象在屬性d下的取值與均值σd的偏離程度就越大,而論域G在屬性d下的取值差別就越大.另外,當不同對象在屬性d下的取值差別越大,屬性d越能區(qū)分論域中的對象,這說明該屬性的重要性越大.因此λ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,所以約簡后的屬性集就變?yōu)榭?相當于約簡了全部屬性.

3 應用形式概念分析理論對多值背景中的函數依賴進行提取

由于形式概念分析理論通常用來處理單值形式背景,為了更好地應用該理論,我們將多值背景S=(G, M,W,J)轉化成單值形式背景KS,下面我們給出KS的形式化定義.

定義6 設S=(G,M,W,J)為一個多值背景,a∈M,x,y∈G,通過下面的規(guī)則:

將其轉化為三元組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] 曲開社,翟巖慧,梁吉業(yè),李德玉.形式概念分析對粗糙集理論的表示及擴展[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] 梁吉業(yè),王俊紅.基于概念格的規(guī)則產生集挖掘算法[J].計算機研究與發(fā)展,2004,41(8):1339-1344.

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

[7] 曲開社,閻俊霞,翟巖慧.GM偏序圖的構建和基于GM偏序圖的規(guī)則提取[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