面向?qū)傩缘膮^(qū)間集概念格*

賀曉麗，魏 玲，錢 婷

1.西北大學(xué) 數(shù)學(xué)學(xué)院，西安 710127

2.西安石油大學(xué) 理學(xué)院，西安 710065

1 引言

形式概念分析[1-2]（formal concept analysis，F(xiàn)CA）是由德國數(shù)學(xué)家Wille于1982年以重建格理論為目的提出的一種數(shù)學(xué)理論。它的數(shù)據(jù)表現(xiàn)形式為二維交叉表即形式背景。形式背景(G,M,I)是一個由對象集G，屬性集M以及G與M間二元關(guān)系I構(gòu)成的三元組。在形式背景上，通過一對伽羅瓦連接可以形成概念(X,B)，其中X為概念的外延，是屬于這個概念的所有對象的集合；而B為內(nèi)涵，是所有這些對象所共同具有的屬性（或特征）集。概念格是知識的一種表現(xiàn)形式，也是數(shù)據(jù)處理的一種工具。

形式概念分析與其他理論的融合研究是其理論研究的一個重要方面，迄今為止已產(chǎn)生諸多頗有意義的研究成果。例如，與三支決策理論結(jié)合，祁建軍等人[3]提出了三支形式概念分析理論；與粒計(jì)算理論相結(jié)合，Belohlávek等人[4]給出了多尺度形式背景中的概念格構(gòu)建理論與算法，在此方面更為詳細(xì)的研究可參看李金海和吳偉志[5]所給出的綜述研究；與模糊集理論相結(jié)合，Belohlávek[6-8]提出了模糊形式背景和模糊概念格；與粗糙集理論相結(jié)合，Düntsch和Gediga[9]提出了面向?qū)傩愿拍罡?，類似地，Yao[10]定義了面向?qū)ο蟾拍罡?。與描述不完備信息的區(qū)間集理論相結(jié)合，馬建敏等人[11]引入了區(qū)間集概念格。其本質(zhì)思想是把概念中表示外延與內(nèi)涵的集合推廣到區(qū)間集，利用區(qū)間集所反映的不確定信息把經(jīng)典概念擴(kuò)展到區(qū)間集概念。隨后，對區(qū)間集概念格的構(gòu)造理論進(jìn)行了研究[12]。在不完備形式背景上，Yao[13]提出了區(qū)間集算子，并對李金海等人[14]提出的近似概念格進(jìn)行了相應(yīng)的區(qū)間集表示。

已經(jīng)知道，面向?qū)傩愿拍罡袷谴植诩c概念格相結(jié)合的一種數(shù)據(jù)分析理論，鑒于粗糙集與區(qū)間集更為密切的聯(lián)系，本文擬將區(qū)間集思想引入到面向?qū)傩愿拍罡窨蚣苤?，給出了面向?qū)傩缘膮^(qū)間集概念格構(gòu)造方法及相應(yīng)的建格算法。

本文組織結(jié)構(gòu)如下：第2章回顧概念格、面向?qū)傩愿拍罡窈蛥^(qū)間集等相關(guān)定義；第3章提出一對新的伽羅瓦連接，并在此基礎(chǔ)上定義了面向?qū)傩缘膮^(qū)間集概念及面向?qū)傩缘膮^(qū)間集概念格；進(jìn)一步研究面向?qū)傩愿拍罡衽c面向?qū)傩缘膮^(qū)間集概念格之間的關(guān)系，同時給出面向?qū)傩缘膮^(qū)間集概念格的構(gòu)造方法及相應(yīng)的建格算法；第4章進(jìn)行了總結(jié)和展望。

2 基礎(chǔ)知識

定義1[1]設(shè)(G,M,I)為一形式背景，對象集X?G和屬性集A?M上定義了一對對偶算子如下：

若X?=A且A*=X，則稱(X,A)為形式背景(G,M,I)的一個概念。記形式背景(G,M,I)的所有概念構(gòu)成的集合為L(G,M,I)，在L(G,M,I)上，定義二元關(guān)系“≤”為：

(L(G,M,I),≤)在偏序關(guān)系“≤”形成完備格，稱(L(G,M,I),≤)為概念格。

定義2[9]設(shè)(G,M,I)為一形式背景，↑和↓是2G與2M之間的一對算子，X↑={m∈M|m*?X≠?}A↓={g∈G|g*?A}。若X↑=A且A↓=X，則稱 (X,A)為面向?qū)傩愿拍睢Ｆ渲?，X為面向?qū)傩愿拍畹耐庋?，A為面向?qū)傩愿拍畹膬?nèi)涵。記形式背景(G,M,I)的所有面向?qū)傩愿拍顦?gòu)成的集合為PL(G,M,I)。在PL(G,M,I)上，定義二元關(guān)系 ≤ 為：(X1,A1)≤(X2,A2)?X1?X2(A1?A2)。容易證明“≤”是偏序關(guān)系且(PL(G,M,I),≤)在偏序關(guān)系“≤”形成完備格，即任意的兩個概念(X1,A1),(X2,A2)的上確界和下確界為：

稱(PL(G,M,I),≤)為面向?qū)傩愿拍罡瘛?/p>

定義3[15]設(shè)U是有限論域，2U為U的冪集。定義X=[X1,X2]={XΔ∈2U|X1?XΔ?X2}，稱為U的區(qū)間集。對于任意的X∈2U，X可以看成是由區(qū)間集[X,X]退化得到的。U上所有的區(qū)間集構(gòu)成的集合記為I(2U)。類似于經(jīng)典集合之間的運(yùn)算，Yao給出了區(qū)間集間的運(yùn)算[15]。

定義4[15]設(shè)U是有限論域，X,Y是U上的區(qū)間集，即X=[X1,X2]，Y=[Y1,Y2]∈I(2U)，定義：

3 面向?qū)傩缘膮^(qū)間集概念格

3.1 面向?qū)傩缘膮^(qū)間集概念格的定義

定義5設(shè)(G,M,I)為一形式背景，對于任意的X=[X1,X2]∈I(2G)，A=[A1,A2]∈I(2M)，定義I(2G)與I(2M)之間的一對算子?:I(2G)→I(2M)和?:I(2M)→I(2G)如下：

例1(G,M,I)為一個形式背景（如表1所示），其中G={1,2,3}，M={a,b,c}。

取X=[3,13]∈I(2G),A=[c,ac]∈I(2M)，按照定義5，有 [3,13]?=[3↑,13↑]=[c,ac]，[c,ac]?=[c↓,ac↓]=[3,13]。

Table 1 Formal context(G,M,I)表1 形式背景(G,M,I)

性質(zhì)1設(shè)(G,M,I)為一形式背景，對于任意的X=[X1,X2]∈I(2G)，A=[A1,A2]∈I(2M)，I(2G)與I(2M)之間的一對算子?:I(2G)→I(2M)和?:I(2M)→I(2G)，則?和?具有以下性質(zhì)：

（1）X?Y?X??Y?

（2）A?B?A??B?

（3）X?X??,A???A

（4）X=X???,A???=A

（5）(X?Y)?=X??Y?,(A?B)?=A??B?

證明下面僅證明（5）。

類似可證明(A?B)?=A??B?。 □

定義6設(shè)(G,M,I)為一形式背景，?X∈I(2G),A∈I(2M)，若X?=A且A?=X,則稱 (X,A)為面向?qū)傩缘膮^(qū)間集概念。其中，X稱為面向?qū)傩缘膮^(qū)間集概念的外延，A稱為面向?qū)傩缘膮^(qū)間集概念的內(nèi)涵。

記形式背景(G,M,I)的所有面向?qū)傩缘膮^(qū)間集概念構(gòu)成的集合為PIL(G,M,I)，所有面向?qū)傩缘膮^(qū)間集概念的外延構(gòu)成的集合為PILG(G,M,I)，所有面向?qū)傩缘膮^(qū)間集概念的內(nèi)涵構(gòu)成的集合為PILM(G,M,I)，定義PIL(G,M,I)上的二元關(guān)系為：(X,A)≤(Y,B)?X?Y(A?B)。

很容易證明上述的二元關(guān)系“≤”是偏序關(guān)系且在此偏序關(guān)系下，PIL(G,M,I)形成完備格，即對任意的兩個概念(X,A)、(Y,B)的下確界和上確界分別如下所示：

例2（續(xù)例1） 因?yàn)閄=[3,13],A=[c,ac]，由例1知X?=[c,ac]=A,A?=[3,13]=X，所以由定義6知 (X,A)是面向?qū)傩缘膮^(qū)間集概念。類似地，可以求出此形式背景的所有面向?qū)傩缘膮^(qū)間集概念及其相應(yīng)的面向?qū)傩缘膮^(qū)間集概念格PIL(G,M,I)。格圖如圖1所示。

Fig.1 Property oriented interval-set concept lattice of Table 1圖1 表1的面向?qū)傩缘膮^(qū)間集概念格

3.2 面向?qū)傩愿拍罡衽c面向?qū)傩缘膮^(qū)間集概念格的關(guān)系

本節(jié)從元素、集合及代數(shù)結(jié)構(gòu)的角度研究面向?qū)傩愿拍罡衽c面向?qū)傩缘膮^(qū)間集概念格之間的關(guān)系。

為了研究集合PIL(G,M,I)與集合PL(G,M,I)之間的關(guān)系，記：

定理3設(shè)(G,M,I)為一個形式背景，PL(G,M,I)為其相應(yīng)的面向?qū)傩愿拍罡?，PIL(G,M,I)為其相應(yīng)的面向?qū)傩缘膮^(qū)間集概念格，則下列式子成立：

上面定理1及定理2從元素上研究了面向?qū)傩愿拍罡衽c面向?qū)傩缘膮^(qū)間集概念格間的關(guān)系，而定理3從集合整體上進(jìn)一步研究了兩者之間的關(guān)系。下面將從代數(shù)結(jié)構(gòu)上探討兩者之間的關(guān)系。

定理4設(shè)(G,M,I)為一個形式背景，PL(G,M,I)為其相應(yīng)的面向?qū)傩愿拍罡?，PIL(G,M,I)為其相應(yīng)的面向?qū)傩缘膮^(qū)間集概念格，則存在一個映射f:PL(G,M,I)→PIL(G,M,I)使得f(PL(G,M,I))是PIL(G,M,I)的一個子格。

證明對于任意的(X,A)∈PL(G,M,I)，定義f(X,A)=([X,X],[A,A])。由定理1知 ([X,X],[A,A])∈PIL(G,M,I)，故f是從PL(G,M,I)到PIL(G,M,I)的一個映射。從而f(PL(G,M,I))是PIL(G,M,I)的一個非空子集。下面證明f(PL(G,M,I))對∧，∨封閉。

（1）對于任意的 ?1,?2∈f(PL(G,M,I))，存在 (X,A)，(Y,B)∈PL(G,M,I)，使得：

由定義6知：

由面向?qū)傩愿拍罡裰械纳洗_界定義知，對于上述的 (X,A),(Y,B)∈PL(G,M,I)，則 (X,A)∨(Y,B)=((X?Y)↑↓,A?B)∈PL(G,M,I)，由f的定義知：

因此?1∨?2∈f(PL(G,M,I))。

（2）對于任意的 ?1,?2∈f(PL(G,M,I))，存在(X,A),(Y,B)∈PL(G,M,I)，使得：

由面向?qū)傩愿拍罡裰邢麓_界的定義知，對于(X,A),(Y,B)∈PL(G,M,I)，則：

因此，由f的定義知：

從而，?1∧?2∈PIL(G,M,I)。故f對∧封閉。

綜上所述f(PL(G,M,I))是PIL(G,M,I)的一個子格。 □

定理5設(shè)(G,M,I)為一個形式背景，PL(G,M,I)為相應(yīng)背景的面向?qū)傩愿拍罡瘢魧τ谌我獾?X1,A1)，(X2,A2)∈PL(G,M,I)且X1?X2，則：

因此(X,A)∈PIL(G,M,I)。 □

3.3 面向?qū)傩缘膮^(qū)間集概念格的構(gòu)造

基于上述二者之間的關(guān)系，給出面向?qū)傩缘膮^(qū)間集概念格的構(gòu)造方法。

定理6設(shè)(G,M,I)為一個形式背景，PL(G,M,I)為其相應(yīng)的面向?qū)傩愿拍罡?，PIL(G,M,I)為其相應(yīng)的面向?qū)傩缘膮^(qū)間集概念格，則：

證明記 ? ={([X1,X2]，[A1,A2])|X1?X2,(X1,A1),(X2,A2)∈PL(G,M,I)}，由定理2知，PIL(G,M,I)??，又由于定理5知??PIL(G,M,I)，故?=PIL(G,M,I)。 □

例3（續(xù)例1）利用定理6構(gòu)造表1的面向?qū)傩缘膮^(qū)間集概念格。通過定義2可計(jì)算出面向?qū)傩愿拍畹耐庋訛椋翰⒂缮鲜鐾庋訕?gòu)成的區(qū)間集有：[? ,? ],[? ,2],[? ,3]，[? ,13]，[? ,123]，[2,2]，[2,123][3,3],[3,13],[3,123]，[13,13]，[13,123]，[123,123]。由定理6知，面向?qū)傩缘膮^(qū)間集概念有([?,?],[?,? ]),([? ,2],[? ,ab]),([? ,3],[? ,c]),([? ,13],[? ,ac]),([? ,123],

利用圖1，可驗(yàn)證上述所求的面向?qū)傩愿拍钫_。依據(jù)定理6，給出相應(yīng)的算法。

算法1面向?qū)傩缘膮^(qū)間集概念格構(gòu)造的算法

輸入：形式背景(G,M,I)。

輸出：面向?qū)傩缘膮^(qū)間集概念格PIL(G,M,I)。

1.PIL(G,M,I)=? ，PL(G,M,I)=?

2.調(diào)用求面向?qū)傩愿拍罡竦乃惴╗16]計(jì)算PL(G,M,I).

4 總結(jié)與展望

本文主要給出了面向?qū)傩缘膮^(qū)間集概念格的定義，并研究了面向?qū)傩缘膮^(qū)間集概念格與面向?qū)傩愿拍罡裰g的關(guān)系，最后給出了面向?qū)傩愿拍罡竦臉?gòu)造方法及其相應(yīng)的算法。對于本文所提的研究對象，將研究其相應(yīng)的屬性約簡及壓縮問題，對所獲知識進(jìn)行凝練提取。另外，還可以將此思想引入到其他理論框架中，例如引入到面向?qū)ο蟾拍罡癫⒀芯啃滦透拍罡裰g的關(guān)系。