基于依賴空間的對(duì)象導(dǎo)出三支概念格的屬性約簡

丁 娜, 馬建敏, 賀青青

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

0 引言

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

依賴空間理論[15]提供了表達(dá)集合獨(dú)立性和依賴概念的一個(gè)通用的框架。Ma等[16]討論了形式概念分析中基于粗糙集理論的面向?qū)ο蟾拍罡窈兔嫦驅(qū)傩愿拍罡竦囊蕾嚳臻g模型, 同時(shí)給出了構(gòu)造這兩類概念格的方法。包永偉等[17]主要研究了面向?qū)ο蟾拍罡窈兔嫦驅(qū)傩愿拍罡竦囊蕾嚳臻g理論, 為這兩類概念格基于一致關(guān)系的知識(shí)約簡與規(guī)則提取提供了理論基礎(chǔ)。Wang等[18]提出基于一致關(guān)系的面向?qū)ο蟾拍罡駥傩约s簡的定義和約簡方法。Ma等[19]提出了一種新的構(gòu)造概念格的方法, 即基于依賴空間構(gòu)造經(jīng)典概念格。

本文利用三支算子定義了一致關(guān)系, 引入依賴空間, 提出了基于依賴空間的對(duì)象導(dǎo)出三支概念格上屬性約簡的定義, 在此基礎(chǔ)上通過引入可辨識(shí)屬性矩陣和可辨識(shí)函數(shù)計(jì)算約簡集。

1 對(duì)象導(dǎo)出三支概念格

稱三元組(G,M,I)為形式背景, 其中G={x1,x2,…,xn}是非空有限對(duì)象集,M={a1,a2,…,am}是非空有限屬性集,I?G×M是G和M之間的二元關(guān)系。對(duì)任意x∈G和a∈M, 若(x,a)∈I, 則稱對(duì)象x具有屬性a;若(x,a)?I, 則稱對(duì)象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上分別定義負(fù)算子:

(3)

(4)

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

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

(5)

(6)

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

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

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

則(OEL(G,M,I),≤)是一個(gè)完備格, 稱為對(duì)象導(dǎo)出三支概念格[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)}為對(duì)象導(dǎo)出三支概念所有外延構(gòu)成的集合,IntOEL(G,M,I)={(A,B)|(X,(A,B))∈OEL(G,M,I)}為對(duì)象導(dǎo)出三支概念所有內(nèi)涵構(gòu)成的集合。

2 基于依賴空間的對(duì)象導(dǎo)出三支概念格

本節(jié)在對(duì)象冪集上定義一致關(guān)系, 引入依賴空間, 在此基礎(chǔ)上討論閉包算子的閉元素與對(duì)象導(dǎo)出三支概念的外延之間的關(guān)系。

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

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

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

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

(7)

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

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

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

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

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

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

則

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

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

(8)

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

(9)

3 基于依賴空間的對(duì)象導(dǎo)出三支概念格的屬性約簡

本節(jié)提出基于依賴空間的對(duì)象導(dǎo)出三支概念格上屬性約簡的定義, 給出協(xié)調(diào)集的判定定理, 借助可辨識(shí)屬性矩陣及辨識(shí)函數(shù)給出屬性約簡方法。

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

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

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

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

2) 對(duì)任意a∈N,

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

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

為可辨識(shí)屬性矩陣。

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

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

因此,

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

2)

證明1) ?。設(shè)N是協(xié)調(diào)集, 則

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

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

得

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

另一方面, 由

得

矛盾。故

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

例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) 計(jì)算所有等價(jià)類:

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,(?,?))}。

對(duì)象導(dǎo)出三支概念格如圖1所示。

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

4) 由對(duì)象導(dǎo)出三支概念計(jì)算可辨識(shí)屬性矩陣Λ, 如表2。

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

5) 計(jì)算形式背景(G,M,I)的辨識(shí)函數(shù):

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)。

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

4 結(jié)論

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

下一步將研究基于依賴空間的屬性導(dǎo)出三支概念格的屬性約簡方法, 進(jìn)一步研究基于一致關(guān)系的對(duì)象導(dǎo)出三支概念格的規(guī)則提取方法。