形式背景的下近似協(xié)調(diào)與粒協(xié)調(diào)的關(guān)系

陳東曉， 李進(jìn)金，2

(1. 華僑大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 福建 泉州 362021；2. 閩南師范大學(xué) 數(shù)學(xué)科學(xué)與統(tǒng)計(jì)學(xué)院， 福建 漳州 363000)

形式概念分析(FCA)是由德國數(shù)學(xué)家Wille[1]提出的一種分析數(shù)據(jù)的有效工具，它的核心是形式背景和概念格.形式背景是由對象集、屬性集以及對象和屬性之間的二元關(guān)系構(gòu)成的.而概念格是將形式背景里的對象子集和屬性子集以一種概念層次體現(xiàn)出來.近年來，形式概念分析已被廣泛應(yīng)用于概念認(rèn)知、知識提取等領(lǐng)域.形式背景是形式概念分析中數(shù)據(jù)的組織形式，由對象集、屬性集與兩者之間的一個(gè)二元關(guān)系組成.形式背景中有3種基本的模態(tài)邏輯算子，即充分性算子、必要性算子和可能性算子[2].Wille利用充分性算子,建立起對象冪集和屬性冪集間的一個(gè)伽羅瓦連接,給出了形式概念的定義.一個(gè)形式背景中,所有形式概念構(gòu)成一個(gè)完備格，稱為概念格.因此，形式概念分析也被稱為概念格理論.必要性算子和可能性算子分別就是粗糙集理論[3]中的下近似算子和上近似算子.利用上、下近似算子,Yao[4]給出了對象定向概念格的定義，Gediga等[2]定義了屬性定向概念.通過對照形式概念的研究，對象定向概念格和屬性定向概念格也取得了許多研究結(jié)果.Shao等[5]研究了對應(yīng)的屬性約簡問題， 給出了約簡的算法.形式背景上的模態(tài)邏輯算子在一定意義下可以相互轉(zhuǎn)換，這為概念格理論與粗糙集理論之間建立起“溝通”的橋梁.因此，在形式背景中，粗糙集理論與概念格理論具有非常密切的聯(lián)系.形式背景中粗糙集近似本質(zhì)上是廣義近似空間中的粗糙運(yùn)算，它的一個(gè)特點(diǎn)是近似集和被近似集不在同一論域.粗糙集理論的一個(gè)主要應(yīng)用是提取決策規(guī)則，它要求近似集和被近似集必須在同一論域.為了在形式背景中利用粗糙集方法導(dǎo)出決策規(guī)則，Li等[6-7]在形式背景中給出了幾種修正的粗糙近似，針對其中一種粗糙近似運(yùn)算研究了基于決策規(guī)則的屬性約簡問題.Dempser-Shafer 證據(jù)理論以基本概率分配為基礎(chǔ)，利用信任函數(shù)和似然函數(shù)構(gòu)成的不確定區(qū)間刻畫證據(jù)的不確定性和未知性.集合的信任測度和似然測度可以看成是對該集合的不確定性的定量刻畫，而同一集合的上近似和下近似可以看成是對該集合所表示信息的定性描述，那么證據(jù)理論與粗糙集理論之間存在必然的聯(lián)系[8-10].文獻(xiàn)[11-17]研究了利用證據(jù)理論刻畫信息系統(tǒng)、決策信息系統(tǒng)中的屬性約簡問題,文獻(xiàn)[18-22]分別通過建立一對覆蓋近似算子與信任函數(shù)、似然函數(shù)的聯(lián)系以討論覆蓋決策信息系統(tǒng)的約簡.在形式背景中，概念格理論與粗糙近似理論之間有著密切關(guān)系[23]，同樣可以利用證據(jù)理論刻畫形式背景的屬性約簡問題.本文給出形式背景下的一種粗糙近似集定義，通過定義信任函數(shù)和似然函數(shù)，給出下近似協(xié)調(diào)集的等價(jià)結(jié)論，討論了下近似協(xié)調(diào)集的約簡，定義了上、下近似核心屬性，并給出充要條件.最后，定義了下近似協(xié)調(diào)的決策形式背景，并得到?jīng)Q策形式背景的下近似協(xié)調(diào)與粒協(xié)調(diào)是等價(jià)的.

1 基本概念和定理

定義1[1,24]形式背景(U，A，I)，其中,U為對象集，A為屬性集，I為U與A之間的二元關(guān)系，(x，a)∈I，表示對象x具有屬性a，也記為xIa.

設(shè)X?U，B?A，定義在形式背景(U，A，I)上的算子,即

X*={a∈A|?x∈X，xIa}，B*={x∈U|?a∈B，xIa}.

命題1[24]設(shè)(U，A，I)為一個(gè)形式背景，?x∈U，a∈A,則有x**=(x)A=∩{X|x∈X，

X∈LU(U，A，I)}，a**=(a)U=∩{B|a∈B，B∈LA(U，A，I)}.

利用粗糙集理論中的上、下近似算子的定義，引入定義2.

根據(jù)定義2有如下結(jié)論.

定理1設(shè)(U，A，I)為一個(gè)形式背景，?X?U，Y?U，則有如下結(jié)論:

證明：容易直接根據(jù)定義2證得.

?B?A，定義X*B={a∈B|?x∈X，xIa}，C*B={x∈U|?a∈C，xIa}，其中，X?U，C?B,容易得到X*B=X*∩B，且有X*A=X*.

命題3[3]設(shè)(U，A，I)為一個(gè)形式背景，C?B?A,則?X?U，?x∈U,有

1)X*C?X*B?X*A，x*C?x*B?x*A；

2)X*A*A?X*B*B?X*C*C，x*A*A?x*B*B?x*C*C；

3)C*B=C*A.

2 形式背景的上、下近似協(xié)調(diào)集

若m(X)>0，稱X是m的焦元，記M={X?U|m(X)>0}，序?qū)?M，m)為U上的一個(gè)信任結(jié)構(gòu).

同一信任結(jié)構(gòu)導(dǎo)出的信任函數(shù)和似然函數(shù)對偶，即Pl(X)=1-Bel(～X)，且Bel(X)≤Pl(X).

粗糙集理論和Dempster-Shafer證據(jù)理論之間有很強(qiáng)的聯(lián)系.以下定理4表明，經(jīng)典的信念和似然函數(shù)可以用Pawlaks集合的上、下近似來表示.

證明:與定理5證明類似.

定義6[24]設(shè)(U，A，I)為一個(gè)形式背景，B?A，若?x∈U，x*B*B=x*A*A，則稱B是(U，A，I)的粒協(xié)調(diào)集.

定理7設(shè)(U，A，I)為一個(gè)形式背景，B?A，則B為下近似協(xié)調(diào)集當(dāng)且僅當(dāng)B為粒協(xié)調(diào)集.

表1 形式背景(U，A，I)Tab.1 Formal context (U,A,I)

x*B*B，B是(U，A，I)的粒協(xié)調(diào)集.

例1設(shè)(U，A，I)為一個(gè)形式背景，U={1，2，3，4，5}，A={a，b，c，d，e}.形式背景,如表1所示.

該形式背景中，對應(yīng)的形式概念為L(U，A，I)={(U，?)，(134，b)，(235，ae)，(24，c)，(14，bd)，(3，abd)，(2，ace)，(4，bcd)，(?，A)}.取B={a，b，c，d}，驗(yàn)證得

即B是下近似協(xié)調(diào)集.由文獻(xiàn)[24]容易驗(yàn)證B是粒協(xié)調(diào)集.

3 決策形式背景的上、下近似協(xié)調(diào)集

定理10CoreL(A，D)={a∈A|SigA{a}{a}>0}.

同理，可以定義上近似協(xié)調(diào)下的屬性重要度.

定義12假設(shè)(U，A，I，D，J)為一個(gè)決策形式背景，B?A，a∈AB對于B的重要度為SigB{a}=

表2 決策形式背景(U，A，I，D，J)Tab.2 Decision formal context (U,A,I,D,J)

定理11CoreU(A，D)={a∈A|SigA{a}{a}>0}.

證明:類似定理10證明.

例2設(shè)(U，A，I，D，J)為一個(gè)決策形式背景，U={1，2，3，4，5}，條件屬性A={a，b，c，d，e}，決策屬性D={f，g，h}.該決策形式背景,如表2所示.

在此決策形式背景中，條件屬性對應(yīng)的概念格為L(U，A，I)={(U，?)，(134，b)，(235，ae)，(24，c)，(14，bd)，(3，abd)，(2，ace)，(4，bcd)，(?，A)}.決策屬性對應(yīng)的概念格為L(U，D，J)={(U，?)，(14，f)，(235，g)，(2，gh)，(?，D)}.計(jì)算得B1={a，c，d}和B2={c，d，e}是其兩個(gè)下近似約簡集，其下近似核心屬性為CoreL(A，D)={c，d}.

4 決策形式背景的下近似協(xié)調(diào)與粒協(xié)調(diào)的關(guān)系

定義13[24]設(shè)(U，A，I，D，J)為一個(gè)決策形式背景，如果?x∈U，有x*A*A?x*D*D，則稱(U，A，I，D，J)為協(xié)調(diào)的;否則,稱(U，A，I，D，J)是不協(xié)調(diào)的.

定理12設(shè)(U，A，I，D，J)為一個(gè)決策形式背景，(U，A，I，D，J)是粒協(xié)調(diào)的，當(dāng)且僅當(dāng)(U，A，I，D，J)是下近似協(xié)調(diào)的.

Li等[25]介紹了粒協(xié)調(diào)與強(qiáng)協(xié)調(diào)及弱協(xié)調(diào)之間關(guān)系，三者相互不一樣,而文中定義的下近似協(xié)調(diào)與粒協(xié)調(diào)等價(jià)，這里不再一一介紹三者之間的關(guān)系.

5 結(jié)束語