基于依賴空間的對象導出三支概念格的屬性約簡

丁 娜, 馬建敏, 賀青青

(長安大學 理學院 陜西 西安 710064)

0 引言

概念格理論[1]作為一種數據分析和信息處理的方法, 已經被廣泛應用到信息檢索、知識發現、推薦系統、軟件工程等領域[2-5]。然而, 隨著知識的不斷發展, 經典概念格已經不能滿足人們的需要, 在描述具體概念時, 不同的刻畫方式可以構造出不同的概念格。近來較熱門的概念格擴展模型為三支概念格[6], 通過三支算子和三支逆算子定義了兩種類型的三支概念格, 即對象導出三支概念格和屬性導出三支概念格。三支概念中對象(屬性)共同具有的屬性(對象)被視為接受的部分, 對象(屬性)共同不具有的屬性(對象)被視為拒絕的部分, 通過共同具有和共同不具有將研究對象(屬性)劃分為三個彼此不相交的部分, 這種反映數據隱藏知識的工具更有利于知識發現以及做三支決策[7-9]。學者們從三支概念格的構造、屬性約簡、規則提取等不同的方面對其研究。Qi等[10]討論了三支概念格和經典概念格的關系, 同時提出一種基于經典概念格構造三支概念格的方法。Yang等[11]結合原形式背景和其補形式背景的一對概念引入復合算子, 利用復合算子研究三支概念格的構造。Qian[12]通過對三支概念格原形式背景和補形式背景的轉換, 結合概念格的構造算法, 提出了三支概念格的構造算法。Ren等[13]提出三支概念格四種類型的屬性約簡, 并且討論了它們之間的關系和具體的屬性約簡方法。張呈玲等[14]在三支概念格的屬性約簡框架下, 借助布爾矩陣理論, 研究了保持對象導出三支概念對象粒矩陣不變的屬性約簡問題。

依賴空間理論[15]提供了表達集合獨立性和依賴概念的一個通用的框架。Ma等[16]討論了形式概念分析中基于粗糙集理論的面向對象概念格和面向屬性概念格的依賴空間模型, 同時給出了構造這兩類概念格的方法。包永偉等[17]主要研究了面向對象概念格和面向屬性概念格的依賴空間理論, 為這兩類概念格基于一致關系的知識約簡與規則提取提供了理論基礎。Wang等[18]提出基于一致關系的面向對象概念格屬性約簡的定義和約簡方法。Ma等[19]提出了一種新的構造概念格的方法, 即基于依賴空間構造經典概念格。

本文利用三支算子定義了一致關系, 引入依賴空間, 提出了基于依賴空間的對象導出三支概念格上屬性約簡的定義, 在此基礎上通過引入可辨識屬性矩陣和可辨識函數計算約簡集。

1 對象導出三支概念格

稱三元組(G,M,I)為形式背景, 其中G={x1,x2,…,xn}是非空有限對象集,M={a1,a2,…,am}是非空有限屬性集,I?G×M是G和M之間的二元關系。對任意x∈G和a∈M, 若(x,a)∈I, 則稱對象x具有屬性a;若(x,a)?I, 則稱對象x不具有屬性a。

在X?G和A?M上分別定義算子[1]:

X*={a∈M|?x∈X,(x,a)∈I},

(1)

A*={x∈G|?a∈A,(x,a)∈I}。

(2)

Qi等[6]在X?G和A?M上分別定義負算子:

(3)

(4)

根據式(1)～(4)給出的算子, Qi等[6]給出了三支算子和三支逆算子的定義和性質, 進一步提出對象導出三支概念。

定義1[6]設(G,M,I)為形式背景,X?G,A,B?M。定義三支算子和三支逆算子為

(5)

(6)

性質1[6]設(G,M,I)為形式背景。對任意X,Y?G,A,B,C,D?M, 下列性質成立:

OEL(G,M,I)表示形式背景(G,M,I)上所有對象導出三支概念的集合。對任意(X,(A,B)),(Y,(C,D))∈OEL(G,M,I), 定義OEL(G,M,I)上的偏序關系≤:

(X,(A,B))≤(Y,(C,D))?X?Y?(C,D)?(A,B),

則(OEL(G,M,I),≤)是一個完備格, 稱為對象導出三支概念格[6], 其下確界和上確界分別為

(X,(A,B))∧(Y,(C,D))=

(X,(A,B))∨(Y,(C,D))=

記ExtOEL(G,M,I)={X|(X,(A,B))∈OEL(G,M,I)}為對象導出三支概念所有外延構成的集合,IntOEL(G,M,I)={(A,B)|(X,(A,B))∈OEL(G,M,I)}為對象導出三支概念所有內涵構成的集合。

2 基于依賴空間的對象導出三支概念格

本節在對象冪集上定義一致關系, 引入依賴空間, 在此基礎上討論閉包算子的閉元素與對象導出三支概念的外延之間的關系。

定義3[15]設V為非空有限集合,K為冪集P(V)上的等價關系。

1) 若對任意(B1,C1)∈K,(B2,C2)∈K, 有(B1∪B2,C1∪C2)∈K, 則稱K為P(V)上的一致關系;

2) 若K為P(V)上的一致關系, 則稱(V,K)為依賴空間。

定理1設(G,M,I)為形式背景,N?M。定義P(G)上的二元關系為

(7)

定義4[1]設(P,≤)是偏序集。若映射c:P→P滿足條件

1) 對任意x∈P,x≤c(x),

2) 對任意x,y∈P,x≤y?,c(x)≤c(y),

3) 對任意x∈P,c(c(x))=c(x),

則稱c是(P,≤)上的閉包算子。

定理2設(G,M,I)為形式背景。對任意X,Y?G,N?M, 定義

則

引理1設(G,M,I)為形式背景。對任意X?G和N?M, 有

由性質1中的3)和引理1中的2)得, 對任意X?G,N?M,

(8)

定理3設(G,M,I)為形式背景。對任意X?G和A,B?M, 有

(9)

3 基于依賴空間的對象導出三支概念格的屬性約簡

本節提出基于依賴空間的對象導出三支概念格上屬性約簡的定義, 給出協調集的判定定理, 借助可辨識屬性矩陣及辨識函數給出屬性約簡方法。

定理4設(G,M1,I1),(G,M2,I2)為具有相同對象集的兩個形式背景。則

由定義5和定理4可得推論1。

推論1設(G,M,I)為形式背景。對任意N?M,N是(G,M,I)的屬性約簡,

1)ExtOEL(G,N,IN)=ExtOEL(G,M,I);

2) 對任意a∈N,

ExtOEL(G,N-{a},IN-{a})≠ExtOEL(G,M,I)。

定義6設(G,M,I)為形式背景。對任意X,Y?G, 定義

為可辨識屬性矩陣。

定理5設(G,M,I)為形式背景。對任意X,Y?G, 有

(A∪C-A∩C)∪(B∪D-B∩D),

因此,

性質2設(G,M,I)為形式背景。對任意X,Y,Z?G,N?M, 性質1)～4)成立:

2)

證明1) ?。設N是協調集, 則

則由定理5有(A∩N,B∩N)≠(C∩N,D∩N)。

下證對任意(X,(A,B))∈OEL(G,M,I)有(X,(A∩N,B∩N))∈OEL(G,N,IN)。

得

但是, 一方面由(A∩N,B∩N)?(A,B)得

另一方面, 由

得

矛盾。故

通過使用吸收律和分配律, 可以將辨識函數f(Λ)變換為最小析取范式, 這個最小析取范式的所有組成成分是形式背景的全部約簡。

例1考慮形式背景(G,M,I), 如表1,其中G={1,2,3,4},M={a,b,c,d,e}。

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

2) 計算所有等價類:

OEL(G,M,I)={(?,(M,M)), (1,(abde,c)), (2,(abc,de)),(3,(d,abce)), (4,(abce,d)), (13,(d,c)),(23,(?,e)), (14,(abe,?)), (24,(abc,d)),(124,(ab,?)), (G,(?,?))}。

對象導出三支概念格如圖1所示。

圖1 (G,M,I)的對象導出三支概念格Figure 1 The object-induced three-way concept lattice of (G,M,I)

4) 由對象導出三支概念計算可辨識屬性矩陣Λ, 如表2。

表2 (G,M,I)的可辨識屬性矩陣Table 2 The discernibility matrix of (G,M,I)

5) 計算形式背景(G,M,I)的辨識函數:

f(Λ)=(a∨b∨c∨d∨e)∧(c∨d∨e)∧

(a∨b∨e)∧(c∨d)∧(a∨b∨c∨d)∧e∧(a∨b)=(a∧c∧e)∨(a∧d∧e)∨(b∧c∧e)∨(b∧d∧e)。

因此對象導出三支概念格的約簡集分別為{a,c,e},{a,d,e},{b,c,e},{b,d,e}。

4 結論

本文基于依賴空間證明了閉包算子的閉元素是對象導出三支概念的外延。在此基礎上提出了基于一致關系的對象導出三支概念格屬性約簡的定義, 該定義下的約簡集是保持由原屬性集確定的一致關系不變的最小屬性子集。最后利用可辨識屬性矩陣的方法計算對象導出三支概念格的屬性約簡集。

下一步將研究基于依賴空間的屬性導出三支概念格的屬性約簡方法, 進一步研究基于一致關系的對象導出三支概念格的規則提取方法。