多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集最優(yōu)尺度選擇與約簡

楊 璇,黃 兵

(南京審計大學 信息工程學院,江蘇 南京 211815)

由波蘭科學家Pawlak所提出的經典粗糙集理論[1]是分析、處理各種類型數據的有效工具,因其自身所具有的不需任何有關數據的初步或附加信息的特性,故對處理模糊和不確定性問題的能力顯得尤其突出。自提出以來,粗糙集理論在集合近似和屬性約簡兩大方面不斷做出重大貢獻,在數據挖掘、圖像處理、模式識別等領域得到廣泛應用。

然而Pawlak經典粗糙集模型也存在不可避免的局限性。相對經典模型中的對象以符號取值,在實際生活中,所面臨的數據往往并不理想,數據的缺失、不確定現(xiàn)象比比皆是。此外,經典粗糙集中基于等價關系的上下近似要求也十分嚴格。在粗糙集理論不斷發(fā)展的過程中,眾學者針對存在的限制對經典粗糙集進行了不同類型的拓展,至今已得到模糊粗糙集[2]、直覺模糊粗糙集[3]、不完備信息系統(tǒng)粗糙集[4]、優(yōu)勢粗糙集[5]、決策粗糙集[6]等眾多拓展模型。其中,決策粗糙集是粗糙集理論與貝葉斯決策理論相結合得到的成果,旨在最大程度地降低分類風險以實現(xiàn)對目標概念的粗糙近似。Yao[6]針對決策粗糙集提出了一種新的規(guī)則歸納方法,通過設定決策閾值α、β來確定其容錯能力,并將分類決策設為由正域POS(α,β)、負域NEG(α,β)、邊界域BND(α,β)3個區(qū)域構成,進一步提高了決策粗糙集的實用價值。這吸引了廣大學者的關注,對其進行了大量改進與推廣。Liu等[7]提出了一種基于不完備信息系統(tǒng)的三支決策模型;Lin等[8]通過對論域進行模糊劃分,從多源信息系統(tǒng)中得到多個模糊粒度,提出了一個新的模糊多粒度決策粗糙集模型;劉丹等[9]在不完備信息系統(tǒng)中引入鄰域容差關系,從樂觀、悲觀、平均3個方面分別討論了相應的不完備鄰域多粒度決策粗糙集模型;Sun等[10]將概率粗糙集推廣到了模糊環(huán)境下,建立了模糊決策粗糙集模型,進一步擴大了決策粗糙集的適用范圍;Song等[11]基于Sun等給出的模糊決策粗糙集模型,采用啟發(fā)式算法進行特征選擇,進一步最小化決策代價;王鵬等[12]考慮到對噪聲數據的容忍性問題,在傳統(tǒng)模糊相似關系中引入一個限定閾值,提出一種改進的模糊粗糙集模型;Yao等[13]探討了基于貝葉斯決策過程的近似概念的定義;王莉等[14]研究了一種新的模糊決策粗糙集模型及相應的屬性約簡算法;方宇等[15]在定性和定量的標準下提出了一種基于三支決策的廣義代價敏感近似屬性約簡算法;王宇等[16]討論了決策粗糙集屬性約簡的一種局部視角方法。

在現(xiàn)實生活中,同一屬性往往會具有不同層次,并且同一屬性在不同層次上取值不同。例如學生成績可分為90～100分、80～90分、70～80分、60～70分、60分以下這5種情況,也可分別用A、B、C、D來表示優(yōu)、良、中、差,或者進一步簡化為及格、不及格兩種情況。考慮到屬性的這一特性,研究學者提出了多尺度的概念并進行了延伸,將多尺度泛化到了優(yōu)勢直覺粗糙集[17]、決策粗糙集[18]、對偶概率粗糙集[19]、鄰域粗糙集[20,21]、變精度粗糙集[22,23]、集值粗糙集[24]等環(huán)境下進行討論。但迄今為止,將模糊決策粗糙集模型引入到多尺度環(huán)境下的研究仍然較為少見。

為此,本文針對多尺度決策系統(tǒng),建立多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集模型,給出相應的最優(yōu)尺度選擇及約簡方法,并提出一個較為簡便的最優(yōu)尺度約簡算法。最后采用UCI數據集進行實例驗證,證明本文所提模型及算法的可行性和有效性。本文所提模型及算法進一步拓展了基于模糊相似關系的決策粗糙集的研究范圍,擴大和提高了基于模糊相似關系的決策粗糙集在實際應用中的廣泛性與有效性,為基于模糊相似關系的決策粗糙集在多尺度決策系統(tǒng)下的知識獲取提供了新思路。

1 預備知識

1.1 基于模糊相似關系的決策粗糙集

1.2 多尺度決策系統(tǒng)

由定義可知,一個多尺度信息表是由多個單尺度信息表組成的,每一個單尺度信息表的屬性之間都存在一定的二元關系。因此,在進行屬性約簡和規(guī)則提取的過程中,往往會將一個多尺度信息表進行分解再加以處理。

定義4[17]設多尺度信息表S=(U,A),其中,aj∈A(j=1,2,…,m)具有Ij個尺度,被限制在其相應尺度的屬性a1,a2,…,aj(j=1,2,…,m)構成一個單尺度信息表SK,其中,K=(l1,l2,…,lm)為一索引集合,稱為S中SK的尺度組合。S中所有尺度組合的族稱為S的尺度集合,記為L={(l1,l2,…,lm)|1≤lj≤Ij,j=1,2,…,m}。

定義5[17]設D=(U,C∪j5i0abt0b)為一多尺度決策表,其中,(U,C)為一多尺度信息表且d?C,d:U→Vd稱為決策屬性。

2 多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集

傳統(tǒng)的基于模糊相似關系的決策粗糙集是基于單尺度決策表進行討論的,單尺度決策表中的每個屬性取值一定。但現(xiàn)實中,同一對象的同一屬性可能具有多個尺度層次,且在每個尺度層次上的取值可能不同。下面給出多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集模型的定義。

定理1基于定義6中的定義給出下列性質:

3 最優(yōu)尺度選擇及約簡

3.1 最優(yōu)尺度選擇

最優(yōu)尺度選擇是從多尺度決策系統(tǒng)中進行知識發(fā)現(xiàn)和規(guī)則提取的一個重要環(huán)節(jié),能夠跳過很多不必要的數據分析工作。下面,基于多尺度決策系統(tǒng),討論多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集的最優(yōu)尺度選擇問題,并給出相應算法。

定義7[27]設K1=(l11,l12,…,l1m),K2=(l21,l22,…,l2m)∈L。

K1≤K2?l1j=l2j,1≤j≤m

K1=K2?l1j=l2j,1≤j≤m

K1

K1∨K2=(max(l11,l21);max(l12,l22);…;

max(l1m,l2m))

K1∧K2=(min(l11,l21);min(l12,l22);…;

min(l1m,l2m))

式中:≤表示偏序關系,∨表示取最大值,∧表示取最小值。

下面給出多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集最優(yōu)尺度選擇方法的相關定義。

下面給出多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集下近似最優(yōu)尺度選擇算法。

算法1多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集下近似最優(yōu)尺度選擇算法

輸入:多尺度決策表S=(U,C∪j5i0abt0b),C={c1,c2,…,cm},Ij(1≤j≤m),Di?U(1≤i≤m),0<α≤1,K0=(l1=1,l2=1,…,lm=1);

輸出:S關于Di的下近似最優(yōu)尺度Op;

1: 設Op=L={(l1,l2,…,lm)|1≤lj≤Ij,1≤j≤m};

4: 得到S關于Di的下近似最優(yōu)尺度Op。

同理可得多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集上近似最優(yōu)尺度選擇算法。

3.2 最優(yōu)尺度約簡

在對最優(yōu)尺度進行選定后,考慮多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集的最優(yōu)尺度約簡問題。下面給出相關定義。

定義9設多尺度決策表S=(U,C∪j5i0abt0b),U/d={D1,D2,…,Dm}構成對論域U的精確劃分,L是S的尺度集合,K=(l1,l2,…,lm)∈L;K?=(/;…;/;li;/;…;/;lj;/;…;/)是K的子尺度;如果K?是K的子尺度且K?≠K,則稱K?是K的一個真子尺度。其中,“/”代表相對應的條件屬性及由其所導出的模糊相似關系被刪除。

定義10設多尺度決策表S=(U,C∪j5i0abt0b),K=(l1,l2,…,lm)∈L,L為S的尺度集合,K??K,Di?U(1≤i≤m),0≤β<α≤1。

考慮到按照上述方法進行最優(yōu)尺度選擇及約簡的時間、空間耗費過大,下面給出獲得一個最優(yōu)尺度約簡的簡便算法。

算法2多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集下近似最優(yōu)尺度約簡算法

輸入:多尺度決策表S=(U,C∪j5i0abt0b),C={c1,c2,…,cm},Ij(1≤j≤m),Di?U(1≤i≤m),0<α≤1,K0=(l1=1,l2=1,…,lm=1);

輸出:S關于Di的下近似最優(yōu)尺度約簡Kr;

1: 設R(C)=C,Kr=(l1=1,l2=1,…,lm=1)=K0;

6: 得到S關于Di的下近似最優(yōu)尺度約簡Kr。

同理可得多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集上近似最優(yōu)尺度約簡算法。

例1給出一多尺度決策表如表1所示。

表1 一個多尺度決策表

U={x1,x2,x3,x4,x5,x6}={{x1,x2,x3,x5,x6},{x4}},R(C)=C={c1,c2,c3},D1={x1,x2,x5},D2={x3,x4,x6},Kr=(l1=1,l2=1,l3=1)=K0;

得到多尺度決策表關于D1的下近似最優(yōu)尺度約簡Kr=(/,/,1)。

得到多尺度決策表關于D2的下近似最優(yōu)尺度約簡Kr=(3,1,/)。

4 實驗分析

對本文所提出的多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集模型和其相應的最優(yōu)尺度選擇及約簡算法,本節(jié)將給出數據實驗分析以證明其可行性與有效性。其中,進行實驗的硬件環(huán)境配置為主頻1.80 GHz的i7-10510U CPU,8 GB DDR4內存,算法運行的軟件環(huán)境為MATLAB R2016a。實驗采用UCI數據庫中的5組標準數據集:Wine、Wpdc、Glass、Sonar、Mess來進行仿真實驗。5組數據集均為包含一定噪聲數據的實際應用數據集。

表2 實驗數據集

實驗將本文算法和文獻[11]中對比算法所得到的特征子集結果在支持向量機分類器下進行分類性能評估,其結果通過分類精度的形式來表示,具體結果見表3。顯然,兩類特征選擇算法所得分類精度均高于原始數據集的分類精度。本文特征選擇算法分類精度得到了一定程度上的提高,約簡后條件屬性個數明顯減少,這說明原始數據集中存在一定的冗余屬性,這些冗余屬性在一定程度上降低了數據的分類精度。通過本文的模型及算法,可以獲得較好的特征選擇結果,提高數據集分類能力。由此證明,本文所提出的模型及算法是有效的。

表3 實驗結果

5 結束語

本文針對多尺度決策系統(tǒng)中每個屬性可能具有不同尺度層次的特性,結合基于模糊相似關系的決策粗糙集,建立了多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集模型,提出了下、上近似最優(yōu)尺度選擇及約簡的判定定理,給出了相應的最優(yōu)尺度選擇及約簡方法?？紤]到算法時間、空間復雜性問題,討論了獲得一個最優(yōu)尺度約簡的簡便算法。最后利用5組UCI標準數據集在MATLAB R2016a環(huán)境下進行仿真實驗,驗證了本文所提模型及算法的有效性。在后續(xù)工作中,將進一步探索所提出的多尺度決策系統(tǒng)中基于模糊相似關系的決策粗糙集在審計風險判斷中的應用。