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

毛華,康然

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

?

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

毛華,康然

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

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

關鍵詞：概念格；建格算法；屬性約簡；分析

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

E-mail: mh@hbu.cn

E-mail: kangran09@163.com

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

本文利用常用的數(shù)據(jù)庫以及主要文獻，對近6年(2009至2015年)概念格在國內外的發(fā)展狀況進行統(tǒng)計和分析，并著重介紹近幾年概念格的相關算法，概念格與其他學科的結合理論，以及在不同領域的應用.

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

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

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

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

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

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

2概念格研究方法

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

2.1　概念格的建格算法

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

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

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

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

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

2.3　概念格的屬性約簡算法

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

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

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

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

1)與粗糙集的結合

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

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

2)與模糊集的結合

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

3概念格的應用

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

3.1　在實體檔案館中的應用

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

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

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

3.3　在車輛運輸安全性中的應用

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

4結束語

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

參考文獻:

[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].計算機學報，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]胡可云，陸玉昌，石純一.概念格及其應用進展[J].清華大學學報：自然科學版，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].江南大學學報：自然科學版，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.

(責任編輯：孟素蘭)

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-), 女, 河北保定人，河北大學在讀碩士研究生，主要研究概念格理論及應用.

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

收稿日期：2015-04-19

中圖分類號：TP18

文獻標志碼:A

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

DOI：10.3969/j.issn.1000-1565.2015.06.018