不完備區(qū)間值決策系統(tǒng)的三支決策模型及增量式規(guī)則獲取算法

摘 要： 在現(xiàn)實應用中，區(qū)間值數據會因為測量、干擾或信息傳輸等噪聲影響導致數據出現(xiàn)缺失值，而且這些數據隨著時間推移呈現(xiàn)動態(tài)遞增趨勢，忽略或刪除這些數據很有可能導致有用信息的丟失而出現(xiàn)決策誤判。為此，針對這一問題，提出面向不完備區(qū)間值決策系統(tǒng)的三支決策模型和增量式規(guī)則獲取算法。首先定義不完備區(qū)間值數據的量化相似容差關系，構造出基于不完備區(qū)間值決策系統(tǒng)的三支決策模型；其次從兩個層級分析對象集動態(tài)規(guī)則獲取策略，提出增量式規(guī)則獲取算法；最后，通過一組UCI數據集對該算法進行驗證。實驗結果表明，該算法不僅能減少誤劃分損失獲得更高的劃分精度，而且在運行時間上也具有較大優(yōu)越性。

關鍵詞： 不完備區(qū)間值決策系統(tǒng)； 三支決策； 量化相似容差關系； 規(guī)則獲取； 增量算法

中圖分類號： TP181"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-029-1460-07

doi：10.19734/j.issn.1001-3695.2021.09.0431

Three-way decisions model and incremental rule acquisition algorithm for

incomplete interval-valued decision system

Liang Yanlinga，b， Tang Xiaoa，b， Gu Ruia，b

（a.School of Mathematical Sciences， b.Institute of Intelligent Information amp; Quantum Information， Sichuan Normal University， Chengdu 610066， China）

Abstract： In practical applications，interval data will have missing values due to measurement，interference，information transmission and other noise effects，and these data show a dynamic increasing trend over time，ignore or delete these data likely lead to the loss of useful information and misjudgment of decision making.To solve this problem，this paper proposed a three-way decisions model and an incremental rule acquisition algorithm for an incomplete interval-valued decision system.Firstly，it defined the quantitative similarity tolerance relationship of incomplete interval value data，and constructed a three-way decisions model based on the incomplete interval-valued decision system.Secondly，this paper analyzed two levels of dynamic rules of the object set to obtain the policy，and proposed an incremental rule acquisition algorithm.Finally，it used a set of UCI data sets to verify the algorithm.Experimental results show that this algorithm can not only reduce the loss of partition error，but also achieve higher partition accuracy，and has great advantages in running time.

Key words： incomplete interval-valued decision system； three-way decisions； quantified similarity tolerance relationship； rule acquisition； incremental algorithm

0 引言

Yao［1，2］提出的三支決策理論是二支理論的進一步拓展，其通過引入分類損失函數，基于貝葉斯決策代價最小化原則將對象劃分為三個互不相交的域，即正域、負域和邊界域。對于正域中的對象采取接受態(tài)度，對于負域中的對象采取拒絕的態(tài)度，而對于邊界域中的對象采取延遲決策的態(tài)度，需獲得更多的信息才能進一步采取決策。相較于二支決策，三支決策的延遲策略更符合人類的認知行為，在一定程度上提高分類準確率和降低誤分類損失，目前在復雜數據分析和處理中發(fā)揮著重要的作用，成為各個領域中的研究熱點［3～10］。

隨著大數據時代的變革和發(fā)展，數據往往是不斷動態(tài)更新的，如果采用傳統(tǒng)的靜態(tài)數據分析模型將會導致工作效率的降低，因此針對海量數據動態(tài)增加的問題，眾多學者提出對模型和算法構建增量式學習。例如，文獻［11］使用卡方統(tǒng)計來評估條件屬性的顯著性，采用相對屬性的條件熵作為啟發(fā)式函數，提出了一種有效的保留中間變量的動態(tài)變化數據集增量算法；文獻［12］針對區(qū)間值決策系統(tǒng)，考慮基于粗糙集理論背景下動態(tài)數據環(huán)境的知識發(fā)現(xiàn)的更新逼近的增量算法，更新有效性顯著優(yōu)于經典方法，且計算時間明顯縮短；文獻［13］則針對屬性增加且屬性值發(fā)生細化的決策信息系統(tǒng)，改進已有的二元分辨矩陣算法，通過判斷新數據與原始數據集的關系來處理動態(tài)數據集；文獻［14］則從屬性隨時間變化的矩陣角度（即添加屬性和刪除屬性）研究了鄰域決策系統(tǒng)中每個決策類的三支區(qū)域更新的兩種增量算法，其對比結果表明，算法在計算效率方面始終優(yōu)于非增量算法。

考慮區(qū)間型數據具有更強的描述不確定性的能力，且由于實際應用中數據常常出現(xiàn)缺失的情況，而目前針對這類不完備數據，文獻［15～20］的處理方法是以容差關系為基礎進行改進，即認為缺失屬性值可與任意屬性值相等，其刻畫方式過于寬松，導致很多誤分類現(xiàn)象的發(fā)生。基于上述研究背景，本文主要針對不完備且動態(tài)增加的區(qū)間值決策系統(tǒng)，提出三支決策模型及其增量式規(guī)則獲取算法。最后通過實驗驗證了該算法能獲得較高的劃分準確率和較低的誤劃分損失，并在算法運行時間上具有優(yōu)越性，為三支決策對不完備區(qū)間值數據的分析和處理提供了一種有效可行的方法。

4 實驗分析和對比

在本章中，為了對比分析算法1、2對處理不完備區(qū)間值系統(tǒng)的可行性和有效性，選取機器學習數據庫UCI中的9個完備數據集（包含：生物，如大腸桿菌及蛋白質序列；醫(yī)療，如糖尿病、肝炎、乳腺癌數據；教育評價數據；公共技術聲吶及車輛數據集等各個領域）進行實驗驗證，各數據集的信息描述如表2所示。

為了滿足實驗需求，首先采用文獻［20］給出的方法，將單值數據轉換為區(qū)間型數據，其次對數據集2～8的條件屬性值進行隨機缺失處理。為分析和比較，將文獻［15］的算法記為IIVDSA1，文獻［17］的算法記為IIVDSA2，本文的非增量算法1記為IIVTWD，增量算法2記為IIIVTWD。實驗運行環(huán)境為：操作系統(tǒng)Windows 10，處理器AMD Ryzen 7 4800U with Radeon Graphics 1.80 GHz，內存16.00 GB；所運用的軟件平臺為MATLAB 2019a。

實驗中用于分析劃分結果的度量函數定義如下：

準確率：acc=nppnpp+nnp

覆蓋率：cov=npp+nnpnpp+nbp+nnp

權衡因子：F=2×acc×covacc+cov

其中：npp、nbp、nnp表示正域、邊界域和負域中的對象數；λbp和λnp分別為當對象實際屬于某類別時被劃分到該類別的邊界域和負域所造成的損失，則誤劃分損失定義為cost=nbp×λbp+nnp×λnp。以下實驗均設置λbp=0.3，λnp=0.7，α=0.8，β=0.3。

4.1 相似率閾值ρ對本文方法的單調性影響

由前文分析可知，相似率閾值ρ的選取決定了量化容差相似類的大小，最終影響本文算法IIVTWD規(guī)則獲取結果。因此，本節(jié)將對表1中的9組數據集進行實驗分析，討論當相似率閾值從0.1到1逐漸遞增時，算法IIVTWD下的ACC、F值、cost的變化趨勢，如圖1～3所示。

從圖1～3大致來看，ACC、F值隨相似率閾值的逐漸增大而增大，呈單調遞增的趨勢，cost隨相似率閾值的逐漸增大而減小，呈單調遞減的趨勢；從局部變化來看，數據集aggregation、hepatitis在相似率閾值大于0.1后的ACC就已經達到了較高值，說明這兩個數據集的正域中的對象個數占比比較高，因此這兩個數據集的誤劃分損失cost也對應趨于最小值，而其他數據集在0.5～1時，ACC、F值才普遍偏高，且呈穩(wěn)定遞增趨勢，與之對應cost逐漸降低；從細節(jié)變化來看，有個別數據集的ACC、F值在相似率閾值增大時下降。例如，teaching數據集在相似率閾值從0.1增加到0.2時，ACC從0.024 3降到0.021 2，F(xiàn)值從0.047 2降到0.415；同樣cost也有在相似率閾值增大時下降的情況，例如，teaching數據集在相似率閾值從0.1增加到0.2時，cost從94.6增加到102.1，diabetes數據集在相似率閾值從0.3增加到0.4時，cost從319.8增加到329.7。這說明ACC、F值、cost與相似率參數并不存在嚴格的單調性。在實際應用中，可結合以上分析結論，并根據數據集的特點和實驗需求選擇合適的相似率閾值。

4.2 分類性能的比較

本節(jié)主要對IIVDSA1、IIVADS2、IIVTWD三種算法的分類性能進行實驗對比分析。基于4.1節(jié)的實驗分析，選取ρ=0.6作為以下實驗的相似率閾值。實驗主要分為兩個部分：a）對無缺失的ecoli數據集進行隨機缺失5%～20%處理，并應用于三種算法得出ACC、F值和cost，具體對比數值如表3所示；b）通過三種方法對表2中除數據集ecoli以外的其他數據集進行實驗，并將各方法下的ACC、F值和cost展示在表4中。

如表3所示，對于隨機缺失的ecoli數據集，從整體情況分析，隨著缺失程度不斷提高，各方法的ACC和F值大致呈遞減趨勢，cost大致呈遞增趨勢，由此可見，隨著缺失程度逐漸提高，各方法的分類性能在逐漸降低。但IIVTWD的ACC和F值大部分要高于IIVDSA1、IIVADS2，cost低于其他兩種方法。由此可知，IIVTWD受缺失程度的影響要小于其他兩種方法。

從表4可以看出，對于隨機缺失的UCI數據集，IIVTWD的分類性能在大多數情況下要優(yōu)于其他方法。尤其在數據量偏大的數據集diabetes、aggregation、sonar、vehicle和balancescale上，IIVTWD分類性能的優(yōu)勢較為明顯。而在數據量較少時，比如在數據集hepatitis、teaching下，此時三種方法的分類性能相差不大，且在數據集hepatitis下，IIVDSA2表現(xiàn)出更好的分類性能和更少的誤劃分損失，在數據集WDBC下，IIVDSA1表現(xiàn)出更好的分類性能和更少的誤劃分損失。

基于以上實驗數據分析，IIVTWD對于同一數據集的分類性能會隨著數據的缺失程度逐漸增大呈逐漸降低的趨勢，但始終優(yōu)于IIVDSA1和IIVADS2；而在不同的不完備數據集下，IIVTWD的分類性能在大多數情況下要優(yōu)于另外兩種算法。因此，結合理論分析和實驗對比可知，本文提出的基于量化相似容差關系的三支決策規(guī)則獲取算法IIVTWD是具有一定合理性和有效性的。

4.3 分類效率的比較

本節(jié)通過實驗比較算法IIVDSA1、IIVADS2、IIVTWD、IIIVTWD分別在對象集增加時的規(guī)則獲取效率，從而驗證本文所提的增量式規(guī)則獲取算法IIIVTWD的高效性。將表2中每個UCI數據集取60%的對象作為基礎對象集，剩余40%分成8等份，每等份分別表示為Xi（i=1，2，…，8），Ui=∪ij=1Xi（i=1，2，…，8）為實驗中每次增加的對象集，因此圖4中每幅圖的橫坐標表示增加的對象集，刻度1表示增加的對象集為U1，刻度2表示增加的對象集為U2，刻度值為1～8，縱坐標表示對象每次增加時規(guī)則獲取的算法運行時間，單位為s。

由圖4中各個數據集的實驗結果可以發(fā)現(xiàn)，隨著不完備區(qū)間值決策系統(tǒng)對象的逐漸增加，IIVTWD算法的運行時間以較快的速率增長，而IIVDSA1、IIVADS2算法增長得較為緩慢，且本文提出的增量式規(guī)則獲取算法IIIVTWD的運行時間始終保持在較低的水平，說明IIIVTWD算法采用兩個層級的增量式更新方法進行規(guī)則獲取具有高效性。

5 結束語

目前提出的增量式規(guī)則獲取大多是針對符號型或完備型信息系統(tǒng)，由于各種主觀和客觀原因，現(xiàn)實世界存在大量的不完備且動態(tài)增加的區(qū)間型數據。本文從統(tǒng)計概率的角度出發(fā)，提出了一種不完備區(qū)間數據的量化容差相似度量方法，然后研究了在對象集增加時量化容差相似類的增量式更新方法，并在此基礎進一步分析了對象集增加時三支決策規(guī)則獲取更新機制，理論證明了該更新方法的高效性，從兩個步驟避免了非增量式計算時的重復計算。最后實驗分析表明，基于量化容差相似類的三支決策模型較其他模型處理不完備數據更加客觀合理，分類效果更優(yōu)；同時，其增量規(guī)則獲取算法比非增量算法具有更高的效率。本文研究的不完備區(qū)間值決策系統(tǒng)下對象增加時的增量規(guī)則獲取，而屬性集的變化也是信息系統(tǒng)中一種常見的變化形式，因此接下來將進一步研究此類問題的三支決策模型的增量規(guī)則獲取。

參考文獻：

［1］Yao Yiyu.Three-way decisions with probabilistic rough sets［J］.Information Sciences，2010，180（3）：341-353.

［2］Yao Yiyu.The superiority of three-way decisions in probabilistic rough set models［J］.Information Sciences，2011，181（6）：1080-1096.

［3］Wang Pingxin，Yao Yiyu.CE3：a three-way clustering method based on mathematical morphology［J］.Knowledge-Based Systems，2018，155（9）：54-65.

［4］Wen Haili，Xia Fei，Tang Hongxiang.Three-way decision for incomplete real-valued data［J］.Journal of Intelligent and Fuzzy Systems，2020，39（5）：1-20.

［5］Sun Bingzhen，Chen Xiangtang，Zhang Liye，et al.Three-way decision making approach to conflict analysis and resolution using probabilistic rough set over two universes［J］.Information Sciences，2020，507：809-822.

［6］Wang Xizhao，Li Jinhai.New advances in three-way decision，granular computing and concept lattice［J］.International Journal of Machine Learning and Cybernetics，2020，11（5）：945-946.

［7］Liu Jiubing，Li Huaxiong，Zhou Xianzhong，et al.An optimization-based formulation for three-way decisions［J］.Information Sciences，2019，495：185-214.

［8］Fang Yu，Gao Cong，Yao Yiyu.Granularity-driven sequential three-way decisions：a cost-sensitive approach to classification［J］.Information Sciences，2020，507：644-664.

［9］Yao Yiyu，Wang Shu，Deng Xiaofei.Constructing shadowed sets and three-way approximations of fuzzy sets［J］.Information Sciences，2017，412-413（10）：132-153.

［10］Zhang Qinghua，Zhao Fan，Yang Jie，et al.Three-way decisions of rough vague sets from the perspective of fuzziness［J］.Information Sciences，2020，523：111-132.

［11］Su Na，An Xinjun，Yan Changqing，et al.Incremental attribute reduction method based on chi-square statistics and information entropy［J］.IEEE Access，2020，8：98234-98243.

［12］Yu Jianhuang，Xu Weihua.Incremental knowledge discovering in interval-valued decision information system with the dynamic data［J］.International Journal of Machine Learning and Cybernetics，2017，8：849-864.

［13］Feng Weibing，Ma Yunyun.An incremental attribute reduction algorithm based on improved binary distinguishable matrix［J］.Journal of Physics：Conference Series，2020，1544（1）：012018.

［14］Hu Chengxiang，Zhang Li.Incremental updating probabilistic neighborhood three-way regions with time-evolving attributes［J］.International Journal of Approximate Reasoning，2020，120：1-23.

［15］Chen Yiying，Li Zhaowen，Zhang Gangqiang.Attribute reduction in an incomplete interval-valued decision information system［J］.IEEE Access，2021，9：2169-3536.

［16］Li Zhaowen，Liao Shimin，Qu Liangdong，et al.Attribute selection approaches for incomplete interval-value data［J］.Journal of Intelligent and Fuzzy Systems，2021，40（5）：1-18.

［17］Dai Jianhua，Wei Bingjie，Zhang Xiaohong，et al.Uncertainty measurement for incomplete interval-valued information systems based on α-weak similarity［J］.Knowledge-Based Systems，2017，136（1）：159-171.

［18］Zhang Chucai，Dai Jianhua，Chen Jiaolong.Knowledge granularity based incremental attribute reduction for incomplete decision systems［J］.International Journal of Machine Learning and Cyberne-tics，2020，11（6）：1141-1157.

［19］Qi Xiaobo，Guo Husheng，Wang Wenjian.A reliable KNN filling approach for incomplete interval-valued data［J］.Engineering Applications of Artificial Intelligence，2021，100（315）：104175.

［20］Zhang Xiao，Mei Changlin，Chen Deguang，et al.Multi-confidence rule acquisition and confidence preserved attribute reduction in interval-valued decision systems［J］.International Journal of Approximate Reasoning，2014，55（8）：1787-1804.