基于測試代價的三支鄰域屬性約簡算法

張欣蕊 萬仁霞 岳曉冬 陳瑞典

摘 要：針對粗糙集屬性約簡時很少考慮屬性自身的測試代價等問題，提出了一種基于測試代價的三支鄰域屬性約簡算法。算法根據(jù)各屬性在鄰域分辨矩陣中出現(xiàn)的頻次和比例來計算屬性重要性，并結合屬性自身的測試代價來構造性價比指標，以此指導屬性的甄選。三支決策方法被用于劃分屬性集，為屬性的約簡處理提供數(shù)據(jù)支撐。在7個UCI公共數(shù)據(jù)集上進行對比實驗，結果表明，該算法可得到比對比算法更小的屬性約簡集合，在分類精度不降低的情況下，該算法具有更少的運行時間和更小的測試代價?；谪斦杖氲念A測應用實例進一步證明了所提算法的有效性和實用性。

關鍵詞：鄰域粗糙集； 鄰域分辨矩陣； 屬性約簡； 測試代價； 三支決策

中圖分類號：TP391?? 文獻標志碼：A

文章編號：1001-3695（2024）03-028-0836-06

doi：10.19734/j.issn.1001-3695.2023.06.0306

Three-way neighborhood attribute reduction algorithm based on test cost

Zhang Xinrui1， Wan Renxia1， Yue Xiaodong2， Chen Ruidian3

（1.College of Mathematics & Information Science， North Minzu University， Yinchuan 750021， China; 2.School of Computer Engineering & Science， Shanghai University， Shanghai 200444， China; 3.Institute for Big Data in Health Fujian Hongyang Software Co.， Ltd.， Fuzhou 350002， China）

Abstract：In order to address the issue of test cost being rarely considered in rough set attribute reduction， this paper proposed a three-way neighborhood attribute reduction algorithm based on test cost. The proposed algorithm calculated the attri-bute importance according to the frequency and proportion of each attribute in the neighborhood resolution matrix， and combined the test cost of the attributes to construct the the cost performance index to guide the selection of attributes. Three-way decision-making method was employed to partition attribute sets， which provided data support for the attribute reduction process. Comparative experiments were conducted on seven UCI public datasets， which demonstrate that the proposed algorithm yields a smaller attribute reduction set compared to the comparison algorithm. Moreover， the proposed algorithm exhibited a shorter running time and lower test cost without compromising classification accuracy. Furthermore， it provided an application example based on fiscal revenue prediction to further validate the effectiveness and practicality of the proposed algorithm.

Key words：neighborhood rough set; neighborhood resolution matrix; attribute reduction; test cost; three-way decisions

0 引言

1982年，粗糙集理論由Pawlak教授［1］首次提出。這是一種用來處理不確定、不精確信息的新型數(shù)學方法。 粗糙集理論［2］利用上下近似的方式對集合進行刻畫，并把整個論域劃分為三部分。基于此，Yao［3］提出了三支決策的思想，認為從正域中得到的規(guī)則表示對決策的接受，從邊界區(qū)域獲得的規(guī)則代表了決策的延遲，從負域得到的規(guī)則表示對決策的拒絕。三支決策思想的提出，為將粗糙集理論運用到實際的決策問題上提供了理論依據(jù)。

屬性約簡［4］是粗糙集領域研究的一項重要內(nèi)容，其目的是在保證屬性集合對知識庫劃分能力不變的前提下，對冗余屬性進行刪除?；诘葍r關系提出的粗糙集模型只能對離散型數(shù)據(jù)進行處理，而在實際應用中卻有大量的連續(xù)數(shù)據(jù)集合［5］。因此，Lin［6］在信息?；?、粒度的基礎上提出鄰域關系。胡清華等人［7］基于Lin的研究成果，提出了一種鄰域粗糙集模型，用鄰域關系代替原有的等價關系來處理連續(xù)型數(shù)據(jù)。在屬性約簡過程中，能否準確度量屬性重要性十分關鍵。典型的屬性重要性定義方法主要有基于Pawlak［8］和基于條件熵［9］兩類。但這兩種方法度量的都是核屬性重要性，而非核屬性的重要性均為零。葉軍等人［10］以分辨矩陣為基礎，提出了一種新的屬性重要性定義方法。該方法既能度量核屬性重要性，也能度量非核屬性重要性，避免了非核屬性重要性都為零的情況。季雨瑄等人［11］把等價關系下的分辨矩陣拓展到鄰域粗糙集中，屬性的重要性函數(shù)是根據(jù)條件屬性在鄰域分辨矩陣中出現(xiàn)的頻次和比例而構造的，并以此作為啟發(fā)性因子，提出了一種新的啟發(fā)式屬性約簡算法。

上述模型都是以精度為目標，但實際應用中不僅需要關注數(shù)據(jù)的分類精度，也要關注獲取數(shù)據(jù)的代價，即測試代價［12］。雖然屬性集越多，分類精度會越高，但同時也會增加測試代價［13］。因此，在屬性約簡的過程中需要考慮測試代價，只有這樣才能使算法更加適應實際問題。劉瓊等人［14］重新定義了基于區(qū)間值鄰域的熵結構，構造了區(qū)間值系統(tǒng)下的代價敏感函數(shù)，并提出了基于代價敏感的區(qū)間值特征選擇方法。Fang等人［15］基于三支決策和分辨矩陣，提出了解決測試代價近似屬性約簡問題的框架，并設計了測試代價屬性約簡算法的添加策略和刪除策略。文獻［16～18］研究了基于測試代價的約簡算法，用于解決多屬性約簡問題。

目前在鄰域粗糙集中引入測試代價的研究較少?；诖?，本文結合三支決策思想，將測試代價融入鄰域粗糙集下的屬性約簡算法，提出了一種基于測試代價的三支鄰域屬性約簡算法。

1 預備知識

1.1 鄰域粗糙集

定義1［7］ 給定論域U={x1，x2，…，xn}，C為條件屬性，D為決策屬性，V是屬性值的集合，f=U×（C∪D）→V是信息函數(shù)，δ（0≤δ≤1）為鄰域半徑，則稱NDS=（U，C∪D，V，f，δ）是一個鄰域決策系統(tǒng)。

3.2 鄰域半徑δ取值分析

δ的取值直接影響屬性約簡的結果。在不同的δ取值下，算法得到的屬性約簡不同，這會造成根據(jù)屬性約簡進行分類后得到的分類精度不同［21］。本文在［0，1］內(nèi)按0.01增進，采用高斯樸素貝葉斯分類算法，δ取值與分類精度的關系如圖2所示。

圖2（a）～（h）描述了在不同的δ取值下，數(shù)據(jù)集約簡后的分類精度和獲取相應屬性所需代價值。隨著δ的增大，各數(shù)據(jù)集的分類精度和屬性代價最后均趨于穩(wěn)定并涵蓋了屬性集合中的所有屬性。由圖2可知，當δ取值為0.03～0.05時，數(shù)據(jù)集的分類精度較高且屬性代價較小，本文選取δ=0.05。

3.3 實驗結果分析

將本文算法與文獻［7，11］算法進行對比，三種算法進行屬性約簡后所得條件屬性情況如表10所示。從表10可以發(fā)現(xiàn)，本文算法與文獻［7，11］算法約簡后得到的條件屬性個數(shù)均有明顯減少，說明三種算法都可以達到屬性約簡的目的，具有有效性。分別使用這三種算法對數(shù)據(jù)集進行屬性約簡， 統(tǒng)計各自對應的屬性約簡長度、測試代價、分類精度和運行時間。實驗結果如圖3～6所示。

觀察圖3可知，本文算法得到的屬性約簡長度均小于文獻［11］的約簡長度。在wine、WDBC、German、sonar數(shù)據(jù)集中，雖然本文算法的約簡長度大于文獻［7］，但在WPBC和Hcvdat數(shù)據(jù)集中，本文算法和文獻［7］得到的屬性約簡長度相同，在heart數(shù)據(jù)集中，本文算法得到的屬性約簡長度在三種算法中最短。由圖4可知，本文算法所得約簡測試代價最小。在圖5中可以發(fā)現(xiàn)，三種算法的分類精度較為接近且精度較高。圖6中，代表本文算法的折線整體位于其他兩條折線的下方，說明本文算法在運行過程中所用時間最短，效率最高。

綜上可知，相較于文獻［7，11］算法，采用本文算法進行屬性約簡后得到的屬性約簡個數(shù)適中，分類精度較高且運行時間較短。

4 實例分析

為了驗證本文算法的實用性，將其應用在財政收入預測中。所采用的數(shù)據(jù)均來自《國家統(tǒng)計年鑒》，數(shù)據(jù)時間為2000—2021年，詳細數(shù)據(jù)如圖7所示。參考相關文獻資料［22］，選取13個影響財政收入（y）的主要因素。

本文選擇了13個可能影響財政收入的指標，數(shù)據(jù)維度較多，需要對數(shù)據(jù)進行降維處理。假設本章數(shù)據(jù)集中各屬性的測試代價全部服從N（0.02，0.01），據(jù)此隨機生成屬性測試代價，具體數(shù)值如表11所示。

分別使用本文構建的屬性約簡算法、文獻［7，11］算法對影響財政收入的因素進行約簡，結果如表12所示。

根據(jù)表12可以發(fā)現(xiàn)，本文構建的基于測試代價的三支鄰域屬性約簡算法得到的屬性約簡集合付出的代價最小，且算法的運行時間最短。

基于本文構建的基于測試代價的三支鄰域屬性約簡算法得到的約簡結果，將影響財政收入的影響因素由初始的13個縮減為3個，分別為就業(yè)人員總數(shù)x1、城鎮(zhèn)居民人均消費性支出x2、年末總人口x3。將這三個因素作為多元線性回歸模型的樣本特征，構建多元線性回歸模型，得到我國財政收入預測模型為

y=0.033+4.488x1+1.591x2-5.802x3（17）

由表13中F檢驗的結果分析可以得到，顯著性P值為0.000***，水平上呈現(xiàn)顯著性，拒絕回歸系數(shù)為0的原假設，因此模型基本滿足要求。

我國財政收入預測模型的擬合效果圖如圖8所示。

由表14可知，我國財政收入預測模型的平均相對誤差為0.082，R2為0.995，調(diào)整后R2為0.994，說明采用本文算法的財政收入預測模型平均誤差較小且擬合質(zhì)量高，模型具有良好的參考性和應用價值。

5 結束語

本文將三支決策思想融入鄰域粗糙集屬性約簡算法中， 提出一種基于測試代價的三支鄰域屬性約簡算法。算法利用各屬性在鄰域分辨矩陣中出現(xiàn)的頻次及比例計算屬性重要性，并在此基礎上考慮屬性的測試代價構造性價比指標，以此作為三支決策的評價函數(shù)，對屬性進行三分。算法有效地解決了屬性約簡問題，與同類算法相比，還具有運行時間短、分類效率高的特點。最后，將本文算法應用于財政收入預測中，得到的財政收入預測模型通過了F檢驗，平均誤差較小且擬合程度較好，說明了本文算法的有效性和實用性。

由于UCI數(shù)據(jù)集中并沒有給出各個屬性相應的測試代價，所以經(jīng)常采用分布函數(shù)隨機生成測試代價。不同的測試代價分布會對約簡結果產(chǎn)生影響。常用的測試代價分布有均勻分布、正態(tài)分布和帕累托分布。為方便計算，本文中采用正態(tài)分布函數(shù)生成測試代價。后續(xù)工作中，將研究采用均勻分布函數(shù)和帕累托分布函數(shù)生成測試代價時本文算法的約簡性能。

參考文獻：

［1］Pawlak Z. Rough sets［J］. International Journal of Computer and Information Sciences， 1982，11（5）： 341-356.

［2］胡成祥， 張莉， 黃曉玲， 等. 面向屬性變化的動態(tài)鄰域粗糙集知識更新方法［J］. 山東大學學報： 理學版， 2023，58（7）： 37-51. （Hu Chengxiang， Zhang Li， Huang Xiaoling， et al. Dynamic neighborhood rough sets approaches for updating knowledge while attributes generalization［J］. Journal of Shandong University： Natural Science， 2023，58（7）： 37-51.）

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

［4］Wang Zhen， Shi Chengjun， Wei Ling， et al. Tri-granularity attribute reduction of three-way concept lattices［J］. Knowledge-Based Systems， 2023，276.

［5］楊潔， 匡俊成， 王國胤， 等. 代價敏感的多粒度鄰域粗糙模糊集的近似表示［J］. 計算機科學， 2023，50（5）： 137-145. （Yang Jie， Kuang Juncheng， Wang Guoyin， et al. Cost-sensitive multigra-nulation approximation of neighborhood rough fuzzy sets［J］. Computer Science， 2023，50（5）： 137-145.）

［6］Lin T Y. Granular computing on binary relations I： data mining and neighborhood systems［J］. Rough Sets in Knowledge Discovery， 1998，1（1）： 107-121.

［7］胡清華， 于達仁， 謝宗霞. 基于鄰域?；痛植诒平臄?shù)值屬性約簡［J］. 軟件學報， 2008，19（3）： 640-649. （Hu Qinghua， Yu Daren， Xie Zongxia. Numerical attribute reduction based on neighborhood granulation and rough approximation［J］. Journal of Software， 2008，19（3）： 640-649.）

［8］盛茹雪， 李紅宇， 姜春茂， 等. 一種基于序貫三支決策的屬性約簡方法研究［J］. 模糊系統(tǒng)與數(shù)學， 2021，35（6）： 48-65. （Sheng Ruxue， Li Hongyu， Jiang Chunmao， et al. An attribute reduction method based on sequential three-way decision［J］. Fuzzy Systems and Mathematics， 2021，35（6）： 48-65.）

［9］張曉燕， 匡洪毅. 區(qū)間值序決策表的條件熵屬性約簡［J］. 山西大學學報： 自然科學版， 2023， 46（1）： 101-107. （Zhang Xiao-yan， Kuang Hongyi. Attribute reduction based on conditional entropy in interval valued ordered decision table［J］. Journal of Shanxi University： Natural Science， 2023，46（1）： 101-107.）

［10］葉軍， 朱華生， 黎敏. 一種屬性重要性定義方法及其在約簡中的應用［J］. 計算機應用研究， 2016， 33（7）： 2075-2078，2086. （Ye Jun， Zhu Huasheng， Li Min. A kind of attribute importance defined method and its application in attribute reduction［J］. Application Research of Computers， 2016，33（7）： 2075-2078，2086.）

［11］季雨瑄， 葉軍， 楊震宇， 等. 結合分辨矩陣改進的鄰域粗糙集屬性約簡算法［J］. 山東大學學報： 工學版， 2022，52（4）： 99-109. （Ji Yuxuan， Ye Jun， Yang Zhenyu， et al. An improved neighborhood rough set attribute reduction algorithm combined with resolution matrix［J］. Journal of Shandong University： Engineering Science， 2022，52（4）： 99-109.）

［12］吳迪， 廖淑嬌， 范譯文. 協(xié)調(diào)多尺度決策系統(tǒng)中基于測試代價的屬性與尺度選擇［J］. 模式識別與人工智能， 2023，36（5）： 433-447. （Wu Di， Liao Shujiao， Fan Yiwen. Attribute and scale selection based on test cost in consistent multi-scale decision systems［J］. Pattern Recognition and Artificial Intelligence， 2023，36（5）： 433-447.）

［13］呂艷娜， 茍光磊， 張里博， 等. 深度置信網(wǎng)絡的代價敏感多粒度三支決策模型研究［J］. 計算機應用研究， 2023，40（3）： 833-838. （Lyu Yanna， Gou Guanglei， Zhang Libo， et al. Research on cost-sensitive multi-granularity three-way decision model for deep belief network［J］. Application Research of Computers， 2023，40（3）： 833-838.）

［14］劉瓊， 代建華， 陳姣龍. 區(qū)間值數(shù)據(jù)的代價敏感特征選擇［J］. 南京大學學報： 自然科學版， 2021，57（1）： 121-129. （Liu Qiong， Dai Jianhua， Chen Jiaolong. Cost-sensitive feature selection for interval-valued data［J］. Journal of Nanjing University： Natural Scicence， 2021，57（1）： 121-129.）

［15］Fang Yu， Min Fan. Cost-sensitive approximate attribute reduction with three-way decisions［J］. International Journal of Approximate Reasoning， 2019，104： 148-165.

［16］張清華， 龐國弘， 李新太， 等. 基于代價敏感的序貫三支決策最優(yōu)粒度選擇方法［J］. 電子與信息學報， 2021，43（10）： 3001-3009. （Zhang Qinghua， Pang Guohong， Li Xintai， et al. Optimal granularity selection method based on cost-sensitive sequential three-way decisions［J］. Journal of Electronics & Information Techno-logy， 2021， 43（10）： 3001-3009.）

［17］鄧大勇， 劉月錚， 肖春水. 決策系統(tǒng)簇的平均代價敏感并行約簡［J］. 浙江師范大學學報： 自然科學版， 2023，46（1）： 7-17. （Deng Dayong， Liu Yuezheng， Xiao Chunshui. A study of average cost-sensitive parallel reducts in a family of decision systems［J］. Journal of Zhejiang Normal University： Natural Science， 2023，46（1）： 7-17.）

［18］劉鑫， 胡軍， 張清華. 屬性組序下基于代價敏感的約簡方法［J］. 南京大學學報： 自然科學， 2020，56（4）： 469-479. （Liu Xin， Hu Jun， Zhang Qinghua. Attribute reduction based on cost sensitive under attribute group order［J］. Journal of Nanjing University： Natural Science， 2020，56（4）： 469-479.）

［19］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.

［20］Yao Yiyu. Three-way decisions and cognitive computing［J］. Cognitive Computation， 2016，8（4）： 543-554.

［21］Li Baizhen， Wei Zhihua， Miao Duoqian， et al. Improved general attribute reduction algorithms［J］. Information Sciences， 2020，536： 298-316.

［22］任晶晶， 高上彬. 基于SVR的呂梁市地方財政收入預測模型［J］. 信息技術與信息化， 2022 （1）： 46-49. （Ren Jingjing， Gao Shangbin. Prediction model of local fiscal revenue in Lyuliang based on SVR［J］. Information Technology and Informatization， 2022（1）： 46-49.）