智慧來，智東杰

河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454150

形式概念分析中的對象概念與屬性概念

智慧來，智東杰

河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454150

1 引言

形式概念分析[1]是Ganter B和Wille R提出的，以序理論和完備格理論為基礎(chǔ)，依據(jù)數(shù)據(jù)庫中提供的基本信息建立起的一種刻畫對象與屬性之間關(guān)系的數(shù)學(xué)結(jié)構(gòu)。形式概念分析強(qiáng)調(diào)以人的認(rèn)知為中心，提供了一種與傳統(tǒng)的、統(tǒng)計(jì)的數(shù)據(jù)分析和知識表示完全不同的方法。由于它便于概念結(jié)構(gòu)的開發(fā)和討論，在某種意義上，概念格已經(jīng)變成了一種外部認(rèn)知的手段[2]。概念格已經(jīng)有許多比較成功的應(yīng)用，例如：姜峰等利用擴(kuò)展概念格在Web上進(jìn)行服務(wù)關(guān)系的自動(dòng)挖掘和維護(hù)[3]，丁衛(wèi)平等利用形式概念分析的理論對不完備電子病歷系統(tǒng)進(jìn)行數(shù)據(jù)挖掘[4]。為了進(jìn)一步提高數(shù)據(jù)表示和數(shù)據(jù)挖掘的效率，有必要對其中的特殊概念進(jìn)行更深入的研究。

2 基本概念

以下的定義來源于Ganter B和Wille R的著作“Formal Concept Analysis：Mathematical Foundation”[1]。為了本文寫作的需要，使用的符號和論述方式可能有所不同。

定義1設(shè)K=（G，Μ，I）是一個(gè)形式背景，A?G，B?Μ。如果A、B滿足條件f（A）=B、g（B）=A，則稱序?qū)Γˋ，B）為形式背景K的一個(gè)概念。A稱為概念（A，B）的外延，B稱為概念（A，B）的內(nèi)涵。L（G，Μ，I）或L（K）表示K中所有概念全體構(gòu)成的集合，即：L（G，Μ，I）={（A×B）∈G×Μ，f（A）=B，g（B）=A}。其中，f(A)={m∈Μ|?g∈A,gIm}，g(B)={g∈G|?m∈B，gIm}。

定義2設(shè)K=（G，Μ，I）是一個(gè)形式背景，(A1，B1)、(A2，B2)∈L(K)，如果A1?A2或B1?B2，稱(A1，B1)是(A2，B2)的子概念，記為(A1，B1)≤(A2，B2)。顯然L（K）關(guān)于“≤”構(gòu)成一個(gè)格，稱為概念格。

定義3在一個(gè)概念格中，如果一個(gè)概念具有形式（g（f（g）），f（g））且g∈G，則稱（g（f（g）），f（g））是一個(gè)對象概念；如果一個(gè)概念具有形式（g（m），f（g（m）））且m∈Μ，則稱（g（m），f（g（m）））是一個(gè)屬性概念。

定義4集合Μ與N之間的二元關(guān)系R是有序二元組（m，n）的集合，其中m∈Μ，n∈N，即R?Μ×N，這里的×是笛卡兒積，（m，n）∈R，也常記做mRn，如果Μ=N，則稱R是Μ上的二元關(guān)系。R的逆關(guān)系用R-1表示，即nR-1m?mRn。

定義5集合Μ上的二元關(guān)系R稱為一個(gè)偏序關(guān)系，如果對所有的x，y，z∈Μ都有：①xRx；②xRy和x≠y?不是yRx；③xRy和yRz?xRz。偏序關(guān)系R常用≤來表示，當(dāng)x≤y且x≠y時(shí)，寫做x＜y。一個(gè)集合Μ及其上的序≤形成的有序二元組（Μ，≤）稱為半序集。

定義6令（Μ，≤）是一個(gè)半序集，A是Μ的子集，Μ中的元素s滿足?a∈A都有s≤a，則稱s是A的一個(gè)下界。對偶地，若Μ中的元素s滿足?a∈A都有s≥a，則稱s是A的一個(gè)上界。如果A的所有下界組成的集合中有最大元素，則稱這個(gè)元素為A的下確界，記infA或∧A。對偶地，上界集合的最小元素稱為上確界，記supA或∨A。

定義7一個(gè)半序集（V，≤），如果V中任意兩個(gè)元素x，y的上確界及下確界都存在，則稱V是一個(gè)格。如果V的任何子集X的上確界及下確界都存在，則稱V是一個(gè)完全格。

定義8對于完全格V的一個(gè)元素v，定義vl=∨{x∈V|x＜v}，vu=∨{x∈V|x＜v}，如果v≠vl即v不是嚴(yán)格小于它的那些元素的上確界，則稱v是上確界不可約的，或者稱v是上確界不可約元；如果v≠vu，即v不是嚴(yán)格大于它的那些元素的下確界，則稱v是下確界不可約的，或者稱v是下確界不可約元。

在不區(qū)分上確界不可約元和下確界不可約元的情況下，它們統(tǒng)稱為不可約元。

定義9a稱為b的下近鄰，當(dāng)a＜b，且沒有c滿足a＜c＜b，這時(shí)也稱b是a的上近鄰，并且記做a?b。

命題1有限格的一個(gè)元素是上確界不可約的，當(dāng)且僅當(dāng)它有且僅有一個(gè)下近鄰；一個(gè)元素是下確界不可約的，當(dāng)且僅當(dāng)它有且僅有一個(gè)上近鄰。

在概念格中，一個(gè)概念的下近鄰是它的子概念，一個(gè)概念的上近鄰是它的父概念。

3 對象（屬性）概念的識別

定理1對象概念是上確界不可約元，上確界不可約元一定是對象概念；對偶的，屬性概念是下確界不可約元，下確界不可約元一定是屬性概念。

證明如果一個(gè)概念有兩個(gè)或兩個(gè)以上的下近鄰，則這個(gè)概念的外延縮減的勢大于等于2，因此不存在唯一一個(gè)對象g∈G使得（g（f（g）），f（g））成立；如果一個(gè)概念只有一個(gè)下近鄰，則這個(gè)概念的對象標(biāo)簽為這個(gè)概念的外延減去下近鄰概念的外延。根據(jù)概念格的對偶原理，可知定理的后半部分成立。

根據(jù)定理1可以得到概念格中對象概念的識別算法，同時(shí)為對象概念貼上對象標(biāo)簽。

算法1概念格中對象概念的識別算法

步驟1訪問概念格中的最小概念，如果其外延非空，那么這個(gè)概念是一個(gè)對象概念，標(biāo)簽為外延中的對象。

步驟2訪問最小概念的所有父概念，若訪問的概念只有最小概念作為其下近鄰，那么這個(gè)概念是一個(gè)對象概念，標(biāo)簽為概念外延減去最小概念的概念外延。

步驟3訪問步驟2中已經(jīng)訪問的所有概念的父概念，直到最大概念為止，若訪問的概念只有一個(gè)子概念，那么這個(gè)概念是一個(gè)對象概念，標(biāo)簽為概念外延減去其子概念的概念外延。

對偶地，可以得到概念格中屬性概念的識別算法。

4 對象（屬性）的比較

定義10對于任意的g1∈G，g2∈G，如果f(g1)?f(g2)或者f(g2)?f(g1)成立，則稱g1和g2是可比的，并記做g1＜g2或者g2＜g1；否則稱g1和g2是不可比的，并記做g1||g2。

對偶地，對于任意的m1∈Μ，m2∈Μ，如果g(m1)?g(m2)或者g(m2)?g(m1)成立，則稱m1和m2是可比的，并記做m1＜m2或者m2＜m1；否則稱m1和m2是不可比的，并記做m1||m2。

定理2對于一個(gè)概念，如果概念（A，B）是一個(gè)屬性概念，并且屬性標(biāo)簽是m，那么g（m）=A，并且對于?m′∈{B-m}有g(shù)(m)?g(m′)；對偶地，如果概念（A，B）是一個(gè)對象概念，并且對象標(biāo)簽是g，那么f（g）=B，并且對于?g′∈{A-g}有f(g)?f(g′)。

證明（反證法）假設(shè)?m′∈{B-m}有g(shù)(m′)?g(m)，那么g({m，m′})=g(m′)?g(m)=B，可知g(m)?g({m，m′})?A，產(chǎn)生矛盾。因此，假設(shè)不成立，定理成立。根據(jù)概念格的對偶原理，可知定理的后半部分成立。

性質(zhì)1在概念格中，如果存在兩個(gè)可比的對象（屬性）概念，那么它們標(biāo)簽中的對象（屬性）也是可比的。

定義11在一個(gè)對象（屬性）集合中，若存在若干對象（屬性）是可比的，則刪除所有大于最小的對象（屬性）的對象（屬性），這個(gè)操作稱為集合的純化操作，記做purify。

例1一個(gè)形式背景如表1，對應(yīng)的概念格如圖1。

表1 形式背景K

在概念格L（K）中，對象概念有：（1）（123，127），對象標(biāo)簽為1；（2）（23，1278），對象標(biāo)簽為2；（3）（3，12378），對象標(biāo)簽為3；（4）（4，13789），對象標(biāo)簽為4；（5）（56，1246），對象標(biāo)簽為5；（6）（6，12346），對象標(biāo)簽為6。

屬性概念有：（1）（123456，1），屬性標(biāo)簽為1；（2）（12356，12），屬性標(biāo)簽為2；（3）（346，13），屬性標(biāo)簽為3；（4）（56，1246），屬性標(biāo)簽為4、6；（5）（{}，Μ），屬性標(biāo)簽為5；（6）（1234， 17），屬性標(biāo)簽為7；（7）（234，178），屬性標(biāo)簽為8；（8）（4，13789），屬性標(biāo)簽為9。

圖1 概念格L（K）

根據(jù)概念格的結(jié)構(gòu)，對象排序?yàn)椋海?＜2＜3）||4||（5＜6）。屬性排序?yàn)椋?＜（（4，6）＜2）||（9＜（8＜7||3））＜1。

對于上面的屬性序列，一個(gè)純化操作的例子為：purify（8＜7||3）={8，3}。

5 內(nèi)涵縮減（外延縮減）的計(jì)算

內(nèi)涵縮減的應(yīng)用主要集中在關(guān)聯(lián)規(guī)則提取[5]和概念的穩(wěn)定性分析[6]這兩個(gè)方面，下面來論述屬性概念在計(jì)算內(nèi)涵縮減中的應(yīng)用。

定義12對于給定的概念C=（A，B），如果屬性集合R滿足g（R）=g（B）=A，且對于任意的R1?R有g(shù)(R1)?g(R)，則稱R是C的一個(gè)內(nèi)涵縮減。

內(nèi)涵縮減的意義在于利用最少的屬性識別概念，因此內(nèi)涵縮減的定義包括兩重內(nèi)容：（1）縮減后的內(nèi)涵仍然能識別這個(gè)對象；（2）縮減后的內(nèi)涵包括的屬性是最少的。

對偶地，可以定義外延縮減：對于給定的概念C=（A，B），如果屬性集合S滿足下述兩個(gè)條件：（1）f(S)=f(A)=B；（2）對于任意的S1?S有f(S1)?f(S)；則稱R是C的一個(gè)外延縮減。

利用內(nèi)涵縮減，可以得到關(guān)聯(lián)規(guī)則。如果概念C=（A，B）的內(nèi)涵縮減R，如果滿足R?B，那么每個(gè)概念C都對應(yīng)一個(gè)蘊(yùn)含集rules(C)={R→Intent(C)-R}。其物理意義是，如果R能表示概念C，那么就能由R得到概念C的其他屬性。

定理3屬性概念的內(nèi)涵縮減為它的標(biāo)簽屬性。

證明根據(jù)定理1，可知定理成立。

定理4對于一個(gè)非屬性概念，它的一個(gè)近似內(nèi)涵縮減為任意兩個(gè)父概念內(nèi)涵縮減的并。

上述定理求得的是一個(gè)近似內(nèi)涵縮減，是因?yàn)镽i∪Rj中可能存在可比的屬性，因此內(nèi)涵縮減為Purify(Ri∪Rj)。

內(nèi)涵縮減的遞歸計(jì)算公式：

（1）如果概念（A，B）是一個(gè)屬性概念，則內(nèi)涵縮減是這個(gè)概念的屬性標(biāo)簽；

（2）如果概念（A，B）不是屬性概念，并且它的父概念為(A1，B1)，(A2，B2)，…，(An，Bn)，這些概念的內(nèi)涵縮減為R1，R2，…，Rn，那么內(nèi)涵縮減為{Purify(Ri∪Rj)|i≠j，i，j∈1，2，…，n}。

根據(jù)上述公式，很容易得到計(jì)算全部概念內(nèi)涵縮減的算法，這里不再贅述。

例2在概念格L（K）中（見圖1），計(jì)算（23，1278）的內(nèi)涵縮減。

（23，1278）的父概念有（123，127）和（234，178），（123，127）有兩個(gè)父概念（12356，12）和（1234，17），（12356，12）是一個(gè)屬性概念，其內(nèi)涵縮減為標(biāo)簽2，（1234，17）也是一個(gè)屬性概念，其內(nèi)涵縮減為標(biāo)簽7，所以（123，127）的內(nèi)涵縮減為purify({2}∪{7})={2，7}，（234，178）也是一個(gè)屬性概念，其內(nèi)涵縮減為標(biāo)簽8，因此（23，1278）的內(nèi)涵縮減為purify({2，7}∪{8})={2，8}。

從上面的計(jì)算過程可以看到，如果要計(jì)算概念格中所有概念的內(nèi)涵縮減，那么每計(jì)算一個(gè)概念的內(nèi)涵縮減就可以通過計(jì)算它的任意兩個(gè)父概念的內(nèi)涵縮減的并來獲得。若是采用文獻(xiàn)[7-8]中的方法逐個(gè)計(jì)算每個(gè)概念的內(nèi)涵縮減，首先要計(jì)算概念和所有父概念內(nèi)涵的差集，然后計(jì)算內(nèi)涵差集最小覆蓋，最終轉(zhuǎn)化為從合取范式到析取范式的轉(zhuǎn)換[9]，并且已經(jīng)證明合范式轉(zhuǎn)換復(fù)雜度是指數(shù)級[10]。顯然，集合并運(yùn)算比首先計(jì)算差集然后實(shí)現(xiàn)范式轉(zhuǎn)換簡便得多。

在實(shí)驗(yàn)對比兩種方法的性能時(shí)，隨機(jī)生成了一個(gè)形式背景，對象數(shù)為300，屬性數(shù)為30，對象和屬性間存在關(guān)系的概率為0.2，生成形式背景的概念格后，隨機(jī)抽取50、100、150、200、250個(gè)概念計(jì)算內(nèi)涵縮減。實(shí)驗(yàn)結(jié)果如圖2，L1是采用范式轉(zhuǎn)換方法的運(yùn)行時(shí)間，L2是本文的方法運(yùn)行時(shí)間。

圖2 算法運(yùn)行時(shí)間對比

6 屬性排序與關(guān)聯(lián)規(guī)則提取

定義13給定關(guān)聯(lián)規(guī)則r:P→Q，記supp(r)=|g(P∪Q)|/ |G|為該規(guī)則的支持度，cοnf(r)=|g(P∪Q)|/|g(P)|為該規(guī)則的置信度。

定理5若屬性bi和bj是可比的，并且bi＜bj，那么一定存在置信度為1的關(guān)聯(lián)規(guī)則bi→bj。

證明因?yàn)閎i＜bj，所以有g(shù)(bi∪bj)=g(bi)，cοnf(bi→bj)= |g(bi∪bj)|/|g(bi)|=1。

定理6若屬性bi和bj是不可比的，即bi||bj，那么關(guān)聯(lián)規(guī)則bi→bj或者bj→bi的置信度一定存在小于1。

證明因?yàn)閎i||bj，所以有|g(bi∪bj)|＜|g(bi)|和|g(bi∪bj)|＜|g(bj)|，根據(jù)置信度定義，易知定理成立。

根據(jù)定理5，可以直接根據(jù)屬性的排序序列直接得到置信度為1的關(guān)聯(lián)規(guī)則。例如，在概念格L（K）中，根據(jù)屬性排序序列5＜（（（4，6）＜2）||（9＜（8＜7||3））＜1，可以得到9→3，2→1，8→1，8→7等關(guān)聯(lián)規(guī)則。

用定理5獲得的關(guān)聯(lián)規(guī)則一定是最簡的。根據(jù)內(nèi)涵縮減計(jì)算得到的關(guān)聯(lián)規(guī)則實(shí)際上蘊(yùn)涵了這些最簡規(guī)則。例如，在概念格L（K）中，（23，1278）的內(nèi)涵縮減為{2，8}，因此可以得到關(guān)聯(lián)規(guī)則28→17，28→17蘊(yùn)涵了2→1，8→1，8→7。但是，根據(jù)序列5＜（（4，6）＜2）||（9＜（8＜7||3））＜1卻無法得到28→17，而這個(gè)序列卻不包含這樣的信息，這樣的信息只能在概念格中找到，也就是若要得到所有任意屬性組合之間的關(guān)系，則需要建立概念格，而后計(jì)算內(nèi)涵縮減得到關(guān)聯(lián)規(guī)則。

7 結(jié)束語

本文深入研究了對象概念和屬性概念，分析了對象概念和屬性概念與不可約元的關(guān)系，提出了對象概念和屬性概念的識別算法，進(jìn)而得到了以屬性概念為遞歸終止條件的內(nèi)涵縮減計(jì)算方法，在最后研究了對象和屬性的比較及其在規(guī)則提取中的應(yīng)用。進(jìn)一步需要研究的是對象概念和屬性概念與奇異點(diǎn)的關(guān)系，以及對象概念和屬性概念與概念穩(wěn)定性的關(guān)系等內(nèi)容。

[1]Ganter B，Wille R.Formal concept analysis：mathematical foundation[M].New York：Springer-Verlag，l999.

[2]Scaife M，Rogers Y.External cognition：how do graphical representations work[J].International Journal of Human Computer Studies，1996，45：185-213.

[3]姜峰，范玉順.基于擴(kuò)展概念格的Web關(guān)系挖掘[J].軟件學(xué)報(bào)，2010，21（10）：2432-2444.

[4]丁衛(wèi)平，顧春華.基于形式概念分析的不完備電子病歷系統(tǒng)粗糙挖掘研究[J].計(jì)算機(jī)科學(xué)，2009，36（10）：230-233.

[5]Passquier N，Taouil R，Bastide Y，et al.Generating a condensed representation for association rules[J].Journal of Intelligent Information Systems，2005，24：29-60.

[6]Roth C，Obiedkov S，Kourie D G.Towards concise representation for taxonomies of epistemic communities[C]//Yahia S B，Nguifo E M.Proc CLA 4th International Conference on Concept Lattices and their Applications，2006，4923：240-255.

[7]智東杰，智慧來，劉宗田.概念格的內(nèi)涵縮減研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（1）：42-44.

[8]謝志鵬，劉宗田.概念格節(jié)點(diǎn)的內(nèi)涵縮減及其計(jì)算[J].計(jì)算機(jī)工程，2001，27（3）：9-11.

[9]智慧來，智東杰，劉宗田.從合取范式到析取范式的轉(zhuǎn)換研究[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（2）：15-17.

[10]Skowron A，Rauszer C.The discernbility matrices and functions in information systems[M]//Intelligent Decision Support，Handbook of Applications and Advances of the Rough Sets Theory.The Netherlands：Kluwer，1992：331-362.

ZHI Huilai,ZHI Dongjie

School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454150,China

In order to further facilitate data representation and improve the efficiency of data mining,two kinds of special concepts,namely object concept and attribute concept are studied.This paper analyzes relationship between object concepts（or attribute concepts）and irreducible elements,and recognition algorithms of object concepts and attribute concepts are put forward.A recursive algorithm for intent reduction which has attribute concepts as termination condition is given.Attributes sequence as well as its application in association rule extraction is studied.

formal concept analysis;object concept;attribute concept;association rule

為了進(jìn)一步提高數(shù)據(jù)表示和數(shù)據(jù)挖掘的效率，對兩類特殊概念即對象概念和屬性概念進(jìn)行了研究。分析了對象概念和屬性概念與不可約元的關(guān)系，提出了對象概念和屬性概念的識別算法；提出了以屬性概念為遞歸終止條件的計(jì)算內(nèi)涵縮減遞歸算法；研究了屬性排序以及屬性序列在規(guī)則提取中的應(yīng)用。

形式概念分析；對象概念；屬性概念；關(guān)聯(lián)規(guī)則

A

TP18

10.3778/j.issn.1002-8331.1112-0540

ZHI Huilai,ZHI Dongjie.Research on object concepts and attribute concepts in formal concept analysis.Computer Engineering and Applications,2013,49（18）：112-115.

國家自然科學(xué)基金（No.60975033）；上海大學(xué)創(chuàng)新基金（No.A.16-0108-08-002，No.SHUCX091010）；河南理工大學(xué)博士基金（No.B2011-102）。

智慧來（1981—），男，博士，講師，研究領(lǐng)域：知識表示、知識管理、推理技術(shù)等；智東杰（1952—），男，高級實(shí)驗(yàn)師，研究領(lǐng)域：形式概念分析、符號計(jì)算等。

2011-12-28

2012-04-05

1002-8331（2013）18-0112-04

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1139.016.html