動態(tài)更新屬性值變化時的最優(yōu)粒度

劉鳳玲，林國平

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

1 引 言

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

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

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

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

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

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

2 基本知識

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

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

對任意的Ck?C，將論域U在Ck下的等價關系、等價類及等價劃分分別記為：

類似記：Rj5i0abt0b={(x，y)∈U×U|fj5i0abt0b(x)=fj5i0abt0b(x)}，[x]j5i0abt0b={y∈U|(x，y)∈Rj5i0abt0b}，U/Rj5i0abt0b={[x]j5i0abt0b|x∈U}={D1，D2，…，Dr}，r為決策類劃分的個數(shù)，即r=|U/Rj5i0abt0b|.

對于論域U中的一個子集X，其關于RCk的下近似和上近似分別為：

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

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

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

定義3[6].設dIS=(U，C∪j5i0abt0b)為多粒度決策系統(tǒng)，若RC1?Rd，則系統(tǒng)dIS是協(xié)調的.若進一步滿足RCk?Rd，則稱dISk=(U，Ck∪j5i0abt0b)協(xié)調.若dISk=(U，Ck∪j5i0abt0b)協(xié)調，則對任意的k′

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

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

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

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

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

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

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

1)當k>kt+1時，則kt+1=kt；

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

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

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

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

下面給出例子來分析及理解所提出的定理.

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

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

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

1)當k>kt+1時，則kt+1=kt；

2)當k≤kt+1時，

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

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

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

1)當k>kt+1時，則kt+1=kt；

2)當k≤kt+1時，

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

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

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

1)當k>kt+1時，則kt+1=kt；

2)當k≤kt+1時，

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

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

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

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

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

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

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

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

Step2.當k′=1：|I|時，則計算[x]Ck′(x∈U)；

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

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

Step5.若k′+1>I,則kk+1=k′,停止運算；若k′+1≤I,則k′=k′+1,并轉到Step 2.

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

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

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

Step1.判斷k與kt+1的大小關系，若k>kt+1，則轉Step2;若k≤kt+1，則轉Step3；

Step2.kt+1=kt,停止運算；

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

Step4.若k′+1>I,則kt+1=kt,停止運算；若k′+1≤I,則k′=k′+1,并轉回Step 3.

5 實驗分析

這部分通過在6個UCI數(shù)據(jù)集來比較靜態(tài)和動態(tài)算法的計算性能.6個數(shù)據(jù)集的相關信息見表2.

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

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

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

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

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

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

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

6 結 語

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