首页 >
论文范文 >
自然科学论文 >
数学论文 >
数理统计论文 >
探讨如何完善混合蒙特卡罗搜索的特征选择算法
摘要：特征选择是机器学习和数据挖掘中处理高维数据的初步步骤,通过消除冗余或不相关的特征来识别数据集中最重要和最相关的特征,从而提高分类精度和降低计算复杂度。文中提出混合蒙特卡罗树搜索特征选择算法(HMCTS),首先,根据蒙特卡罗树搜索方法迭代生成一个初始特征子集,利用ReliefF算法过滤选择前k个特征形成候选特征子集;然后,利用KNN分类器的分类精度评估候选特征,通过反向传播将模拟结果更新到迭代路径上所有选择的节点;最后,选择高精度的候选特征作为最佳特征子集。仿真结果表明,对比HPSO-LS和MOTiFS算法,HMCTS算法具有良好的可扩展性,且分类精度高。
加入收藏
高维数据;特征选择;相关特征;蒙特卡罗树搜索;可扩展性;
随着多媒体技术和计算机技术的高速发展,数据维度急剧增长[1,2]。特征选择是对高维数据进行降维的有效方法,目标是在保持数据底层结构的同时找到最重要的特征,实现高分类精度和降低计算复杂度[3,4]。
文献[5]中提出粒子群优化的混合特征选择算法在粒子群优化中使用局部搜索策略,考虑相关信息来选择不相关和重要特征子集。文献[6]中提出封装式蒙特卡罗树搜索的特征选择算法结合树搜索与随机采样获得最佳特征子集,由于随机性而选择一些噪声特征,在允许的模拟次数内处理高维数据时,分类精度降低。
本文提出混合蒙特卡罗树搜索的特征选择算法始特征子集,用ReliefF算法过滤选择前k个特征形成候选特征子集;再应用KNN分类器的分类精度评估候选特征,通过反向传播将模拟结果更新到迭代路径上所有选择的节点;最后选择高精度的候选特征作为最佳特征子集。仿真结果表明,对比HPSO-LS和MOTiFS算法,HMCTS算法具有良好的可扩展性,且分类精度高。
1、模型建立
蒙特卡罗搜索[7]有4个步骤:即选择,扩展,模拟和反向传播。在选择期间,搜索树从根节点遍历到非终端具有未扩展子节点的节点,基于UCT算法选择具有最高近似的节点;然后在扩展期间添加新子节点来扩展树;在模拟期间,从新的子节点进行随机模拟,直到到达终止节点,模拟奖励也在此阶段近似;最后,通过所选节点反向传播模拟奖励以更新树。树策略负责节点选择和扩展步骤,采用UCT算法[8]在各级节点上使用式(1)近似每个节点的重要性并排序,从而选择在每级选择具有最高近似值的节点。而默认策略负责模拟步骤。
UTCv=WvNv+C×2×ln(Np)Nv (1)
式中,Nv和Np分别表示节点v和父节点p已被访问次数;C是平衡探索需求和利用需求的一个常数;Wv是节点v上获胜模拟的计数。所提出的特征选择算法HMCTS模型如图1所示。
2、HMCTS算法
2.1特征选择树
假设特征选择为单个玩家游戏树,其中必须选择具有最大累积奖励的最佳表现节点(特征)。每个节点代表两个相应的特征状态之一:选择或不选择特征。
定义1:
对于特征集F={f1,f2,…,fi,…,fn},特征选择树是满足以下条件的树:
图1HMCTS模型图
①根是∅0,表示没有选择任何特征。
②任何节点在级别i-1上都有两个子节点fi和∅i,其中0<i<n。
在特征选择树中,节点fi代表特征fi被选择了,∅i表示特征fi未被选择。从根节点到叶节点的任何路径构成特征子集。因此,目标是找到提供最佳奖励(即准确性)的路径。该算法使用MCTS遍历特征选择树并选择其中一个路径。
2.2选择
遵循树策略,UCT算法遍历已经扩展的树,从根节点到当前节点(具有扩展子节点的非终止节点)。每个级别上通过使用式(2)选择获得具有高分的节点。如果在i级上选择节点fi,则证明特征fi在以前的迭代中为高奖励做出贡献,添加在特征子集Finitial中。另一方面,如果选择节点∅i,则特征fi没有为高奖励做出贡献,不添加特征fi到Finitial。
UCT算法在特征选择问题上的核心目标是找到具有最高奖励的路径(即准确性),如式(2)所示:
UTCvj=max(Qvj)+C×2×ln(Nvi)Nvj (2)
式中,max(Qvj)表示节点vj的最大奖励;C>0是一个常数;Nvj和Nvi分别是节点vj和父节点vi已被访问的次数。在树遍历期间,在每个树级别上选择具有最高分数的节点。
2.3扩展
通过添加新的子节点来扩展搜索树,将子节点添加到紧急节点(选择期间选择的最后一个节点)。同样,将UCT得分最高的子节点添加到搜索树中。假设在某个时刻紧急节点是vi,如果算法在搜索树中添加节点fi+1,表明特征fi+1包含在初始特征子集Finitial中。相反,添加子节点∅i+1,表明特征fi+1不包含在Finitial中。
2.4模拟
模拟步骤由默认策略控制,随机选择一个来自扩展子节点vi到叶节点vn的路径,因此,当前特征子集Finitial中包含或排除剩余的未扩展特征的概率一样。
假设扩展的子节点在当前的迭代中,特征f1～fi包含在选择步骤和扩展步骤(树策略)期间的初始特征子集Finitial中,剩余的特征fi+1～fn根据模拟步骤(默认策略)随机添加,在生成特征子集时随机采样并进行树搜索。
2.5候选特征子集生成
每次迭代都会生成初始特征子集Finitial,由于默认策略的完全随机性,很可能选择Finitial中高比例的特征。随着特征维度增加,选择的Finitial中包含噪声特征。为了解决这个问题,在Finitial中采用过滤器选择前k个特征形成候选特征子集Fcandidate,如式(3)所示:
Fcandidate=topK_Filter(Finitial)(3)
使用过滤器有两个优点:首先有助于从随机选择中消除噪声特征,其次有助于目标函数控制所选的特征维度并实现高精度。
2.6奖励计算和反向传播
将分类器应用于候选特征子集Fcandidate,Fcandidate上的分类精度用作当前扩展节点模拟奖励Qsimulation,通过反向传播奖励来更新搜索树,如式(4)所示:
Qsimulation=ACCclassifier(Fcandidate)(4)
式中,ACCclassifier(Fcandidate)是Fcandidate的分类精度。如果Fcandidate提供更高的准确性,则更新最佳特征子集,该过程继续,直到满足停止标准。
本文使用KNN分类器[9]进行奖励(分类精度)计算,KNN是非参数,最简单、最有效的学习算法。使用ReliefF[10]作为过滤方法,它的关键思想是根据特征值在彼此接近的样本之间的区别来估计他们的权重,根据类标签对特征进行排名。HMCTS算法代码如下:
3、仿真分析
3.1数据集和参数设置
为了验证本文所提算法的性能,选取低维数据集Multiple[11]和高维数据集Colon、Lymphoma[12]进行仿真分析,将所提HMCTS算法与HPSO-LS和MOTiFS进行仿真对比分析,实验中对算法的平均准确率及可扩展性两个个性能指标进行了分析。数据集详细信息如表1所示。
文本进行10倍交叉验证,其中1倍用作测试集,剩余9倍用于训练和验证。将所有数据集的缩放因子C修正为0.1,终止标准(#simulations)和top-k过滤有两种不同的设置。低维数据集和高维数据集分别设置#simulations为1000和10000,对于低维数据集,选择和分析特征总数的前5%,10%,15%,20%,25%,30%,高维数据集只有非常小比例的特征是相关的,但不是多余的。因此,top-k仅选择顶部5,10,15,20,25,30的特征。
表1仿真数据集
3.2仿真结果分析
为了对比分析不同算法的分类精度,分别在三个数据集中仿真平均准确率,对比如图2-4所示。
图2Multiple中不同特征的平均准确率
由图2可看出,HMCTS算法在低维数据集中平均准确率高于HPSO-LS和MOTiFS算法,这是由于混合式蒙特卡罗树能快速搜索找到最优特征子集,从而提高算法分类精度。
图3Colon中不同特征的平均准确率
由图3-4可以看出,HMCTS算法在高维数据集中平均准确率高于HPSO-LS和MOTiFS算法,而且当数据特征的维度越大时,混合蒙特卡罗树搜索性能更好,分类精度更高,表明算法可扩展性好。为了说明HMCTS的蒙特卡罗搜索策略的有效性和算法性能,将算法平均准确率和选择的特征列于表2中。从表中可看出HMCTS选择极少数特征就能使分类精度得到极大提高,表中的最后一列显示了没有特征选择的分类精度。
图4Lymphoma中不同特征的平均准确率
表2比较不同算法平均准确率(选择特征和未选择特征)
4、结束语
针对如何有效提高高维数据的分类精度和降低计算复杂度问题,提出混合蒙特卡罗搜索的特征选择算法HMCTS。首先,根据蒙特卡罗树搜索方法迭代生成一个初始特征子集,采用ReliefF算法过滤选择前k个特征形成候选特征子集;然后,采用KNN分类器的分类精度评估候选特征,通过反向传播将模拟结果更新到迭代路径上所有选择的节点;最后,选择高精度的作为最佳特征子集。仿真结果表明,对比HPSO-LS和MOTiFS算法,HMCTS算法具有良好的可扩展性,且分类精度高。在进一步的研究中,将考虑高维不平衡数据特点,改进算法。
参考文献:
[1]胡晶.云计算海量高维大数据特征选择算法研究[J].计算机仿真,2019(4):190-193.
[7]朱合兴.基于蒙特卡罗树搜索的预测状态表示模型获取及特征选择研究[D].厦门:厦门大学,2017.
[8]梁国军,谢垂益,胡伶俐,等.UCT算法在不围棋博弈中的实现[J].韶关学院学报,2015,36(8):17-21.
刘云,肖雪,黄荣乘.混合蒙特卡罗搜索的特征选择算法的优化[J].信息技术,2020,44(05):28-31+36.
基金:国家自然基金资助项目(61761025).
分享：
遵义市普通高校羽毛球教师普遍存在着年轻化的趋势，教学内容与教学方法都比较单一，教学内容的学时均未达到国家指定的标准。因此，为了提高遵义市普通高校羽毛球选项课的开展，笔者提出了以下建议：1.实施人才引进。2.增加教学内容。3.转变教师的教学方法。4.严格遵循《指导纲要》的相关规定。
2020-07-09
数理统计的应用原理主要是通过随机现象的有限次数来实验和观测所得数据进行归纳和分析，并在得出的数据中找出一定的规律性来制定出一个具有科学依据的有效判断和推断。其特点是不仅具有能够为行业发展、管理工作提供有效参考数据的实际应用性，通过合理应用还可以提高行业竞争力。
2020-07-09
“概率论与数理统计”是研究随机现象数量规律的一门学科，也是研究生产生活中随机现象中隐藏的固有统计规律的一门数学学科，该课程的应用几乎遍及自然科学、社会科学、工程技术、军事科学及生活实际等各领域。“概率论与数理统计”课程的系统学习，可以培养学生认识问题、研究问题与处理相关实际问题的能力[1]。
2020-07-09
概率论和数理统计课程是国内高等院校理工类和经管类专业的一门基础性课程。这门课程具有很强的实践性,里面涉及到的理论和方法可以应用到很多领域,帮助解决问题,大数据统计分析更是一种非常实用的统计法[1]。它在医学、金融、保险等很多领域都发挥着非常重要的作用,因此被很多高校的很多专业所青睐,将其设置为公共基础课程。
2020-07-09
概率论与数理统计是一门通过演绎和归纳的方法研究随机现象及其规律性的一门学科。其理论和方法已被广泛应用于金融、经济、军事、生物、大数据等诸多领域中，是理科、工科、经济管理类专业必修的一门数学基础课程。尤其是随着计算机的普及和大数据时代的到来，概率论和数理统计是进行数据分析和数据处理的核心基础课程。
2020-07-09
《概率论与数理统计》是应用型本科院校各专业一门重要基础课,该课程的教学质量直接关系到人才培养的规格和质量,而该课程的建设是保证和提高教学质量的基础和前提。课程由概率论与数理统计两部分组成。概率论部分侧重于理论探讨介绍概率论的基本概念,建立一系列定理和公式,寻求解决统计和随机过程问题的方法。
2020-07-09
《概率论与数理统计》是一门研究和探索客观世界随机现象统计规律性的数学学科,是全国各类高等院校理科、工科、经济、管理、医学、农林等专业的必修基础课。它是以概率论为基础,研究如何以有效的方式获得、整理和分析受到随机性影响的数据,并以这些数据为依据,建立有效的数学模型,从而揭示所研究问题的统计规律性。
2020-07-09
《概率论与数理统计》是工科专业的一门必修课,是基础课中难度最大的学习领域,是一门处理随机现象的学科,其思想方法不同于高等数学、线性代数等研究确定性现象的数学分支。传统的教学方法注重理论的推导及简单应用,不能很好地将概率统计的知识应用于实际的问题中,使这门应用性很强的课程与实际存在一定距离。
2020-07-09
数学文化这个词的内涵,简单地说,是指数学的思想、精神、方法、观点,以及它们的形成和发展;广泛地说,除了上面的内涵之外,还包括数学家、数学史、数学美、数学发展的人文成分、数学与社会的联系等等。数学在人类文明的历史进程中一直都是先进的文化。人类历史每一个重大的事件背后都有数学的身影。
2020-07-09
在氨纶生产过程中，工艺、设备、自控以及人工智能方面飞速发展，工厂的生产规模已经从年产几千吨发展到年产十几万吨，以数理统计结果为决策依据的工作方法被越来越多的技术人员所认同。数理统计，甚至是大数据分析所发挥的作用会越来越大。本文介绍了氨纶生产中一些可以作为工具使用的数理统计方法。
2020-07-09
人气：6027
人气：3169
人气：3023
人气：2628
人气：2543
我要评论
期刊名称：数学的实践与认识
期刊人气：2784
主管单位：中国科学院
主办单位：中国科学院数学与系统科学研究院
出版地方：北京
专业分类：科学
国际刊号：1000-0984
国内刊号：11-2018/O1
邮发代号：2-809
创刊时间：1971年
发行周期：半月刊
期刊开本：16开
见刊时间：1年以上
影响因子：0.553
影响因子：0.322
影响因子：0.352
影响因子：0.000
影响因子：0.000
科普杂志阅读、期刊信息查询、论文下载、文献查询、原创文章检测等多项服务。
服务热线
您的论文已提交，我们会尽快联系您，请耐心等待！
你的密码已发送到您的邮箱，请查看！
2020-05-26
275
上传者：管理员
