形式概念分析

形式概念分析

劉宗田

上海大學(xué)計算機(jī)學(xué)院,200072

ztliu@第1節(jié)基本理論人類在認(rèn)知過程中，把所感覺到的具有共同特點的事物抽取出來，加以概括，稱為概念。在哲學(xué)中，概念被理解為由外延和內(nèi)涵兩個部分所組成的思想單元?；诟拍畹倪@一哲學(xué)思想，德國的R.Wille教授于1982年首先提出了形式概念分析理論。第1節(jié)基本理論定義1.1（形式背景）一個形式背景K=(G,M,I)由集合G、M以及它們之間的關(guān)系組成I，G的元素稱為對象(Objects)，M的元素稱為屬性(Attributes)。為了表示一個對象o和一個屬性m在關(guān)系I中，可以寫成oIm或(o,m)∈I，讀成“對象o有屬性m”。第1節(jié)基本理論第1節(jié)基本理論定義1.2（概念）對于形式背景K，在G的冪集和M的冪集之間可以定義兩個映射f和g如下：

O

G:f(O)={d|

x

O:(xId)}

D

M:g(D)={x|

d

D:(xId)}來自P(G)

P(M)的二元組(O,D)如果滿足兩個條件：O=g(D)及D=f(O)，則它被稱為是形式背景K的一個形式概念，簡稱概念，,記為C=(O,D)，其中D和O分別被稱為概念C的內(nèi)涵和外延．K的所有形式概念的集合被標(biāo)記為CS(K)．第1節(jié)基本理論定義1.3（概念格）對于概念(O1,D1)和(O2,D2)．如果D2

D1，則形式概念(O1,D1)是形式概念(O2,D2)的亞概念，記為(O1,D1)

(O2,D2)．通過這個關(guān)系，我們得到一個有序集CS(K)=(CS(K),

)，這是一個完全格，被稱為形式背景K的概念格,記為L(K)．第1節(jié)基本理論第2節(jié)概念格的生成與運算

概念格的構(gòu)造問題是形式概念分析應(yīng)用的前提。由于概念格的時空復(fù)雜度隨著形式背景的增大而可能指數(shù)性的增大，有關(guān)概念格的生成問題一直是形式概念分析應(yīng)用研究的一個重點。國內(nèi)外的學(xué)者和研究人員對此進(jìn)行了深入的研究，提出了一些有效的算法來生成概念格，這些算法一般可分為兩類：批生成算法(BatchAlgorithm)和漸進(jìn)式生成算法(IncrementalAlgorithm)。。第2節(jié)概念格的生成與運算2.1批生成方法現(xiàn)有的批處理概念格生成算法大多都是先生成形式背景所對應(yīng)的所有概念，然后再決定概念之間的亞概念－超概念連接關(guān)系。有的算法只生成所有的概念，有的算法用來產(chǎn)生其Hasse圖，也有的算法既生成所有的概念，又同時形成其Hasse圖。第2節(jié)概念格的生成與運算算法2.1概念格的批生成算法：輸入：形式背景輸出：概念格L步驟1、初始化格；步驟2、初始化隊列；步驟3、取出隊列F中的一個概念C，產(chǎn)生出它的每個子概念Cc；步驟4、如果某個子概念Cc以前沒有產(chǎn)生過，則加入到L中，加入隊列F；第2節(jié)概念格的生成與運算步驟5、增加概念C和其子概念Cc的鏈接關(guān)系；步驟6、反復(fù)步驟3~步驟5，直至隊列F為空；步驟7、輸出概念格L。第2節(jié)概念格的生成與運算2.2漸進(jìn)式生成方法GodinR.等在1995年提出的概念格生成算法是最經(jīng)典的一個漸進(jìn)式生成算法，通常稱為Godin算法。該算法從空概念格開始，通過將形式背景中的對象逐個插入概念格來實現(xiàn)對概念格的漸進(jìn)式構(gòu)造。第2節(jié)概念格的生成與運算對于每次新增一個對象，都需和已生成概念格中的概念進(jìn)行比較，這時已有的概念節(jié)點和新增的對象之間可以存在三種關(guān)系：無關(guān)概念(OldConcept)、更新概念(ModifiedConcept)和新增概念的產(chǎn)生子概念(GeneratorConcept)。漸進(jìn)式構(gòu)造主要是對更新概念和新增概念進(jìn)行不同處理后，再調(diào)整概念之間的相互關(guān)系。第2節(jié)概念格的生成與運算算法11.2概念格的漸進(jìn)式生成算法：輸入：形式背景輸出：概念格L步驟1、初始化格L為{({},M)}；步驟2、從G中取一個對象g；步驟3、對于格L中的每個概念，如果，則把g并到A1

中；第2節(jié)概念格的生成與運算步驟4、如果同時滿足：；和不存在(A1,B1)的某個父節(jié)點滿足，則要產(chǎn)生一個新節(jié)點；步驟5、對新產(chǎn)生的節(jié)點加入到L中，同時調(diào)整節(jié)點之間的鏈接關(guān)系；步驟6、反復(fù)步驟2到步驟5，直至形式背景中的對象處理結(jié)束；步驟7、輸出概念格L。第2節(jié)概念格的生成與運算2.3概念格并運算定義2.1

如果形式背景K1=(U1,A1,I1)和K2=(U2,A2,I2)滿足U1

U,U2

U,A1

A,A2

A,則稱K1和K2是同域形式背景,L(K1)和L(K2)是同域概念格.，如果K1和K2滿足U1∩U2=ф,則稱K1和K2、L(K1)和L(K2)分別是外延獨立的,簡稱獨立的。第2節(jié)概念格的生成與運算定義2.2

如果..K1=(U1,A1,I1)和K2=(U2,A2,I2)是同域且獨立的,則K1+K2=(U1∪U2,,A1∪A2,,I1∪,I2)第2節(jié)概念格的生成與運算定義2.3

對于C1=(O1,D1)和C2=(O2,D2)，如果D1=D2，則稱C1內(nèi)涵等于C2，簡稱C1等于C2第2節(jié)概念格的生成與運算定義2.4對于C1=(O1,D1)和C2=(O2,D2)，如果D1

D2，則稱C1內(nèi)涵小于C2，簡稱C1大于C2，或稱C2小于C1

第2節(jié)概念格的生成與運算定義2.5對于C1=(O1,D1),C2=(O2,D2)和C3=(O3,D3)，定義C1+C2等于C3,,如果O3=O1∪O2,,D3=D1∩D2.

第2節(jié)概念格的生成與運算定義2.6

如果L(K1)和L(K2)是兩個同域且獨立的概念格，則定義L(K1)∪L(K2)是概念格L滿足:1對于L(K1)中的任意概念C1=(O1,D1)和L(K2)中的任意概念C2=(O2,D2)，令D1∩D2=D3，如果在L(K1)中大于C1的任意概念C’1=(O’1,D’1)不存D3

D’1并且在L(K2)中大于C2的任意概念C’2=(O’2,D’2)不存D3

D’2，則C1+C2

L;2對于L(K1)中的任意概念C1,如果在L(K2)中不存在等于或小于C1的概念,則C1

L;3對于L(k2)中的任意概念C2,如果在L(K1)中不存在等于或小于C2的概念,則C2

L;4上述3種情況之外的概念不屬于L。

第2節(jié)概念格的生成與運算K1第2節(jié)概念格的生成與運算K2。

第2節(jié)概念格的生成與運算定理2.1

如果L(K1)和L(K2)是同域且獨立的概念格，則L(K1)∪L(K2)=L(K1+K2)。證明：略

第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算這里U1={123456}和U2={(1)(2)}

第2節(jié)概念格的生成與運算算法2.1

兩個同域一致概念格的縱向合并算法輸入：兩個概念格L(K1)和L(K2)

輸出：L(K1)∪L(K2)

BEGIN

FORL(K2)中每個概念按內(nèi)涵的勢的升序

DO

采用概念插入算法插入到L(K1)

ENDFOR

更新的L(K1)就是L(K1)∪L(K2)

END

第2節(jié)概念格的生成與運算2.5概念格交運算

第2節(jié)概念格的生成與運算

第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算第2節(jié)概念格的生成與運算2.6概念格的運算定律第2節(jié)概念格的生成與運算第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取概念的內(nèi)涵與事務(wù)數(shù)據(jù)庫中的項目集非常類似，而且有更嚴(yán)格的限制，因此可以在概念格上提取關(guān)聯(lián)規(guī)則，而且比直接在事務(wù)數(shù)據(jù)庫上提取有更多的優(yōu)勢。第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取1基于先輩晚輩節(jié)點對的關(guān)聯(lián)規(guī)則提取

第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取在概念格上提取規(guī)則，我們可以只關(guān)心那些外延對象數(shù)大于等于支持度閾值的節(jié)點，并且只關(guān)心晚輩外延對象個數(shù)與先輩外延對象個數(shù)的比值大于等于可信度閾值的節(jié)點對。第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取當(dāng)支持度閾值

和可信度閾值

確定之后，如果它們對于任何節(jié)點都是統(tǒng)一的，則有下面定理。第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取例1.3

對于下圖中的形式背景和概念格，規(guī)定支持度閾值

=0.4和可信度閾值

=0.66，則符合閾值條件的節(jié)點序列#2#4#8、#5#8和#6#8,只考慮每個序列兩端的節(jié)點對，即考慮#2#8、#5#8和#6#8，得規(guī)則第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取2基于內(nèi)涵縮減的蘊(yùn)含規(guī)則提取定義1.16（內(nèi)涵縮減）對于給定的概念C=(A,B)，如果屬性集合R滿足下述兩個條件則它R被稱為是C的一個內(nèi)涵縮減。如果。則稱是真內(nèi)涵縮減。第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取如果概念C有真內(nèi)涵縮減R，則它對應(yīng)的蘊(yùn)含規(guī)則集為第3節(jié)概念格上的關(guān)聯(lián)規(guī)則提取例4在例3中形式背景所對應(yīng)的概念格中，對于每個概念，我們將以此計算出其蘊(yùn)含集：概念#2的內(nèi)涵為{be)，它具有2個真內(nèi)涵縮減和{e}，因此。概念#3的內(nèi)涵為，其內(nèi)涵縮減也是，這并非真內(nèi)涵縮減，因此無規(guī)則需要生成。概念#4的內(nèi)涵為{bce}，它具有2個真內(nèi)涵縮減{bc}和{ce}，因此。第4節(jié)模糊概念格在這方面，國外已有了一些研究成果。例如Wolff(1998)提出了一種基于模糊信息的表示法，將傳統(tǒng)的形式背景中的屬性用模糊語言變量值表示，依據(jù)標(biāo)度分類形式背景的對象，構(gòu)造基于標(biāo)度的格。Burusco和Fuentes(1994)討論了L-模糊概念集合的格結(jié)構(gòu)，并給出了一個計算這種格的方法。第4節(jié)模糊概念格1一種模糊概念格模型第4節(jié)模糊概念格第4節(jié)模糊概念格第4節(jié)模糊概念格第4節(jié)模糊概念格第4節(jié)模糊概念格第4節(jié)模糊概念格第4節(jié)模糊概念格2模糊概念格漸進(jìn)式生成為了能夠用漸進(jìn)式方法計算模糊參數(shù)σ和λ，在格的構(gòu)造算法中，分別引進(jìn)中間參數(shù)kd和hd。第4節(jié)模糊概念格第4節(jié)模糊概念格算法1.5模糊概念格的漸進(jìn)式生成算法：輸入：模糊形式背景輸出：模糊概念格L步驟1、初始化格L為{({},M)}，初始節(jié)點中kd=0,hd=0；步驟2、從G中取一個對象g；步驟3、對于格L的每個概念，如果，則把g并到A1

中；對Ｂ1中的每個d第4節(jié)模糊概念格步驟4、如果Ｃ1同時滿足：；和不存在(A1,B1)的