變精度多粒度粗糙集近似集更新的矩陣算法

鄭文彬 李進金 于佩秋 林藝東

摘 要：隨著信息大爆炸時代的到來，數(shù)據(jù)集的巨大化和數(shù)據(jù)集結(jié)構(gòu)的復(fù)雜化已經(jīng)成為近似計算中不能忽視的問題，而動態(tài)計算是解決這些問題的一種行之有效的途徑。對現(xiàn)有的應(yīng)用于經(jīng)典多粒度粗糙集動態(tài)近似集更新方法進行了改進，提出了應(yīng)用于變精度多粒度粗糙集（VPMGRS）的向量矩陣近似集計算與更新方法。首先，提出了一種基于向量矩陣的VPMGRS近似集靜態(tài)計算算法;其次，重新考慮了VPMGRS近似集更新時的搜索區(qū)域，并根據(jù)VPMGRS的性質(zhì)縮小了該區(qū)域，有效地提升了近似集更新算法的時間效率;再次，根據(jù)新的搜索區(qū)域，在VPMGRS近似集靜態(tài)計算算法的基礎(chǔ)上提出了一種新的VPMGRS近似集更新的向量矩陣算法;最后，通過實驗驗證了所提算法的有效性。

關(guān)鍵詞：動態(tài)計算;近似集更新;變精度多粒度粗糙集;矩陣算法

中圖分類號：TP18

文獻標(biāo)志碼：A

Matrixbased algorithm for updating approximations in

variable precision multigranulation rough sets

ZHENG Wenbin1，2*， LI Jinjin3， YU Peiqiu3， LIN Yidong4

1.School of Computer Science， Minnan Normal University， Zhangzhou Fujian 363000， China;

2.Fujian Key Laboratory of Granular Computing and Its Important Applications（Minnan Normal University）， Zhangzhou Fujian 363000， China;

3.School of Mathematics and Statistics， Minnan Normal University， Zhangzhou Fujian 363000， China;

4.School of Mathematical Sciences， Xiamen University， Xiamen Fujian 361005， China

Abstract：

In an information explosion era， the large scale and structure complexity of datasets become problems in approximation calculation. Dynamic computing is an efficient approach to solve these problems. With the development of existing updating method applied to the dynamic approximation in multigranular rough sets， a vector matrix based method for computing and updating approximations in Variable Precision MultiGranulation Rough Sets （VPMGRS） was proposed. Firstly， a static algorithm for computing approximations based on vector matrix for VPMGRS was presented. Secondly， the searching area for updating approximations in VPMGRS was reconsidered， and the area was shrunk according to the properties of VPMGRS， effectively improving the time efficiency of the approximation updating algorithm. Thirdly， according to the new searching area， a vector matrix based algorithm for updating approximations in VPMGRS was proposed based on the static algorithm for computing approximations. Finally， the effectiveness of the designed algorithm was verified by experiments.

Key words：

dynamic computing; approximation updating; variable precision multigranulation rough set; matrix algorithm

0?引言

自粗糙集[1]模型于1982年被波蘭學(xué)者Pawlak 提出以來，粗糙集模型被廣泛應(yīng)用于各種領(lǐng)域，例如模式識別[2]、機器學(xué)習(xí)[3]、圖像處理[4]、數(shù)據(jù)挖掘[5]等。為了拓展粗糙集模型的應(yīng)用范圍，學(xué)者提出了許多粗糙集模型的拓展模型，例如覆蓋粗糙集[6]、變精度粗糙集[7]、概率粗糙集[8]、多粒度粗糙集[9]、變精度多粒度粗糙集（Variable Precision MultiGranulation Rough Sets， VPMGRS）[10]等。

VPMGRS模型是竇慧莉等[10]于2012年提出的，該模型進一步拓展了多粒度粗糙集模型的應(yīng)用前景。

VPMGRS是一種強大的數(shù)學(xué)工具，在許多多粒度視角下的現(xiàn)實生活場景中具有非常廣泛的應(yīng)用和非常強大的表示能力; 然而自VPMGRS被提出以來，較少有學(xué)者進行VPMGRS近似集計算與近似集更新方面的研究。不論應(yīng)用何種粗糙集模型，包括且不限于VPMGRS模型，近似集計算都是應(yīng)用中必要且重要的一環(huán)，例如：在有些屬性約簡的過程中必須計算正域，在規(guī)則提取時必須計算下近似集和上近似集。 在數(shù)據(jù)大爆炸時代，近似集計算開始變得越來越困難，數(shù)據(jù)集的巨大化使得有時不可能在整個數(shù)據(jù)集上進行計算，數(shù)據(jù)集的復(fù)雜化使得數(shù)據(jù)的結(jié)構(gòu)也經(jīng)常變化，屬性增減、屬性值改變、樣本增多與減少在近似集計算時變得非常普遍。針對這些問題，在各種改變的場景下動態(tài)計算近似集是行之有效的解決方案。計算和更新多粒度粗糙集及其拓展模型的上下近似集引起眾多研究者的廣泛關(guān)注，這些研究通常分為4類，即：如何在增減屬性時更新近似集[11]，如何在改變屬性值時更新上下近似集[12]，如何在決策屬性改變時更新上下近似集[13]，如何在論域中對象變化時更新上下近似集[14]。

本文提出一種在屬性增加和減少時計算和更新VPMGRS上下近似集的新方法。首先提出了一種應(yīng)用于VPMGRS的向量矩陣近似集靜態(tài)計算方法;其次，根據(jù)VPMGRS的性質(zhì)，縮小了更新上下近似集的搜索區(qū)域，更小的搜索區(qū)域意味著更少的計算時間;再次，根據(jù)新的搜索區(qū)域，提出了在屬性增減時基于矩陣向量的VPMGRS近似集更新算法;最后，采用了幾個UCI（http：//archive.ics.uci.edu/ml/index.php）數(shù)據(jù)集進行實驗驗證了所提算法的有效性。

1?預(yù)備知識

本章列舉所有與本文工作相關(guān)的定義與定理。

定義1[15]設(shè)集合A與B是論域U的非空子集，定義集合A相對于集合B的相對正確分類率為：

P（A，B）=|A∩B|/|A|

其中|A|代表集合A的基數(shù)。

定義2[9]令S=（U，AT，V， f）為一個信息系統(tǒng)，其中：U={x1，x2，…，xn}為非空有限論域;AT={A1，A2，…，Am}為非空有限屬性集族;Ak∈AT是一個屬性集。V=∪A∈ATVA為屬性值的值域，VA為屬性集A的值域;f：U×AT→V為一個決策函數(shù)使得f（x，A）∈VA對任意的A∈AT，x∈U都成立。

定義3[10]變精度多粒度樂觀粗糙集（Optimistic Variable Precision MultiGranulation Rough Sets， OVPMGRS）。令S=（U，AT，V， f）為一個信息系統(tǒng)。對于任意的XU， X的可變精度多粒度樂觀下近似集與樂觀上近似集分別表示為：

mk=1AβkO（X）={x∈U|P（[x]A1，X）≥β∨

P（[x]A2，X）≥β∨…∨P（[x]Am，X）≥β}

mk=1AβkO（X）=～mk=1AβkO（～X）

其中～X表示X的補集，β∈（0.5，1]。

由對偶性容易得到以下定理：

定理1[10]令S=（U，AT，V， f）為一個信息系統(tǒng)。 對于任意的XU，X的可變精度多粒度樂觀上近似集表示為mk=1AβkO（X），則有：

mk=1AβkO（X）={x∈U|P（[x]A1，X）>（1-β）∧

P（[x]A2，X）>（1-β）∧…∧

P（[x]Am，X）>（1-β）}

定義4[10]變精度多粒度悲觀粗糙集（Pessimistic Variable Precision MultiGranulation Rough Sets， PVPMGRS）。令S=（U，AT，V， f）為一個信息系統(tǒng)。 對于任意的XU，X的可變精度悲觀下近似集與上近似集分別表示為：

mk=1AβkP（X）={x∈U|P（[x]A1，X）≥β∧

P（[x]A2，X）≥β∧…∧P（[x]Am，X）≥β}

mk=1AβkP（X）=～mk=1AβkP（～X）

由對偶性容易得到以下定理：

定理2[10]令S=（U，AT，V， f）為一個信息系統(tǒng)。 對于任意的XU，X的可變精度多粒度悲觀上近似集表示為mk=1AβkP（X），則有：

mk=1AβkP（X）={x∈U|P（[x]A1，X）>（1-β）∨

P（[x]A2，X）>（1-β）∨…∨

P（[x]Am，X）>（1-β）}

定義5[16]令S=（U，AT，V， f）為一個信息系統(tǒng)。對于任意的XU，X的向量矩陣表示為G（X）=[g1（X），g2（X），…，g|U|（X）]T，其中g(shù)i（X）=1，xi∈X0，xiX，T表示矩陣的轉(zhuǎn)置。

定理3?對于任意的集合X，YU，X相對于Y的相對正確分類率為：

P（X，Y）=[G（X）]T·G（Y）∑|U|i=1gi（X）

其中·為矩陣乘法。

證明?xi∈X∩Y ?gi（X）=1∧gi（Y）=1 ?|X∩Y|=[G（X）]T·G（Y）

綜上所述，P（X，Y）=[G（X）]T·G（Y）∑|U|i=1gi（X）。

2?基于矩陣的近似集靜態(tài)計算算法

為了對變精度多粒度粗糙集（VPMGRS）近似集更新方法進行研究，本文首先對其近似集計算方法進行研究，給出靜態(tài)的VPMGRS上、下近似集計算算法。

定義6?令S=（U，AT，V， f）為一個信息系統(tǒng)。對于任意的XU，X在屬性集Ak上的變精度多粒度近似集特征向量定義為HAk（X）=[hAk1（X），hAk2（X），…，hAk|U|（X）]T，其中：

hAki（X）=P（[xi]Ak，X）; k∈{1，2，…，m}

顯然，當(dāng)[xi]Ak∩X=時，有hAki（X）=0，即如果能夠確保[xi]Ak∩X=，則可以直接令hAki（X）=0。

定義7?令S=（U，AT，V， f）為一個信息系統(tǒng)。對于任意的XU，定義向量HAk（X）兩個截向量HAk≥α（X）=[Ak1（X），Ak2（X），…，Ak|U|（X）]T與HAk>α（X）=[Ak1（X），Ak2（X），…，Ak|U|（X）]T，式中：

Aki（X）0，hAki<α1，hAki≥α

Aki（X）0，hAki≤α1，hAki>α

其中：k∈{1，2，…，m}， i∈{1，2，…，|U|}，α∈R為任一實數(shù)。

定理4?令S=（U，AT，V， f）為一個信息系統(tǒng)。對于任意的XU，X的變精度多粒度樂觀下近似集與樂觀上近似集分別表示為mk=1AβkO（X）和mk=1AβkO（X），則有：

1）G（mk=1AβkO（X））=∨mk=1HAk≥β（X）

2）G（mk=1AβkO（X））=∧mk=1HAk>1-β（X）

證明

1）xi∈mk=1AβkO（X） ?gi（mk=1AβkO（X））=1 ?k∈{1，2，…，m}，s.t.P（[xi]Ak，X）≥β ?∨mk=1hAki（X）≥β ?∨mk=1Aki（X）=1。

綜上所述，G（mk=1AβkO（X））=∨mk=1HAk≥β（X）。

2）證明過程類似于1）。

算法1?基于矩陣的變精度多粒度粗糙集上、下近似集算法。

輸入?1）S=（U，AT，V， f）;2）G（[xi]Ak），k∈{1，2，…，m}，i∈{1，2，…，|U|}; 3）G（X）;4）β;

輸出?mk=1AβkO（X）和mk=1AβkO（X）， mk=1AβkP（X）和mk=1AβkP（X）。

程序前

1）

n←|U|

2）

For i=1→n

3）

For j=1→n

4）

For k=1→m?#m=|AT|

5）

If gi（X）=1∧gi（[xj]Ak）=1

#保證[xj]Ak∩X≠

6）

hAkj（X）←[G（[xj]Ak）]T·G（X）∑|U|i=1gi（[xj]Ak）

7）

End If

8）

End For

9）

End For

10）

End For

11）

G（mk=1AβkO（X））←∨mk=1HAk≥β（X）

12）

G（mk=1AβkO（X））←∧mk=1HAk>1-β（X）

13）

G（mk=1AβkP（X））←∧mk=1HAk≥β（X）

14）

G（mk=1AβkP（X））←∨mk=1HAk>1-β（X）

15）

Return mk=1AβkO（X）和mk=1AβkO（X）， mk=1AβkP（X）和mk=1AβkP（X）

程序后

定理5

令S=（U，AT，V， f）為一個信息系統(tǒng)。對于任意的XU，X的變精度多粒度悲觀下近似集與上近似集分別表示為mk=1AβkP（X）和mk=1AβkP（X），則有：

1）G（mk=1AβkP（X））=∧mk=1HAk≥β（X）;

2）G（mk=1AβkP（X））=∨mk=1HAk>1-β（X）。

證明?證明過程類似于定理4。

由定理4與定理5可以得到算法1，即為基于矩陣的變精度多粒度粗糙集上下近似集算法，若RAk（X）={x|[x]Ak∩X≠}，則該算法的時間復(fù)雜度為Θ（max|RAk（X）||U|）。步驟2）～10）是用來計算HAk（X）的，時間復(fù)雜度為Θ（max|RAk（X）||U|）; 步驟11）～14）是用來計算mk=1AβkO（X）、mk=1AβkO（X）、mk=1AβkP（X）、mk=1AβkP（X）的，時間復(fù)雜度為Θ（m|U|）。

3?基于矩陣的近似集更新方法

基于本文給出的變精度多粒度粗糙集近似集靜態(tài)計算方法，提出了基于矩陣的變精度多粒度粗糙集近似集更新算法。

3.1?添加屬性時的近似集更新算法

在本節(jié)中，用St=（U，AT，V， f）表示一個t時刻的信息系統(tǒng)，其中AT={A1，A2，…，Am}為非空有限屬性集族，用St+1=（U，AT，V，F(xiàn)）表示一個t+1時刻的信息系統(tǒng)，其中AT={A1，A2，…，Am}為非空有限屬性集族。用mk=1AβkO（X）和mk=1AβkO（X）表示t時刻OVPMGRS的上、下近似集，用mk=1AβkP（X）和mk=1AβkP（X）表示t時刻PVPMGRS的上、下近似集，Ak是一個屬性集，β∈（0.5，1]。 用mk=1AβkO（X）和mk=1AβkO（X）表示t+1時刻OVPMGRS的上、下近似集，用mk=1AβkP（X）和mk=1AβkP（X）表示t+1時刻PVPMGRS的上、下近似集，Ak∈AT，Ak∈AT使得AkAk，即從t時刻到t+1時刻屬性增加了。

定理6?令St=（U，AT，V， f）為一個t時刻的信息系統(tǒng)，St+1=（U，AT，V，F(xiàn)）為一個t+1時刻的信息系統(tǒng)。HAk（X）為X在屬性集Ak上的變精度多粒度近似特征向量，HAk（X）為X在屬性集Ak上的變精度多粒度近似集特征向量，則對于任意的k∈{1，2，…，m}，X有以下性質(zhì)成立：

1）hAki（X）=1hAki（X）=1

2）hAki（X）=0hAki（X）=0

證明

1） hAki（X）=1 ?P（[xi]Ak，X）=1 ?[xi]AkX

[xi]AkX ?hAki（X）=1。

2） 證明類似于1）。

定理6說明，在向?qū)傩约刑砑訉傩詴r，計算HAk（X）可以不計算HAk（X）中0和為1的那些位，因為由[x]Ak[x]Ak，x∈U都成立，有HAk（X）中為0和1的位在HAk（X）中也不變。

算法2?基于矩陣的變精度多粒度粗糙集上下近似集更新算法。

輸入?1） S=（U，AT，V， f）; 2） G（[xi]Ak），k∈{1，2，…，m}，i∈{1，2，…，|U|}; 3）G（X）; 4）β; 5）HAk（X）。

輸出?mk=1AβkO（X）和mk=1AβkO（X）， mk=1AβkP（X）和mk=1AβkP（X）。

程序前

1）

HAk（X）←HAk（X）

2）

n←|U|

3）

For i=1→n

4）

For k=1→m?#m=|AT|

5）

If hAki（X）∈（0，1）

6）

hAki（X）←[G（[xi]Ak）]T·G（X）∑|U|i=1gi（[xi]Ak）

7）

End If

8）

End For

9）

End For

10）

G（mk=1AβkO（X））←∨mk=1HAk≥β（X）

11）

G（mk=1AβkO（X））←∧mk=1HAk>1-β（X）

12）

G（mk=1AβkP（X））←∧mk=1HAk≥β（X）

13）

G（mk=1AβkP（X））←∨mk=1HAk>1-β（X）

14）

Return mk=1AβkO（X）和mk=1AβkO（X），mk=1AβkP（X）和mk=1AβkP（X）

程序后

由定理6可以得到變精度多粒度粗糙集上下近似集更新算法，因為只對HAk（X）中處于（0，1）區(qū)間內(nèi)的元素進行更新，若RAk′（X）={x|[x]Ak∩X≠∧[x]AkX}，則算法2的時間復(fù)雜度為O（∑mk=1|R′Ak（X）||U|）。步驟3）～9）是用來更新HAk（X）的，時間復(fù)雜度為O（∑mk=1|RAk′（X）||U|）; 步驟10）～13）是用來更新mk=1AβkO（X）、mk=1AβkO（X）、mk=1AβkP（X）、mk=1AβkP（X）的，時間復(fù)雜度為O（m|U|）。顯然有RAk′（X）RAk（X）即最壞的情況下動態(tài)更新算法的時間復(fù)雜度才會等于靜態(tài)計算算法。

3.2?減少屬性時的近似集更新

下面將舉出反例說明屬性減少時，定理6將不再成立。

例1?一個多粒度信息系統(tǒng)如表1所示。令X={x2，x5，x6}，A1={a1，a2，a3}，A2={a4，a5，a6}，A3={a7，a8，a9}，A1={a2}，A2={a4}，A3={a9}，由定義6知hA12（X）=1，hA12（X）=1/2≠1;hA31（X）=0，hA31（X）=1/2≠0，所以當(dāng)屬性減少時定理6不再成立。

例1說明了當(dāng)屬性減少時不能使用本文所提出的近似集更新方法進行上下近似集更新，當(dāng)本文的動態(tài)算法不能用于屬性減少時，可以用本文提出的靜態(tài)算法來計算變精度多粒度粗糙集上下近似集。

4?UCI數(shù)據(jù)實驗分析

為了驗證算法的有效性，本文選取了8個UCI數(shù)據(jù)來驗證近似集靜態(tài)計算算法與近似集更新算法的有效性。實驗所使用的UCI數(shù)據(jù)集如表2所示?？梢钥吹綐颖緮?shù)從194到1-000，屬性數(shù)目從5到59。所有實驗均在系統(tǒng)為64bit Windows 10，CPU為Inter Core i7 6700HQ CPU 2.60GHz，16GB內(nèi)存的個人計算機上進行，所使用的編程語言是Matlab r2015b。

4.1?不同大小數(shù)據(jù)集的計算時間對比

在本節(jié)中，令β=0.9，將數(shù)據(jù)集等分成10份U1，U2，…，U10，然后以每一份數(shù)據(jù)集為增加的步長，逐步地使數(shù)據(jù)集增大，即dataset1=U1，dataset2=U1∪U2，dataset3=U1∪U2∪U3…并使X大致為每個臨時數(shù)據(jù)集的0.85倍大小，X中元素從每個臨時數(shù)據(jù)集中隨機選擇。模擬屬性增加時，對每個數(shù)據(jù)集，首先隨機選出一個屬性，然后將剩余的屬性分為大致相等的三組At1、At2、At3。首先用算法1計算VPMGRS上下近似集，然后令A(yù)t1、At2、At3、At+11=At1∪、At+12=At2∪、At+13=At3∪，分別使用算法1（靜態(tài)算法）與算法2（動態(tài)算法）及對比算法基于關(guān)系矩陣的多粒度粗糙集近似更新算法[17]與基于關(guān)系矩陣的多粒度粗糙集近似計算算法[17]計算VPMGRS上下近似集并對比計算時間，得出如圖1的實驗結(jié)果，本文實驗中計算時間的單位為秒。

[11]YANG X， QI Y， YU H， et al. Updating multigranulation rough approximations with increasing of granular structures[J]. Knowledge Based Systems， 2014， 64（1）： 59-69.

[12]CHEN H， LI T， LUO C， et al. A rough setbased method for updating decision rules on attribute values coarsening and refining [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（12）： 2886-2899.

[13]CHENG Y. Dynamic maintenance of approximations under fuzzy rough sets [J]. International Journal of Machine Learning and Cybernetics， 2018， 9（12）： 2011-2026.

[14]HU J， LI T， LUO C， et al. Incremental fuzzy probabilistic rough sets over two universes[J]. International Journal of Approximate Reasoning， 2017， 81： 28-48.

[15]ZIARKO W. Variable precision rough set model[J]. Journal of Computer and System Sciences， 1993， 46（1）： 39-59.

[16]程燕.基于矩陣的覆蓋粗糙集算法研究[D]. 合肥： 安徽大學(xué)， 2017. （CHENG Y. Study on covering rough set algorithm based on matrix [D]. Hefei： Anhui University， 2017.）

[17]HU C， LIU S， LIU G. Matrixbased approaches for dynamic updating approximations in multigranulation rough sets [J]. KnowledgeBased Systems， 2017， 122： 51-63.

This work is partially supported by the National Natural Science Foundation of China （11871259， 61379021）， the Youth Fund of Natural Science Foundation of China （11701258）.

ZHENG Wenbin， born in 1971， M. S.， senior lecturer. His research interests include rough set， granular computing， data mining， artificial intelligence.

LI Jinjin， born in 1960， Ph. D.， professor. His research interests include artificial intelligence， granular computing， topology.

YU Peiqiu， born in 1991， M. S. candidate. His research interests include rough set， granular computing， data mining， artificial intelligence.

LIN Yidong， born in 1989， Ph. D. candidate. His research interests include uncertainty theory.