劉鳳玲，林國(guó)平

(閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建 漳州 363000)

1 引 言

數(shù)據(jù)規(guī)模隨著信息技術(shù)的迅速發(fā)展而不斷膨脹，粒計(jì)算常用于處理復(fù)雜的數(shù)據(jù)系統(tǒng).粒計(jì)算是將所需探究的論域劃分成若干相對(duì)簡(jiǎn)單的粒，簇、塊或集合構(gòu)成了這些粒.

Zadeh于1979年首次提出模糊信息粒這一概念[1].隨后，相關(guān)應(yīng)用背景的粒計(jì)算模型與方法相繼被提出[2-5].信息粒在解決復(fù)雜問(wèn)題中起重要作用，其可將較為復(fù)雜的信息系統(tǒng)抽象地轉(zhuǎn)化為若干相對(duì)簡(jiǎn)單的信息系統(tǒng)，這樣既可以降低處理難度，又可以提高預(yù)測(cè)信息的準(zhǔn)確性.

在大部分信息系統(tǒng)中，同一對(duì)象在同一個(gè)屬性下只有一個(gè)屬性值，這使得人們只能從固定的粒度或視角分析數(shù)據(jù)信息.然而，在實(shí)際應(yīng)用中，根據(jù)實(shí)際問(wèn)題的不同需要，同一個(gè)對(duì)象在同一個(gè)屬性下可以取不同粒度層次標(biāo)記的值. 例如，需要評(píng)定獎(jiǎng)學(xué)金時(shí)學(xué)生的考試成績(jī)一般記錄為0～100之間的數(shù)，需要知曉成績(jī)優(yōu)秀、較好等級(jí)別的人數(shù)時(shí)可以將成績(jī)記為“優(yōu)秀”、“較好”、“中等”、“差”. 進(jìn)一步的，如果需要，還可以將其分為兩個(gè)值，比如給予學(xué)位認(rèn)定時(shí)記為“合格”和“不合格”.基于此，Wu等人根據(jù)對(duì)象在決策系統(tǒng)中擁有不同的粒度標(biāo)記，于2011年首次給出了多粒度標(biāo)記決策系統(tǒng)的概念[6].近年來(lái)，基于多粒度標(biāo)記劃分的粗糙集數(shù)據(jù)分析方法得到不斷完善和發(fā)展，多粒度標(biāo)記決策系統(tǒng)是人們研究的熱點(diǎn). 目前，查閱相關(guān)文獻(xiàn)發(fā)現(xiàn)學(xué)者們主要從最優(yōu)粒度選擇[7-17]、規(guī)則約簡(jiǎn)或提取[18，19]及知識(shí)表示[20]等方面對(duì)多粒度標(biāo)記決策系統(tǒng)進(jìn)行研究. 從系統(tǒng)的協(xié)調(diào)性與完備性的角度來(lái)看，學(xué)者們主要研究了協(xié)調(diào)且完備的、協(xié)調(diào)不完備的以及不協(xié)調(diào)但完備的這三種多粒度標(biāo)記決策系統(tǒng).在實(shí)際應(yīng)用中，多粒度標(biāo)記決策系統(tǒng)是常被用于各種信息分析，如被廣泛應(yīng)用于數(shù)據(jù)挖掘、圖像處理、人工智能、地理信息甄別和軍事技術(shù)等領(lǐng)域.

如今是大數(shù)據(jù)時(shí)代，在許多實(shí)際情況下，由于各種需求或人為失誤，數(shù)據(jù)可能會(huì)發(fā)生變化.因此，需要對(duì)動(dòng)態(tài)數(shù)據(jù)集中隱藏的知識(shí)進(jìn)行相應(yīng)的更新. 增量更新機(jī)制是利用前面獲得的計(jì)算結(jié)果來(lái)獲取動(dòng)態(tài)數(shù)據(jù)集中的知識(shí)而不是重新從頭開(kāi)始計(jì)算.在動(dòng)態(tài)環(huán)境中，目前基于粗糙集理論的增量更新方法主要涉及對(duì)象的變化[21-23]、屬性的變化[24，25]以及屬性值的變化[26，27].而有關(guān)多粒度標(biāo)記決策系統(tǒng)方面的動(dòng)態(tài)更新，本人只查閱到學(xué)者們討論了在多粒度決策系統(tǒng)中，對(duì)象更新環(huán)境下選擇最優(yōu)粒度的策略并設(shè)計(jì)了相應(yīng)的算法.

事實(shí)上，在實(shí)際應(yīng)用中人為或其他因素難免不出現(xiàn)收集到的多粒度標(biāo)記決策系統(tǒng)在某個(gè)粒度標(biāo)記下的屬性值是錯(cuò)誤的，而此時(shí)則需要將正確的屬性值更新進(jìn)去，從而得正確的數(shù)據(jù)，即此時(shí)新的系統(tǒng)屬性值發(fā)生了更新.若當(dāng)前粒度尺度下屬性值發(fā)生變化，則粗于該粒度尺度的粒度尺度可能也隨之發(fā)生變化.一般來(lái)說(shuō)，在多粒度標(biāo)記系統(tǒng)中等級(jí)越小的粒度越細(xì)，然而粒越細(xì)獲取知識(shí)的成本越高，因此選擇合適的粒度級(jí)別來(lái)獲取規(guī)則及求目標(biāo)近似集等較為重要，即最優(yōu)粒度選擇是多粒度標(biāo)記系統(tǒng)中的知識(shí)獲取較為關(guān)鍵的一步.基于此，本文針對(duì)屬性值變化環(huán)境下的不協(xié)調(diào)多粒度決策系統(tǒng)最優(yōu)粒度的選擇進(jìn)行研究.

由于WU在文獻(xiàn)[9]中分析了不協(xié)調(diào)多粒度決策系統(tǒng)中8種不協(xié)調(diào)性選擇最優(yōu)粒度的對(duì)比，指出實(shí)際上只有4種：分布協(xié)調(diào)； 最大分布協(xié)調(diào)；而分配協(xié)調(diào)、似然協(xié)調(diào)、上近似協(xié)調(diào)及廣義協(xié)調(diào)互相等價(jià)； 下近似協(xié)調(diào)與信任協(xié)調(diào)等價(jià).基于此，本文將只討論4種協(xié)調(diào)性下屬性值變化環(huán)境下的不協(xié)調(diào)多粒度決策系統(tǒng)選擇最優(yōu)粒度的策略：分布協(xié)調(diào)、最大分布協(xié)調(diào)、上近似協(xié)調(diào)及下近似協(xié)調(diào).

2 基本知識(shí)

2.1 多粒度標(biāo)記決策系統(tǒng)的概念

在多粒度標(biāo)記系統(tǒng)中，每一個(gè)屬性aj∈AT均為多粒度標(biāo)記屬性，也即對(duì)于同一個(gè)對(duì)象x∈U在不同粒度層面下有不同的取值.為方便討論，本文約定沒(méi)有特別說(shuō)明情況下在同一系統(tǒng)中，所有條件屬性的粒度層次均為I.

對(duì)任意的Ck?C，將論域U在Ck下的等價(jià)關(guān)系、等價(jià)類及等價(jià)劃分分別記為：

類似記：Rq0kig00={(x，y)∈U×U|f0emiqkc(x)=f0uq0wo0(x)}，[x]qcm0swm={y∈U|(x，y)∈Rkq0e00k}，U/Rwu0cyuc={[x]wi0cmme|x∈U}={D1，D2，…，Dr}，r為決策類劃分的個(gè)數(shù)，即r=|U/Ru0cy8ou|.

對(duì)于論域U中的一個(gè)子集X，其關(guān)于RCk的下近似和上近似分別為：

若對(duì)任意的[x]RCk∈U/RCk，總存在[x]Rd∈U/R6gcam00使得[x]RCk?[x]Rd成立，則記RCk?Rd.

假設(shè)dIS=(U，C∪qykueyo)為一個(gè)多決策的多粒度標(biāo)記決策系統(tǒng)，該系統(tǒng)中所有條件屬性均有I個(gè)等級(jí)粒度，則dIS=(U，C∪0c0qimg)可分解為I個(gè)信息系統(tǒng)，也即dIS=dIS1∪dIS2∪…∪dISI.

2.2 不協(xié)調(diào)多粒度標(biāo)記決策系統(tǒng)的協(xié)調(diào)性與最優(yōu)粒度選擇

定義3[6].設(shè)dIS=(U，C∪8mkqmsy)為多粒度決策系統(tǒng)，若RC1?Rd，則系統(tǒng)dIS是協(xié)調(diào)的.若進(jìn)一步滿足RCk?Rd，則稱dISk=(U，Ck∪ygokiq0)協(xié)調(diào).若dISk=(U，Ck∪qkiuos0)協(xié)調(diào)，則對(duì)任意的k′

定義4[9].設(shè)dIS=(U，C∪mw08m00)為不協(xié)調(diào)的多粒度決策系統(tǒng)，則

1)如果LCk(d)=LC1(d)，就稱dISk關(guān)于dIS下近似協(xié)調(diào).若dISk關(guān)于dIS下近似協(xié)調(diào)，但若k+1≤I，dISk+1關(guān)于dIS不是下近似協(xié)調(diào)，那么S的下近似最優(yōu)粒度為第k粒度層次.

2)如果HCk(d)=HC1(d)，就稱dISk關(guān)于dIS上近似協(xié)調(diào).若dISk關(guān)于dIS上近似協(xié)調(diào)，但如果k+1≤I，dISk+1關(guān)于dIS不是上近似協(xié)調(diào)，那么S的下近似最優(yōu)粒度為第k粒度層次.

3)如果對(duì)任意的x∈U，有μCk(d)=μC1(d)，就稱dISk關(guān)于dIS分布協(xié)調(diào).若dISk關(guān)于dIS分布協(xié)調(diào)，但若k+1≤I，dISk+1關(guān)于dIS不是分布協(xié)調(diào)，那么S的分布最優(yōu)粒度為第k粒度層次.

4)如果對(duì)任意的x∈U，有γCk(d)=γC1(d)，就稱dISk關(guān)于dIS最大分布協(xié)調(diào).若dISk關(guān)于dIS最大分布協(xié)調(diào)，但若k+1≤I，dISk+1關(guān)于dIS不是最大分布協(xié)調(diào)，那么S的最大分布最優(yōu)粒度為第k粒度層次.

3 屬性值變化環(huán)境下的不協(xié)調(diào)多粒度決策系統(tǒng)的最優(yōu)粒度選擇

定理1.設(shè)在t時(shí)刻，不協(xié)調(diào)多粒度決策系統(tǒng)為dIS(t)=(U，C∪yseomsa)，且系統(tǒng)dIS(t)的下近似最優(yōu)粒度層次為第kt粒度層次；在t+1時(shí)刻，k′k粒度層次下的屬性值也隨之發(fā)生變化，記此時(shí)的多粒度決策系統(tǒng)為dISt+1=(U，C∪u0ckgyu)，并記此時(shí)該系統(tǒng)dISt+1的下近似最優(yōu)粒度層次為第kt+1粒度層次，則以下兩個(gè)命題成立：

1)當(dāng)k>kt+1時(shí)，則kt+1=kt；

2)當(dāng)k≤kt+1時(shí)，若dISk關(guān)于dISt+1不是下近似協(xié)調(diào)的，則kt+1=k-1；若dISk關(guān)于dISt+1是下近似協(xié)調(diào)的，則判斷k+1的下近似協(xié)調(diào)性，若dISk+1關(guān)于dISt+1是下近似協(xié)調(diào)的，則繼續(xù)判斷k+2的下近似協(xié)調(diào)性，以此循環(huán)，直至k+m關(guān)于dISt+1不是下近似協(xié)調(diào)的，則kt+1=k+m-1.

證明：在t時(shí)刻，系統(tǒng)dIS(t)的下近似最優(yōu)粒度層次為第kt粒度層次，則由定義4易知，對(duì)任意的k′≤kt，dISk′均關(guān)于dISt是下近似協(xié)調(diào)的；dISkt+1關(guān)于dISt不下近似協(xié)調(diào).

1)若k>kt+1，則說(shuō)明在t+1時(shí)刻，任意的k′≤kt+1所對(duì)應(yīng)的屬性值均未發(fā)生變化.此時(shí)對(duì)任意的k′≤kt+1，dISk′均關(guān)于dISt+1是下近似協(xié)調(diào)的，又dISkt+1關(guān)于dISt+1不是下近似協(xié)調(diào)的，從而由定義4可知t+1時(shí)刻系統(tǒng)的下近似最優(yōu)粒度為kt.即可得kt+1=kt.

2)若k≤kt+1，則說(shuō)明任意的k′≤k-1所對(duì)應(yīng)的屬性值均未發(fā)生變化.即此時(shí)對(duì)任意的k′≤k-1，dISk′均關(guān)于dISt+1是下近似協(xié)調(diào)的.若dISk關(guān)于dISt+1不是下近似協(xié)調(diào)的，又dISk-1關(guān)于dISt+1是下近似協(xié)調(diào)的，則由定義4可知t+1時(shí)刻系統(tǒng)的下近似最優(yōu)粒度層次為k-1；若dISk關(guān)于dISt+1下近似協(xié)調(diào)則由定義4中的(1)可知成立.

下面給出例子來(lái)分析及理解所提出的定理.

例1.如表1為一個(gè)多粒度標(biāo)記決策系統(tǒng)，記為dIS=(U，C∪0o0ge0w).該表的條件屬性有三個(gè)粒度層次，其中“G，F(xiàn)，B，S，M，L，Y，N”分別表示“好，中等，差，小，中，大，是，否”.按粒度層次該信息表可分解為三個(gè)信息表，即dIS=dIS1∪dIS2∪dIS3，其中，

表1 多決策的多粒度標(biāo)記信息表Table 1 Multi-granular labeled table with multi-decision

定理2.設(shè)在t時(shí)刻，不協(xié)調(diào)多粒度決策系統(tǒng)為dIS(t)=(U，C∪uomyiyc)，且系統(tǒng)dIS(t)的上近似最優(yōu)粒度層次為第kt粒度層次；在t+1時(shí)刻，k′k粒度層次下的屬性值也隨之發(fā)生變化，記此時(shí)的多粒度決策系統(tǒng)為dISt+1=(U，C∪0gqm0s0)，并記此時(shí)該系統(tǒng)dISt+1的上近似最優(yōu)粒度層次為第kt+1粒度層次，則

1)當(dāng)k>kt+1時(shí)，則kt+1=kt；

2)當(dāng)k≤kt+1時(shí)，

若dISk關(guān)于dISt+1不是上近似協(xié)調(diào)的，則kt+1=k-1；

若dISk關(guān)于dISt+1是上近似協(xié)調(diào)的，則判斷k+1的上近似協(xié)調(diào)性，若dISk+1關(guān)于dISt+1是上近似協(xié)調(diào)的，則繼續(xù)判斷k+2的上近似協(xié)調(diào)性，以此循環(huán)，直至k+m關(guān)于dISt+1不是上近似協(xié)調(diào)的，則kt+1=k+m-1.

定理3.設(shè)在t時(shí)刻，不協(xié)調(diào)多粒度決策系統(tǒng)為dIS(t)=(U，C∪iuigio0)，且系統(tǒng)dIS(t)的分布最優(yōu)粒度層次為第kt粒度層次；在t+1時(shí)刻，k′k粒度層次下的屬性值也隨之發(fā)生變化，記此時(shí)的多粒度決策系統(tǒng)為dISt+1=(U，C∪0kgsc80)，并記此時(shí)該系統(tǒng)dISt+1的分布最優(yōu)粒度層次為第kt+1粒度層次，則以下兩個(gè)命題成立：

1)當(dāng)k>kt+1時(shí)，則kt+1=kt；

2)當(dāng)k≤kt+1時(shí)，

若dISk關(guān)于dISt+1不是分布協(xié)調(diào)的，則kt+1=k-1；

若dISk關(guān)于dISt+1是分布協(xié)調(diào)的，則判斷k+1的分布協(xié)調(diào)性，若dISk+1關(guān)于dISt+1是分布協(xié)調(diào)的，則繼續(xù)判斷k+2的分布協(xié)調(diào)性，以此循環(huán)，直至k+m關(guān)于dISt+1不是分布協(xié)調(diào)的，則kt+1=k+m-1.

定理4.設(shè)在t時(shí)刻，不協(xié)調(diào)多粒度決策系統(tǒng)為dIS(t)=(U，C∪oi8owqg)，且系統(tǒng)dIS(t)的最大分布最優(yōu)粒度層次為第kt粒度層次；在t+1時(shí)刻，k'k粒度層次下的屬性值也隨之發(fā)生變化，記此時(shí)的多粒度決策系統(tǒng)為dISt+1=(U，C∪osqu0qi)，并記此時(shí)該系統(tǒng)dISt+1的最大分布最優(yōu)粒度層次為第kt+1粒度層次，則以下兩個(gè)命題成立：

1)當(dāng)k>kt+1時(shí)，則kt+1=kt；

2)當(dāng)k≤kt+1時(shí)，

若dISk關(guān)于dISt+1不是最大分布協(xié)調(diào)的，則kt+1=k-1；

若dISk關(guān)于dISt+1是最大分布協(xié)調(diào)的，則判斷k+1的最大分布協(xié)調(diào)性，若dISk+1關(guān)于dISt+1是最大分布協(xié)調(diào)的，則繼續(xù)判斷k+2的最大分布似協(xié)調(diào)性，以此循環(huán)，直至k+m關(guān)于dISt+1不是最大分布協(xié)調(diào)的，則kt+1=k+m-1.

4 屬性值變化環(huán)境下的不協(xié)調(diào)多粒度決策系統(tǒng)的最優(yōu)粒度選擇算法

下面以下近似協(xié)調(diào)為例給出相應(yīng)的靜態(tài)算法和動(dòng)態(tài)算法.

算法1.靜態(tài)：多粒度決策系統(tǒng)的最優(yōu)粒度選擇

輸入：t+1時(shí)刻求得的多粒度決策系統(tǒng)dIS(t+1)=(U，C∪owuqcgk).

輸出：多粒度決策表的最優(yōu)粒度kt+1.

Step1.計(jì)算決策劃分U/Rd={D1，D2，…，Dr}，k′=1；

Step2.當(dāng)k′=1：|I|時(shí)，則計(jì)算[x]Ck′(x∈U)；

Step3.當(dāng)k′=1：|I|時(shí)，求出LCk′(d)；

Step4.判斷LCk′(d)與LC1(d) 的關(guān)系，若LCk′(d)≠LC1(d),則kt+1=kt-1,停止運(yùn)算.若LCk′(d)=LC1(d),則轉(zhuǎn)Step 5.

Step5.若k′+1>I,則kk+1=k′,停止運(yùn)算；若k′+1≤I,則k′=k′+1,并轉(zhuǎn)到Step 2.

算法2.動(dòng)態(tài)：多粒度決策系統(tǒng)在屬性值更新環(huán)境下的最優(yōu)粒度選擇

輸入：t時(shí)刻求得的多粒度決策系統(tǒng)dIS(t)=(U，C∪0kus0i0)及其最優(yōu)粒度層次kt及其決策劃分{D1，D2， …，Dr}、t+1時(shí)刻的多粒度決策系統(tǒng)dIS(t+1)，屬性值變化的最小粒度層次k.

輸出：多粒度決策表在屬性值更新之后的最優(yōu)粒度kt+1.

Step1.判斷k與kt+1的大小關(guān)系，若k>kt+1，則轉(zhuǎn)Step2;若k≤kt+1，則轉(zhuǎn)Step3；

Step2.kt+1=kt,停止運(yùn)算；

Step3.當(dāng)k′=k：|I|時(shí)，求出LCk′(d)；判斷LCk′(d)與LC1(d) 的關(guān)系，若LCk′(d)≠LC1(d),則kt+1=kt-1,停止運(yùn)算，若LCk′(d)=LC1(d)，則轉(zhuǎn)Step 4.

Step4.若k′+1>I,則kt+1=kt,停止運(yùn)算；若k′+1≤I,則k′=k′+1,并轉(zhuǎn)回Step 3.

5 實(shí)驗(yàn)分析

這部分通過(guò)在6個(gè)UCI數(shù)據(jù)集來(lái)比較靜態(tài)和動(dòng)態(tài)算法的計(jì)算性能.6個(gè)數(shù)據(jù)集的相關(guān)信息見(jiàn)表2.

表2 數(shù)據(jù)集描述Table 2 Data set description

在這個(gè)實(shí)驗(yàn)中，比較了隨著數(shù)據(jù)規(guī)模增大，靜態(tài)和動(dòng)態(tài)算法的執(zhí)行時(shí)間.所有的算法運(yùn)行在個(gè)人電腦，配置Windows 7，Intel(R)Core(TM)i7-3632QM CPU 2.20GHz，4GB內(nèi)存.編程語(yǔ)言matalb.

將預(yù)處理好的每個(gè)數(shù)據(jù)集分割為等大小的10份.第1份作為第1個(gè)數(shù)據(jù)集，第1和第2份的組合作為第2個(gè)數(shù)據(jù)集，第2個(gè)數(shù)據(jù)集和第3份數(shù)據(jù)的組合作為第3個(gè)數(shù)據(jù)集，以此類推，全部10份的數(shù)據(jù)組合作為第10個(gè)數(shù)據(jù)集.10個(gè)數(shù)據(jù)集的目標(biāo)概念都使用所對(duì)應(yīng)的數(shù)據(jù)集的決策類.這10個(gè)數(shù)據(jù)集可以用來(lái)觀察靜態(tài)和動(dòng)態(tài)算法執(zhí)行時(shí)間隨著數(shù)據(jù)集規(guī)模增大的變化情況.

在本小節(jié)中，不失一般性，對(duì)于所有粒度標(biāo)記下屬性值變化的可能都進(jìn)行了實(shí)驗(yàn)，即對(duì)k=1，2，3，4，5這五種情況都進(jìn)行了靜態(tài)和動(dòng)態(tài)的實(shí)驗(yàn).由于k=1，2，3，4，5時(shí)靜態(tài)算法的計(jì)算時(shí)間一致，故本文只羅列一次.為了公平，兩個(gè)算法沒(méi)有進(jìn)行其它的優(yōu)化.

圖1 靜態(tài)和動(dòng)態(tài)算法最優(yōu)粒度選擇的計(jì)算時(shí)間比較Fig.1 Comparison of computation time of optimal scale selection between static and dynamic algorithms

實(shí)驗(yàn)結(jié)果見(jiàn)圖1和表3.圖1展示了兩個(gè)算法計(jì)算時(shí)間隨數(shù)據(jù)集規(guī)模的變化情況.從圖1(x軸表示數(shù)據(jù)集占總數(shù)據(jù)的比例，y軸表示計(jì)算時(shí)間)不難發(fā)現(xiàn)，對(duì)于相同的大小的數(shù)據(jù)集，當(dāng)k≥2時(shí)靜態(tài)最優(yōu)粒度選擇算法時(shí)間消耗一致地低于靜態(tài)最優(yōu)粒度選擇算法.另外，在大多數(shù)數(shù)據(jù)中，計(jì)算時(shí)間的差值隨著數(shù)據(jù)的增加而增大.k=1時(shí)計(jì)算時(shí)間基本持平.表3展示了兩個(gè)算法在6個(gè)數(shù)據(jù)集各自產(chǎn)生的第10個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間.結(jié)果顯示局部多粒度下近似算法僅僅花費(fèi)了相應(yīng)全局算法的十分之一執(zhí)行時(shí)間.

表3 靜態(tài)和動(dòng)態(tài)算法計(jì)算時(shí)間比較(時(shí)間：秒)Table 3 Comparison of computation time between static and dynamic algorithms(time：s)

6 結(jié) 語(yǔ)

研究了某個(gè)粒度下屬性值變化時(shí)最優(yōu)粒度的選擇策略，并設(shè)計(jì)了相應(yīng)的靜態(tài)和動(dòng)態(tài)最優(yōu)粒度選擇算法并進(jìn)行了相關(guān)實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，新提出的方法可以對(duì)于屬性值變化的系統(tǒng)可以有效進(jìn)行選擇最優(yōu)粒度，且設(shè)計(jì)的動(dòng)態(tài)最優(yōu)粒度選擇算法在一定程度上提高了計(jì)算效率.