形式概念分析

形式概念分析

劉宗田

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

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

O

G:f(O)={d|

x

O:(xId)}

D

M:g(D)={x|

d

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

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

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

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

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

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

中；第2節(jié)概念格的生成與運(yùn)算步驟4、如果同時(shí)滿足：；和不存在(A1,B1)的某個(gè)父節(jié)點(diǎn)滿足，則要產(chǎn)生一個(gè)新節(jié)點(diǎn)；步驟5、對(duì)新產(chǎn)生的節(jié)點(diǎn)加入到L中，同時(shí)調(diào)整節(jié)點(diǎn)之間的鏈接關(guān)系；步驟6、反復(fù)步驟2到步驟5，直至形式背景中的對(duì)象處理結(jié)束；步驟7、輸出概念格L。第2節(jié)概念格的生成與運(yùn)算2.3概念格并運(yùn)算定義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)分別是外延獨(dú)立的,簡(jiǎn)稱獨(dú)立的。第2節(jié)概念格的生成與運(yùn)算定義2.2

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

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

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

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

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

如果L(K1)和L(K2)是兩個(gè)同域且獨(dú)立的概念格，則定義L(K1)∪L(K2)是概念格L滿足:1對(duì)于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對(duì)于L(K1)中的任意概念C1,如果在L(K2)中不存在等于或小于C1的概念,則C1

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

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

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

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

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

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

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

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

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

BEGIN

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

DO

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

ENDFOR

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

END

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

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

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

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

和可信度閾值

確定之后，如果它們對(duì)于任何節(jié)點(diǎn)都是統(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

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

=0.4和可信度閾值

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

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