吳克晴, 陳希邦

（江西理工大學(xué)理學(xué)院，江西 贛州341000）

0 引 言

粒計(jì)算(Granular Computing,GrC)首先由Zadeh教授[1]提出。 粒計(jì)算是通過(guò)信息?；^(guò)程將復(fù)雜的問(wèn)題進(jìn)行分解、 轉(zhuǎn)化得到多個(gè)相對(duì)簡(jiǎn)單的子問(wèn)題，然后再對(duì)這些簡(jiǎn)單的子問(wèn)題進(jìn)行處理，從而實(shí)現(xiàn)對(duì)復(fù)雜問(wèn)題的求解[2]。粒計(jì)算的基礎(chǔ)是信息粒化，即在給定的?；瘻?zhǔn)則下，?；倪^(guò)程是通過(guò)對(duì)問(wèn)題空間的劃分產(chǎn)生多個(gè)信息粒，這些?？梢杂脕?lái)描述問(wèn)題本身所包含的一些信息，粒之間的偏序關(guān)系就形成了多層次的粒結(jié)構(gòu)。 粒計(jì)算的思想應(yīng)用于各種領(lǐng)域，如結(jié)構(gòu)化問(wèn)題的求解、結(jié)構(gòu)化信息處理等[3-4]。

形式概念分析[5]與粗糙集[6]在1982 年同時(shí)被提出， 許多學(xué)者都認(rèn)為它們是很有效的粒計(jì)算的方法，并且兩者之間有著極強(qiáng)的互補(bǔ)性。

形式概念分析[5]這一理論是由德國(guó)數(shù)學(xué)家Wille R教授提出， 國(guó)內(nèi)的研究學(xué)者通常稱(chēng)之為概念格理論。 概念格理論多用于知識(shí)發(fā)現(xiàn)以及知識(shí)表征，通過(guò)知識(shí)本身的外延和內(nèi)涵之間的依賴(lài)或者因果關(guān)系，通過(guò)構(gòu)建Hasse 圖來(lái)建立概念層次結(jié)構(gòu)。 概念格理論經(jīng)過(guò)多年的研究探索，已經(jīng)逐漸形成了一些具有特色的研究方向，比如概念格屬性約簡(jiǎn)[7]、三支概念分析[8]等。目前，在人工智能、機(jī)器學(xué)習(xí)、信息檢索等領(lǐng)域，概念格理論均有較為廣泛的應(yīng)用，同時(shí)與粗糙集、模糊集、數(shù)據(jù)挖掘等理論具有很好的結(jié)合性[9]。 而粗糙集作為一種處理不確定性問(wèn)題的數(shù)學(xué)工具，特別是在人工智能領(lǐng)域中作為一個(gè)較新的學(xué)術(shù)熱點(diǎn)，在機(jī)器學(xué)習(xí)、知識(shí)獲取、決策分析、過(guò)程控制等許多領(lǐng)域得到了廣泛的應(yīng)用[10-11]。

研究人員通過(guò)粒計(jì)算與形式概念分析以及粗糙集的結(jié)合，得到一系列成果，如粒規(guī)則獲取[12]、三支粒約簡(jiǎn)[13]、多粒度概念格的構(gòu)建[14]等。王一賓等[15]研究了基于對(duì)象導(dǎo)出三支概念格的規(guī)則提取。 Ma等[16]通過(guò)討論分層擴(kuò)展集的性質(zhì)，提出了一種快速構(gòu)造面向?qū)ο蟾拍罡竦乃惴ā?李金海等[17]利用經(jīng)典形式背景給出多粒度標(biāo)記形式背景的定義，證明了多粒度標(biāo)記形式背景與多粒度標(biāo)記信息系統(tǒng)在語(yǔ)義上等價(jià)。Zhi 等[18]基于必要的屬性分析，從不完整的形式語(yǔ)境中探討知識(shí)發(fā)現(xiàn)，提出了一種新的知識(shí)發(fā)現(xiàn)粒度描述方法。 文獻(xiàn)[19]通過(guò)使用縮放算法，可以通過(guò)現(xiàn)有的屬性（對(duì)象）導(dǎo)向概念格直接生成基于不同屬性粒度的屬性（對(duì)象）導(dǎo)向概念格。 文獻(xiàn)[20]基于形式概念分析中粒的思想和粗糙集理論中上、 下近似的方法通過(guò)對(duì)必然屬性分析的粒描述進(jìn)行了研究， 定義了一元可定義粒以及二元可定義粒。

文獻(xiàn)[20]主要通過(guò)面向?qū)ο蟾拍罡竦慕嵌葘?duì)其進(jìn)行了研究，而在研究中，作者并沒(méi)有從面向?qū)傩愿拍罱嵌冗M(jìn)行研究，因此，文中在文獻(xiàn)[20]的基礎(chǔ)上進(jìn)一步擴(kuò)展，首先是對(duì)屬性粒的描述，然后給出一元可定義屬性粒、一元屬性描述子的描述、二元可定義屬性粒、二元屬性描述子的描述，最后通過(guò)對(duì)比驗(yàn)證可以證明其有效性。

1 基本概念

為了本文內(nèi)容的完整性以及便于讀者的閱讀，本節(jié)主要是介紹文中所提到的一些基本概念。

1.1 形式概念分析與概念格

定義1（G，M，I）為形式背景，對(duì)象擁有的屬性所構(gòu)成的集合為g*={m∈M|gIm}，同樣的，屬性m所對(duì)應(yīng)的對(duì)象的集合為m*={g∈G|gIm}。 其規(guī)則詳見(jiàn)文獻(xiàn)[21]中的定義1.6。

定義2[21]設(shè)（G，M，I）為形式背景，其中A?G，B?M，定義：

定義3[21]設(shè)（G，M，I）為形式背景，A?G，B?M。 有A□=B 且B◇=A，則稱(chēng)序?qū)Γˋ，B）為面向?qū)ο蟾拍?；若A◇=B 且B□=A，則稱(chēng)序?qū)Γˋ，B）為面向?qū)傩愿拍睢?/p>

本文主要通過(guò)對(duì)面向?qū)傩愿拍畹难芯浚?稱(chēng)A為面向?qū)傩愿拍睿ˋ，B）的外延，B 為面向?qū)傩愿拍睿ˋ，B）的內(nèi)涵，在不產(chǎn)生歧義的情況下，統(tǒng)稱(chēng)A 為外延，B 為內(nèi)涵[21]。

定義4[21]設(shè)C1=（A1，B1），C2=（A2，B2）是形式背景K=（G，M，I）上的兩個(gè)面向?qū)傩愿拍睿舸嬖贏1?A2，則有C1≤C2，稱(chēng)關(guān)系≤是概念的“層次序”，（簡(jiǎn)稱(chēng)“序”）；如果不存在概念（A3，B3）使得A1?A3?A2， 則稱(chēng)C1是C2的直接子概念，C2是C1的直接父概念，記做C1＜C2。K=（G，M，I）的所有面向?qū)傩愿拍钣眠@種序組成的集合稱(chēng)為面向?qū)傩愿拍罡?，記做LA=（G，M，I）。

1.2 面向?qū)傩愿拍罡竦臉?gòu)建

本小節(jié)主要從粗糙集中的下近似角度出發(fā)，通過(guò)使用“*”算子，來(lái)構(gòu)建面向?qū)傩愿拍罡馵22]。

例1 一 個(gè) 形 式 背 景K=（G，M，I），G={1 ，2，3，4，5}，M={a，b，c，d，e，f}，其G 與M 之間的關(guān)系如表1 所示。

算法1 由下近似出發(fā)，構(gòu)建面向?qū)傩愿拍罡瘢?/p>

Step1：分別計(jì)算g＊i，其中g(shù)i∈G；

表1 形式背景

Step2：計(jì)算P（M）中的元素；

Step3：逐一判斷P（M）中的每一個(gè)元素是否滿(mǎn)足g＊i?B 且g＊i?B，其中B?M，若滿(mǎn)足，則（∪gi，B）為一個(gè)面向?qū)傩愿拍?；否則（∪gi，B）舍去；

Step4：將Step3 中得到的所有概念按照對(duì)象外延的包含關(guān)系順次連接， 從而得到概念格LA=（G，M，I）。

根據(jù)上述算法，對(duì)例1 所示的形式背景可以通過(guò)下近似構(gòu)建其面向?qū)傩愿拍罡瘢鐖D1 所示。

圖1 例1 形式背景的面向?qū)傩愿拍罡?/p>

1.3 粒的描述

粒計(jì)算作為一種新興的計(jì)算方法，它為相關(guān)研究領(lǐng)域提供了基于信息?；瘉?lái)解決復(fù)雜問(wèn)題的理論框架，是當(dāng)前計(jì)算機(jī)領(lǐng)域中解決復(fù)雜問(wèn)題和核心技術(shù)之一。 近幾年來(lái)，許多研究學(xué)者通過(guò)粒計(jì)算的理論知識(shí)來(lái)研究知識(shí)發(fā)現(xiàn)領(lǐng)域的一些問(wèn)題。

定義一個(gè)論域G， 所有可能的粒組成G 的冪集，記做2G，論域G 的屬性集用M 表示，即G 與M之間的二元關(guān)系由I：G×M 來(lái)表示，因此，一個(gè)形式背景K=（G，M，I）可以用來(lái)描述一個(gè)論域[19]。

同理，定義一個(gè)屬性論域M，M 中所有可能的粒組成的冪集，記做2M，與屬性集對(duì)應(yīng)的對(duì)象集用論域G 表示，其二元關(guān)系同樣可以有I：G×M。

定義5[23]一個(gè)形式背景K=（G，M，I），設(shè)B 為論域G 中對(duì)象的屬性的集合， 其B1，B2，B3， …，Bn中是B 的子集，則稱(chēng)是論域G 上的屬性粒。

定義6 給定一個(gè)粒B?2M以及一個(gè)對(duì)象集A?G，則若對(duì)任意的g∈A，都有g(shù)*?B，則對(duì)象集A 必然具有屬性粒B。

屬性粒的大小表示該粒所包含的信息量的度量，屬性粒越小則說(shuō)明信息量越小，反之亦然。

2 一元屬性描述子的粒描述

本小節(jié)主要研究基于一元屬性描述子的屬性粒描述，定義了正文字可定義屬性粒和負(fù)文字可定義屬性粒，它們統(tǒng)稱(chēng)為一元可定義屬性粒，并將對(duì)它的描述稱(chēng)為一元屬性描述子。

2.1 正文字可定義屬性粒的描述

文獻(xiàn)[20]中提出了正文字可定義粒并對(duì)其性質(zhì)進(jìn)行了分析，本節(jié)從面向?qū)傩愿拍罡窠嵌忍剿餍缘亩x了正文字可定義屬性粒。

定義7 一個(gè)形式背景K=（G，M，I），B?2M，若存在一個(gè)面向?qū)傩愿拍頒∈L（K），有C 的內(nèi)涵為B，則B 稱(chēng)為一個(gè)正文字可定義屬性粒。

在形式概念分析中，文獻(xiàn)[20]采用最小產(chǎn)生子來(lái)表達(dá)一個(gè)概念的核心屬性，類(lèi)似地，本文定義最小對(duì)象產(chǎn)生子來(lái)表達(dá)一個(gè)概念的核心對(duì)象。

定義8 一個(gè)凈化的面向?qū)傩愿拍頒=（A，B），設(shè)X?A，有X◇=A◇=B，且對(duì)于任意的S?X，有S◇?A◇，則稱(chēng)X 是概念C 的一個(gè)最小對(duì)象產(chǎn)生子。

對(duì)于最小對(duì)象產(chǎn)生子的方法與文獻(xiàn)[20]中最小產(chǎn)生子的方法類(lèi)似，這里則不進(jìn)一步描述。

對(duì)例1 所示的形式背景，它的正文字可定義屬性粒及其最小對(duì)象產(chǎn)生子如表2 所示。

表2 正文字可定義屬性粒及其最小對(duì)象產(chǎn)生子

2.2 負(fù)文字可定義屬性粒的描述

對(duì)于面向?qū)傩愿拍罡瘢?有正文字可定義屬性粒，就會(huì)存在負(fù)文字可定義屬性粒，而負(fù)文字可定義屬性粒是針對(duì)形式背景的補(bǔ)背景而言的。 對(duì)例1的形式背景K=（G，M，I），G＝{1，2，3，4，5}，M＝{a，b，c，d，e，f}，其補(bǔ)背景Kc=（G，M，Ic）如表3 所示。

表3 形式背景的補(bǔ)背景

表3 的形式背景Kc的面向?qū)傩愿拍罡袢鐖D2所示。

圖2 面向?qū)傩愿拍罡馤（Kc）

在形式背景Kc中，根據(jù)形式背景K 定義正文字可定義屬性粒及最小對(duì)象產(chǎn)生子的方法，可以得到負(fù)文字可定義屬性粒及其最小對(duì)象產(chǎn)生子，如表4 所示。

表4 負(fù)文字可定義屬性粒及其最小對(duì)象產(chǎn)生子

2.3 一元不可定義屬性粒的描述

在一個(gè)形式背景中，正文字可定義屬性粒與負(fù)文字可定義屬性粒統(tǒng)稱(chēng)一元可定義屬性粒， 此外，若該粒不是一元可定義屬性粒，則稱(chēng)為一元不可定義屬性粒。

下面給出基于一元屬性描述子的近似描述精度。

一個(gè)形式背景K=（G，M，I），mA是一元可定義屬性粒的集合，B?2M是一個(gè)一元不可定義屬性粒， 若?Bl，Bu?mA， 有Bl?B?Bu， 且不存在Bl*，Bu*?mA，使得Bl?Bl*?B?Bu*?Bu，則稱(chēng)Bl，Bu分別為B 的A-下近似屬性粒和A-上近似屬性粒，且B 的A-近似描述為dA（B）=[d（Bl），d（Bu）]，其中，d（Bl）和d（Bu）分別為B 的A-下近似和A-上近似的最小產(chǎn)生子，B 的A-近似精度為

3 二元屬性描述子的粒描述

上一節(jié)中主要通過(guò)定義正文字可定義屬性粒和負(fù)文字可定義屬性粒，以及探索面向?qū)傩愿拍畹淖钚‘a(chǎn)生子來(lái)對(duì)屬性粒進(jìn)行描述。在對(duì)屬性粒的描述中，為了提高其精度，需要同時(shí)用到原形式背景以及其補(bǔ)背景所包含的信息，因此，本節(jié)將提出基于二元屬性描述子的二元可定義屬性粒，并提出基于二元可定義屬性粒的M-三支概念格及其構(gòu)建算法。

定義9定義一個(gè)形式背景K=（G，M，I），其中U，V?G，B?M，若（U，V）□=B，且B◇=（U，V），稱(chēng)（（U，V），B）為屬性誘導(dǎo)的三支概念，簡(jiǎn)稱(chēng)M-三支概念，其中（U，V）為M-三支概念的外延。

這里對(duì)由對(duì)象誘導(dǎo)的三支概念不做贅述。

在上述定義中的形式背景中，U 描述了擁有屬性A 的對(duì)象集，V 描述了不擁有屬性A 的對(duì)象集，G-U-V 描述了擁有其他情況。

M-三支概念之間的偏序關(guān)系可以定義為：（（U1，V1），B1）≤（（U2，V2），B2）?B1≤B2，則 稱(chēng) 形 式背景的所有M-三支概念滿(mǎn)足偏序關(guān)系≤構(gòu)成一個(gè)完備格，記為屬性誘導(dǎo)的三支概念格，簡(jiǎn)稱(chēng)M-三支概念格，記做LM（K）。

3.1 二元可定義屬性粒的描述

定義10定義一個(gè)形式背景K=（G，M，I），B?2M，若存在M-三支概念（（U，V），B）∈LM（K），則稱(chēng)B 為二元可定義屬性粒，（U，V）為二元對(duì)象描述子。

定義11一個(gè)M-三支概念C=（（U，V），B）∈LM（K），設(shè)（u，v）?（U，V），有（u，v）◇=（U，V）◇=B，且對(duì)于任意的（u1，v1）?（U，V），有（u1，v1）◇?（U，V）◇，則稱(chēng)（u，v）是概念C 的一個(gè)最小對(duì)象產(chǎn)生子。

類(lèi)似于3.2 和3.3 小節(jié)的討論， 對(duì)于例1 中的形式背景，可以得到該形式背景所對(duì)應(yīng)的M-三支概念格以及二元可定義屬性粒和最小產(chǎn)生子。

3.2 算法描述

對(duì)于M-三支概念格的構(gòu)造算法，主要分為兩個(gè)部分，一是構(gòu)造混合形式背景KM，二是對(duì)混合形式背景構(gòu)建其概念格，具體步驟如下：

算法2

Step1：輸入形式背景K=（G，M，I）；

Step2：計(jì)算補(bǔ)背景Kc=（G，M，Ic）；

Step3：將K，Kc按照對(duì)象集疊置，得到混合形式背景

Step4：分別計(jì)算（gi，gj）*，其中（gi，gj）*∈GM；

Step5：計(jì)算P=（M）中的元素；

Step6：逐一判斷P=（M）中的每個(gè)元素是否滿(mǎn)足（gi，gj）*?B 且（gi，gj）*＝B，其中B?M，若滿(mǎn)足（∪（gi，gj）*，B）則為一個(gè)三支概念；否則（∪（gi，gj）*，B）舍去；

Step7： 將step 3 中得到的所有概念按照對(duì)象外延的包含關(guān)系順次連接，從而得到概念格L=（G，M，I），如圖3 所示。

該形式背景所對(duì)應(yīng)的M-三支概念、二元可定義屬性粒和最小產(chǎn)生子如表5 所示。

3.3 二元不可定義屬性粒的描述

類(lèi)似一元不可定義屬性粒， 二元不可定義屬性粒指的是不存在M-三支概念（（U，V），B）∈LM（K），則B 為二元不可定義屬性粒。

下面給出基于二元屬性描述子的近似描述精度。

一個(gè)形式背景K=（G，M，I），mD是一元可定義屬性粒的集合，B?2M是一個(gè)二元不可定義屬性粒， 若?Bl，Bu?mD， 有Bl?B?Bu， 且不存在Bl*，Bu*?mD，使得Bl?Bl*?B?Bu*?Bu，則稱(chēng)Bl，Bu分別為B 的D-下近似屬性粒和D-上近似屬性粒， 且B的D-近似描述為dD（B）=[d（Bl），d（Bu）]，其中，d（Bl）和d（Bu）分別為的D-下近似和D-上近似的最小產(chǎn)生子，B 的D-近似精度為:

4 對(duì)比驗(yàn)證

4.1 三種近似描述的對(duì)比驗(yàn)證

圖3 M-三支概念格

表5 二元可定義屬性粒及其最小對(duì)象產(chǎn)生子

文獻(xiàn)[20]結(jié)合粗糙可定義粒、一元可定義粒以及二元可定義粒來(lái)討論粒的描述精度問(wèn)題，本文提出了一元可定義屬性粒、二元可定義屬性粒，并分別基于一元可定義屬性粒和二元可定義屬性粒討論了粒的近似描述問(wèn)題。下面從描述精度角度對(duì)這三種近似描述方法進(jìn)行比較研究。

為了統(tǒng)一描述，全體粗糙可定義屬性粒組成的集合記做gR，給定一個(gè)屬性粒B，基于粗糙可定義屬性粒的上近似和下近似可定義為R-上近似和R-下近似，其近似描述記做R-近似描述，記做dR（B），描述精度記做ρR（B）。

設(shè)一個(gè)形式背景K=（G，M，I）， 粗糙可定義屬性粒的全體mR、 一元可定義屬性粒的全體mA、二元可定義屬性粒的全體mD有mR?mA?mD，描述精度滿(mǎn)足ρR（B）≤ρA（B）≤ρD（B）。在此需要說(shuō)明的是，每一個(gè)近似描述對(duì)應(yīng)著一個(gè)近似描述精度，由于某一屬性粒的近似描述可能存在多種情況，為保證描述精度的唯一性，可取最大的近似描述為該屬性粒的最佳近似描述。

對(duì)于例1 中的形式背景， 取B={b，c，d}， 則有R-下近似為{b，d}，R-上近似為{a，b，c，d，f}，屬性粒B 的R-近似描述dR（B）=[d（Bl），d（Bu）]=[d{b，d}，d{a，b，c，d，f}]=[3，2∨3]， 即R-描述精度為ρR（B）=同理，根據(jù)2.3 小節(jié)和3.3 小節(jié)中的兩種近似描述可得，屬性粒B 的A-近似描述dA（B）=[d（Bl），d（Bu）]=[d{b，d}，d{a，b，c，d，f}]=[3，2∨3]，由公式（5）可得，A-描述精度ρA（B）=0.4，滿(mǎn)足ρR（B）≤ρA（B），屬性粒B 的D-近似描述dD（B）=[d（Bl），d（Bu）]=[d{b，d}，d{b，c，d，f}]=[3，2∨┒1]，由公式（6）可得，D-描述精度ρD（B）=0.5，滿(mǎn)足ρA（B）≤ρD（B），即可證實(shí)ρR（B）≤ρA（B）≤ρD（B）成立。實(shí)際上，對(duì)于?B∈2M，均可證明ρR（B）≤ρA（B）≤ρD（B）成立。

4.2 與其他知識(shí)獲取方法的對(duì)比

通過(guò)構(gòu)建屬性粒，并對(duì)其進(jìn)行近似描述，在對(duì)形式概念描述的同時(shí)， 不可定義屬性集的描述問(wèn)題得以解決， 與概念格中只對(duì)形式概念進(jìn)行描述的研究相比， 本文對(duì)不可定義屬性集的描述則是對(duì)與模糊集理論來(lái)說(shuō)， 對(duì)挖掘更多的知識(shí)提供了可能性。

人們獲取知識(shí)的途徑有很多種，為了凸顯本文研究與其他方法的異同，本文選擇了幾種較為典型的知識(shí)挖掘方法進(jìn)行對(duì)比，具體如表6 所示。 可以看出，文本表征法是單一的文本表示，雖然成熟全面但已經(jīng)不適應(yīng)當(dāng)今知識(shí)獲取的途徑，超文本表征法是文本從靜態(tài)到動(dòng)態(tài)的新形態(tài)， 但其操作復(fù)雜，與用戶(hù)的交互性較差；FCA 表示法即用建格的方式直觀的表征信息， 具有層級(jí)性和交叉連接的特征；粒描述表示法也是本文的方法，在FCA 表示法的基礎(chǔ)上，通過(guò)粒化、構(gòu)建屬性粒的方式來(lái)處理形式背景，在獲取形式概念的知識(shí)的同時(shí)，對(duì)非形式概念的知識(shí)也有了表示的方法，即通過(guò)近似描述的方式可以獲取更全面的知識(shí)。

表6 知識(shí)挖掘的方法對(duì)比

5 結(jié) 論

粒計(jì)算是目前大數(shù)據(jù)方向最有效的解決問(wèn)題的方法之一，粒計(jì)算與形式概念分析理論的結(jié)合使得知識(shí)發(fā)現(xiàn)的過(guò)程更細(xì)致化，能夠更好的令讀者學(xué)習(xí)以及理解知識(shí)發(fā)現(xiàn)過(guò)程，本文通過(guò)從面向?qū)傩愿拍罡竦膬?nèi)涵角度定義了一元可定義屬性粒、二元可定義屬性粒以及M-三支概念格的構(gòu)造算法。 需要指出的是，文獻(xiàn)[20]從概念格基于必然屬性角度定義了一元描述子，二元描述子以及N-三支概念格，并對(duì)其進(jìn)行了描述，本文不僅通過(guò)屬性格角度對(duì)其進(jìn)行了擴(kuò)展，而且還對(duì)M-三支概念格的構(gòu)造算法進(jìn)行了描述，通過(guò)驗(yàn)證可證實(shí)研究的有效性，使得面向?qū)ο蟾拍罡窈兔嫦驅(qū)傩愿拍罡衽c粒計(jì)算的結(jié)合更為豐富。

為了更好地實(shí)現(xiàn)通過(guò)面向?qū)傩愿拍罡駥?duì)屬性粒的構(gòu)建，還需要進(jìn)一步的研究工作，主要包含：

1）面向?qū)傩愿拍罡窠ㄔ斓膶傩粤?huì)隨著屬性約簡(jiǎn)后變更，則變更后的動(dòng)態(tài)更新問(wèn)題需要進(jìn)一步解決；

2）如何降低M-三支概念格構(gòu)造算法的時(shí)間復(fù)雜度需要進(jìn)一步思考。