形式概念分析中的面向對象概念約簡

智慧來，李逸楠

(河南理工大學 計算機科學與技術學院，河南 焦作 454003)

0 引言

形式概念分析理論是對領域本體進行抽象描述，并且以概念的形式呈現[1]。經過多年的研究探索，該理論已經在概念格構造[2]、屬性約簡[3-7]、概念約簡[8-10]、規則獲取[11]、粒計算[5,12-17]等方向獲得了大量的研究成果，廣泛應用于信息檢索、數據挖掘、知識發現、人工智能等諸多領域。

在當今大數據時代，知識獲取變得愈加復雜。眾所周知，概念格的構造本質上是一個NP-hard問題[18]。因此，在保持概念格某種性質不變的前提下進行概念格的約簡就顯得極其重要。圍繞概念的約簡，已經有眾多學者提出了各自的想法[3-10]。Keprt與Belohlavek等[19-20]將形式概念分析理論引入矩陣分解，并提出了一種計算理想因子的方法，從而開啟了利用形式概念分析理論實現矩陣分解的研究。

粗糙集理論是對象刻畫的另一種有效理論，通過采用近似的方式以處理數據的不確定性[21]。形式概念分析理論和粗糙集理論之間有著極強的互補性[22]。姚一豫[23-24]基于粗糙集理論，定義了面向對象概念和面向屬性概念，并且深入討論了兩者的性質。相比較于形式概念，面向對象概念刻畫的是外延中對象集的必然屬性，與形式概念表達的共同屬性語義截然不同[14]。鑒于面向對象概念與形式概念同樣具有廣泛的應用場景[14-15]，因此亦有必要研究面向對象概念的約簡問題。

本文研究如何在重構原形式背景二元關系的前提下進行面向對象概念的約簡。具體地，通過減少面向對象概念，尋找盡可能少的面向對象概念，從這些面向對象概念出發，可以重構原形式背景的二元關系。在本文中，首先提出面向對象概念框架下的因子分解和面向對象概念約簡，然后討論面向對象概念約簡的存在性及判定方法，并提出一種面向對象概念約簡求解算法，最后依據面向對象概念在約簡過程中所起的不同作用，將其分為核心、相對必要和不必要面向對象概念。

1 基礎知識

形式背景是領域本體的抽象描述。假定，用G表示領域本體中的全部對象，并且用若干屬性M刻畫這些對象。具體地，若對象x具有屬性a，則用I(x,a)=1表示，否則記為I(x,a)=0。此時，得到的三元組(G,M,I)即為該領域本體的形式背景。

在本文中，對于單元素集合，為了方便起見，只列出元素并省略大括號。例如，用x表示集合{x}。

定義1[24]797設K=(G,M,I)為一個形式背景，x∈G,a∈M,X?G,A?M，定義算子如下：

x*={a|a∈M,I(x,a)=1}，a*={x|x∈G,I(x,a)=1}，

X□={a∈M|a*?X}，A◇={x∈G|x*∩A≠?}。

此外，令上標“c”表示一個集合的補集。例如，Xc=G-X，Ic=G×M-I。

定義2[24]797設K=(G,M,I)為一個形式背景，X?G,A?M。若X=A且A=X□，則稱(X,A)是一個面向對象概念，并稱X和A分別是這個面向對象概念的外延與內涵。進一步，稱所有面向對象概念形成的格結構為面向對象概念格，記作OL(K)。

例1表1中的形式背景K=(G,M,I)對應的面向對象概念一共有13個，如表2所示，對應的面向對象概念格如圖1所示。

表1 形式背景K=(G,M,I)

表2 形式背景K的全體面向對象概念

圖1 形式背景K的面向對象概念格

2 面向對象概念約簡及特征

本節具體研究如何在重構原形式背景二元關系的前提下進行面向對象概念的約簡。為了敘述方便，下文將省略此前提，簡述為“面向對象概念約簡”。

2.1 面向對象概念框架下的因子分解

設Un×k，Vk×m，Wn×m分別為n×k，k×m，n×m布爾矩陣，通過尋找盡可能小的k，使得Wn×m=Un×k°Vk×m成立。在文獻[25]中，稱Un×k°Vk×m為布爾矩陣乘積，并稱這一過程為布爾因子分解。

下文將通過引入面向對象概念作為因子來實現這一過程。

定義3設OL(K)為形式背景K=(G,M,I)的面向對象概念格，F?OL(K)。若

且F中的元素最少，則稱F中的元素為理想因子，并稱這一過程為面向對象概念框架下的理想因子分解。

實際上，理想因子分解與布爾因子分解有著直接的對應關系。若采用布爾矩陣W表示形式背景K，用F構造布爾矩陣U與V，則有Wc=U°V，且布爾矩陣U的列數最少。這里，Wc=E-W，E表示元素全為1的矩陣。

具體地，記G={x1,x2,…,xn}，M={a1,a2,…,am}，F={(X1,A1),(X2,A2),…，(Xk,Ak)}則布爾矩陣Un×k=(uij)n×k和Vk×m=(vij)k×m中的任一元素分別表示為：

例2(續例1)通過計算可知，例1中的形式背景存在理想因子c2，c4,c6,c8,c9,并且由這些理想因子可以得關于Wc的布爾因子分解。

2.2 面向對象概念約簡

首先，定義面向對象概念約簡如下。

定義4設OL(K)為形式背景K的面向對象概念格，F?OL(K)。若

性質1任意形式背景至少存在一個面向對象概念約簡。

證明令K表示任意一個形式背景。若對任意的面向對象概念(X,A)∈OL(K)，有

則OL(K)本身就是面向對象概念約簡。

若對任意的面向對象概念(Xj,Aj)∈F，有

則F是面向對象概念約簡；否則，需要進一步探究F1=F-{(X2,A2)}的約簡。

重復上述過程，且鑒于OL(K)是有限集，可知K至少存在一個面向對象概念約簡。

定義5[26]設S是由有限集D的子集構成的集合。S的一個碰撞集H是D的一個子集，使得對任意的S′∈S有H∩S′≠?。進一步，若不存在S的另外一個碰撞集H′使得H′?H，則稱H是S的一個極小碰撞集，并用hit(S)表示S的全體極小碰撞集。

例如，令S={{1},{2,3}，{2,4}}則有

hit(S)={{1,2},{1,3,4}}。

設OL(K)為形式背景K的面向對象概念格，(xi,ai)為任意的二元關系，定義集合族SK如下：

Sk={{(X,A)∈OL(K)|(xi,ai)∈Xc×A}|(xi,ai)∈Ic},

則計算K的全體面向對象概念約簡等價于求Sk的全體極小碰撞集hit(Sk)。

基于此，下面給出一種面向對象概念約簡求解算法，如算法1所示。通過算法1，我們可以得到給定形式背景的全體面向對象概念約簡。

算法1形式背景K的全體面向對象概念約簡求解算法

輸入：形式背景K。

輸出：K的全體面向對象概念約簡。

步驟1：建立K的面向對象概念格OL(K)；

步驟2：對于OL(K)中的每一個面向對象概念，構造SK={(X,A)|(xi,ai)∈Xc×A}|(xi,ai)∈Ic}；

步驟3：計算hit(Sk)；

步驟4：輸出hit(SK)中的所有元素并編號，即為形式背景K的全體面向對象概念約簡，算法結束。

例3(續例1)對于表1中的形式背景K，使用算法1，通過構造SK，并計算hit(SK)即可得到K的全體面向對象概念約簡。具體地：

首先，對于OL(K)中的每一個面向對象概念，為了方便起見，我們用表2中的序號指代，可以得到集合族

SK={{c5,c8,c11},{c5,c8},{c5,c9},{c5,c9,c12},{c4,c10},{c4,c7{c4,c9},{c4,c7,c9,c12},{c6,c11},{c6,c10},{c3,c6,c8,c11},{c3,c8},{c3,c6,c10},{c2,c7},{c2},{c2,c7,c12},{c9},{c9,c12}};

其次，計算

hit(SK)={{c2,c4,c6,c8,c9},{c2,c3,c4,c5,c6,c9},{c2,c4,c8,c9,c10,c11},{c2,c6,c7,c8,c9,c10},

{c2,c7,c8,c9,c10,c11},{c2,c3,c4,c5,c9,c10,c11},{c2,c3,c5,c6,c7,c9,c10},{c2,c3,c5,c7,c9,c10,c11}};

最后，輸出hit(SK)中的所有元素并編號，即為形式背景K的全體面向對象概念約簡。最終輸出結果如下：

F1={c2,c4,c6,c8,c9},F2={c2,c3,c4,c5,c6,c9},F3={c2,c4,c8,c9,c10,c11},

F4={c2,c6,c7,c8,c9,c10},F5={c2,c7,c8,c9,c10,c11},F6={c2,c3,c4,c5,c9,c10,c11},

F7={c2,c3,c5,c6,c7,c10},F8={c2,c3,c5,c7,c9,c10,c11}。

實際上，對任意的Fi∈{F1,F2，…，F8}，有

(3,a),(3,c),(4,a),(4,b),(4,c),(5,d),(5,f),(5,g),(6,e),(6,g)}=Ic。

下面給出面向對象概念約簡的性質。

一是扎實開展惠企走訪，及時輸血民營企業。受宏觀經濟下行壓力加大等因素的影響，民營企業經營面臨多重困難。金融機構要扛起支持民營企業的責任與擔當，緩解民企融資困難，積極為廣大小微企業和民營企業創造更大的生存空間。要積極開展對廣大民營企業和中小微企業的走訪工作，認真梳理走訪企業的共性問題，找準企業的融資痛點難點，通過推進企業在線融資，提升小微企業授信的專業化管理水平，創新小微企業金融服務，幫助企業拓寬融資渠道，擴大信貸工廠批量授信規模等方式，切實做到“對癥下藥”。

證明必要性。因為F是面向對象概念約簡，所以F是面向對象概念協調集，有

又因為

即F是面向對象概念協調集。

2.3 面向對象概念特征

依據面向對象概念在約簡過程中所起的不同作用，可以把面向對象概念分為三類，具體如下。

例4(續例1)對于表1中的形式背景，其面向對象概念的分類見表3。

表3 形式背景K的面向對象概念分類

綜上可知，給定一個形式背景，對于任意一個面向對象概念約簡，它一定包含所有的核心面向對象概念，一定不包含不必要面向對象概念，并且包含部分相對必要面向對象概念。通過這些面向對象概念，最終可以重新構建給定形式背景的二元關系。

3 結論

本文研究如何在重構原形式背景二元關系的前提下進行面向對象概念的約簡，并將面向對象概念分為核心、相對必要和不必要面向對象概念。文獻[8]與文獻[10]研究了在經典形式概念框架下的保持二元關系不變的因子分解與概念約簡問題。雖然本文亦是研究概念約簡，但二者存在著兩點重要不同。其一，形式概念與面向對象概念具有不同的語義，適用于不同的應用場景。其二，對于同一個形式背景，形式概念與面向對象概念不存在直接的對應關系，不能互相誘導，這就造成了文獻[10]中的結論無法直接推廣到面向對象概念的約簡。上述差異表明本文的研究不僅是有意義的，而且是很有必要的。

由于計算集合族的全體極小碰撞集是一個NP-hard問題，形式背景的規模及其關系的填充比例將直接影響概念約簡的計算時間。因此，對形式背景與概念約簡的計算時間兩者關系的實驗與理論研究也是十分有意義的。此外，眾所周知，形式概念分析的研究已經不再局限于經典形式概念，因而如何將現有的概念約簡研究拓展到面向屬性概念[27]、三支概念[28]、近似概念[29]、模糊概念[30]也是值得深入探討的問題。

(責任編輯：何軍民)