一種基于概念格的集值信息系統中的知識獲取方法

康向平, 苗奪謙

(1.同濟大學 計算機科學與技術系，上海 201804; 2. 同濟大學 嵌入式系統與服務計算教育部重點實驗室，上海 201804)

?

一種基于概念格的集值信息系統中的知識獲取方法

康向平1,2, 苗奪謙1,2

(1.同濟大學 計算機科學與技術系，上海 201804; 2. 同濟大學 嵌入式系統與服務計算教育部重點實驗室，上海 201804)

摘要：以集值信息系統為研究背景，以概念格為理論基礎，提出了一種基于概念格的集值信息系統中的知識獲取方法。該模型首先將復雜的集值信息系統轉化為形式上更加簡單的單值背景，然后借助概念格理論，重點探討了基于相容關系的粒化模型和集值系統中的格代數結構，該代數結構可以將論域中的所有覆蓋以格的形式有機結織起來。此外，探討了集值信息系統中的約簡、核等問題。本文有助于拓展概念格的應用范圍，同時也為集值信息系統的分析和處理提供了一種有益思路。

關鍵詞：粗糙集；概念格；集值信息系統；相容關系；代數結構

針對模糊、不確定等問題，波蘭學者Pawlak基于粒化和近似思想于1982年提出了粗糙集[1]，該理論于20世紀90年代逐步走向成熟并隨后引起了國內外學者的廣泛關注[2]。與其他類似理論相比較，其不需要借助復雜的先驗知識便可以在數據集中有效獲取知識，相對來講會更加客觀和易用。近年來，粗糙集正快速從單一理論向多理論融合方向發展、從簡單應用向復雜數據建模方向延伸，其相關研究成果已被廣泛應用于數據挖掘、機器學習等領域[3-5]。

概念格是與粗糙集同時代產生的一種數據分析工具[6]，其最早是由德國學者Wille基于人腦的概念思維提出來的。在概念格構筑的理論體系中，概念、格代數結構，伽羅瓦(Galois)連接等是核心要素。其中，概念可以分別從內涵和外延兩個不同角度進行刻畫，具有豐富的語義，有助于深化人們對現實生活中概念的概要認識和準確理解；代數格結構作為一種基于序關系建立起來的概念層次模型，客觀上反映了概念之間的泛化/特化關系；伽羅瓦連接則為生成概念和代數結構的核心理論基礎。近年來，關于概念格的基礎理論研究和應用拓展已經取得了一系列重要成果[7-10]。

雖然上述理論方法上存在一定差異，但集合論和二元關系都是它們的建模基礎，同時它們均面向相類似的數據集，這就意味著它們之間可能存在著某種緊密的關聯。在充分挖掘它們各自理論優勢的基礎上，探討二者之間的融合理論必將有助于粗糙集和概念格的進一步拓展。近年來，許多學者探討了它們之間的融合理論[11]。一些學者把概念格中的概念思維、格代數結構、伽羅瓦連接等要素引入到粗糙集中，探討了信息系統中的格代數結構、約簡、規則獲取等[12-13]；一些學者把形式背景視為一類特殊的信息系統，然后借助粗糙集中的近似算子和區分矩陣，提出了概念格中的粗糙概念分析、屬性約簡，以及上近似格和下近似格等[14-16]；一些學者從不同角度對比了兩種理論，揭示了它們之間的緊密聯系[17-20]，這樣做不僅有助于人們從不同角度深化對單一理論的認識和理解，同時也有助于兩種理論之間的深度融合。

在關于經典信息系統的描述中，對象在屬性下的取值是唯一的。然而，在一些復雜的信息系統，對象在屬性下的取值有時可能不是一個值，而是由若干個元素組成的一個非空集合，即取值不是一個值而是一個集合。當取值是一個集合時，若其代表一個取值范圍，那么此時取值就存在一定的不確定性。例如，在地震預測中，不同專家可能得出不一樣的預測結果，也許這些預測結果都是合理的，但卻只有一種預測是正確的。據此，人們將經典信息系統進一步泛化為集值信息系統。本質上，信息的不完備性也可以理解為上述不確定性的一種特殊情況[21-22]。例如，在不完備信息系統中，針對取值缺失的情況，人們通常會用一個集合替代某個缺失值，即依據先驗知識或算法將缺失值限定在某個范圍，并將該范圍視為缺失值。在此意義下，不完備信息系統本質上是一種特殊的集值信息系統。針對上述不確定性，以往人們更多采用的是一些間接的知識獲取方法，即數據建模是建立在對數據預處理的基礎之上。此類方法雖然簡單易用，但數據預處理可能會丟失大量的有用信息或由于人為因素增加一些額外的偏差信息，存在一定的局限性。針對上述情況，許多學者嘗試發展直接面向集值信息系統的知識獲取方法[23-28]，諸如基于相容關系、優勢關系等的粗糙集模型。直接處理方法不經過數據預處理，能直接對原始數據進行處理，可以有效避免由于數據預處理不當所導致的偏差逐層傳導擴大。

針對上述不確定性問題，同時考慮到概念格在二元關系分析中的良好數學基礎，本文引入了概念格，并重點探討了基于相容關系的粒化模型和集值系統中的格代數結構，該代數結構可以將論域中的所有覆蓋以格的形式有機結織起來。此外，本文還重點探討了集值信息系統中的約簡、核等問題。總的來講，本文結論一方面有助于拓展概念格的應用范圍，另一方面也為集值信息系統的分析和處理提供了一種有益思路。

1概念格

表1　一個典型的形式背景

圖1　從表1導出的概念格結構Fig.1　The concept lattice derived from table 1

定義4關于概念格的詳細介紹請參閱文獻[29]。

2集值信息系統和單值形式背景

表2　一個典型的集值信息系統

單值背景中的經典算子往往并不適用于多值的信息系統。即若采用定義1中的算子，必須將信息系統轉化為單值形式背景。由此，針對集值信息系統，本文采用了如下轉化策略。

由于衍生背景不再保留原信息系統中屬性值自身的信息，僅體現相同屬性下不同對象之間的關系，因而在形式上較原信息系統更加簡單明了。一個由表2所示集值信息系統衍生的形式背景如表3。

表3　一個衍生形式背景

3集值信息系統中的代數結構和粒化模型

概念格是一類重要的格代數結構，其在形式概念分析理論中扮演了重要的角色。據此，本文嘗試基于形式概念分析理論重點探討集值信息系統中的格代數結構、信息粒化等問題。其中，本文提到的粒化模型是基于定義3中的相容關系構造的。

證明由定義1、定義2和定義3即得，證畢。

引理2在定義4中，有下述結論成立：

證明由定義1和定義4即得，證畢。

在表2中，表4是由R{d,e}決定的中間背景，相應的概念格如圖2所示。顯然，依據定理2，可以判定{u1,u2,u5,u6}、{u1,u2,u7,u8}、{u3,u4}均是U/RB中的極大相容類。在圖2中，“ui”簡化表示為“i”。

表4　一個中間背景

依據定理2，本文在集值信息系統中進一步定義如下α和β映射。

圖2　從表4導出的概念格結構Fig. 2　A concept lattice derived from table 4

定義8設(U×U,AT,J)是(U,AT,V,F)的衍生背景，映射+:ν(L)→P(AT)被描述為

映射+:P(AT)→ν(L)被描述為

對于任意屬性子集B?AT，有

定理3 設(C,B)是一個相容概念，則C=U/RB。

定理4在上述定義中，設R,R1和R2是論域U中的相容關系，B,D?AT。有下述結論成立：

故結論B?B++成立。

證明與參考文獻[29]中有關結論的證明過程相類似，在此不再詳述。證畢。

例如，基于定義7中的算子，可以從表3導出一個如圖3的格結構，該結構即為表2所示集值信息系統中的相容概念格。圖3中的X1/X2/…/Xl表示覆蓋{X1,X2,…,Xl}，任意“ui”表簡化表示為“i”。

圖3　一個相容概念格Fig.3　A tolerance concept lattice

4集值信息系統中的約簡、核、依賴等知識的獲取

定理1約簡、核、依賴等作為粗糙集研究的重要組成部分，也是本文研究的重點。針對集值信息系統中的相關問題，本文給出一種基于定理6的求解方法。此節內容是通過借鑒文獻[12]得到的。

定理7設m∈B?AT，若滿足下述條件：

進而由(B-m)++=B++即得

與條件相矛盾！所以m∈Core(B)成立，證畢。

定理8設C?B?AT，若C是滿足下述條件的最小屬性子集：

則C是B的一個約簡。

證明基于定理6，由上述條件即得B++=C++，進而有

又由于C是滿足上述條件的B的最小屬性子集，故C是B的一個約簡，證畢。

在表2中所示的集值信息系統中，當B={a,b,c,d}時，依據上述定理，并參照表5中的包含關系，我們不難發現{a,d}和{b,c,d}是B的約簡，Core(B)=g0gggggg；而當B={a,b,c}時，{a}和{b,c}是B的約簡，Core(B)=?。為便于表示，表5中的任意屬性子集{m1,m2,…,mn}簡化為m1m2…mn。

定理9設B,D?AT，若滿足條件：

則B→D是一個依賴。

證明由條件可知：

進而由定理6即得D++?B++。由于

故B→D是一個依賴。證畢。

一個信息系統中往往包含著大量的冗余依賴，例如，當D?B時，B→D是絕對冗余的；當B1?B2且D2?D1時，由B1→D1可以推導出B2→D2，即B2→D2是相對冗余的。在表2中，去掉上述冗余依賴后，一個規模較小的依賴集如表6。在表6中，m1m2…mn表示集合{m1,m2,…,mn}。

表5　一些屬性子集與內涵之間的包含關系

表6　一個依賴集

5結束語

我們知道，二元關系是粗糙集的核心要素，而概念格本質上又是一種以二元關系為研究對象的數學工具，因此將概念格融入到粗糙集研究中，必將有助于拓展粗糙集的分析能力。本文嘗試將概念格中的概念思維、格代數結構、伽羅瓦連接等引入到集值信息系統中，重點探討了基于相容關系的粒化模型和集值系統中的格代數結構，該代數結構可以將論域中的所有覆蓋以格的形式有機結織起來。此外，本文還探討了集值信息系統中的約簡、核等問題。理論推理和實例驗證揭示了本文結論的合理性和有效性。本文從概念格視角提出了集值信息系統中的知識獲取方法，有助于人們深入理解粗糙集理論，也有助于揭示兩種理論之間的緊密聯系。相關研究內容仍將是我們下一階段的研究重點。

參考文獻:

[1]PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341-356.

[2]PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Dordrecht: Kluwer Academic Publishers, 1991.

[3]王國胤, 張清華, 胡軍. 粒計算研究綜述[J]. 智能系統學報, 2007, 2(6): 8-26.

WANG Guoyin, ZHANG Qinghua, HU Jun. An overview of granular computing[J]. CAAI transactions on intelligent systems, 2007, 2(6): 8-26.

[4]王國胤, 姚一豫, 于洪. 粗糙集理論及應用研究綜述[J]. 計算機學報, 2009, 32(7): 1229-1246.

WANG Guoyin, YAO Yiyu, YU Hong. A survey on rough set theory and applications[J]. Chinese journal of computers, 2009, 32(7): 1229-1246.

[5]傘冶, 葉玉玲. 粗糙集理論及其在智能系統中的應用[J]. 智能系統學報, 2007, 4(2): 40-47.

SAN Ye, YE Yuling. Rough set theory and its application in the intelligent systems[J]. CAAI transactions on intelligent systems, 2007, 4(2): 40-47.

[6]WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//RIVAL I. Ordered Sets. Netherlands: Springer, 1982: 445-470.

[7]LI Jinhai, MEI Changlin, WANG Lidong, et al. On inference rules in decision formal contexts[J]. International journal of computational intelligence systems, 2015, 8(1): 175-186.

[8]LI Jinhai, MEI Changlin, WANG Junhong, et al. Rule-preserved object compression in formal decision contexts using concept lattices[J]. Knowledge-based systems, 2014, 71: 435-445.

[9]QI Jianjun, QIAN Ting, WEI Ling. The connections between three-way and classical concept lattices[J]. Knowledge-based systems, 2016, 91: 143-151.

[10]ZHAI Yanhui, LI Deyu, QU Kaishe. Decision implication canonical basis: a logical perspective[J]. Journal of computer and system sciences, 2015, 81(1): 208-218.

[11]張文修, 姚一豫, 梁怡. 粗糙集與概念格[M]. 西安: 西安交通大學出版社, 2006.

[12]KANG Xianping, LI Deyu, WANG Suge, et al. Rough set model based on formal concept analysis[J]. Information sciences, 2013, 222: 611-625.

[13]曲開社, 翟巖慧, 梁吉業, 等. 形式概念分析對粗糙集理論的表示及擴展[J]. 軟件學報, 2007, 18(9): 2174-2182.

QU Kaishe, ZHAI Yanhui, LIANG Jiye, et al. Representation and extension of rough set theory based on formal concept analysis[J]. Journal of software, 2007, 18(9): 2174-2182.

[14]仇國芳, 張志霞, 張煒. 基于粗糙集方法的概念格理論研究綜述[J]. 模糊系統與數學, 2014, 28(1): 168-177.

QIU Guofang, ZHANG Zhixia, ZHANG Wei. A survey for study on concept lattice theory via rough set[J]. Fuzzy systems and mathematics, 2014, 28(1): 168-177.

[15]WAN Qing, WEI Ling. Approximate concepts acquisition based on formal contexts[J]. Knowledge-based systems, 2015, 75: 78-86.

[16]KENT R E. Rough concept analysis: a synthesis of rough sets and formal concept analysis[J]. Fundamenta informaticae, 1996, 27(2-3): 169-181.

[17]CHEN Jinkun, LI Jinjin, LIN Yaojin, et al. Relations of reduction between covering generalized rough sets and concept lattices[J]. Information sciences, 2015, 304: 16-27.

[18]LI Jinhai, REN Yue, MEI Changlin, et al. A comparative study of multigranulation rough sets and concept lattices via rule acquisition[J]. Knowledge-based systems, 2016, 91: 152-164.

[19]SHAO Mingwen, LEUNG Y. Relations between granular reduct and dominance reduct in formal contexts[J]. Knowledge-based systems, 2014, 65: 1-11.

[20]TAN Anhui, LI Jinjin, LIN Guoping. Connections between covering-based rough sets and concept lattices[J]. International journal of approximate reasoning, 2015, 56: 43-58.

[21]KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112(1/2/3/4): 39-49.

[22]KRYSZKIEWICZ M. Rules in incomplete information systems[J]. Information sciences, 1999, 113(3/4): 271-292.

[23]王國胤. Rough集理論在不完備信息系統中的擴充[J]. 計算機研究與發展, 2002, 39(10): 1238-1243.

WANG Guoyin. Extension of rough set under incomplete information systems[J]. Journal of computer research and development, 2002, 39(10): 1238-1243.

[24]LEUNG Y, LI Deyu. Maximal consistent block technique for rule acquisition in incomplete information systems[J]. Information sciences, 2003, 153: 85-106.

[25]ZHANG Wenxiu, MI Jusheng. Incomplete information system and its optimal selections[J]. Computers & mathematics with applications, 2004, 48(5/6): 691-698.

[26]GUAN Yanyong, WANG Hongkai. Set-valued information systems[J]. Information sciences, 2006, 176(17): 2507-2525.

[27]QIAN Yuhua, DANG Chuangyin, LIANG Jiye, et al. Set-valued ordered information systems[J]. Information sciences, 2009, 179(16): 2809-2832.

[28]QIAN Y H, LIANG J Y, SONG P, et al. On dominance relations in disjunctive set-valued ordered information systems[J]. International journal of information technology & decision making, 2010, 9(1): 9-33.

[29]GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin Heidelberg: Springer-Verlag, 1999.

康向平, 男, 1982年生, 博士后, 主要研究方向為概念格、粗糙集、粒計算。

苗奪謙, 男, 1964年生, 教授, 博士生導師，中國人工智能學會理事、中國計算機學會杰出會員、中國自動化學會智能自動化專委會委員、上海市計算機學會理事、上海市人工智能學會理事，主要研究方向為粗糙集、粒計算、Web 智能、數據挖掘和機器學習。 主持完成國家級、省部級自然科學基金與科技攻關項目多項, 參與完成973計劃項目、863計劃項目、國家自然科學基金重大研究計劃項目、上海市科委重大科技攻關項目等多項。作為項目組成員, 曾獲國家教委科技進步三等獎、教育部科技進步一等獎、上海市技術發明一等獎、重慶市自然科學一等獎等。發表學術論文260余篇, 其中被SCI或EI檢索150余篇. 編著教材及著作12部, 獲得專利授權9項。

中文引用格式：康向平, 苗奪謙.一種基于概念格的集值信息系統中的知識獲取方法[J]. 智能系統學報， 2016, 11(3): 287-293.

英文引用格式：KANG Xiangping, MIAO Duoqian. A knowledge acquisition method based on concept lattice in set-valued information systems [J]. CAAI transactions on intelligent systems, 2016,11(3): 287-293.

A knowledge acquisition method based on concept lattice in set-valued information systems

KANG Xiangping1,2, MIAO Duoqian1,2

(1. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China； 2. Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 201804, China)

Abstract：The paper takes set-valued information systems as research background, proposes a knowledge acquisition method on the basis of concept lattice. The model can transforms a complicated set-valued information system into a simpler one-valued context, and then by means of concept lattice, emphasizes the granularity model based on tolerance relation and the algebra structure in the set-valued information system, where the algebraic structure can organize all covers in the form of lattice structure, and it can be considered an important algebraic structure in the set-valued information system. Meanwhile, the paper also offers some simple solutions to common problems, such as reduction, core. In short, this paper not only helps to explore the application range of concept lattice, but also offers a useful idea for the analysis and processing of set-valued information systems.

Keywords：rough set; concept lattice; set-valued information systems; tolerance relations; algebraic structure

作者簡介：

中圖分類號：TP18

文獻標志碼：A

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

通信作者：康向平. E-mail：tongji_kangxp@sina.com.

基金項目：國家自然科學基金項目(61273304, 61202170)；國家博士后科學基金項目(2014M560352)；高等學校博士學科點專項科研基金項目(20130072130004).

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

DOI:10.11992/tis.201603055

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