智慧來(lái)，李逸楠

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454003)

0 引言

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

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

粗糙集理論是對(duì)象刻畫的另一種有效理論，通過(guò)采用近似的方式以處理數(shù)據(jù)的不確定性[21]。形式概念分析理論和粗糙集理論之間有著極強(qiáng)的互補(bǔ)性[22]。姚一豫[23-24]基于粗糙集理論，定義了面向?qū)ο蟾拍詈兔嫦驅(qū)傩愿拍?，并且深入討論了兩者的性質(zhì)。相比較于形式概念，面向?qū)ο蟾拍羁坍嫷氖峭庋又袑?duì)象集的必然屬性，與形式概念表達(dá)的共同屬性語(yǔ)義截然不同[14]。鑒于面向?qū)ο蟾拍钆c形式概念同樣具有廣泛的應(yīng)用場(chǎng)景[14-15]，因此亦有必要研究面向?qū)ο蟾拍畹募s簡(jiǎn)問(wèn)題。

本文研究如何在重構(gòu)原形式背景二元關(guān)系的前提下進(jìn)行面向?qū)ο蟾拍畹募s簡(jiǎn)。具體地，通過(guò)減少面向?qū)ο蟾拍睿瑢ふ冶M可能少的面向?qū)ο蟾拍?，從這些面向?qū)ο蟾拍畛霭l(fā)，可以重構(gòu)原形式背景的二元關(guān)系。在本文中，首先提出面向?qū)ο蟾拍羁蚣芟碌囊蜃臃纸夂兔嫦驅(qū)ο蟾拍罴s簡(jiǎn)，然后討論面向?qū)ο蟾拍罴s簡(jiǎn)的存在性及判定方法，并提出一種面向?qū)ο蟾拍罴s簡(jiǎn)求解算法，最后依據(jù)面向?qū)ο蟾拍钤诩s簡(jiǎn)過(guò)程中所起的不同作用，將其分為核心、相對(duì)必要和不必要面向?qū)ο蟾拍睢?/p>

1 基礎(chǔ)知識(shí)

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

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

定義1[24]797設(shè)K=(G,M,I)為一個(gè)形式背景，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≠?}。

此外，令上標(biāo)“c”表示一個(gè)集合的補(bǔ)集。例如，Xc=G-X，Ic=G×M-I。

定義2[24]797設(shè)K=(G,M,I)為一個(gè)形式背景，X?G,A?M。若X=A且A=X□，則稱(X,A)是一個(gè)面向?qū)ο蟾拍?，并稱X和A分別是這個(gè)面向?qū)ο蟾拍畹耐庋优c內(nèi)涵。進(jìn)一步，稱所有面向?qū)ο蟾拍钚纬傻母窠Y(jié)構(gòu)為面向?qū)ο蟾拍罡?，記作OL(K)。

例1表1中的形式背景K=(G,M,I)對(duì)應(yīng)的面向?qū)ο蟾拍钜还灿?3個(gè)，如表2所示，對(duì)應(yīng)的面向?qū)ο蟾拍罡袢鐖D1所示。

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

表2 形式背景K的全體面向?qū)ο蟾拍?/p>

圖1 形式背景K的面向?qū)ο蟾拍罡?/p>

2 面向?qū)ο蟾拍罴s簡(jiǎn)及特征

本節(jié)具體研究如何在重構(gòu)原形式背景二元關(guān)系的前提下進(jìn)行面向?qū)ο蟾拍畹募s簡(jiǎn)。為了敘述方便，下文將省略此前提，簡(jiǎn)述為“面向?qū)ο蟾拍罴s簡(jiǎn)”。

2.1 面向?qū)ο蟾拍羁蚣芟碌囊蜃臃纸?/h3>

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

下文將通過(guò)引入面向?qū)ο蟾拍钭鳛橐蜃觼?lái)實(shí)現(xiàn)這一過(guò)程。

定義3設(shè)OL(K)為形式背景K=(G,M,I)的面向?qū)ο蟾拍罡瘢現(xiàn)?OL(K)。若

且F中的元素最少，則稱F中的元素為理想因子，并稱這一過(guò)程為面向?qū)ο蟾拍羁蚣芟碌睦硐胍蜃臃纸狻?/p>

實(shí)際上，理想因子分解與布爾因子分解有著直接的對(duì)應(yīng)關(guān)系。若采用布爾矩陣W表示形式背景K，用F構(gòu)造布爾矩陣U與V，則有Wc=U°V，且布爾矩陣U的列數(shù)最少。這里，Wc=E-W，E表示元素全為1的矩陣。

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

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

2.2 面向?qū)ο蟾拍罴s簡(jiǎn)

首先，定義面向?qū)ο蟾拍罴s簡(jiǎn)如下。

定義4設(shè)OL(K)為形式背景K的面向?qū)ο蟾拍罡瘢現(xiàn)?OL(K)。若

性質(zhì)1任意形式背景至少存在一個(gè)面向?qū)ο蟾拍罴s簡(jiǎn)。

證明令K表示任意一個(gè)形式背景。若對(duì)任意的面向?qū)ο蟾拍?X,A)∈OL(K)，有

則OL(K)本身就是面向?qū)ο蟾拍罴s簡(jiǎn)。

若對(duì)任意的面向?qū)ο蟾拍?Xj,Aj)∈F，有

則F是面向?qū)ο蟾拍罴s簡(jiǎn)；否則，需要進(jìn)一步探究F1=F-{(X2,A2)}的約簡(jiǎn)。

重復(fù)上述過(guò)程，且鑒于OL(K)是有限集，可知K至少存在一個(gè)面向?qū)ο蟾拍罴s簡(jiǎn)。

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

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

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

設(shè)OL(K)為形式背景K的面向?qū)ο蟾拍罡瘢?xi,ai)為任意的二元關(guān)系，定義集合族SK如下：

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

則計(jì)算K的全體面向?qū)ο蟾拍罴s簡(jiǎn)等價(jià)于求Sk的全體極小碰撞集hit(Sk)。

基于此，下面給出一種面向?qū)ο蟾拍罴s簡(jiǎn)求解算法，如算法1所示。通過(guò)算法1，我們可以得到給定形式背景的全體面向?qū)ο蟾拍罴s簡(jiǎn)。

算法1形式背景K的全體面向?qū)ο蟾拍罴s簡(jiǎn)求解算法

輸入：形式背景K。

輸出：K的全體面向?qū)ο蟾拍罴s簡(jiǎn)。

步驟1：建立K的面向?qū)ο蟾拍罡馩L(K)；

步驟2：對(duì)于OL(K)中的每一個(gè)面向?qū)ο蟾拍?，?gòu)造SK={(X,A)|(xi,ai)∈Xc×A}|(xi,ai)∈Ic}；

步驟3：計(jì)算hit(Sk)；

步驟4：輸出hit(SK)中的所有元素并編號(hào)，即為形式背景K的全體面向?qū)ο蟾拍罴s簡(jiǎn)，算法結(jié)束。

例3(續(xù)例1)對(duì)于表1中的形式背景K，使用算法1，通過(guò)構(gòu)造SK，并計(jì)算hit(SK)即可得到K的全體面向?qū)ο蟾拍罴s簡(jiǎn)。具體地：

首先，對(duì)于OL(K)中的每一個(gè)面向?qū)ο蟾拍睿瑸榱朔奖闫鹨?jiàn)，我們用表2中的序號(hào)指代，可以得到集合族

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}};

其次，計(jì)算

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)中的所有元素并編號(hào)，即為形式背景K的全體面向?qū)ο蟾拍罴s簡(jiǎn)。最終輸出結(jié)果如下：

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}。

實(shí)際上，對(duì)任意的Fi∈{F1,F2，…，F(xiàn)8}，有

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

下面給出面向?qū)ο蟾拍罴s簡(jiǎn)的性質(zhì)。

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

證明必要性。因?yàn)镕是面向?qū)ο蟾拍罴s簡(jiǎn)，所以F是面向?qū)ο蟾拍顓f(xié)調(diào)集，有

又因?yàn)?/p>

即F是面向?qū)ο蟾拍顓f(xié)調(diào)集。

2.3 面向?qū)ο蟾拍钐卣?/h3>

依據(jù)面向?qū)ο蟾拍钤诩s簡(jiǎn)過(guò)程中所起的不同作用，可以把面向?qū)ο蟾拍罘譃槿悾唧w如下。

例4(續(xù)例1)對(duì)于表1中的形式背景，其面向?qū)ο蟾拍畹姆诸愐?jiàn)表3。

表3 形式背景K的面向?qū)ο蟾拍罘诸?/p>

綜上可知，給定一個(gè)形式背景，對(duì)于任意一個(gè)面向?qū)ο蟾拍罴s簡(jiǎn)，它一定包含所有的核心面向?qū)ο蟾拍?，一定不包含不必要面向?qū)ο蟾拍?，并且包含部分相?duì)必要面向?qū)ο蟾拍睢Ｍㄟ^(guò)這些面向?qū)ο蟾拍?，最終可以重新構(gòu)建給定形式背景的二元關(guān)系。

3 結(jié)論

本文研究如何在重構(gòu)原形式背景二元關(guān)系的前提下進(jìn)行面向?qū)ο蟾拍畹募s簡(jiǎn)，并將面向?qū)ο蟾拍罘譃楹诵?、相?duì)必要和不必要面向?qū)ο蟾拍?。文獻(xiàn)[8]與文獻(xiàn)[10]研究了在經(jīng)典形式概念框架下的保持二元關(guān)系不變的因子分解與概念約簡(jiǎn)問(wèn)題。雖然本文亦是研究概念約簡(jiǎn)，但二者存在著兩點(diǎn)重要不同。其一，形式概念與面向?qū)ο蟾拍罹哂胁煌恼Z(yǔ)義，適用于不同的應(yīng)用場(chǎng)景。其二，對(duì)于同一個(gè)形式背景，形式概念與面向?qū)ο蟾拍畈淮嬖谥苯拥膶?duì)應(yīng)關(guān)系，不能互相誘導(dǎo)，這就造成了文獻(xiàn)[10]中的結(jié)論無(wú)法直接推廣到面向?qū)ο蟾拍畹募s簡(jiǎn)。上述差異表明本文的研究不僅是有意義的，而且是很有必要的。

由于計(jì)算集合族的全體極小碰撞集是一個(gè)NP-hard問(wèn)題，形式背景的規(guī)模及其關(guān)系的填充比例將直接影響概念約簡(jiǎn)的計(jì)算時(shí)間。因此，對(duì)形式背景與概念約簡(jiǎn)的計(jì)算時(shí)間兩者關(guān)系的實(shí)驗(yàn)與理論研究也是十分有意義的。此外，眾所周知，形式概念分析的研究已經(jīng)不再局限于經(jīng)典形式概念，因而如何將現(xiàn)有的概念約簡(jiǎn)研究拓展到面向?qū)傩愿拍頪27]、三支概念[28]、近似概念[29]、模糊概念[30]也是值得深入探討的問(wèn)題。

(責(zé)任編輯：何軍民)