代价敏感属性约简的归并算法研究

《代价敏感属性约简的归并算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、困书分类号ＴＰ３学校代码：１０６１５：朵喪／５袜乐费ＩＩ攀位觀±擎値德文论文题目代价敏感属性约简的归并算法研究硕±生姓名张爱婷第一导师姓名晚沒滨第二导师姓名圏ｊｉ专业学位类型工提专＃當化工程领域名称软件工程研究方向数据挖掘二〇—六年六月西南石油大学研究生学位论文知识产权声巧书及学位论文版权使用授权书，目Ｐ工本人完全了解学校有关保护知识产权的规定；研究生在校攻读学位期间论文作的知识产权单位属于西南石油大学。学校有权保留并向国家有关部口或机构送交论文的复印件和电子版レッ将本学位论文的全部或部分。

2、本人允许论文被查阅和借阅。学校可，可皆内容编入有关数据库进行检索、采用影印、缩印或扫描等复制手段保存和汇编本学一位论文，，律注明作者单。同时本人保证毕业后结合学位论文研究课题再撰写的文章位为西南石油大学。本学位论文属于１、保密（），在年解密后适用本授权书。２、不保密）（＼／＂＂（请在Ｗ上相应括号内打Ｖ）学位论文作者签名：指导教师签名：曰／年＞曰如（年（月＾３。（月３西南石油大学研究生学位论文独剑性声明本人声明：所呈交的研究生学位论文是本人在导师指导下进行的研巧工作及取得的。，研巧成果据我所知，除了文中特别加Ｗ标注和致谢的地方

3、外本论文不包含其他人己经发表或撰写过的研究成果，也不包含其他人为获得西南石油大学或其它教育机构的学一位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名；年月、曰＾摘要数据挖掘又称数据库中的知识发现（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｉｎＤａｔａｂａｓｅ，ＫＤＤ），是目前人工智能和数据库领域研究的热点问题，。在现实世界中数据集中存储的属性有几十、几百、甚至上千种。这些属性中有很多是兀余的，它们会干扰数据挖掘的过程，也很大一一程度上会影响算法的效率。因此，人们提出了

4、属性约简这预处理技术。另方面，现实世界中的行为或者事物都有各种代价，，如测试代价、误分类代价、延迟代价等涉及金钱、时间、人工等方面的开销。代价敏感学习致力于涉及各类代价的挖掘问题。’当前被研究的代价敏感属性约简问题包括：最小测试代价属性约简问题、简单公共测试代价属性约简问题、最小测试时间代价问题等。人们将不同算法框架应用于这些具体问题。启发式算法的速度很快，但是由于它们常常会收敛于局部最优解，因此正确率。不高。回溯算法虽然能够保证找到最优解，但是运行时间往往不能被接受仿生算法也、常常能找到最优解，不过其耗费的时间代价过大。最近还有学者提出半贪屯

5、算法，能够一定时间内得到较好的结果在。一本文将分治算法与回溯算法相结合，提出种归并算法，Ｗ改善回溯算法的不足。本文的归并算法包含Ｈ个关键技术：分组与合并、回溯算法、Ｗ及竞争机制。该算法先一些属性子集组的大小对算法的性能有很大的影响将属性随机分组，得到，ｇ。在极端情况下，，组的大小与属性数目相同的情况下归并算法将退回为回溯算法。属性子集通过回溯算法得到属性子集的约简一，然后将每对相邻的约简合并成个新的属性子集。重复Ｗ上过程直到只剩一个属性子集，这个属性子集的约简就是原问题的约简。属性分组，后，全局重要的属性可能在局部约简时被删除导致归并算法得到

6、的解不是全局最优解。因此我们采用竞争机制，运行归并算法Ｐ次，得到Ｐ个解，再从这Ｐ个解中选取最优解。本文将该算法运用于最小测试代价属性约简问题、简单公共测试代价属性约简问题ｅｒｓ－及最小测试时间代价问题这Ｈ个问题。并使用来自ＵＣＩ（ＵｎｉｖｉｔｙｏｆＣａｌｉｆｏｒｎｉａＩｒｖｉｎｅ）数据库中的四个真实数据集对提出的归并算法进行实验。其中每种数据集使用了Ｈ种不同分布的测试代价。通过实验我们得知：竞争机制能有效提高结果的质量；对于不同问题，Ｐ值大于６之后算法结果趋于稳定；最优ｇ值对于不同情况略有不同，在最小测试代价问题中为６，简单公共测试代价、

7、最小测试时间代价问题中均为７。与现有的启发式算法、蚁群算法和回溯算法相比，归并算法在保持较高的正确率的情况下，一能够大大缩短运行时间，本文提出的归并算法是针对该类问题的种有效并且高。因此效的算法。关键词：代价敏感学习；粗糖集；属性约简；分治；回溯算法；竞争机制ＡｂｓｔｒａｃｔＤａｔａｍｉ打ｉｎｇ，ａｌｓｏｋｎｏｗｎａｓｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙｉｎｄａｔａｂａｓｅｓ（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｉｎＤａｔａｂａｓｅＫＤＤｌｉｆｉｌｌｉｉｓｃｕｒｒｅｎ