一種基于最大滿矩陣生成概念格的算法

郭倫眾，宋振明

(西南交通大學 數學學院,四川 成都 610097)

?

一種基于最大滿矩陣生成概念格的算法

郭倫眾，宋振明

(西南交通大學 數學學院,四川 成都 610097)

摘要：形式概念分析的核心是概念格，它在本質上描述了對象和屬性之間的聯系，表明了概念之間的泛化和例化關系,因此概念格的構造就顯得尤為的重要。從形式背景的關系矩陣出發,掃描形式背景的行和列找出屬性值為1的全部滿矩陣，定義了最大滿矩陣的概念，證明了最大滿矩陣是概念矩陣的充要條件。并在此理論上提出了一種基于最大滿矩陣生成概念格的算法，并對所提出的算法進行了理論論證。通過實例的運算，驗證了該算法的有效性。

關鍵詞：概念；形式概念分析；矩陣；算法

中文引用格式：郭倫眾，宋振明. 一種基于最大滿矩陣生成概念格的算法[J]. 智能系統學報， 2015, 10(6): 838-842.

20 世紀80 年代初, 德國的Wille 授提出了形式概念分析理論[1]。到目前， 概念格作為形式概念分析的核心數據結構, 已經成為一種用于數據組織和數據分析的形式化工具, 在數字圖書館及文獻檢索、軟件工程、數據挖掘等許多領域得到了廣泛應用[2]。概念格的構造是應用概念格的前提，因此概念格的構造效率就成為人們一直關注的焦點，提出了許多的構造算法。例如：Godin[3]提出了概念格的漸進生成算法;T.B.Ho[4]提出了基于概念格的概念聚類算法;劉宗田等[5]對Godin算法進行了改進;林春杰等[6]提出了基于不完備信息的近似概念格改進的概念格增量構造算法;李海霞[7]提出了基于概念格Hasse圖的一種對象漸減式構造算法;崔芳婷等[8]根據用戶的需求，把用戶感興趣的背景知識定義為約束，提出一種基于約束的模糊概念格構造算法;劉宏英等[9]基于對多維序列的理解，提出一種新的多維概念格并給出了漸進式構造算法。本文首先將形式背景看成一個0、1的關系矩陣，然后將形式背景化為既約的[10]，最后提出了一種基于最大滿矩陣來獲取概念格的算法。

1基本概念

下面給出形式背景的相關概念。

定義1[10]設U是對象集合，M是屬性的集合，I是2個集合U與M之間的關系，則稱三元組K=(U,M,I)為一個形式背景(簡稱背景)。

對于u∈U,m∈M,(u,m)∈I(或寫作uIm)表示對象u具有屬性m。

定義2[10]設K=(U,M,I)是一個背景。對于A?U,B?M。令

表1　形式背景K1

實際上，該形式背景完全由矩陣

刻畫，稱此矩陣為形式背景矩陣。

可以驗證這個背景的全部概念是：

(u1u2u3u4,f)、(u1u2,acfg)、(u2u3u4,ef)、(u1u2u4,cfg)、(u2u4,cefg)、(u2u3,bef)、(u2,abcefg)、(u4,cdefg)、(Φ,abcdefg)。

為了讓形式背景盡可能的簡單，下面給出凈化背景的定義。

例1 把表1凈化后，得到形式背景K2，如表2。

表2　形式背景K2

為了方便，給具有某種特點的對象或屬性一個統一的名稱。

顯然∧可約的屬性與∨可約的對象是可以刪除的。如果所有對象都具有某個屬性m，則稱m為“滿列屬性”；對應地，如果有某個對象u具有所有屬性，則稱u為“滿行對象”。由定義可得“滿列屬性”與“滿行對象”都是可約的。

如果一個凈化背景的每個對象概念都是∨不可約的，則稱這個背景為行既約的。如果一個凈化背景的每個屬性概念都是∧不可約的，則稱這個背景為列既約的。既是行既約的又是列既約的，則稱其是既約的。

例2把表2化成既約的，得形式背景K3,如表3所示。

表3　形式背景K3

這里把屬性f刪除，將屬性c與g合并成一個屬性也不會影響概念格的結構。

由于對具有相同內涵的對象和具有相同外延的屬性的各自合并所得的概念格與原概念格同構。所以在生成概念之前可以先把形式背景化為既約的，這樣就會使形式背景變得簡單些。

2滿矩陣與概念

定義6 在形式背景矩陣中，對于對象集A?U,如果屬性集B?M有

對偶地，可以定義最大對象滿矩陣：

在形式背景矩陣中，對于屬性集B?M，如果對象集A?U有

說明：給定對象集，則其對應的最大屬性滿矩陣是唯一的；給定屬性集，則其對應的最大對象滿矩陣是唯一的。

性質1 設(U,M,I)為一形式背景，對任意的對象集A1?A2?U，有

說明：該性質的依據就是對象集越大，則其具有的共同屬性不會多于其子集所具有的共同屬性。所以對象集A2具有的共同屬性應該小于或等于其子集A1具有的共同的屬性。

性質2 設(U,M,I)為一形式背景，對任意的屬性集B1?B2?M,有

說明：該性質的依據就是具有的共同屬性越多，則其對象集的個數不會增多。所以具有屬性集B2的對象個數應該小于或等于具有屬性集B1的對象個數。

定理1 概念矩陣一定是最大屬性滿矩陣和最大對象滿矩陣。

下面給出滿矩陣是概念矩陣的一個充分條件：

為了找出形式背景中所有的概念，根據定理1，可以先找出它的所有最大屬性滿矩陣或最大對象滿矩陣，進而根據定理2判斷那些滿矩陣為概念矩陣，最后得到所有的概念。

3方法

1)將形式背景化為既約背景。首先凈化背景，及合并具有相同內涵的對象和具有相同外延的屬性，然后刪除其內涵等于其他對象內涵交的那些對象，對應地刪除其外延等于其他屬性外延的交的那些屬性，得到的就是既約背景。

下面用具體例子說明該算法的過程。

通過上面的矩陣可以計算表3的概念層次如下：

1)形式背景矩陣對應的非零矩陣的最大屬性滿矩陣有：

2)由定理2得出概念矩陣有：

最后，得到概念所有的概念：

另外，可以先找出所有的最大對象滿矩陣，再根據定理2得到概念矩陣，進而得到所有的概念。

為了進一步說明該算法的有效性，給出實例：

根據上文給出的定義，刪除可約對象β，合并相同對象后，可以寫出表4對應的既約背景如表5。

表4　9個項目與6個特征的對應關系

表5　既約背景

下面寫出它既約背景對應的關系矩陣：

通過上面的矩陣可以計算表5的概念層次如下：

1)形式背景矩陣對應的非零矩陣的最大屬性滿矩陣有：

2)由定理2得出概念矩陣有：

3)最后，得到概念所有的概念：

5結束語

目前，已有不少概念格的建格算法，本文從矩陣的角度出發，利用矩陣與概念之間的聯系，定義了一種新的基于概念的矩陣——最大滿矩陣，找出了最大滿矩陣與概念之間的聯系，進而得出了一種基于矩陣的概念格生成算法，具體例子說明該算法是有效的。

參考文獻:

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

[2]OOSTHULZEN G D. The application of concept lattice to machine learning[R]. South Africa: University of Pretoria, 1996.

[3]GODIN R, MISSAOUI R, ALAOUI H. Incremental concept formation algorithms based on Galois (concept) lattices[J]. Computational Intelligence, 1995, 11(2): 246-267.

[4]HO T B. Incremental conceptual clustering in the framework of Galois lattice[C]//LU H, LIU H, MOTODA H. KDD: Techniques and Applications. Singapore: World Scientific, 1997: 49-64.

[5]謝志鵬, 劉宗田. 概念格的快速漸進式構造算法[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.

[6]林春杰, 普杰信, 張瑞玲. 近似概念格及其增量構造算法研究[J]. 計算機應用研究, 2012, 29(1): 25-27.

LIN Chunjie, PU Jinxin, ZHANG Ruilin. Approximation concept lattice and incremental constructing algorithm[J]. Application Research of Computers, 2012, 29(1): 25-27.

[7]李海霞. 基于Hasse圖的概念格的一種漸減式構造算法[J]. 河南科技學院學報, 2015, 43(3): 57-60, 66.

LI Haixia. A decreasing algorithm of concept lattice based on Hasse diagram[J]. Journal of Henan Institute of Science and Technology, 2015, 43(3): 57-60, 66.

[8] 崔芳婷, 王黎明, 張卓. 基于約束的模糊概念格構造算法[J]. 計算機科學, 2015, 42(8): 288-293, 318.

CUI Fangting, WANG Liming, ZHANG Zhuo. Construction algorithm of fuzzy concept lattice based on constraints[J]. Computer Science, 2015, 42(8): 288-293, 318.

[9]劉宏英, 郭顯娥, 胡小珍. 多維概念格及其構造算法[J]. 計算機工程與應用, 2012, 48(12): 96-99, 111.

LIU Hongying, GUO Xian'e, HU Xiaozhen. Multidimensional concept lattice and constructing algorithm[J]. Computer Engineering and Applications, 2012, 48(12): 96-99, 111.

[10]馬垣, 曾子維, 遲呈英, 等. 形式概念及其新進展[M]. 北京: 科學出版社, 2010: 11-24.

[11]蔣平, 任勝兵, 林鵑. 形式概念分析在軟件工程中的應用[J]. 計算機技術與發展, 2008, 18(4): 127-129, 213.

JIANG Ping, REN Shengbing, LIN Juan. Using formal concept analysis for software engineering[J]. Computer Technology and development, 2008, 18(4): 127-129, 213.

宋振明，男，教授，碩士生導師，主要研究方向為智能信息處理、運籌與控制、不確定性推理。

郭倫眾，女，1992年生，碩士研究生，主要研究方向為智能信息處理。

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

英文引用格式：GUO Lunzhong， SONG Zhenming. A novel concept-lattice acquisition approach based on the greatest full matrix of formal context[J]. CAAI Transactions on Intelligent Systems, 2015, 10(6): 838-842.

A novel concept-lattice acquisition approach

based on the greatest full matrix of formal context

GUO Lunzhong， SONG Zhenming

( School of Mathematics, Southwest Jiaotong University, Chengdu 610097, China)

Abstract：The concept lattice plays a crucial role in formal concept analysis, which describes essential object relations and attributes and illustrates the relation between generalization and specialization. Therefore, the development of effective methods for generating a concept lattice has been an important research topic. Based on the relational matrix of formal context, the rows and columns of the formal context are scanned to identify the full matrix. In this study, we define the concept of the greatest full matrix, and we prove that the greatest full matrix is a necessary and sufficient condition for the concept matrix. We also propose and theoretically demonstrate a concept-lattice generation algorithm based on the greatest full matrix. Finally, we provide an example to illustrate the rationality and effectiveness of the proposed algorithm.

Keywords：concept; formal concept analysis; matrix; algorithm

作者簡介：

通信作者：郭倫眾. E-mail：18380106827@163.com.

基金項目：國家自然科學基金資助項目(61175055).

收稿日期：2015-06-30. 網絡出版日期：2015-11-10.

中圖分類號：TP18

文獻標志碼：A

文章編號：1673-4785(2015)06-0838-05

DOI:10.11992/tis.201507063