面向屬性概念的屬性粒構建

吳克晴, 陳希邦

（江西理工大學理學院，江西 贛州341000）

0 引 言

粒計算(Granular Computing,GrC)首先由Zadeh教授[1]提出。 粒計算是通過信息?；^程將復雜的問題進行分解、 轉化得到多個相對簡單的子問題，然后再對這些簡單的子問題進行處理，從而實現(xiàn)對復雜問題的求解[2]。粒計算的基礎是信息粒化，即在給定的粒化準則下，粒化的過程是通過對問題空間的劃分產生多個信息粒，這些?？梢杂脕砻枋鰡栴}本身所包含的一些信息，粒之間的偏序關系就形成了多層次的粒結構。 粒計算的思想應用于各種領域，如結構化問題的求解、結構化信息處理等[3-4]。

形式概念分析[5]與粗糙集[6]在1982 年同時被提出， 許多學者都認為它們是很有效的粒計算的方法，并且兩者之間有著極強的互補性。

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

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

文獻[20]主要通過面向對象概念格的角度對其進行了研究，而在研究中，作者并沒有從面向屬性概念角度進行研究，因此，文中在文獻[20]的基礎上進一步擴展，首先是對屬性粒的描述，然后給出一元可定義屬性粒、一元屬性描述子的描述、二元可定義屬性粒、二元屬性描述子的描述，最后通過對比驗證可以證明其有效性。

1 基本概念

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

1.1 形式概念分析與概念格

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

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

定義3[21]設（G，M，I）為形式背景，A?G，B?M。 有A□=B 且B◇=A，則稱序對（A，B）為面向對象概念；若A◇=B 且B□=A，則稱序對（A，B）為面向屬性概念。

本文主要通過對面向屬性概念的研究， 稱A為面向屬性概念（A，B）的外延，B 為面向屬性概念（A，B）的內涵，在不產生歧義的情況下，統(tǒng)稱A 為外延，B 為內涵[21]。

定義4[21]設C1=（A1，B1），C2=（A2，B2）是形式背景K=（G，M，I）上的兩個面向屬性概念，若存在A1?A2，則有C1≤C2，稱關系≤是概念的“層次序”，（簡稱“序”）；如果不存在概念（A3，B3）使得A1?A3?A2， 則稱C1是C2的直接子概念，C2是C1的直接父概念，記做C1＜C2。K=（G，M，I）的所有面向屬性概念用這種序組成的集合稱為面向屬性概念格，記做LA=（G，M，I）。

1.2 面向屬性概念格的構建

本小節(jié)主要從粗糙集中的下近似角度出發(fā)，通過使用“*”算子，來構建面向屬性概念格[22]。

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

算法1 由下近似出發(fā)，構建面向屬性概念格：

Step1：分別計算g＊i，其中gi∈G；

表1 形式背景

Step2：計算P（M）中的元素；

Step3：逐一判斷P（M）中的每一個元素是否滿足g＊i?B 且g＊i?B，其中B?M，若滿足，則（∪gi，B）為一個面向屬性概念；否則（∪gi，B）舍去；

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

根據(jù)上述算法，對例1 所示的形式背景可以通過下近似構建其面向屬性概念格，如圖1 所示。

圖1 例1 形式背景的面向屬性概念格

1.3 粒的描述

粒計算作為一種新興的計算方法，它為相關研究領域提供了基于信息?；瘉斫鉀Q復雜問題的理論框架，是當前計算機領域中解決復雜問題和核心技術之一。 近幾年來，許多研究學者通過粒計算的理論知識來研究知識發(fā)現(xiàn)領域的一些問題。

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

同理，定義一個屬性論域M，M 中所有可能的粒組成的冪集，記做2M，與屬性集對應的對象集用論域G 表示，其二元關系同樣可以有I：G×M。

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

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

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

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

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

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

文獻[20]中提出了正文字可定義粒并對其性質進行了分析，本節(jié)從面向屬性概念格角度探索性的定義了正文字可定義屬性粒。

定義7 一個形式背景K=（G，M，I），B?2M，若存在一個面向屬性概念C∈L（K），有C 的內涵為B，則B 稱為一個正文字可定義屬性粒。

在形式概念分析中，文獻[20]采用最小產生子來表達一個概念的核心屬性，類似地，本文定義最小對象產生子來表達一個概念的核心對象。

定義8 一個凈化的面向屬性概念C=（A，B），設X?A，有X◇=A◇=B，且對于任意的S?X，有S◇?A◇，則稱X 是概念C 的一個最小對象產生子。

對于最小對象產生子的方法與文獻[20]中最小產生子的方法類似，這里則不進一步描述。

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

表2 正文字可定義屬性粒及其最小對象產生子

2.2 負文字可定義屬性粒的描述

對于面向屬性概念格， 有正文字可定義屬性粒，就會存在負文字可定義屬性粒，而負文字可定義屬性粒是針對形式背景的補背景而言的。 對例1的形式背景K=（G，M，I），G＝{1，2，3，4，5}，M＝{a，b，c，d，e，f}，其補背景Kc=（G，M，Ic）如表3 所示。

表3 形式背景的補背景

表3 的形式背景Kc的面向屬性概念格如圖2所示。

圖2 面向屬性概念格L（Kc）

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

表4 負文字可定義屬性粒及其最小對象產生子

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

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

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

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

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

上一節(jié)中主要通過定義正文字可定義屬性粒和負文字可定義屬性粒，以及探索面向屬性概念的最小產生子來對屬性粒進行描述。在對屬性粒的描述中，為了提高其精度，需要同時用到原形式背景以及其補背景所包含的信息，因此，本節(jié)將提出基于二元屬性描述子的二元可定義屬性粒，并提出基于二元可定義屬性粒的M-三支概念格及其構建算法。

定義9定義一個形式背景K=（G，M，I），其中U，V?G，B?M，若（U，V）□=B，且B◇=（U，V），稱（（U，V），B）為屬性誘導的三支概念，簡稱M-三支概念，其中（U，V）為M-三支概念的外延。

這里對由對象誘導的三支概念不做贅述。

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

M-三支概念之間的偏序關系可以定義為：（（U1，V1），B1）≤（（U2，V2），B2）?B1≤B2，則 稱 形 式背景的所有M-三支概念滿足偏序關系≤構成一個完備格，記為屬性誘導的三支概念格，簡稱M-三支概念格，記做LM（K）。

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

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

定義11一個M-三支概念C=（（U，V），B）∈LM（K），設（u，v）?（U，V），有（u，v）◇=（U，V）◇=B，且對于任意的（u1，v1）?（U，V），有（u1，v1）◇?（U，V）◇，則稱（u，v）是概念C 的一個最小對象產生子。

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

3.2 算法描述

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

算法2

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

Step2：計算補背景Kc=（G，M，Ic）；

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

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

Step5：計算P=（M）中的元素；

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

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

該形式背景所對應的M-三支概念、二元可定義屬性粒和最小產生子如表5 所示。

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

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

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

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

4 對比驗證

4.1 三種近似描述的對比驗證

圖3 M-三支概念格

表5 二元可定義屬性粒及其最小對象產生子

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

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

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

對于例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，滿足ρ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，滿足ρA（B）≤ρD（B），即可證實ρR（B）≤ρA（B）≤ρD（B）成立。實際上，對于?B∈2M，均可證明ρR（B）≤ρA（B）≤ρD（B）成立。

4.2 與其他知識獲取方法的對比

通過構建屬性粒，并對其進行近似描述，在對形式概念描述的同時， 不可定義屬性集的描述問題得以解決， 與概念格中只對形式概念進行描述的研究相比， 本文對不可定義屬性集的描述則是對與模糊集理論來說， 對挖掘更多的知識提供了可能性。

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

表6 知識挖掘的方法對比

5 結 論

粒計算是目前大數(shù)據(jù)方向最有效的解決問題的方法之一，粒計算與形式概念分析理論的結合使得知識發(fā)現(xiàn)的過程更細致化，能夠更好的令讀者學習以及理解知識發(fā)現(xiàn)過程，本文通過從面向屬性概念格的內涵角度定義了一元可定義屬性粒、二元可定義屬性粒以及M-三支概念格的構造算法。 需要指出的是，文獻[20]從概念格基于必然屬性角度定義了一元描述子，二元描述子以及N-三支概念格，并對其進行了描述，本文不僅通過屬性格角度對其進行了擴展，而且還對M-三支概念格的構造算法進行了描述，通過驗證可證實研究的有效性，使得面向對象概念格和面向屬性概念格與粒計算的結合更為豐富。

為了更好地實現(xiàn)通過面向屬性概念格對屬性粒的構建，還需要進一步的研究工作，主要包含：

1）面向屬性概念格建造的屬性粒會隨著屬性約簡后變更，則變更后的動態(tài)更新問題需要進一步解決；

2）如何降低M-三支概念格構造算法的時間復雜度需要進一步思考。