菜鸟豆腐汤
范文一：特征选择方法
1、为什么要做特征选择 在有限的样本数目下，用大量的特征来设计分类器计算开销太大而且分类性能差。
2、特征选择的确切含义
将高维空间的样本通过映射或者是变换的方式转换到低维空间，达到降维的目的，然后通过特征选取删选掉冗余和不相关的特征来进一步降维。
3、特征选取的原则
获取尽可能小的特征子集，不显著降低分类精度、不影响类分布以及特征子集应具有稳定适应性强等特点
4、特征选择需要考虑的问题
a、确定选择算法，在允许的时间内以最小的代价找出最小的、最能描述类别的特征组合，b、确定评价标准，衡量特征组合是否是最优，得到特征获取操作的停止条件。
5、特征获取方法
a、按照特征子集的形成方式可以分为三种，穷举法（exhaustion）、启发法（heuristic）和随机法（random）。穷举法需要遍历特征空间中所有的特征组合，所以方法复杂度最大，实用性不强；启发法通过采用期望的人工机器调度规则，重复迭代产生递增的特征子集，复杂度略低于穷举法，但是只能获取近似最优解；随即方法分为完全随机方法和概率随机方法两种，对参数设置的依赖性较强。
b、按照特征评价标准来分，根据评价函数与分类器的关心，可以分为筛选器和封装器两种，筛选器的评价函数与分类器无关，封装器采用分类器的错误概率作为评价函数。筛选器的评价函数可以细分为距离测度、信息测度、相关性测度和一致性测度。距离测度用距离来衡量样本之间的相似度，信息测度用利用最小不确定性特征来分类。
6、特征获取方法的选取原则
a、处理的数据类型
b、处理的问题规模
c、问题需要分类的数量
d、对噪声的容忍能力
e、无噪声环境下，产生稳定性好、最优特征子集的能力。
本文参考王娟等《特征选择方法综述》论文。
范文二：新颖的无监督特征选择方法
新颖的无监督特征选择方法
第39卷第3期
201O年5月
电子科技大学
JournalofUniversityofElectronicScienceandTechnologyofChina
Vl01_39No.3
Mav20l0
新颖的无监督特征选择方法
朱颢东,2,一,李红婵,钟勇2
(1.郑州轻工业学院计算机与通信工程学院郑州450002;2.中国科学院成都计算机应用研究所成都610041
3.中国科学院研究生院北京石景山区100039)
【摘要】针对有监督特征选择方法因为需要类信息而无法应用于文本聚类的问题,提出了一种新的无监督特征选择方法:
结合文档频和K.Means的特征选择方法.该方法首先使用文档频进行无监督特征初选,然后再通过在不同K-Means聚类结果上
使用有监督特征选择方法来实现无监督特征选择.实验表明该方法不仅能够成功地选择出最为重要的一小部分特征,而且还
能提高聚类质量.
关键词分类:聚类算法:文档频:特征选择:K-Means
中图分类号TP301.6文献标识码Adoi:10.39690.issn.1001-0548.2010.03.019
NewUnsupervisedFeatureSelectionMethod ZHUHao-dong'',LIHong-chan,andZHONGYong' (1.SchoolofComputerandCommunicationEngineering,ZhengzhouUniversityofLightIn
dustryZhengzhou450002;
2.ChengduInstituteofComputerApplication,ChineseAcademyofSciencesChengdu6100
41;
3.TheGraduateSchooloftheChineseAcademyofSciencesShijingshanBeijing100039) AbstractDuetounavailabilityofclasslabelinformation,supervisedfeatureselectionmethodscarlnotbe
appliedtotextclustering.Inthiscase,anewunsupervisedfeatureselectionmethodcombinedDocument
FrequencywithK-Me~sisproposed.Themethodfirstlyemploysdocumentfrequencytoselectinitial
unsupervisedfeatures,andthenbringsintounsupervisedfeatureselectionbymeansofmainlyperformingeffective
supervisedfeatureselectionmethodsondifferentK-Meansclusteringresults.Experimentalresultsshowthatthe
newmethodcannotonlysuccessfullyselectoutthebestsmallpartoffeatures,butalsoCansignificantlyimprove
clusteringperformance.
Keywordsclassification;clusteringalgorithms;documentfrequency;featureselection;K-Means
有监督特征选择方法在文本分类中得到了广泛
的应用,例~I]IG和CHI两种高效的有监督特征选择
方法能移走文本中多达98%的单词而且还能不降低
文本分类的性能【lJ.文献【l】系统地研究了用于文本
聚类的无监督特征选择方法,通过对文档频数,单
词权,单词熵等多种无监督特征方法进行对比分析,
发现这些无监督特征选择方法在不降低聚类性能的
前提下通常只能移走90%左右的单词,如果再移走
更多的单词,文本聚类的性能就会急剧下降.因此,
用于文本聚类的无监督特征选择仍是一个亟待进一
步研究的问题.
为此,本文提出了一个基于文档频和K.Means
的无监督特征选择方法,该方法使用分类领域的有
监督特征选择方法解决文本聚类领域的无监督特征 选择问题.实验结果表明该方法不但能得到使用有 监督特征选择所得到的聚类结果,而且还优于任何 一
种无监督特征选择所得到的聚类结果.
l几种无监督特征选择算法
在文本聚类中最为常用的几种无监督特征选择 方法有文档频,单词权,单词熵和单词贡献度【2J, 下面对它们做一下简单介绍,具体请参考文献[2]. 1.1文档频(DF】
文档频(documentfrequency,DF)是最易理解的 一
种无监督特征选择方法.某个词的文档频是在整 个文本集中出现该词的文本数.文档频的理论前提 是:词在某个类中出现次数过多或过少对问题是无 贡献的,删除这些单词对聚类的结果不但没有负面 影响,而且还可能会提高聚类结果,尤其是在那些 稀单词恰好是噪声单词的情况【l】.
收稿日期:2008—09—171修回日期:2009—03—26 基金项目:四川省科技计划项N(2008GZ0003)四川省科技攻关项
1~I(07GG006-019)
作者简介:朱颢东(1980一).男.博士.主要从事软件过程技术与方法,文本挖掘和智
能信息处理方面的研究
第3期朱颢东等:新颖的无监督特征选择方法4l3 文档频的优点在于它速度十分快,其时间复杂 度O(n)N文本数成线性关系,因此非常适合于海量 文本数据集的特征选择【jJ.
1.2单词权(TS)
文献[4]提出的单词权(termstrength,TS)被用于
删除对文本检索没有贡献的单词.该方法的主要思 想是:单词在相关的文本中出现的频率越高,在不 相关的文本中出现的频率越低,该词的重要性越大. 在单词权方法执行过程中,由于要计算所有文 本对之间的相似度,因此,该算法的时间复杂度较 高,最低为O(n).不过,单词权不依赖于类信息, 是一种无监督的特征选择算法,所以能用于文本聚类. 1.3单词熵(EN)
文献【5】提出的单词熵(entropy-basedfeature
ranking,EN)是专门用于聚类问题的特征选择方法. 该方法的基本思想是:不同的单词对数据的结构影 响不同,单词重要性越大对数据的结构影响也就越 大.该方法的缺点在于其时间复杂度太高,为 O(m×"),作用于海量数据时}生能十分低. 1.4单词贡献度(TC1
文献[6]提出的单词贡献度,其基本思想是:单 词对整个文本数据集相似性的贡献程度越大其重要 性也就越大,即有:
re(t)=.f(t,a1)×厂(f,,)(1)
胃
式中f(t,)表示单词f在文档d中的权重,该权重 通常由该单词词频的对数乘以该单词的文档频,并 进行归一化处理而获得【7J.文档频的使用增强了文 档频低的单词的贡献,同时削弱了文档频较高的单 词的贡献.通过进一步分析式(1)发现:单词的文档 频越高其被累加的次数也就越多,从而平衡了单词 权重和单词文档频之间的矛盾,那些只出现在1个文 本中和出现在所有文本中的单词的贡献度都将为0, 而那些相对出现较多且具有较高权重的单词的贡献
度较大.
2无监督特征选择方法思想
有监督特征选择在文本分类中得到了较为成功 的应用,特别是lG和CHI两种有监督特征选择方法 能移走文本中多达98%的单词而且还能略微提高文 本分类的性能j.但是,有监督特征选择却因为依 赖类信息而很少地被应用于文本聚类【lo】,即使把它 们应用于文本聚类,它们也只能在不降低文本聚类 性能的前提下最多移走90%左右的单词,并且随着 移走更多的单词文本聚类的性能会急剧降低L3J.在 这种情况下,就很自然地产生了一个疑问:如果将 那些在文本分类中被成功应用的有监督特征选择方 法用于文本聚类,是否也能较大程度地提高文本聚 类的性能?文献【6】做了一组较为理想的实验.在实 验中事先查看了文档的类别信息,然后再使用IG和 CHI两种有监督的特征选择方法进行特征选择.实 验结果表明该两种有监督特征选择方法不但能够移 走高达98%的单词而且还能持续提高文本聚类的 性能.
有监督特征选择无法直接应用于文本聚类,因 为该类方法需要依赖于文档的类别信息,而文档的 类别信息正是文本聚类所要解决的问题.这似乎是 个矛盾,但是这种矛盾传却达了一个新的启发信息: 能否在聚类的结果上使用现存的有监督特征选择方 法,然后再在无监督特征选择的基础上进行重新聚 类?本文试图证明该问题.
文献【2】表明:文档频在删除90%单词时,它的 性能与IG和CHI的性能相当,效率十分高.为此, 本文在初始聚类特征选择时选用该方法.由于在众
多聚类算法中,K.Means算法过程简单,易理解, 因此本文使用该算法聚类.对于将要使用的有监督 特征选择方法,本文选择降维效果较好的IG方法. 根据上面的选择,本文进行了一次实验,其过 程为:首先利用文档频数在准备聚类的文档集上进 行特征选择,然后再利用K-Means算法进行多次不 同的聚类,紧接着再在每一个聚类结果上使用IG进 行特征选择并再次进行聚类.该过程可以循环多次, 直至达到满意的聚类效果.从实验结果发现再次聚 类的结果几乎完全好于原始的聚类结果,而且当原 始聚类的结果越好,聚类结果也就越接近理想的分 类结果,在其基础上使用有监督特征选择方法选择 出来的特征也就越接近于理想情况下使用相同方法 所选择出来的特征,进而再次聚类的结果也就越好. 然而,在实际执行的过程中面临很大的问题: (1)对待聚类的海量文档来说,具体聚类成多少个类 别很难设定;(2)各类别文档在大多数情况下分布是 极不均衡的,有的类别文档数可能很大,而有的类 别文档数又可能很小,甚至d,N可以作为噪声处理. 在该情况下,每个聚类结果都具有很大的不确定性, 它们可能把一个大类分割成很多小类,也很可能把 很多小类聚合成一个大类,而目前的各种方法又很 难确定哪一个聚类结果更接近实际的分类.因此在 单次聚类结果上进行的特征选择也具有不确定性, 414电子科技大学第39卷
选出的特征集质量高就会较大提高聚类性能,反之 就会降低聚类性能.
为了解决该两个问题,文献【l1】突破K-Means算 法的限制,提出了一种较好的方法,该方法通过合
并在不同初始条件下产生的多个不同K-Means聚类 结果得到最后的聚类结果,不但能够有效地消除单 次K-Means聚类结果的随机性,而且还能够发现任 意形状的簇.受该方法的启发,发现K-Means算法 所得到的解是一个局部最优解,它能从不同角度刻 画数据的分布规律,不同的解之间多多少少都存在 一
种互补和加强的关系,因此,通过合并在不同 K.Means聚类结果上所选择的特征集,可以很好地 消除在单次聚类结果上进行特征选择的随机性.因 此提出了一种新的用于聚类的无监督特征选择方法 ——
结合文档频和K-Means的特征选择方法.该方 法首先使用文档频进行特征初选,然后再通过指定 不同的K值和初始点获得不同的K.Means聚类结果, 紧接着再在不同聚类结果上使用IG获得特征子集, 并把各特征子集合并获得最终的特征集,最后对所 得的特征集进行微调以突出那些类区分能力较大的 特征,并把调整后的特征子集作为最终的特征集. 之所以在最后加一个特征调整模块,主要是因 为不同的词对分类的贡献是不同的,例如名词的分 类能力就比助词的强.对某些文档向量进行调整时 须突出分类重要词,调整的方法为:按一定比例降 低非重要词所占比重.调整方法的特点为:(1)突出 分类重要词和文档本质意义;(2)调整方法简单易 行,只要扫描一遍文档词向量即可.
3无监督特征选择方法描述
结合文档频和K-Means的无监督特征选择方法如下.
输入:?,个待聚类的文档,最小文档频MINDF, 最大文档频MAXDF,最大聚类个数MAXK,最小 聚类个数MK,聚类次数特征选择方法IG. 输出:一个集合P,该数组集合为最终所选择的 特征子集,初始P为空;
步骤1:对整个文档集进行自动分词;
步骤2:根据停用词表去除停用词,称为第一次 特征过滤,并统计词频和单词的文档频: 步骤3:移除DF值大于MAXDF和低于MINDF 的词,进行第二次特征过滤得到特征集Q; 步骤4:For(j=l:,户H)
(1)随机地从【MIN_K,MAX_
K】中选择一个数
作为
(2)从特征集Q中随机选择七个初始中心点,并 依次进行k-Means聚类,得到类集C;
(3)以类集C为基础,利用特征选择方法IG进行 特征选择,得到特征子集凰
P=P+H.
Endfor;
步骤5:对特征集P进行微调,以突出哪些贡献 较大的特征词,然后输出调整后的特征集尸. 从方法流程上看,该方法相当于一个适用于聚 类领域的特征选择系统框架,在步骤的3中可以用其 它任何有监督特征选择方法代替IG方法.当然步骤4 的(1)和步骤4的(2)也可以用其他聚类方法代替,之 所以用K-Means是因为该聚类方法简单易理解.总 的来说本文提供的是一种适用于文本聚类领域的特 征提取框架.
4实验验证
实验数据选择复旦大学计算机信息与技术系国 际数据库中心自然语言处理小组构建的中文文本分 类语料库.分词时采用的是中科院计算所的开源项 目"汉语语法分析系统ICTCLAS"系统.之所以选 择有类别信息的语料库,是为了聚类后有个对比. 分别使用文档频(可视为O)和本节提出的方法并 使用k-Means算法进行聚类,其中本文方法进行了16 次实验仿真,也即参数分别为O到15.其实验结果 如图1所示.
M/q"
图1聚类精度随增加的变化趋势
从图l可以看出随着的增加聚类精度增加,并 且j到一定次数时聚类精度就几乎不会再增加 了,符合实际.因为聚类精度不可能随着无限 增大而增大,毕竟所采用的聚类算法也有自身的不 足.需要说明的是,图l并不是用于说明聚类算法的 第3期朱颢东等:新颖的无监督特征选择方法4l5 精度大小的,而是用于证明本文所提出的方法思想, 即聚类算法的精度是随着的增加而增加,并最终 趋于一个平衡状态的..
5结束语
本文把分类领域的有监督特征选择方法用于聚 类领域,提出了一种结合文档频和K-Me~s的无监 督特征选择方法.该方法通过在不同聚类结果上使 用有监督特征选择的思想,将那些在文本分类中非 常有效但无法直接应用于文本聚类的有监督的特征 选择方法成功地应用于文本聚类中,极大地降低了 文本向量空间的维度,显着地提高了文本聚类的性
能.实验表明该方法不仅能够成功地选择出较优秀
的特征子集,而且还能显着提高聚类性能,从而在
一
定程度上解决了文本聚类中的无监督特征选择问
题,该方法在文本聚类中有一定的实用价值.
参考文献
【1】YANGPEDERSENIo.Acomparativestudyonfeature selectionintextcategorization[C]//ProcofInternational ConferenceonMachineLearning.SanFrancisco:Morgan KaufmannPublishers,1997:412-420.
【2】刘涛,吴功宜,陈正.一种高效的用于文本聚类的无
监督特征选择算法【J】.计算机研究与发展,2005,21(3):
381-386.
LIUTao,WUGong—yi,CHENGZheng.Aneffective
unsupervisedfeatureselectionmethodfortextclustering[J]. JournalofComputerResearchandDevelopment,2005, 2l(3):381—386.
【3】JIANGNing,GONGXu-jun,SHIZhong-zhi.Text clusteringinhigh-dimensionfeaturespace[J].Joumalof ComputerEngine&andApplication,2002,21(2):63-67. f41WILBURJWSIRO1]INK.Theautomaticidentification ofstopwords[J].JournalDfInformationScience,1992. 18(1):45-55.
【51MANORANJAND,LIUHuan.Featureselectionfor clustering[C]//ProcofKnowledgeDiscoveryandData Mining.Heidelberg:SpringerBerlin,2000:110-121. 【6】LluTao,LJuSheng-ping.Anevaluationonfeature selectionfortextclustering[C]//Procoflnternational ConfereneeonMachineLearning.SanFrancisco:Morgan KaufmannPllb1ishers.2003:53-58.
【7】SALTONGAutomatictextprocessing:thetransformation, analysisandretrievalofinformationbycomputer[C]//Proc ofThelCML89.Pennsylvania:Addison—Wsley,1989.
32(2):l1—17.
『81XUYan.Aformalstudyoffeatureselectionintext categorization[J1.AmericanJoumalofCommunicationand Computer,2009,6(4):32-4l.
【91DES?R0M0SCIS,M0LCD.Featureselectionfor
high—dimensionaldata[J].ComputationalManagement Science,2009,6(11:25-40
【lO1JENNIFERGD,BRODLEYCE.Featuresubsetselection andorderidentificationforunsupervisedleaming[C]//Proc oflntemationalConferenceonMachineLearning.San Francisco:MorganKaufmannPublishers,2000:88-97. 『Il1FREDJNAK.Evidenceaccumulationclustering basedonK-meansalgorithm[C]//ProcofSSPR/SPR. Heidelberg:SpringerBerlin.2002:31.37.
编辑蒋晓
范文三：一种新型的文本无监督特征选择方法
第30卷第6期 2007年6月重庆大学学报(自然科学版)
Journal of Chongqing University (N tur l Science Editi on )
Vol . 30 No . 6Jun . 2007
文章编号:10002582X (2007) 0620077203
一种新型的文本无监督特征选择方法
何中市, 徐浙君
a
b
(重庆大学a . 计算机学院; b . 语言认知与信息处理研究所, 重庆400030)
摘 要:结合文档频数DF (Docu ment Frequency ) 和特征相似度FS (Feature Si m ilarity ) 方法, 提出一
种新的无监督特征选择方法DFFS 。该方法利用文档频数过滤掉90%的特征之后, 再借助特征相似度移除尽可能多的冗余特征。采用K -均值方法, 对比DFFS 方法与其他3种常用特征选择方法(DF, T C, TS ) 的聚类性能。实验一:当特征数量由60001, DF , 而DFFS 方法则有提高, 甚至当特征数量进一步减少到, :在保持10%～2%的特征时, DFFS DFFS 方法的明显优于其他方法。
关键词:; 单词权; 单词熵 中图分类号:文献标志码:A 由于文本是非结构化的数据, 要想从大量的文本中挖掘有用的信息就必须首先将文本转化为可处理的结构化形式。目前人们通常采用向量空间模型来描述文本向量, 但是如果直接用分词算法和词频统计方法得到的特征项来表示文本向量中的各个维, 那么这个向量的维度将是非常的大。这种未经处理的文本矢量不仅给后续工作带来巨大的计算开销, 使整个处理过程的效率非常低下, 而且会损害聚类算法的精确性, 从而使所得到的聚类结果很难令人满意
[1]
无监督的特征选择很难选择出最具类区分力的特征。
L iu 等人于2003年对用于文本聚类的无监督特
[5]
征选择算法作了系统的研究, 比较了包括文档频数、单词权、单词贡献度在内的多种无监督特征算法, 结果发现它们在不降低聚类性能的前提下通常只能移走90%左右的单词, 当移走更多的单词时, 文本聚类的性
能会急剧下降。因此, 用于文本聚类的无监督特征选择仍是一个有待进一步解决的难题。为此提出了一种基于文档频数和特征相似度的特征选择方法(Docu 2ment Frequency and Feature Si m ilarity, 简记为DFFS ) ,
。因此, 必须对文本向量做进一步
净化处理, 在保证原文含义的基础上, 找出对文本特征类别最具代表性的文本特征。为了解决这个问题, 最有效的办法就是通过特征选择来降维。
特征选择在文本分类的应用上已经非常广泛而且深入, 比如信息增益和χ统计作为2种最为有效的有监督特征选择算法能在不降低文本分类性能的前提上移走到达98%的单词
[225]
2
该方法可以移走96%左右的单词而不降低聚类的性能, 且算法效率高。
1 几种常见的文本无监督特征选择方法
特征选择通常采用单一特征指标或者特征对之间的相异度指标进行排序选择。1. 1 单一特征指标方法
, 但是在文本聚类问题上, 特
征选择的研究与应用却相对较少, 究其原因是文本聚类不像文本分类一样具有已知的训练数据, 它没有任何已知的信息可以利用, 所以在缺乏类信息的条件下
在文本聚类中常用的基于无监督特征选择方法, 包括文档频数、单词权和单词贡献度
[3]
。
78
1) 文档频数
重庆大学学报(自然科学版) 第30卷
文档频数(Document Frequency, DF ) 是最为简单的一种特征选择算法, 它指的是在整个数据集中有多少个文本包含这个单词。DF 有一个基本的假设, 那就是认为对一个类来说, 出现次数过多或过少的单词是没有意义的, 删除这些单词对分类的结果不仅不会造成不利的影响, 相反可能会将其有所提高, 特别是当那些稀有的单词刚好是噪声单词的时候。
文档频数最大的优势就是速度快, 它的时间复杂度和文本数量成线性关系, 所以非常适合于超大规模文本数据集的特征选择。不仅如此, 文档频数还非常地高效, 在有监督的特征选择应用中当删除90%单词的时候其性能与信息增益和x 统计的性能还不相上下。
2) 单词权
单词权(Ter m Strength, TS ) 为重要, 其定义如下
=t |rel D (D =
,
D 中相关的元素(文档) 有序对
(1)
2
如下3种计算方法。
1) 相关系数法(Correlati on Coefficient )
基于2个随机变量之间的线性相关关系, 根据相关系数公式
x, =
,
2个特征之间的相异度指标定义为S (x, y ) =1-
x, 。
2) 最小平方回归误差法(Least square regressi on err or )
基于最小平方回归误差的相异度指标定义为2个随机变量x, y 之间的回归误差x, , 即S (x, y ) =
x, , i
=y i -a -bx i ,
a, b 由最小平方回归误差原理确定。
3) 最大信息压缩指标法(Maxi m al infor mati on co m 2p ressi on index )
基于最大信息压缩指标的相异度指标定义为S (x, y ) =x, , 其中
x, =
+2
其中rel D (D ) 表示D 中相关的元素有序对。TS (t ) 计算的是一个条件概率, 即一个词t 在一对相关文本中的某一个文本中出现的条件下, 在另一个文本中出现的概率。
因此TS (t ) 表示rel D (D ) 中, 同时包含项t 的有序对的比例。3) 单词贡献度
单词贡献度(Ter m Contributi on, TC ) 认为一个单词的重要性取决于它对整个文本数据集相似性的贡献程度, 其计算公式如式下
=
i, j ∩i ≠j
+var (y )
-2
1-2
-2
S (x, y ) , 比如最大信息压缩指标。
。
可以采用以上3种方法中的任意一种计算相异度
[4]
2 基于文档频数和特征相似度的特征选择方法
基于特征相似度的特征选择方法的思想如下。从全体特征构成的集合开始, 不断地去掉一些特征(k 个, 这k 个特征是某一个代表特征的k 个最近邻
t, t, ,
(2)
∑
居; 代表特征的选取原则是极小化—由于去掉这些特
k 征引起的误差—用距离/相异度r i 表示) , 并不断减
[5]
其中f (t, d ) 表示的单词t 在文本d 中的权重。
少k, 使误差也不断减少, 直到减少到k =1。
通过前面的介绍, 可知DF 在删除90%单词的时候性能是相当好的, 这说明剩余的10%的特征中包含了极大部分有价值的特征, 当然其中也包含了大量冗余的特征。那么如何在这剩下的10%特征中挑选出那些最具区分能力的特征呢?
笔者基于特征相似度的特征选择的思想, 提出了一种新的文本特征选择方法, 即基于文档频数和特征相似度的特征选择方法, 简记为DFFS (Document Fre 2quency and Feature Si m ilarity ) 。该方法首先通过DF
1. 2 特征对之间的相异度指标计算方法
基于特征相似度的方法是根据特征对之间的相异
度指标(或者相似度) , 在一组相似的特征中选择一个特征代表这一组特征, 丢弃组中其他的特征
[6]
。比如
物体有体积、密度和质量3个特征, 其中体积和质量是线性相关的, 认为它们是相似的, 只要取其中一个特征即可。如果将特征x 和y 之间的相异度记为S (x, y ) ,
S (x, y ) 越大, 就意味着这2个特征越不相似。这里讨
论特征之间根据线性相关来确定它们之间的相似度, 从而确定相异度。目前, 特征对之间的相异度指标有
来缩减大部分无关特征, 然后再利用特征相似度方法
第6期 何中市, 等: 一种新型的文本无监督特征选择方法79
从纯特征的角度再减少部分特征。也就是说, DFFS 经过了3次特征过滤, 如图1所示
。
图1 DFFS 的3次特征过滤
下面给出DFFS 特征选择方法的具体步骤。
1) 对整个文档集进行自动分词;
2) 根据停用词表去除停用词(第1次特征过滤) , 并统计词频和单词的文档频数;
3) 去掉DF 值过高或过低的词(第2次特征过滤) ; 4) 根据特征相似度方法计算特征的相关性, 进行特征子集选择(第3次特征过滤) ;
5) 根据归一化的TF -I D F 方法为每个特征附一权重。
图2 精度比较
图中将DFFS 方法与基于单一特征指标的3种特
征选择方法(DF:文档频数, T C:单词权, TS:单词贡献度, 2点:
) 90%的特征。这也说明了原始特。
2) 在4种无监督聚类方法中TC 、TS 和DFFS 均能移走96%左右的单词而不降低聚类性能, 而DF 只能移走92%左右的单词, 如果再继续提取特征聚类的性能将急剧下降。从图中还可以看到在移走相同数量的单词的情况下, 用DFFS 选择的特征效果是最佳的。
由此可以看出, DFFS 通过计算特征之间的相关性来删除一些相关的特征, 取得了不错的效果。并且该方法不依赖于分类的先验知识, 具有较高的计算效率, 适合于解决文本聚类的特征选择问题, 具有一定的应用价值。
3 实验及结果分析
实验数据从I , 4本, 其中包括科技类) 、财经类(190) 、体育类(180) 、和政治类(240) 。通过DF 和DFFS 来进行特征选择, 并通过K -均值算法来实现文本的聚类, 表1给出了3组实验数据, 从中可以看出不同的特征对精度的影响。实验中采用中国科学院计算所汉语词法分析系统进行分词, 基于最大信息压缩指标计算相异度S (x, y ) , 实验结果如表1。
表1 不同的特征对精度的影响
特征数精度/%
DF 600073. 0
DFFS 3058
74. 7
特征数精度/%
305873. 5
1047
75. 1
特征数精度/%
104771. 1
350
74. 7
从表1中可以看出, 当特征数过多时反而使精度
不高, 这也说明在众多的特征中包含了大量没有类区分能力的特征。接着比较2种方法在特征数不一致的情况下的精度, 如用DF 取得6000个特征, DFFS 在此基础上又移走了2942个特征, 但是精度却提高了, 同样后面的2组数据也证明了DFFS 的有效性。最后再来比较特征数相等的情况, 表中给出了2组数据, 即特征数为3058和1047, 同样可以看出DFFS 比DF 更能提取出那些更具类区分能力的单词。从表中还可以看出用DF 来进行特征选择时, 当特征数过少时反而使聚类的性能急剧下降, 这说明在降维过程中造成数据中的分类信息丢失, 影响了聚类的效果, 而笔得提出的DFFS 方法则没有出现这中情形。
由于一般的无监督特征选择方法在移走90%的特征之后均有不错的效果, 所以图2进一步考虑了在剩下的10%特征上继续进行特征选择对聚类结果的影响情况
。
4 结束语
无监督特征选择方法一直是一个非常重要的研究课题。笔者利用DF 的优点, 引入特征相似度, 提出了DFFS 方法, 实验证明该方法是有效的。与DF 结合的方法也是一种好的思想, 目前不少无监督特征选择方法由于时间复杂度高不适合用于文本这样高维的问题, 但是与DF 结合的思想为其他无监督方法在文本聚类中的引入敞开了大门。参考文献:
[1] AGGRAWAL C C, Y U P S . Finding generalized p r ojected
clusters in high di m ensi onal s paces[J ].AC M SI G MOD Re 2cord, 2000, 29(2) :70281.
[2] Y ANG Y, PE DERSE N Y O. A comparative study on feature
selecti on in text categorizati on[C ]//Proc . of I C ML ’97. San Francisco . C A, US A:Morgan Kauf mann Publishers I nc . , 1997:4122420.
(下转第83页)
第6期 孙天昊, 等: 一种基于等效置换的协商策略83
Negoti a ti on Strategy Based on Equal 2utility Exchange
SUN Ti a n 2hao , ZHU Q i ng 2she ng, L I S hua ng 2q i ng
(College of Computer Science and Engineering, Chongqing University, Chongqing 400030, China )
Abstract:I n order t o enhance and op ti m ize the negotiati on result reached by concessinon negotiati on strategies, equal 2u 2tility exchange negotiati on strategy is p r oposed . Equal 2utility exchange makes use of the relati onshi p bet w een the Agent ’s negotiati on 2related issues of the multi 2issues utility evaluati on mechanis m. I n order t o get a better negotiati on result, val 2ues of s ome issues are adjusted dyna m ically, ensuring the utility of Agent not l ower . Then algorithm is p resented . Feasibil 2ity and efficiency of equal 2utility exchange negotiati on strategy have been p r oved by experi m ent . Equal 2utility exchange negotiati on strategy can enhance j oint utility partly and reach a better negotiati on result than concessi on neg otiati on strat 2egies .
Key words:concessi on negotiati on strategy; equal 2utility on ti m al; utility .
(编辑 吕建斌)
(上接第79页)
[3] 刘涛, 吴功宜, 陈正. 一种高效的用于文本聚类的无监督
lecti on for text clustering[C ]//Proc . of I C ML ’03. San Fran 2cisco, C A, US A:Morgan Kauf mann Publishers I nc, 2003:128.
[6] M I TRA P, MURTHY C A, P AL S K . Unsupervised feature
selecti on using feature si m ilarity [J ].3012312.
I EEE Transacti ons on
Pattern Analysis and Machine I ntelligence . 2002, 24(3) :
特征选择算法[J ].计算机研究与发展, 2005, 42(3) :
3812386.
[4] W I L BUR WJ, Y ANG Y . An analysis of statistical ter m strength
and its use in the indexing and retrieval of molecular bi ol ogy texts[J].Co mput B i olMed . 1996, 26(3) :209222.
[5] L I U T, L I U S, CHE N Z, et al . An evaluati on on feature se 2
A New M ethal Unsupervised Feature Selecti on for TextM i n i n g
HE Zho ng 2sh i , XU Zhe 2j un
a
b
(a . College of Computer Science; b . I nstiture of Language Recogniti on and I nf or mati on
Pr ocessing, Chongqing University, Chongqing 400030, China )
Abstract:A novel app r oach for unsupervised feature selecti on is p resented, denoted by DFFS, which combines Docu 2ment Frequency and Feature Si m ilarity . This method re moveds ninety percent words based on docu ment frequency, then re moveds the redundancy features according t o feature si m ilarity . K 2mean app r oach is used t o measure the superi ority of DFFS t o the other common used feature selecti on methods, such as DF, TC and TS . I n the first experi m ent, the cluste 2ring perfor mance of DF is decreased shar p ly when the feature number decreased fr om 6000t o 1047, where DFFS keep 2ing or increasing the clustering perf or mance . I n another experi m ent, with the feature number rai m ining at 10%～2%, DFFS is superi ority t o the other three app r oaches, and is apparently superi ority t o others with 2%ra m ianing features . Key words:natural language p r ocessing; feature selecti on; docu ment frequency; ter m strength; entr opy 2based feature ranking
(编辑 陈移峰)
范文四：一种基于特征聚类的特征选择方法
优先出版
计 算 机 应 用 研 究
第32卷
一种基于特征聚类的特征选择方法
王连喜a，蒋盛益b
(广东外语外贸大学 a．图书馆；b．思科信息学院，广州 510006)
摘 要：特征选择是数据挖掘和机器学习领域中的一种常用数据预处理技术。在无监督学习环境下，定义了一种特征平均相关度的度量方法，并在此基础上提出了一种基于特征聚类的特征选择方法FSFC。该方法首先利用聚类算法在不同子空间中搜索簇群，使具有较强依赖关系（存在冗余性）的特征被划分到同一个簇群中，然后从每一个簇群中挑选具有代表性的子集共同构成特征子集，最终达到去除不相关特征和冗余特征的目的。在UCI数据集上的实验结果表明，FSFC方法与几种经典的有监督特征选择方法具有相当的特征约减效果和分类性能。 关键词：特征选择；特征聚类；相关度；无监督学习 中图分类号：TP391.2 文献标志码：A
Novel feature selection method based on feature clustering
WANG Lian-xia, JIANG Sheng-yib
(a. Library, b. Cisco School of Informatics, Guangdong University of Foreign Studies, Guangzhou 510006, China) Abstract: Feature selection has become a very useful pre-processing technology in data mining and machine learning. This paper proposed a mean-similarity measure and a new feature selection method based on feature clustering (named FSFC) in the unsupervised learning. Firstly, the entire feature space is divided into a set of homogeneous subspaces when a clustering algorithm is used for the full feature set. Then the final feature set is formed by selecting some representative features from each cluster. At last, it removed the irrelevant and redundant features. Experimental results on UCI datasets show that the performance of dimensionality reduction and classification with C4. 5 and NaiveBayes obtained by FSFC is close to the several states of art supervised feature selection algorithms.
Key Words: feature selection; feature clustering; similarity; unsupervised learning
特征选择作为数据挖掘和机器学习领域中的主要预处理技术，已经成为了广大学者们研究的重要课题之一，并产生了许多有价值的成果。这些成果中的大多数研究都产生于有监督的学习环境中，而对于无监督学习环境下的特征选择研究则显得较为薄弱[1,2]。其原因在于：一方面，无监督特征选择研究是在无先验知识的指导下进行的，不利于评价特征的价值；另一方面，无监督的特征选择研究充满了较多的不确定性，得到的结果往往难以被解释和验证[3]。
聚类是无监督学习环境下的一种常用数据分析方法，其目的旨在依据相互之间的依赖程度对数据进行划分，从而帮助人们准确分析和提取隐藏在数据中的潜在规律或模式。根据这一原理，可以使用聚类算法将具有较大依赖关系(冗余度高)的特征聚集到一起。实际上，目前已有许多特征选择方法是在特征聚类的基础上展开研究的。代表性成果有：Mitra等使用最大信息压缩指标来度量两个随机变量的相似度，并以此为依据对特征集进行聚类，然后在聚类结果中选出具有代表性的特征组成特
--------------------------------
基金项目：国家自然科学基金项目(61202271)；国家社会科学基金项目(13CGL130)；教育部人文社会科学项目(14YJCZH)；广东省自然科学基金项目(S2012040007184)；广东省普通高校科技创新项目(2012KJCX0049，2013KJCX0069)；广东省科技计划项目(2012B031400016)
作者简介：王连喜(1985-)，男，湖南常宁人，硕士，主要研究方向为数据挖掘与自然语言处理；蒋盛益(1963-)，男，湖南隆回人，博士，教授，硕导，主要研究方向为数据挖掘与自然语言处理．
征子集。该方法十分经典，但是需要一个指定的期望特征个数参数K，而且该方法对不同的K值也比较敏感[4]。Ienco和Meo则依据特征之间的相关关系对特征全集进行分层聚类，然后利用包装方法从每个簇中选择出最佳的特征组成最终的特征子集。虽然该方法不需要调整任何参数，但是包装方法的引入既增加了时间开销又加入了学习算法的偏置[5]。Witten等将稀疏K-means和分层聚类构成一种特征聚类框架，该框架首先将特征全集进行聚类并划分成多个特征簇，然后利用Lasso型惩罚因子在每个簇中选择出具有代表性的特征构成最终的特征子集
[6]。Liu
等在有监督学习环境下采用凝聚层次聚类算法对特征集
进行划分，然后通过去除各个特征簇中与类别距离较远的特征的方式以形成最终的特征子集[7]。Zhao等以最大信息系数为特征相关性的度量指标对特征集进行仿射传播聚类，然后从每个簇中选取质心作为该簇的代表性特征[8]。最近，Bandyopadhyay等提出了一种融合特征聚类与密集子图发现的无监督特征选择方法，首先以密集子图的方式获取非冗余特征集，然后以规范
文章预览已结束
获取全文请访问 http://www.arocmag.com/article/02-2015-05-020.html
范文五：第一特征选择的信息论方法
第34卷第1期
2005年3月内蒙古师范大学学报(自然科学汉文版) Journal of Inner Mongolia Normal University (Natural Science Edition ) Vol. 34No. 1Mar. 2005
第一特征选择的信息论方法
杨打生1, 艾 华2
(1. 内蒙古电子信息职业技术学院, 内蒙古呼和浩特010010; 2. , 010021)
摘 要:提出一种第一特征选择的信息论方法, 息, 关键词:模式识别; ; :1001228735(2005) 012200502203
, 、提高识别的正确率、提高模式识别的实时性方面起着非常重要的作用. . 目前, 用于特征选择的算法很多, 如搜索法、实验法、相关法等. 近年来有学者借助信息论的概念进行特征选择[1], 并取得了一定的进展.
用信息论方法进行特征选择的过程中, 通常使用“至上而下”的选择方法, 首先选择对分类最有效的一个输入特征作为第一特征, 然后在已选特征的条件下逐一选择其他输入特征, 使它们的组合对分类识别最有效. 因此, 第一特征的选择非常重要, 第一特征选择的好坏可能会使特征选择的结果完全不同, 甚至直接影响整个特征选择以至模式识别的性能.
1 用信息论的方法进行特征选择[2]
为了描述方便, 先建立一个特征选择模型:设原始特征空间为FR , 包含有n 个特征, C 为分类类别. 现需要从FR 中选择k 个对分类最有效的特征, 形成一个新的特征空间S , 并要求k <>
在特征选择过程中, 可以借助信息论中的互信息作为可分离性判据. 在特征选择的信息论算法中, 目前应用较多的是“Greedy selection ”选择法, 其步骤如下:
(1) 初始化. 将原始输入特征空间FR 赋值给F , S 置空.
(2) 对F 中的每一个输入特征f i , 计算I (F i ; C ) .
(3) 选择使I (F i ; C ) 最大的那个f i , 将f i 加入到S 中, 记为{f i }→S , 同时, 在F 中去掉f i (记为F |{f i }) .
(4) 重复以下过程, 直到选够k 个特征:①对F 中的所有特征f i , 计算I (C; F i S ) ; ②选择使I (C; F i S ) 最大的那个f i ,{f i ) →S , F |{f i }.
(2) 、(3) 完成第一特征的选择, I (F i ; C ) 是输入特征f i 和输出类别C 的互信息; 步骤(4) 其中, 步骤(1) 、
完成后续特征的选择, I (C; F i S ) 是f i 和f s 与C 的联合互信息.
2 第一特征选择过程中存在的问题及改进
在“Greedy selection ”算法中, 第一特征的选择仅考虑了该输入特征和输出类别的互信息, 也就是将各个输入特征单独用于分类时对分类的有效性. 实际上, 在进行特征选择时要考虑几个特征共同用于分类时对分类的有效性. 因此, 仅按照I (F i ; C ) 最大来选择第一特征并不一定能选择出最佳的特征组.
例如, 设X 、Y 为均匀分布在[-1, 1]上的随机变量, 输出类别Z 和输入变量X 、Y 之间的关系为:
Z =
收稿日期:2004-09-22
作者简介:杨打生(1966-) , 男, 内蒙呼和浩特市人, 内蒙古电子信息职业技术学院讲师, 东南大学硕士研究生. 0 X Y >01 X Y <0.>
第1期杨打生等:第一特征选择的信息论方法 ?51?
2以X 、Y 和X Y 作为输入特征, 选择两个特征进行分类识别. 本例中Z 的取值仅与X 、Y 的符号有关, 是一个
2典型的异或逻辑. 对于异或逻辑, X 、Y 和X Y 对输出类别提供的信息是一样的, 即它们对分类识别的有效
性是平权的. 因此, 仅用输入特征和输出类别的互信息大小来选择第一特征, 选择的结果具有随机性.
就理想情况而言, 希望第一特征选择为X , 这样第二特征无论选择为Y 还是选择为X 2Y , 都可以准确判断出Z. 也就是说, 第一特征选择得好, 可以降低后续特征的选择要求. 反之, 如果第一特征不选择X , 那么第二特征必须选择X , 否则, 仅由Y 和X 2Y 是不能实现正确分类识别的.
从信息论的观点来考虑第一特征的选择问题, , 还要考虑第一特征和其他特征组合共同包含的类别信息, 组, 从而提高整个特征选择的性能. 为此, 记f i 为待选输入特征, f j 为一个未选输入特征, 用C , I (F i j C i f j 联合后与C 的互信息, 它描述了f i 和f j . i f j 的联合互信息之和
. 因此, 可以用
j (j ≠i ) j (j ≠i ) ∑I (F F j i |C ) 反映了f i 和∑I (F F j i |C ) 作为第一特征选择的判别
函数, 为此, Greedy selection ”算法中, 只需将第一特征选择过程中的I (F i ; C ) 替换为
可. j (j ≠i ) ∑I (F F j i |C ) 即
3 实验数据及结果
输出Z 和输入X 、Y 的关系由(1) 式表示. 随机生成10组数据, 每组1200点, 每组类别结果为1和为0
2的各取500点. 10组数据分别记为Y 1, Y 2, …, Y 10, 以X 、Y 、X Y 作为输入特征.
(X , X 2Y ) 、(Y , X 2Y ) 组合分类, 它们的空间分布分随机生成属于两类的数据各15个, 分别以(X , Y ) 、
别如图1、图2、图3所示. 从图中可以看出, (X , Y ) 特征组合的空间距离最大, 可分性最好; (X , X 2Y ) 特征组合的空间距离小, 但仍然是可分的; 在(Y , X 2Y ) 这种组合中, 两类在空间中是不可分的. 这与前面的分析
2
一致, 按对分类的有效性排队, 它们依次为X 、Y 、X Y.
图1 X —Y 的空间分布 图2 X —X 2Y 的空间分布 图3 Y —X 2Y 的空间分布分别以I (F i ; C ) 和
j (j ≠i ) ∑I (F F j i |C ) 为判别函数对Y 1, Y 2, …, Y 10进行第一特征的选择, 选择结果见表1.
j (j ≠i ) 表1 分别以I (F i ; C ) 和
判别函数
I (F i ; C )
j (j ≠i ) ∑I (F F j i |C ) 为判别函数的第一特征选择结果Y 4Y 5Y X Y 6Y X Y 7Y X Y 8X X Y 9X 2Y X Y 10Y X Y 1X 2Y C ) X Y 2X 2Y X Y 3X X X 2Y X ∑I (F j F i |
?52?内蒙古师范大学学报(自然科学汉文版) 第34卷 由表1可以看出, 用
j (j ≠i ) ∑I (F F j i |C ) 作为第一特征选择的判别函数选择性能更为理想.
参考文献:
[1] Guyon I , Elisseeff A. An introduction to variable and feature selection [J].Journal of Machine Learning Research ,2003,
(3) :1157-1182.
[2] Nojun Kwak ,Chong 2Ho Choi. Input feature selection for classification [J].On Neural Net 2
works ,13(1) :2002,143-159.
[3] 吕锋, 王虹, 刘皓春, 等. 信息理论与编码[M ].北京:[4] 边肇祺, 张学工. 模式识别[M ].北京:[5] 吴湘淇. 信号、M 北京:Selection Met hod Based on Mut ual Information
YAN G Da 2sheng 1, A I Hua 2
(1. I nner Mongolia Elect ronic I nf ormation V ocational Technical College , H uhhot 010010, China;
2. Facult y Economics I nner Mongolia Universit y , H uhhot 010021, China )
Abstract :The met hod for first feat ure selection based on mut ual information is proposed wit h consid 2ering of t he joint mut ual information between outp ut classes and joint inp ut feat ures. This met hod works well even in nonlinear classification problems.
K ey w ords :pattern recognition ; first feat ure ; selection ; mut ual information
【责任编辑陈汉忠】
(上接第49页)
St udy of t he Technique for Embedding and Arranging
Vertically of Mongolian Characters in Web Pages
L I Hai 2zhu
(A rts College , I nner Mongolia Universit y , H uhhot 010022, China )
Abstract :The technique for embedding and arranging vertically of Mongolian characters in web pages is discussed. The Mongolian web pages can be developed by aligning Mongolian characters vertically wit h t he help of CSS techniques and can be searched and up dated easily.
K ey w ords :Mongolian web pages ; Mongolian character typefaces ; embed ; align vertically
【责任编辑陈汉忠】
