资源目录
压缩包内文档预览：
编号：21099956
类型：共享资源
大小：6.51MB
格式：ZIP
上传时间：2019-07-23
上传人：远***
认证信息
个人认证
蒋**（实名认证）
广西
IP属地：广西
20
积分
- 关 键 词：
-
基于粗糙集的数据挖掘方法
数据挖掘方法
基于粗糙集的
的数据挖掘方法
粗糙集的数据挖掘方法
基于粗糙集方法的数据挖 掘
- 资源描述：
-
基于粗糙集方法的社交媒体数据挖掘,基于粗糙集的数据挖掘方法,数据挖掘方法,基于粗糙集的,的数据挖掘方法,粗糙集的数据挖掘方法,基于粗糙集方法的数据挖 掘
- 内容简介：
-
青岛理工大学实习信息反馈表院（系）名称： 专业： 班级： 组别： 人数： 实习性质： 指导教师（工程师）： 实习起止日期： 年 月 日至 年 月 日 实习基地（实习单位）名称： 项 目条 款实习单位评议情况填表说明实习指导书的质量1、针对性如何好、较好、一般、差注：1、实习单位按实习准备、组织管理、实施过程的具体情况，在左栏诸项中划勾进行评议。2、欢迎对我校实习情况提出宝贵意见及建议。3、此表一式三份，实习完毕后，由带队老师带回或由实习单位直接邮寄，由院（系）签署处理意见后 ，交教务处实践教学科一份，另院（系）、教研室各保留一份。4、是否实习基地请标注。2、是否适应当前专业发展是（较好、一般）、否3、能否体现理论与实践结合能（较好、一般）、否学生实习情况与质量1、能否完成安排工作能、否2、完成效果如何好、较好、一般、差3、完成岗位工作的质量如何好、较好、一般、差学生实习态度及纪律1、实习中认真刻苦情况好、较好、一般、差2、遵守厂规、厂纪情况好、较好、一般、差3、是否听从岗位安排是（全部、部分）、否4、深入生产第一线情况全部、部分、无5、向师傅虚心请教情况经常、较少、无6、有无迟到、早退或旷工情况多、较多、偶尔、无学生能力素质1、独立发现、解决问题的能力情况好、较好、一般、差2、创新性和开拓性如何好、较好、一般、差教师指导工作情况1、指导工作细致与否好、较好、一般、差2、工作责任心情况好、较好、一般、差3、指导能力与方式好、较好、一般、差实习组织管理工作1、准备情况如何好、较好、一般、差2、安全防护工作如何好、较好、一般、差3、组织安排是否科学有序好、较好、一般、差4、管理工作如何好、较好、一般、差5、是否按实习计划安排进度是、否实习基地（单位）其他意见及建议、改进措施： 实习单位代表签字： （ 公 章 ） 年 月 日（院）系处理意见： 负责人签字： （ 公 章 ） 年 月 日实习学生签名：年 月 日 青岛理工大学毕业设计（论文）任务书院 （系）： 理 学 院 专 业： 数学与应用数学 学生姓名： 陈萌 学 号: 201201140 设计(论文)题目： 基于粗糙集方法的社交媒体数据挖掘 起 迄 日 期: 2016年3月-6月 设计(论文) 地点: 校内/校外 指 导 教 师: 高峰 教 研 室 主 任： 高峰 发任务书日期: 2016 年 3 月 10 日毕 业 设 计（论 文）任 务 书1本毕业设计（论文）课题的目的和要求：本文提出一种基于粗糙集理论的web文本分类模型，该模型从已分类的训练文本出发，建立一系列不同层次的文本分类子系统，利用Rough Set理论有效处理不精确、不确定、含糊信息的特性，对分类决策表进行属性约简，并推导出社交媒体文本分类的规则集。 有别于传统的对关键字频度进行累加的方法，本文提出基于信息熵的文本关键词测度函数，通过对关键词函数值进行比较，获取对文本分类最具影响性的关键词序列；同时，针对社交媒体上异质、非结构化信息的特点，该分类算法考虑超文本标记对关键词权值的影响。基于对所获实验材料的社交媒体文本分类实验，实现相关的社交媒体文本挖掘算法，对提并出的算法进行实验分析。2本毕业设计（论文）课题的技术要求与数据（或论文主要内容）：通过查阅相关文献与资料，较为全面地了解、概括、总结文本自动分类方法，基于粗糙集的约简算法实现性能优越的中文文本分类系统。主要内容：1. 介绍中文文本分类主要方法及国内外研究现状。2. 介绍粗糙集理论以及基于粗糙集的约简算法。3. 发展基于粗糙集理论以及基于粗糙集的约简算法实现社交媒体文本挖掘。毕 业 设 计（论 文）任 务 书3对本毕业设计（论文）课题成果的要求包括图纸、论文、图表、实物等：要求设计基于粗糙集方法的互联网社交媒体文本挖掘方法，借助matlab实现数值试验，并以论文的形式提交。4主要参考文献资料：123456789101112毕 业 设 计（论 文）任 务 书5本毕业设计（论文）课题工作进度计划：起 迄 日 期工 作 内 容2016年第1周第2周第3-4周第5-8周第9-10周第11周第12周 研究任务书查阅整理参考文献构建论文主体框架整理分析资料，算法设计、数值试验初步完成论文审阅及修改论文完成论文、准备答辩教研室审查意见：负责人： 2016年 月 日院（系）意见：院（系）负责人： 2016 年 月 日青岛理工大学本科生毕业设计（论文）选题、审题表 院（部）理学院指 导教 师姓 名高峰专 业数学与应用数学职 称副教授申报题目名称基于粗糙集方法的社交媒体数据挖掘题目类型ABC题目来源ABC课题简介：本文提出一种基于粗糙集理论的web文本分类模型，该模型从已分类的训练文本出发，建立一系列不同层次的文本分类子系统，利用Rough Set理论有效处理不精确、不确定、含糊信息的特性，对分类决策表进行属性约简，并推导出社交媒体文本分类的规则集。 有别于传统的对关键字频度进行累加的方法，本文提出基于信息熵的文本关键词测度函数，通过对关键词函数值进行比较，获取对文本分类最具影响性的关键词序列；同时，针对社交媒体上异质、非结构化信息的特点，该分类算法考虑超文本标记对关键词权值的影响。基于对所获实验材料的社交媒体文本分类实验，实现相关的社交媒体文本挖掘算法，对提并出的算法进行实验分析。设计（论文）要求及应具备条件：论文要求1. 介绍中文文本分类主要方法及国内外研究现状。2. 介绍粗糙集理论以及基于粗糙集的约简算法。3. 发展基于粗糙集理论以及基于粗糙集的约简算法实现社交媒体文本挖掘。要去具备文献搜集能力，计算机编程能力。教研室主任意见签名： 年 月 日 院（部）意 见签名： 年 月 日选题学生姓名：陈萌 班级：数学121 学号： 201201140注：题目类型： A工程设计 B 应用研究 C理论研究题目来源： A科研、工程实际题目 B有科研、工程实际背景的题目 C自拟题目填表说明1、 该表的填写只针对1名学生做毕业设计（论文）时选择使用，如同一课题由2名及2名以上同学选择，应在申报课题的名称上加以区别（加副标题），并且在“设计（论文）要求”一栏中加以体现。2、 “题目类型”一栏： A 工程设计 B 应用研究 C 理论研究3、“题目来源”一栏：A科研、工程实际题目 B有科研、工程实际背景的题目 C自拟题目4、“设计（论文）要求（包括应具备的条件）”一栏：“要求”主要指本课题技术方面的要求，而“条件”指从事该课题必须应具备的基本条件（如文献、仪器设备、材料、预做、工作地点及学生须具备的技能）中文文本分类特征表示及分类方法比较研究周雪忠方青 吴朝晖浙江大学计算机学院杭州3 10027Email:厦z x z,斤e n严它hc s.为u .ed u.c n文摘:本文就目前基于词频表示的中文文本分类实验结果缺乏可比性的情况,结合中文文本分类的字/词频特征向量和经典文本分类方法如吓mF瓜o e ehio、Na i veB盯es、s印即r tv eetorMa比in e s(SvM)等进行了系统的可控比较实验。实验表明,Na i veBa ye s在词频向量 上的性能最差(不 超过8 1.8 0%);sV M的综合 性能最好,平均分类准确率达到 8 2.6 0%(三种特征表示);而T FI DF/ R o cch i。结合中文词频特征时,取得 了最好 的性能(达到8 7.5 9%);字频特征在 小样本时比词频特征更好,不同的分词处理方法直接影响分类性能。关键词:文本 分类,特征表示,比较研究A ComPa r ati veS tud yo nT extRePresentationandCla ssif ier sinC hine seT extCategorizat io nZ houX ue山ongFa ngQingW血Zha oh uiCollegeofComPute rseie n e e,Zhe jia ngUniv er sit y ,Hangz ho u3l002 7Email:zx z,f ye n,wZhe s.Z Ju.ed u.e nAbstra et:D uet othela ekofeom Pa r ahv e st u勿o nword ba sed Chinesetex tela s sif ie atio ninthePr eviou sr ese areh,th isPa PerProPosesaeont rol lede omParativeChine setex tclas si f iea t ionexPer imento neombiningeharaeter / wo rdr ePre se nt atio na ndela ss一e alelas sif ie rssu ehas开ID F瓜o e ehio、Na iveBa yes、SuPPor t.V eetorMaehine s(SVM)ete.It15showedthatwor dba sedNa i veBa yesha swo rstPerf or ma n e e(notex ee ed81.80%);SVMha stheove rall be stPedbr ma neeo nthre edif f erentf eat u rer ePr ese ntat io n s,ofw hieht heav e rageae eu raey 1582.6 0%.It15intere stingthatT FID E卫o e ehioha sthehig he stPer f or ma nee(87.5 9%)w he ne ombin edw ith wo rdr ePr es ent a t ion.Cha r aete rshowsbet t erPer f or ma neet ha nwor do nsmallt r ainings et,and t hewordseglllen t at io nal gor ithmswo uldaf f eet theaeeu ra eyofre xtela s sif ie rs.Key words:介xtCat egor iz atio n,Re Pr ese nt ation,ComPa r at iveS切dy引言文本分类 作为非结构化文本信息的 内容管理和组织技术已经得到广泛的研究和利用【 l 【习 9 川【】2 1 13 。简单地说,文本分类就是对一定领域的自山文本 自动分配一个或多个类标记本文承国家97 3重点基础 研究发展规划项目(项目号G 19 9 0544 5m的资助。454.的过程。而在9 0年代引进机器学习方法之后,其文档与类别的关系模式是通过对文档样本(经验数据)的机器学习而得到的。就目前的文本分类研究认为,支持向量机( suppo r tv ec to rMacl iine)是分类准确度最高的方法 912 13 ,但其分类速度很慢。比较西文文本分类研究,中文文本分类研究的重要内容之一就是文本的特征表示问题。文本的特征表示一直是中文信息检索的研究热点 5】 9J。中文信息处理的基础是分词,一般的文本分类也不例外,根据西文 研究的结果发展起来的中文文本分类也以词特征为最基本的文本模型表示基础。分词的处理及标准的语料集对中文文本分类研究非常重要,但在大部分的研究中根本未提及分词算法及其效率、没有标准的语料集【1 1叼。本文从文本分类高维性和中文信息处理的特点,对基于中文字、词特征及相关经典的文本分类进行了系统的比较研究,由于没有标准的中文文本分类语料集,为了能有一定的可比性,本文还给出了对照的在英文标准语料集 2 0Newsg r ou Ps上的各分类方法的实验结果。通过比较实验表明:l )字是中文文本分类的有效特征表示,特别是在小样本的情况下,字频特征比 词频特征能提供更好的分类信息;2)分词算法直接影响中文文本分类的性能;3 )在中文文本分类中,快速、简单的方法TF ID F瓜o c c hi o取得了不错的性能;4)Na i veBa ye s对样本训练集很敏感,SVM在单标签文本分类中具备最好的分类准确率。本文的后继内容按如下安排。第二节介绍中文文本分类的相关工作;第三节介绍本文采用的文本分类方法;第四节给出实验设计并分析实验结果:第五节是结论和展望。二.相关工作中文文本分类研究多集中在基于词向量的特征抽取方法或分类方法的研究【l 【 3 1【14,其实验结果也未提供具体的分词算法和分词的准确率等数据。虽然文本分类对分词 的准确率要求没有句法、语法分析及机器翻译(9 9.9%)等这么高,但分词的准确率能非常大的影响信息检索的性能 51。己有不少针对信息检索的特征表示研究 5 9 1。在2 1中采用基于字特征基础上的混合特征进行文本分类取得了好的性能。字频 向量的中文文本分类在15 1中作了初步的研究,其采用最小线性二乘方估计方法( Le as thn ea rSq ua r eF it ),在对字特征进行一定筛选预处理(包括频度、集中度及广度)的基础上,在4% 篇文献样本,七个类的测试 中获得了8 7.4 5%的准确度15 )。但没有进行必要的比较研究。本文在分析中文文本特点的基础上,着重对基于字、词表示的中文分类研究,给出 了系统的可比较的实验结果。首次对字、词特征表示与相应的经典分类方法的结合的研究,并比较了不同的分词算法(双向最大匹配算法与正向最大匹配算法)的词频特征分类性能的差异,指出了分词算法对词频特征分类的影响。三.文本分类方法3.1.Na iveBa yes贝叶斯分类器是一种简单的分类方法,在机器学习中有广泛的研究,也在文本分类中广泛的采用。它的基本思想就是运用词和类的联合分布( 训练阶段)来估计给定文档对于类的概率(铡.455.试或预测阶段)。Na i veBa ye s方法假设词 的分布是相互独立的。独立性假设使得Na l veBa ye s方法具有较小的计算复杂度(非Na i veBa ye s方法的计算复杂度是指数级的)。当然N滋v eBa ye s方法的性能不是很好。它有多种版本的N B分类器,如多项式混合模型等,本文只采用最基础的朴素贝叶斯分类器。定义C二c:,cZ,c、是k个目标类的集合,定义砰=w l,姚,巩为类集合C中的词特征集合。给定新的文档d,则文档d属于c类的概率有如下计算公式给出:P ( c/d )一翌e )刀(c,P(d)(3.1)根据词关于类分布的独立性假设,通过如下 公式计算文档d的最可能类:。* ( y t一娜咚冰/介冰)你咐/。产气3.2 )其中n (哄,d)代表文档d中词w出现的词频,而尸(琳/c l )一般通过如下公式(拉普拉斯分布)最大似然估计学习得到:尸(w,/c ,)=l+艺,。,n(w,d,)”十艺几,艺,。,”(w t,心)(3.3)类的概率P(c)由最大似然估计确定e,PLc:,二飞二一下一于一丫乙jcJI(3.4)3.2.TFIDF/Roe ehioT FI DF /Ro cc hi o分类方法是继承至信息检索Ro cc hi。关联反馈算法的文本分类方法,它通过构造一个类的原型向量表示,并计算测试文档向量与该类原型向量的相似度来达到分类的目的。设类原型向量c=( w1,wZ,w;:,) ,其中:。,wk j,竹尸二二D.2一一厂2几毋一101,CI一心E尸。戈IJ以口i!鸽已月v石G ilw勺刀石G(3.5)其中刀与r可调整正样本和负样本对原型向量的作用(本文实验中刀与z的取值分别为5和I ),尸O S,表示类C,的正样本集合,反之N EG,表示负样本集合,文档的 词特征丁F IDF权值w芍=T F(w、,d,).I D F(”,、)T F(w、,d,)及I D F(, 、1、)在11中有详细 的定义则测试文档d,的分类判别可简单的采用如 下 公式:456H刀勺D F=a r gma x价cCdj.c idjl 卜 Ic ,(3.6)3.3.SuPPor t决etorMa eh ine(SVM)svM是由Jo a c h毗最早运用于文本分类的9 ,而nnge ta l.也把SVM与其他文本分类的方法进行比较【13 ,这些研究实验表明SVM是迄今为止分类性能最好的文本分类器,其唯一的缺点就是训练速度很慢。SVM 是统计学习理论基础上的新兴的机器学习方法,它基于结构风险最小化( st r uct Li re拓s kMinjm让a t io n)原则。其基本出发点就是控制学习机器的经验风险和推广能力,从而达到最小的实际风险。对推广能力的控制通过一个称为最优分类超平面的机制来实现。设一个N维的超平面a,它能以最大的可能间隔分开正样 本和负样本数据,则叮被称为N维最优分类超平面。如 图(F ig.l ) 所示(线性可分情况),a就是最优分类超平面,而之不是最优分类超平面,红颜色的正负样本点称为支持向量。支持向量是各类样本的边缘 向量,由此可见,支持向量使基于边缘(弱)特征的分类方法。Fig.1S vM的最优分类超平面c T示意图更准确地说,设D=y,又、是训练集,其中牙是样本向量,y任王十l ,一1是类标签,表示正样本,一1表示负样本,则对线性可分情况,SVM 就是找到合适的汤(使)和b,满足如下公式:汤又,一b七+ly=+l(37)命又,一b一1夕,二一1( 3 .8 )对于非线性可分的情况,SVM通过不同的核函数如多项式、径 向基函数(RBF )和S igmo id函数来实现线性空间到非线性空间的映射。Jo a c hims指出现有的文本分类语料集都是线性可分的5 。本文采用线性SVM进行文本分类。.457.四.试验设计及结果分析4.1.语料集中文语料集是从中科院下载的文本都是新闻电讯稿,绝大部分采自新华社,还有20 0余篇采自中国新闻社和人民日报,总共2513篇文档。所有的新闻稿都由领域专家事先进行分类,按照中图分类法分成政治、经济、军事等共 3 8类。由于不少类如数学、材料和机械等类的语料不到2 0篇,所以我们抽取其中1 6个至少大于5 0篇的类如体育、经济、军事、水利等类别作为测试的语料集,总共166 4篇,建模得到的字特征模型字数为394 5,对应 的词特征模型词数为2200 0左右 (双向最大匹配算法(FMM+ BMM)及正向最大匹配算法(FMM)。该中文语料集相对比较小,属于小样本的情况。我们对测试集和 训练集进行了不 同比例的分割(0.1一0 .9),即测试集分别是10%与9 0%,并随机分割类内文档,每次分割的测试集进行1 0次测试,取平均值得到试验结果。为了增加实验结果的通用性和可比性,本文实验未采用任何特征抽取或选取方法。4.2.评价标准本文采用的性能评价标准是微平均准确率(Micr oAc cu ra cy)。设C是样本的类别数,C表示属于第i类的测试样本文档数,H。表示属于i类的样本被归类为第j类的数目,则第i类的准确率值的计算公式为:HAe c(i)=一-二:(4.1)砚微平均准确 率 为:几 么咬(C)=艺拭艺:C生竺创-一-二(4气,I=侧为了提高本文 的实验的可比性,我们在20Newsg r o叩s上分别 对本文的三种分类方法做了实验。Zo Newsgroups山Lang创建和收集被广泛使用 的语料集之一l12。在2叭ews歹o ups上20个类,按l/ 3划分测试集与i )l练集,SVM、T FIoF瓜o c ehio和NalveBayes的微平均准确率分别是8 3.4 6%、8 1.54 c y 0、5 2.15%。没有采用任何特征选取 和抽取方法。4 .3.实验结果及 分析本文对中文分类研究进行了基于字、词的对 比研究,在词特征的处理中,考虑到不同分词算法及其性能影响,采用 了最普遍的正向最大匹配算法及双向最大匹配算法(具有一定的交集型歧义处理能力)。以下 各 图(F ig .2,3,4 ,5,6,7 )数据表明:l )以字频向量为基础的线性SvM取得最好的性能,最好 MA值达到8 6,0 5%。Na iv eBa ye s与T FIDF/Ro c ehio相 差无几。2 )词频特征表示的TF IDF /Ro cc hi o的分类准确率相.1好.甚至在测试集相对充分的时候高于SVM 的性能取得所有分类方法的最高准确率8 7.5 9%。山此表 明,应根据不同 的.458.语料集,采用不同高性能的分类方法,分类方法的性能并不是绝对的,而是与语料集有关。3 ) 特征表示和分类器的结合实验中,其中T F I DF 服o c c h io ( w ) 取得最好的分类效果,S V M( W ) 次之,N a lveBay e s ( W) 的性能最差。本图中的词频是基于F MM+ BMM方法得到的。4 ) N a 计e B a y e s在字频特征的时候取得最好的性能.不同的分词算法F MM和F MM+ B MM处理得到的词频特征在三个分类方法性能上都表现出明显的差异。.;骊鲡 耐23 56 789!Fi g . 2 基于字频特征的三种分类方法的微平均准确率( MA )叮一一一一一一,_9 0 1 ,三州,一七纽一一币- 一一一一一一-一一一一一一- 一一一目- 习l8 0 1州.卜拭. 卜嵌. 卜七J .卜, J . , 卜扁月盯飞二. 卜7 0 日.卜书. 卜魂i月卜书恤卜4:. 卜吮. 卜4 褚. 卜妇. . 一-.一一_;一6 0 日.卜翎亥翔卜J; 黔卜4 沮卜J 鑫. 卜J. 卜4 . 卜进. 卜. U l 口Na工veBaves 5 0 日粗曰1 . 曰粉曰凄.曰狙曰之. 曰; . 卜谁沮曰一H 旧T FI D FR occhl。 I O H 黯卜粗卜奉. 卜魂; 口卜J 轰. 卜月-. 卜. 卜. 卜J. 口 。,、,3 0 H 粗卜沮卜绍鬓. 卜翎署.卜4 起卜4丫. 卜J . 卜J . 卜.该. 目匕二一一一-一一- 一一一O H 拳.卜; . 卜翔卜; .卜粗卜者. 卜J 芬. 卜J . 卜J.一一0 曰落.卜组. 卜刁. 卜组.卜粗卜刁葵. 卜J . 卜J . 卜J.一一一.123一6 789一F i g.3 基于F MM十B MM分词算法的三种分类方法的微平均准确率( MA)一一一一- -一一一1 0 0尸-,喇.,.一- 一9 0 1 ee二吮亡-,二一南一-一一-一一,-林,一一一一一- 一一一司l一8 0 性甘旧H . 门H 甘柑H 盯旧H知心扫坛国利队抽卜住, 盯七一一 口r F I DF/尺oCehio(W ) -一7 0 汁. l .H . l . 月.1 . 只. 1 . 目. 1 . 目口1. 目. 1 . 目.甩目门月翻.,t,、二。、。洲1 1 1 1 1 1 1 1 1 1 姗 1 8 1 收1 6 1 1 1 1 1 1 1 1 1 旧1群黑黑C ”生O 片. 1 .月. 旧以.旧、目. 1 . 目. 1 . 目. 1. 目. 旧封.旧日. 旧卜i 口入a二veBa、。:女w、l 3 丈) 比. 旧H . 旧H .旧衬. 旧月. 旧目. 1. 目. 旧目.旧目. 旧翻. S V M(C )l: 1 J l目一I J I 日I l 日l I 抖1 1 1 朋11 日l l 目l l 目l 旧l一12飞15 6了8 9F i g.4 字词频比较实验三分类方法的微平均准确率.4 5 9. 撅撅口口NalvcBayc s(C) ) ). . .XB(F邓丁) ) )口口NB(FM”,BMM) ) )自曰0八曰八UO日0n U n UC甘QO C 工JI 右U工n月注j 勺,太56789Flg.5 NalveBaye s特征 表示及 分词算法L匕较l l l l l l l l1 1 1. . . 撇撇撇撇撇撇撇撇撇1 1 1 l l l/ 日0八曰( )0Cl l八U八曰0八曰八曰门OJRl匕匀JqCq J白z123456789一一一一一一一一一一一F ig.6 SVM特征表示及 分词算法 比较口口TFIDF/Ro eehl o(C) ) ). . .TR(FMM) ) )口口TR(FMMBMM) ) ) 藉藉藉藉藉藉藉藉藉藉藉藉藉藉藉藉1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1nn0 OC目nC八曰n0 0日qn八月 匕尸OJ组工今J q 白l34567吕Fig.7 T FI n F/Ro e chio特 征表示及 分词算法L匕较五.结论与展望文本特征表不 是中文文 本分类 的重要研究内容,字、词特征是 中文 分类研究中的主 要表 示方法。字特征有着维 数相对 固定,相对较低 的特点,而问特征内容复杂多样,维数很高。本文460结合特定的分类方法。对字词特征的表示进行了系统的研究。在实际应用中可结合特征表示和分类方法,如采用简单、低维的特征表示和复杂的分类方法(字特征十SVM),或者采用相对高维的特征表示和简单的分类方法(词特征十TFI DF瓜o cc hio )可得到理想的分类性能要求。虽然从实验结果来看,分词算法能一定的影响文本分类的性能,但简单高效的算法如双向最大匹配算法(FMM+BMM)己经足够。参考文献l.A二H了几na nd P .Y u,ACom pa r at iveSt ud yo nc h in eseT extcat e go n zat ionMet ho d s,p狱CAIZ00 0w o由hopo n介xta ndw七bMining,Mel bou me,P P.24一35,Aug ust2 0( X ).2.c.K.P .w ong,R -W .P Lu k,K.Ew ong,K.L.Kw ok,T extcat e即r iz at ionu singHyb r id(Min ed)T er m,Pro ee edin gsofthef if t hinter na tlo nalwor k shoPonInf or ma tio nret r iev alw ithAsia nla ng uages,Page s:217一2 18.Nov ember2000,Ho ngKo ng,C h一n a3.D IAOLi一11,HUK e.y Un,LUY u一ehang,sH ICh u n一勇,I呷r ovedst Umpscomb in edbyBoo singf orT exCategonz at io n.Jo ur nalofSof iwar e,V ol.13,N O.8,Pa ge s:1361一07.4.Fa b面ose ba stia ni,MaehineLe ar n mgi nAu to m at e dT ex tcategor is a tion.CMeo帅u ting sur v eys,v ol.34,No1,Mar c h200 2,p p.1一47.51.Jia n.、 恤nN ie,Jia ngf engGa o,Jia nZ ha nga ndMingZ ho u,O nt heU seof认 / ordsa ndN -脚msf o rChin e seIn丘川matio nRe苗e va l.PrO Ce edingso ft hef i仙intema t ion alwo改shO Po nInf onnationr et r ie valw it hAsia nla ng ua ges,Pa ges :14 1一148, N o vembe r ,20 ( )0,HongKong,China6.f yh -Jo ngT s盯a ndJ ing一Do o认/ ang,I叮甲ro v mgAuto ma t iec hi neseTextCa tegor i za tio nbyEr r orCor r ect io nPr oee edi ngs oft恤sthIn temation alWbr k sh OP玩f or ma t io nR et r iev alwi t hAsia nLan即嗯e s.Zo oo,Nov emb e rHogKo ng,Chin a.Pages:l一8.7.Jia一Y unN ie,Ma r t inBr isebeis火iaobo砒n,onehineseT ex t砒t r ie val,sIGI R96,pages:22 5一233.8.Lewis,D.D,Repr ese nt a tio nQu al it yinT ex:c la ssif ieaho n:A nIntro duet ionandEx Per iont.pr oe eed ingsofaSPe eeha nd Nat Ur alLa ng uageW匕r kshoPPages288一2 95.19 90,H iddenV al le y ,Pennsylvania.L SA.19.KL.Kw ok,ComPar ingRepr e se ntarionsinC hine seInf or ma tionRet r ieval.SIGIR97,P AGES;34礴l,phila delp hia.Penn sylvania,UnitedSta te s-101.Thor ste nJo a ehims,T extCateg or iz atio nwithSu PPor tV eerorMa ehine s二Lear ningwithMa nyRelevaotFeat ure s,Pages:13 7一142.P ro e eedings of ECML一98.1 1.Thorste nJoaehims,APr obab ilistieA nal ysisoftheRo eehioAlgor it h mwit hTFIDFf orT exrCa tegor izatio n.Page s :143一151,Pro e eed ings ofICML一97,14thIn ter natio nalConf eren e eonMa chin eLe aming.12.矶ming 、 恤ng,AEv aluat ionofSt atistie alAp pr oa ehestoT extCategor iz at io n.Jo ur naloflnf or ma t, o nRet neval,V ol1 Nol/2.6 9一90.13Y im in gY anga nd XinL iu,Ar e一e x am in at ionofte xte atego二at ionmethod s.ProeeedingsofSIGIR9 9,Pages.42一一49.1 4.解冲锋,李星,基于序列的文本 自动分类算法,软件学报,V ol.1 3.No .4 .O783一。7.15 .曹素丽,曾伏虎,曹焕光,基于汉字字频向量的中文文本自动分类系统,山西大学学报、自然科学版)22( 2) :l料一14 9,199 9.(161.ht t P:/w w w一2.e s.cm u.e蒯一m Cc allu爪bow /461基于粗糙集的属性约简算法 夏春艳1 李树平2 刘世勇3 牡丹江师范学院 计算机科学与技术系，黑龙江省牡丹江市 157012 The Approach for Attributes Reduction Based on Rough Set Theory Abstract：This paper researches attributes reduction of Rough Set Theory. Put forward a heuristic attribute reduction algorithm based on the table of compatibility information and incompatible information at same time. The experimental results show that the algorithm is verified to be more feasible and effective. Key words： Rough Set Attribute Reduction Attribute dependencies 摘要： 本文主要研究基于粗糙集理论的属性约简算法。 提出了一种同时适合于相容信息表和不相容信息表的启发式约简算法，并通过算例验证了该算法的可行性和有效性。 关键词： 粗糙集 属性约简 属性依赖度 中图分类号：TP311 文献标识码：A 0 引言引言 粗糙集理论是由波兰华沙理工大学Z.Pawlak教授在1982年提出的， 是一种研究不精确、不确定性知识的数学工具1。该理论已经在数据挖掘、机器学习、过程控制、决策分析和模式识别等领域得到了广泛的应用， 并取得了良好的效果。 属性约简就是在保持分类能力不变的前提下， 通过对知识的化简导出问题的决策或分类规则， 是粗糙集理论中的一个重要研究课题2。它的意义在于可以删除冗余信息，形成精简的规则库以便人们(或者机器人)作出快速、准确的决策。高效的约简算法是粗糙集应用于知识发现的基础，但属性的最小约简仍是个 NPhard 问题。 目前，国内外已有很多关于属性约简的算法，如吕静3基于分明矩阵的属性约简算法，胡可云4基于属性频率的约简算法等等，这些算法简单、迅速并具有较好的属性约简效果。但是， 这些算法都是根据区分矩阵先求出属性的核， 然后在核的基础上逐步扩展求出属性约简。 而通过区分矩阵计算核的方法只能适合于相容信息系统， 对于不相容信息系统则不适合。本文为适应不相容信息系统， 给出对于相容和不相容信息系统都适用的求核方法， 并根据属性的重要度提出一种启发式属性约简算法。 实例证明， 本算法在相容与不相容信息系统中都能求出属性的核，并能得到属性约简的较好结果。 基金项目：申请人：李树平；项目名称：基于粗集理论的属性约简算法的研究 基金颁发部门：黑龙江省教育厅;编号：11531389; 牡丹江师范学院科学技术研究基金项目：项目名称:不分明度量理论（NO.KY2008007） 1 粗糙集基本概念及相关定义粗糙集基本概念及相关定义 定义 1.1 信息系统 S=(U,A,f,V)，其中 U 为域；A 是有限属性集，分为条件属性集 C和决策属性集 D，即 A=CD，CD=；V 是属性集 A 的值域；而 f：AV 是从属性到值域的映射；信息系统常略写为(U,A)。 定义 1.2 设 R 是 U 上的等价关系，若 PR 且，那么P（P 中所有等价关系的交集）也是一个等价关系，称为 P 上的不可区分关系,记为 ind(P)。U/R 表示 R 的所有等价类构成的集合，xR表示包含元素 xU 的 R 等价类。 定义 1.3 对于一个知识系统 S=(U,V,f,R)，PR，不可区分关系可用如下表示： ind(P)=(x,y)UU pP, f(x,a)= f(y,a) 如果(x,y)ind(P)，则称 x 和 y 是不可区分的。符号 U/ind(P)表示不可区分关系 ind(P)在 U 上导出的分类，可简记为 U/P。 定义 1.4 给定知识库 S(U，R)，对于每个子集 XU 和一个等价关系 RIND(S)，定义两个子集： /|RXYU R YX=U /|RXYU R YX= IU 分别称它们为 X 的 R 下近似集和 R 上近似集。集合()RBNXRXRX=称为 X 的 R 边界域()RPOSXRX=称为的 R 正域；()RNEGXURX=称为 X 的 R 负域。 定义 1.5 令 P 和 Q 为 U 中的等价关系，Q 的 P 正域记为 POSP(Q)，即 /( )PX U QPOSQPX=U 定义 1.6 知识的依赖性可形式化地定义如下： 令 S （U， R） 是一个知识库， PR,QR，则知识 Q 依赖于知识 P（记作 PQ）当且仅当 IND(P)IND(Q)。 令 S（U，R）为一知识库，且 P，QR，当 kP(Q)|POSP(Q)|/|U| 我们称知识 Q 是 k 度依赖于知识 P 的，记作 P kQ。系数P(Q)可以看作 Q 和 P 间的依赖度。 定义1.7 令C为条件属性的集合，D为决策属性的集合，在已知条件属性R的前提下，一个属性aCR关于决策属性D的重要度定义为： SGF(a，R，D)R|a|(D)R(D) 2 启发式约简算法启发式约简算法 计算属性的最小约简已被证明是 NP-hard 问题，为降低约简的复杂性，并获得较优的结果，应采用启发式算法。为此，粗糙集提出了核的概念，核是所有约简中不可缺少的属性。而利用区分矩阵求属性的核只适合于相容决策表， 为此给出对于相容与不相容信息系统都适合的求核方法。 对于一个信息系统 S=(U, V, f, Ad)，如果去掉某一属性 a 其正域发生变化，即 (A-a)A( )( )POSdPOSd 则说明属性 a 是核属性。因为，决策属性 d 的 A 相对正域是 U 中所有根据分类/A 的信息可以准确地划分到d的等价类中去的对象的集合。 当去掉某一属性a后， 决策属性d的A-a相对正域发生变化，也就是说明 a 在 A 中是必要的，即属性 a 是核属性。反之， (A-a)A( )( )POSdPOSd= 则说明属性 a 不是核属性。 算法思想：首先，利用相对正域求出相容与不相容信息系统的核。然后，以属性的依赖度定义属性的重要度， 根据属性重要度为启发信息， 依次选择属性重要度大的属性加入约简集，直到满足终止条件为止，假设依赖度阈值。 算法如下： 输入：决策表系统 S=(U,V,f,Ad) 输出：属性约简 Red 1 CORE(A)= ; 2 For each aA 计算相对正 POS(A-a)(d) If（POS(A-a)(d) POSA(d)） CORE(A)= CORE(A)+a; End if End for 3 Red=CORE(A); 4 计算约简集的依赖度 kR(d); 5 如果 kR(d)=，那么下转 10，否则转向 6; 6 对于每一个 aA-Red,计算属性重要性 SIG(a,R,d); 7 选择重要性最大的属性 a，Red=Reda; 8 计算 Red 的依赖度 kR(d); 9 如果 kR(d)=，那么下转 10，否则转向 6; 10 输出约简 Red. 3 实例分析实例分析 为了更好的分析以上算法，我们用一个相容信息表 1 和一个不相容信息表 2 来作分析。 相容信息表： 表 1 一个实际的天气预报决策表 U Outlook (a1) Temperature (a2) Humidity (a3) Windy (a4) Class (d) 1 Sunny Hot High Flase N 2 Sunny Hot High True N 3 Overcast Hot High Flase P 4 Rain Mild High Flase P 5 Rain Cool Normal Flase P 6 Rain Cool Normal True N 7 Overcast Cool Normal True P 8 Sunny Cool High False N 9 Sunny Cool Normal False P 10 Rain Mild Normal False P 11 Sunny Mild Normal True P 12 Overcast Mild High True P 13 Overcast Hot Normal False P 14 Rain Mild High True N 计算相对正域，求出属性的核：POS(A-a1)(d) POSA(d)，POS(A-a2)(d)= POSA(d)，POS(A-a3)(d)= POSA(d)，POS(A-a4)(d) POSA(d)，所以 R=a1,a4即outlook,windy是属性核。 UR=1,8,9,2,11,3,13,7,12,4,5,10,6,14 URa2=3,13,4,10,1,2,5,6,7,8,9,11,12,14 Ud=Y1,Y2, Y1=1,2,6,8,14, Y2=3,4,5,7,9,10,11,12,13 kR (d )= 3/14, kRa2 (d )=11/14, SIG(a2,R,d)=8/14. URa3=1,8,2,3,4,5,10,6,7,9,11,12,13,14 kR (d )= 3/14, kRa3 (d )=12/14, SIG(a2,R,d)=9/14. 在 a2 和 a3 中 a3 的重要性大，所以选取 a3 加入约简集中，即：Red=a1,a3,a4。假设依赖度阈值=0.85， 则满足终止条件， 即最后的属性约简集为 Red=outlook,humidity,windy。 不相
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号