孟志剛,曲開社,康向平

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

孟志剛,曲開社,康向平

(山西大學(xué)計算機(jī)與信息技術(shù)學(xué)院,山西太原030006)

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

多值背景;屬性約簡;函數(shù)依賴

0 引言

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

形式概念分析(formal concept analysis)是德國學(xué)者Wille[1]提出的一種從形式背景(formal context)建立概念格來進(jìn)行數(shù)據(jù)分析和規(guī)則提取的強有力工具,已被廣泛地研究[2-8],并應(yīng)用到軟件工程[6]和信息獲取[4-8]等領(lǐng)域.

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

定義1[2]一個多值背景是一個四元組S=(G,M,W,J),其中G為對象集,M為屬性集,W為屬性值域,J?G×M×W為三元關(guān)系序偶,滿足當(dāng)(g,m,w)∈J且(g,m,v)∈J時有w=v成立.

定義2[2]一個形式背景K是一個三元組K=(G,M,I),其中G為所有對象的集合,M為所有屬性的集合,I?G×M為G和M中元素之間的關(guān)系序偶對集合.對于g∈G,m∈M,用gIm或(g,m)∈I表示“對象g具有屬性m”.

定義3[2]設(shè)K=(G,M,I)為一形式背景.對于集合A?G,記:

相應(yīng)地,對于集合B?M,記:B′={g∈G|(g,m)∈I,?m∈B}.

定義4[2]設(shè)K=(G,M,I)為一形式背景,A?G,B?M,稱C=(A,B)為K的一個概念,如果A′=B且B′=A.此時稱A為C的外延,B為C的內(nèi)涵.我們用B(K)記K的所有概念組成的集合.

引理1[2]設(shè)K=(G,M,I)為一形式背景,A,A1,A2?G為對象子集,B,B1,B2?M為屬性子集,下列結(jié)論成立:(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ū)分不同的對象.在實際應(yīng)用中,人們并不太關(guān)心多值背景中全部屬性而是對能夠區(qū)分對象貢獻(xiàn)大的屬性比較感興趣.因此我們從實用的角度出發(fā),給出了一種基于屬性重要性的屬性約簡方法.

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

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

λd反映了對象在屬性d下的發(fā)散程度,即λd越大,對象在屬性d下的取值與均值σd的偏離程度就越大,而論域G在屬性d下的取值差別就越大.另外,當(dāng)不同對象在屬性d下的取值差別越大,屬性d越能區(qū)分論域中的對象,這說明該屬性的重要性越大.因此λd可以代表屬性d在多值背景S中的重要性程度.

在下文中我們將依據(jù)λd對多值背景S=(G,M,W,J)中的屬性進(jìn)行約簡,去掉那些對論域分類貢獻(xiàn)小的屬性.在多值背景S=(G,M,W,J)中,設(shè)閾值0≤α≤1,約簡后的屬性集為:Mα=d∈M|λd≥α,其中,α可以根據(jù)經(jīng)驗設(shè)定.當(dāng)α=0時,約簡后的屬性集就退化到原屬性集,相當(dāng)于沒有對任何屬性約簡.當(dāng)α=1時,由于多值背景經(jīng)過量綱處理后的屬性值都不大于1,而根據(jù)定義5求得的λd都不大于1,所以約簡后的屬性集就變?yōu)榭?相當(dāng)于約簡了全部屬性.

3 應(yīng)用形式概念分析理論對多值背景中的函數(shù)依賴進(jìn)行提取

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

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

將其轉(zhuǎn)化為三元組KS=(～P2(G),M,IS),其中～P2(G)={{x,y}|x,y∈G,x≠y},稱KS為S生成的單值形式背景.

定義7[2]設(shè)S=(G,M,W,J)為一多值背景,B,C?M,任取x,y∈G,如果下式都成立,

則稱屬性集C函數(shù)依賴于屬性集B.

定義8 已知由多值背景S生成的單值形式背景KS=(～P2(G),M,IS)中,設(shè)B,C?M,若滿足:

則稱B屬性蘊含C,記作B→C.

定理1 已知多值背景S和它生成的單值形式背景KS=(～P2(G),M,IS),設(shè)B,C?M,則

證明:對于任意的B,C?M,設(shè)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函數(shù)依賴B.

同理,可以證明如果C函數(shù)依賴B則有B→C.證畢

顯然,由定理1可知,單值形式背景KS中的屬性蘊含就是多值背景S中的函數(shù)依賴.

引理2[2]已知形式背景K=(G,M,I),設(shè)A,B?M,則A→B成立,當(dāng)且僅當(dāng)B?A″.

應(yīng)用引理2的結(jié)論,我們可以得到單值形式背景KS=(～P2(G),M,IS)中的所有屬性蘊涵,進(jìn)而由定理1可知,我們得到了原多值背景S=(G,M,W,J)中的所有函數(shù)依賴.

4 多值背景約簡及其上的函數(shù)依賴提取算法

依據(jù)上面的討論,我們提出了多值背景約簡及其上的函數(shù)依賴提取算法,算法的具體過程如下所述.

1)消除量綱的影響

由于屬性下取值的度量單位不同,因此,各屬性下取值變化幅度就不同.我們將通過預(yù)處理消除量綱對屬性約簡的影響.具體做法:在多值背景S=(G,M,W,J)中,任取o∈G,d∈M,找出屬性d下對象取值的最大值max(Vd),用對象o在屬性d下的取值f(o,d)除以max(Vd)得到處理后的屬性值.通過該方法對多值背景中各屬性進(jìn)行處理.

2)進(jìn)行屬性約簡

設(shè)閾值0≤α≤1,進(jìn)而依據(jù)定義5中的λd對多值背景S=(G,M,W,J)中的屬性進(jìn)行約簡,即去掉那些對論域分類貢獻(xiàn)小的屬性.

3)對象集的處理

為了減少計算量,對多值背景中的對象集G進(jìn)行處理,使得處理后的多值背景S=(GR,M,W,J)只含有每個等價類中的一個元素,這里GR?G.

4)背景轉(zhuǎn)換

將多值背景轉(zhuǎn)化為單值背景.

5)函數(shù)依賴的提取

依據(jù)引理2,可以判斷任意屬性A,B?M之間是否具有屬性蘊含關(guān)系.這樣我們可以根據(jù)定理1逐個求出多值背景上的全部函數(shù)依賴.結(jié)束.

下面我們通過一個例子來說明算法的有效性.給出一個多值背景如表1.

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

首先依據(jù)算法第一步對多值背景進(jìn)行預(yù)處理,然后按照定義5中的公式分別計算得到各個屬性的均值和重要性程度如表2所示.

表2 進(jìn)行屬性約簡的一些重要實驗數(shù)據(jù)Table 2 Important experimental data to attributes reduction

依據(jù)算法進(jìn)行屬性約簡,其中α設(shè)定為0.003,根據(jù)表2中的屬性重要性程度顯然可以約去屬性d、f、g然后進(jìn)行對象約簡,求得對象的等價類劃分為G/R={1,2,{3,5},4},按照算法取G/R中每個等價類中的一個元素,得到處理后的對象集為GR={1,2,3,4}.約簡后的多值背景如表3所示.

表3 經(jīng)過約簡后的多值背景Table 3 Many-valued context after reduction

依據(jù)定義6,將表3所示的多值背景轉(zhuǎn)換為表4所示的單值形式背景.

表4 由表3所示的多值背景轉(zhuǎn)換后的單值形式背景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,ν)成立,對應(yīng)的(1,j,ν)=(4,j,ν)(3,j,ν)=(5,j,ν)也總成立,所以{a,c, h}→{j}也是原多值背景S的一條函數(shù)依賴.這說明我們在轉(zhuǎn)化后單值背景中得到的屬性蘊涵與原多值背景中的函數(shù)依賴是一致的.

5 結(jié)論

本文在多值背景中,提出了一種多值背景約簡及其上的函數(shù)依賴提取算法.并在實例中說明我們在轉(zhuǎn)化后單值背景中得到的屬性蘊涵與原多值背景中的函數(shù)依賴是一致的.這為在多值背景中提取函數(shù)依賴提供了一種較有效的方法.

[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è),李德玉.形式概念分析對粗糙集理論的表示及擴(kuò)展[J].軟件學(xué)報,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ī)則產(chǎn)生集挖掘算法[J].計算機(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偏序圖的構(gòu)建和基于GM偏序圖的規(guī)則提取[J].計算機(jī)工程與應(yīng)用,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

國家自然科學(xué)基金(70471003;60275019);山西省自然科學(xué)基金(2007011040)

孟志剛(1982-),男,山西朔州人,碩士研究生,主要研究領(lǐng)域為概念格、粗糙集.E-mail:mzg421@163.com