粗糙集理论在决策级数据融合的应用研究
|
摘要
数据融合技术已经成为当今信息产业的亮点和热点,其应用已经涵盖了军事和民事等诸多领域。由于多种原因都会造成数据在传输过程的遗失,而最小属性约简问题已被证明是NP难题,所以寻求高效、实用的数据补齐算法和属性约简算法是众多研究者一直致力解决的问题。基于粗糙集理论在处理不确定问题时较之模糊集、D-S证据理论等其他工具的独特优势,本文采用粗糙集理论研究决策级数据融合的数据补齐和属性约简问题。
首先,本文深入分析了一个经典数据补齐算法及其改进算法,发现了该算法及其改进算法存在数据补齐资格不可控、适用范围受限等缺陷。通过引入相容阈值和标准化距离函数,本文提出了一个基于量化容差关系的改进算法。新算法改进了数据之间相似性的刻画手段,避免了数据之间相似性的片面刻画,降低了时空开销,实现了补齐资格的可控性,扩大了原算法的适用范围。其次,通过对一个属性约简算法的分析验证,本文发现了该算法存在着在核基为零条件下无法进行有效约简的缺陷,进而剖析了该缺陷存在的根源,指出了该缺陷存在的普遍性,并针对这个缺陷提出了真核、伪核的概念和一系列相关定理,然后基于这些概念和定理给出了改进算法。新算法克服了原算法的缺陷,提高了适用性。
决策级数据融合的数据补齐和属性约简算法直接关系到最终决策质量,本文提出的两个改进算法可望比原算法有更好的表现。
Nowadays data fusion technology has become a bright spot or a hot spot in IT and its application includes many fields, such as military and civil ones. For data will be missing by all kinds of reasons in the transiting procedure and minimum attribute reduction problem has been proved a NP-hard one, finding a effective and practical data complement and attribute reduction algorithm always are tempting puzzles to many researchers. Though we have some comparatively mellow algorithms to resolve the two problems, they all have some flaws. Because of the rough set theory have some particular advantages than other tools, such as vagueness set and D-S evidence theory, so this thesis selects it to study the decision level's data fusion.
Firstly, this thesis deeply analyzes a classical data complement algorithm and it's improved algorithms, finds many flaws of them, which includes the competency of the filling data can't be controlled, the application scope of the algorithms is restricted, etc. This thesis, based on valued tolerance relation, presents an improved algorithm by introducing a tolerance threshold and a normalized distance function to give a further improvement. The new algorithm improves the depicting approach of two piece of data's comparability, and avoids the unilateral description of two piece of data's comparability. It reduces the cost of time and space computation, realizes the control ability of filling qualification, and enlarges the application scope of the old algorithms. Secondly, by validating and analyzing, this thesis finds a flaw in an attribute reduction algorithm, which cause the algorithm can't effectively deal with the attribute reduction when the cardinal number of core equals zero. This thesis not only analyzes the source of the flaw but also points out that the flaw widely exists in many attribute reduction algorithm. Aimming at the flaw this thesis introduces hypo-core and real-core concepts and a series of their concerning theorems. Based on these concepts and theorems this thesis improved the attribute reduction algorithm. The new algorithm amends the flaw in the original, enlarges the application scope.
For the quality of decision rules depends on the data complement and attribute reduction algorithms of the decision level of data fusion, the two improved algorithms hopely have better performances than the the originals.
首先,本文深入分析了一个经典数据补齐算法及其改进算法,发现了该算法及其改进算法存在数据补齐资格不可控、适用范围受限等缺陷。通过引入相容阈值和标准化距离函数,本文提出了一个基于量化容差关系的改进算法。新算法改进了数据之间相似性的刻画手段,避免了数据之间相似性的片面刻画,降低了时空开销,实现了补齐资格的可控性,扩大了原算法的适用范围。其次,通过对一个属性约简算法的分析验证,本文发现了该算法存在着在核基为零条件下无法进行有效约简的缺陷,进而剖析了该缺陷存在的根源,指出了该缺陷存在的普遍性,并针对这个缺陷提出了真核、伪核的概念和一系列相关定理,然后基于这些概念和定理给出了改进算法。新算法克服了原算法的缺陷,提高了适用性。
决策级数据融合的数据补齐和属性约简算法直接关系到最终决策质量,本文提出的两个改进算法可望比原算法有更好的表现。
Nowadays data fusion technology has become a bright spot or a hot spot in IT and its application includes many fields, such as military and civil ones. For data will be missing by all kinds of reasons in the transiting procedure and minimum attribute reduction problem has been proved a NP-hard one, finding a effective and practical data complement and attribute reduction algorithm always are tempting puzzles to many researchers. Though we have some comparatively mellow algorithms to resolve the two problems, they all have some flaws. Because of the rough set theory have some particular advantages than other tools, such as vagueness set and D-S evidence theory, so this thesis selects it to study the decision level's data fusion.
Firstly, this thesis deeply analyzes a classical data complement algorithm and it's improved algorithms, finds many flaws of them, which includes the competency of the filling data can't be controlled, the application scope of the algorithms is restricted, etc. This thesis, based on valued tolerance relation, presents an improved algorithm by introducing a tolerance threshold and a normalized distance function to give a further improvement. The new algorithm improves the depicting approach of two piece of data's comparability, and avoids the unilateral description of two piece of data's comparability. It reduces the cost of time and space computation, realizes the control ability of filling qualification, and enlarges the application scope of the old algorithms. Secondly, by validating and analyzing, this thesis finds a flaw in an attribute reduction algorithm, which cause the algorithm can't effectively deal with the attribute reduction when the cardinal number of core equals zero. This thesis not only analyzes the source of the flaw but also points out that the flaw widely exists in many attribute reduction algorithm. Aimming at the flaw this thesis introduces hypo-core and real-core concepts and a series of their concerning theorems. Based on these concepts and theorems this thesis improved the attribute reduction algorithm. The new algorithm amends the flaw in the original, enlarges the application scope.
For the quality of decision rules depends on the data complement and attribute reduction algorithms of the decision level of data fusion, the two improved algorithms hopely have better performances than the the originals.
引文
[1]王欣.多传感器数据融合问题的研究.吉林大学博士学位论文.2006:3-8,13-14,18-21页
[2]孟宪尧.数据融合技术与船舶自动化.大连:大连海事大学出版社,2003:4页
[3]黄鹍,陈森发,周振国等.基于粗集和证据理论的多源信息融合方法.信息与控制.2004,8,33(4):422-423页
[4]J.-M.Wei et al..Rough set based approach for inducing decision trees knowl.Based Syst.2006,10(1):3P
[5]张启忠,罗志增.粗糙集在信息融合中的应用.机电工程.2007,18(5):29页
[6]Guan J W,Bell D A.Approximate Reasoning and Evidence Theory.Information Science.1997,19(6):8-9P
[7]吴陈,杨习贝,傅凡等.基于扩展粗糙集模型的集值不完备信息系统决策研究.计算机工程与应用.2005,15:57页
[8]王亚英,张春慨,邵惠鹤.启发式知识约简算法的研究与应用.控制与决策.2007,11,16(6):886页
[9]Zdzislaw Pawlak,Andrzej Skowron.Rudiments of Rough Sets.Information Sciences.2007,3(27):3 P
[10]Yingjie Yang,Robert John.Roughness Bounds in Rough Set Operation.Information Sciences.2006,176:3256 P
[11]王国胤.Rough集理论在不完备信息系统中的扩充.计算机研究与发展.2002:10,39(10):1238-1243页
[12]王国胤.Rough集理论与知识获取.西安:西安交通大学出版社,2001:92-99,143-146页
[13]苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展.1999,6,36(6):681页
[14]Wong.S.K.M,Ziarko W.On Optimal Decision Rules.Bulletin of Polish Academy of Sciences.1985,33:693-696 P
[15]唐彬,李龙澍.关于基于分明矩阵的属性约简算法的探讨.计算机工程与应用.2004,14:184页
[16]E.Waltz,J.Llinas.Multi-sensor Data Fusion.Artech House:Norwood Massachusets,1990:18P
[17]White F E.Data fusion lexicon.Joint directors of laboratories.Technical Panel for C~3,Data fusion sub-panel,naval ocean systems center,San Diego,CA,USA,1987:1380P
[18]White F E.A model for data fusion.In:Proc.1st National Symposium on Sensor Fusion.Orlando,FL,vol.2,Apr.,1988:5-8P
[19]Steinberg A N,Bowman C L,White F E.Revisions to the JDL Data Fusion Model.In Sensor Fusion:Architectures,Algorithms,and Applications,Proceedings of the SPIE.Orlando:Florida,1999:430-441P
[20]D.L.Hall,J.Llinas.An Introduction to Multisensor Data Fusion.the Proceedings of IEEE.1997,1,5(1):6-23 P
[21]L.Wald.An European Proposal for terms of reference in data fusion.International Archives of Photogrammetry and Remote Sensing.1998,17(7):651-654 P
[22]谢平.故障诊断中信息熵特征提取及融合方法研究.燕山大学博士学位论文.2006:10页
[23]李静,贾利民.数据融合综述.交通标准化.2007,9(169):192-194页
[24]杨华,林卉.数据融合的研究综述.矿山测量.2005,9(3):24页
[25]牟聪.多传感器数据融合系统中数据预处理的研究.西北工业大学硕士学位论文.2006:6页
[26]王刚.数据融合若干算法的研究.西安理工大学硕士学位论文.2006:4-6页
[27]管天云.多传感器信息融合研究.浙江大学博士学位论文.1998:14页
[28]郭璘.基于信息融合的交通信息采集研究.中国科技大学博士学位论文.2007:31页
[29]张文修,吴伟志,梁吉业等.粗糙集理论与方法.北京:科学出版社,2006:1-25页
[30]Z.Pawlak.Rough sets.International Journal of Computer and Information Sciences.1982,11:341-356 P
[31]Kryszkiewicz M.Rough set approach to incomplete information systems.Information Sciences.1998,112:39-49 P
[32]刘富春.不完备信息系统中粗糙集理论的扩充.计算机与现代化.2005,118(6):1-6页
[33]Stefanowski J,Tsoukias A.On the Extension of Rough Sets under Incomplete Information.In:Proceedings of the 7th International Workshop on New Directions in Rough Sets,Data Mining,and Granular-Soft Computing.Berlin:Springer-Verlag,1999:73-81 P
[34]朱小飞,卓丽霞.一种基于量化容差关系的不完备数据分析方法.重庆工学院学报.2005,19(5):23-25页
[35]张在美.一种基于粗糙集的不完备信息处理方法研究.湖南大学硕士学位论文.2007:32-33页
[36]张振华,刘文奇.一种基于粗糙集理论不完备数据的改进算法.计算机工程与科学.2002,24(2):41-42,67页
[37]张亮,吴根秀.粗糙集在不完备信息系统中的一种扩充方法.计算机与现代化.2005,117(5):18-20页
[38]徐泽水,达庆利.多属性决策的组合赋权方法研究.中国管理科学.2002,10(2):84-86页
[39]Yongguang Bao,Xiaoyong Du,Naohiro Ishii.Improving Performance of the K-Nearest Neighbor Classifier by Tolerant Rough Sets.IEEE.2001:167-171 P
[40]Daijin Kim.Data classification based on tolerant rough set.Pattern Recognition.2001,34:1613-1624 P
[41]李然.连续值域信息系统的规则提取与知识约简.模糊系统与数学.2003,17(4):40-47页
[42]梁吉业,曲开社,徐宗本.信息系统的属性约简.系统工程理论与实践. 2001,12(12):76-80页
[43]曾黄麟.粗集理论及其应用—关于数据推理的新方法.重庆:重庆大学出版社,1996:32-33页
[44]Feng-Hsu Wang.On acquiring classification knowledge from noisy data based on rough set.Expert Systems with Application.2005,29:49-64 P
[45]Tzung-PeiHong,Li-Huei Tseng,Shyue-Liang Wang.Learning rules from incomplete training examples by rough sets.Expert Systems with Application.2002,22:285-293 P
[46]H.Huang,G.Y.Wang,Y.Wu.A direct approach for incomplete information systems.Mining and Knowledge Discovery:Theory,Tools,and Technology Ⅵ,edited by Belur V.Dasarathy,Proceedings of SPIE Vol.5433(SPIE,Bellingham,WA,2004):114-121P
[47]Marzena Kryszkiewicz.Rules in incomplete information systems.Information Science.1999,113:271-292P
[48]William Zhu.Topological approaches to covering rough sets.Information Sciences.2007,177:1499-1508P
[2]孟宪尧.数据融合技术与船舶自动化.大连:大连海事大学出版社,2003:4页
[3]黄鹍,陈森发,周振国等.基于粗集和证据理论的多源信息融合方法.信息与控制.2004,8,33(4):422-423页
[4]J.-M.Wei et al..Rough set based approach for inducing decision trees knowl.Based Syst.2006,10(1):3P
[5]张启忠,罗志增.粗糙集在信息融合中的应用.机电工程.2007,18(5):29页
[6]Guan J W,Bell D A.Approximate Reasoning and Evidence Theory.Information Science.1997,19(6):8-9P
[7]吴陈,杨习贝,傅凡等.基于扩展粗糙集模型的集值不完备信息系统决策研究.计算机工程与应用.2005,15:57页
[8]王亚英,张春慨,邵惠鹤.启发式知识约简算法的研究与应用.控制与决策.2007,11,16(6):886页
[9]Zdzislaw Pawlak,Andrzej Skowron.Rudiments of Rough Sets.Information Sciences.2007,3(27):3 P
[10]Yingjie Yang,Robert John.Roughness Bounds in Rough Set Operation.Information Sciences.2006,176:3256 P
[11]王国胤.Rough集理论在不完备信息系统中的扩充.计算机研究与发展.2002:10,39(10):1238-1243页
[12]王国胤.Rough集理论与知识获取.西安:西安交通大学出版社,2001:92-99,143-146页
[13]苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展.1999,6,36(6):681页
[14]Wong.S.K.M,Ziarko W.On Optimal Decision Rules.Bulletin of Polish Academy of Sciences.1985,33:693-696 P
[15]唐彬,李龙澍.关于基于分明矩阵的属性约简算法的探讨.计算机工程与应用.2004,14:184页
[16]E.Waltz,J.Llinas.Multi-sensor Data Fusion.Artech House:Norwood Massachusets,1990:18P
[17]White F E.Data fusion lexicon.Joint directors of laboratories.Technical Panel for C~3,Data fusion sub-panel,naval ocean systems center,San Diego,CA,USA,1987:1380P
[18]White F E.A model for data fusion.In:Proc.1st National Symposium on Sensor Fusion.Orlando,FL,vol.2,Apr.,1988:5-8P
[19]Steinberg A N,Bowman C L,White F E.Revisions to the JDL Data Fusion Model.In Sensor Fusion:Architectures,Algorithms,and Applications,Proceedings of the SPIE.Orlando:Florida,1999:430-441P
[20]D.L.Hall,J.Llinas.An Introduction to Multisensor Data Fusion.the Proceedings of IEEE.1997,1,5(1):6-23 P
[21]L.Wald.An European Proposal for terms of reference in data fusion.International Archives of Photogrammetry and Remote Sensing.1998,17(7):651-654 P
[22]谢平.故障诊断中信息熵特征提取及融合方法研究.燕山大学博士学位论文.2006:10页
[23]李静,贾利民.数据融合综述.交通标准化.2007,9(169):192-194页
[24]杨华,林卉.数据融合的研究综述.矿山测量.2005,9(3):24页
[25]牟聪.多传感器数据融合系统中数据预处理的研究.西北工业大学硕士学位论文.2006:6页
[26]王刚.数据融合若干算法的研究.西安理工大学硕士学位论文.2006:4-6页
[27]管天云.多传感器信息融合研究.浙江大学博士学位论文.1998:14页
[28]郭璘.基于信息融合的交通信息采集研究.中国科技大学博士学位论文.2007:31页
[29]张文修,吴伟志,梁吉业等.粗糙集理论与方法.北京:科学出版社,2006:1-25页
[30]Z.Pawlak.Rough sets.International Journal of Computer and Information Sciences.1982,11:341-356 P
[31]Kryszkiewicz M.Rough set approach to incomplete information systems.Information Sciences.1998,112:39-49 P
[32]刘富春.不完备信息系统中粗糙集理论的扩充.计算机与现代化.2005,118(6):1-6页
[33]Stefanowski J,Tsoukias A.On the Extension of Rough Sets under Incomplete Information.In:Proceedings of the 7th International Workshop on New Directions in Rough Sets,Data Mining,and Granular-Soft Computing.Berlin:Springer-Verlag,1999:73-81 P
[34]朱小飞,卓丽霞.一种基于量化容差关系的不完备数据分析方法.重庆工学院学报.2005,19(5):23-25页
[35]张在美.一种基于粗糙集的不完备信息处理方法研究.湖南大学硕士学位论文.2007:32-33页
[36]张振华,刘文奇.一种基于粗糙集理论不完备数据的改进算法.计算机工程与科学.2002,24(2):41-42,67页
[37]张亮,吴根秀.粗糙集在不完备信息系统中的一种扩充方法.计算机与现代化.2005,117(5):18-20页
[38]徐泽水,达庆利.多属性决策的组合赋权方法研究.中国管理科学.2002,10(2):84-86页
[39]Yongguang Bao,Xiaoyong Du,Naohiro Ishii.Improving Performance of the K-Nearest Neighbor Classifier by Tolerant Rough Sets.IEEE.2001:167-171 P
[40]Daijin Kim.Data classification based on tolerant rough set.Pattern Recognition.2001,34:1613-1624 P
[41]李然.连续值域信息系统的规则提取与知识约简.模糊系统与数学.2003,17(4):40-47页
[42]梁吉业,曲开社,徐宗本.信息系统的属性约简.系统工程理论与实践. 2001,12(12):76-80页
[43]曾黄麟.粗集理论及其应用—关于数据推理的新方法.重庆:重庆大学出版社,1996:32-33页
[44]Feng-Hsu Wang.On acquiring classification knowledge from noisy data based on rough set.Expert Systems with Application.2005,29:49-64 P
[45]Tzung-PeiHong,Li-Huei Tseng,Shyue-Liang Wang.Learning rules from incomplete training examples by rough sets.Expert Systems with Application.2002,22:285-293 P
[46]H.Huang,G.Y.Wang,Y.Wu.A direct approach for incomplete information systems.Mining and Knowledge Discovery:Theory,Tools,and Technology Ⅵ,edited by Belur V.Dasarathy,Proceedings of SPIE Vol.5433(SPIE,Bellingham,WA,2004):114-121P
[47]Marzena Kryszkiewicz.Rules in incomplete information systems.Information Science.1999,113:271-292P
[48]William Zhu.Topological approaches to covering rough sets.Information Sciences.2007,177:1499-1508P