基于加权频繁子图挖掘的图模型在文本分类中的应用-论文.pdf

《基于加权频繁子图挖掘的图模型在文本分类中的应用-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Vo1．14No．22Aug．2014第14卷第22期2014年8月科学技术与工程1671—1815(2014)22—0080—06ScienceTechnologyandEngineering⑥2014Sci．Tech．Engrg．基于加权频繁子图挖掘的图模型在文本分类中的应用王海荣(黄淮学院信息工程学院，驻马店463000)摘要针对传统文本分类算法的分类精度低和计算复杂度高的问题，提出一种基于加权频繁子图挖掘的图模型文本分类算法。首先将文档集表示成图集；然后运用加权图挖掘算法提取频繁子图；最后，对特征向量进行分类。提出的算法仅提取最重要的子图，使其整体具有

2、较好的分类效果和较高的计算效率。为评估该算法有效性，将其与多种现有分类算法分别对一个数据集进行分类实验，实验结果表明，提出的算法具有更高的识别精度和更少的运行时间。关键词文本分类图模型加权频繁子图挖掘最小支持度特征提取中图法分类号TP399；文献标志码A文本分类方法中最常见的是基于词／词袋表示必要的模式J。加权关联规则挖掘(Weightedasso—的向量空间模型法，其主要优点是分类算法易于实ciationrulesmining，WARM)中一个重大问题是项现。然而，词／词组向量空间法仅适合采集频繁出现集不具有“向下闭合”(DC)属性，对此有一种解决的词／词袋

3、，而忽略了结构和语义信息，事实证明结方案是在挖掘频繁项集之后将权重当做一个后处理构信息对分类精度也有重要的影响¨。基于图模步骤J，但是这样权重就不会集成到关联规则挖掘型的文本表示方法比词／词袋表示方法更直观、表现(associationrulesmining，ARM)过程中。文献[9]力更强，但引入了一个额外的复杂度，两幅图之间相提出一个加权支持模型，满足加权DC属性。文献似度的计算复杂度明显高于两个向量之问相似度计[10]为了维持DC属性并推动权重约束深入挖掘过算。有学者研究采用混合表示法j，结合结构元素程而为WARM引入一系列概念，如“加权范围”、(使用图

4、模型)和重要特征(使用向量模型)混合表“权重自信度”和“支持自信度”，尽管WARM的思示，然而，这些混合模型的计算量仍然很大。想不能直接应用到加权频繁子图挖掘中，然而这个早期有关文本分类方法的研究大都是针对研究对本文分类方法研究有一定的启发。Web文档，文献[3]表明单独使用文档结构就可以基于图模型的文本挖掘方法的主要缺点是较高分类Web文档，本文将证明结合结构和语义信息的的计算复杂度。本文提出一种运用加权图挖掘分析方法更为有效。引入混合表示是为了解决单纯图表法来解决这个问题，将权重约束应用到频繁子图挖示带来的高计算复杂度问题，文献[4]表明混合表掘过程中，通

5、过仅产生最重要的模式来减少搜索示法的性能优于单纯图模型表示方法，然而处理这空间。些混合模型需要的计算量仍然很大，主要因为：①1频繁子图节点和边的数目巨大、边标签数目少、节点标签结构重复性高；②搜索空间的指数复杂度高等原因J。现以事务图集D={G，G，⋯，G}为开端介采用各种方法挖掘频繁子图已经得到了广泛的绍标准事务图挖掘方法，r(g，G)为任意图g和G研究。。J，但主要的问题是在挖掘过程中许多次要的的关系函数。如果g是G中一副子图的同构图，则频繁子图也被挖掘。目前有研究者使用搜索策略、(g，G)=1(resp．0)。数据结构或两者的组合，来寻找有效的图挖掘算法

6、。定义1图g相对于数据库D：{G，G，⋯，有学者建议使用基于频繁子图挖掘的约束来去除不G}的支持度计数值可表示为sco(g)=∑(g，2014年3月1413收到河南省科技厅科技攻关计划项G)，g相对于数据库D的支持度sup(g)是支持度(112102210457)、河南省教育厅自然基金项目(2011C580003)资助计数值SCO(g)与数据集D大小的比值，即：作者简介：王海荣(1981一)，女，汉族，河南省遂平人，硕士，讲师。研究方向：文本挖掘、数据挖掘等。E—mail：wangbrhn@】63．OOm。up(g)：n22期王海荣：基于加权频繁子图挖掘的图模

7、型在文本分类中的应用81SCO(g)和sup(g)与大部分项都依赖于数据集然后定义包括在g的k一模式的支持度计数值D，为了避免混淆符号，隐藏了这种依赖性。下界定义2给定图g，如果sup(g)大于或等于用sbou——ndn(g)=IwDOUilal(8)户定义的最小阈值0，则认为g在D中是频繁的，频ng，繁子图挖掘算法的目的就是找出数据集D中所有如式(5)定义，通过设置sboundk(g)=的频繁子图。sbound(g)，可将定义扩展为It=k。假定带有权重的图与它们的顶点或边有关联，定义5当≤11,≤mL中只有一部分n符合令为分配权重到任意图g的函数，图顶点(

8、或边)sco(g)