半监督Relief-F特征选择算法.pdf
《半监督Relief-F特征选择算法.pdf》由会员分享,可在线阅读,更多相关《半监督Relief-F特征选择算法.pdf(6页珍藏版)》请在咨信网上搜索。
1、第4 7卷/第4期/2 0 2 3年7月河北师范大学学报/自然科学版/J O U R N A LO FH E B E IN O R M A LU N I V E R S I T Y(N a t u r a lS c i e n c e)V o l.4 7N o.4J u l.2 0 2 3文章编号:1 0 0 0-5 8 5 4(2 0 2 3)0 4-0 3 4 8-0 6收稿日期:2 0 2 2-0 9-2 2;修回日期:2 0 2 2-1 1-1 0基金项目:国家自然科学基金(6 2 2 7 6 1 5 8);山西省回国留学人员科研资助项目(2 0 2 1-0 0 7)作者简介:靳炳烨(
2、1 9 9 8),男,山西晋城人,硕士研究生,研究方向为粒计算和数据挖掘.半监督R e l i e f-F特征选择算法靳炳烨,王 锋,魏 巍(山西大学 计算机科学与技术学院,山西 太原 0 3 0 0 0 6)摘要:数据规模的不断增加,使得为数据库中全部样本做标记变得尤为困难,数据集也因此呈现出了明显的弱标记性.为此,针对大规模少数标记数据集的特征选择问题,基于经典的R e l i e f-F算法,通过综合考虑有标记样本与无标记样本对数据样本近邻的影响,重新定义样本近邻的搜索策略,提出了一种面向符号数据的半监督特征选择算法.为进一步分析新算法的有效性,仿真实验中选取了5组U C I数据集,并引
3、入机器学习中3个常用分类器对新算法和对比算法的特征选择结果的分类性能作了分析和比较,实验结果很好地验证了本文中提出的新算法的有效性和可行性.关键词:特征选择;R e l i e f-F算法;半监督学习;距离度量中图分类号:T P1 8 2 文献标志码:A d o i:1 0.1 3 7 6 3/j.c n k i.j h e b n u.n s e.2 0 2 3 0 1 0 1 3S e m i-s u p e r v i s e dR e l i e f-FF e a t u r eS e l e c t i o nA l g o r i t h mJ I NB i n g y e,WAN
4、GF e n g,WE IW e i(S c h o o l o fC o m p u t e ra n dI n f o r m a t i o nT e c h n o l o g y,S h a n x iU n i v e r s i t y,S h a n x iT a i y u a n 0 3 0 0 0 6,C h i n a)A b s t r a c t:W i t ht h e i n c r e a s eo f d a t a s i z e,i t i sv e r yd i f f i c u l t t od e t e r m i n e l a b e l
5、s f o r a l l o b j e c t s i nd a t a b a s-e s.D a t as e t sp r e s e n tw e a km a r k e d n e s sa sw e l l.H e n c e,f o rf e a t u r es e l e c t i o no np a r t i a l l a b e l e dd a t as e t s,b yr e f e r e n c et o c l a s s i c a l R e l i e f-F a l g o r i t h m,a n e f f e c t i v es
6、e m i-s u p e r v i s e df e a t u r es e l e c t i o n a l g o r i t h m i sp r o p o s e dt od e a lw i t hp a r t i a l l a b e l e dd a t a.I n t h i s a l g o r i t h m,o n t h eb a s i so f c o n s i d e r i n g l a b e l e ds a m p l e s a n du n l a b e l e ds a m p l e s,ak i n do fn e ws e
7、 a r c hs t r a t e g yf o r f i n d i n gn e a r e s tn e i g h b o r s i s i n t r o d u c e d.F o ra n a l y z i n ge f f e c t i v e n e s so f t h en e wa l g o r i t h m,f i v eU C Id a t as e t s a n d t h r e e c o mm o n l yu s e dc l a s s i f i e r s a r ee m p l o y e d t oi l l u s t r
8、a t ec l a s s i f i c a t i o np e r f o r m a n c eo ft h en e wp r o p o s e da l g o r i t h m.T h ec o m p a r i s o na n da n a l y s i sr e s u l t ss h o wt h a t t h en e ws e m i-s u p e r v i s e df e a t u r es e l e c t i o na l g o r i t h mi se f f e c t i v ea n df e a s i b l e.K e
9、yw o r d s:f e a t u r es e l e c t i o n;r e l i e f-Fa l g o r i t h m;s e m i-s u p e r v i s e d l e a r n i n g;d i s t a n c em e a s u r e随着互联网技术和信息产业的快速发展,数据获取和采集的能力飞速提高,数据规模呈现了前所未有的增长和庞大.如何从海量的大数据中抓取重点,挖掘出最有用的信息一直以来便是智能信息领域中的研究重点和热点1.特征选择是数据挖掘领域中一种常见的数据降维技术,主要通过一定的度量来选择优的特征,移除不相关或冗余特征,进而提高学
10、习模型的性能,降低过拟合等2-6.目前,依照数据样本是否具有类别信息,现有特征选择方法可分为有监督特征选择、无监督特征选择和半监督特征选择7-8.其中,半监督特征选择算法便是将半监督学习机制引入到了处理少数标记数据的特征选择中.针对半监督特征选择的探索,一些研究者也已经取得了可观的研究成果9-1 3.文献1 4 提出了一种新颖的基于空间覆盖的半监督特征选择算法,该算法同时利用已标签数据和未标签数据进行特征选择.文献1 5基于粗糙集理论和信息熵的概念,提出了一种基于信息熵的粗糙特征选择算法.文献1 6 基于集合间相关度和自相关度的定义提出了一种基于类标号扩展的半监督特征选择算法.此外,文献1 7
11、-1 8 通过引入面向部分标记数据的特征重要度,设计了基于粗糙集理论的半监督粗糙特征选择算法.在此基础上,为进一步提高大数据背景下半监督特征选择的算法性能和可移植性,并充分利用大量无标记样本.本文中,笔者通过重新定义数据样本近邻的求解和搜索策略,以符号数据为研究对象,设计了一种基于R e l i e f-F的半监督特征选择算法.R e l i e f-F算法是较为常用的一种特征选择算法,由于其简单、易于实现已经被广泛应用于多个领域.经典的R e l i e f-F算法仅适用于有标记数据集1 9,为有效处理少数标记数据集,刘吉超等2 0在R e l i e f-F算法上进行扩展,把无标签数据和有
12、标签数据综合来考虑,从而提出了一种基于R e l i e f-F的半监督特征选择算法.该算法主要通过使用无标记样本辅助有标记样本来确定样本的近邻,进而更新特征的权重.但是该算法求解过程中只使用了少部分无标记样本,大量的无标记样本中蕴含的信息仍被忽略掉.为此,在文献2 0 算法的基础上,笔者对于有标记样本的近邻求解机制进行了优化,提出了一种优化的基于R e l i e f-F的半监督特征选择算法.为进一步验证新算法的有效性,仿真实验中选取了5组U C I数据集,并引入机器学习中3个常用分类器对新算法和对比算法的特征选择结果的分类性能作了分析和比较,实验结果很好地验证了本文中提出的新算法的有效性和
13、可行性.1 基本概念为有效度量符号数据样本的距离,进而确定其近邻样本,算法中引入了一种基于粗糙集的面向符号数据的距离度量,为此,粗糙集理论以及该距离度量的相关概念介绍如下.1.1 粗糙集相关概念粗糙集理论中,一个含有类信息的数据集通常被表示为一个四元组S=(U,A,V,f),其中U是数据样本集,称为论域,A=CD,C是特征集,D是类别信息,V=UaAVa,Va是其值属性a的值域.f:UAV是一个信息函数.对于任意的aA,并且xU,f(x,a)Va.令BC,x,yU有如下的等价关系:RB=(x,y)UU|f(x,a)=f(v,a),aB.由等价关系RB形成的等价类表示为 xB=y|(x,y)RB
14、.对于每个数据集的子集XU和BA,X的下近似和上近似算子分别为 B-(X)=xU|xBX 和B-(X)=xU|xB.1.2 一种基于粗糙集的距离度量基于上述粗糙集理论,为有效度量符号数据样本的相似性,文献2 1 提出了一种基于粗糙集的距离度量.该度量方式不仅考虑了在同一特征下不同特征值的异同,还考虑了其他特征对特征值距离(或相似度)的影响,即同一特征下2个值之间的相似度不仅取决于它们本身还与它们所处的环境有关.定义1 令S=(U,CD)是一个符号数据表,对于任意aiC,设p,qVai,p和q相对于ai的内部距离定义为 ai(p,q)=1,pq,0,p=1.(1)定义2 令S=(U,CD)是一个
15、符号数据表,对于任意aiC,设p,qVai,p和q相对与属性aj(ji)的外部距离定义为 aj=1UxUuajX(x)-uajY(x),(2)其中X=x|f(x,ai)=p,xU,Y=x|f(x,ai)=q.定义3 令S=(U,CD)是一个符号数据表,对于任意aiC,设p,qVai,p和q关于属性集A的定义为 (p,q)=1mmj=1aj(p,q),其中m表的特征数量.定义4 令S=(U,CD)是一个符号数据表,xi,xjU(1i,jn),xi和xj之间的距离定义为943 d1(xi,xj)=mi=1(f(xi,al),f(xj,al).(3)2 一种基于R e l i e f-F的半监督特征
16、选择算法2.1 算法思想R e l i e f-F算法是对经典特征选择算法R e l i e f的拓展,可有效处理多分类问题,其核心思想是:属于相同类的数据样本,那么它们之间的距离应该更近;而对于不同类的数据样本,那么它们之间的距离应该相对更远.因此,一个好的特征应该是让同类的数据样本离的更近,不同类的数据样本离的更远.R e l i e f-F算法的特征权重更新公式的主要框架是:在每个特征权重值初始值的基础上,不断减少选定数据样本及其同类近邻在该特征上的差异值,同时不断增加选定数据样本及其不同类近邻在该特征上的差异值.如果某特征的权重值较大,则说明该特征可使选定数据样本和同类样本近邻之间差异
17、更小,而和不同类样本近邻之间差异更大,即可以更好的区分类别.为有效处理少数标记数据集,刘吉超等2 0将半监督学习思想引入经典的R e l i e f-F算法中,设计了一种基于R e l i e f-F的半监督特征选择算法.该算法的核心思想是:所选取数据样本的同类近邻和不同类近邻均是从无标记数据样本中选取,并依此来更新特征权重.但是由于经典R e l i e f-F算法并未求解所有样本的近邻,而且实际数据集中通常只有少数有标记样本,尤其大数据背景下,无标记样本的规模更加庞大,因此上述方法只利用了少量的无标记样本,而大量的无标记样本未被使用,其中蕴含的大量信息也被忽略.为此,为更多地发现大量无标记
18、样本中的有用信息,设计了一种新的基于R e l i e f-F的半监督特征选择算法.新算法在求解样本近邻过程中扩大了搜索范围,充分利用了大量无标记样本,依此提高特征选择的性能.新算法的核心思想是:对给定数据样本,基于多个不同类样本的近邻来确定所选定样本的不同类近邻,即对选定样本不再基于单一的不同类样本来寻找其不同类近邻,而是从多个不同类样本的多组近邻中确定不同类近邻.2.2 算法步骤新算法的创新主要是改进了不同类样本近邻的求解方式,对选定的每个样本s(sYi类),首先求解类Yj(ij)中所有对象的近邻,即xYj,从无标记样本中求解x的k个最近邻.假设Yj中有n个对象,则一共会找到n k个近邻;
19、然后在这n k个近邻选取到s的k个无标记样本最近邻,即Yj(ij)类中s的k个近邻.新算法对不同类样本最近邻求解扩充了原有的搜索范围,更加充分利用了大量无标记数据样本.新算法的详细步骤见算法1.算法1 一种基于R e l i e f-F的半监督特征选择算法(As e m i-s u p e r v i s e df e a t u r es e l e c t i o na l g o r i t h mb a s e do nR e l i e f-F,S R f F S).输入:数据集S=S1S2,其中S1为有标记数据样本集,S2为无标记数据样本集,特征个数m,类别集C.输出:特征的权重值
20、Wk=(1,2,m).步骤1 初始化特征权重wk(k=1,2,m).步骤2 循环执行步骤2.12.4M次.步骤2.1 从有标记样本S1中随机抽取一个样本s,样本s的类别为cq(cqC).步骤2.2 从无标记数据集中基于定义4求解s的d个近邻,标记为Hqt(t=1,2,d).步骤2.3 在其余的每一类cpC(pq)中循环执行以下操作:步骤2.3.1 对类别cp中的每一个对象ycp在无标记数据中基于定义4找y的d个近邻;步骤2.3.2 在类别cp中所有对象的近邻中基于定义4计算出离s最近的d个近邻(假设cp类有1 0个对象,那么要求解1 0d个近邻,然后在1 0d个近邻中找离s最近的1 0个近邻)
21、.步骤2.4 基于下面公式更新所有特征的权重:wk=wk-dt=1D(Ak,s,Hqt)Md+pqP(cp)1-P(CP)dt=1D(Ak,s,Mpt),(4)其中:D(Ai,x,y)=0,vxi=vyi1,vxivyi,P(cp)表示样本为类别cp的概率.053步骤3 输出特征权重值wk=k(1,2,m).算法1对原先刘吉超等2 0提出的基于R e l i e f-F的半监督特征选择算法的改进主要有2点内容:首先引入了一种基于粗糙集理论的距离度量方式;其次在为和目标实例不同类的样本找最近邻的时候综合考虑每个类下的所有对象的距离,在此基础上确定所选样本的最近邻样本。而在求解出最近邻样本后,算法
22、1中使表1 实验数据集T a b.1 D a t aS e t s数据集样本数特征数类别数c a r6 8 392d e r m a t o l o g y3 6 63 36b a c k u p-l a r g e3 0 73 51 9t i c-t a c-t o e9 5 862c a r17 2 864用了与经典R e l i e f-F算法相同的特征权重值更新公式.3 实验分析为有效验证本文第2节中提出算法1的可行性,本节中选取了5组U C I数据集进行仿真实验分析.实验分析中使用的编程语言是J a v a 1.8,程序的开发平台是I D E A.程序运行的计算机配置 是:C P U
23、 I n t e r(R)i 5-6 3 0 0 HQ,2.8 0 GH Z;内 存 为1 6 G B;操作系统为W i n d o w s1 0,数据集的描述见表1.由于实际应用中,数据库中只有少部分数据样本获取到了类标签,大量存在的仍是无标记样本,为此,实验中选取有标记样本占比3 0%,即无标记数据样本占数据集7 0%的情况.为进一步验证新算法的有效性,与文献2 0 中的半监督特征选择算法(S F S R算法)以及文献1 5 中的基于信息熵的半监督特征选择算法(S E F S算法)作了比较.特征选择结果的分类性能由机器学习中常用的3个分类器:l o g i s t i c、支持向量机(S
24、VM)、朴素贝叶斯(N B C)来验证.实验比较结果见表24.表24分别给出了在3个分类器下S F S R算法、S E F S算法和I S F S R算法在表1中5组U C I数据集上的特征选择结果及其分类性能的对比结果。在表2-4中,N表示有效特征子集中特征的个数;分类性能是每组数据集的特征选择结果在上述3个分类器上的分类精度,分类精度值是通过十折交叉验证方法求解得到的最终值.实验过程中使用的分类器集成在数据挖掘软件w e k a中.此外,为更清晰地比较相同数据集由不同特征选择算法求解得到的特征子集的分类精度,表24中的最后一行列出了同一个算法在所有数据集上的分类精度均值.表2 在L o g
25、 i s t i c下算法性能的比较T a b.2 C o m p a r i s o no fA l g o r i t h mP e r f o r m a n c eU n d e rL o g i s t i c数据集S F S RS E F SS R f F SN分类精度N分类精度N分类精度c a n c e r40.9 3 830.2 3 4440.9 3 560.0 7 5140.9 3 990.0 5 84d e r m a t o l o g y1 00.8 6 880.1 7 791 00.7 4 040.0 9 561 70.8 5 240.0 5 16b a c k u
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 监督 Relief 特征 选择 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。