基于測試代價(jià)的三支鄰域?qū)傩约s簡算法

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

摘 要：針對粗糙集屬性約簡時(shí)很少考慮屬性自身的測試代價(jià)等問題，提出了一種基于測試代價(jià)的三支鄰域?qū)傩约s簡算法。算法根據(jù)各屬性在鄰域分辨矩陣中出現(xiàn)的頻次和比例來計(jì)算屬性重要性，并結(jié)合屬性自身的測試代價(jià)來構(gòu)造性價(jià)比指標(biāo)，以此指導(dǎo)屬性的甄選。三支決策方法被用于劃分屬性集，為屬性的約簡處理提供數(shù)據(jù)支撐。在7個(gè)UCI公共數(shù)據(jù)集上進(jìn)行對比實(shí)驗(yàn)，結(jié)果表明，該算法可得到比對比算法更小的屬性約簡集合，在分類精度不降低的情況下，該算法具有更少的運(yùn)行時(shí)間和更小的測試代價(jià)?；谪?cái)政收入的預(yù)測應(yīng)用實(shí)例進(jìn)一步證明了所提算法的有效性和實(shí)用性。

關(guān)鍵詞：鄰域粗糙集； 鄰域分辨矩陣； 屬性約簡； 測試代價(jià)； 三支決策

中圖分類號：TP391?? 文獻(xiàn)標(biāo)志碼：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ù)學(xué)方法。 粗糙集理論［2］利用上下近似的方式對集合進(jìn)行刻畫，并把整個(gè)論域劃分為三部分?；诖?，Yao［3］提出了三支決策的思想，認(rèn)為從正域中得到的規(guī)則表示對決策的接受，從邊界區(qū)域獲得的規(guī)則代表了決策的延遲，從負(fù)域得到的規(guī)則表示對決策的拒絕。三支決策思想的提出，為將粗糙集理論運(yùn)用到實(shí)際的決策問題上提供了理論依據(jù)。

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

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

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

1 預(yù)備知識(shí)

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，δ）是一個(gè)鄰域決策系統(tǒng)。

3.2 鄰域半徑δ取值分析

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

4 實(shí)例分析

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

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

分別使用本文構(gòu)建的屬性約簡算法、文獻(xiàn)［7，11］算法對影響財(cái)政收入的因素進(jìn)行約簡，結(jié)果如表12所示。

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

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

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

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

我國財(cái)政收入預(yù)測模型的擬合效果圖如圖8所示。

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

5 結(jié)束語

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

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

參考文獻(xiàn)：

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

［2］胡成祥， 張莉， 黃曉玲， 等. 面向?qū)傩宰兓膭?dòng)態(tài)鄰域粗糙集知識(shí)更新方法［J］. 山東大學(xué)學(xué)報(bào)： 理學(xué)版， 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］楊潔， 匡俊成， 王國胤， 等. 代價(jià)敏感的多粒度鄰域粗糙模糊集的近似表示［J］. 計(jì)算機(jī)科學(xué)， 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］胡清華， 于達(dá)仁， 謝宗霞. 基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡［J］. 軟件學(xué)報(bào)， 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ù)學(xué)， 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］. 山西大學(xué)學(xué)報(bào)： 自然科學(xué)版， 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］葉軍， 朱華生， 黎敏. 一種屬性重要性定義方法及其在約簡中的應(yīng)用［J］. 計(jì)算機(jī)應(yīng)用研究， 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］季雨瑄， 葉軍， 楊震宇， 等. 結(jié)合分辨矩陣改進(jìn)的鄰域粗糙集屬性約簡算法［J］. 山東大學(xué)學(xué)報(bào)： 工學(xué)版， 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)中基于測試代價(jià)的屬性與尺度選擇［J］. 模式識(shí)別與人工智能， 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)絡(luò)的代價(jià)敏感多粒度三支決策模型研究［J］. 計(jì)算機(jī)應(yīng)用研究， 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ù)的代價(jià)敏感特征選擇［J］. 南京大學(xué)學(xué)報(bào)： 自然科學(xué)版， 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］張清華， 龐國弘， 李新太， 等. 基于代價(jià)敏感的序貫三支決策最優(yōu)粒度選擇方法［J］. 電子與信息學(xué)報(bào)， 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)簇的平均代價(jià)敏感并行約簡［J］. 浙江師范大學(xué)學(xué)報(bào)： 自然科學(xué)版， 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］劉鑫， 胡軍， 張清華. 屬性組序下基于代價(jià)敏感的約簡方法［J］. 南京大學(xué)學(xué)報(bào)： 自然科學(xué)， 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的呂梁市地方財(cái)政收入預(yù)測模型［J］. 信息技術(shù)與信息化， 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.）