基于差別矩陣的區(qū)間值決策系統(tǒng)β分布約簡

李磊濤，張 楠*，童向榮，岳曉冬

（1.數(shù)據(jù)科學與智能技術山東省高校重點實驗室（煙臺大學），山東煙臺 264005；2.煙臺大學計算機與控制工程學院，山東煙臺 264005；3.上海大學計算機工程與科學學院，上海 200444）

0 引言

粗糙集理論［1-5］是一個重要的數(shù)據(jù)處理工具，可以用來處理數(shù)據(jù)中的不確定性問題，最先由Pawlak［1］提出，已應用于許多領域。屬性約簡［1-7］是粗糙集理論的核心研究內(nèi)容之一。當前，消除不必要的屬性、縮小數(shù)據(jù)規(guī)模從而加速數(shù)據(jù)的處理顯得尤為重要，而屬性約簡的目的就是盡可能消除數(shù)據(jù)中不必要的屬性，得到?jīng)Q策系統(tǒng)中某種分類特征不變的最小屬性子集。通過屬性約簡既可以縮小數(shù)據(jù)規(guī)模又不會破壞知識的原始信息，恰好滿足了當前的需求。目前已經(jīng)有許多學者對知識約簡做了大量工作。1992年，Skowron 等［8］提出了一種基于差別矩陣的正域約簡方法，隨后國內(nèi)外許多學者對此做了大量的擴展工作；1999年，苗奪謙等［9］提出了在決策信息表中屬性重要性度量的概念；2003 年，張文修等［10］提出了最大分布屬性約簡以及分配屬性約簡的算法；2007 年，徐偉華等［11］在不協(xié)調(diào)信息系統(tǒng)中提出了基于優(yōu)勢關系的經(jīng)典分布和最大分布約簡的概念，并建立了相應的差別矩陣；2017年，Su等［12］提出了一種基于組合子集的編碼方法，并給出了一種基于粗糙集理論和魚群算法的最小化屬性約簡的搜索策略；2018年，Liu 等［13］在決策系統(tǒng)中提出了特定類β分布保持約簡的概念；2020年，Abdolrazzagh-Nezhad 等［14］通過構造一個新的成本函數(shù)并利用改進的文化算法來解決多目標屬性約簡問題，最后提出了無監(jiān)督屬性約簡的新方法。

以上傳統(tǒng)的粗糙集理論都是處理單一值數(shù)據(jù)，并不適合于處理區(qū)間值數(shù)據(jù)。實際應用中存在許多區(qū)間值形式的數(shù)據(jù)，它們通過不精確的估計數(shù)值范圍來描述對象，因此在粗糙集領域中，區(qū)間值信息系統(tǒng)受到廣泛研究。2008 年，Leung等［15］考慮到兩個區(qū)間值數(shù)據(jù)的相似度問題提出了誤分率的概念，揭示了在兩個區(qū)間值數(shù)據(jù)的交集部分被錯誤分類為另一個區(qū)間值的程度；2009 年，張楠等［2］提出了極大相容塊的概念，去除了相容類中不滿足傳遞性的對象，提高了分類精度，并在區(qū)間值信息系統(tǒng)中構造了對于任意對象的新的粗糙近似；2011 年，Dai 等［16］基于相容關系提出了擴展條件熵和粗糙決策熵以及區(qū)間近似粗糙度的概念，實驗結果表明粗糙決策熵的度量要優(yōu)于區(qū)間近似粗糙度；2014年，徐菲菲等［7］提出了基于屬性的依賴度以及互信息的區(qū)間值啟發(fā)式屬性約簡，選擇屬性依賴度高、互信息低的屬性加入約簡集合；2015 年，Yang等［17］提出了一種基于α參數(shù)優(yōu)勢的粗糙集方法處理區(qū)間值信息系統(tǒng)問題，并為了簡化決策規(guī)則而引入了上下近似約簡；2016 年，張楠等［18］在區(qū)間值決策系統(tǒng)中基于正域的確定性以及邊界域的不確定性提出了確定性規(guī)則和不確定性規(guī)則保持約簡；2018 年，尹繼亮等［19］基于區(qū)間值決策系統(tǒng)提出了最大分布約簡的概念，只將最大的分布值進行處理，實驗結果表明該算法的效率高于經(jīng)典的分布約簡；2020 年，Liu 等［20］在區(qū)間值信息系統(tǒng)中提出了一種無監(jiān)督屬性約簡方法，利用模糊類構造α-近似等價關系以及近似等價類，從而提出了新的屬性重要性的度量方式?；谝陨涎芯靠芍墨I［7］提出了依賴度以及互信息的約簡目標，文獻［16-20］則提出了決策熵、條件熵、確定性、不確定性以及最大分布的約簡目標。

目前，未有對區(qū)間值決策系統(tǒng)下β分布約簡的討論，最大分布約簡雖然提高了效率，但只考慮了最大的分布，所以會損失一些信息，因此本文提出了在區(qū)間值決策系統(tǒng)下β分布約簡的概念，可以有效處理區(qū)間類型的數(shù)據(jù)。該方法通過放松構造差別矩陣的條件減少差別矩陣的元素，可以保留分布信息并減小約簡長度。

1 基本知識

1.1 區(qū)間值決策系統(tǒng)

在應用中存在大量的區(qū)間值數(shù)據(jù)，它規(guī)定了某個屬性的取值范圍，接下來給出相關概念。

1.2 相似度

相似度表示兩個區(qū)間值數(shù)據(jù)之間相似的程度，通過相似度可以求出區(qū)間值系統(tǒng)的相容關系及相容類，接下來給出相關定義。

對于區(qū)間值決策系統(tǒng)IdS=(U，C∪D，V，f)，U為包含n個對象的論域，則在相似度閾值θ下相容類集合定義如下：

在單值決策系統(tǒng)中應用經(jīng)典粗糙集理論時，對象之間的等價關系具有自反性、對稱性、傳遞性，由此獲得的等價類實現(xiàn)了對于論域U的劃分，而區(qū)間值決策系統(tǒng)中的相容類實現(xiàn)了對于論域U的覆蓋。

例1 對于給定的區(qū)間值決策系統(tǒng)，如表1所示，論域U={x1，x2，…，x6}為對象的集合，C={a1，a2，a3，a4}為條件屬性的集合，決策屬性D=j5i0abt0b。

表1 區(qū)間值決策系統(tǒng)Tab.1 Interval-valued decision system

1.3 區(qū)間值決策系統(tǒng)的經(jīng)典分布約簡

文獻［22］中提出了區(qū)間值決策系統(tǒng)經(jīng)典分布約簡的思想，下面給出其相關定義和經(jīng)典分布約簡算法的描述。

定義6假設IdS=(U，C∪D，V，f)是區(qū)間值決策系統(tǒng)，IdS的差別矩陣為n×n的矩陣，記為M=(cij)n×n，其中cij滿足：

其中：cij為差別矩陣的第i行、第j列元素，i，j=1，2，…，|U|。［22］

定義7設IdS=(U，C∪D，V，f)是區(qū)間值決策系統(tǒng)，ak表示條件屬性的第k個屬性，cij為差別矩陣的第i行、第j列元素，該區(qū)間值決策系統(tǒng)對應的θ-相容類分布約簡的差別函數(shù)是由與條件屬性對應的變元構成，該函數(shù)如下：

其中：∨cij=∨ak，ak∈cij表示所有屬性對應變元的析取項。通過吸收律和分配律將合取范式Fθ(IdS)轉化為析取范式Hθ(IdS)。［22］

定理1設IdS=(U，C∪D，V，f)是區(qū)間值決策系統(tǒng)，Hθ(IdS)是分布約簡的差別函數(shù)Fθ(IdS)的轉化，若R是一個分布約簡結果，當且僅當R是Hθ(IdS)的一個包含項。［22］

基于差別矩陣的分布約簡算法（Distribution Reduction Algorithm based on Discernibility Matrix，DRADM）描述如下。

2 區(qū)間值決策系統(tǒng)的β分布約簡

本章在區(qū)間值決策系統(tǒng)中應用β概率分布，提出了基于差別矩陣的區(qū)間值決策系統(tǒng)β分布約簡算法。

在步驟6通過差別函數(shù)轉化求得β分布約簡部分：首先計算差別函數(shù)的項數(shù)，最差情況下整個下三角部分均需計算，因此項數(shù)為|U|22；然后計算每兩項的轉化時間，假設最壞情況下每一項均有最多|C|個元素，因此時間復雜度為O(|C|2)，所以總的時間復雜度為

3 實驗與結果分析

在本章將基于差別矩陣的區(qū)間值決策系統(tǒng)β分布約簡算法通過UCI（University of California-Irvine）數(shù)據(jù)集進行實驗驗證，具體實驗包括：約簡結果的對比和算法效率差異的對比。

實驗環(huán)境為：個人筆記本電腦，Inter Core i5-8300H CPU，主頻為2.30 GHz，內(nèi)存為8 GB，操作系統(tǒng)為64 位Windows 10家庭版，程序運行環(huán)境為Python 3.7。

實驗選取了14 組UCI 數(shù)據(jù)集，數(shù)據(jù)集的相關信息如表2所示（表中|U|為對象數(shù)目，|C|為條件屬性數(shù)目）。對于非數(shù)值的類別數(shù)據(jù)用0，1，2，…數(shù)值數(shù)據(jù)代替，對于缺失值則用該缺失值所在列的最頻繁項的值代替，由于這些數(shù)據(jù)集每一項的值都是單值，因此要把這些數(shù)據(jù)集轉化為區(qū)間值數(shù)據(jù)集，本文采用文獻［23］中介紹的轉化方法。

表2 UCI數(shù)據(jù)集Tab.2 UCI datasets

3.1 約簡結果對比

本節(jié)在表2 所示的14 組UCI 數(shù)據(jù)集上將本文提出的β-DRIVS 與DRADM［22］以及最大分布約簡算法（Maximum Distribution Reduction Algorithm based on Discernibility Matrix，MDRADM）［19］的約簡結果和對應的壓縮比（壓縮比為最小約簡長度與屬性長度的比值）進行比較。當τ=2，θ=0.4，0.5，0.6，β=0.3，0.5，0.7時進行實驗，結果如表3～5所示。為描述方便，表3～5中較長的集合在表6中列出。

從實驗結果可以看出，大多情況β分布約簡結果中的蘊涵項是DRADM 約簡結果的子集，這是因為當β=0.5時，假設數(shù)據(jù)集的概率分布形如可得：此時經(jīng)典概率分布與β概率分布所得差別矩陣相同，因此兩者約簡結果相同。

表3 θ=0.4時UCI數(shù)據(jù)集約簡結果對比Tab.3 Comparison of reduction results on UCI datasets when θ=0.4

表5 θ=0.6時UCI數(shù)據(jù)集約簡結果對比Tab.5 Comparison of reduction results on UCI datasets when θ=0.6

表6 較長的集合列表Tab.6 Longer collection list

表7～9 分別是當θ=0.4、θ=0.5、θ=0.6，τ取2 時在Statlog 數(shù)據(jù)集上取不同β值的β-DRIVS 以及DRADM 和MDRADM 在不同對象數(shù)目條件下約簡結果的對比。表中，約簡長度指每個算法的約簡集合中最短的約簡長度。相應的集合為：集合1=｛｛4，0｝，｛5，0｝，｛14，0｝，｛4，6｝，｛4，8｝，｛4，10｝，｛4，11｝，｛5，6｝，｛5，8｝，｛5，10｝，｛5，11｝，｛14，6｝，｛14，8｝，｛14，11｝，｛14，10，1｝，｛14，10，7｝，｛14，10，13｝，｛14，10，15｝｝；集合2=｛｛0，5｝，｛5，6｝，｛8，5｝，｛10，5｝，｛11，5｝｝；集合3=｛｛5｝，｛14，0｝，｛0，4｝，｛0，9｝，｛0，13｝，｛0，15｝，｛14，1｝，｛14，2｝，｛14，4｝，｛6，4｝，｛8，4｝，｛10，4｝，｛11，4｝，｛14，6｝，｛6，9｝，｛6，13｝，｛6，15｝，｛14，7｝，｛14，8｝，｛8，9｝，｛8，13｝，｛8，15｝，｛14，9｝，｛10，9｝，｛11，9｝，｛14，10｝，｛10，13｝，｛10，15｝，｛14，11｝，｛11，13｝，｛11，15｝，｛14，12｝，｛14，13｝，｛14，15｝，｛0，16，1｝，｛6，16，1｝，｛8，16，1｝，｛10，16，1｝，｛11，16，1｝｝。

在表9 中，當對象數(shù)目分別為100、200、400、600、846 時，β-DRIVS 的平均約簡長度分別為1.6、2.2、1.4、2.4、2.6，DRADM 約簡長度分別為2.0、3.0、3.0、4.0、4.0，MDRADM 約簡長度分別為2.0、3.0、3.0、4.0、3.0，本文提出的算法約簡長度最短。從表7～9 可以看出，隨著β值的改變，β分布約簡的約簡結果也發(fā)生了變化。當β=0.5 時，假設數(shù)據(jù)集概率分布形如當β=0.4 時不同β值的算法得到的差別矩陣不同，因此隨著β的變化，所得的約簡結果也發(fā)生變化，此時約簡效率也會變化。3.2節(jié)將討論β取值的變化對于約簡效率的影響。

3.2 約簡效率差異對比

本節(jié)在數(shù)據(jù)集Liver Disorders、BLOGGER、Teaching Assistant Evaluation、Auto Mpg 上，當相似度閾值θ=0.4，0.5，0.6 時，對不同β取值的β-DRIVS 進行約簡效率差異對比。由于β=0.3 與β=0.7 的約簡結果相同，β=0.1 與β=0.9 的約簡結果相同，因此在本節(jié)只對β=0.1，0.3，0.5 三種情況下的算法進行約簡效率差異對比。

在上述四個數(shù)據(jù)集上，計算相容類花費了大部分時間，而通過差別函數(shù)的轉化求得約簡時間相對較少，不同β取值只會對差別函數(shù)轉化的效率產(chǎn)生影響，因此通過曲線無法體現(xiàn)不同β取值對約簡效率的影響。本節(jié)通過Wilcoxon 秩和檢驗［24］來展現(xiàn)約簡效率差異，通常設置顯著性水平為0.05。對于本文算法：假設兩個不同β取值的β-DRIVS 約簡效率沒有明顯變化。本實驗每次對兩組約簡效率數(shù)據(jù)進行檢驗，每組數(shù)據(jù)為20 次約簡的時間消耗（在20 個數(shù)據(jù)下，檢驗結果相對較好）。如果返回的p-value小于0.05，那么假設不成立，即約簡效率有明顯變化；反之假設成立。

表10 是當θ=0.4、θ=0.5、θ=0.6，τ取2 時，不同β取值的β-DRIVS 在數(shù)據(jù)集Liver Disorders、BLOGGER、Teaching Assistant Evaluation、Auto Mpg 上p-value的取值，其中下劃線標注的是小于0.05的p-value數(shù)據(jù)。

由表10 可以看出，在數(shù)據(jù)集Liver Disorders、Teaching Assistant Evaluation、Auto Mpg 上，當相似度閾值θ=0.5，0.6時，以及在數(shù)據(jù)集BLOGGER 上相似度閾值θ=0.6時，對不同β值下的約簡效率進行秩和檢驗所得的p-value均大于0.05，此時β值對于約簡效率幾乎沒有影響。在這種情況下輸出分布結果，發(fā)現(xiàn)分布均為(0，1)。此時β值不能使概率分布發(fā)生變化，因此不能影響約簡效率。

表7 θ=0.4時Statlog數(shù)據(jù)集約簡結果對比Tab.7 Comparison of reduction results on Statlog datasets when θ=0.4

表8 θ=0.5時Statlog數(shù)據(jù)集約簡結果對比Tab.8 Comparison of reduction results on Statlog datasets when θ=0.5

表9 θ=0.6時Statlog數(shù)據(jù)集約簡結果對比Tab.9 Comparison of reduction results on Statlog datasets when θ=0.6

表10 約簡效率差異的對比Tab.10 Comparison of reduction efficiency difference

在數(shù)據(jù)集BLOGGER 上：當θ=0.4 時，根據(jù)所得的p-value值，可以看出β取0.1 或0.3 與β取0.5 的約簡效率有較大差異，而β取0.1和0.3時約簡效率幾乎沒有差異；當θ=0.5時，β取0.1 或0.5 與β取0.3 的約簡效率有較大差異，而β取0.1和0.5時約簡效率幾乎沒有差異，原因是這幾種情況下β分布相同。在數(shù)據(jù)集Teaching Assistant Evaluation 上，根據(jù)p-value可知β取0.3 或0.5 與β取0.1 的約簡效率有較大差異。β取0.3 和0.5 時約簡效率幾乎沒有差異，原因與BLOGGER 數(shù)據(jù)集情況類似，此處不再贅述。在數(shù)據(jù)集Auto Mpg 上，根據(jù)pvalue可知三種不同的β取值對于約簡效率均有很大影響，原因與Liver Disorders數(shù)據(jù)集情況相同，此處不再贅述。

4 結語

為了有效處理區(qū)間類型數(shù)據(jù)，本文提出了區(qū)間值決策系統(tǒng)β分布約簡的概念，構造了對應的差別矩陣和差別函數(shù)，提出了基于差別矩陣的區(qū)間值決策系統(tǒng)β分布約簡算法，并在14 組UCI 數(shù)據(jù)集上通過與DRADM 和MDRADM 的約簡結果對比來驗證算法的有效性，而且在不同的β取值下做了約簡效率的對比。由于不同的β值會對約簡效率產(chǎn)生影響，因此在未來的研究中要選取合適的β值來簡化差別矩陣。本文的算法是在一定條件下提出的，因此在更加泛化的關系下獲得約簡是未來的研究方向之一。