基于局部搜索的软集最小正规参数约简方法
|
摘要
软集在解决不确定性问题的决策分析过程中,参数约简是关键和棘手的问题.软集正规参数约减方法采用全局搜索方式求解最大的参数约简集,存在候选属性集计算量大和冗余度高的问题,针对这一问题提出一种基于局部搜索的软集最小参数约简方法.给出频度和等价类、最小生成元的概念,在此基础上给出分层局部搜索的软集最小参数约简算法,减少搜索空间和加速逐层约简的过程,最后求出软集最小正规约简的最优解.通过分析和实例证明该软集参数约简方法,大幅度减小了候选参数约简集数量,降低运算的复杂度.
In the process of decision-making analysis for solving uncertainties,parameter reduction is a key and difficult problem.The normal parameter reduction method of soft set solves the maximum parameter reduction set by global search,which has the problems of large computational complexity and high redundancy of candidate attribute set.To solve this problem,a local search based minimum parameter reduction method of soft set is proposed.The concepts of frequency,equivalent class and minimum generator are given.On this basis,a hierarchical local search algorithm for minimal parameter reduction of soft sets is presented,which reduces the search space and speeds up the process of layer-by-layer reduction.Finally,the optimal solution of minimal normal reduction of soft sets is obtained.Through analysis and examples,it is proved that the soft set parameter reduction method greatly reduces the number of candidate parameter reduction sets and reduces the complexity of operation.
In the process of decision-making analysis for solving uncertainties,parameter reduction is a key and difficult problem.The normal parameter reduction method of soft set solves the maximum parameter reduction set by global search,which has the problems of large computational complexity and high redundancy of candidate attribute set.To solve this problem,a local search based minimum parameter reduction method of soft set is proposed.The concepts of frequency,equivalent class and minimum generator are given.On this basis,a hierarchical local search algorithm for minimal parameter reduction of soft sets is presented,which reduces the search space and speeds up the process of layer-by-layer reduction.Finally,the optimal solution of minimal normal reduction of soft sets is obtained.Through analysis and examples,it is proved that the soft set parameter reduction method greatly reduces the number of candidate parameter reduction sets and reduces the complexity of operation.
引文
[1]Plackett R L.Probability theory[J].Historia Mathematica,1976,3(2):233-234.
[2]Zadeh,L.A.Fuzzy sets[J].Information and Control,1965,8.3:338-353.
[3]Pawlak Z.Rough sets[J].International Journal of Computer&Information Sciences,1982,11(5):341-356.
[4]Molodtsov D.Soft set theory-First results[J].Computers&Mathematics with Applications,1999,37(4-5):19-31.
[5]Molodtsov D.The theory of soft sets[M].Moscow:URSS Publishers,2004.
[6]耿生玲.软集理论及其在知识获取中的应用研究[D].西安:陕西师范大学,2013.
[7]侯文艳.软集在关联规则挖掘中的应用[D].成都:西南交通大学,2017.
[8]冯锋,张珑耀,张青.基于软集上逻辑公式的极大关联规则描述与挖掘方法[J].吉林大学学报(理学版),2018,232(04):145-152.
[9]刘志才.模糊软集及其在不确定性决策中的应用研究[D].成都:西南交通大学,2018.
[10]耿生玲,李永明,刘震.不完备决策软集与优势可信规则获取[J].计算机工程与科学,2013,35(12):153-160.
[11]耿生玲,李永明,冯峰.软集决策信息系统的属性约简[J].小型微型计算机系统,2011,32(4).
[12]Maji P K,Roy A R,Biswas R.An application of soft sets in a decision making problem[J].Computers&Mathematics with Applications,2002,44(8-9):1077-1083.
[13]Chen D,Tsang E C C,Yeung D S,et al.The parameterization reduction of soft sets and its applications[J].Computers&Mathematics with Applications,2005,49(5-6):757-763.
[14]邹艳,肖智,龚科.基于最优选择对象不变的软集合参数约简[J].系统工程学报,2009,24(4):457-461.
[15]Kong Z,Gao L,Wang L,et al.The normal parameter reduction of soft sets and its algorithm[J].Computers&Mathematics with Applications,2008,56(12):3029-3037.
[16]Ma X,Sulaiman N,Qin H,et al.A new efficient normal parameter reduction algorithm of soft sets[J].Computers&Mathematics with Applications,2011,62(2):588-598.
[17]Danjuma S,Ismail M A,Herawan T.An Alternative Approach to Normal Parameter Reduction Algorithm for Soft Set Theory[J].IEEEAccess,2017,PP(99):1-1.
[18]Han B,Li Y,Geng S.0-1Linear programming methods for optimal normal and pseudo parameter reductions of soft sets[J].Applied Soft Computing,2016,54.
[19]Pei D,Miao D.From soft sets to information systems[C].IEEE International Conference on Granular Computing.IEEE,2005.
[20]Sun Q M,Zhang Z L,Liu J.Soft sets and soft modules[C].International Conference on Rough Sets&Knowledge Technology.Springer-Verlag,2008.
[2]Zadeh,L.A.Fuzzy sets[J].Information and Control,1965,8.3:338-353.
[3]Pawlak Z.Rough sets[J].International Journal of Computer&Information Sciences,1982,11(5):341-356.
[4]Molodtsov D.Soft set theory-First results[J].Computers&Mathematics with Applications,1999,37(4-5):19-31.
[5]Molodtsov D.The theory of soft sets[M].Moscow:URSS Publishers,2004.
[6]耿生玲.软集理论及其在知识获取中的应用研究[D].西安:陕西师范大学,2013.
[7]侯文艳.软集在关联规则挖掘中的应用[D].成都:西南交通大学,2017.
[8]冯锋,张珑耀,张青.基于软集上逻辑公式的极大关联规则描述与挖掘方法[J].吉林大学学报(理学版),2018,232(04):145-152.
[9]刘志才.模糊软集及其在不确定性决策中的应用研究[D].成都:西南交通大学,2018.
[10]耿生玲,李永明,刘震.不完备决策软集与优势可信规则获取[J].计算机工程与科学,2013,35(12):153-160.
[11]耿生玲,李永明,冯峰.软集决策信息系统的属性约简[J].小型微型计算机系统,2011,32(4).
[12]Maji P K,Roy A R,Biswas R.An application of soft sets in a decision making problem[J].Computers&Mathematics with Applications,2002,44(8-9):1077-1083.
[13]Chen D,Tsang E C C,Yeung D S,et al.The parameterization reduction of soft sets and its applications[J].Computers&Mathematics with Applications,2005,49(5-6):757-763.
[14]邹艳,肖智,龚科.基于最优选择对象不变的软集合参数约简[J].系统工程学报,2009,24(4):457-461.
[15]Kong Z,Gao L,Wang L,et al.The normal parameter reduction of soft sets and its algorithm[J].Computers&Mathematics with Applications,2008,56(12):3029-3037.
[16]Ma X,Sulaiman N,Qin H,et al.A new efficient normal parameter reduction algorithm of soft sets[J].Computers&Mathematics with Applications,2011,62(2):588-598.
[17]Danjuma S,Ismail M A,Herawan T.An Alternative Approach to Normal Parameter Reduction Algorithm for Soft Set Theory[J].IEEEAccess,2017,PP(99):1-1.
[18]Han B,Li Y,Geng S.0-1Linear programming methods for optimal normal and pseudo parameter reductions of soft sets[J].Applied Soft Computing,2016,54.
[19]Pei D,Miao D.From soft sets to information systems[C].IEEE International Conference on Granular Computing.IEEE,2005.
[20]Sun Q M,Zhang Z L,Liu J.Soft sets and soft modules[C].International Conference on Rough Sets&Knowledge Technology.Springer-Verlag,2008.