基于相容模糊概念的規則提取方法

胡小康，王俊紅

(山西大學 計算機與信息技術學院，山西 太原 030006)

?

基于相容模糊概念的規則提取方法

胡小康，王俊紅

(山西大學 計算機與信息技術學院，山西 太原 030006)

摘要：概念格是具有嚴格數學模型的數據分析與規則提取的一種有效工具，大部分情況下是在完備的精確形式背景即二值背景下進行研究,然而在現實生活中遇到的大多數情況是不完備的模糊形式背景，不完備模糊形式背景中包含許多不確定的信息，其上的知識表示與完備形式背景下的知識表示既有區別又有聯系。為了研究兩者的內在聯系，本文定義了相似模糊概念和相容模糊概念,構建了相似模糊概念格和建立了在不完備模糊形式背景下相容模糊概念之間的偏序關系，進而設計出面向不完備模糊形式背景下的關聯規則挖掘算法.最后通過實驗驗證了該方法的有效性和可行性。

關鍵詞：形式背景；概念格；相似模糊概念；相容模糊概念；知識獲取；關聯規則；偏序關系；相容關系

概念格也稱為Galois格，又叫做形式概念分析，由德國的Wille[1]在20世紀80年代提出。概念格的每個節點是一個形式概念，概念格結構模型是形式概念分析中的核心結構，它描述了對象和屬性之間的關系。概念格是研究知識表示和推理的理論，它具有嚴格的數學模型，已經在機器學習、數據挖掘、軟件工程等領域[2-6]得到廣泛的應用。

通常我們研究的形式背景是完備的，也就是對象和屬性之間的關系是已知的，但是在實際應用中，大多數信息是模糊[7]的、復雜的。更糟糕的是在現實生活中由于人的認知能力以及機器的局限性，人們經常不能準確地判斷對象和屬性之間的關系，使得獲取的形式背景經常存在數據缺失，從而得到形式背景是不完備的模糊形式背景，這對于知識獲取產生了很大障礙。因此不完備模糊形式背景的研究獲得了廣泛的關注。

粗糙集理論中的信息系統就是形式概念分析中的形式背景，對于不完備信息系統[8]，粗糙集已通過相容關系、非對稱相似關系等進行了一些研究。在形式概念分析中Liu J等在文獻[9]中將多值形式背景轉變為單值形式背景后，通過把不完備屬性在不同對象上的不同取值進行擴展，從而得到了完備的形式背景來進行概念的提取。Dubois D等在文獻[10]提出了利用概率論來解決不完備形式背景的方法。Krupka M等在文獻[11]中定義了不完備的模糊形式背景，然后提出了在不完備模糊形式背景下構建概念格的方法。Djouadi Y等在文獻[12] 中將不完備模糊形式背景中的隸屬度值均采用區間值來表示，將不完備模糊形式背景轉化為區間值模糊形式背景(interval-valued fuzzy formal concept,IVFF)，在此基礎上提出了基于區間值形式背景的概念格構建方法。Li J H等在文獻[13]中提出了在不完備形式背景下構建相似概念格的方法，此外基于相似概念格還研究了在不完備的決策形式背景下獲取規則的方法。上述研究中，無論是將不完備形式背景轉化為區間值形式背景，還是對不完備屬性進行擴展來構造概念格的方法，僅僅適用于形式背景中數據量缺失較少的情況。當形式背景中數據缺失量較大時，所構造的概念格中包含有大量不確定的信息，這對知識獲取造成了很大影響。

本文為了減少形式背景中數據缺失量對知識獲取的影響，提出并定義了相似模糊概念和相容模糊概念并給出了相容模糊概念的構建方法，建立了相容模糊概念之間的偏序關系，進而設計面向模糊不完備信息的關聯規則挖掘算法。

1基本概念

1.1形式概念分析

定義1[1]一個形式背景K=(G,M,I)是一個三元組 ，其中G是對象集合，M是屬性集合，I是G與M之間的一個二元關系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對應概念格的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′)是模糊形式概念，當且僅當FA(A)=B與FO(B)=A同時成立。A、B分別叫做模糊形式背景的模糊外延和模糊內涵。

定義5[14](A1,B1)和(A2,B2)是形式背景(G′,M′,I′)的兩個模糊概念。(A1,B1)是(A2,B2)的子概念，記作(A1,B1)≤(A2,B2)，當且僅當A1?A2(?B2?B1)。

目前所研究的形式背景是完備的，換句話講，此時對象或者具有某屬性，或者不具有某屬性，他們之間的關系是確定的。數據缺失現象在生活中普遍存在。例如，對一些突發事件，并沒有該事件的完整記錄；再如病人突發疾病，而不能對病人進行全面檢查，然后來制定相應的治療方案。下面給出一個例子來說明，表2是醫生診斷表，即為不完備模糊形式背景，其中o1、o2、o3、o4表示病人編號，組成對象集G′。a、b、c、d、e、f表示病人的癥狀，其代表為頭痛、血壓、惡心、食欲不振、咳嗽、乏力，組成屬性集M′。用*來表示缺失數據，但是這些數據是客觀存在的。

表2　初始模糊形式背景

表3　置信度閾值為T的模糊形式背景

2相似模糊概念與相容模糊概念

在形式概念分析中，對不完備形式背景進行完備化處理，一般可采用以下3種方法。

1)刪除法。刪除法即刪除形式背景中缺失數據的一列或者一行，也就是刪除一個對象或者刪除一個屬性。這類方法操作起來比較簡單，但是在刪除過程中會導致原先存在的數據缺失，可能會造成獲取的知識不準確。

2)填補法。填補法就是對不完備形式背景中缺失的數據填充為1或者0，使之補全為一個完備的形式背景。這類方法比較簡單，但是容易造成獲取的知識錯誤，因為好多缺失信息都是人為地填充0或者1。

3)擴展屬性法[15]。擴展屬性法即把原有不完備形式背景下的屬性集合中的屬性分為完備和不完備屬性兩部分，然后將不完備屬性在不同對象的不同取值進行擴展，從而把不完備形式背景補充完整。此方法的好處是既不會增加知識也不會缺失知識，但是增加了知識獲取的時間和空間復雜度。

定義6在不完備模糊形式背景Kc=(G′,M′,IM) 中，對于集合A∈G′，記作：

(5)

式中A∈G′。

(6)

式中B?M′。

(7)

(8)

(9)

(10)

(11)

(12)

相似模糊概念與相容模糊概念既有區別也有聯系，在經典的不完備形式背景中“補全法”將缺失數據補充為1，而在不完備的模糊形式背景中，相似模糊概念是將不完備模糊形式背景中的缺失數據補充為0.5得到的。而相容模糊概念是對相似模糊概念的擴展，它是在相似模糊概念基礎上通過設置參數(α,β)，去除一些數據量缺失較大的相似模糊概念而得到的。根據定義6和定義7以及傳統的概念獲取算法[16],可以得出相似模糊概念和相容模糊概念的構造算法，具體算法步驟參考算法1與算法2。

算法1在不完備形式背景Kc中，相似模糊概念的構造算法。

2)獲得第一個概念(FO(M),M)設置概念的隸屬度值并加入w(Kc)中。

3)遍歷對象g，其中g∈G，如果遍歷完成轉到6)，反之轉到4)。

算法2在不完備形式背景Kc中，相容模糊概念的獲取算法。

2)如果相似模糊概念都被進行計算過，則輸出相容模糊概念轉到3)，反之再進行1)。

3基于相容模糊概念的規則提取

關聯規則數據挖掘中最活躍的研究方法之一[17-21]。規則就是形如“如果…那么…(If…Then…)”前者為條件，后者為結果。典型的關聯規則發現問題是對超市中的購物籃數據進行分析，例如最著名的案例就是啤酒與尿布。

對于關聯規則A?B的支持度是supp(A?B)=|FO(A∪B)|/|U|，置信度為conf(A?B)>β關聯規則A?B被稱為關于(ω,τ)關聯規則，當supp(A?B)>ω時把A∪B稱為頻繁的。

在不完備的模糊背景下，規則提取是一件比較困難的工作，在之前的工作中已經獲得了相似模糊概念和相容模糊概念，然后根據算法3構造好相似模糊概念格，但是由于相似模糊概念中有許多不確定性信息，所以構造的相似模糊概念格也是不準確的。通過對相似模糊概念的篩選，最后得到了較為準確的相容模糊概念，可以在構造好的相似模糊概念格基礎上得到相容模糊概念的之間的偏序關系，從而可以提取出可信度較高的關聯規則，具體算法參考算法4。

算法3相似模糊概念格的構造算法。

輸出相似模糊概念格。

2)遍歷屬性m，其中m∈M，并求得A與FO(m)交集I。如果遍歷結束轉到1)，否則轉到3)。

4)輸出相似模糊概念格，算法結束。

算法4不完備形式背景下規則提取的算法。

輸出關聯規則∑。

1)對相似模糊概念格進行處理，除去相容模糊概念之外的概念，更新父節點和子節點。

4)輸出∑。

在得到提取規則∑后，可以給其支持度閾值ω與置信度閾值τ。然后根據需要從提取的規則中篩選出符合要求的規則。

4示例展示

現在舉例來展示規則提取的過程，在表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)}。

根據算法4可以得出閾值τ為0.9，置信度閾值為0.5的關聯規則：

1){a,d,e}?{c,f}置信度為0.5。

解釋：如果頭疼、食欲不振、咳嗽則惡心、乏力。

2){a,e}?置信度為0.67。

解釋：如果頭疼、咳嗽則血壓會高。

5實驗結果與分析

本文基于相容模糊概念的關聯規則提取可分為在不完備模糊形式背景中相容模糊概念的構造過程和根據相容模糊概念的偏序關系進行提取規則的過程。本文算法在Win7環境下用MATLAB來實現，并在UCI數據庫的water數據集(526個對象，38個屬性)進行實驗。實驗主要對2個指標進行測量：第1個是在不完備模糊形式背景下相似模糊概念數目與對象數目以及相容模糊概念與對象數目之間的關系；第2個是提取的關聯規則數目與對象數目之間的關系。在本實驗中針對不完備模糊形式背景，設定相容模糊參數為(α=0.8,β=0.9)，關聯規則的置信度閾值為0.8。在不完備形式背景下相似模糊概念與相容模糊概念的數量關系可由圖3體現，圖4則體現了對象數目與關聯規則數量之間的關系。圖3與圖4都在相容模糊參數與屬性數量都不變的情況下，取water數據集中的前200個對象進行測量。圖3與圖4中橫坐標都表示對象的數量，初始為0，分別一次遞增50與10進行測試。圖3縱坐標表示由不完備形式背景形成概念的數量，圖4縱坐標表示由相容模糊概念獲得的關聯規則的數量。通過圖3、4的實驗結果可以觀察到，在不完備模糊形式背景中隨著對象數目的增多，通過本算法獲得知識準確性與傳統的方法相比具有一定的優勢。

圖3　對象與概念個數關系Fig.3　Relationship between object and concept

圖4　對象與關聯規則個數關系Fig.4　Relationship between object and association rule

6結束語

目前在不完備模糊形式背景下的研究越來越多。本文結合在傳統的不完備形式背景下獲取概念的方法，提出了在不完備模糊形式背景中提取出相容模糊概念，并根據相似模糊概念格提取出相容規則的方法。實驗表明，該方法可以有效的降低形式背景中因數據缺失和數據的模糊性對獲取知識準確性帶來的的影響。未來的工作還需要改進和細化文中的一些算法，例如如何在知識庫分類能力保持不變的情況下刪除不相關的冗余屬性；如何把模糊概念格與粗糙集理論有效結合以解決不確定規則提取中的規則冗余性等問題。

參考文獻:

[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]. 東北大學學報:自然科學版, 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]. 山西大學學報:自然科學版, 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]謝志鵬, 劉宗田. 概念格的快速漸進式構造算法[J]. 計算機學報, 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]梁吉業, 王俊紅. 基于概念格的規則產生集挖掘算法[J]. 計算機研究與發展, 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]王志海, 胡可云, 胡學綱, 等. 概念格上規則提取的一般算法與漸進式算法[J]. 計算機學報, 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年生，碩士研究生，主要研究方向為形式概念分析、數據挖掘。

王俊紅，女，1979年生，副教授，主要研究方向形式概念分析、粗糙集和數據挖掘。主持或參與多項國家863計劃、國家自然科學基金和省部級等科研項目。發表學術論文10余篇。

中文引用格式：胡小康，王俊紅.基于相容模糊概念的規則提取方法[J]. 智能系統學報， 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

文獻標志碼：A

文章編號：1673-4785(2016)03-0352-07

通信作者：王俊紅.E-mail:wjhwjh@sxu.edu.cn.

基金項目：國家自然科學基金項目(61202018，61303008，61305057).

收稿日期：2016-03-19.網絡出版日期：2016-05-13.

DOI:10.11992/tis.201603043

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0925.026.html