胡小康,王俊紅
(山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006)
?
基于相容模糊概念的規(guī)則提取方法
胡小康,王俊紅
(山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006)
摘要:概念格是具有嚴(yán)格數(shù)學(xué)模型的數(shù)據(jù)分析與規(guī)則提取的一種有效工具,大部分情況下是在完備的精確形式背景即二值背景下進行研究,然而在現(xiàn)實生活中遇到的大多數(shù)情況是不完備的模糊形式背景,不完備模糊形式背景中包含許多不確定的信息,其上的知識表示與完備形式背景下的知識表示既有區(qū)別又有聯(lián)系。為了研究兩者的內(nèi)在聯(lián)系,本文定義了相似模糊概念和相容模糊概念,構(gòu)建了相似模糊概念格和建立了在不完備模糊形式背景下相容模糊概念之間的偏序關(guān)系,進而設(shè)計出面向不完備模糊形式背景下的關(guān)聯(lián)規(guī)則挖掘算法.最后通過實驗驗證了該方法的有效性和可行性。
關(guān)鍵詞:形式背景;概念格;相似模糊概念;相容模糊概念;知識獲??;關(guān)聯(lián)規(guī)則;偏序關(guān)系;相容關(guān)系
概念格也稱為Galois格,又叫做形式概念分析,由德國的Wille[1]在20世紀(jì)80年代提出。概念格的每個節(jié)點是一個形式概念,概念格結(jié)構(gòu)模型是形式概念分析中的核心結(jié)構(gòu),它描述了對象和屬性之間的關(guān)系。概念格是研究知識表示和推理的理論,它具有嚴(yán)格的數(shù)學(xué)模型,已經(jīng)在機器學(xué)習(xí)、數(shù)據(jù)挖掘、軟件工程等領(lǐng)域[2-6]得到廣泛的應(yīng)用。
通常我們研究的形式背景是完備的,也就是對象和屬性之間的關(guān)系是已知的,但是在實際應(yīng)用中,大多數(shù)信息是模糊[7]的、復(fù)雜的。更糟糕的是在現(xiàn)實生活中由于人的認(rèn)知能力以及機器的局限性,人們經(jīng)常不能準(zhǔn)確地判斷對象和屬性之間的關(guān)系,使得獲取的形式背景經(jīng)常存在數(shù)據(jù)缺失,從而得到形式背景是不完備的模糊形式背景,這對于知識獲取產(chǎn)生了很大障礙。因此不完備模糊形式背景的研究獲得了廣泛的關(guān)注。
粗糙集理論中的信息系統(tǒng)就是形式概念分析中的形式背景,對于不完備信息系統(tǒng)[8],粗糙集已通過相容關(guān)系、非對稱相似關(guān)系等進行了一些研究。在形式概念分析中Liu J等在文獻[9]中將多值形式背景轉(zhuǎn)變?yōu)閱沃敌问奖尘昂?,通過把不完備屬性在不同對象上的不同取值進行擴展,從而得到了完備的形式背景來進行概念的提取。Dubois D等在文獻[10]提出了利用概率論來解決不完備形式背景的方法。Krupka M等在文獻[11]中定義了不完備的模糊形式背景,然后提出了在不完備模糊形式背景下構(gòu)建概念格的方法。Djouadi Y等在文獻[12] 中將不完備模糊形式背景中的隸屬度值均采用區(qū)間值來表示,將不完備模糊形式背景轉(zhuǎn)化為區(qū)間值模糊形式背景(interval-valued fuzzy formal concept,IVFF),在此基礎(chǔ)上提出了基于區(qū)間值形式背景的概念格構(gòu)建方法。Li J H等在文獻[13]中提出了在不完備形式背景下構(gòu)建相似概念格的方法,此外基于相似概念格還研究了在不完備的決策形式背景下獲取規(guī)則的方法。上述研究中,無論是將不完備形式背景轉(zhuǎn)化為區(qū)間值形式背景,還是對不完備屬性進行擴展來構(gòu)造概念格的方法,僅僅適用于形式背景中數(shù)據(jù)量缺失較少的情況。當(dāng)形式背景中數(shù)據(jù)缺失量較大時,所構(gòu)造的概念格中包含有大量不確定的信息,這對知識獲取造成了很大影響。
本文為了減少形式背景中數(shù)據(jù)缺失量對知識獲取的影響,提出并定義了相似模糊概念和相容模糊概念并給出了相容模糊概念的構(gòu)建方法,建立了相容模糊概念之間的偏序關(guān)系,進而設(shè)計面向模糊不完備信息的關(guān)聯(lián)規(guī)則挖掘算法。
1基本概念
1.1形式概念分析
定義1[1]一個形式背景K=(G,M,I)是一個三元組 ,其中G是對象集合,M是屬性集合,I是G與M之間的一個二元關(guān)系gIm或(g,m)∈I,表示對象g具有屬性m。在形式背景中定義式(1)和式(2):
(1)
(2)
表1 形式背景
1){?,(a,b,c,d)};
2){(x1),(a,d)};
3){(x3),(a,c)};
4){(x2),(b,c)};
5){(x1,x3),(a)};
6){(x2,x3,x4),(c)};
7){(x1,x2,x3,x4),?}。
圖1 表1對應(yīng)概念格的Hasse圖Fig.1 Hasse diagram of table 1
1.2模糊形式概念
定義3[14]一個模糊形式背景是一個三元組(G′,M′,I′),其中G′是對象的有限集,M′是屬性有限集,I′是G′×M′的模糊集合。(g,m)∈I′有一個隸屬度值u(g,m)∈[0,1] 。
定義4[14]給定一個模糊形式背景K′={G′,M′,I′=φ(G′×M′)}和一個置信度閾值T=[t1,t2],在形式背景中定義式(3)與式(4):
(3)
式中A?G′。
(4)
式中B?M′。
模糊形式背景(G′,M′,I′)同置信度閾值T下的一個二元組(A,B)(A?G′,B?M′)是模糊形式概念,當(dāng)且僅當(dāng)FA(A)=B與FO(B)=A同時成立。A、B分別叫做模糊形式背景的模糊外延和模糊內(nèi)涵。
定義5[14](A1,B1)和(A2,B2)是形式背景(G′,M′,I′)的兩個模糊概念。(A1,B1)是(A2,B2)的子概念,記作(A1,B1)≤(A2,B2),當(dāng)且僅當(dāng)A1?A2(?B2?B1)。
目前所研究的形式背景是完備的,換句話講,此時對象或者具有某屬性,或者不具有某屬性,他們之間的關(guān)系是確定的。數(shù)據(jù)缺失現(xiàn)象在生活中普遍存在。例如,對一些突發(fā)事件,并沒有該事件的完整記錄;再如病人突發(fā)疾病,而不能對病人進行全面檢查,然后來制定相應(yīng)的治療方案。下面給出一個例子來說明,表2是醫(yī)生診斷表,即為不完備模糊形式背景,其中o1、o2、o3、o4表示病人編號,組成對象集G′。a、b、c、d、e、f表示病人的癥狀,其代表為頭痛、血壓、惡心、食欲不振、咳嗽、乏力,組成屬性集M′。用*來表示缺失數(shù)據(jù),但是這些數(shù)據(jù)是客觀存在的。
表2 初始模糊形式背景
表3 置信度閾值為T的模糊形式背景
2相似模糊概念與相容模糊概念
在形式概念分析中,對不完備形式背景進行完備化處理,一般可采用以下3種方法。
1)刪除法。刪除法即刪除形式背景中缺失數(shù)據(jù)的一列或者一行,也就是刪除一個對象或者刪除一個屬性。這類方法操作起來比較簡單,但是在刪除過程中會導(dǎo)致原先存在的數(shù)據(jù)缺失,可能會造成獲取的知識不準(zhǔn)確。
2)填補法。填補法就是對不完備形式背景中缺失的數(shù)據(jù)填充為1或者0,使之補全為一個完備的形式背景。這類方法比較簡單,但是容易造成獲取的知識錯誤,因為好多缺失信息都是人為地填充0或者1。
3)擴展屬性法[15]。擴展屬性法即把原有不完備形式背景下的屬性集合中的屬性分為完備和不完備屬性兩部分,然后將不完備屬性在不同對象的不同取值進行擴展,從而把不完備形式背景補充完整。此方法的好處是既不會增加知識也不會缺失知識,但是增加了知識獲取的時間和空間復(fù)雜度。
定義6在不完備模糊形式背景Kc=(G′,M′,IM) 中,對于集合A∈G′,記作:
(5)
式中A∈G′。
(6)
式中B?M′。
(7)
(8)
(9)
(10)
(11)
(12)
相似模糊概念與相容模糊概念既有區(qū)別也有聯(lián)系,在經(jīng)典的不完備形式背景中“補全法”將缺失數(shù)據(jù)補充為1,而在不完備的模糊形式背景中,相似模糊概念是將不完備模糊形式背景中的缺失數(shù)據(jù)補充為0.5得到的。而相容模糊概念是對相似模糊概念的擴展,它是在相似模糊概念基礎(chǔ)上通過設(shè)置參數(shù)(α,β),去除一些數(shù)據(jù)量缺失較大的相似模糊概念而得到的。根據(jù)定義6和定義7以及傳統(tǒng)的概念獲取算法[16],可以得出相似模糊概念和相容模糊概念的構(gòu)造算法,具體算法步驟參考算法1與算法2。
算法1在不完備形式背景Kc中,相似模糊概念的構(gòu)造算法。
2)獲得第一個概念(FO(M),M)設(shè)置概念的隸屬度值并加入w(Kc)中。
3)遍歷對象g,其中g(shù)∈G,如果遍歷完成轉(zhuǎn)到6),反之轉(zhuǎn)到4)。
算法2在不完備形式背景Kc中,相容模糊概念的獲取算法。
2)如果相似模糊概念都被進行計算過,則輸出相容模糊概念轉(zhuǎn)到3),反之再進行1)。
3基于相容模糊概念的規(guī)則提取
關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘中最活躍的研究方法之一[17-21]。規(guī)則就是形如“如果…那么…(If…Then…)”前者為條件,后者為結(jié)果。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的購物籃數(shù)據(jù)進行分析,例如最著名的案例就是啤酒與尿布。
對于關(guān)聯(lián)規(guī)則A?B的支持度是supp(A?B)=|FO(A∪B)|/|U|,置信度為conf(A?B)>β關(guān)聯(lián)規(guī)則A?B被稱為關(guān)于(ω,τ)關(guān)聯(lián)規(guī)則,當(dāng)supp(A?B)>ω時把A∪B稱為頻繁的。
在不完備的模糊背景下,規(guī)則提取是一件比較困難的工作,在之前的工作中已經(jīng)獲得了相似模糊概念和相容模糊概念,然后根據(jù)算法3構(gòu)造好相似模糊概念格,但是由于相似模糊概念中有許多不確定性信息,所以構(gòu)造的相似模糊概念格也是不準(zhǔn)確的。通過對相似模糊概念的篩選,最后得到了較為準(zhǔn)確的相容模糊概念,可以在構(gòu)造好的相似模糊概念格基礎(chǔ)上得到相容模糊概念的之間的偏序關(guān)系,從而可以提取出可信度較高的關(guān)聯(lián)規(guī)則,具體算法參考算法4。
算法3相似模糊概念格的構(gòu)造算法。
輸出相似模糊概念格。
2)遍歷屬性m,其中m∈M,并求得A與FO(m)交集I。如果遍歷結(jié)束轉(zhuǎn)到1),否則轉(zhuǎn)到3)。
4)輸出相似模糊概念格,算法結(jié)束。
算法4不完備形式背景下規(guī)則提取的算法。
輸出關(guān)聯(lián)規(guī)則∑。
1)對相似模糊概念格進行處理,除去相容模糊概念之外的概念,更新父節(jié)點和子節(jié)點。
4)輸出∑。
在得到提取規(guī)則∑后,可以給其支持度閾值ω與置信度閾值τ。然后根據(jù)需要從提取的規(guī)則中篩選出符合要求的規(guī)則。
4示例展示
現(xiàn)在舉例來展示規(guī)則提取的過程,在表3中討論的置信度閾值是T=[0.5,1],通過算法1,可以得出在表3的不完備模糊背景下形成的相似模糊概念為
1){?,(a,b,c,d,e,f)};
2){(0.6/o1),(a,c,d,e,f)};
3){(0.5/o2),(a,b,c,e,f)};
4){(0.61/o1,0.5/o2),(a,c,e,f)};
5){(0.5/o3),(b,c,d,e,f)};
6){(0.6/o1,0.5/o3),(c,d,e,f)};
7){(0.5/o2,0.5/o3),(b,c,e,f)};
8){(0.61/o1,0.5/o2,0.6/o3),(c,e,f)}.;
9){(0.5/o4),(a,b,d,e)};
10){(0.6/o1,0.5/o4),(a,d,e)};
11){(0.7/o2,0.5/o4),(a,b,e)};
12){(0.8/o1,0.7/o2,0.5/o4),(a,e)};
13){(0.5/o3,0.5/o4),(b,d,e)};
14){(0.6/o1,0.5/o3,0.5/o4),(d,e)};
15){(0.7/o2,0.5/o3,0.5/o4),(b,e)};
16){(o1,o2,o3,o4),(0/a,0/b,0/c,0/d,0.5/e,0/f)}。
圖2 相似模糊概念的相似模糊概念格Fig.2 Approximat fuzzy concept lattice
1){0.6/(o1),(a,c,d,e,f)};
2){0.5/(o2),(a,b,c,e,f)};
3){0.57/(o1,o2,o3),(c,e,f)};
4){0.55/(o1,o4),(a,d,e)};
5){0.6/(o2,o4),(a,d,e)};
6){0.667/(o1,o2,o4),(a,e)};
7){0.083/(o1,o2,o3,o4),(c)}。
根據(jù)算法4可以得出閾值τ為0.9,置信度閾值為0.5的關(guān)聯(lián)規(guī)則:
1){a,d,e}?{c,f}置信度為0.5。
解釋:如果頭疼、食欲不振、咳嗽則惡心、乏力。
2){a,e}?置信度為0.67。
解釋:如果頭疼、咳嗽則血壓會高。
5實驗結(jié)果與分析
本文基于相容模糊概念的關(guān)聯(lián)規(guī)則提取可分為在不完備模糊形式背景中相容模糊概念的構(gòu)造過程和根據(jù)相容模糊概念的偏序關(guān)系進行提取規(guī)則的過程。本文算法在Win7環(huán)境下用MATLAB來實現(xiàn),并在UCI數(shù)據(jù)庫的water數(shù)據(jù)集(526個對象,38個屬性)進行實驗。實驗主要對2個指標(biāo)進行測量:第1個是在不完備模糊形式背景下相似模糊概念數(shù)目與對象數(shù)目以及相容模糊概念與對象數(shù)目之間的關(guān)系;第2個是提取的關(guān)聯(lián)規(guī)則數(shù)目與對象數(shù)目之間的關(guān)系。在本實驗中針對不完備模糊形式背景,設(shè)定相容模糊參數(shù)為(α=0.8,β=0.9),關(guān)聯(lián)規(guī)則的置信度閾值為0.8。在不完備形式背景下相似模糊概念與相容模糊概念的數(shù)量關(guān)系可由圖3體現(xiàn),圖4則體現(xiàn)了對象數(shù)目與關(guān)聯(lián)規(guī)則數(shù)量之間的關(guān)系。圖3與圖4都在相容模糊參數(shù)與屬性數(shù)量都不變的情況下,取water數(shù)據(jù)集中的前200個對象進行測量。圖3與圖4中橫坐標(biāo)都表示對象的數(shù)量,初始為0,分別一次遞增50與10進行測試。圖3縱坐標(biāo)表示由不完備形式背景形成概念的數(shù)量,圖4縱坐標(biāo)表示由相容模糊概念獲得的關(guān)聯(lián)規(guī)則的數(shù)量。通過圖3、4的實驗結(jié)果可以觀察到,在不完備模糊形式背景中隨著對象數(shù)目的增多,通過本算法獲得知識準(zhǔn)確性與傳統(tǒng)的方法相比具有一定的優(yōu)勢。
圖3 對象與概念個數(shù)關(guān)系Fig.3 Relationship between object and concept
圖4 對象與關(guān)聯(lián)規(guī)則個數(shù)關(guān)系Fig.4 Relationship between object and association rule
6結(jié)束語
目前在不完備模糊形式背景下的研究越來越多。本文結(jié)合在傳統(tǒng)的不完備形式背景下獲取概念的方法,提出了在不完備模糊形式背景中提取出相容模糊概念,并根據(jù)相似模糊概念格提取出相容規(guī)則的方法。實驗表明,該方法可以有效的降低形式背景中因數(shù)據(jù)缺失和數(shù)據(jù)的模糊性對獲取知識準(zhǔn)確性帶來的的影響。未來的工作還需要改進和細(xì)化文中的一些算法,例如如何在知識庫分類能力保持不變的情況下刪除不相關(guān)的冗余屬性;如何把模糊概念格與粗糙集理論有效結(jié)合以解決不確定規(guī)則提取中的規(guī)則冗余性等問題。
參考文獻:
[1]WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered sets. Netherlands: Springer, 1982: 445-470.
[2]POELMANS J, IGNATOV D I, KUZNETSOV S O, et al. Formal concept analysis in knowledge processing: a survey on applications[J]. Expert systems with applications, 2013, 40(16): 6538-6560.
[3]MINEAU G W, GODIN R. Automatic structuring of knowledge bases by conceptual clustering[J]. IEEE transactions on knowledge and data engineering, 1995, 7(5): 824-829.
[4]COLE R, EKLUND P W. Scalability in formal concept analysis[J]. Computational intelligence, 1999, 15(1): 11-27.
[5]CARPINETO C, ROMANO G. A lattice conceptual clustering system and its application to browsing retrieval[J]. Machine learning, 1996, 24(2): 95-122.
[6]MA Jianmin, ZHANG Wenxiu. Axiomatic characterizations of dual concept lattices[J]. International journal of approximate reasoning, 2013, 54(5): 690-697.
[7]胡明涵, 張莉, 任飛亮. 模糊形式概念分析與模糊概念格[J]. 東北大學(xué)學(xué)報:自然科學(xué)版, 2007, 28(9): 1274-1277.
HU Minghan, ZHANG Li, REN Feiliang. Fuzzy formal concept analysis and fuzzy concept lattices[J]. Journal of northeastern university : natural science, 2007, 28(9): 1274-1277.
[8]GRZYMALA-BUSSE J W. Rough set approach to incomplete data[C]//Proceedings of the 7th international conference on artificial intelligence and soft computing-ICAISC 2004. Berlin Heidelberg, Germany, 2004: 50-55.
[9]LIU Jun, YAO Xiaoqiu. Formal concept analysis of incomplete information system[C]//Proceedings of the 7th international conference on fuzzy systems and knowledge discovery. Yantai, China, 2010, 5: 2016-2020.
[10]DJOUADI Y, DUBOIS D, PRADE H. Possibility theory and formal concept analysis: Context decomposition and uncertainty handling[C]//Proceedings of the 13th international conference on information processing and management of uncertainty. Berlin Heidelberg, Germany, 2010: 260-269.
[11]KRUPKA M. Fuzzy concept lattices with incomplete knowledge[C]//Proceedings of the 14th international conference on information processing and management of uncertainty in knowledge-based systems. Berlin Heidelberg, Germany, 2012: 171-180.
[12]DJOUADI Y, PRADE H. Interval-valued fuzzy formal concept analysis[C]//Proceedings of the 18th international symposium. Berlin Heidelberg, Germany, 2009: 592-601.
[13]LI Jinhai, MEI Changlin, LV Yuejin. Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction[J]. International journal of approximate reasoning, 2013, 54(1): 149-165.
[14]LAI Hongliang, ZHANG Dexue. Concept lattices of fuzzy contexts: formal concept analysis vs. rough set theory[J]. International journal of approximate reasoning, 2009, 50(5): 695-707.
[15]何淑賢, 王育紅, 翟巖慧, 等. 不完備形式背景及其完備化方法[J]. 山西大學(xué)學(xué)報:自然科學(xué)版, 2006, 29(4): 364-367.
HE Shuxian, WANG Yuhong, ZHAI Yanhui, et al. Incomplete formal context and the completion approach[J]. Journal of Shanxi university : natural science edition, 2006, 29(4): 364-367.
[16]謝志鵬, 劉宗田. 概念格的快速漸進式構(gòu)造算法[J]. 計算機學(xué)報, 2002, 25(5): 490-496.
XIE Zhipeng, LIU Zongtian. A fast incremental algorithm for building concept lattice[J]. Chinese journal of computers, 2002, 25(5): 490-496.
[17]梁吉業(yè), 王俊紅. 基于概念格的規(guī)則產(chǎn)生集挖掘算法[J]. 計算機研究與發(fā)展, 2004, 41(8): 1339-1344.
LIANG Jiye, WANG Junhong. An algorithm for extracting rule-generating sets based on concept lattice[J]. Journal of computer research and development, 2004, 41(8): 1339-1344.
[18]LEKHA A, SRIKRISHNA C V, VINOD V. Fuzzy association rule mining[J]. Journal of computer science, 2015, 11(1): 71-74.
[19]LAKHAL L, STUMME G. Efficient mining of association rules based on formal concept analysis[M]//GANTER B, STUMME G, WILLE R. Formal concept analysis. Berlin Heidelberg: Springer-Verlag, 2005: 180-195.
[20]KUMAR CH A, DIAS S M, VIEIRA N J. Knowledge reduction in formal contexts using non-negative matrix factorization[J]. Mathematics and computers in simulation, 2015, 109: 46-63.
[21]王志海, 胡可云, 胡學(xué)綱, 等. 概念格上規(guī)則提取的一般算法與漸進式算法[J]. 計算機學(xué)報, 1991, 22(1): 66-70.
WANG Zhihai, HU Keyun, HU Xuegang, et al. General and incremental algorithms of rule extraction based on concept lattice[J]. Chinese journal of computers, 1991, 22(1): 66-70.
胡小康,男,1991年生,碩士研究生,主要研究方向為形式概念分析、數(shù)據(jù)挖掘。
王俊紅,女,1979年生,副教授,主要研究方向形式概念分析、粗糙集和數(shù)據(jù)挖掘。主持或參與多項國家863計劃、國家自然科學(xué)基金和省部級等科研項目。發(fā)表學(xué)術(shù)論文10余篇。
中文引用格式:胡小康,王俊紅.基于相容模糊概念的規(guī)則提取方法[J]. 智能系統(tǒng)學(xué)報, 2016, 11(3): 352-358.
英文引用格式:HU Xiaokang, WANG Junhong. Research on rule extraction method based on compatibility fuzzy concept[J]. CAAI transactions on intelligent systems, 2016,11(3): 352-358.
Research on rule extraction method based on compatibility fuzzy concept
HU Xiaokang, WANG Junhong
(School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China)
Abstract:The concept lattice is an effective data analysis and rule extraction tool with a strict mathematical model. In most instances, studies are carried out in a complete formal context, i.e., a two-value context. However, in real life, an incomplete fuzzy formal context is frequently experienced. Incomplete fuzzy contexts contain a lot of uncertain information. There are both distinctions and relationships that can be identified between the forms of knowledge representation in the incomplete fuzzy formal and complete formal contexts. To study their internal relationship, in this paper, we define approximate fuzzy and compatible fuzzy concepts, establish an approximate fuzzy concept lattice, and identify a partial ordering relationship between compatible fuzzy concepts in an incomplete fuzzy formal context. We extend the design of an association rules mining algorithm to address the background of the incomplete fuzzy formal context, and conduct an experiment to demonstrate the feasibility and effectiveness of the proposed method.
Keywords:formal context; concept lattice; approximate fuzzy concept; compatible fuzzy concept; knowledge representation; association rules; partial ordering relation; compatible relation
作者簡介:
中圖分類號:TP18
文獻標(biāo)志碼:A
文章編號:1673-4785(2016)03-0352-07
通信作者:王俊紅.E-mail:wjhwjh@sxu.edu.cn.
基金項目:國家自然科學(xué)基金項目(61202018,61303008,61305057).
收稿日期:2016-03-19.網(wǎng)絡(luò)出版日期:2016-05-13.
DOI:10.11992/tis.201603043
網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0925.026.html