自动分类技术（共8篇）
自动分类技术 篇1
在专利信息技术领域中,自动分类技术的研究自2010年变为实用,成为标志性里程碑。多年来基于历史信息的海量计算占主导。笔者致力于简单实效的轻量级软件研究,提出一种基于分类表的简约方法。通过实验来验证其可行性。
1 实验背景
早期手工分类,从粗到细,完全由分类员完成。主要工具是查阅专利分类表。随着计算机应用的发展,分类表由书籍变成电子版,又经历了网络版、网页版变迁。2010年以后才真正标志性地实现了自动分类技术的应用,将研究变为实用。一种基于历史文献的分类方法至今占据着主导位置。
1.1 基于历史文献的分类方法
以历史文献作训练空间,构建语料库,通过数学模型运算获得相似度评分,提供备选方案。其中数学模型可以多种。如SVM、KNN、Naive Bayes等等[1]。其优点是对已分类文献分类效果良好。其缺点是需配备海量装备,代价大。
这种方法后来也受到两点质疑。
1)发明专利的创新性
由于专利文献由两类构成:一类是开创性发明,另一类是改进性发明。对于开创性发明,其新技术方案所依据的基本原理与已有技术有质的不同。这类专利之间相似度很低。因此基于历史的方法,问题会出在参照物信息不充分上。
2)IPC分类的渐变性
在专利审查流程中有一种预警机制。当某个时期某个领域专利案件量增长超出预期就会报警。同时引起两个部门的注意。A)宏观战略研究部门,主要观测是否将有引领潮流的革命性技术到来,例如:纳米。预测5到10年将进入市场,对宏观经济产生影响。B)审查业务管理部门,检测到案件量当超过某个数量级的阀值时,就要考虑审查增员问题,或者考虑该分类是否需要再细分。一种变化是增加小组细目,另一种变化停止原小组细目,重新分配一个新的大组,然后再分到各个小组细目。因此,专利分类表会根据需要随时调整。因此基于历史的方法问题会出在参照物信息不确定上。
1.2 基于分类表的分类方法
分类表作为指导性工具,曾经是手工时代的产物,早已被自动化工具所取代,目前只剩备忘录作用。笔者以为分类表不仅有良好层级结构,还有规则指向,交叉参考等。如能充分利用,可以开发出分类导航(XML- Xslt版已初具导航作用)产品;将括弧中规则指向和交叉参考与人工智能相结合,自动分类可以达到极高准确率,当然引入规则会变得相当复杂。分类表简单使用,已经具备可计算性。这恰恰是轻量级分类方法须采用的重要手段之一,不可或缺。这种方法也有许多困难需要面对。例如:
1)专利文献语言文化差异
专利文献格式严格,结构特征明显。作者撰写文档,须通过形式审查才能进入审批流程。由于对撰写具体内容不作限定,说明书的撰写水平受作者的语言文化背景、地域差异、学识和规范习惯等因素影响,因人而异。发明标题中的词素非常重要,需要抓住主题重点;权利要求书的描述是树形结构,可以程式化固定。例如:“一种”(独立权利要求),“根据”(从属权利要求),可以构成林、树、杈关系。这对主分类和相关分类分析有参考价值。笔者曾抽样分析,结果令人失望。严格按统一规范来撰写的并不多,失去利用价值。要求文字术语统一规范,更是难事。
2)专利分类表术语不统一规范
电子版分类表中符号混乱,文字缺乏统一规范。通过取样几个近义词,便可略见一斑。参见表1。
某些词语意思相近,复杂而繁多,分布在不同分类中,给解析带来困难。
3)抽象专利分类表与具象专利文献之间术语差异
该差异是两者不在一个层面自然形成的,需要一个沟通机制。由此,引出基于同义词的术语分类方法。
1.3 基于同义词的分类方法
专利文献加工中人工标引主要的工作就是标注文献的关键词和同义词。该方法主要作为提高专利检索查准率、查全率的必要手段之一。而对于文档自动分类来说,利用分词技术来获取文档中有限高频词。两者目标一致,方法有别,一个人工,一个计算技术。由于计算技术缺乏模糊识别、灵活和准确的理解力。因此,最终还是需要适当植入人工标引关键词来弥补计算技术的缺陷,提高准确性。
其哲学思想也与数学方法论不相矛盾。如果把专利文献和专利分类看作向量空间模型,文档空间被看成是被简化了的一组能够代表文档的高频正交词条有限特征向量空间,词条频度权重,看作特征轴上的投影。IPC分类也是有限特征向量空间子集,由不同的特征排列组合而成。某些特征被不同的分类空间所共用。像星座群一样,每个星座对不同的分类群起的作用不同,有些分类群整体很耀眼,有些分类群整体有些黯淡,甚至没有光芒。如果文档空间向量与ipc空间向量存在交集,在ipc某些特征轴上能够直接找到投影;否则,就相离。如果,某些特征通过变换折射也可以找到投影,那么认为,两者之间间接存在交集。这里折射变换的原理也就是同义词和上位词植入的基本原理。
如果直接用分类表来解析文献,寻求的分类目标可能会发散。因为文档空间与IPC分类空间不直接在一个层面上,坐标没有对应关系,投影回到原点。有人会提出按照文档结构分类方法,认为标题或文摘部分很重要,通过增加整个标题或文摘的权重来施加影响力。这对于空间的形状会有所改善,但并未发生质的改变。也只是改变了投影形状量的大小。只有,真正将文档空间中不在同一个层面的那些高频特征词,通过上位词或同义词的折射变换,才可以改善其在分类空间中的投影,以突显或还原其真实形态。
利用这一方法,通过逐一折射扫描,捕捉分类空间的投影。不仅可以原型再现,还可以通过局部放大,来达到逐一捕获主IPC和或其他相关IPC的目的。分类会因同义词强化效果大大改善,达到很好的收敛性。
因此,建立一个完善的同义词库意义重大。提供捡拾同义关系词的入口,是基于同义词分类方案进入一个良性循环的必要手段。这是需要全员参与的工作,需要群体的智慧。同样,提供一个可植入关键词的入口,对于不依赖于现有或历史,也是设计者需要考虑的。
建立同义词或上位词关系词方法其实简单。例如:蛋白质是由肽构成的,肽是由氨基酸构成的。那么建立“肽→蛋白质”关系,肽是上位词,蛋白质是下位词。文献中使用了“…蛋白质”,就植入上位的“蛋白质”和“肽”;又例如:文献用“英文/英语”,那么就植入其上位词“外语”,建立“外语→英语”关系。新建立的关系词被积累保存到同义词库,一劳永逸。
与基于历史文献语料库相比,同义词库无疑是轻量级的。同义词库可以弥补专利分类表中词语抽象的不足,用来化解专利文献中词语具象的复杂性。在专利分类表和专利文献之间搭建起沟通的桥梁。
2 IPC自动分类的技术实现
IPC自动分类的实现,其专利文献自动分类实验流程图,如图1所示。
专利分类流程图分为两个部分,可以分开实现,IPC分类表语料库加工层最终得到的是分类表语料库。由{ipc,wj,cc,idf}构成,内容参见定义1。
定义1:ipci,用以表示IPC分类表中的某个专利分类号;wij,用以表示ipci分类描述文字切分出的某个特征词;cc(wij)表示,特征词wij在IPC分类表中有多少分类与之有关;N,用以表示IPC分类表中总共有多少分类条目;idf(wij) ,用以表示IPC分类条目中的词条相对于总体分类的反文档数,是wij的重新评估的权重,idf(wij)=log(N/ cc(wij))。
原始文档加工层,最终得到文档目标语料。由{wi,dn,tf}构成,内容参见定义2。
定义2:D,用以表示原始文献;wk,用以表示D中切分出的词条;dn(wk),用以表示wk的重复数;n,用以表示D中的总词条数,n=∑dn(wk);tf(wk),用以表示wk的词频,tf(wk)= dnk/ n;
计算相似度层,用三种算法分别计算相似度排名。参见自动分类算法。
2.1 IPC自动分类的算法
本文给出自定义的两种算法和一种已有算法进行对比。即:
WHZ算法——一个自定义算法
Tf-Idf算法——一个已有算法
Hit-Rate算法——一个自定义算法
2.1.1 WHZ算法
whz算法属于自定义算法,用来抑制版权争端,与Tf-Idf和BM25算法相当。
定义3:
文档D与分类条目ipci相似度,用whz(D,ipci)表示。
whz(D,ipci)=∑(dn(wj)/cc(wij))dn(w)w
其中,dn(wj)代表文档词条wj重复度权重,cc(wij)代表ipci条目中wj词条被多少个其他ipc分类条目所共用或分享。
2.1.2 Tf-Idf算法
Tf-Idf算法属于已有算法,其标准形式的定义有BM25算法[略]。
定义4:
文档D与分类条目ipci相似度,用Tf-Idf (D, ipci)表示,或sim(D, ipci)表示。
其中,dn(wj)代表词条wj重复数,cc(wij)代表词条wj逆文档数,亦即词条与其他ipc分类也相关的ipc条目数。
2.1.3 Hit-Rate算法
由于whz自定义算法,与tf-idf算法总体趋势接近。为防止前两种算法接近重叠,我们又从另外角度给出了一种自定义的算法。其主旨是,将ipc条目其所涉及分词,与专利文献中高重复度的词相匹配,匹配占比越大,得分越高,与ipc条目越相似。
定义5:
函数has(wij)如果wij出现在文献D中,则取值1,如果没有出现在文献D中,则取值0;Hit-r(D,ipci),用于表示命中率或占比。
其中j=1..m,则∑j(1)=m。
文档D与分类条目ipci相似度,用Hit-Rate(D, ipci)表示。
3 实验效果(The experiment effect)
抽样考察4个发明公开专利文献。取试验样本4个发明公开专利的“标题+文摘”,参见表2。
专利文献切分分词,参见表3。
观测实验结果,植入关键词对自动分类的三种算法排名的影响,参见表5。
直接通过分类表计算自动分类相似度排名,收敛性较差。参见表4 左部结果。植入同义词调整后,分类效果明显改善,基本收敛。参见表4右部结果。
笔者通过植入同义词和上位词来改善分类表解析不收敛的问题。如果调整得不到希望的分类,亦即,分类不收敛,就要重新调整其他同义词方向,来改变策略,直至得到与文献内容相符合且最接近的分类为止。
从实验效果看,本文所用的分类表与同义词修正相结合的分类方法,收敛效果明显。与实际采用何种算法无关,要发散都发散,要收敛都收敛。无疑TF-IDF优于自定义。
4 结论
IPC自动分类技术作为计算机辅助工具来使用,可为人们提供一种具有参考价值的分类信息,供使用者选择。本文所述分类方法是一种基于分类表和同义词相结合的方法,不依赖于历史信息也不受限于历史信息的不足,不需要大量训练数据的方法。其优点是:能将专利文献中的不同权重的高频词,通过同义词库的扩充,与分类表直接比对,不需要花费大量资源收集专利文献语料库,只需借助有限同义词植入来调整分类运算,来解决分类不收敛的问题。该方法在存储量和运算量方面属于轻量级的,且运算速度快,加工一篇文献不到1秒,需要的资源不多。通过植入同义词或上位词调整权重,可以改变某些分类的发散或收敛方向,来达到逐一捕获主ipc和每一个相关ipc的目的。可作为半自动的简单灵活的分类捕捉工具。其缺点是算法受限于同义词库的建立,取决于植入同义词的经验,调整植入词,改变某些分类的发散或收敛方向,需要使用者自己凭经验来掌握和控制。初期需花费一些时间将分类表作一个初步同义词整理,然后通过工作进行中不断来扩充同义词库,使之趋于完善。该方法对CPC自动分类的实现有借鉴意义。
参考文献
[1]刘玉琴,桂婕,朱东华.基于IPC知识结构的专利自动分类方法[J].计算机工程,2008,34(3):207-209.
图书自动分类技术研究与实现 篇2
关键词：图书分类,TF-IDF,朴素贝叶斯
0 引言
在图书馆工作中,最复杂、重要且耗时最长的工作就是图书分类工作。图书分类工作通常是由人手工进行,但是由于图书分类的复杂性、多样性、模糊性等因素,使图书分类工作更加困难,准确性也不能够得到绝对保证,仅仅提高工作人员的素质是根本不够的。随着科技的迅速发展,使用新的计算机技术来解决图书分类问题是十分必要的,其中一种比较有效的方法是采用专家系统技术对图书进行自动分类[1]。但是专家系统需要一个覆盖面广、内容充足的知识库,以及拥有强大推理能力的系统支撑,还需要逻辑严谨、类别清晰的规则库才能保证系统的正常运行。因此,构建专家系统是十分困难的,建立知识库与规则库也需要耗费大量的人力、物力。
1 图书分类算法介绍
1.1 TF-IDF算法
TF-IDF是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法,用于评估字词对于一个文件集或一个语料库中一份文件的重要程度。
在一份给定的文件里,词频指某个给定的词语在该文件中出现的频率。该数字是对词数的归一化,以防止其偏向长的文件。逆向文件频率是一个词语普遍重要性的度量。某一特定词语的IDF,可以由总文件数目除以包含该词语文件的数目,再将得到的商取对数得到。
某一特定文件内的高词语频率,以及该词语在整个文件集合中的低文件频率,可以产生出高权重的TF-IDF。因此,TF-IDF倾向于过滤掉常见词语,保留重要词语。
1.2 朴素贝叶斯算法
朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。朴素贝叶斯分类是一种十分简单的分类算法,被称为朴素贝叶斯分类是因为该方法的思想非常朴素。其思想基础如下:对于给出的待分类项,求解在此项出现的条件下各个类别出现的概率,哪个最大则认为此待分类项属于哪个类别。
朴素贝叶斯分类的正式定义如下:(1)设{a1,a2,…,am}为m个待分类项,而每个a为x的一个特征属性;(2)有n个类别的集合{y1,y2,…,yn};(3)计算当x出现时属于y1的概率,x出现时属于y2的概率,…,直到x出现时属于yn的概率;(4)如果当x出现时属于yk的概率最大,则x属于yk。
2 图书分类设计与实现
图书分类系统主要分为4大模块,如图1所示。
(1)图书信息采集模块。图书信息采集模块主要用于图书信息的收集工作。主要功能是从图书电商网站中将图书信息相关页面内容采集到本地,并按照图书电商提供的图书类别将采集到的图书信息聚类在一起。
(2)图书数据清洗模块。图书数据清洗模块主要功能是将图书信息采集模块收集到的图书网页信息进行分析,去除与图书信息无关的内容,抽取出系统需要的图书信息,并将其存入到样本库中。
(3)特征提取模块。图书数据清洗模块仅仅是将收集到的图书页面信息中与图书相关的信息抽取出来,而特征提取模块主要功能是从入库后的图书信息中提取出每一类图书的特征,并将相关特征存入数据库。
(4)特征比对模块。特征比对模块的主要功能是根据样本库中的所有图书类别特征将未知类别的图书进行分类定位,得到该书的类别。
2.1 图书信息采集模块
图书信息采集模块主要是从图书电商中采集图书的基本信息,包括图书名称、作者、出版社、ISBN号、商品编码、出版时间、内容简介、编辑推荐、经典书评、书摘、前言等信息。
图书信息采集模块主要分为4个部分:(1)选择一个图书网站作为数据源;(2)将此图书网站中的图书分类采集到本地;(3)根据采集到的图书分类地址,获取到此类图书的列表,再将图书列表采集到本地;(4)将每一个图书分类中的图书信息采集到本地。图书信息采集工作不是一次性将一个网站内的图书全部采集完,而是分阶段采集数据,采用这种模式的原因如下:(1)由于现在各个公司都开始对数据进行保护,很多大型网站都做了防爬取工作,当进行长时间、高频率访问时,将获取不到数据,甚至会封IP,从而达不到数据采集的目的;(2)由于图书信息采集的数据源多,采集流程较长,各个流程虽有一定联系,但又相对独立,所以采用数据分步落地的方式可以使工作更加安全、有效。
2.2 图书数据清洗模块
图书信息清洗模块主要是将采集到的图书网页信息进行数据清洗,抽取出有意义的图书信息,主要包括图书名称、内容简介、编辑推荐、文摘等。
在图书信息采集模块中,已将图书所在页面采集到本地,并且将同一类图书的页面信息存在同一文件夹下,所以在做数据清洗时,提取结构化信息则变得相对方便。
图书信息清洗模块主要分为3个步骤:(1)扫描本地图书文件,即扫描爬取到本地的图书网页信息;(2)分析爬取的图书网页信息,清洗掉与图书无关的信息,将每一本图书的基本信息提取出来;(3)将抽取出的图书信息存入数据库,作为下一步研究的基本数据。
2.3 特征提取模块
图书结构化信息入库后,需要将每一类的图书特征抽取出来,并且将提取出的特征存入数据库中。
(1)提取同类图书信息。提取同类图书信息是指将同一类图书的图书名称、内容简介、编辑推荐、文摘信息提取到一个文件中。
(2)分词、清洗。分词、清洗由两部分组成,即信息分词部分与通用词、停用词清洗部分。其中分词部分是使用NLPIR汉语分词系统进行分词处理,通用词、停用词清洗部分是在分词过程中一并处理的。预先准备通用词和停用词词库,在分词过程中去除出现在通用词和停用词词库中的信息,最终得到确切的图书描述词汇。
(3)TF-IDF算法提取特征。当分词、清洗环节结束时,每一个分类中每一本书的描述信息都已经过处理,得到了更加精炼的描述关键词,再根据每一本图书的关键词,计算出在本类别中出现次数最多,但在其它类别中出现次数最少的词,即可作为本类图书的特征词。其中,由于不同类别包含的图书数量不一致,并不是某一关键词出现在其它类别就不能当作本类图书的关键词,还需要看在本类别中出现的频率是否较高。如在本类图书中与其它图书类别中出现频率都较高,此种情况可视为此关键词既属于本类图书,也可能属于其它类别图书。
2.4 特征比对模块
在特征抽取模块中,已经将每一类图书的特征提取出来,并存入数据库中。在特征比对模块中,需要将某本未知分类的图书进行定位,确认其分类,并将此本图书的关键词加入分类特征中。
(1)获取待分类图书信息。待分类图书信息主要包括图书名称、图书作者、图书简介等,其中图书名称和图书简介信息属于关键信息,图书作者信息属于辅助信息。图书作者信息的主要功能是可以根据作者查询出其在哪些图书类别中发行过哪些图书,从而首先试图在其擅长领域中定位新书,减少处理次数。
(2)待分类图书关键词提取。待分类图书信息是未经处理的原始信息,要通过朴素贝叶斯算法进行图书定位,必须先将图书简介信息进行分词与去噪处理。其中分词部分使用NLPIR汉语分词系统进行处理,去噪部分指去除通用词和停用词。由于图书简介信息内容并不是很丰富,所以在关键词提取阶段应该尽量保留信息,以获得更多图书描述信息。
(3)朴素贝叶斯算法确定分类。根据对朴素贝叶斯算法的介绍,可以知道朴素贝叶斯算法是计算当每一个关键词出现,确认是某一个分类的概率值,然后将每一个关键词在某一个分类中出现的概率值相乘,找出乘积最大的分类,即可以确定此书属于该分类。由于待分类的图书信息有限,而某一个分类的特征词又有很多,再将所求得的概率值相乘,最终会是一个极小的数字,并且当特征词数量在一定的数量级时得到的结果将为0,所以在计算过程中,将每一个关键词出现时确定是某个分类的概率值放大同等倍数,并不会影响计算结果的准确性。
3 实验结果与分析
3.1 实验数据及结果
本文选取从京东商城上爬取的180万本图书信息作为测试样本。根据对样本集的测试,得出每一类图书的特征词抽取个数范围对图书分类的效率和正确性影响最大,具体分析如下:
(1)特征词抽取个数范围对数据结果的影响。在对图书样本集进行训练的过程中,发现在提取不同个数的特征词时,将对最终图书定位产生影响,显示出不同的效率值与准确率。经过不断调整,最终得到了比较理想的效率值和准确率值。图书样本集在选取不同的特征词抽取个数范围时对效率值和准确值的影响如表1所示。
从表1中可以得出,训练数据集中特征词抽取个数对整体结果影响较大。从表中的结果数据不难看出,当特征词抽取个数不够时,虽然效率较高,但是正确性和精确性不高;然而当特征词抽取个数过多时,关键词过多,反而也会使正确性和精确性下降。
(2)最优值分析。如何确定最优值,是在相同样本训练集情况下、提取特征词个数不同时,产生不同的正确率和精确率以及效率值,再从这些值中选取出正确率、精确率及效率值表现相对较好的结果。
由表1可以判断,当特征词抽取个数为250~400时,正确率、精确率及效率值都相对较好。尤其是当特征词抽取个数为350时,正确率、精确率最高,而效率值波动并不是很大。所以认为当样本信息足够多、数量足够大时,选取350个特征词进行特征比对能得出较为理想的结果。
3.2 实验概述及结果分析
本次实验的目的是希望通过特征提取及特征比对的方法来确定某本未知分类的图书分类。由上述图书分类系统整体结构设计可以看出,实验主要分为3大部分:(1)图书信息爬取及结构化信息提取;(2)使用TD-IDF算法提取每一类图书的特征词;(3)使用朴素贝叶斯算法定位未知图书的分类。由实验结果可知,当特征词抽取个数较多或较少时都会影响最终结果的正确性和精确性。经过反复试验,最终确定出一个较为合理的区间,在该区间中能够得到一个较为准确的结果。
4 结语
在图书馆工作中,图书分类工作十分复杂且耗时,为了解决图书分类问题,已有很多学者开始从事图书自动分类研究工作,并取得了一定成果。本文在这些已有技术的基础上提出了基于TF-IDF及朴素贝叶斯算法来解决图书分类问题。
本文采用互联网图书信息及图书分类作为训练样本进行实验,在图书信息采集过程中遇到了网站防护及数据延迟加载等问题;在数据清洗过程中,分词工具的选择、通用词及停用词词库的构建都十分重要,如果分词工具选择与词库构建不合理,对最终结果正确性的影响将很大;在特征提取阶段,最关键的问题是关键词统计,以及此关键词在其它文档中出现的频率。由于图书种类较多,抽取出的图书关键词也很多,并且未采用分布式系统处理数据,所以在计算和统计时花费了很长时间。在整个系统设计中,特征比对之前的工作都是在做数据集的训练工作。特征比对使用之前训练好的数据来最终确定一本书的分类。由于使用朴素贝叶斯算法进行文本分类处理,并且图书分类较多,每一个分类中的特征关键词也较多,所以最终得到的概率乘积会非常小。当图书分类的特征关键词达到一定数量时,最终得到的结果值会被认为是零,影响结果判断,所以在特征提取时,特征词数量是决定结果正确与否的关键因素。在本文中,经过反复实验,最终得到一个区间,当特征词数量在该区间内时,最终得到相对准确的结果。
综上所述,本文研究针对图书馆情报学图书分类问题,虽然在图书自动分类领域已有一些较为成熟的研究成果,但是本文从另外一种角度,尝试使用不同的技术来分析研究该问题,并且取得了一定成果,对图书馆情报学研究有一定的参考借鉴意义。
参考文献
[1]张惠.图书自动分类专家系统的研究[J].佛山科学技术学院学报:自然科学版,2001,19(2):37-40.
[2]李静梅,孙丽华,张巧荣,等.一种文本处理中的朴素贝叶斯分类器[J].哈尔滨工程大学学报,2003,24(1):71-74.
[3]涂茵.图书分类中常见问题探讨[J].河南图书馆学刊,2015(6):62-64.
[4]张笑.图书分类中的问题及对策[J].卷宗,2015(3):21-21.
[5]程克非,张聪.基于特征加权的朴素贝叶斯分类器[J].计算机仿真,2006,23(10):92-94.
[6]张红蕊,张永,于静雯.云计算环境下基于朴素贝叶斯的数据分类[J].计算机应用与软件,2015(3):27-30.
[7]于秀丽,王阳,齐幸辉.基于朴素贝叶斯的垂直搜索引擎分类器设计[J].无线电工程,2015(11):13-16.
[8]罗欣,夏德麟,晏蒲柳.基于词频差异的特征选取及改进的TF-IDF公式[J].计算机应用,2005,25(9):2031-2033.
[9]韩敏,唐常杰,段磊,等.基于TF-IDF相似度的标签聚类方法[J].计算机科学与探索,2010(3):240-246.
自动分类技术 篇3
基于遥感影像光谱信息的二叉决策分类树自动生成方法研究
使用决策树方法进行遥感影像分类时需要人工辅助构建决策树,这种方法存在着一旦数据变化就要人工参与重新建立决策树的缺点.针对这一问题,文中提出了依据地物类的样本训练结果,自动构建二叉决策分类树的方法.从阈值的.完整性、有效性以及自动选择满足用户需求最佳的建立决策树标准等方面保证决策树的精度以及合理性等.分类结果表明,与最大似然法相比,文中提出算法分类效果良好.
作 者：闫培洁 于子凡 王勇军 YAN Pei-jie YU Zi-fan WANG Yong-jun 作者单位：武汉大学遥感信息工程学院,武汉,430079刊 名：测绘科学 ISTIC PKU英文刊名：SCIENCE OF SURVEYING AND MAPPING年，卷(期)：200934(6)分类号：P237关键词：遥感影像分类 光谱信息 二叉决策树 自动生成 remote sensing classification spectral information binary decision tree automatically generation
中文网页自动分类构架设计 篇4
关键词：网页自动分类,分词技术,特征抽取
1. 引言
本论文从网页分类方面对万维网上的数据处理技术进行了研究。对中文网页自动分类技术这一具有重要理论意义和广阔应用前景的课题进行了研究和探索。
研究内容主要包括:设计了一种中文网页自动分类技术模型, 应用该模型设计的中文网页分类器能够满足处理大规模中文网页的要求。
2. 技术模型架构
为了能够有效地组织和分析海量的Web信息资源, 帮助用户迅速地获取其所需要的知识和信息, 人们希望能够按照其内容实现对网页的自动分类。
每一个网页分类系统都是建立在一定的文档分类方法基础之上。准确、高效的文档属性选择和文档分类方法通常会不断出现, 因此, 一个文档分类系统应该具备功能和性能上的可扩展性, 这就要求文档分类系统建立在模块化、可扩展的体系结构基础之上。图1所示为我们设计的中文Web网页自动分类技术的体系结构。
3. 数据库部件和功能模块组成
整个技术的主要功能由下列数据库部件和功能模块组成:
(1) 分类模型库
基于机器学习的分类通常由训练和分类两个阶段组成, 在训练阶段, 从训练文本学习分类知识, 建立分类器;在分类阶段, 根据分类器将输入文本分到最可能的类别中。根据训练样本集中的文本数据和具体的属性选择方法与分类方法, 计算得到的分类模型数据, 都存于该库中。将属性选择方法和分类方法的任何一种组合都作为一个分类模型。
(2) 未标记网页库
保存大量的未标记网页数据。当训练集中的样本数量较少时, 可以通过未标记网页的利用方法从该库中选取一定的未标记网页加入到小规模的训练集中, 从而弥补训练样本的不足, 减少人工标记大量网页的需要。
(3) 特征抽取模块
负责从原始Web文档中提取特征信息。首先对网页进行页面分析, 提取出其中的文本信息, 经过分词程序分词后, 去除停用词 (如“的”、“和”等虚词) , 然后统计单词在当前网页中的词频 (同时考虑单词出现在网页中的位置) 。
构成文本的词汇数量是相当大的, 所以, 表示文本的向量空间的维数也相当大, 可以达到几万维。因此我们需要进行维数压缩的工作, 这样做的目的主要有两个:第一, 为了提高程序的效率, 提高运行速度;第二, 所有几万个词汇对文本分类的意义是不同的。
某些稀有词在全部训练文档中出现的次数都很少, 对于分类的意义不大, 应予以滤除。我们设定一个出线次数阈值, 如果某个特征项在训练集中的总出现次数小于该值, 则滤除该特征项。
(4) 文档属性选择模块
负责实施分类属性的选择, 提供各种用于文档属性选择的方法, 它实际上是一个算法库。该模块规定统一的属性选择算法接口, 以便于文档分类属性选择算法的增加与删减。
一些通用的、各个类别都普遍存在的词汇对分类的贡献小;在某特定类中出现比重大而在其它类中出现比重小的词汇对文本分类的贡献大。为了提高分类精度, 对于每一类, 我们应去除那些表现力不强的词汇, 筛选出针对该类的特征项集合, 存在多种筛选特征项的算法, 如前面介绍的文档频率、信息增益、χ2统计、互信息等。
(5) 文档分类方法 (模型) 模块
和前一个模块类似, 这是一个分类算法库。目前实现的分类算法有基本SVM算法、决策SVM算法。根据实际的研究和使用需要, 我们可以在该模块中补充新的分类算法。
(6) 分类模型训练模块
也就是学习模块, 即根据训练文档、属性选择方法和分类算法推算分类模型。
(7) 分类测试模块
对预处理后的Web文档进行分类处理。
(8) 输入预处理模块
对待分类的输入Web文档中进行预处理, 从文档中提取出文本信息, 滤掉对分类无用的非文本信息, 通过分词提取出网页中的有效特征, 并进行权值计算。
(9) 性能评估模块
通过对测试结果的分析, 进而评估分类器的性能。
(10) 输出表现模块
输出分类结果和指标。
(11) 训练样本集维护模块
负责增加和删减训练样本集中的文档。
(12) 分类控制模块
对整个分类过程进行控制, 包括设置分类训练和测试的参数、确定文档属性的选择方法、确定分类方法以及设置利用未标记数据的参数等。
(13) 人机界面
提供一个Web网页分类的交互环境。
(14) 未标记网页利用模块
该模块可以在少量的训练样本条件下, 从未标记网页数据库中抽取出部分网页补充到训练集中, 从而提高分类器性能, 减少人工标记网页的数量。
上述体系结构的突出优点是:
a.模块化的系统结构, 使得文档分类过程中的取词、选词等主要步骤相对独立, 各个步产生的中间结果可以重用, 从而提高效率。
b.文档属性选择和分类方法的分离, 便于属性选择方法和分类方法之间的优化组合。
c.文档属性选择方法库和分类方法库的使用, 有利于分档分类系统的扩展和完善。
d.未标记网页利用模块可以有效地减少人工标记大量的训练样本的需要。
4. 结束语
设计中文Web网页自动分类技术, 该技术综合了本文在中文网页分类技术方面的研究, 应用所研究的分类法提高分类器性能方面的工作, 根据实际的研究和使用需要做出设计。采用模块化的结构, 使得文档分类过程中的主要步骤相对独立, 各个步骤产生的中间结果可以重用, 从而提高了效率。文档属性选择方法库和分类方法库的使用, 也有利于文档分类技术的扩展和完善。
参考文献
[1]周水庚, 关佶红, 胡运发, 周傲英.一个无需辞典支持和切词处理的中文文档分类系统.计算机研究与发展, 2001, 38 (7) ;
自动控制旋转分类储物柜 篇5
1 国内外研究现状分析
通过对专利的查询可得知, 目前有一两个产品名称相近但运作方式不同的专利产品存在, 结构与我们的具有较大差异, 这些产品在机械部分过于复杂, 成本较高, 不便于制作。虽有电机, 但在智能控制部分又显得不够人性化, 没有实现精确快速又方便操作的功能要求。
2 基本原理分析
需要取用物品时, 按动按钮, 单片机中断系统响应并执行该动作, CPU处理并将响应传给继电器, 继电器控制电机, 此时同步带转动, 带动储物盒转动, 光电门检测到转动信号并向单片机发送计数脉冲, 经单片机处理返回到继电器, 电机则相应编号的储物盒就转到当前的位置。
3 传动部分
3.1 传动方式选择
在选择传动方式时, 由于考虑要定位盒子, 所以备选的方式有链条传动和同步带传动。链条传动平稳, 传动可靠性强, 但精度低, 质量大, 安装精度要求高。而同步带传动精度高, 质量轻, 结合了带传动和齿轮传动的特点。有以下优点:1) 传动比恒定;2) 结构紧凑;3) 由于带薄而轻, 抗拉强度高, 故带速高达40m/s, 传递功率可达200KW;4) 效率高, 高达0.98。故最终选用同步带传动, 经三维建模仿真如图:
下部用两个带轮传动, 通过电机带动中心轴, 使同步带转动, 从而是连接在附板链条的收纳小盒也转动。
3.2 电机的选择
开始时, 考虑到控制的精准和效率, 经讨论, 选用#47型号步进电机。但是, 在进行了市场调查后, 发现步进电机需要的电源适配器和驱动器的体积太大, 所以, 经再次讨论, 最后选定直流减速电机, 其参数如下:型号:ZGA60FHH68, 空载转速50 r/min, 额定转速35r/min额定力矩8.8kg·cm。经试验算出输入转速为12~15r/min, 因此取两轴传动比i=3。
3.3 回转抽屉传动带 (同步带) 的确定
回转抽屉利用同步带带动盒子转动:
优点:精度高, 重量轻, 可定制, 方便加工, 可吸收一定程度震动, 结合了带传动、齿轮传动和链条传动的特点。
设计背景:抽屉大小大概为500×250mm, 高度约150mm, 理想中心距约250mm。
确定齿形。根据性能及常用性, 选择齿形为梯形齿传动平稳可靠。根据背景结合同步带的系列标准选用L型同步带。
此处选择代号为100的L型同步带, 带宽bs=25.4mm
同时对应选择有双边挡圈的带轮, 对应带轮的最小宽度为bf=26.7
节径d=zPb/ (pai)
外径da=d-2*&
查表得小带轮最小齿数>12
选择齿数z=26
核算确定最终带轮直径与节线长度
此时算得d=78.83mm
带长为L0=26×9.525+250×2=747.65mm, (计算所得带长) 对比同步带节线长度Lp系列:选择
所以选择节线长度Lp=762.00mm
计算所得带长L0=747.65mm
实际中心距a=a0+ (Lp-L0) /2=257.175mm
最终选择型号300L100型同步带, 实际中心距a=257.175, 则Δa=±0.3mm。
4 位置设计
4.1 盖板设计
为使轴轻巧, 考虑到传动力矩和应力要求, 选用6061和6205铝合金。6061铝合金要求有一定强度、可焊性与抗蚀性高的各种工业结构性, 如制造卡车、塔式建筑、船舶、电车、家具、机械零件、精密加工等用的管、棒、形材、板材6205铝合金厚板、踏板与耐高冲击的挤压件。盖板的图为:
4.2 连接件
中间两个通孔用于将同步带与其用钓鱼线牢牢记住, 与同步带接触的面再使用硅橡胶进行粘合和减震, 另一面与盒子间使用AB胶进行固接。
4.3 滚轮的选择与安放
联接点在底板。安装方便, 定位准确, 但当运动不平稳是将导致“卡死”。联接点在盒子。不会出现“卡死”现象, 且所用滚轮少, 但安装稍繁琐。
4.4 用于光电门检测贴片的安装
为使光电门能正常检测到是否有盒子到达指定位置, 我们自主加工了一批贴片用于黏在盒子下方, 伸出一定距离, 被光电门检测到。
采用对极型光电门EE-SX670A, 用以检测是否有盛物盒到达指定位置, 既贴片是否挡住光电门。最后用CAD的系统零件图和装配图, 装配示意图如图所示:
5 控制部分
该项目采用STC89RC52单片机控制, 接受传感器型信号和扫描开关按钮, 控制继电器来控制直流减速电机的运行, 电机的换向用H桥式电路来实现 (如图中的4个继电器) 。利用电路仿真软件得电路图为:
脉冲计算方式为:
如上图所示, 定义顺时针转动为逆向, 逆时针转动为正向。
实物样机
6 结论
研究中, 对利用同步带和链条的抽屉都做了实验, 发现, 利用链条的系统从宏观看是连续的, 但实际上是间断的, 且链条刚度远大与同步带, 所以运动振动小, 利用这一特点可运用在数车的自动换刀上。转动的轴应设计成双轴承系统, 否则过大的剪力会使系统瘫痪。另外, 作为智能抽屉, 程序的后续工作是让其具有自检系统和故障排除系统, 尽量使程序更可靠。
摘要：普通抽屉由于抽出空间的限制, 内部的物品很难抽出, 最重要的是不能实现物品的有效分类。基于此, 利用链条或同步带连续传动且结构紧凑的特点, 结合单片机、光电门、H桥换向电路等电子器件的原理, 设计出了一种新型的智能抽屉, 即自动旋转分类储物柜。它能利用狭长的空间并实现物品的有效分类, 是一种自动的, 有数据储存功能的新型抽屉。实验室的样机表明, 它能实现所述功能, 并能运用于许多场合。
关键词：抽屉,分类储物,同步带,链条,单片机
参考文献
[1]马俊, 王玫.机械制图 (第4版) [M].北京:北京邮电大学出版社, 2007.
[2]秦世伦.工程力学[M].北京:机械工业出版社, 2012.
[3]廖念钊.互换性与技术测量 (第五版) [M].北京:中国计量出版社, 2007.
[4]机械原理 (第七版) [M].高等教育出版社, 2006.
[5]工程力学 (静力学与材料力学) [M].高等教育出版社, 2004.
[6]邱宣怀.机械设计 (第四版) [M].高等教育出版社, 1997.
[7]工程机械[J].道路冰雪清除技术及发展趋势, 2005.
文本自动分类算法的比较与研究 篇6
关键词：文本分类,特征项,支持向量机算法,K近邻法,贝叶斯方法
1 引言
20世纪90年代以来,Internet以惊人的速度发展起来,它容纳了海量的各种类型的原始信息,包括文本信息、声音信息、图像信息等等。如何在浩如烟海而又纷繁芜杂的文本中掌握最有效的信息始终是信息处理的一大目标。基于人工智能技术的文本分类系统能依据文本的语义将大量的文本自动分门别类,从而更好地帮助人们把握文本信息。近年来,文本分类技术已经逐渐与搜索引擎、信息推送、信息过滤等信息处理技术相结合,有效地提高了信息服务的质量。
2 分类算法
简单地说,文本分类系统的任务是:在给定的分类体系下,根据文本的内容自动地确定
文本关联的类别。从数学角度来看,文本分类是一个映射的过程,它将未标明类别的文本映射到已有的类别中,该映射可以是一一映射,也可以是一对多的映射,因为通常一篇文本可以同多个类别相关联。用数学公式表示如下:
其中,A为待分类的文本集合,B为分类体系中的类别集合。
文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息,总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时,根据总结出的判别规则,确定文本相关的类别。
2.1 文本的表示
计算机并不具有人类的智能,人在阅读文章后,根据自身的理解能力可以产生对文章内容的模糊认识,而计算机并不能轻易地“读懂”文章,从根本上说,它只认识0和1,所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”,假定组成文本的字或词在确定文本类别的作用上相互独立,这样,可以就使用文本中出现的字或词的集合来代替文本,不言而喻,这将丢失大量关于文章内容的信息,但是这种假设可以使文本的表示和处理形式化,并且可以在文本分类中取得较好的效果。
目前,在信息处理方向上,文本的表示主要采用向量空间模型(VSM)。向量空间模型的基本思想是以向量来表示文本:(w1,w2,…wn),其中wi为第i个特征项的权重,那么选取什么作为特征项呢,一般可以选择字、词或词组,根据实验结果,普遍认为选取词作为特征项要优于字和词组,因此,要将文本表示为向量空间中的一个向量,就首先要将文本分词,由这些词作为向量的维数来表示文本,最初的向量表示完全是0、1形式,即,如果文本中出现了该词,那么文本向量的该维为1,否则为0。这种方法无法体现这个词在文本中的作用程度,所以逐渐0、1被更精确的词频代替,词频分为绝对词频和相对词频,绝对词频,即使用词在文本中出现的频率表示文本,相对词频为归一化的词频,其计算方法主要运用TF-IDF公式,目前存在多种TF-IDF公式,如下是一种比较普遍的TF-IDF公式:
其中,W(t,d)为词t在文本d中的权重,而tf(t,d)为词t在文本d中的词频,N为训练文本的总数,nt为训练文本集中出现t的文本数,分母为归一化因子。
2.2 训练方法与分类算法
训练方法和分类算法是分类系统的核心部分,目前存在多种基于向量空间模型的训练算法和分类算法,本文以下具体介绍三种分类算法:
1)简单向量距离分类法
该方法的分类思路十分简单,根据算术平均为每类文本集生成一个代表该类的中心向量,然后在新文本来到时,确定新文本向量,计算该向量与每类中心向量间的距离(相似度),最后判定文本属于与文本距离最近的类,它计算新文本特征向量和每类中心向量间的相似度的公式为:
其中,di为新文本的特征向量,dj为第j类的中心向量,M为特征向量的维数,Wk为向量的第K维。
2)贝叶斯算法(Bayes)
该算法的基本思路是计算文本属于类别的概率,文本属于类别的概率等于文本中每个词属于类别的概率的综合表达式,具体算法步骤如下:
Step 1:计算特征词属于每个类别的概率向量,(w1,w2,w3……wn),其中:
计算公式与计算互信息量的公式相同
Step 2:在新文本到达时,根据特征词分词,然后按下面的公式计算该文本di属于类Ci的概率:
其中,P(Cj|θ赞)=Cj训练文档数/总训练文档数,P(Cr|θ赞)为相似含义,|C|为类的总数,N(Wk,di)为Wk在di中的词频,n为特征词总数。
Step 3:比较新文本属于所有类的概率,将文本分到概率最大的那个类别中。
3)KNN(K最近邻居)算法
该算法的基本思路是:在给定新文本后,考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本,根据这K篇文本所属的类别判定新文本所属的类别,具体的算法步骤如下:
Step 1:根据特征项集合重新描述训练文本向量
Step 2:在新文本到达后,根据特征词分词新文本,确定新文本的向量表示
Step 3:在训练文本集中选出与新文本最相似的K个文本,计算公式为:
其中,K值的确定目前没有很好的方法,一般采用先定一个初始值,然后根据实验测试的结果调整K值,一般初始值定为几百到几千之间。
Step 4:在新文本的K个邻居中,依次计算每类的权重,计算公式如下:
其中,x为新文本的特征向量,Sim(x,di)为相似度计算公式,与上一步骤的计算公式相同,而y(di,cj)为类别属性函数,即,如果di属于类Cj,那么函数值为1,否则为0。
Step 5:比较类的权重,将文本分到权重最大的那个类别中。
除此以外,支持向量机和神经网络算法在文本分类系统中应用也较为广泛,支持向量机的基本思想是使用简单的线形分类器划分样本空间。对于在当前特征空间中线形不可分的模式,则使用一个核函数把样本映射到一个高维空间中,使得样本能够线形可分。
而神经网络算法采用感知算法进行分类。在这种模型中,分类知识被隐式地存储在连接的权值上,使用迭代算法来确定权值向量。当网络输出判别正确时,权值向量保持不变,否则进行增加或降低的调整,因此也称为奖惩法。
2.3 考虑词序的扩展算法(The Extending Algorithm Based on Word Order)
一篇文档中常有一些词串(又称n-grams)不止一次出现,且大部分构成有序的名词短语。例如“machine learning”,“imitation game”等在A.M.Turning所著的文档“Computing Machinery and Intelligent”中多次出现。这些词串应作为整体视为文档的特征词,并且当用户仅选定词串的部分单词作为查询时,剩下的单词应该首先被提交作为用户查询的扩展信息。
短语是词的搭配信息的一种,可以被视为单词之间的一种强关联关系。一般通过数据挖掘中的技术[韩家炜2001],如APPRI-ORI算法[Fürnkranz 1998]或者统计学理论,如互信息、假设检验等方法从大量的语料库中来抽取词与词之间的搭配关系。由于目前没有大量的相关文档测试集,同时APPRIORI算法会产生大量的侯选项集,我们采用以下相对较简单的方法从文档中抽取高频的二元词串作为文档短语。
我们假定文档的短语均由实词构成,即短语中不含有停用词表中的单词,如短语“of course”就不能被看作文档短语。系统首先利用停用词表从文档中去除频率极高且与文档主题无关的词,如the,a,there等等;然后通过词频统计,将低频词(出现频率低于2)去除,剩下的单词放入一个名为Concurrence Set的集合。文档中的每个句子被视为词的有序集合,对于Concurrence Set中的每个单词t,找出紧邻它的前一个单词或后一个单词k,判断它是否属于Concurrence Set。如果k属于Concurrence Set,并且作为词t的紧邻在文档中的不同句子中出现,则可以认为词k与词t构成了文档中的一个二元短语。
因此,利用词与词之间的有序关联与共现关系,可以较全面地反映一篇文档的主要观点,快速确定相应的类别,有助于新文档的分类,并且能够帮助用户方便地了解文档的主要内容,这一方面从一个侧面反映了用户的搜索兴趣,另一方面帮助用户确定检索领域。在本文中,笔者充分考虑词序关联与共现关系,提出了考虑词序的扩展算法,简写为Eab-Wo。
3 算法实验分析
本文实验数据是直接利用搜索引擎从雅虎网(http://news.yahoo.com)上按新闻的11个类别分别下载了一定数量的文档,保存到本地数据库中,然后进行分析,加入了部分人工处理后得到的一组数据来测试的。实验采用查全率和查准率的评定标准。实验结果见表1。
如表1所示,通过比较、分析各类算法表明,考虑词序可以更好的提高分类的查准率和查全率,得到更有效的分类结果。本实验是在封闭的数据集上进行的。由于实验条件、数据规模、个人技术能力等方面的不足,算法仍处在初步试验阶段。
参考文献
[1]Evgeniy Gabrilovich,Susan Dumais,Eric Horvitz.Newsjunkie:Providing Personalized Newsfeeds via Analysis of Information Novelty.WWW2004,May17-22,2004,New York,USA.
[2]Davi de Castro Reis,Paulo B.Golgher,Altigran S.da Silva.Automatic Web News Extraction Using Tree Edit Distance.WWW2004,May17-22,New York,USA.
[3]王煜,白石,王正欧.用于Web文本分类的快速KNN算法[J].情报学报,2007,26(1):60-64.
[4]李杨,曾海泉,刘庆华,等.基于kNN的快速WEB文档分类[J].小型微型计算机系统,2004,25(4):725-729.
[5]厉宇航,罗振声,程慕胜.基于概念层次的英文文本自动分类研究[J].计算机工程与应用,2004(11):75-77.
自动分类技术 篇7
最近的研究表明Surface Web已经链接到了数十亿的静态页面,然而Web上有部分内容不能通过超链接直接访问到。这部分页面仅当用户填充表单并提交查询后才可以访问。这部分页面被称为是Hidden Web或者Deep Web[1,2]。根据Bright Plant公司的调查[3]已知:在内容上,Deep Web网站比Surface Web网站更专、更深,Deep Web提供的内容主要是后台的网络数据库[4],每个信息都可以通过一个或多个HTML表单查询到;在质量上,来源于这些网站的信息是高质量的,对于用户来说具有更高的价值。一方面考虑到Web的动态特性,即新资源的上载和旧资源的删除或者修改。能够通过简单使用HTML表单接口来自动发现这种Deep Web网站极其重要[5]。另一方面,由于网络数据库的领域特性,用户一般只对其中特定的领域感兴趣。有效地利用这些网络数据库中的信息,需要将其按领域进行分类。
为了定位Deep Web数据源,对一个比较好的定位机制的需求也迫在眉睫。文献[6]中提出的使用机器学习中C4.5决策树的方法来实现Web上查询接口的判别,其主要分两个步骤:首先是查询接口特征的自动生成,其次是以这些特征为依据,利用C4.5算法得到一棵决策树,通过这棵决策树来进行查询接口的判定。实验结果表明:从Web中随机查询的数据集准确性达到了87%,显然还有很大的提升空间,其实还有一些有用的信息可以利用,如HTML表单中,控制组件之间的文档内容,控制组件的数量和布局,页面中的频繁词汇等等。文献[7]提出了一种利用朴素贝叶斯分类算法的自动判定网页表单是否是Deep Web查询接口的方法,文章提取了HTML表单标签的属性值和控件类型以及控制标签之间的词汇信息等作为贝叶斯分类的特征集,实验结果表明在查询接口的查全率和查准率方面都有提高,但是忽略了整个页面的信息和数据源的领域相关性。文献[8]使用强化学习来建立一个聚焦爬虫,其对于分散的概念比较有效,并且其设计是用来搜索非Hidden Web数据库的内容。文献[9]提出了一种使用强化学习的基于Agent的Hidden Web爬虫(ALAC)来实现Deep Web数据源的判别。
本文描述了一种多分类器来实现对Deep Web数据源的分类和判别的方法,首先使用聚焦表单的爬虫实现对页面表单的抓取,然后利用朴素贝叶斯分类器对文档页面领域性分类的优势,对于抓取到的表单页面进行领域相关性分类,获取所需的领域信息,过滤非领域相关性的页面信息,最后依据C4.5决策树分类器对于查询接口判别错误率低的特点,对抓取到的领域表单页面进行查询接口的判别。
1 数据源的分类和判别框架
数据源分类的目标是在聚焦爬虫检索到的异构的表单中只选择领域相关和作为查询接口的表单。过程如下:给定一个Web表单的集合F和网络数据库领域D,这里F是通过聚焦爬虫自动搜集到的。目标是从集合F中选出那些仅作为D中某一特定领域的可查询的表单,过滤掉与特定领域不相关的可查询表单和非查询功能表单。
定义1
可查询表单作为网络数据库的查询接口,通常是以HTML中的表单的形式表示,当用户提交要查询的信息时,网络数据库会返回其查询结果的那些表单。
定义2
非查询表单主要包括两部分的信息。其一,只是作为信息的提交功能,虽与网络数据库进行交互,但是不会返回查询结果的表单;其二,作为搜索引擎或者元搜索引擎的表单,虽然返回查询结果,但结果一般是非结构化或者半结构化链接信息。
HTML表示的网页中包含有大量复杂的信息,可以从中获取大量有用的信息集合。网页特征的选择对于网页分类的速度和精度都至关重要。因此,如何有效地选择合适的网页特征对网页进行描述,是进行网页表单分类和判别的首要问题。
传统的查询接口分类与判别方法,如决策树和贝叶斯,其原理是对于提取到的表单页面,使用单一分类器分析表单文本与结构特征来实现查询接口的分类和判别,这样用于分类的特征就局限到表单内的特征,而忽略了整个页面的文本信息,而且单一分类器只对于某一功能有优势(贝叶斯对于接口分类有优势,决策树对于判定查询接口有较小的出错率)。故这里提出了一种分层的思想,即使用不同分类器分别对Deep Web数据源进行分类和判定。在这里,关注于提取整个页面的文本信息(用于表单网页的分类)和表单包含的全部信息(作为查询接口判别的特征)。
本文通过三个基本组件来实现上面的功能:基于表单的聚焦爬虫(FFC)、表单页面分类器(FPC)和表单分类器(FC)。图1显示了其结构框架。
聚焦爬虫工作原理
首先给定一个主题相关页面作为种子,然后宽度搜索其中静态连接,将链接到的包含HTML表单的页面抓取下来。在爬虫的抓取过程中,本文用到了一种有效的爬虫终止策略:1)当爬虫检索到一个给定的表单个数的时候,爬虫就离开此网站;2)当爬虫在一个网站上爬过的超链接超过提前预定的个数的话,爬虫也终止此网站的爬行。聚焦爬虫功能是根据页面之间的特征,将爬行的主题集中到含有表单信息的页面,从而避免了在非表单页面上的消耗。
表单页面分类器
将由爬虫获取到的表单页面,使用改进过的朴素贝叶斯分类器将包含表单的页面根据其领域相关性自动识别其领域,过滤掉不相关领域内的表单。
表单分类器
表单分类器将使用改进的C4.5决策树算法对相关领域的表单进行查询接口的判别,将其分为可查询的和非查询的表单,其细节将在下面内容讨论。
2 数据源的分类和判定
2.1 表单页面的分类器
表单页面分类可作为文本分类技术的一种扩展,但表单网页的特征比较复杂,网页格式灵活,而且同一格式的网页也存在多个标准,因此对其分类相比较于文档分类要难于处理,这里引入了朴素贝叶斯文档分类器。根据贝叶斯学习框架对于文档分类的处理过程,这里首先对特征进行标准化以提高分类的准确性。假设文档数据是通过参数模型产生的,使用训练数据来计算模型参数的最大后延估计。根据这个估计,来对新的测试文档所生成的模型使用贝叶斯规则计算其所属类别的后延概率来对其进行分类。分类过程就是将文档归类到有最大概率的类别里面。
贝叶斯分类器使用文档频率和词频对文档类别参数化。每个类别cj有一个和其它类别相关的先验概率P(cj),通过包含不同词汇的多项式模型来表示文档类别。也就是说,对于词汇表V中的每个词wt,P(wtcj)表示分类器在给定具体的类别cj时此词wt发生的概率。下面用di表示一个文档,它是一个无序的词的集合。为了使用此分类模型对其分类,首先假设对于每一个给定的类别,每个文档中出现的单词是相互独立的。利用此假设,分类问题就显得比较直接了。计算此文档di相对于文档类别cj的概率P(cjdi)并将其归类到P(cjdi)值最大的类别cj中。然后用wdik表示在文档di中的第k个词。根据前面的假设,使用贝叶斯规则可将P(cjdi)扩展为:
通过训练集合来学习到P(cj)和P(wtcj)这些参数值。与传统的贝叶斯分类不同的是,为了避免零概率可能会消除乘积中涉及的所有其他(后验)概率的影响,将拉普拉斯校准分别用于计算先验概率P(cj)和条件概率P(wtcj)。
算法1朴素贝叶斯分类器学习算法
其中,Examples为一组页面及其目标值,C为所有可能的目标值的集合。此函数作用是学习概率项P(wtcj),它描述了从类别cj中的一个页面文档中随机抽取的一个词为wt的概率。该函数也学习类别的先验概率P(cj)。
1)网页文本处理
(1)页面预处理。
(1)HTML去噪,删除HTML标签;
(2)Anchor Text提取,提取文档的In-link和Out-link Anchor Text;
(3)中文分词。
(2)特征选词
(1)禁用词表,预定义禁用词表,将禁用词表中出现的词从文档的特征向量中删去;
(2)词性选择,基于ICTCLAS的分词结果,只特定词性标注的词作为特征项;
(3)信息增益,对数据集进行特征降维,压缩特征空间;
(4)存放处理结果到DOC文档中。
(3)集Examples处理后的DOC文档中所有词以及其它信息:
V←将处理后的文本信息出现的所有词和记号的集合。
2)计算所需要的概率项P(cj)和P(wtcj)
根据上面贝叶斯文本分类器对于文档分类的知识分可知:
对C中的每个目标值cj
(1)docj←文档DOC中目标值为cj的文档子集;
其中di∈DOC,|C|表示目标值个数;
对V中每个词wt
(1)N(wt,di)表示为单词wt出现在文档di中的次数,并且P(cjdi)∈{0,1},作为表示文档的类别标签;
算法2贝叶斯分类算法
对待分析页面进行预处理,处理结果存入文档Doc中,文档Doc返回其估计的目标值。ai代表在Doc中的第i个位置上出现的词。
1)positions←在Doc中的所有词的位置,它包含能在V中找到的记号;
2)返回vNB:
对于给定的大量的训练文档,朴素贝叶斯分类器在文本文档分类方面表现良好[10],关于贝叶斯文本分类的细节在文献[11]有详细的描述。对于这里的分类只关心是否是用户关心的领域页面表单。
2.2 查询表单的判别分类器
在2.1节中,使用朴素贝叶斯对包含表单的页面进行领域分类,提取出感兴趣的页面,然后对固定领域的表单进行查询接口的判定。HTML表单包含有复杂的结构,通过它可以得到一个特征丰富的集合。事实上,表单结构化的特征就可以作为判断此表单是否是查询接口的一个指示器。此部分描述了一个自动产生HTML表单特征的方法作为有效进行查询接口探测的标准。
图2显示了统计得来的一些数据信息。由图2知:可查询的表单有比较多的Selection List和Check Box,而非查询表单有比较多的Text Box。其它的一些结构信息也被用来作为C4.5决策树的特征,如:hidden标签的个数,Radio标签的个数,Submit标签的个数,Password标签的个数,Text Box的个数,Submit的方法,还有一个很有用的是“查询”“搜索”此类别的关键字。事实上,表单中查询关键字和提交按钮的出现在特征集中拥有最高的权值。上面提到的特征信息都是可以从Web表单中自动提取的,不需要手工的预处理。在文献[6]提出使用决策树来对查询表单进行分类,此分类器使用的特征是其自动从表单提取出来的。因为此策略同时也考虑到表单标签内部的文本信息,使得策略最后要考虑的特征个数多于550个。而这里只用到了17个特征,这样极大地压缩了分类的特征空间。
这里用机器学习中的C4.5决策树算法进行判定。因为它有比较小的错误率,而且可以根据产生的特征类型对算法进行修改,更重要的是此算法会生成一个规则树,可以描述成简单的分类规则:IF条件成立,THEN判断是/否查询接口。而规则树的生成过程就是将分类能力最好的属性作为树的根节点进行测试,然后为根节点属性的每个可能值产生一个分支,并把训练样例排列到适当的分支之下。然后重复整个过程,用各个分支节点关联的训练样例来选取在该点被测试的最佳属性。一旦规则树生成后,查询接口的判定问题就简化为规则树的条件逻辑问题。
3 实验结果与分析
为了验证使用多分类器进行查询接口分类和判定的有效性,实验中从对于表单的网络爬虫随机抓取的网页中抽取大量的网页表单,然后手工对其进行分类,选取了65个Deep Web查询接口和130个非查询接口组成的训练集,140个Deep web查询接口和160个非查询接口组成的测试集,测试其与单一使用C4.5决策树分类器或贝叶斯分类器比较结果如图3所示。
实验表明,和单一使用C4.5决策树或贝叶斯分类器相比,此方法在精度和召回率方面都有所改善,特别是精度。召回率实验结果中,多分类器和C4.5决策树和单一贝叶斯方法相比效果虽有改进但不是很明显,它是使用贝叶斯分类器对页面进行分类时产生的误差引起,在图书领域有显著增强。分析原因,图书页面中含有丰富的文本信息,经过分词处理,与图书相关的关键词的出现以及词频,使得在使用朴素贝叶斯分类时,能更准确的将其进行分类;精度实验结果与C4.5和贝叶斯方法相比有较大提高,工作、图书、租赁领域,其精度都在90%以上,特别是工作领域其精度达94.4%。分析原因是,对于同一领域的页面表单,HTML表单的结构和特征有大的相似性,其中用到的Check Box和Select List比较多,Text Box比较少,而且对于特殊的领域,为了方便用户进行查询,网络查询接口提供给用户的选择控件的功能是一致的,这样多分类器中的决策树分类器更能将查询接口从中正确判别出来。
4 结束语
随着Deep Web数据库数量和其蕴含数据量的增长,对Deep Web数据的集成越来越成为研究领域关注的问题,而Deep Web数据源的分类和判别是进行Deep Web数据集成的基础,其二者的结合不仅保证了更高的准确性和效率,而且更有其实际应用意义。本文在研究以往判别查询接口方法的基础上,针对其提取特征方式不同和精度低以及忽略领域相关性的问题,提出了一种结合多分类器的方式来对Deep Web数据源进行分类和判别。实验结果比较于使用单一决策树分类器,在召回率和精度方面都有提高。以后的工作是对此种方法中的领域分类结果进行分析,分析出不同领域的查询接口的特征,缩小贝叶斯分类器在进行网页分类的错误率,根据提取不同领域的特征信息来提高查询接口的召回率和精度。
参考文献
[1]Bergman M K.The deep web:surfacing the hidden value[J/OL].The Journal of Electronic Publishing,2001,7(1).http://www.press.mich.edu/jep/07-01/bergman.html.
[2]Chang K C C,He B Li.CStructured databases on the Web:Observa-tions and Implications[R].Technical Report,UIUC,2004.
[3]Bergman M K.Deep Web Whitepaper[EB/OL].2004.http://briight-planet.com.
[4]Fllorescu D Levyay,Mendel A Zon.Database techniques for the world-wide web:A survey[J].SIGMOD Record,1998,27(3):5974.
[5]He B,Pater M,Zhang Z.Accessing the Deep Web:A Survey[C]//Communications of the ACM(CACM),2007.
[6]Cope J,Craswell N,Hawking D.Automated Discovery of Search Inter-faces on the Web[C]//Proceeding of ADC2003,2003.
[7]高岭,赵朋朋,崔志明.Deep Web查询接口的自动判定[J].计算机技术与发展,2007,17(5):14815.
[8]Rennie J,McCallum A.Using Reinforcement Learning to Spider the web Efficiently[C]//Proceeding of ICML,1999.
[9]Akilandeswari J,Gopalan N P.A Novel Design of Hidden Web crawler Using Reinforcement Learning[C]//APPT2007.Based Agents.Berlin Heidelberg,c2007.
[10]David D Lewis.Naive(Bayes)at forty:The independence assumption in information retrieval[C]//ECML-98.1998.
自动分类技术 篇8
Web已经发展成为拥有巨大信息资源的分布式信息空间, 包含有巨量的各种类型的Web文档。搜索引擎很难满足不同用户对检索结果精化的要求。本文研究的Web文本自动分类系统, 通过学习用户感兴趣的样本文本自动建立用于Web文本分类的特征词库, 通过特征词条匹配自动实现Web文本分类, 有效提高检索的精度, 给出符合用户要求的定制检索结果, 可以大大降低人工二次浏览筛选的工作量。
1Web文本自动分类系统总体框图
1.1网络蜘蛛
网络蜘蛛有两种策略来遍历Web空间:广度优先和深度优先。采用广度优先策略, 有利于提高网络蜘蛛的抓取速度。
要正确提取HTML文档中所需的链接和文本信息, 首要的问题是对HTML进行解析, 将HTML字符流变为由HTML标签系列组成的结构化文档。按照Robots协议, 网络蜘蛛进入一个网站时应首先访问一个特殊的文本文件Robots.txt, 这个文件通常置于网站服务器的根目录下, 网站管理员可以通过Robots.txt来定义哪些目录不能被网络蜘蛛访问, 或者哪些目录对于某些特定的网络蜘蛛不能被访问。网站管理员建立将链接信息写入sitemap.htm中, 那么, 网络蜘蛛可以把sitemap.htm文件作为网站Web文档抓取的入口。
1.2HTML结构化解析
网络蜘蛛抓取的Web文档中包括多种格式的信息, 如HTML档、图片、DOC文档、PDF文档、多媒体信息及其它格式的信息基于Web文本内容的分类对其中的图片和声像信息并不感兴趣, 应将其剔除。静态Web文档是HTML格式文档, 动态Web文档是由脚本来动态生成的HTML格式文档。因此, 从客户端的角度来看, 静态Web文档和动态Web文档并无不同。网络蜘蛛在获得了HTML格式的文档后, 将提取其中的链接信息来跟踪子链接, 提取其中的文本信息供文档分类使用。
1.3Web文本预处理
Web文本预处理包括文本内容过滤和中文分词。文本内容过滤是从网络蜘蛛输出的Web文本中提取用于分类的文本内容, 中文分词把中文文本内容切分成中文词条。
网络蜘蛛输出的Web文本仅包括HTML标记、文本和脚本。由Web文本过滤模块对脚本和HTML标记进行过滤, 提取所需的用于文档分类的文本内容。由于中文文本没有显式的词条分隔标志, 中文分词的任务是将中文词条自动分隔开来获得中文文本使用的中文词条集。由Web文本过滤模块对脚本和HTML标记进行过滤, 提取所需的用于文档分类的文本内容。而中文词典的存储结构采取词库按词条的长度分为4个子库, 分别容纳四字词、三字词、双字词和单字词。词库的存储结构为哈希表, 因此构建4个哈希表分别存储四字词、三字词、双字词和单字词。词条按长度分别被存入到对应的哈希表中。词条在哈希表中的存放位置由词条的哈希码决定。对于中文文本切分经过综合比较分析, 采用最大匹配法 (MM) 既简便易行, 又能保证分类的质量。
1.4特征选取与文本分类
文本分类是按预先定义的类别, 确定待分类文本的类属, 文本分类的依据是词条 (term) 在文本中的使用。通常, 一个文本的词条很多, 不可能将这些词条都作为分类的特征, 这就需要从文本被切分后获得的词条集中挑选出若干具有分类意义的特征词条组成用于分类的特征词条集。
基于机器学习的自动方式主要是通过对若干不同类别文本的学习, 自动建立特征词库。而且, 当供学习的样本文本更新后, 通过重新学习就可自动更新特征词库, 以适应对新的文本类别的分类识别。
在对一系列的特征选取算法进行了比较分析后, 采用了称之为文本频度与词条频度综合法, 简称为DFTF (Document Frequency and Term Frequency) 方法来实现特征选取。任何一个待分类的文本经过 “中文词条切分”处理后, 得到该文本的词条集, 在特征词库的支持下, 由“文本分类器”得出该文本的所属类别。文本分类器把文本词条集中的词条逐一与特征词库中的特征词匹配, 然后采用贝叶斯分类算法得出该文本所属类别。
采用改进了的贝叶斯文本分类算法, 其算法如下:
1、从词条集Tx中依序逐一取出词条与特征词库中的特征词进行匹配, 若txk与ti (cj) 匹配, 则将类别cj赋予txk, 记为txk (cj) ;若txk与所有特征词匹配失败, 则取下一个词条。直到Tx为空集, 得到分类后的词条集为{txk (cj) }。 (k=1, 2….n;j=1, 2….mx)
2、逐一计算词条的类条件概率undefined式中, nkj、nxj与前面定义的相同;m是一个常量, 称为等效样本大小;p是将要确定的概率的先验估计, 在缺少p的先验概率的知识背景的情况下, 一种典型的方法是假定遵循均匀的先验概率, 也就是说, 如果有M个分类, 可取P=1/M。
3、计算文本x的类条件概率
undefined
4、计算文本x属于某个类别cj的概率
undefined
其中, undefined
5、取max{P (c1|Tx) , P (c2|Tx) , …, =P (cmx|Tx) }的文本类别为文本x的类别。
2实验与测试结果分析
为了测试研制的Web文本自动分类系统的性能, 这里选择了30个样本文本, 并对系统中待定参数选取了3种不同的值, 自动生成三个不同的特征词条库, 然后分别用于对随机选取的10个Web文本进行自动分类, 讨论测试结果并予以分析。
2.1特征选取的测试结果与分析
首先从因特网上下载了30篇Web文档作为样本文本。经过人工判读文本内容, 其中10篇文本的类别确定为“反动言论类 (c1) ” , 10篇文本的类别为“利用互联网贩黄赌博诈骗类 (c2) ”, 另外10篇文本的类别为“社会新闻类 (c3) ”。这三类样本文本的标题及字数分别为表1、表2、表3所示:
对上述三类30篇样本文本经中文分词后得到的词条集中的各类词条数如表4中所示。采用文本频度与词条频度综合方法对该词条集进行特征词条选取, 对三类词条子集删除各自重复词条后的词条数分别如表4 中所示。在DFTF选取方法中, 取文本频度系数α=0.4, 词条频度权系数β=0.6。
为了比较DFTF方法中, 不同过滤阈值对提取特征词条的影响, 分别设定λ=0.4、λ=0.6和λ=0.8进行测试, 不同阈值对获取的特征词库的影响如表5所示。
由表4和5中的数据可见, 若取阈值λ=0.4, 则将样本文本切分后的13205个词条过滤至2580个特词条;若取阈值λ=0.6, 则过滤至1956个特征词条, 且对三类词条的降维程度大致相当;若取阈值λ=0.8, 则过滤至1271个特征词条, 其中对c3类词条的降维程度大大超过c1类和c2类词条。事实上, c3类是“社会新闻”类, 该类文本内容用词的广泛程度远超过“国内外足球比赛”类 (c1类) 和“利用互联网贩黄赌博诈骗类” (c2类) 的文本, 因此c3类词条的综合频度将低于c1类和c2类词条。当取较高的阈值对词条过滤时, 会将较多的c3类词条过滤掉, 将对c3类Web文本的分类识别产生不利影响。
2.2文本分类的测试结果与分析
根据Web文本的标题随机下载了10篇Web文本, 分别在上述3个特征词库的支持下进行文本自动分类。自动分类的结果和人工阅读文本内容后给出的分类结果如表6所示。
表6中, 序号7的文本内容是介绍一位著名科学家的生平与业绩, 序号9的文本内容是讨论基于网络平台的分布式订票系统的构建技术, 这2个文本人工分类为c4类, 即不属于c1～c3类。
由于贝叶斯分类器不具备拒识功能, 只能将这2个文本分类为c1～c3类中的某一类, 因此, 自动分类结果与人工分类结果不一致。另外, 序号4的文本在特征词条数较多的特征词库1的支
持下, 自动分类结果正确;在特征词条较少, 尤其是c3类特征词条较少的特征词库2或特征词库3的支持下, 自动分类结果错误。对上述10篇Web文本自动分类的正确率分别是0.8、0.7和0.7。
根据测试结果, 可以得出以下结论:①分类的类别数应足够多, 应能覆盖人工分类的类别;②各类的样本文本数应较多, 从中提取一批覆盖面宽、代表性强的特征词条;③特征词库的规模越大, 分类正确率越高, 但是, 将导致自动分类的时空开销越大, 因此, 阈值的选取十分重要;④本文给出的贝叶斯分类算法不具备拒识功能, 从而增大了误识率。可以对本文给出的贝叶斯分类算法的第5步予以修正:对文本类别概率P (cj|Tx) 设一个阈值λ, 若对所有的类别都有P (cj|Tx) <λ, 则对文本Tx拒识;否则, 取max{P (c1|Tx) , P (c2|Tx) , …, P (cmx|Tx) }的文本类别为文本x的类别。
3结束语
本文提出了一种基于机器学习的Web文本自动分类系统的实现方案, 并详细分析了各功能模块实现的方法、算法和技术。有以下几点反映出我的研究成果:①中文词典的存储结构采用多个哈希表;②采用机器学习的特征词条选取方法来自动建立特征词库, 从而可通过重新学习来自动更新特征词库, 以适应对新的文本类别的分类识别。给出了一个简便易行、时空开销相对较小的特征词库选取算法文本词条频度法;③对贝叶斯文本分类算法进行了修正, 用m-估计计算代替词条的类条件概率的计算, 从而避免了出现概率较低的词条对计算文本分类概率值过于强势的影响。
参考文献
[1]尹朝庆, 尹皓.人工智能与专家系统[M].北京:中国水利水电出版社, 2001.
[2]FREITAG D.Information exteactionfrom HTML:Application of aGeneral Machine Learning Approach[A].AAAI’98[C], 1998.
[3]李晓黎.网上信息检索与分类中的数据采掘研究[D].中国科学院计算技术研究所, 2001.
[4]黄萱菁, 吴立德, 王文欣, 等.具有机器学习的无需人工编制词典的切词系统[J].模式识别与人工智能, 1996 (9) .
[5]何克抗.书面汉语自动分词专家系统设计原理[J].中文信息学报, 1991 (2) .
[6]陈振南.特征选取与权重分配于中文新闻分类之比较[D].国际资讯管理学术研讨会, 2002.
[7]郑海, 林鸿飞.给予段落匹配的文本分类机制[J].计算机工程与应用, 2004 (2) .