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

智慧來，智東杰

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

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

智慧來，智東杰

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

1 引言

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

2 基本概念

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

定義1設K=（G，Μ，I）是一個形式背景，A?G，B?Μ。如果A、B滿足條件f（A）=B、g（B）=A，則稱序?qū)Γˋ，B）為形式背景K的一個概念。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設K=（G，Μ，I）是一個形式背景，(A1，B1)、(A2，B2)∈L(K)，如果A1?A2或B1?B2，稱(A1，B1)是(A2，B2)的子概念，記為(A1，B1)≤(A2，B2)。顯然L（K）關(guān)于“≤”構(gòu)成一個格，稱為概念格。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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對于一個概念，如果概念（A，B）是一個屬性概念，并且屬性標簽是m，那么g（m）=A，并且對于?m′∈{B-m}有g(shù)(m)?g(m′)；對偶地，如果概念（A，B）是一個對象概念，并且對象標簽是g，那么f（g）=B，并且對于?g′∈{A-g}有f(g)?f(g′)。

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

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

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

例1一個形式背景如表1，對應的概念格如圖1。

表1 形式背景K

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

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

圖1 概念格L（K）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（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ù)上述公式，很容易得到計算全部概念內(nèi)涵縮減的算法，這里不再贅述。

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

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

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

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

圖2 算法運行時間對比

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。

證明因為bi＜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。

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

7 結(jié)束語

本文深入研究了對象概念和屬性概念，分析了對象概念和屬性概念與不可約元的關(guān)系，提出了對象概念和屬性概念的識別算法，進而得到了以屬性概念為遞歸終止條件的內(nèi)涵縮減計算方法，在最后研究了對象和屬性的比較及其在規(guī)則提取中的應用。進一步需要研究的是對象概念和屬性概念與奇異點的關(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]姜峰，范玉順.基于擴展概念格的Web關(guān)系挖掘[J].軟件學報，2010，21（10）：2432-2444.

[4]丁衛(wèi)平，顧春華.基于形式概念分析的不完備電子病歷系統(tǒng)粗糙挖掘研究[J].計算機科學，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].計算機工程與應用，2009，45（1）：42-44.

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

[9]智慧來，智東杰，劉宗田.從合取范式到析取范式的轉(zhuǎn)換研究[J].計算機工程與應用，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

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

形式概念分析；對象概念；屬性概念；關(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.

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

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

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