廣義多尺度信息系統的知識獲取與矩陣方法

黃建新,李偉康*,張曉萍,李進金,2

(1.華僑大學 數學科學學院,福建 泉州 362021;2.閩南師范大學 數學科學與統計學院,福建 漳州 363000)

0 引言

多尺度信息系統是粗糙集理論的重要推廣模型之一,由Wu和Leung于2011年提出,亦稱為多尺度信息表[1]。目前,多尺度信息系統的研究已經成為數據挖掘領域的熱門方向之一,并且取得了許多重要成果[2]。多尺度信息系統與信息系統的區別在于從不同的標記層面對系統進行分析,這樣有利于提升模型的泛化能力等。規則提取與尺度選擇是研究多尺度信息系統知識發現與獲取的兩個重要方向[1,3]。文獻[4]從局部對象的角度出發,提出了一種規則簡化的方法。文獻[5]中在不完備多尺度信息系統的基礎上,定義了一種優勢關系,進一步定義了基于優勢關系的上下近似的概念,并且討論了相關性質。針對不協調的多尺度決策信息系統,文獻[6]中介紹了8 種協調性和最優粒度概念,并研究了它們之間的相互關系。Li和Hu研究了不同屬性、不同等級的多尺度決策信息系統,在此基礎上,研究了尺度選擇問題,進而提出了一種推廣的多尺度信息系統,稱為廣義多尺度信息系統[7]。在多尺度決策信息系統中,尺度選擇是規則提取的重要基礎,文獻[1]和[3]研究了不同尺度組合下的決策規則提取。文獻[8]研究了不完備多尺度決策信息系統的規則提取問題,隨著尺度的粗化,模型具有更好的泛化效果。相比于多尺度信息系統,廣義多尺度信息系統是一種更有效的數據分析模型。文獻[9]中基于多尺度信息系統,研究了一種動態的序貫三支決策模型,并提出了一種最優尺度組合選擇的方法。文獻[10]中定義了一種多尺度屬性重要度的概念,在此基礎上,提出了一種逐步優化的尺度組合選擇方法。文獻[11]中研究了不完備多尺度信息系統中具有尺度動態變化的三支決策的更新問題,對相似關系所引起的決策粒的更新機制進行了挖掘。文獻[12]和[13]中分別研究了不協調廣義多尺度決策系統和不完備廣義多尺度決策系統的尺度組合選擇問題,并利用證據理論對相應系統中的最優尺度組合特征進行了刻畫。文獻[14]中研究了廣義多尺度決策信息系統中的局部最優粒度選擇問題,并給出了局部最優粒度選擇的方法。

粗糙集理論是以集合的運算為基礎,在文獻[15]中建立了屬性集與布爾矩陣之間的關系,在此基礎上給出了粗糙集理論中概念與運算的布爾矩陣表示。文獻[16]中利用論域子集的特征矩陣、等價關系矩陣和誘導矩陣三個矩陣間的運算來計算子集的上下近似集。文獻[17]中從矩陣的視角探討了知識粒度、粗糙度和屬性重要度等概念的計算方法,并且揭示了知識粒度與等價關系矩陣之間的關系。粗糙集理論與矩陣理論聯系密切,矩陣的方法不僅提供了上下近似的簡單的計算方法,也提供了一種新的推理的方法，使得粗糙集理論得以深入發展。文獻[18]中用矩陣方法研究粗糙集,分別給出粗糙集、模糊粗糙集與粗糙模糊集的上下近似的矩陣表示方法。文獻[19]中基于矩陣的直觀性和矩陣運算的簡便性引入區間向量,構造了基于關系矩陣計算區間集粗糙上下近似的方法。文獻[20]中提出了一種基于矩陣的不完備決策信息系統協調性判定方法。目前,在多尺度決策信息系統的研究中,以大量的集合運算為基礎背景,所提出的尺度選擇與規則提取方法相較矩陣方法缺乏直觀性與簡便性。文獻[21]中以矩陣的布爾運算為基礎,提出了一種判斷多尺度決策信息系統協調性的方法,并且利用屬性重要度,給出了一種尺度組合選擇的矩陣方法。本文從矩陣的角度出發,研究廣義多尺度決策信息系統的規則提取,進一步研究尺度組合選擇的矩陣方法。與文獻[21]相比較,本文的尺度組合選擇的矩陣方法是以矩陣的乘法運算為基礎,直接從尺度組合的關系矩陣出發,這樣的方法是簡便的以及深刻的。

在Pawlak粗糙集理論中,下近似集和上近似集是兩個重要的概念。

定義1[3]設K=(U,R)是一個近似空間,R是論域U上的一個等價關系,對于?X?U,

{x∈U|[x]R?X}

{x∈U|[x]R∩X≠φ}

在下文的討論中,我們用∧與∨分別表示合取和析取。對于任意a∈B?A,我們稱二元組(a,v)為B的一個原子,其中v∈Va。任意B原子通過合取方式聯結,稱為B的一個描述。設t是B的一個描述,我們用B(t)表示t中所涉及的屬性的集合,‖t‖表示支持集。我們記DES(B)={t|t是B描述且‖t‖=φ}。對于?t∈DES(B),如果B(t)=B,我們稱t是一個完整的B的描述。我們記FDES(B)={t|t是完整的B描述}。

定義3[10]稱二元組(U,A)為一個廣義多尺度信息系統,其中論域U={x1,x2,…,xn}是一個非空有限對象集,A={a1,a2,…,am}為一個非空有限屬性集,每個屬性都是多尺度屬性。假設屬性aj∈A有Ij個等級尺度標記,則一個廣義多尺度信息系統可表示為

1 等價關系矩陣與上下近似集的矩陣表示

我們先介紹相關矩陣的概念以及上下近似集的矩陣計算[16]。

定義4設U是非空有限論域,且U={x1,x2,…,xn},R是U上的等價關系,X是U的任意子集,則

稱為等價關系R的關系矩陣或特征矩陣,顯然MR是對稱矩陣。

稱為X的特征矩陣,簡記為Xn×1=(u1,u2,…,un)T。

在后面的論述中,如果沒有特別說明,我們將論域U的子集X與X對應的n維布爾列向量等同看待,例如,U={x1,x2,x3,x4,x5},X={x1,x3,x5},則有X=(1,0,1,0,1)T。

定義5設R是論域U上的等價關系,|U|=n,則由等價關系矩陣MR所誘導的對角矩陣Gn×n定義為

顯然,G為對稱矩陣。

定義6矩陣Am×n=(aij)m×n的λ截矩陣(Aλ)m×n可定義為

這里λ∈[0,1]。

引理1設U是非空有限論域,且U={x1,x2,…,xn},R是U上的等價關系,則

且1≤|[xi]R|≤n,i=1,2,…,n,其中|[xi]R|表示集合[xi]R的基數。

命題1設K=(U,R)是一個近似空間,|U|=n,MR=(mij)n×n是R的等價關系矩陣,X是U的任意子集,則有

(1)X的下近似集的特征矩陣為

(2)X的上近似集的特征矩陣為

例1K=(U,R)為一個近似空間,X?U,其中論域U={x1,x2,x3,x4,x5,x6,x7},

R={(x1,x1),(x1,x2),(x2,x2),(x2,x1),

(x3,x3),(x4,x4),(x4,x7),(x5,x5),

(x6,x6),(x7,x7),(x7,x4)}

X={x1,x3,x4,x7}

根據定義4,經計算得等價關系R的關系矩陣為

MR所誘導的對角矩陣為

X的特征矩陣為X=(1,0,1,1,0,0,1)T,則

2 廣義多尺度決策信息系統的規則提取

定義7設S=(U,A,D)是一個廣義多尺度決策信息系統,其中(U,A)是一個廣義多尺度信息系統,D是決策屬性。如果(U,A1,D)是一個協調的決策信息系統,即RA1?RD,那么我們稱S是一個協調的廣義多尺度決策信息系統;否則,稱S是不協調的。

給出如下命題2,來判斷廣義多尺度決策信息系統的協調性。

命題2對于一個廣義多尺度決策信息系統S=(U,A,D),如果?t∈FDES(A1),s∈FDES(D),規則t→s是不確定的,那么S是不協調的;否則,S是協調的。

證明因為規則t→s是不確定的,所以?x,y∈‖t‖,x∈‖s‖,y?‖s‖,使得(x,y)∈RA1(x,y)?RD。因此,RA1?RD不成立,S是不協調的反之,S是協調的。

根據文獻[8],我們可以得到如下命題3。

命題3設S=(U,A,D)是一個廣義多尺度決策信息系統,t∈DES(Ak),s∈DES(D),則

定義8對于一個協調的廣義多尺度決策信息系統S=(U,A,D),我們稱k∈L是S的最優尺度組合,當且僅當Sk是協調的,且對于任意h≥k,Sh是不協調的。

命題4設S=(U,A,D)是一個廣義多尺度決策信息系統,對于k,h∈L,如果k≤h,那么|DES(Ak)|≥|DES(Ah)|和|FDES(Ak)|≥|FDES(Ah)|。

證明根據定義3,顯然命題成立

例2表1是某中學的入學考試成績表,根據考生編號,依次用x1,x2,…,x8來表示八位考生。通過觀察分析,這是一個廣義多尺度決策信息系統,條件屬性A={語文，數學，英語},決策屬性D={是否錄取}。每個條件屬性分別有3個尺度標記,依次是五分制、等級制和是否合格。

通過計算,我們可以知道表1是一個協調的廣義多尺度決策信息系統,(3,3,2)是最優尺度組合,即語文和數學分別取是否合格,英語取等級制我們取最細尺度組合,通過計算,得到以下決策規則集:

表1 A班級的考試成績表

確定性規則:

r1:(語文,1)∧(數學,2)∧(英語,1)→(錄取,否),確定性因子1,支持的對象x6;

r2:(語文,2)∧(數學,3)∧(英語,3)→(錄取,否),確定性因子1,支持的對象x2;

r3:(語文,3)∧(數學,1)∧(英語,2)→(錄取,否),確定性因子1,支持的對象x4;

r4:(語文,3)∧(數學,3)∧(英語,2)→(錄取,否),確定性因子1,支持的對象x8;

r5:(語文,3)∧(數學,4)∧(英語,3)→(錄取,是),確定性因子1,支持的對象x7;

r6:(語文,4)∧(數學,4)∧(英語,5)→(錄取,是),確定性因子1,支持的對象x3;

r7:(語文,4)∧(數學,5)∧(英語,4)→(錄取,是),確定性因子1,支持的對象x1;

r8:(語文,5)∧(數學,4)∧(英語,4)→(錄取,是),確定性因子1,支持的對象x5

我們取最優尺度組合,通過計算,得到以下決策規則集:

確定性規則:

r9:(語文,合格)∧(數學,合格)∧(英語,優)→(錄取,是),確定性因子1,支持的對象x3;

r10:(語文,合格)∧(數學,合格)∧(英語,良)→(錄取,是),確定性因子1,支持的對象x1,x5,x7;

r11:(語文,合格)∧(數學,合格)∧(英語,差)→(錄取,否),確定性因子1,支持的對象x8;

r12:(語文,合格)∧(數學,不合格)∧(英語,差)→(錄取,否),確定性因子1,支持的對象x4;

r13:(語文,不合格)∧(數學,合格)∧(英語,良)→(錄取,否),確定性因子1,支持的對象x2;

r14:(語文,不合格)∧(數學,不合格)∧(英語,差)→(錄取,否),確定性因子1,支持的對象x6。

通過以上決策規則集的比較,容易得出,最優尺度組合下的決策規則集,泛化效果更好。

針對于不協調的廣義多尺度決策信息系統,在本文中,我們給出保持決策屬性正域不變的最優尺度組合選擇的定義。

定義9設S=(U,A,D)是一個不協調的廣義多尺度決策信息系統,我們稱k∈L是S的保持正域不變的最優尺度組合,當且僅當posAk(D)=posA1(D),且對于任意h≥k,posAh(D)≠posA1(D)。

例3與表1相似,表2是某中學的入學考試成績表。

通過計算,我們可以知道表2是一個不協調的廣義多尺度決策信息系統,(3,2,3)是保持正域不變的最優尺度組合,即語文和英語分別取是否合格,數學取等級制我們取最細尺度組合,通過計算,得到以下決策規則集:

確定性規則:

r1:(語文,1)∧(數學,3)∧(英語,2)→(錄取,否),確定性因子1,支持的對象x4;

r2:(語文,3)∧(數學,3)∧(英語,4)→(錄取,是),確定性因子1,支持的對象x2;

r3:(語文,3)∧(數學,4)∧(英語,3)→(錄取,是),確定性因子1,支持的對象x8;

r4:(語文,4)∧(數學,3)∧(英語,3)→(錄取,是),確定性因子1,支持的對象x3;

r5:(語文,4)∧(數學,4)∧(英語,3)→(錄取,是),確定性因子1,支持的對象x6;

r6:(語文,5)∧(數學,4)∧(英語,3)→(錄取,是),確定性因子1,支持的對象x7。

不確定性規則:

r7:(語文,4)∧(數學,2)∧(英語,4)→(錄取,否),確定性因子0.5,支持的對象x1;

表2 B班級的考試成績表

r8:(語文,4)∧(數學,2)∧(英語,4)→(錄取,是),確定性因子0.5,支持的對象x5。

我們取保持正域不變的最優尺度組合,通過計算,得到以下決策規則集:

確定性規則:

r9:(語文,合格)∧(數學,優)∧(英語,合格)→(錄取,是),確定性因子1,支持的對象x6,x7,x8;

r10:(語文,合格)∧(數學,良)∧(英語,不合格)→(錄取,否),確定性因子1,支持的對象x2,x3;

r11:(語文,不合格)∧(數學,良)∧(英語,不合格)→(錄取,否),確定性因子1,支持的對象x4。

不確定性規則:

r12:(語文,合格)∧(數學,差)∧(英語,合格)→(錄取,否),確定性因子0.5,支持的對象x1;

r13:(語文,合格)∧(數學,差)∧(英語,合格)→(錄取,是),確定性因子0.5,支持的對象x5。

通過以上決策規則集的比較,容易得出,保持正域不變的最優尺度組合下的決策規則集,泛化效果更好。

3 基于矩陣的規則提取與尺度選擇

事實上,集合與矩陣通過特定的矩陣運算進行聯系。在命題5中,我們給出利用特征矩陣計算規則確定性因子的方法。

證明根據規則確定性因子的定義,顯然可得

命題6設S=(U,A,D)是一個廣義多尺度決策信息系統,|U|=n,t∈DES(Ak),s∈DES(D),則

(1)決策規則t→s是確定的當且僅當‖t‖T(G(MAk(t)‖s‖))1=‖t‖T‖t‖;

證明(1)根據命題3,我們僅需證

‖t‖T(G(MAk(t)‖s‖))1=

(2)證明方法與(1)類似。

命題7對于一個協調的廣義多尺度決策信息系統S=(U,A,D),k∈L是S的最優尺度組合當且僅當(GAk(MAkMD))1=MD,且對于任意h≥k,(GAh(MAhMD))1≠MD。

根據命題7,對于協調的廣義多尺度決策信息系統,我們給出利用特征矩陣來選擇最優尺度組合的方法,見算法1。

根據廣義多尺度決策信息系統的協調性,我們可以知道算法1是收斂的。在不考慮步驟1和2對算法影響的情況下,算法1的時間復雜度是O(m×I1×…×Im)。

算法1 計算協調廣義多尺度決策信息系統的最優尺度組合輸入:協調的廣義多尺度決策信息系統S=(U,A,D)輸出:最優尺度組合。步驟1 令n=對象的個數;m=條件屬性的個數;Ij=屬性尺度的數量,j=1,2,…,m;步驟2 令最優尺度組合k=(I1,I2,…,Im);i=0;j=1;步驟3 如果(GAk(MAkMD))1==MD,那么輸出最優尺度組合k,然后執行步驟5,否則,如果i+1≠j,那么i=i+1,然后執行步驟4,否則i=i+2,然后執行步驟4;∥這里G和M分別為對角矩陣和特征矩陣。步驟4 如果i≤m,那么k=(I1,…,Ii-1,…,Im),然后執行步驟3,否則,i=0,如果Ij>1,那么Ij=Ij-1,j=j+1,然后執行步驟3;步驟5 結束。

例4繼例2,我們有條件屬性在尺度組合(3,3,2)下的關系矩陣,決策屬性的關系矩陣和誘導矩陣分別如下:

根據命題7,通過計算可得

(GA(3,3,2)(MA(3,3,2)MD))1=MD,

且

(GA(3,3,3)(MA(3,3,3)MD))1≠MD,

所以尺度組合(3,3,2)是最優尺度組合。

通過例4,我們知道矩陣方法判斷最優尺度組合是直觀的和有效的。命題7闡明協調的廣義多尺度決策信息系統中最優尺度組合與特征矩陣之間的聯系,并給出最優尺度組合的矩陣計算方法。下面,我們研究不協調的廣義多尺度決策信息系統中,保持決策屬性正域不變的最優尺度組合與特征矩陣之間的聯系,并給出矩陣計算方法。

算法2 計算不協調廣義多尺度決策信息系統的最優尺度組合。輸入:不協調的廣義多尺度決策信息系統S=(U,A,D)。輸出:最優尺度組合。步驟1 令n=對象的個數,m=條件屬性的個數,Ij=屬性尺度的數量,j=1,2,…,m;步驟2 令最優尺度組合k=(I1,I2,…,Im),i=0,j=1;步驟3 如果∑X∈U/D(GAk(MAkX))1==∑X∈U/D(GA1(MA1X))1,那么輸出最優尺度組合k,然后執行步驟5,否則,如果i+1≠j,那么i=i+1,然后執行步驟4,否則i=i+2,然后執行步驟4;∥這里G、M和X分別為對角矩陣和特征矩陣,A1表示取最細尺度組合的條件屬性。步驟4 如果i≤m,那么k=(I1,…,Ii-1,…,Im),然后執行步驟3,否則,i=0,如果Ij>1,那么Ij=Ij-1,j=j+1,然后執行步驟3;步驟5 結束。

命題8設S=(U,A,D)是一個不協調的廣義多尺度決策信息系統,k∈L是S的保持正域不變的最優尺度組合,當且僅當

且對于任意h≥k,不成立。

證明結合命題1與定義9,顯然可證。

根據命題8,對于不協調的廣義多尺度決策信息系統,我們給出利用特征矩陣來選擇保持決策屬性正域不變的最優尺度組合的方法,見算法2。

我們可以容易知道算法2是收斂的在不考慮步驟1和2對算法影響的情況下,算法2的時間復雜度是O(m×I1×…×Im)。

例5繼例3,我們有條件屬性分別在尺度組合(3,2,3)和最細尺度組合下的關系矩陣,誘導矩陣以及U/D={X1,X2}分別如下:

根據命題8,通過計算可得

且

所以尺度組合(3,2,3)是保持正域不變的最優尺度組合。

4 結論

規則提取與尺度選擇是多尺度信息系統中知識獲取的兩個重要方式。本文給出了廣義多尺度信息系統中規則提取與尺度組合選擇的矩陣方法,這樣的方法相較于傳統的基于集合運算的方法是直觀的和簡便的。此外,在廣義多尺度決策信息系統中,隨著尺度的粗化,決策規則的泛化效果越好。利用矩陣對最優尺度組合進行刻畫,體現了廣義多尺度信息系統理論與矩陣理論之間的密切聯系,同時,它促進了多尺度決策系統的理論研究。未來進一步研究的工作是將此方法應用于規則提取的算法設計,以及改進已有的尺度選擇算法。此外,我們也將通過對比實驗,進一步分析尺度選擇算法的時間復雜度。