屬性聚類下三支概念的對比

張曉燕，王佳一

（西南大學 人工智能學院，重慶 400715）

0 引言

形式概念分析［1］作為一種數(shù)據(jù)分析和知識處理的數(shù)學工具，它的主要思想是以形式背景為研究對象，以形式概念與概念格為核心概念，通過概念之間的偏序關系刻畫對象和屬性的內(nèi)在關系［2］。因此，該理論是一種非常有效的可視化數(shù)據(jù)處理方法。然而，傳統(tǒng)的形式概念分析理論只研究了數(shù)據(jù)“共同（被）具有”關系的問題，而忽略了“共同不（被）具有”關系的問題［3-4］，導致現(xiàn)實應用中該理論具有一定的局限性［5］。

2014 年，Qi 等［6］提出了新的形式概念分析理論，即三支概念分析。三支概念分析是將三支決策理論與概念格相融合，提出了對象誘導的三支概念格與屬性誘導的三支概念格。這兩種三支概念格均同時研究了“共同（被）具有”和“共同不（被）具有”的關系。它們獲得的概念更加精確，構(gòu)建的三支概念格相較于以往經(jīng)典概念格，在實際應用過程中概念識別也會更加精確。

在三支概念正式提出后，許多學者對此進行了擴展和深入研究。Qian 等［7］利用形式背景的疊置與并置，提出了三支概念格的構(gòu)造方法，并仿照對象誘導概念格與屬性誘導概念格給出了對象誘導的三支面向?qū)ο蟾拍罡窈蛯傩哉T導的三支面向?qū)傩愿拍罡竦亩x，分析了四種概念之間的異同。蘇新等［8］比較研究了基于對象和基于屬性的三支概念格合并方法。Wei 等［9］立足于三支概念格，在三支協(xié)調(diào)的意義下研究了決策背景的規(guī)則獲取問題，并與強協(xié)調(diào)決策背景所獲得的一般決策規(guī)則進行了詳細的比較研究。

除了對三支概念本身的研究外，學科交叉融合也極大擴展了三支概念的前景。Li 等［10］將多粒度與三支概念結(jié)合，研究了基于多粒度的三支認知概念學習模型。龍柄翰等［11］建立了模糊三支概念分析，將模糊集理論與三支概念分析相融合，重點考慮模糊背景中“共同具有的程度”與“共同不具有的程度”兩方面不確定的共性信息，為三支概念在模糊領域的實際應用奠定了較好的基礎。

在多粒度研究方面，對象?；?、屬性?；约瓣P系?；雀拍睿?2-13］的提出將多粒度與概念認知聯(lián)系起來。這些研究緩解了龐大的概念個數(shù)，在約束寬松的情況下減小了時間空間復雜度，并且為獲取數(shù)據(jù)的多層次概念知識表示與處理方法提供了新的方法［14］。多粒度方面的研究主要包括對象（屬性）的粗化與細化研究。屬性?；卜Q為屬性的吸收和分解，在?；^程中概念也會隨之轉(zhuǎn)化，從而可以獲得在不同粒度空間的形式概念。另外，Belohlavek 等［15］通過粒度樹與剪枝研究了給予屬性?；男问礁拍罘治龇椒?，從而生成不同粒度層次的形式背景。然而，剪枝的構(gòu)造過程中要求不同粒度層次的屬性在某種意義上存在偏序關系。這一條件較為苛刻，甚至難以實現(xiàn)?；诖朔N局限，Liu 等［16］推廣了該方法，提出了屬性聚類的概念，即設定一個等價類條件，再以此為基礎進行屬性吸收，從而構(gòu)建多粒度層次。

然而，在多粒度層次方面，對三支概念的研究尚且不足。同時，目前的研究無法通過粒度轉(zhuǎn)化直接得到多粒度概念格和多粒度三支概念格，這對于多個粒度層次下的分析十分不利，且需要大量冗余的計算［17］。針對該情況，本文提出以屬性聚類為基礎的三支概念構(gòu)建，并重點研究不同概念格下的三支概念轉(zhuǎn)化，進一步豐富三支形式概念分析理論。

1 基礎知識

1.1 概念格

設有形式背景K=(G，M，I)，其中：G為對象集，M為屬性集，I為G和M之間的二元關系。在經(jīng)典形式背景中，I的取值只有0 或1 兩種可能。對于x∈G，m∈M，當I(x，m)=1時，表示對象x和屬性m存在關系I；當I(x，m)=0 時，表示對象x和屬性m不存在關系I。

為研究對象子集和屬性子集之間的關系，現(xiàn)給出兩個導出算子，分別作用于屬性子集和對象子集，對于X?G，A?M，有：

特別地，當對象子集或?qū)傩宰蛹袃H有一個元素時，記{x}*為x*，記{m}*為m*。

對于形式背景K=(G，M，I)，若對于X?G，A?M，有X*=A且A*=X，則(X，A)稱為一個形式概念，其中概念的外延為X，概念的內(nèi)涵為A。形式背景K=(G，M，I)下的所有形式概念的集合為L(K)，L(K)即為概念格［18］。

概念的上下近似算子定義如下：

由上可知，上下近似算子將本身較為嚴格的概念格約束放寬，使概念格更具實際意義。根據(jù)上下近似算子，可以定義新的算子形成面向?qū)ο蠛兔嫦驅(qū)傩缘母拍罡瘛?/p>

對于形式背景K=(G，M，I)，若對于X?G，A?M，有Xu=A且Ad=X，則(X，A)稱為面向?qū)傩缘母拍?。在形式背景下，所有面向?qū)傩缘母拍罘Q為面向?qū)傩愿拍罡瘢碙p(K)。進一步，若有Xd=A且Au=X，則(X，A)可被稱為面向?qū)ο蟮母拍?。所有面向?qū)ο蟮母拍罘Q為面向?qū)ο蟾拍罡瘢碙O(K)。

1.2 三支概念格

如果說概念格研究的是共同具有的關系，那么三支概念格就是同時研究共同具有和共同不具有兩個關系。在應用中，單方面的研究往往具有片面性，從正反兩方面研究能使研究結(jié)果更精準，提高概念分析的正確率。

為了研究共同不具有的關系，下面給出負算子［19］的定義。對于子集X?G，A?M，有：

顯然，通過負算子可以表示并研究形式背景的“共同不具有”這一關系。但如果需要同時研究具有和不具有的關系，還需要定義一對算子。需要特別說明的是，單個對象子集在運算后會得到兩個屬性子集，即共同具有的屬性和共同不具有的屬性。同理，單個屬性子集在運算后也會得到兩個對象子集。因此，由于出發(fā)點的不同，可以得到下面兩種三支概念。

對 于X?G和A，B?M：XO=(X*，)，(A，B)O=A*∩。當XO=(A，B)且(A，B)O=X，則稱(X，(A，B))為對象誘導的三支概念，簡稱OE 概念，其中X為OE 概念的外延，(A，B)為OE 概念的內(nèi)涵。

對 于X，Y?G和A?M：AA=(X，Y)A=X*∩。當AA=(X，Y)且(X，Y)A=A時，則稱((X，Y)，A)為屬性誘導的三支概念，簡稱AE 概念，其中(X，Y)為AE 概念的外延，A為AE 概念的內(nèi)涵。

類似地，對于上下近似算子，也有相似的負算子定義：

于是，根據(jù)負算子可以有面向?qū)ο笕Ц拍詈兔嫦驅(qū)傩缘娜Ц拍?。對于X?G和A，B?M，定義：XO＇=(Xd，)，(A，B)O＇=Au∩當XO＇=(A，B) 且(A，B)O＇=X，則 稱(X，(A，B))為面向?qū)ο蟮娜Ц拍睿喎QOEO 概念，其中X為OEO 概念的外延，(A，B)為OEO 概念的內(nèi)涵。在形式背景K=(G，M，I)中，所有對象誘導的面向?qū)ο笕Ц拍畹募媳环Q為對象誘導的面向?qū)ο笕Ц拍罡瘢洖镺EOL(K)。

對 于X，Y?G和A?M，定 義：AA＇=(Ad，)，(X，Y)A＇=Xu∩。當AA＇=(X，Y)且(X，Y)A＇=A時，稱((X，Y)，A)為面向?qū)傩缘娜Ц拍睿喎QAEP 概念，其中(X，Y)為AEP 概念的外延，A為AEP 概念的內(nèi)涵。在形式背景K=(G，M，I)中，所有屬性誘導的面向?qū)傩匀Ц拍畹募媳环Q為屬性誘導的面向?qū)傩匀Ц拍罡?，記為AEPL(K)。

無論是OE 概念、AE 概念、OEO 概念還是AEP 概念，均在定義中利用了負算子，即同時研究了共同具有和共同不具有的問題，它們的區(qū)別在于概念形成的過程和約束。

對于形式背景K=(G，M，I)，給定任意x∈G和m∈M，則有下列結(jié)論成立：

1.3 屬性聚類

在實際應用中，形式背景往往包括大量的屬性和對象，但在某個具體的研究中，往往不需要研究全部的屬性，因此屬性約簡或?qū)傩晕站惋@得尤為重要。屬性聚類作為一種較為通用的屬性吸收方法，是基于粒度樹和剪枝的屬性粒化的推廣。屬性聚類的獲取過程更簡便，不要求聚類之前與之后的屬性存在實際意義上的偏序關系，因此也具有更好的適用性。

屬性聚類的特征是基于某種特定需求或者先驗關系的。通過等價關系的作用，部分屬性被聚合起來，形成新的屬性（集）。需要特別說明的是，雖然新的屬性集中元素均是以聚類之前的屬性為元素的集合，但在新的形式背景下，每個集合被看作一個整體，被稱為新的屬性。

對于形式背景K=(G，M，I)，R為先驗關系或特定關系確立的等價關系，[m]R為包含屬性m的屬性等價類，屬性聚類后形成的新形式背景(G，MR，IR)［12］如下：

相較于舊的形式背景，新的形式背景的對象集相同，但屬性集發(fā)生了變化，新的屬性和舊的屬性存在包含與被包含關系，屬性聚類是一個由細粒度到粗粒度的過程。因此，在屬性聚類下，可以在不同層次、不同粒度下進行研究。

2 屬性聚類前后三支概念的變化

2.1 屬性聚類的推廣

在第1 章屬性聚類過程中定義對應關系時，采用了樂觀定義方法，即在構(gòu)成新屬性的屬性集中，只要有一個屬性可以與對象x構(gòu)成關系I，那么新的屬性就與對象x構(gòu)成關系IR。這在應用中會存在一定的局限性。如在日常生活中，常常會遇到以下語境——“以下五條條件中符合三條的獲得評比資格”或者“符合以下所有條件的獲得評比資格”。這便是不同的屬性聚類方式。

為解決此類問題，下面定義悲觀屬性聚類和一般屬性聚類。

定義1對于形式背景K=(G，M，I)，R為先驗關系或特定關系確立的等價關系，[m]R為包含屬性m的屬性等價類，悲觀屬性聚類后形成的新形式背景(G，)如下：

顯然，樂觀屬性聚類與悲觀屬性聚類均為一般屬性聚類的特殊情況：當N(m)=1 時，為樂觀屬性聚類；當N(m)=|[m]R|時，為悲觀屬性聚類。因此，在研究屬性聚類性質(zhì)的時候，只需要研究一般屬性聚類的性質(zhì)然后通過改變N(m)取值研究樂觀屬性聚類與悲觀屬性聚類的情況。

例1 表1 為某形式背景K=(G，M，I)，現(xiàn)給出一組R等價類的選取方式以及兩組不同的N(m)取值，構(gòu)建兩個形式背景和如表2。

表1 形式背景 K=(G，M，I)Tab.1 Formal context K=(G，M，I)

現(xiàn)給出一組等價類R的構(gòu)造方法，即歸屬于同一等價類的屬性，在此定 義下均 為等價：[a]R={a，b，c，d}，[e]R={e，f，g，h}，[i]R={i，j，k}。

給出兩組([m]R，N(m))的取值，用來比較研究N(m)取值的大小對屬性聚類結(jié)果的影響：

根據(jù)此給出如表2 所示的兩個形式背景。

2.2 屬性聚類下三支概念格的表示

為了研究在屬性聚類后三支概念的影響，建立在同一對象集下，屬性聚類前后三支概念的聯(lián)系，故在本文中利用等價類的方式表示屬性集。對于屬性集M={m1，m2，…，mn}，在聚類后以等價類的方式表示為：

證明 這里只證明1）、3）、5）、7）、9），其余證明過程類似。

由定義3 可知，R粒度一般屬性聚類形式概念也是概念，符合基本概念的相關性質(zhì)。

定 義4當存在一組XOR=(A，B) 且(A，B)OR=X，則(X，(A，B))為R粒度一般屬性聚類對象誘導的三支概念，簡稱為OER 概念，其中X為OER 概念的外延，(A，B)為OER 概念的內(nèi)涵。記所有OER 概念為OER 概念格，即OERL()。

定 義5當存在一組AAR=(X，Y) 且(X，Y)AR=A時，((X，Y)，A)為R粒度一般屬性聚類下屬性誘導的三支概念，簡稱為AER 概念，其中(X，Y)為AER 概念的外延，A為AER概念的內(nèi)涵。記所有AER 概念為AER 概念格，即AERL()。

于是可得OER 概念與AER 概念均為三支概念，滿足三支概念相關性質(zhì)。

2.3 屬性聚類前后三支概念的比較

在多粒度形式概念的構(gòu)造中，往往采用分別構(gòu)建的方法，這就造成了大量冗余計算以及資源的浪費。事實上，在構(gòu)建多粒度過程中，不同粒度的形式背景存在關聯(lián)。這種關聯(lián)可以作為推導路徑，輔助構(gòu)建多粒度形式概念。

在R水平一般屬性聚類之后，新的屬性由原屬性集組成，新的對應關系可由原對應關系表示。任何原屬性集中的屬性，都能在新屬性集中找到對應小屬性集合包含，且該屬性集合的存在是唯一的。

三支概念的一種較為簡單的獲取方式是利用Ⅰ型混合背景與Ⅱ型混合背景，這種方法比直接利用定義求解更加迅速直觀。在經(jīng)過R水平一般屬性聚類后，經(jīng)原則計算，新形成的屬性要么與某對象存在關系，要么不存在關系。以OE 概念與OER 概念(X，(A，B))為例，對于確定的對象集X，在其聚類前的屬性集合對(A，B)，與其聚類后的屬性集合對（如果存在），記為(AR，BR)。任取AR中的元素[m]R，必有超過N(m)個元素與對象集X中任意元素存在關系I。且根據(jù)等價類的提取原則，AR中各個[m]R交集為空。即有：

同理，任取BR中的元素[m]R，必有超過個元素與對象集X中任意元素不存在關系I。且根據(jù)等價類的提取原則，BR中各個[m]R交集為空。即有：

對此可以看出，經(jīng)過屬性聚類的三支概念事實上是對本身嚴格的約束條件予以放松處理。但是，該放松處理并不是無限放松，而是有一定限度的。接下來，給出最低約束指數(shù)的定義來度量這種放松限度。

根據(jù)其性質(zhì)，也可記為：

顯然，eOER的大小與等價類R以及N(m)有關。因此，在進行屬性約簡時，如果等價類R已確定，可以通過調(diào)整N(m)的設定提高eOER；如果N(m)已經(jīng)確定，可以通過調(diào)整等價類R提高eOER。

于是，可知以下性質(zhì)成立：

性質(zhì)2 對于AE 概念和AER 概念((X，Y)，A)，以及指定的對象集合對(X，Y)，記由I和確定的屬性集分別為A與AR。對于任取[m]R∈AR，必有[m]R∈X*R且[m]R∈，則對于[m]R必須同時滿足：

顯然，類似于最低OER 約束指數(shù)，eAER的大小依然與等價類R以及N(m)有關。因此，在進行屬性約簡時候，如果等價類R已確定，可以通過調(diào)整N(m)的設定來提高eAER；如果N(m)已經(jīng)確定，可以通過調(diào)整等價類R來提高eAER。

例3（續(xù)例2）針對例2 給出的四個概念格，計算相應的eOER及eAER。

3 結(jié)語

本文是對多粒度屬性聚類和三支概念的融合。首先，將屬性聚類推廣為一般屬性聚類、樂觀屬性聚類與悲觀屬性聚類三種情況；然后通過對比屬性聚類前后三支概念的構(gòu)成，定義了度量屬性聚類對三支概念的放松影響的兩個指數(shù)；接著研究發(fā)現(xiàn)屬性聚類過程中等價類的選取以及約束條件的選擇是影響指數(shù)大小的兩個因素，進一步完善了三支概念分析理論。