特征函數(shù)描述下的多粒度覆蓋粗糙集及其不確定性度量

劉財(cái)輝，凌 敏，錢(qián) 進(jìn)

(1.贛南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 贛州 341000；2.華東交通大學(xué) 軟件學(xué)院，江西 南昌 330013)

0 引 言

粗糙集理論是由Pawlak[1]于1982年提出的一種主要用于處理不確定知識(shí)的工具.近年來(lái),對(duì)粗糙集理論的研究取得了大量的研究成果[2-6].為使粗糙集更好地解決實(shí)際問(wèn)題，Qian等人[7-8]在Pawlak粗糙集的基礎(chǔ)上提出了樂(lè)觀多粒度粗糙集和悲觀多粒度粗糙集；Yang[9]在Qian的基礎(chǔ)上進(jìn)一步提出了一種基于優(yōu)勢(shì)關(guān)系的樂(lè)觀多粒度粗糙集和悲觀多粒度粗糙集.隨著研究的深入，人們發(fā)現(xiàn)，知識(shí)與知識(shí)之間存在交叉的情況，因此覆蓋粗糙集的概念應(yīng)運(yùn)而生.Zakowski[10]首先提出了覆蓋廣義粗糙集，將Pawlak粗糙集的全域劃分推廣為覆蓋全域，并在此基礎(chǔ)上建立了一對(duì)粗糙逼近運(yùn)算；Tsang等[11]提出了一種基于最小描述的新型覆蓋粗糙集模型；Zhu等[12]通過(guò)加強(qiáng)上、下近似之間的依賴(lài)，提出了一種新型的覆蓋粗糙集模型.此外,一些其他學(xué)者也從不同角度對(duì)覆蓋粗糙集做了大量的研究[13-17].

不確定性度量作為研究粗糙集的一個(gè)重要問(wèn)題，Pawlak等人首先給出了粗糙精度、粗糙度的度量方法，然而事實(shí)表明這些方法不能準(zhǔn)確度量現(xiàn)有信息粒度的劃分.Beaubouef等人[18]用香農(nóng)熵的概念來(lái)研究粗糙關(guān)系的不確定性度量；苗奪謙等[19-20]研究了粒計(jì)算與不確定性之間的關(guān)系；Yao[21]揭示了信息粒度與概念逼近的關(guān)系，用信息粒度來(lái)衡量不同粒度結(jié)構(gòu)下的不確定性信息；李金海等[22]在多粒度形式背景下，將信息熵對(duì)信息的不確定性研究拓展至最優(yōu)粒度選擇，為多粒度形式背景下的不確定性研究提供了新角度；王國(guó)胤等[23]展開(kāi)了信息論在粗糙集中的研究，將信息熵應(yīng)用到粗糙集中的不確定性分析，并給出了條件熵下的數(shù)據(jù)約簡(jiǎn)新方法；Leung等[24]提出了在不完備信息系統(tǒng)下的最大一致塊方法，可得到更精確的近似集；梁吉業(yè)等[25]研究了不同二元關(guān)系下信息系統(tǒng)信息粒的表示，建立了信息粒度與熵的互補(bǔ)關(guān)系，這統(tǒng)一了完備信息系統(tǒng)和不完備信息系統(tǒng)中的不確定性度量；Qian等[26-27]人定義組合熵與知識(shí)粒度的概念，以研究信息系統(tǒng)不確定性.隨著粗糙集模型的擴(kuò)展,許多學(xué)者對(duì)擴(kuò)展模型中不確定性問(wèn)題做了研究[28-31].

多粒度覆蓋粗糙集模型作為多粒度粗糙集的推廣，與實(shí)際應(yīng)用更加貼近.為更清晰地對(duì)知識(shí)分類(lèi)和推理，研究覆蓋粗糙集模型中的不確定性問(wèn)題是一件很有價(jià)值的工作.因此本文主要對(duì)多粒度覆蓋粗糙集的不確定性進(jìn)行了深入研究，具體內(nèi)容如下:第1節(jié)給出了覆蓋粗糙集和多粒度粗糙集的相關(guān)定義；第2節(jié)通過(guò)定義基于最小描述交的特征函數(shù)，定義了一類(lèi)新的多粒度覆蓋粗糙集模型，并討論了不同類(lèi)型的上下近似算子及性質(zhì)；第3節(jié)從上、下近似和邊界域兩個(gè)角度定義了不確定性度量；第4節(jié)在4個(gè)UCI數(shù)據(jù)集上對(duì)三個(gè)模型進(jìn)行了實(shí)驗(yàn)分析，并觀察不確定性度量的變化情況，驗(yàn)證了本文所提方法的正確性和有效性；第5節(jié)進(jìn)行了總結(jié).

1 基本概念

1.1 覆蓋粗糙集

定義1[32]設(shè)U是非空有限論域，C={C1,C2,…,Cn}是U的一個(gè)子集族，對(duì)于∪C=U，?Ci≠?，稱(chēng)C是U上的一個(gè)覆蓋，〈U,C〉為一個(gè)覆蓋近似空間.

定義2[32]設(shè)〈U,C〉為覆蓋近似空間，對(duì)?x∈U，x關(guān)于U的最小描述Md(x)定義為：

Md(x)={K∈C|x∈K∧(?S∈C∧x∈S∧S?K?S=K)}.

1.2 多粒度粗糙集

定義4[33]給定信息系統(tǒng)I=(U,AT,V,F),Ai?AT,i=1,2,…,m(m≤2|AT|)，對(duì)?X?U,x關(guān)于X的支持特征函數(shù)定義如下：

2 基于支持特征函數(shù)的多粒度覆蓋粗糙集

在覆蓋粗糙集和多粒度粗糙集的基礎(chǔ)上，為了描述多粒度覆蓋粗糙集的基本特征及反映各個(gè)元素從屬于覆蓋集U的程度,我們給出了基于最小描述交的支持特征函數(shù)的概念，提出了一類(lèi)基于支持特征函數(shù)下的多粒度覆蓋粗糙集模型：廣義多粒度覆蓋粗糙集、樂(lè)觀多粒度覆蓋粗糙集和悲觀多粒度粗糙集.為避免多粒度覆蓋粗糙集在樂(lè)觀條件下近似的定義過(guò)于寬松，知識(shí)粒度過(guò)于飽和；在悲觀情況下近似的定義過(guò)于嚴(yán)格，知識(shí)粒度過(guò)于空缺，定義了一個(gè)參數(shù)β，以刻畫(huà)最小描述交Md(x)與X的包含程度.

定義7設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，C={C1,C2,…,Cn}，對(duì)?x∈U，支持特征函數(shù)定義如下：

2.1 廣義多粒度覆蓋粗糙集(GMC)

定義8設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，C={C1,C2,…,Cn}，設(shè)定一個(gè)閾值β∈(0,1),對(duì)?x∈U，廣義多粒度覆蓋粗糙集的上下近似定義為：

證明由于篇幅所限，證明略.

定理2設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，對(duì)?X?U，當(dāng)γ<β時(shí)滿(mǎn)足:

證明由于篇幅所限，證明略.

2.2 樂(lè)觀多粒度覆蓋粗糙集(OMC)

定義9設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，C={C1,C2,…,Cn}，設(shè)定一個(gè)閾值β∈(0,1),對(duì)?x∈U，樂(lè)觀多粒度覆蓋粗糙集的上下近似定義為：

2.3 悲觀多粒度覆蓋粗糙集(PMC)

定義10設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，C={C1,C2,…,Cn}，設(shè)定一個(gè)閾值β∈(0,1),對(duì)?x∈U，悲觀多粒度覆蓋粗糙集的上下近似定義為：

以上兩個(gè)模型的性質(zhì)類(lèi)似于定理1.

定理3設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，C={C1,C2,…,Cn}，設(shè)定一個(gè)閾值β∈(0,1)，對(duì)?x∈U,有下列公式成立：

定理3可由定義8、定義9和定理2證明.

3 多粒度覆蓋粗糙集的不確定性度量

本節(jié)在基于支持特征函數(shù)的多粒度覆蓋粗糙集模型的基礎(chǔ)上，提出了幾種不確定性度量方法.從上下近似和邊界域的角度出發(fā)，分別定義了兩種類(lèi)型的近似精度、粗糙度和近似質(zhì)量，并研究了相關(guān)性質(zhì).

定義11設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，對(duì)?X?U，X關(guān)于覆蓋集C的第一類(lèi)廣義多粒度覆蓋粗糙集的近似精度和粗糙度可以定義為：

同理，X關(guān)于覆蓋集C的第一類(lèi)樂(lè)觀多粒度覆蓋粗糙集及悲觀多粒度覆蓋粗糙集的近似精度和粗糙度分別定義為：

定義12設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，對(duì)?X?U，X關(guān)于覆蓋集C在三種模型下的第二類(lèi)近似精度和粗糙度可以定義為：

定義13設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，對(duì)?X?U，X關(guān)于覆蓋集C在三種模型下的近似質(zhì)量可以定義為：

定理4設(shè)〈U,C〉為覆蓋近似空間，C為U上的一個(gè)覆蓋，對(duì)?X?U，不確定性度量還存在如下關(guān)系：

此定理可由定義2.2～2.4和定理2.2證明.

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

為進(jìn)一步研究和驗(yàn)證廣義多粒度覆蓋粗糙集(GMC)、樂(lè)觀多粒度覆蓋粗糙集(OMC)及悲觀多粒度覆蓋粗糙集(PMC)模型下三種不確定性度量的關(guān)系，我們從UCI數(shù)據(jù)庫(kù)中獲取了Iris、German、Stalog、AnuranCalls(MFCCS)4個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)比較分析，數(shù)據(jù)集分別用U1,U2,U3,U4表示,具體信息如后面的表1所示.該實(shí)驗(yàn)是在實(shí)驗(yàn)環(huán)境為64位、Intel(R)Core(TM)i7-8700CPU@3.20GHz的臺(tái)式電腦下完成的，實(shí)驗(yàn)軟件為MATLAB2019a，部分實(shí)驗(yàn)算法如下：

Algorithm1:Uncertaintymeasurementofgeneralizedmulti-granularitycoveringroughsetsINPUT:d,β,U={U1,U2,…,Un},C={C1,C2,…,Cn}OUTPUT:αβGMC(X)I,ρβGMC(X)I,αβGMC(X)II,ρβGMC(X)II,ωβGMC(X)1. fori=1:ndo2. forj=1:mdoP(i,:)=(P(i,:)-min(P(i,:)))/(max(P(i,:))-min(P(i,:)));3. end4. end5. fori=1:ndo//%CalculatetheEuclideandistancebetweeneachobject6. forj=1:mdoDis(x,y)=sqrt(∑(xi122xi1?xi2+xi22))7. end8. end9. fori=1:mdo//%Calculatethetolerancerelationshipofeachobject10. forj=1:mdo11. ifDis(x,y)≤dthenCi(xi)=Ci(xi)∪{xj}.12. end13. end14. end15. fori=1:mdoΔCCiX(x)=0,ΔCCi～X(x)=016. forj=1:mdo17. if∩Md(x)?XthenΔCCiX(x)=ΔCCiX(x)+118. elseΔCCiX(x)=ΔCCiX(x)19. end20. if∩Md(x)?～XthenΔCCi～X(x)=ΔCCi～X(x)+121. elseΔCCi～X(x)=ΔCCi～X(x)22. end23. end24. endGMC∑mi=1Ciβ(X)=GMC∑mi=1Ciβ(X)∪xi25. fori=1:ndo26. ifΔCCiX(x)m≥βthenGMC∑mi=1Ciβ(X)=GMC∑mi=1Ciβ(X)∪xi27. end28. if1-ΔCCiX(x)m≥1-βthenGMC∑mi=1Ciβ(X)=GMC∑mi=1Ciβ(X)∪xi29. end30. endreturnαβ(X)I,ρβGMC(X)I,αβGMC(X)II,ρβGMC(X)II,ωβGMC(X)

表1 數(shù)據(jù)集信息Tab.1 Datasets information

對(duì)算法1的時(shí)間復(fù)雜度進(jìn)行分析：步驟1至8，對(duì)數(shù)據(jù)進(jìn)行歸一化處理，并計(jì)算對(duì)象之間的歐式距離，時(shí)間復(fù)雜度為O(|U|2×|Ci|×n) (n為論域的個(gè)數(shù))；步驟9至14、步驟15至23，分別計(jì)算覆蓋對(duì)象之間的關(guān)系、最小描述交對(duì)給定概念及其補(bǔ)集的支持特征函數(shù)值，時(shí)間復(fù)雜度均為O(|U|2×m)；步驟24至30，計(jì)算覆蓋空間下的上、下近似值，時(shí)間復(fù)雜度為O(|U|).

主要實(shí)驗(yàn)步驟如下：

1) 將U1,U2,U3,U4,數(shù)據(jù)集按90%等比例隨機(jī)取樣,并歸一化處理,使所取樣本取值置于[0,1]區(qū)間.

2) 計(jì)算每個(gè)數(shù)據(jù)集所取樣本歸一化后歐氏距離,并設(shè)定相應(yīng)的距離閾值為:d1=0.5,d2=0.5,d3=0.4,d4=0.08,通過(guò)調(diào)參設(shè)定信息水平參數(shù)閾值β=0.3.

3) 計(jì)算三種多粒度覆蓋粗糙集在閾值條件下對(duì)應(yīng)的上下近似及支持特征函數(shù)值，由此得到廣義多粒度覆蓋粗糙集(GMC)、樂(lè)觀多粒度覆蓋粗糙集(OMC)及悲觀多粒度覆蓋粗糙集(PMC)在U1,U2,U3,U4下的近似質(zhì)量ω、兩種類(lèi)型的近似精度αI,II和粗糙度βI,II.

4) 實(shí)驗(yàn)進(jìn)行5次隨機(jī)采樣，重復(fù)上述3個(gè)步驟，得到5次實(shí)驗(yàn)結(jié)果，如圖1～圖3所示.

圖1 兩種類(lèi)型的近似精度Fig.1 Two types of approximation accuracy

圖2 兩種類(lèi)型的粗糙度Fig.2 Two types of roughness

圖3 近似質(zhì)量Fig.3 Approximate quality

為更直觀、簡(jiǎn)潔地看到三個(gè)模型在不同度量方法下的差異，可從實(shí)驗(yàn)結(jié)果圖1～圖3得出以下結(jié)論：

圖1展示了廣義,樂(lè)觀和悲觀三種多粒度覆蓋粗糙集在四個(gè)數(shù)據(jù)集下兩種類(lèi)型近似精度的關(guān)系，發(fā)現(xiàn)兩種類(lèi)型在樂(lè)觀條件下的近似精度均大于廣義條件下的近似精度且大于悲觀條件下的近似精度;圖2展示了三種模型在四個(gè)數(shù)據(jù)集下的兩種類(lèi)型粗糙度的關(guān)系,發(fā)現(xiàn)兩種類(lèi)型在悲觀條件下的粗糙度均大于廣義條件下的粗糙度且大于樂(lè)觀條件下的粗糙度；圖3展示了三種模型在四個(gè)數(shù)據(jù)集下近似質(zhì)量的關(guān)系,發(fā)現(xiàn)樂(lè)觀條件下的近似質(zhì)量大于廣義條件下的近似質(zhì)量且大于悲觀條件下的近似質(zhì)量.可見(jiàn)該實(shí)驗(yàn)結(jié)果滿(mǎn)足定理4.

在對(duì)象選擇時(shí)，樂(lè)觀多粒度覆蓋粗糙集過(guò)于寬松，無(wú)法準(zhǔn)確地描述概念.主要原因是樂(lè)觀多粒度覆蓋粗糙集在選擇對(duì)象時(shí)具有積極的描述，對(duì)象只需在至少一個(gè)域下支持該概念即可.容易造成在下近似中可能會(huì)增加許多無(wú)用的描述：在上近似中容易丟失有用的描述，這將使概念的描述不準(zhǔn)確.相反，悲觀多粒度覆蓋粗糙集對(duì)域的概念要求則過(guò)于嚴(yán)格.

介于悲觀、樂(lè)觀多粒度覆蓋粗糙集模型在實(shí)際應(yīng)用中均存在局限性，本文提出了一種新的多粒度粗糙集模型，它通過(guò)調(diào)節(jié)信息參數(shù)β∈(0,1)來(lái)控制對(duì)象的選擇，閾值用于控制對(duì)象在大多數(shù)域中被正面描述，低于該閾值的對(duì)象則被刪除.

從圖1～圖3，我們可以看到不同模型在不同數(shù)據(jù)集的結(jié)果是不一致的，不同度量方法得到的度量結(jié)果也并不完全一致.因此在實(shí)際應(yīng)用中，不同領(lǐng)域應(yīng)根據(jù)自己的需求選擇模型，還應(yīng)根據(jù)不同的方案選擇合理的度量方法.

5 結(jié) 論

本文從多粒度的角度，結(jié)合覆蓋粗糙集形成多粒度覆蓋粗糙集.在支持特征函數(shù)的背景下加入信息參數(shù)，先后提出了三種多粒度覆蓋粗糙集的擴(kuò)展模型：廣義多粒度覆蓋粗糙集、樂(lè)觀多粒度覆蓋粗糙集和悲觀多粒度覆蓋粗糙集，并討論了它們的相關(guān)定理和性質(zhì).為更深入研究多粒度覆蓋粗糙集，我們討論了在不同情況適用于三種模型的不確定性度量方法.最后我們?cè)O(shè)計(jì)了一個(gè)計(jì)算不確定性度量的算法，并用四個(gè)數(shù)據(jù)集對(duì)該算法進(jìn)行了驗(yàn)證.實(shí)驗(yàn)表明，廣義多粒度覆蓋粗糙集模型具有更廣泛的適用性.