張曉燕，王佳一

（西南大學(xué) 人工智能學(xué)院，重慶 400715）

0 引言

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

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

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

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

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

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

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

1.1 概念格

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

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

特別地，當(dāng)對(duì)象子集或?qū)傩宰蛹袃H有一個(gè)元素時(shí)，記{x}*為x*，記{m}*為m*。

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

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

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

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

1.2 三支概念格

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

為了研究共同不具有的關(guān)系，下面給出負(fù)算子［19］的定義。對(duì)于子集X?G，A?M，有：

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

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

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

類似地，對(duì)于上下近似算子，也有相似的負(fù)算子定義：

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

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

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

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

1.3 屬性聚類

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

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

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

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

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

2.1 屬性聚類的推廣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例3（續(xù)例2）針對(duì)例2 給出的四個(gè)概念格，計(jì)算相應(yīng)的eOER及eAER。

3 結(jié)語

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