協(xié)調(diào)決策形式背景下概念格的屬性約簡

摘要：概念格是知識處理與分析中的一個有力工具，對它進(jìn)行約簡可以提高效率簡化問題。該文在協(xié)調(diào)決策形式背景下給出了協(xié)調(diào)集及屬性特征的判定定理，并在此基礎(chǔ)上得到了一種求屬性約簡的方法。

關(guān)鍵詞： 概念格；協(xié)調(diào)決策形式背景；協(xié)調(diào)集；屬性約簡

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)35-2225-03

Attribute Reduction in Consistent Decision Formal Context

LIU Ya-li

(School of Science，Kunming University of Science and Technoledge，Kunming 650093，China)

Abstract: The concept lattice is useful in knowledge processing and analyzing.By reducing lattice，it can get the process more efficiently and the work will be simpler.This paper gives the judgement theorems of consistent set and characters of attributes in consistent decision formal context and provides an algorithm to explore the reduction.

Key words: concept lattice;consistent decision formal context;consistent set;attribute reduction

1 引言

形式概念分析，也稱概念格，是由Wille于1982年提出的[1]，它提供了一種支持?jǐn)?shù)據(jù)分析的有效工具。概念格的每個節(jié)點(diǎn)是一個形式概念，由兩部分組成：外延，即概念所覆蓋的實例；內(nèi)涵，即概念的描述，該概念覆蓋實例的共同特征。另外，概念格通過Hasse圖生動和簡潔地體現(xiàn)了這些概念之間的泛化和特化關(guān)系。因此，概念格被認(rèn)為是進(jìn)行數(shù)據(jù)分析的有力工具。概念格理論已被廣泛應(yīng)用于知識工程、數(shù)據(jù)挖掘、信息檢索、軟件工程等領(lǐng)域[2-5]。

屬性約簡是知識發(fā)現(xiàn)研究的重要課題，所謂屬性約簡，就是針對不同的目的的要求，刪除其中不相關(guān)或不重要的屬性，使知識進(jìn)行簡化，又不丟失基本信息。文[6]提出了決策形式背景，本文基于決策形式背景討論了協(xié)調(diào)集及屬性特征的判定定理，得到了協(xié)調(diào)決策形式背景知識約簡的一種方法。

2 基本概念

定義2.1[7] 稱（U，A，I）為形式背景，其中U={x1，x2，...，xn}為對象集，每個xi（i≤n）稱為一個對象；A={α1，α2，...，αm}為屬性集，每個αj（j≤m）稱為一個屬性；I為U和A之間的二元關(guān)系，I#8838;U×A 。若(x，α)∈I，則說x具有屬性α，記為 xIα。

該文中，用1表示(x，α)∈I ，用0表示(x，α)#8713;I，這樣形式背景就可以表示為只有0和1的表格。

對于X#8838;U，B#8838;A，定義運(yùn)算：

，記{x}*為x*；，記{a}*為a*。若且，， 則稱形式背景是正則的。本文所研究的形式背景都是正則的。

定理2.1[7]設(shè)（U，A，I）是形式背景，X1，X2，X#8838;U和B1，B2，B#8838;A，則：

定義2.2[7]設(shè)（U，A，I）為形式背景。如果一個二元組（X，B）滿足X*=B且X=B*，則稱（X，B）是一個形式概念，簡稱概念。其中X稱為概念的外延，B稱為概念的內(nèi)涵。

用L（U，A，I）表示形式背景（U，A，I）的全體概念，規(guī)定：

容易證明“≤”是L（U，A，I）上的偏序關(guān)系。

若（X1，B1），（X2，B2）∈L（U，A，I） ，則

也是概念，從而L（U，A，I）是格。

定義2.3[8]設(shè)L（U1，A1，I1）和L（U1，A1，I1）是兩個概念格，如果對于（X，B）∈L（U2，A2，I2）總存在（X'，B'）∈L（U1，A1，I1）使得X'=X ，則稱L（U1，A1，I1）細(xì)于L（U1，A1，I1），記作L（U1，A1，I1）≤L（U2，A2，I2）。

在形式背景（U，A，I）下，，記，那么（U，D，ID）仍然是形式背景。對于運(yùn)算，在（U，A，I）下仍用X*表示，在（U，D，ID）下用XD*表示，顯然。

定義2.4[6]設(shè)（U，A，I），（U，Q，J）是兩個形式背景，有形同的論域，則稱（U，A，I，Q，J）為決策形式背景。若L（U，A，I）≤L（U，Q，J）稱決策形式背景是協(xié)調(diào)的。若D#8838;A ，有（U，D，ID）≤（L，Q，J）稱D是決策形式背景的協(xié)調(diào)集，且不存在任何D的真子集是決策形式背景的協(xié)調(diào)集，稱D為決策形式背景的約簡集。

定義2.5 設(shè)協(xié)調(diào)決策形式背景（U，A，I，Q，J）的所有約簡集為{Di|Di是約簡，i∈τ}(τ是一指標(biāo)集)，可將屬性分為：

1) 絕對必要屬性2) 不必要屬性

推論2.1 α∈A是絕對必要屬性#8660;A-{α}不是協(xié)調(diào)集

推論2.2 α∈A是不必要屬性#8660;A-{α}是協(xié)調(diào)集

3 協(xié)調(diào)決策形式背景下協(xié)調(diào)集及屬性特征的判定定理

引理3.1 設(shè)（U，A，I，Q，J）是協(xié)調(diào)決策形式背景，D#8834;A，D≠Ф，則D是協(xié)調(diào)集當(dāng)且僅當(dāng)

證明：（#8656;） ∵ L(U，A，I)≤L（U，Q，J） ，因此對#8704;（X，B）∈L（U，Q，J）一定有（X，X*）∈L（U，A，I）。由已知（X*∩D）*=（B**∩D）*=B*=X，因此（X，X*∩D）∈L（U，D，ID），即L（U，D，ID）≤L（U，Q，J） ，所以D為約簡集。

（#8658;）假若D是協(xié)調(diào)集，即L（U，D，ID）≤L（U，Q，J）。因此對（F*，F(xiàn)Q**）∈L（U，Q，J），存在E#8838;D，（F*，E）∈L（U，D，ID），因此F*=E*。又E ＝（F*）D*=F**∩D，所以 （F**∩D）*=F

引理3.2 設(shè)（U，A，I，Q，J）是協(xié)調(diào)決策形式背景，D#8834;A，D≠Ф。則D是協(xié)調(diào)集當(dāng)且僅當(dāng)#8707;E#8838;D，E≠Oslash; ， E*=F*。

證明：（#8658;）由引理3.1即得。

（#8656;）由已知，E*=F*，E#8838;E**=F**，所以E#8838;F**∩D，因此（F**∩D）*#8838;E*=F*，又F**∩D#8838;F**，所以（F**∩D）*#8839;F***=F*，即得F**∩D=F*，由引理3.1，D為協(xié)調(diào)集。

引理3.3 設(shè)（U，A，I，Q，J）是協(xié)調(diào)決策形式背景，D#8834;A，D≠Ф，則D是協(xié)調(diào)集當(dāng)且僅當(dāng)#8704;e∈Q，#8707;E#8838;D，E≠Oslash; ， E*=e*。

證明：（#8658;）由引理3.2即證。

（#8656;）對#8704;F#8838;Q，F(xiàn)≠Oslash;，記F={ek:k∈τ}（τ為指標(biāo)集）。由已知ek∈F#8838;Q，#8707;Ek#8838;D，Ek≠Oslash; ， 使得Ek*=ek*。因此F*=ek*=Ek* ＝（Ek)*，令E=Ek，即對#8704;F#8838;Q，F(xiàn)≠Oslash;， #8707;E=Ek#8838;Q使E*=F*。由引理3.2， D是協(xié)調(diào)集。

引理3.4 設(shè)（U，A，I，Q，J）是協(xié)調(diào)決策形式背景D#8834;A，D≠Ф，則D是協(xié)調(diào)集當(dāng)且僅當(dāng)#8704;e∈Q， （e**∩D）*=e*

證明： （#8658;）由引理3.1即證。

（#8656;） 由已知e∈Q， （e**∩D）*=e*，記E=e**∩D則E#8838;D，E≠Ф，且E*=e*，由引理3.3，D是協(xié)調(diào)集。

定理3.1設(shè)（U，A，I，Q，J）是協(xié)調(diào)決策形式背景，若#8707;e#8838;Q，α∈e** ，且(e**-{α})*≠e* ，則α是絕對必要屬性。

證明：若α是不必要屬性，則A-{α}是協(xié)調(diào)集。那么，，即(e**-{α})*=e*，這與已知矛盾，所以α是絕對必要屬性。

定理3.2設(shè)（U，A，I，Q，J）是協(xié)調(diào)決策形式背景，若#8707;e#8838;Q，α∈e**，有(e**-{α})*=e*，則α是不必要屬性。

證明：若α是絕對必要屬性，則A-{α}不是協(xié)調(diào)集，那么，#8707;e∈Q，使，即(e**-{α})*≠e*，這與已知矛盾，所以α是不必要屬性。

定理3.3設(shè)（U，A，I，Q，J）是協(xié)調(diào)決策形式背景，對于#8704;e∈Q ，有α#8713;e** ，這則α是不必要屬性。

證明：若α是絕對必要屬性，則存在約簡集D使#8704;e∈Q ，，而α#8713;e** ，即，所以D-{α}為協(xié)調(diào)集，則與D使約簡集矛盾！所以α是不必要屬性。

4 一種求協(xié)調(diào)決策形式背景屬性約簡的算法

對于協(xié)調(diào)決策形式背景（U，A，I，Q，J）而言，若A中的每個元素均為絕對必要屬性，則A即為一個約簡。否則設(shè)存在Kil為A中的不必要屬性，則A-{Ki1}為協(xié)調(diào)集，此時考察D=A-{Ki1}，如果D中每個元素均為協(xié)調(diào)決策形式背景（U，A，ID，Q，J）絕對必要屬性，則D即為（U，A，I，Q，J）的一個約簡。否則設(shè)Ki2∈D為D中的不必要屬性，此時再考察D=D-{Ki2}=A-{Ki1，Ki2} ，重復(fù)上述過程，由于A使有限集，則總可以找到D#8838;A ，D為約簡集?；诖怂枷耄覀兛梢缘玫饺缦虑蠹s簡的一個算法。

int Amatrix[][]; //定義屬性矩陣

int objCount;//對象個數(shù)

int propCount; //屬性個數(shù)

bool isNecessaryProp[propCount]; //是否是必要屬性矩陣

bool isNecessary(int prop[]);//定義是否是必要屬性的子函數(shù)

main() //程序主函數(shù)

{

int i，j=0;

bool isNecessaryP;//判斷某個屬性是否為必要屬性，是為true，否為1

for(i=0;i

{

isNecessaryP=isNecessary(Amatrix[][i]);

isNecessaryPropMatrix[i]=isNecessaryP;

}

for(i=0;i

{

if(isNecessaryPropMatrix[i])

{

hasNecessaryProp[j]=i;

j++;

}}

輸出結(jié)果集(hasNecessaryProp[j]中存放了哪些是必要屬性);

}

bool isNecessary(int prop[])//判斷是否為必要屬性的子函數(shù)，返回值為bool型，參數(shù)為屬性列矩陣

{

int Qmatrix[][];//決策集

int Qcount;//決策集列數(shù)

int Qmatrix1[][];//Qmatrix*的結(jié)果集

int Qmatrix2[];//Qmatrix**的結(jié)果集

int i，j=0，k=0;

bool t=1;

for(i=0;i

{

if(Amatrix[對象obj的序號][i]==Qmatrix[對象obj的序號][i])

{

Qmatrix1[][j]=Amatrix[][i];

j++;

}

for(i=0;i

{

if(Amatrix[對象obj的序號][j]==true)

{

Qmatrix2[k]=對象obj的序號;

k++;

}

}}

for(i=0;i

{

if(Amatrix[][i]蘊(yùn)涵在Qmatrix**中)

{

if(Qmatrix**-Amatrix[][i])*!=Qmatrix*

t=true;

} }

return t;

}

例：給出協(xié)調(diào)決策形式背景（U，A，I，Q，J），其中U={1，2，3，4} ，A={a，b，c，d，e，f} ，Q={g，h，k} （見下表）

我們對表所描述的協(xié)調(diào)決策形式背景求約簡如下：α是A的不必要屬性，則D=A-{α} ，b是D的絕對必要屬性，則D不發(fā)生改變，c是D的不必要屬性，則D=D-{c}=A-{a，c}，d是D的絕對必要屬性，則D不發(fā)生改變，e是D的不必要屬性，則D=D-{e}=A-{a，c，e}，f是D的絕對必要屬性，則D不發(fā)生改變，從而D=A-{a，c，e}={b，d，f} 為協(xié)調(diào)決策形式背景（U，A，I，Q，J）的一個約簡。

注：協(xié)調(diào)決策形式背景（U，A，I，Q，J）的約簡可能不唯一，要求出其全部約簡只需改變A中元素的排列順序即可。

5 結(jié)束語

概念格理論是一種數(shù)據(jù)分析和知識處理的工具，已被成功應(yīng)用于許多領(lǐng)域。本文給出了協(xié)調(diào)決策形式背景下的概念格協(xié)調(diào)集及屬性特征的判定定理，并在此基礎(chǔ)上得到了尋找約簡的方法。

參考文獻(xiàn)：

[1] Wille R.Restructuring lattice theory:an approach based on hierarchies of concepts [C]//IVAN R.Ordered Sets.Boston:Reidel，1982:445-470.

[2] Oosthuizen GD.The Application of Concept Lattice to Machine Learning [R] Technical Report，University of Pretoria，South Africa，1996.

[3] Ho T B.Incremental conceptual clustering in the framework of Galois lattie[A].in Lu H，Motoda H，Liu H，eds KDD:Techniques and Applications[C].World Scientific，1997，49-64.

[4] Kent R E，Bowman C M.Digital Libraries，Conceptual knowledge systems and the Nebula interface[R].University of Arkansas，1995.

[5]Corbett D，Burrow A L .Knowledge reuse in SEED exploiting conceptual graphs[A].International Conference on Conceptual Graphs(ICCS’96)[C].Sydney，1996，56-60.

[6] Wolff K E.A comceptual view of knowledge bases in rough set theory[C].Lecture Notes in Computer Science.Vol.2005，Spring-Berlin，2001:220-228.

[7] GanterB，Wille R.Formal Concept Analysis[M].MathematicalFoundations，Berlin:Springer，1999.

[8] 張文修，魏玲，祁建軍.概念格的屬性約簡理論與方法[J].中國科學(xué)，2005，35(6).