廣義多尺度信息系統(tǒng)的知識(shí)獲取與矩陣方法

黃建新,李偉康*,張曉萍,李進(jìn)金,2

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

0 引言

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

粗糙集理論是以集合的運(yùn)算為基礎(chǔ),在文獻(xiàn)[15]中建立了屬性集與布爾矩陣之間的關(guān)系,在此基礎(chǔ)上給出了粗糙集理論中概念與運(yùn)算的布爾矩陣表示。文獻(xiàn)[16]中利用論域子集的特征矩陣、等價(jià)關(guān)系矩陣和誘導(dǎo)矩陣三個(gè)矩陣間的運(yùn)算來(lái)計(jì)算子集的上下近似集。文獻(xiàn)[17]中從矩陣的視角探討了知識(shí)粒度、粗糙度和屬性重要度等概念的計(jì)算方法,并且揭示了知識(shí)粒度與等價(jià)關(guān)系矩陣之間的關(guān)系。粗糙集理論與矩陣?yán)碚撀?lián)系密切,矩陣的方法不僅提供了上下近似的簡(jiǎn)單的計(jì)算方法,也提供了一種新的推理的方法，使得粗糙集理論得以深入發(fā)展。文獻(xiàn)[18]中用矩陣方法研究粗糙集,分別給出粗糙集、模糊粗糙集與粗糙模糊集的上下近似的矩陣表示方法。文獻(xiàn)[19]中基于矩陣的直觀性和矩陣運(yùn)算的簡(jiǎn)便性引入?yún)^(qū)間向量,構(gòu)造了基于關(guān)系矩陣計(jì)算區(qū)間集粗糙上下近似的方法。文獻(xiàn)[20]中提出了一種基于矩陣的不完備決策信息系統(tǒng)協(xié)調(diào)性判定方法。目前,在多尺度決策信息系統(tǒng)的研究中,以大量的集合運(yùn)算為基礎(chǔ)背景,所提出的尺度選擇與規(guī)則提取方法相較矩陣方法缺乏直觀性與簡(jiǎn)便性。文獻(xiàn)[21]中以矩陣的布爾運(yùn)算為基礎(chǔ),提出了一種判斷多尺度決策信息系統(tǒng)協(xié)調(diào)性的方法,并且利用屬性重要度,給出了一種尺度組合選擇的矩陣方法。本文從矩陣的角度出發(fā),研究廣義多尺度決策信息系統(tǒng)的規(guī)則提取,進(jìn)一步研究尺度組合選擇的矩陣方法。與文獻(xiàn)[21]相比較,本文的尺度組合選擇的矩陣方法是以矩陣的乘法運(yùn)算為基礎(chǔ),直接從尺度組合的關(guān)系矩陣出發(fā),這樣的方法是簡(jiǎn)便的以及深刻的。

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

定義1[3]設(shè)K=(U,R)是一個(gè)近似空間,R是論域U上的一個(gè)等價(jià)關(guān)系,對(duì)于?X?U,

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

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

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

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

1 等價(jià)關(guān)系矩陣與上下近似集的矩陣表示

我們先介紹相關(guān)矩陣的概念以及上下近似集的矩陣計(jì)算[16]。

定義4設(shè)U是非空有限論域,且U={x1,x2,…,xn},R是U上的等價(jià)關(guān)系,X是U的任意子集,則

稱為等價(jià)關(guān)系R的關(guān)系矩陣或特征矩陣,顯然MR是對(duì)稱矩陣。

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

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

定義5設(shè)R是論域U上的等價(jià)關(guān)系,|U|=n,則由等價(jià)關(guān)系矩陣MR所誘導(dǎo)的對(duì)角矩陣Gn×n定義為

顯然,G為對(duì)稱矩陣。

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

這里λ∈[0,1]。

引理1設(shè)U是非空有限論域,且U={x1,x2,…,xn},R是U上的等價(jià)關(guān)系,則

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

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

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

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

例1K=(U,R)為一個(gè)近似空間,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}

根據(jù)定義4,經(jīng)計(jì)算得等價(jià)關(guān)系R的關(guān)系矩陣為

MR所誘導(dǎo)的對(duì)角矩陣為

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

2 廣義多尺度決策信息系統(tǒng)的規(guī)則提取

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

給出如下命題2,來(lái)判斷廣義多尺度決策信息系統(tǒng)的協(xié)調(diào)性。

命題2對(duì)于一個(gè)廣義多尺度決策信息系統(tǒng)S=(U,A,D),如果?t∈FDES(A1),s∈FDES(D),規(guī)則t→s是不確定的,那么S是不協(xié)調(diào)的;否則,S是協(xié)調(diào)的。

證明因?yàn)橐?guī)則t→s是不確定的,所以?x,y∈‖t‖,x∈‖s‖,y?‖s‖,使得(x,y)∈RA1(x,y)?RD。因此,RA1?RD不成立,S是不協(xié)調(diào)的反之,S是協(xié)調(diào)的。

根據(jù)文獻(xiàn)[8],我們可以得到如下命題3。

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

定義8對(duì)于一個(gè)協(xié)調(diào)的廣義多尺度決策信息系統(tǒng)S=(U,A,D),我們稱k∈L是S的最優(yōu)尺度組合,當(dāng)且僅當(dāng)Sk是協(xié)調(diào)的,且對(duì)于任意h≥k,Sh是不協(xié)調(diào)的。

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

證明根據(jù)定義3,顯然命題成立

例2表1是某中學(xué)的入學(xué)考試成績(jī)表,根據(jù)考生編號(hào),依次用x1,x2,…,x8來(lái)表示八位考生。通過(guò)觀察分析,這是一個(gè)廣義多尺度決策信息系統(tǒng),條件屬性A={語(yǔ)文，數(shù)學(xué)，英語(yǔ)},決策屬性D={是否錄取}。每個(gè)條件屬性分別有3個(gè)尺度標(biāo)記,依次是五分制、等級(jí)制和是否合格。

通過(guò)計(jì)算,我們可以知道表1是一個(gè)協(xié)調(diào)的廣義多尺度決策信息系統(tǒng),(3,3,2)是最優(yōu)尺度組合,即語(yǔ)文和數(shù)學(xué)分別取是否合格,英語(yǔ)取等級(jí)制我們?nèi)∽罴?xì)尺度組合,通過(guò)計(jì)算,得到以下決策規(guī)則集:

表1 A班級(jí)的考試成績(jī)表

確定性規(guī)則:

r1:(語(yǔ)文,1)∧(數(shù)學(xué),2)∧(英語(yǔ),1)→(錄取,否),確定性因子1,支持的對(duì)象x6;

r2:(語(yǔ)文,2)∧(數(shù)學(xué),3)∧(英語(yǔ),3)→(錄取,否),確定性因子1,支持的對(duì)象x2;

r3:(語(yǔ)文,3)∧(數(shù)學(xué),1)∧(英語(yǔ),2)→(錄取,否),確定性因子1,支持的對(duì)象x4;

r4:(語(yǔ)文,3)∧(數(shù)學(xué),3)∧(英語(yǔ),2)→(錄取,否),確定性因子1,支持的對(duì)象x8;

r5:(語(yǔ)文,3)∧(數(shù)學(xué),4)∧(英語(yǔ),3)→(錄取,是),確定性因子1,支持的對(duì)象x7;

r6:(語(yǔ)文,4)∧(數(shù)學(xué),4)∧(英語(yǔ),5)→(錄取,是),確定性因子1,支持的對(duì)象x3;

r7:(語(yǔ)文,4)∧(數(shù)學(xué),5)∧(英語(yǔ),4)→(錄取,是),確定性因子1,支持的對(duì)象x1;

r8:(語(yǔ)文,5)∧(數(shù)學(xué),4)∧(英語(yǔ),4)→(錄取,是),確定性因子1,支持的對(duì)象x5

我們?nèi)∽顑?yōu)尺度組合,通過(guò)計(jì)算,得到以下決策規(guī)則集:

確定性規(guī)則:

r9:(語(yǔ)文,合格)∧(數(shù)學(xué),合格)∧(英語(yǔ),優(yōu))→(錄取,是),確定性因子1,支持的對(duì)象x3;

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

r11:(語(yǔ)文,合格)∧(數(shù)學(xué),合格)∧(英語(yǔ),差)→(錄取,否),確定性因子1,支持的對(duì)象x8;

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

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

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

通過(guò)以上決策規(guī)則集的比較,容易得出,最優(yōu)尺度組合下的決策規(guī)則集,泛化效果更好。

針對(duì)于不協(xié)調(diào)的廣義多尺度決策信息系統(tǒng),在本文中,我們給出保持決策屬性正域不變的最優(yōu)尺度組合選擇的定義。

定義9設(shè)S=(U,A,D)是一個(gè)不協(xié)調(diào)的廣義多尺度決策信息系統(tǒng),我們稱k∈L是S的保持正域不變的最優(yōu)尺度組合,當(dāng)且僅當(dāng)posAk(D)=posA1(D),且對(duì)于任意h≥k,posAh(D)≠posA1(D)。

例3與表1相似,表2是某中學(xué)的入學(xué)考試成績(jī)表。

通過(guò)計(jì)算,我們可以知道表2是一個(gè)不協(xié)調(diào)的廣義多尺度決策信息系統(tǒng),(3,2,3)是保持正域不變的最優(yōu)尺度組合,即語(yǔ)文和英語(yǔ)分別取是否合格,數(shù)學(xué)取等級(jí)制我們?nèi)∽罴?xì)尺度組合,通過(guò)計(jì)算,得到以下決策規(guī)則集:

確定性規(guī)則:

r1:(語(yǔ)文,1)∧(數(shù)學(xué),3)∧(英語(yǔ),2)→(錄取,否),確定性因子1,支持的對(duì)象x4;

r2:(語(yǔ)文,3)∧(數(shù)學(xué),3)∧(英語(yǔ),4)→(錄取,是),確定性因子1,支持的對(duì)象x2;

r3:(語(yǔ)文,3)∧(數(shù)學(xué),4)∧(英語(yǔ),3)→(錄取,是),確定性因子1,支持的對(duì)象x8;

r4:(語(yǔ)文,4)∧(數(shù)學(xué),3)∧(英語(yǔ),3)→(錄取,是),確定性因子1,支持的對(duì)象x3;

r5:(語(yǔ)文,4)∧(數(shù)學(xué),4)∧(英語(yǔ),3)→(錄取,是),確定性因子1,支持的對(duì)象x6;

r6:(語(yǔ)文,5)∧(數(shù)學(xué),4)∧(英語(yǔ),3)→(錄取,是),確定性因子1,支持的對(duì)象x7。

不確定性規(guī)則:

r7:(語(yǔ)文,4)∧(數(shù)學(xué),2)∧(英語(yǔ),4)→(錄取,否),確定性因子0.5,支持的對(duì)象x1;

表2 B班級(jí)的考試成績(jī)表

r8:(語(yǔ)文,4)∧(數(shù)學(xué),2)∧(英語(yǔ),4)→(錄取,是),確定性因子0.5,支持的對(duì)象x5。

我們?nèi)”３终虿蛔兊淖顑?yōu)尺度組合,通過(guò)計(jì)算,得到以下決策規(guī)則集:

確定性規(guī)則:

r9:(語(yǔ)文,合格)∧(數(shù)學(xué),優(yōu))∧(英語(yǔ),合格)→(錄取,是),確定性因子1,支持的對(duì)象x6,x7,x8;

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

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

不確定性規(guī)則:

r12:(語(yǔ)文,合格)∧(數(shù)學(xué),差)∧(英語(yǔ),合格)→(錄取,否),確定性因子0.5,支持的對(duì)象x1;

r13:(語(yǔ)文,合格)∧(數(shù)學(xué),差)∧(英語(yǔ),合格)→(錄取,是),確定性因子0.5,支持的對(duì)象x5。

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

3 基于矩陣的規(guī)則提取與尺度選擇

事實(shí)上,集合與矩陣通過(guò)特定的矩陣運(yùn)算進(jìn)行聯(lián)系。在命題5中,我們給出利用特征矩陣計(jì)算規(guī)則確定性因子的方法。

證明根據(jù)規(guī)則確定性因子的定義,顯然可得

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

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

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

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

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

命題7對(duì)于一個(gè)協(xié)調(diào)的廣義多尺度決策信息系統(tǒng)S=(U,A,D),k∈L是S的最優(yōu)尺度組合當(dāng)且僅當(dāng)(GAk(MAkMD))1=MD,且對(duì)于任意h≥k,(GAh(MAhMD))1≠M(fèi)D。

根據(jù)命題7,對(duì)于協(xié)調(diào)的廣義多尺度決策信息系統(tǒng),我們給出利用特征矩陣來(lái)選擇最優(yōu)尺度組合的方法,見(jiàn)算法1。

根據(jù)廣義多尺度決策信息系統(tǒng)的協(xié)調(diào)性,我們可以知道算法1是收斂的。在不考慮步驟1和2對(duì)算法影響的情況下,算法1的時(shí)間復(fù)雜度是O(m×I1×…×Im)。

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

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

根據(jù)命題7,通過(guò)計(jì)算可得

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

且

(GA(3,3,3)(MA(3,3,3)MD))1≠M(fèi)D,

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

通過(guò)例4,我們知道矩陣方法判斷最優(yōu)尺度組合是直觀的和有效的。命題7闡明協(xié)調(diào)的廣義多尺度決策信息系統(tǒng)中最優(yōu)尺度組合與特征矩陣之間的聯(lián)系,并給出最優(yōu)尺度組合的矩陣計(jì)算方法。下面,我們研究不協(xié)調(diào)的廣義多尺度決策信息系統(tǒng)中,保持決策屬性正域不變的最優(yōu)尺度組合與特征矩陣之間的聯(lián)系,并給出矩陣計(jì)算方法。

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

命題8設(shè)S=(U,A,D)是一個(gè)不協(xié)調(diào)的廣義多尺度決策信息系統(tǒng),k∈L是S的保持正域不變的最優(yōu)尺度組合,當(dāng)且僅當(dāng)

且對(duì)于任意h≥k,不成立。

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

根據(jù)命題8,對(duì)于不協(xié)調(diào)的廣義多尺度決策信息系統(tǒng),我們給出利用特征矩陣來(lái)選擇保持決策屬性正域不變的最優(yōu)尺度組合的方法,見(jiàn)算法2。

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

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

根據(jù)命題8,通過(guò)計(jì)算可得

且

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

4 結(jié)論

規(guī)則提取與尺度選擇是多尺度信息系統(tǒng)中知識(shí)獲取的兩個(gè)重要方式。本文給出了廣義多尺度信息系統(tǒng)中規(guī)則提取與尺度組合選擇的矩陣方法,這樣的方法相較于傳統(tǒng)的基于集合運(yùn)算的方法是直觀的和簡(jiǎn)便的。此外,在廣義多尺度決策信息系統(tǒng)中,隨著尺度的粗化,決策規(guī)則的泛化效果越好。利用矩陣對(duì)最優(yōu)尺度組合進(jìn)行刻畫(huà),體現(xiàn)了廣義多尺度信息系統(tǒng)理論與矩陣?yán)碚撝g的密切聯(lián)系,同時(shí),它促進(jìn)了多尺度決策系統(tǒng)的理論研究。未來(lái)進(jìn)一步研究的工作是將此方法應(yīng)用于規(guī)則提取的算法設(shè)計(jì),以及改進(jìn)已有的尺度選擇算法。此外,我們也將通過(guò)對(duì)比實(shí)驗(yàn),進(jìn)一步分析尺度選擇算法的時(shí)間復(fù)雜度。