基于粗糙集的不完备谣言信息系统的知识获取与决策.pdf

第 9 卷 第 2 期 信 息 安 全 学 报 Vol.9 No.2 2024 年 3 月 Journal of Cyber Security March 2024 通讯作者:卫红权,博士,研究员,Email:。本课题得到中原英才计划项目(No.212101510002)资助。收稿日期:2022-05-24;修改日期:2022-08-19;定稿日期:2023-11-01 基于粗糙集的不完备谣言信息系统的知识 获取与决策 王 标1,卫红权1,2,王 凯1,2,刘树新1,2,江昊聪1,2 1中国人民解放军战略支援部队信息工程大学 郑州 中国 450001 2国家数字交换系统工程技术研究中心 郑州 中国 450002 摘要 网络谣言可能扰乱人们的思想、心理和行为,引发社会震荡、危害公共安全,而微博等社交平台的广泛应用使得谣言造成的影响与危害变得更大,因此,谣言检测对于网络空间的有序健康发展具有重要的意义。当前谣言的自动检测技术更多关注检测模型的构建和输入数据的表现形式,而在改善数据质量以提高谣言识别效果方面的研究很少。基于此,本文将粗糙集理论应用于不完备谣言信息系统进行知识获取与决策,实质上是通过粗糙集理论解决不完备谣言信息系统的不确定性度量,冗余性以及不完备性等问题,以获得高质量的数据,改善谣言检测效果。首先系统总结了粗糙集理论中不确定性度量的方法,包括香农熵、粗糙熵、Liang 熵以及信息粒度等四种不确定度量方法,并整理和推导了这四种不确定度量方法从完备信息系统到不完备信息系统的一致性拓展。基于上述总结的四种不确定度量方法,提出了基于最大相关最小冗余(MCMR,Maximum Correlation Minimum Redundancy)的知识约简算法。该方法基于熵度量方式,能够综合考量决策信息与冗余噪音,在 UCI 及 Weibo 等 8 个数据集上实验验证,结果表明本文算法优于几种基线算法,能够有效解决信息系统的冗余性。另外,提出了一种基于极大相容块的不完备决策树算法,在不同缺失程度数据上实验验证,结果表明本文算法能够有效解决信息系统的不完备性。关键词 谣言检测;粗糙集;不完备信息系统;最大相关最小冗余;极大相容块 中图法分类号 TP391.1;O236 DOI 号 10.19363/J10-1380/tn.2024.03.02 Knowledge Acquisition and Decision Making in Incom-plete Rumor Information System based on Rough Set WANG Biao1,WEI Hongquan1,2,WANG Kai1,2,LIU Shuxin1,2,JIANG Haocong1,2 1PLA Strategic Support Force Information Engineering University,Zhengzhou 450002,China 2National Digital Switching System Engineering and Technological R&D Center,Zhengzhou 450002,China Abstract Online rumors may disrupt peoples thoughts,psychology and behavior,cause social shocks and endanger public safety.The widespread use of social platforms such as Weibo makes the impact and harm caused by rumors even greater.Therefore,rumor detection is of great significance to the orderly and healthy development of cyberspace.The current automatic detection techniques for rumors focus more on the construction of detection models and the represen-tation of input data,while there is little research on improving the quality of data to improve the effect of rumor detec-tion.Based on this idea,this paper applies the rough set theory to the incomplete rumor information system for knowl-edge acquisition and decision-making.In essence,to obtain high-quality data and improve rumor detection,the rough set theory is used to solve the uncertainty measurement,redundancy,and incompleteness of the incomplete rumor in-formation system.Firstly,it systematically summarizes the methods of uncertainty measurement in rough set theory,including four uncertainty measurement methods such as Shannon entropy,rough entropy,Liang entropy,and informa-tion granularity,and organizes and derives the consistent expansion of the four uncertainty measurement methods from complete information system to incomplete information system.Based on the four uncertainty measurement methods summarized above,a knowledge reduction algorithm based on Maximum Correlation Minimum Redundancy(MCMR)is proposed.The method is based on entropy measurement,which can comprehensively consider decision information and redundant noise.Experiments on 8 data sets such as UCI and Weibo show that the algorithm in this paper is supe-rior to several baseline algorithms and can effectively solve the redundancy of the information system.In addition,this paper proposes an incomplete decision tree algorithm based on maximal consistent blocks.Experiments on data with different degrees of missingness show that the algorithm in this paper can effectively solve the incompleteness of the information system.20 Journal of Cyber Security 信息安全学报,2024 年 3 月,第 9 卷,第 2 期 Key words rumor detection;rough set;incomplete information system;maximum correlation minimum redundancy;maximal consistent blocks 1 引言 微博等社交平台的广泛应用缩短了信息传播的周期,扩大了信息传播的范围,使得虚假信息传播更加容易实现,造成的影响和危害变得更大1。比如当前新冠疫情传播的谣言四处而起,给政府、社会和人们造成了巨大的困扰。越来越多的现实网络被人们研究,从建模到信息挖掘2,社交网络3领域的谣言识别一直是近年来研究的热点。谣言识别本质上是一个分类问题,从早期的传统机器学习方法到深度学习方法,我们一直致力于寻找更好的分类模型,提高谣言识别的效果。早期自动检测大多基于传统的机器学习方法,如决策树4-5、支持向量机4-8、随机森林5,9、逻辑回归9、朴素贝叶斯9、传统自然语言处理10等方法,采用手工提取特征,耗时耗力,而且不能提取深层的特征。近年来的自动检测方法越来越多地采用深度学习方法,如卷积神经网络(CNN)11-12,BERT 预训练模型13、长短期记忆网络(LSTM)12,14,RNN15、门控循环单元GRU16-17,图卷积神经网络(GCN)18-19等。深度学习模型能够自动提取特征,且可以进行深度拟合,识别谣言效果好,但是可解释性不强,鲁棒性弱,调参困难等问题也不容忽视。同时,当前的文献更注重从模型构建方面提高谣言的识别效果,从数据分析与处理方面提高数据质量的文献较少。而数据的复杂性20、不确定性21、不完备性22和冗余性23是在网络空间发展中逐渐具备的特征。数据的质量将直接影响到模型的性能。当前数据的复杂性越来越高,突出表现在数据的量级以及数据源的种类。本文所描述的数据复杂性是数据源种类中的数值多样性,包括符号型、连续型、离散型、区间型、模糊型、标签类、文本以及空值等。混合类型数据不能直接用于模型的训练,需要进一步处理,而数据处理的好坏将直接影响到模型的性能。而数据的不确定性包括随机性、粗糙性以及模糊性,分别是因为因果关系不确定、知识不充分以及定义不明确造成的。不同的不确定性数据需要不一样的模型处理,反过来也会对模型的性能产生影响。同时,在数据获取或处理时有些信息是缺失的,即不完备性,这部分数据可能具有极大价值,但因为缺失常被直接删掉或用其他值代替,没有有效地发挥其数据的作用和效果。还有,相似冗余的数据,在给我们带来可用信息的同时,也造成了不必要的噪音以及计算消耗。沿着这个思路,本文从如何解决谣言信息系统的不确定性,不完备性以及冗余性角度出发进行谣言识别。粗糙集理论是 Pawlak24提出的一种数学工具,它能够定量分析处理不确定,不一致,不完备的信息与知识。本文将粗糙集理论应用于谣言识别,在不完备谣言信息系统中进行知识获取与决策,本质上是通过粗糙集理论解决谣言信息系统的不确定性度量,冗余性以及不完备性。本文的贡献主要有:将粗糙集理论应用于谣言检测,系统总结了粗糙集理论中的不确定性度量方法和不同度量方法在完备信息系统和不完备信息系统中的一致性表达。提出了一种基于最大相关最小冗余的知识约简算法,该算法能够综合考量决策信息与冗余噪声,实验结果表明,算法优于多种基线算法,能有效解决信息系统的冗余性。基于极大相容块提出了一种以决策粗糙指标为核的不完备决策树模型,可有效解决信息系统的不完备性。2 相关工作 2.1 谣言检测最新研究 随着社交网络的不断发展以及谣言特征的不断变化,谣言检测经历了人工事实核查、传统机器学习、深度学习等阶段。目前的研究大部分都是基于深度学习方法,而且多采用图神经网络(GNN)来提取谣言的传播特征。Bian 等人18首次将 GCN 应用于社交媒体的谣言检测,通过自顶向下和自底向上的双向 GCN 提取谣言的传播和扩散特征。为了动态调整传播图中每个节点的权重,Wu 等人25采用基于注意力机制的图神经网络模型,进一步提升了谣言检测的性能。然而当前的检测模型大多基于静态网络,针对这个问题,Song等人26提出了一种新的基于时间传播的动态检测框架,可以融合结构、内容语义和时间信息。现有的模型大部分都是有监督学习模型,需要大量的标签数据,而数据的标注是一项费时费力的工程。为此,He等人27引入了对比自监督学习来有效实现事件增强,并缓解有限的标签数据问题。王标 等:基于粗糙集的不完备谣言信息系统的知识获取与决策 21 但总的来讲,深度学习模型适合进行谣言识别的感知与预警,但其可解释性不足的问题让人们无法完全信服模型的判断,而人工选择特征,可解释性较强的传统机器学习算法更适合进行决策。2.2 粗糙集理论研究与应用 粗糙集理论是 Pawlak 教授24于 1982 年提出的。后来,Ivo 等人28,Theresa 等人29,Liang 等人30-31将香农熵及其变体应用于粗糙集理论中测度系统的不确定性。Liang 等人22,32-33结合补集提出了熵的新形式,即 Liang 熵,同时整理证明了 Liang 熵与知识粒度,香农熵与粗糙熵的关系。传统粗糙集的属性约简算法依赖于严格的等价关系,有很多局限。众多学者在此基础上,提出决策粗糙集34,概率粗糙集35,多粒度粗糙集36,变精度粗糙集37等,并应用于不相容决策信息表38,不完备决策信息表39,连续型属性决策信息表40,有序型属性决策信息表41,属性动态变化决策信息表42等。粗糙集理论广泛应用于各种领域,如种类识别、物流模式决策、医疗诊断、智能识别、机器学习、数据分析以及网络检测等43。周正国44运用模糊粗糙集属性约简的方法,在海量的数据挖掘中,利用Canopy 算法对 K-means 算法进行改进,实现了K-means算法在Hadoop 平台上的并行化计算。郭威45基于贝叶斯粗糙集提出了大数据频繁项挖掘方法,具有较高的鲁棒性,大大提高了数据挖掘的准确率和运行时间。2.3 不完备信息系统知识获取研究 现实中,不精确的数据测量造成的误差、不同的数据理解以及数据获取的严格限制等都可能导致信息系统的不完备性46。在粗糙集理论中,知识被看作是一种分类的能力。不完备信息系统中的知识获取一般有两种方式:间接处理与直接处理46。间接处理,就是将不完备信息系统进行完备化,然后用传统的知识获取方法进行处理。常见的完备化操作有填充值与删除值。填充值包括填充均值、最大值、最小值、0、1 等,删除值就是不考虑含有未知属性值的对象,直接删除。直接处理,就是将粗糙集中的部分概念在不完备信息系统下进行适当拓展。主要采用了相似关系、相容关系和极大相容关系等。Slowiski 等人47利用粗糙集理论对对象属性值的不精确、不完备等进行了建模与描述,对不确定数据进行了推理。Lipski 等人48基于相容关系提出了一种在信息不完整数据库中进行查询的模型。3 粗糙集基础 3.1 完备信息系统,SU A V f是一个信息系统,其中U为对象的非空有限集合,称为论域(universe);A 为属性的非空有限集合;特别地,CDA,C 为条件属性集合,D 为决策属性集合,带有决策属性集合 D 的信息系统又被称为决策信息系统。aa AVV,aV表示属性a的值域;:f UAV 是一个函数,即对,x U aA ,有,af x aV。,SU A V f可简记为,SU A。形式上,用信息表来表示,如表1。它的行代表对象,也是数据中的样本;列代表属性,属性值对应数据样本的不同维度的特征值。在粗糙集理论中,知识代表的是分类能力,也就是利用对象的条件属性值区分其决策属性值的能力,传统的粗糙集理论建立在严格的不可区分关系上49。令BA,定义属性集B的不可区分关系(indiscernibility)IND B为 ,IND Bx yU UaB f x af y a 如果,x yIND B,则称x和y是B不可区分的。符号/U IND B表示不可区分关系 IND B在U上导出的划分。符号 Bx表示包含xU的B等价类。3.2 不完备信息系统 设,SU A V f是一个信息系统,某些时候,对一些对象而言,一些属性值可能是缺损的。如果至少有一个属性aA,aV中含有空值,则称S是一个不完备信息系统(incomplete information system),否则它是完备信息系统。这表明完备信息系统是不完备信息系统的特例。并用*表示空值50。设BA,我们定义相容关系,SIM Bu v,*,*U UaB f u af v a or f u aor f v a 易知 a BSIM BSIMa,令 BSu表示对象集,vU u vSIM B。BSu表示与U具有相容关系的所有对象集合,相对B而言,这些关系可能是可区分的,也可能是不可区分的。/BU SIM BSuuU,/U SIM B中的元素称为相容类。/U SIM B中的相容类一般不构成U的划分,它们构成U的覆盖,即对于每一个22 Journal of Cyber Security 信息安全学报,2024 年 3 月,第 9 卷,第 2 期 uU有 BSU ,且 Bu USuU。3.3 极大相容块 相比于相容关系,极大相容块是对不完备信息划分的更简洁、更凝练的表示方式,下面给出极大相容块的定义。定义定义 151.设,SU A V f是一个不完备信息系统,BA,XU,我们称X关于B是相容的,如果对任意的,x yX有,x ySIM B。如果不存在一个对象子集YU使得XY且Y关于B是相容的,则X被称为一个极大相容子集或极大相容块52。极大相容块也是极大对象集合,里面的所有对象都是相似的或者相容的,是不可区分的。以 blockCB表示由BA导出的所有极大相容块所构成的类52,如例1。例例 1.表1是一个简化的不完备谣言决策信息表。其中City,Province,Friends,Followers,Gender是系统的条件属性,d为决策属性。下面Ci、P、Fr、Fo、G分别代表City、Province、Friends、Followers、Gender 属性的值域见表1。当B=Ci,G时,则有:123456/1,3,2,3,6,1,2,3,6,4,5,4,5,6,2,3,5,6BBBBBBU SIM BSuSuSuSuSuSu block12341,3,2,3,6,4,5,5,6CBXXXX 表 1 不完备谣言信息表 Tabel 1 Incomplete rumor information table ID City Province Friends Followers Genderd 1 005 014 10,100 100,200 Women1 2 003*10,100 100,200 Women1 3*10,100 10,99 Women0 4 005*10,100 10,99 Men 1 5*0,9 10,99 Men 0 6 003 006 10,100 100,200*1 4 基于粗糙集的知识获取与决策 本文首先总结了粗糙集中用于不确定性度量的方式,以及它们在完备和不完备信息系统中的一致性表达,以此说明在完备信息系统中构造的知识约简与决策算法与在不完备信息系统中是一致的,在不完备信息系统中进行知识约简与决策更具有普适性和泛化性。在此基础上,总结了9种用于构造约简算法的重要性度量,并厘清了它们之间存在的约束关系,实质上只能构造4种约简算法。本文从熵度量的角度提出了最大相关最小冗余约简算法,用于解决谣言信息系统的冗余性;并基于极大相容块提出了用决策粗糙指标构造的决策树算法,用于不完备谣言信息系统中的决策。框架如图1所示。图 1 知识获取与决策框架 Figure 1 Knowledge acquisition and decision-making framework 4.1 不确定性度量 本文主要从不完备谣言信息系统的知识粗糙性方面刻画数据的不确定性,知识是利用属性分类的能力,随着属性的增多,对于论域中对象的分类就会越加精细。如例1,利用属性City对论域进行划分,只能划分为1,3,4,5和2,3,5,6;利用属性集B=Ci,G对论域进行划分,则能划分为1,3,2,3,6,4,5,5,6。随着属性的增多,论域中的对象划分的越来越细,知识的粗糙性也越来越低。在粗糙集理论中,度量不确定性有两个主要方向:粒度度量、熵度量。它们为从不同角度研究不确定性提供了相应的指标22,53。粒度度量指标主要有Liang熵及信息粒度,以代数论集合观点定义;熵度王标 等:基于粗糙集的不完备谣言信息系统的知识获取与决策 23 量指标主要有香农熵和粗糙熵,从信息论信息观点定义。本文总结了这四种度量指标及其变体在完备和不完备信息系统中的一致性表达。具体见表2,相关符号说明见下述证明。Liang等人22已经证明了香农熵、Liang熵、粗糙熵、信息粒度从完备信息系统到不完备信息系统的一致性拓展。本文推导证明了Liang熵中的条件信息熵在不完备信息系统中的一致性拓展,其他变体如互信息熵、联合熵、互信息粒度、联合信息粒度等不确定度量方式在完备和不完备信息系统中的一致性证明类似,这里不做一一证明。定 义定 义 2.设,SU A是 一 个 不 完 备 系 统,B DA,12/,.,BBBUU SIM BSuSuSu,12/,.,DDDUU SIM DSuSuSu。从Liang熵的角度,D相对于B的条件信息熵定义为:11/UBiDiiSuSuE D BUU (1)引理引理 132.设,SU A是一个完备信息系统,B DA,12/,.,mU IND BX XX,/U IND D 12,nY YY。D相对于B的条件信息熵退化为:11/ccmnjiijijYXXYE D BUU (2)其中,ciX和cjY分别是iX和jY的补集。证 明证 明:显 然 有ijiXYX,1)(nijijXYX,1()nijjXY。ijXY中的元素对应于iX中的12,.,ijzijijijuuu,1,2,.,im,1,2,.,jn。ijz代表集合ijXY中的元素数量。12,.,ibiiiiXu uu,ib代表 集 合iX中 的 元 素 数 量,并 且 有1nijijzb,1miibU。因此,1212.ijijziBijBijBijzjDijDijDijXSuSuSuYSuSuSu 1111111111111122111111111111111.ccBDBDzzBDYXXYXYXYUUUUSuSuSuSuUUUUSuSuUU 那么,11111212111111111111122111111111212111122111111111.11.111.nnccnBDjjjzzBDBDzzzzBDBDnnBDBDbbBDSuSuYXXYUUUUSuSuSuSuUUUUSuSuSuSuUUUUSuSuSuSuUUUUSuSuUU 所以,1122111111221111221111.11.1mmccmnBDjiijijbbBDBDbbbbBDBmDmUBiDiiSuSuYXXYUUUUSuSuSuSuUUUUSuSuSuSuUUUUSuSuUU 引理(1)说明完备信息系统的条件信息熵是不完备信息系统的一个特殊实例。或者说不完备信息系统的条件信息熵是对完备信息系统的一致性扩展。4.2 知识约简算法 4.2.1 属性约简及属性重要性属性约简及属性重要性 知识约简,即属性约简54,是粗糙集理论中的热点研究,旨在保持分类能力不变或者降低不多的情况下,删除其中冗余或者不重要的属性。决策信息系统经过属性约简,可以降低特征属性的维度55,提高基于属性的分类性能56,简化数据描述57和避免过拟合问题58。信息系统中属性约简的关键是如何构造系统中属性重要性的评价标准。24 Journal of Cyber Security 信息安全学报,2024 年 3 月,第 9 卷,第 2 期 给定决策信息系统且BC,一般的,属性aB的相对重要性定义为:,Sig a B DM BaDM B D 本文给出了新的定义:,Sig a B DM C DM BaD (3),M B D为B相对于D的重要性度量。这两种定义在筛选约简子集的核属性时效果一致,但是前一公式是从属性自身相对于候选属性子集的重要性考虑,取其中的最大值;后一公式是相对于全属性集的度量距离来衡量,取其中的最小值,在算法实现上更容易控制阈值来选择核属性的个数。当前,重要性度量主要从粒度度量和熵度量两个方面。从表2可以知道,M B D有9种基本度量方式,分别是:CH,MH,JH,CE,ME,JE,CG,MG,JG 其中CH,MH,JH是从熵度量角度,CE,ME,JE,CG,MG,JG是从粒度度量角度。跟决策有关的度量方式满足的约束条件有以下几种情况:(1)信息粒度和Liang熵的变体满足:/;11E D BCG B DE D BMG D BE DBJG DB (4)表 2 不同度量在完备和不完备信息系统中的表达 Tabel 2 Expression of different measures in both complete and incomplete information systems 度量类 度量方法 完备信息系统 不完备信息系统 信息熵 21logmiiiXXH BUU 211logUBiiSuH BUU 条件信息熵 211/logmnijijiijXYXYCH D BUX 211/logUDiBiBiiSuSuCH D BUSu 互信息熵 211;logmnijijijijXYXYMH D BUXYU 211;logUDiBiDiBiiSuSuMH D BUSuSuU 香农熵 联合熵 211logmnijijijXYXYJH DBUU 211logUDiBiiSuSuJH DBUU 信息熵 11miiiXXE BUU 111UPiiSuE BUU 条件信息熵 11/ccmnjiijijYXXYCE D BUU 11/UBiDiiSuSuCE D BUU 互信息熵 11;ccmnjiijijYXXYME D BUU 11;UBiDiiUSuUSuME D BUU Liang熵 联合熵 111mnijijijXYXYJE DBUU 111UBiDiiSuSuJE DBUU 粗糙熵 粗糙熵 211logmiriiXEBUX 2111logUrBiiEBUSu 知识粒度 2211miiG BXU 11UBiiSuG BUU 条件信息粒度 11/ccmnijijijXYXYCG D BUU 11/UDiBiDiiSuSuSuCG D BUU 互信息粒度 11;mnijijijXYXYMG D BUU 11;UDiBiBiDiiSuSuSuSuMG D BUU信息粒度 联合信息粒度 2211mnijijXYJG DBU 11UBiDiiSuSuJG DBUU 王标 等:基于粗糙集的不完备谣言信息系统的知识获取与决策 25 (2)香农熵及其变体满足:;/H D BH DH D B (5)(3)信息粒度及其变体满足:/JG DBG DCG D B (6)以属性重要性选取相应属性加入约简属性集合时,我们有以下推论:由式4可知,Liang熵变体与信息粒度变体是一致的,即CE与CG,ME与MG,JE与JG是一致的;由式5可知,香农互信息熵与条件信息熵是一致的,即MH与CH是一致的;由式6可知,条件信息粒度与联合信息粒度是一致的,即JG与CG(本文算法使用的CG指/CG B D)是一致的。最终我们得到的9种重要性度量实质上可归纳为MH,JH,MG,JG这4种。4.2.2 最大相关最小冗余度量最大相关最小冗余度量 上节提到了MH,JH,MG,JG这4种重要性度量方式,前两种从代数集合观出发,考虑的是某属性对论域中确定分类子集的影响;后两种从信息观出发,考虑的是某属性对于论域中不确定分类子集的影响,它比代数表示更加直观,能够导出高效的知识约简算法59。本文从熵度量角度提出了最大相关最小冗余度量指标。在图2中,D表示决策属性集,B表示约简属性集,ia表示候选属性,可以得到:;/;iiiH D B aMH D BaMH D a;/iiH D B aMH D BH D B a;/iH Da B ;iMH D BaMH D B 在属性选择上,;iMH D Ba(这种情况下B确定)。在图2中,代表新增属性ia对于决策贡献的信息量,而 代表了ia与约简属性集B的重叠信息,即对于决策冗余的信息量,有时还会成为噪音数据。我们希望选到 尽可能大 尽可能小的属性,因此我们提出了最大相关最小冗余重要性度量指标MCMR:,iiSig a B DH a (7)这里我们称 为候选属性ia的最大相关指标MaxC,为候选属性ia的最小冗余指标MinR,代表相应的权重值,且1。iH a为ia的信息熵,主要是为了避免倾向于选取取值较多的属性。图 2 熵度量维恩图 Figure 2 Entropy measure Venn diagram 4.2.3 基于属性重要性的约简算法基于属性重要性的约简算法 给定不完备谣言决策信息系统,U CD且BC,基于不同的属性重要性度量指标,构造不同的约简算法。基于MH,JH,MG,JG的知识约简算法,如算法1,其中重要性度量指标,M B D分别使用MH,JH,MG,JG进行度量。算法1.基于MH,JH,MG,JG的约简算法 输入:不完备谣言信息系统,U CD。输出:一个属性约简子集B 1:计算重要性度量,M C D;2:置初始属性约简子集B 。3:WHILEM C,DM B,D q-DO 4:min,iiiaC BaM C DM BaD 5:iBBa 6:END WHILE 基于最大相关MaxC、最小冗余MinR 以及最大相关最小冗余指标MCMR的属性约简算法,如算法2所示,其中属性重要性,Sig a B D分别使用;/iH D aB,;iH D B a以及 iH a进行度量。其中算法1以及算法2中基于MaxC、MinR的约简算法代表了6类知识约简算法,前4种是前文讲到的4种不同度量方式构造的算法,是常用的约简算法;后2种是基于不确定度量方式总结的2类算法,分别代表了两种方向或者思考,一种基于相关性,一种基于冗余性;而基于MCMR的约简算法是本文提出的算法。26 Journal of Cyber Security 信息安全学报,2024 年 3 月,第 9 卷,第 2 期 算法2.基于MaxC,MinR,MCMR的约简算法 输入:不完备谣言信息系统,U CD。输出:一个属性约简子集B 1:计算互信息,MH C D;2:置初始属性约简子集B 。3:WHILE;MH C DMH B DDo 4:max,iiiaC BaSig a B D 5:iBBa 6:END WHILE 如例1,假设这里以算法1中的基于MH构建的约简算法来选择约简属性集。以属性Fo划分的等价和相容关系类分别为:12/()1,2,6,2,3,5U IND FoXX 123456/1,2,6,1,2,63,4,5,3,4,5,3,4,51,2,6FoFoFoFoFoFoU SIMSuSuSuSuFoSuSu，以决策属性d划分的等价和相容关系类分别为:12/()1,2,4,6,3,5U IND dYY 1234563/1,2,4,6,1,2,4,6,1,2,4,6,5,3,51,2,4,6dddddddU SIMSuSuSuSuSuSu，则Fod划分的等价和相容关系类为:/()1,2,6,4,3,5U IND Fod 234561/1,2,6,1,2,6,3,5,4,3,5,1,2,6FodFodFodFodFodFodU SIMSuSuSuSuSuFudSo计算得到互信息熵为:2112;log11log 30.45923mnijijijijXYXYMH d FoUXYU 112121;log11log 30.45923UiBiiiBiddSuSuMH d FoUSuSuU 可以看到,两者结果相同,也间接证明了4.1节中的香农互信息熵在不完备信息系统中的表达是完备信息系统的一致性拓展。同理分别计算出以属性Ci,P,Fr,G划分论域时的互信息熵,选取其中互信息熵最大的作为核属性加入到约简子B中。并按照算法1得到最终的属性约简子集B。4.3 不完备决策树算法 对于一个非完备的信息系统来说,由于完备系统与非完备系统在拓扑结构上存在本质差异51,60-61,所以在非完备系统中,香农熵定义所需要的离散型概率分布也是不可能得到的,只能通过相容关系或者极大相容块进行拓展。如例1中,在属性Ci,P,G等列的属性值存在缺失,只能采取传统的数值填补或者删除,不能直接用传统意义的完备信息系统的方法来计算各类熵值。因此,本文基于极大相容块提出决策粗糙指数,并构建了决策树模型用于不完备系统中的谣言检测。定义定义362.设U是一个论域,B是一个条件属性集合,BC,12/,.,mU BXXX,D为决策属性,其中12/,.,tU BD DD为决策概念集,则决策概念集的粗糙熵为 11logmtijiBijiXDXE DUX (8)由2.2节可知 a PSIM PSIMa,并且在不完备信息系统中,相似关系也是相容关系。基于极大相容块,将定义3扩展到不完备信息系统。算法3.不完备决策树算法 输入:不完备谣言信息系统,U CD f,阈值0 输出:一个决策树T 1:计算属性约简集合B;MCMR算法2 2:,U CD fU BD f 3:FORiaCDO miniiaCaargD a 决策粗糙指数 CCa 王标 等:基于粗糙集的不完备谣言信息系统的知识获取与决策 27 4:IF D a DO 5:block12,.,mCaXXX 极大相容块类 6:FOR blockjXCaDO ,jU CD fXCD f 7:block12,.,.,jnCDD DDD 8:IF block=1CDTHEN ,TLabelf U D 9:ELSE IF C THEN ,maxjTjf U DLabelargD 10:ELSE RETURN Step3 END IF END FOR END IF END FOR 11:RETURN T block12block12block12,.,.,.,mtnCBXXXCDD DDCBDY YY 其中jY为属性BD所决定的极大相容块。则有:11logmnjiBijiYXE DUX (9)属性B在U上导出的极大相容类 blockCB的香农信息熵为 21logmiiiXXH BUU (10)决策粗糙熵更倾向于区分属性的分类能力,决策粗糙熵越小,分类粒度越细,但分类效果并不一定好。而条件熵(/)H D B能够衡量决策属性在条件属性集B下的信息熵,条件熵越小,说明条件属性集B消除的不确定性越大。结合决策粗糙熵以及条件熵的优势,我们提出了决策粗糙指数()D B。()(/)()()BE DH D BD BH B (11),代表相应的权重值,且1。决策粗糙指数 D B越小,选用属性集B用于决策的分类效果越好。基于决策粗糙指数 D B的不完备决策树算法,如算法3所示。5 实验结果分析 本文对4.2.3节和4.3节所提到的算法进行了实验论证。5.1 相关数据集 本文使用了4个UCI机器学习数据集用于4.2.3节中MCMR指标与其他重要性度量的对比实验,这4个数据集分别是Car、Abalone、Adult以及Bank,具体实验在5.2节。本文从Weibo数据集63-64中提取了Post、Structure、User、Union等4个数据集。在5.3节中检验了本文所提约简算法在不同模型上的分类效果以及约简效果,这些模型有最大熵、决策树、提升算法+决策树以及随机森林等,它们的核心都使用了不同的不确定性度量方式。在5.4节中对比了本