基于一一映射的概念格屬性約簡(jiǎn)算法
2009-01-01 00:00:00呂躍進(jìn)李金海
計(jì)算機(jī)應(yīng)用研究 2009年3期
(廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院， 南寧 530004)
摘 要：首先給出了基于一一映射的概念格不同類(lèi)型屬性的等價(jià)刻畫(huà)定理，在此基礎(chǔ)上得到了一種新穎的概念格屬性約簡(jiǎn)算法；最后通過(guò)實(shí)例表明了該約簡(jiǎn)算法的可行性與有效性。
關(guān)鍵詞：形式背景； 概念格； 屬性約簡(jiǎn)
中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：10013695(2009)03084903
Oneone mappingbased algorithm for attribute reduction of concept lattice
LV Yuejin， LI Jinhai
(School of Mathematics Information Science， Guangxi University， Nanning 530004， China)
Abstract:First， from the viewpoint of oneone mapping， this paper gave the theory of measuring the characteristic of diffenent attributes equivalently， and then proposed a novel algorithm to find attribute reduction of concept lattices.At last，it used a real example to demonstrate both its feasibility and effectiveness， respectively.
Key words：formal context; concept lattice; attribute reduction
概念格，又稱(chēng)為Galois格，是德國(guó)數(shù)學(xué)家R.Wille[1]于1982年首次提出的。概念格是根據(jù)數(shù)據(jù)集中對(duì)象與屬性之間的二元關(guān)系建立的一種概念層次結(jié)構(gòu)，生動(dòng)簡(jiǎn)潔地體現(xiàn)了概念之間的泛化和特化關(guān)系。作為數(shù)據(jù)分析和知識(shí)處理的有力工具，概念格理論已被廣泛應(yīng)用于知識(shí)工程、數(shù)據(jù)挖掘、信息檢索、軟件工程等領(lǐng)域[2~5]。
概念格約簡(jiǎn)就是在保持對(duì)象集不變的前提下，尋找最小的屬性集，它能夠完全確定形式背景上的概念及其層次結(jié)構(gòu)，也就是說(shuō)這個(gè)最小屬性集確定的概念格與全體屬性集確定的概念格同構(gòu)。概念格屬性約簡(jiǎn)使得形式背景中隱含知識(shí)的發(fā)現(xiàn)變得更容易，也使得這些知識(shí)的表示變得更簡(jiǎn)單，這對(duì)概念格理論的研究和應(yīng)用都有重要意義。
目前文獻(xiàn)[6]提出了概念格的屬性約簡(jiǎn)理論，并從可辨識(shí)屬性矩陣的角度給出了約簡(jiǎn)方法，但該約簡(jiǎn)方法依賴于對(duì)象與屬性集之間的“*”運(yùn)算，求約簡(jiǎn)時(shí)所需要的計(jì)算量大。文獻(xiàn)[7，8]在文獻(xiàn)[6]的基礎(chǔ)上從粗糙集的角度尋找不同類(lèi)型屬性的刻畫(huà)，給出的約簡(jiǎn)方法不依賴于對(duì)象與屬性集之間的“*”運(yùn)算，但其付出的代價(jià)是計(jì)算約簡(jiǎn)時(shí)所需要的計(jì)算量比文獻(xiàn)[6]中的方法更大。所以當(dāng)數(shù)據(jù)集較大時(shí)，以上方法都面臨著巨大的挑戰(zhàn)。
為了減少求概念格屬性約簡(jiǎn)的計(jì)算量，使得基于概念格的數(shù)據(jù)挖掘更具有可操作性，本文通過(guò)對(duì)對(duì)象與屬性集之間的“*”運(yùn)算進(jìn)行深入研究后，給出了一種基于一一映射的概念格屬性約簡(jiǎn)算法。
1 預(yù)備知識(shí)
為了后面敘述方便，本章介紹一些概念格屬性約簡(jiǎn)的基本概念與性質(zhì)，詳細(xì)的描述見(jiàn)文獻(xiàn)[1，6]。
定義1 稱(chēng)(U，A，I)為一個(gè)形式背景。其中U={x1，x2，…，xn}為對(duì)象集，每個(gè)xi(i≤n)稱(chēng)為一個(gè)對(duì)象；A={a1，a2，…，am}為屬性集，每個(gè)ai(i≤m)稱(chēng)為一個(gè)屬性；I為U與A之間的二元關(guān)系，IU×A。若(x，a)∈I，則說(shuō)x具有屬性a，記為xIa。
若用1表示(x，a)∈I，用0表示(x，a)I，這樣形式背景就可以表示為只有0和1的表格。
對(duì)于形式背景(U，A，I)，在對(duì)象集XU和屬性集BA上分別定義運(yùn)算：
X*={a｜a∈A，x∈X，xIa}(1)
B*={x｜x∈U，a∈B，xIa}(2)
x∈U，記{x}*為x*；a∈A，記{a}*為a*。若x∈U，x*≠，x*≠A，且a∈A，a*≠，a*≠U則稱(chēng)形式背景(U，A，I)是正則的。
定義2 設(shè)(U，A，I)為形式背景。如果一個(gè)二元組(X，B)滿足X*=B，且B*=X，則稱(chēng)(X，B)是一個(gè)形式概念，簡(jiǎn)稱(chēng)概念。其中X稱(chēng)為概念的外延，B稱(chēng)為概念的內(nèi)涵。
形式背景(U，A，I)的概念可以用超概念與亞概念的關(guān)系來(lái)定義它們之間的序關(guān)系：
(X1，B1)≤(X2，B2)X1X2(B2B1)(3)
則“≤”是一個(gè)偏序關(guān)系。(U，A，I)的所有概念的偏序集記為L(zhǎng)(U，A，I)，稱(chēng)為概念格。其中：(X1，B1)叫做(X2，B2)的亞概念；(X2，B2)叫做(X1，B1)的超概念。
若(X1，B1)和(X2，B2)是概念，則
(X1，B1)∧(X2，B2)=(X1∩X2，(B1∪B2)**)(4)
(X1，B1)∨(X2，B2)=((X1∪X2)**，B1∩B2)(5)
也是概念，從而L(U，A，I)是格，并且是完備格。
性質(zhì) 1 設(shè)(U，A，I)是形式背景，X1，X2，XU，且B1，B2，BA，有
1)X1X2X*2X*1，B1B2B*2B*1；
2)XX**，BB**；
3)X*=X***，B*=B***，XB*BX*；
4)(X1∪X2)*=X*1∩X*2，(B1∪B2)*=B*1∩B*2；
5)(X1∩X2)*X*1∪X*2，(B1∩B2)*B*1∪B*2；
6)(X**，X*)和(B*，B**)都是概念。
定義 3 設(shè)L(U，A1，I1)和L(U，A2，I2)是兩個(gè)概念格。如果對(duì)于任意(X，B)∈L(U，A2，I2)，總存在(X′，B′)∈L(U，A1，I1)，使得X′=X，則稱(chēng)L(U，A1，I1)細(xì)于L(U，A2，I2)，記做
L(U，A1，I1)≤L(U，A2，I2)(6)
如果L(U，A1，I1)≤L(U，A2，I2)且L(U，A2，I2)≤L(U，A1，I1)，那么稱(chēng)兩個(gè)概念格同構(gòu)，記做
L(U，A1，I1)L(U，A2，I2)(7)
在形式背景(U，A，I)下，對(duì)于任意DA，記ID=I∩(U×D)，那么(U，D，ID)也是一個(gè)形式背景。對(duì)于運(yùn)算X*(XU)，在(U，A，I)下還用X*表示，在(U，D，ID)用X*D表示，顯然IA=I，X*A=X*，X*D=X*∩D。
性質(zhì)2 設(shè)(U，A，I)為形式背景，DA，D≠，總有L(U，A，I)≤L(U，D，ID)。
定義4 設(shè)(U，A，I)為形式背景。如果存在屬性集DA，使得L(U，D，ID)L(U，A，I)，則稱(chēng)D是形式背景(U，A，I)的協(xié)調(diào)集。若進(jìn)一步的有d∈D，L(U，D-g0gggggg，ID-g0gggggg)L(U，A，I)均不成立，則稱(chēng)D是(U，A，I)的約簡(jiǎn)。所有(U，A，I)約簡(jiǎn)的交集稱(chēng)為(U，A，I)的核心。
定義5 設(shè)形式背景(U，A，I)的所有約簡(jiǎn)為{Di｜Di是約簡(jiǎn)，i∈τ}(τ為一指標(biāo)集)。可將屬性集A分為三部分：a)核心屬性b∶b∈∩Di；b)相對(duì)必要屬性c∶c∈∪Di-∩Di；c)絕對(duì)不必要屬性d∶d∈A-∪Di。
性質(zhì)3 a∈A是非核心屬性A-{a}是協(xié)調(diào)集。
性質(zhì)4 a∈A是核心屬性A-{a}不是協(xié)調(diào)集。
2 概念格屬性特征的等價(jià)刻畫(huà)定理
為了敘述方便，記形式背景(U，A，I)所有概念組成的集合為AL={(X，B)｜(X，B)∈L(U，A，I)}，所有概念的內(nèi)涵組成的集合為AI={B｜(X，B)∈AL}；對(duì)于任意屬性集DA，記集合AID={B∩D｜B∈AI}，集合DAI={(B∩D)*｜B∈AI}，另外記集合DL={((B∩D)*，B∩D)｜B∈AI}。由于對(duì)象集U和屬性集A均為有限集，集合AL、AI、DAI、AID、DL也均為有限集。
設(shè)L(U，A，I)為概念格，屬性集DA，那么集合AI到集合DAI的映射f:B→(B∩D)*為滿射。
在給出概念格不同類(lèi)型屬性的等價(jià)刻畫(huà)定理之前，先給出一個(gè)引理。
引理 設(shè)L(U，A，I)為概念格，DA。(X，B)∈L(U，D，ID)當(dāng)且僅當(dāng)(X，B)∈DL。
證明 a)充分性。因?yàn)?X，B)∈DL，存在B′∈AI，使得X=(B′∩D)*，且B=B′∩D。根據(jù)B′∈AI可得(B′*，B′)∈L(U，D，I)，再結(jié)合定義2有
B′**=B′(8)
式(2)可知以下等式成立：
B*D=(B′∩D)*D=(B′∩D)*=X(9)
由式(8)與性質(zhì)1中的1)和2)有
X*D=(B′∩D)** ∩DB′**∩D=B′∩D=B(10)
根據(jù)性質(zhì)1中的2)有
B=B′∩D(B′∩D)**(11)
B=B′∩DD(12)
根據(jù)式(11)(12)有
B=B′∩D(B′∩D)**∩D=(B′∩D)**D=X*D(13)
根據(jù)式(10)(13)有
X*D=B(14)
由式(9)和(14)即可證得(X，B)∈L(U，D，ID)。
b)必要性。已知屬性集DA，根據(jù)性質(zhì)2可得L(U，A，I)≤L(U，D，ID)；又(X，B)∈L(U，D，ID)，由定義3，存在(X′，B′)∈L(U，A，I)，使得X′=X，因此有(X，X*)∈L(U，A，I)，且X*∈AI。因?yàn)?X，B)∈L(U，D，ID)，B=X*D=X* ∩D，且X=B*D=(X* ∩D)*D=(X*∩D)*。
所以(X，B)=((X*∩D)*，X*∩D)∈DL。
引理1說(shuō)明形式背景(U，D，ID)的所有概念的外延組成的集合恰好為DAI。
下面給出基于一一映射的概念格不同類(lèi)型屬性的等價(jià)刻畫(huà)定理。
定理 屬性特征的等價(jià)刻畫(huà)定理。設(shè)L(U，A，I)為概念格，b∈A，令D=A-{b}，下列命題成立：
a)b為非核心屬性集合AI到集合DAI的映射f:B→(B∩D)*為一一映射；
b)b為核心屬性集合AI到集合DAI的映射f:B→(B∩D)*不是一一映射。
證明 a)充分性。因?yàn)榧螦I到集合DAI的映射f:B→(B∩D)*為一一映射，那么｜AI｜=｜DAI｜(兩集合的元素個(gè)數(shù)相同)，根據(jù)引理1有，形式背景(U，D，ID)的所有概念的外延組成的集合恰好為DAI，故｜AI｜=｜DL｜，由此可以推出
｜AL｜=｜DL｜(15)
又因?yàn)閷傩约疍A，根據(jù)性質(zhì)2有，L(U，A，I)≤L(U，D，ID)，由定義3有，任意(X，B)∈L(U，D，ID)，存在(X′，B′)∈L(U，A，I)，使得X′=X。那么任意((B∩D)*，B∩D)∈DL，存在(X′，B′)∈AL，使得X′=(B∩D)*，由式(15)有，任意(X′，B′)∈AL，存在((B∩D)*，B∩D)∈DL，使得(B∩D)*=X′，即任意(X′，B′)∈(U，A，I)，存在(X，B)∈L(U，D，ID)，使得X=X′，所以L(U，D，ID)≤L(U，A，I)，概念格L(U，A，I)與L(U，D，ID)同構(gòu)，即D是協(xié)調(diào)集，由性質(zhì)3即可證得b為非核心屬性。
b)必要性。由于b為非核心屬性，根據(jù)性質(zhì)3可知，屬性集D為協(xié)調(diào)集，依據(jù)協(xié)調(diào)集的定義可以得出L(U，D，ID)L(U，A，I)。因此：
(a)對(duì)于任意概念((B∩D)*，B∩D)∈DL，存在(X′，B′)∈AL，使得X′=(B∩D)*;
(b)對(duì)于任意概念(X′，B′)∈AL，存在((B∩D)*，B∩D)∈DL，使得(B∩D)*=X′。
由(a)和(b)可得集合DAI中的元素兩兩不相同；否則由(a)和(b)可以推出，形式背景(U，A，I)存在兩概念的內(nèi)涵不相同，但外延卻相同，這與兩概念的外延相同必有相同的內(nèi)涵相矛盾。所以集合AI到DAI的映射f:B→(B∩D)*為一一映射。
b)根據(jù)a)的結(jié)論，再結(jié)合逆否命題同時(shí)為真或同時(shí)為假即可得證。
推論 設(shè)L(U，A，I)為概念格，b∈A，令D=A-{b}，下列命題成立：
a)b為非核心屬性集合AI到集合AID的映射f:B→(B∩D)為一一映射；
b)b為核心屬性集合AI到集合AID的映射f:B→(B∩D)不是一一映射。
3 概念格屬性約簡(jiǎn)算法
對(duì)于任意形式背景(U，A，I)而言，如果A中的每個(gè)屬性均為核心屬性，那么A本身即為一個(gè)約簡(jiǎn)，若A中存在非核心屬性a1，由性質(zhì)3得A/{a1}為協(xié)調(diào)集；如果協(xié)調(diào)集A/{a1}中的每個(gè)屬性均為核心屬性，同理可得A/{a1}為形式背景(U，A，I)的一個(gè)約簡(jiǎn)，否則A/{a1}中存在非核心屬性a2，由性質(zhì)3得A/{a1，a2}為協(xié)調(diào)集，再研究A/{a1，a2}。重復(fù)以上過(guò)程，由于A是有限集，這樣依次操作下去總可以找到一個(gè)約簡(jiǎn)。根據(jù)以上思想，結(jié)合推論1可以得到以下的概念格屬性約簡(jiǎn)算法。
算法 基于一一映射的概念格屬性約簡(jiǎn)算法
輸入:形式背景(U，A，I)
輸出:A的一個(gè)相對(duì)約簡(jiǎn)
a)令E=A；
b)若存在屬性a∈E，令D=E/{a}，使得映射f:EI→EID為一一映射，轉(zhuǎn)c)；否則轉(zhuǎn)d)
c)選擇滿足f:EI→EID為一一映射的屬性集D=E/{a}，執(zhí)行E←D，并轉(zhuǎn)b)；
d)結(jié)束，輸出結(jié)果E。
例1 形式背景(U，A，I)如表1所示。其中對(duì)象集U={1，2，3，4}，屬性集A={a，b，c，d，e，f}，求其約簡(jiǎn)。
形式背景(U，A，I)有六個(gè)概念：(X1，B1)=(，A)，(X2，B2)=(U，)，(X3，B3)=(13，e)，(X4，B4)=(1，cdef)，(X5，B5)=(24，abcd)，(X6，B6)=(124，cd)。
其概念格如圖1所示。
下面利用算法1計(jì)算例1的約簡(jiǎn)。
a)對(duì)于屬性a，令E=A，那么
D=E/{a}={b，c，d，e，f}
B1∩D={b，c，d，e，f}，B2∩D=
B3∩D={e}，B4∩D={c，d，e，f}
B5∩D={b，c，d}，B6∩D={c，d}
故f:EI→EID為一一映射，執(zhí)行E←E/{a}。
b)對(duì)于屬性b，E={b，c，d，e，f}，那么
D=E/{b}={c，d，e，f}
B1∩D={c，d，e，f}，B2∩D=
B3∩D={e}，B4∩D={c，d，e，f}
B5∩D={c，d}，B6∩D={c，d}
故f:EI→EID不為一一映射。
c)對(duì)于屬性c，E={b，c，d，e， f}，那么
D=E/{c}={b，c，d，e，f}
B1∩D={b，d，e，f}，B2∩D=
B3∩D={e}，B4∩D={d，e，f}
B5∩D={b，d}，B6∩D=g0gggggg
故f:EI→EID為一一映射，執(zhí)行E←E/{c}。
d)對(duì)于屬性d，E={b，d，e，f}，那么
D=E/g0gggggg={b，e，f}
B1∩D={b，e，f}，B2∩D=
B3∩D={e}，B4∩D={e，f}
B5∩D={b}，B6∩D=
故f:EI→EID不為一一映射。
e)對(duì)于屬性e，E={b，d，e，f}，那么
D=E/{e}={b，d，f}
B1∩D={b，d，f}，B2∩D=
B3∩D=，B4∩D={d，f}
B5∩D={b，d}，B6∩D=g0gggggg
故f:EI→EID不為一一映射。
f)對(duì)于屬性f，E={b，d，e，f}，那么
D=E/{f}={b，d，e}
B1∩D={b，d，e}，B2∩D=
B3∩D={e}，B4∩D={d，e}
B5∩D={b，d}，B6∩D=g0gggggg
故f:EI→EID為一一映射，E←E/{f}。
g)對(duì)于屬性b，d，e∈E，映射f:EI→EID均不為一一映射，算法結(jié)束，輸出結(jié)果E={b，d，e}。
由算法1求得一個(gè)約簡(jiǎn)E={b，d，e}，其概念格如圖2所示。在整個(gè)求約簡(jiǎn)的過(guò)程中，不涉及對(duì)象與屬性集之間的“*”運(yùn)算，僅僅只是簡(jiǎn)單的集合間的交運(yùn)算，所需計(jì)算量小，簡(jiǎn)單容易操作。
4 結(jié)束語(yǔ)
屬性約簡(jiǎn)是概念格理論中的一個(gè)重要內(nèi)容之一，目前對(duì)此方面的研究處于起步階段，其理論方法亟待完善。本文從一一映射的角度給出了一種新穎的概念格屬性約簡(jiǎn)算法。與現(xiàn)有算法相比，本文給出的約簡(jiǎn)算法只需要簡(jiǎn)單的集合間的交運(yùn)算，而不涉及對(duì)象與屬性集之間的“*”運(yùn)算，此外它計(jì)算約簡(jiǎn)時(shí)所需要的計(jì)算量小，簡(jiǎn)單容易操作。關(guān)于模糊概念格的屬性約簡(jiǎn)方法筆者將另文給出。
參考文獻(xiàn)：
［1］WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[C]//Proc of Ordered Sets.DordrechtBoston:Reidel，1982:445470.
［2］OOSTHULZEN G D.The application of concept lattice to machine learning[D].Pretoria :University of Pretoria，1996.
［3］HO T B.Incremental conceptual clustering in the framework of Galois lattice[C]// LU H，MOTODA H，LIU H. Proc of KDD:Techniques and Applications.Singapore: World Scientific，1997:4964.
［4］SIFF M， REPS T.Identifying modules via concept analysis[C]//Proc of International Confercence on Software Maintenance.Washington:IEEE Computer Society，1997:170179.
［5］SCHMITT I，SAAKE G.Merging inheritances for scheme integration based on concept lattices[EB/OL].(20041008). [20080306]. http://www.mathematic.tudram stadt.de/ags/agl.
［6］張文修，魏玲，祁建軍.概念格的屬性約簡(jiǎn)理論[J].中國(guó)科學(xué):E輯，2005，35(6):628639.
［7］吳強(qiáng)，周文，劉宗田，等.基于粗糙集理論的概念格屬性約簡(jiǎn)及算法[J].計(jì)算機(jī)科學(xué)，2006，33(6):179181.
