形式概念分析

形式概念分析

劉宗田

上海大學計算機學院,200072

ztliu@第1節(jié)基本理論人類在認知過程中，把所感覺到的具有共同特點的事物抽取出來，加以概括，稱為概念。在哲學中，概念被理解為由外延和內涵兩個部分所組成的思想單元?；诟拍畹倪@一哲學思想，德國的R.Wille教授于1982年首先提出了形式概念分析理論。第1節(jié)基本理論定義1.1（形式背景）一個形式背景K=(G,M,I)由集合G、M以及它們之間的關系組成I，G的元素稱為對象(Objects)，M的元素稱為屬性(Attributes)。為了表示一個對象o和一個屬性m在關系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的內涵和外延．K的所有形式概念的集合被標記為CS(K)．第1節(jié)基本理論定義1.3（概念格）對于概念(O1,D1)和(O2,D2)．如果D2

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

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

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

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

中；第2節(jié)概念格的生成與運算步驟4、如果同時滿足：；和不存在(A1,B1)的某個父節(jié)點滿足，則要產生一個新節(jié)點；步驟5、對新產生的節(jié)點加入到L中，同時調整節(jié)點之間的鏈接關系；步驟6、反復步驟2到步驟5，直至形式背景中的對象處理結束；步驟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內涵等于C2，簡稱C1等于C2第2節(jié)概念格的生成與運算定義2.4對于C1=(O1,D1)和C2=(O2,D2)，如果D1

D2，則稱C1內涵小于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)中每個概念按內涵的勢的升序

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é)概念格上的關聯(lián)規(guī)則提取概念的內涵與事務數據庫中的項目集非常類似，而且有更嚴格的限制，因此可以在概念格上提取關聯(lián)規(guī)則，而且比直接在事務數據庫上提取有更多的優(yōu)勢。第3節(jié)概念格上的關聯(lián)規(guī)則提取1基于先輩晚輩節(jié)點對的關聯(lián)規(guī)則提取

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

和可信度閾值

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

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