概念格理論發(fā)展分析

毛華,康然

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定　071002)

?

概念格理論發(fā)展分析

毛華,康然

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定071002)

摘要：通過查找多個國內(nèi)外數(shù)據(jù)庫,對近年(2009至2015年)國內(nèi)外概念格理論的發(fā)展現(xiàn)狀進(jìn)行統(tǒng)計分析.介紹了近年有關(guān)概念格的建格算法、提取規(guī)則和關(guān)聯(lián)規(guī)則、屬性約簡的方法以及概念格與其他學(xué)科的結(jié)合理論，此外還介紹了概念格理論在實體檔案館、排產(chǎn)管理和車輛運輸安全性中的應(yīng)用.

關(guān)鍵詞：概念格；建格算法；屬性約簡；分析

第一作者：毛華(1963-) , 女，河北石家莊人,河北大學(xué)教授, 主要研究計算機(jī)數(shù)學(xué)基礎(chǔ)及應(yīng)用.

E-mail: mh@hbu.cn

E-mail: kangran09@163.com

概念格[1-2](concept lattice)，也叫做形式概念分析(formal concept analysis)，是由Wille首先提出的.概念格作為數(shù)據(jù)統(tǒng)計與分析的有效工具之一，擁有完備性和精確性的特點.概念格是根據(jù)對象和屬性之間的二元關(guān)系建立起來的概念層次結(jié)構(gòu)，又由于概念格能生成Hasse示圖，這使它能生動、簡明地體現(xiàn)出各概念之間的關(guān)系.由于其可視性強，又與其他的理論不斷結(jié)合，而被廣泛地應(yīng)用于軟件工程、知識發(fā)現(xiàn)等領(lǐng)域[3-4].

本文利用常用的數(shù)據(jù)庫以及主要文獻(xiàn)，對近6年(2009至2015年)概念格在國內(nèi)外的發(fā)展?fàn)顩r進(jìn)行統(tǒng)計和分析，并著重介紹近幾年概念格的相關(guān)算法，概念格與其他學(xué)科的結(jié)合理論，以及在不同領(lǐng)域的應(yīng)用.

1概念格研究現(xiàn)狀

本節(jié)主要通過查找國內(nèi)主要數(shù)據(jù)庫，對與概念格有關(guān)的論文進(jìn)行統(tǒng)計，得到圖1.分析圖1得知有關(guān)概念格理論及應(yīng)用方面的論文數(shù)量一直處于較平穩(wěn)狀態(tài)，并于2013年開始有進(jìn)一步的發(fā)展，不論是從文獻(xiàn)數(shù)量還是引文數(shù)量都有所上升.

國際上概念格領(lǐng)域的研究更是科學(xué)界的一個熱點,每年都會有大量的成果發(fā)表于各類期刊雜志(見圖2,圖3),代表概念格領(lǐng)域最高水平的國際會議ICFCA(international conference of formal concept analysis)自2003年每年舉行1次,發(fā)表的論文集反應(yīng)當(dāng)年的最高研究成果,這些都不斷推動概念格理論的擴(kuò)大與發(fā)展.

圖1　相關(guān)論文數(shù)量隨年代變化趨勢

圖2　每年出版的文獻(xiàn)數(shù)

圖3　每年的引文數(shù)

2概念格研究方法

從概念格理論誕生[1]到對概念格的完備性等性質(zhì)[5]的討論,說明概念格理論的進(jìn)一步成熟.而后,又有學(xué)者研究概念格的建格算法、提取規(guī)則和關(guān)聯(lián)規(guī)則、屬性約簡等[6-9]方法,同時,還有學(xué)者研究概念格與其他學(xué)科理論相結(jié)合的問題.

2.1　概念格的建格算法

概念格的建格過程實際上是概念聚類的過程,對同一批數(shù)據(jù),所生成的格也是唯一的.在已提出的許多建格算法[10-17]的基礎(chǔ)上,謝志鵬[18]，胡可云等[19]提出了一些概念格的改進(jìn)算法.

近幾年來,隨著概念格的發(fā)展,在國內(nèi),Zhang等[7]針對區(qū)間概念格的概念外延在區(qū)間范圍內(nèi)滿足內(nèi)涵屬性的特性,提出基于屬性集合冪集的區(qū)間概念格的漸進(jìn)式生成算法.Liu等[6]通過分析粗糙概念格的概念和結(jié)構(gòu),并結(jié)合一般概念格的構(gòu)建思想,針對決策形式背景,提出一種以決策屬性值為切入點的粗糙概念格的分層建格算法,豐富了粗糙概念格的構(gòu)建理論.周建等[20]將形式背景中的對象和屬性之間的二元關(guān)系簡化為布爾矩陣,并對布爾矩陣進(jìn)行算法處理,著重分析求外延的算法及計算機(jī)語言的實現(xiàn),得到概念格的一種建格算法.

2.2　概念格的提取規(guī)則和關(guān)聯(lián)規(guī)則挖掘算法

數(shù)據(jù)挖掘是知識發(fā)現(xiàn)的一門重要技術(shù),關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要模式之一.而概念格是數(shù)據(jù)分析的有力工具,也是進(jìn)行數(shù)據(jù)挖掘和規(guī)則提取的一種有效方法. 有關(guān)基于增量式概念格建造算法上的蘊含規(guī)則提取算法，可參見文獻(xiàn)[10],有關(guān)基于Bordat算法的分類任務(wù)，可參見文獻(xiàn)[21]，而應(yīng)用到瀏覽檢索中的概念聚類算法，可參見文獻(xiàn)[17].

近幾年又有許多學(xué)者提出了更為簡單、便捷的算法.如Wang等[22]提出的基于對象集的概念格提取規(guī)則算法.Guo等[23]針對傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法不利于用戶選擇關(guān)鍵數(shù)據(jù)進(jìn)行分析、無法處理多值屬性數(shù)據(jù)及效率低下等問題,提出了Apriori改進(jìn)算法，以及多值屬性的相關(guān)規(guī)則挖掘,并且運用概念格理論對多值屬性數(shù)據(jù)進(jìn)行了重新定義和分類,建立了數(shù)據(jù)挖掘參數(shù)調(diào)整機(jī)制.Fu等[24]針對現(xiàn)有的基于頻繁模式樹 FP-tree 和概念格的規(guī)則挖掘算法在構(gòu)造概念格時存在重復(fù)遍歷 FP-tree 問題,在挖掘后件約束的規(guī)則時算法構(gòu)造的概念格包含冗余結(jié)點的這2個問題,提出了通過遍歷 FP-tree 生成候選概念格節(jié)點的策略,并根據(jù)候選概念格節(jié)點進(jìn)一步構(gòu)造規(guī)則約束條件下無冗余概念格.

2.3　概念格的屬性約簡算法

概念格屬性約簡是保持對象集不改變,找出概念格中最小的屬性集的過程.屬性約簡的過程能夠完全確定形式背景上的概念及其層次結(jié)構(gòu), 更容易發(fā)現(xiàn)形式背景中隱含的知識,也使得這些知識的表示變得更簡單.

Ganter[5]提出屬性約簡的思想,而Zhang等[25]提出了不同于Ganter的屬性約簡理論,進(jìn)一步擴(kuò)充了概念格約簡理論.最近,Chen等[8]提出了一種面向?qū)ο蟾拍罡竦膶傩约s簡方法并指出概念格的協(xié)調(diào)集和約簡集與對象概念格的并不可約元的外延集之間的關(guān)系.Liu等[9]通過對概念格和同構(gòu)理論的研究,發(fā)現(xiàn)不同的概念格之間存在同構(gòu)關(guān)系,并提出一系列概念格同構(gòu)的判定定理.基于這一理論,Liu等提出了概念格同構(gòu)意義下屬性約簡的方法,這一方法能夠降低形式背景結(jié)構(gòu)空間復(fù)雜度,提高知識處理效率.

2.4　概念格與其他學(xué)科結(jié)合產(chǎn)生的方法

為了擴(kuò)大和充實概念格理論,也為了該理論的廣泛應(yīng)用,必須將該理論與其他學(xué)科相結(jié)合.由目前研究成果得知,概念格與其他學(xué)科的結(jié)合較為廣泛,其中與粗糙集和模糊集的結(jié)合成果相對豐富.

1)與粗糙集的結(jié)合

粗糙集[26]是發(fā)現(xiàn)知識、挖掘知識的數(shù)學(xué)工具,能有效地分析和處理不精確、不完備的信息.粗糙集利用等價關(guān)系對數(shù)據(jù)表進(jìn)行分類[27],而概念格是基于相同數(shù)據(jù)表,并結(jié)合序理論對概念分層加以討論.

Xu等[28]將變精度粗糙集β-上、下分布約簡算法的優(yōu)勢與概念格形式背景相結(jié)合,提出了基于變精度粗糙集的概念格約減算法,同時分析了變精度粗糙集模型中的β值的選取算法、可辨識矩陣屬性約簡,以及傳統(tǒng)算法中存在的問題,并且對傳統(tǒng)算法進(jìn)行了改進(jìn).Mao等[29]通過利用變精度粗糙集中的β-上、下近似與概念格中概念相結(jié)合,提出了概念格上的變精度粗糙集近似算子,并根據(jù)這一近似運算對形式背景中任意不可定義的對象集進(jìn)行近似,求出與其最接近的概念的外延,并得到了上、下近似概念.

2)與模糊集的結(jié)合

Burusco[30]在1994 年提出L-模糊概念,最早將模糊思想引入概念格.定義了基于三角?；蛱N涵算子的求導(dǎo)算子,之后Burusco[31]通過迭代求不動點可以得到模糊概念.Ma等[32]提出了一種基于模糊形式概念分析的模糊本體學(xué)習(xí)方法,該方法意圖從領(lǐng)域文檔中獲取模糊概念和模糊概念關(guān)系,并通過模糊形式概念分析,將其添加到源模糊本體轉(zhuǎn)化的模糊概念格中,以完成模糊本體學(xué)習(xí).

3概念格的應(yīng)用

概念格良好的結(jié)構(gòu)特征使其不斷飛速發(fā)展,已被廣泛地應(yīng)用于知識發(fā)現(xiàn)和數(shù)據(jù)挖掘等領(lǐng)域[2-3,33-34].本文將重點對概念格在實體檔案館、排產(chǎn)管理和車輛運輸安全性的應(yīng)用進(jìn)行闡述和分析.

3.1　在實體檔案館中的應(yīng)用

鄧君等[35]對實體檔案用戶行為進(jìn)行實踐調(diào)研,以此形成實體檔案館用戶行為的單值形式背景,并構(gòu)建實體檔案館用戶行為概念格,提出基于概念格的實體檔案用戶行為研究方法.該方法通過初步細(xì)分檔案用戶的信息,提出與檔案用戶相關(guān)的關(guān)聯(lián)規(guī)則,并挖掘出與檔案用戶行為相關(guān)的規(guī)律,為探索新型檔案用戶服務(wù)手段奠定了良好的基礎(chǔ).

3.2　在排產(chǎn)管理中的應(yīng)用

針對汽車沖壓廠生產(chǎn)數(shù)據(jù)量急劇增加的問題,Zhang等[36]提出了在沖壓廠生產(chǎn)信息數(shù)據(jù)中運用基于概念格的關(guān)聯(lián)規(guī)則挖掘技術(shù),并且采用橫向拆分與縱向合并的策略構(gòu)造概念格,將普通概念格轉(zhuǎn)化為量化概念格來生成關(guān)聯(lián)規(guī)則.該方法具有較高的挖掘效率,且能有效地尋找數(shù)據(jù)間隱藏的信息,為企業(yè)排產(chǎn)管理提供理論依據(jù).

3.3　在車輛運輸安全性中的應(yīng)用

Yang等[37]為自然語言的處理建立了一種數(shù)學(xué)工具，即基于Lukasiewicz蘊涵代數(shù)的語言真值概念格,將其應(yīng)用于車輛運輸安全性能的語言信息分析系統(tǒng)中,為了考察車輛的運輸安全性,作者選擇機(jī)動靈活性能及安全性能這2個因素作為研究對象,選取“載重量”、“爬坡能力”、“運行速度”、“使用時間”、“能耗量”這幾個因素作為研究的屬性,根據(jù)所給出的影響車輛運輸能力的語言真值形式背景,構(gòu)造出語言真值概念格,從而使得各因素的取值及它們之間的關(guān)系較為清晰地以Hasse圖呈現(xiàn)出來.

4結(jié)束語

通過近幾年來概念格在國內(nèi)外發(fā)展的現(xiàn)狀統(tǒng)計和分析表明,概念格以其獨有的特性不斷地贏得眾多學(xué)者的關(guān)注,其應(yīng)用范圍也不斷地拓展.從概念格理論研究歷史中得出,將其他學(xué)科與概念格理論相結(jié)合會創(chuàng)造出新思想、新方法.擬陣論始創(chuàng)于1935年,由Whitney[38]首先提出,后又不斷地發(fā)展[39-40].在查找近些年有關(guān)概念格與其他理論的結(jié)合應(yīng)用方面的文獻(xiàn)時,發(fā)現(xiàn)文獻(xiàn)[41]是國內(nèi)較早研究概念格與擬陣相結(jié)合的文章.目前也有學(xué)者研究擬陣與人工智能相結(jié)合的問題[42-43].今后期望有更多其他學(xué)科與概念格理論相結(jié)合[44],使概念格理論不斷地被充實,發(fā)揮出自身的優(yōu)勢,也使其他相關(guān)理論得到進(jìn)步和發(fā)展.國內(nèi)外眾多學(xué)者應(yīng)當(dāng)抓住這一領(lǐng)域,以其為契機(jī),將概念格理論不斷的擴(kuò)充、延伸,使其得到更進(jìn)一步的發(fā)展.

參考文獻(xiàn):

[1]WILLE R. Restructuring lattice theory: An approach based on hierarchies of concepts[C]//RIVAL I. Ordered Sets. Boston: Dordrecht Reidel, 1982: 445-470.

[2]DAVEY B A, PRIESTLEY H A. Introduction to Lattices and Order[M]. Cambridge: Cambridge University Press, 2002.

[3]ZHOU Wan, ZHOU Caixue. Research on the extracting rules of text categorization based on the extended concept lattice model[J]. Computer Engineering and Science, 2009, 24(1): 34-39.

[4]HE Chao, CHEN Xueqi, GUO Jiafeng. Mining hierarchical concept lattice for faceted navigation[J]. Chinese Journal of Computers, 2011, 34(9): 1589-1602.

[5]GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin: Springer, 1999.

[6]LIU Baoxiang, CHEN Huanhuan, LIU Jiebing. Layered construction algorithm and application of rough concept lattice[J]. Computer Science, 2013, 40(4): 214-216.

[7]ZHANG Chunying, WANG Liya. Incremental construction algorithm based on attribute power set for interval concept lattice [J]. Application Research of Computer, 2014, 31(3): 731-734.

[8]CHEN Yongping, YANG Sichun, SU Xin. Attribute reduction of object-oriented concept lattices based on join-irreducible elements[J]. Computer Engineering and Applications, 2014, 50(10): 131-135.

[9]LIU Jianming, LIU Baoxiang. On attribute reduction and its algorithm based on concept lattice isomorphism[J]. Computer Applications and Software, 2014, 31(5): 34-37.

[10]GODIN R. Incremental concept formation algorithm based on Galois (concept) lattices[J]. Computational Intelligence, 1995,11(2): 246-267.

[11]HO T B. An approach to concept formation based on formal concept analysis[J]. IEICE Trans Information and Systems, 1995, E78-D(5): 553-559.

[12]BODA J P. Calcul pratique du treillis de galois d-une correspon-dence[J]. Math Sci Humaines, 1986, 96(2): 31-47.

[13]CHEIN M. Algorithm de recherche des sous-matrices premieres d-une matrice[J].Bull Math Soc Sic Math,1969,13(6):21-25.

[14]GUENOCHE A. Construction du treillis de galois d’une relation binaire[J]. Mathématiques et Sciences Humaines, 1990,109: 41-53.

[15]NOURINE L, RAYNAUD O. A fast algorithm for building lattices[J]. Information Processing Letters, 1999, 71: 199-204.

[16]CARPINETO C, ROMANO G. Galois: an order-theoretic approach to conceptual clustering[Z]. Proceedings of the Tenth Znternational Conference, Amherst, 1993.

[17]HO T B. Incremental conceptual clustering in the frame work of Galois lattice[Z]. Proceeding of Knowledge Discovery and Date Mining, Singapore, 1997.

[18]謝志鵬，劉宗田.概念格的快速進(jìn)展式構(gòu)造算法[J].計算機(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.

[19]胡可云，陸玉昌，石純一.概念格及其應(yīng)用進(jìn)展[J].清華大學(xué)學(xué)報：自然科學(xué)版，2000，40(9)：77-81.

HU Keyun, LU Yuchang, SHI Chunyi. Advances in concept lattice and its application[J]. Journal of Tsinghua University: Science and Technology,2000, 40(9): 77-81.

[20]周建，莫智文.形式背景下概念格的一種建格算法[J].江南大學(xué)學(xué)報：自然科學(xué)版，2013，12(4)：429-431.

ZHOU Jian, MO Zhiwen. Study of establishing lattice algorithms based on the concept lattice under the formal contexts[J].Journal of Jiangnan University:Natural Science Edition, 2013, 12(4): 429-431.

[21]NJIWOUA P, NGUIFO E M. Forwarding the choice of bias LEGAL-F: using feature selection to reduce the complexity of LEGAL[Z]. Proceedings of ENELEARN-97, ILK and INFOLAB, Tiburg, 1997.

[22]WANG Zhihai, HU Keyun, HU Xuegang, et al. General and incremental algorithms of rule extraction based on concept lattice[J]. Chinese Journal of Computers, 1999, 22(1): 66-70.

[23]GUO Xiaobo, ZHAO Shuliang, WANG Changbin, et al. Multi-valued attribute association rules mining based on concept lattice[J]. Computer Science, 2014, 41(3): 267-272.

[24]FU Dongmei,WANG Zhiqiang. Mining algorithm of association rule based on FP-tree and constrained concept lattice and application research[J]. Application Research of Computers, 2014, 31(4): 1013-1016.

[25]ZHANG Wenxiu, WEI Ling, QI Jianjun. Attribute reduction theory and approach to concept lattice[J]. Science in China Series E-Information Science, 2005, 35(6): 628-639.

[26]PAWLAK Z. Rough sets [J]. International Journal of Computer and Information Sciences, 1982, 11: 341-356.

[27]WANG Guoyin, YAO Yiyu, YU Hong. A survey on rough set theory and its application[J]. Chinese Journal of Computers, 2009, 32(7): 1229-1246.

[28]XU Hongsheng, ZHANG Ruiling. Application of improved variable precision rough set in concept lattice construction[J]. Computer Science, 2013, 40(3): 271-275.

[29]MAO Hua, KANG Ran. Variable precision rough set approximations in concept lattice[J]. Journal of Progressive Research in Mathematics, 2015, 2(1): 47-56.

[30]BURUSCO A, FUENTES G R. Concept lattices defined from implication operators[J]. Fuzzy Sets and Systems, 2000, 114: 431-436.

[31]BURUSCO A, FUENTES G R. The study of the L-fuzzy concept lattice[J]. Mathware and Soft Computing, 1994, 3: 209-218.

[32]MA Di, LI Guanyu. A fuzzy ontology learning method based on fuzzy formal concept analysis[J]. Computer Applications and Software, 2014, 31(9): 166-172.

[33]SU Yajuan, ZHANG Tao. A kind of fuzzy concept lattice defined from product implication operators[J]. Computer Engineering and Applications, 2012, 48(19): 42-45.

[34]TILLEY T, COLE R, BECKER P, et al. A survey of formal concept analysis support for software engineering activities [EB/OL]. (2010-10-11)[2015-04-09]. http://citeseerx.ist.pus. edu/viewdoc/download?doi=10.1.1.105.372 6&rep=rep1&type=pdf.

[35]鄧君，馬曉君，張巨峰,等.基于概念格的實體檔案館用戶行為研究[J].圖書情報工作，2014,58(12):109-117.

DENG Jun, MA Xiaojun, ZHANG Jufeng, et al. Study on entity archives’ user behavior based on concept lattice[J]. Library and Information Service, 2014, 58(12): 109-117.

[36]ZHANG Xiao, LONG Wei, LU Bin. Application of association rule based on concept lattice for scheduling manage-ment[J]. Computer Engineering and Applications, 2014, 50(9): 264-270.

[37]YANG Li, WANG Yuhui, XU Yang. Linguistic truth-valued concept lattice based on graded linguistic values chain and its application[J]. Computer Applications, 2012, 32(9): 2523-2526.

[38]WHITNEY H. On the abstract properties of linear dependence[J]. American Journal of Mathematics, 1935, 57: 509-533.

[39]WELSH D J A. Matroid Theory[M]. London: Academic Press, 1976.

[40]OXLEY J. Matroid Theory [M]. New York: Oxford University Press, 2011.

[41]MAO Hua. The relation between matroid and concept lattice[J]. Advances in Mathematics, 2006, 35(3): 361-365.

[42]ZHU W, WANG Shiping. Rough matroids based on relations[J]. Information Sciences, 2013, 232: 241-252.

[43]MAO Hua. Characterization and reduction of concept lattices through matroid theory[J]. Information Sciences, 2014, 281: 338-354.

[44]SINGH P K, KUMAR C A. Bipolar fuzzy graph representation of concept lattice[J]. Information Sciences, 2014, 288: 437-448.

(責(zé)任編輯：孟素蘭)

Development analysis of concept lattice theory

MAO Hua, KANG Ran

(College of Mathematics and Information Science, Hebei University, Baoding 071002, China)

Abstract:By searching many databases at home and abroad in recent years (2009-2015), we statistically analyze these databases and obtain the current situation of development of concept lattice theory. After that, we also describe some algorithms of building lattices, extract rules and association rules, and attribute reduction of concept lattices. In addition, we introduce some combinations of concept lattice. We also introduce the applications of concept lattice theory, such as in entity archives, production scheduling management and the safety of transportation.

Key words:concept lattice; building lattices; attribute reduction; analyze

通信作者：康然(1988-), 女, 河北保定人，河北大學(xué)在讀碩士研究生，主要研究概念格理論及應(yīng)用.

基金項目：國家自然科學(xué)基金資助項目(61073121; 61572011; 61202178); 河北省自然科學(xué)基金資助項目(A2013201119)

收稿日期：2015-04-19

中圖分類號：TP18

文獻(xiàn)標(biāo)志碼:A

文章編號：1000-1565(2015)06-0667-06

DOI：10.3969/j.issn.1000-1565.2015.06.018