代价约束下的属性选择问题

《代价约束下的属性选择问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、理学硕士学位论文代价约束下的属性选择问题李静宽闽南师范大学二○一五年六月学校代码：10402学号：2012062014分类号：密级：理学硕士学位论文代价约束下的属性选择问题学位申请人:李静宽指导教师:闵帆教授、赵红副教授学位类别:理学硕士学科专业:应用数学授予单位:闽南师范大学答辩日期:二○一五年六月CODE：10402NO.：2012062014U.D.C.：ClassifiedIndex：ADissertationfortheMasterDegreeofScienceFeatureSelectionwi

2、thCostConstraintCandidate：JingkuanLiSupervisor：Prof.FanMin,A.P.HongZhaoSpecialty：AppliedMathematicsAcademicDegreeAppliedfor：MasterofScienceUniversity：MinnanNormalUniversityDateofOralExamination：June,2015闽南师范大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。

3、除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权闽南师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本

4、学位论文属于1、保密□，在______年解密后适用本授权书。2、不保密□。（请在以上相应方框内打“√”）作者签名：日期：年月日导师签名：日期：年月摘要摘要实际生活中存在各种代价，包括测试代价、误分类代价、计算代价和延迟代价等。测试数据需要付出一定代价，我们称之为测试代价。这些代价包括金钱、时间和其它各种资源。当我们对实例做出错误分类的时候，同样也需要付出代价。这些由错误分类造成的代价，我们称之为误分类代价。等待而没有做有意义的事情所浪费的时间，我们称为延迟代价。代价敏感学习问题逐渐成为研究的热点。在数据挖掘

5、和机器学习中，约束满足问题是一类常见而有意义的问题。在各个方面，如金融经济、组合数学，计算复杂性理论、密码安全学和应用数学等领域中约束满足问题的变类得到广泛的应用。正是因为现实世界中各种代价的存在，而很多时候我们的资源是有限的，我们所能够承担的代价并不能满足完成所有的测试或者其他代价的要求。如何利用有限的资源来尽量的完成测试需求或者其他方面需求的问题，正受到越来越多的研究人员的关注和研究分析。目前，已有不少研究者做了部分约束满足方面的研究工作，通过定义不同的约束条件来研究代价敏感约束满足问题。代价敏感学习是

6、数据挖掘的研究热点，约束满足问题是人工智能和机器学习领域著名的问题之一。因此本文利用粗糙集知识研究这两个热点问题，提出了代价约束下的属性选择问题。研究目标是处理不同类型数据模型的代价敏感约束满足问题以及获得不同的约束条件下的高效解决算法。本文主要分为两大部分。第一部分详细研究了基于代价敏感粗糙集理论的名词性数据的属性选择问题。首先，我们提出了在时间代价约束下的随机算法来处理名词性数据的属性选择问题。时间代价约束是算法设计的一个主要目标，主要是为了在尽可能短的时间内获得良好的实验结果。其次，为了进一步降低算法

7、的运行时间，我们在快速随机算法的基础上提出了重启策略优化的随机算法来解决最小测试代价属性选择问题。实验结果表明重启策略优化的随机算法在单位时间内能够获得最优的属性子集。重启策略优化的-I-闽南师范大学理学硕士学位论文随机算法在处理大规模数据集有着突出的表现，不足之处就是算法在固定实验次数的情况下，实验结果差于启发式算法。在处理名词性数据的属性选择问题的最后一部分，我们提出了代价约束下的属性选择问题，首次考虑了测试代价和误分类代价对于约束问题的影响。基于测试代价和误分类代价对代价约束下属性选择问题的影响，我们

8、提出了一类新的启发式算法。实验结果表明，我们设计的算法能够在代价约束下获得不错的效果。第二部分详细研究了同时考虑测试代价和误分类代价这两类代价的数值型数据的代价约束属性选择问题。在处理数值型数据的问题上我们采用了邻域粗糙集的相关知识。通过计算对象的不一致对象个数，我们设计了一类新的启发式算法来解决数值型数据的代价约束属性选择问题。实验结果表明，我们设计的启发式算法能够在算法效率和效果方面获得不错的结果。关键词：代