（计算机应用技术专业论文）基于形式概念分析的中文网页分类研究.pdf

西华大学学位论文独创性声明 ：所呈交的学位论文，是本人在导师的指导下进行研究 。尽我所知，除文中已经注明引用内容和致谢的地方外， 个人或集体已经发表的研究成果，也不包含其他已申请 用过的成果。与我一同工作的同志对本研究所做的贡献 明确的说明并表示了谢意。 ，本人愿意承担相关法律责任。 学位论文作者签名：翻& 芡 日期： 7 。 11 6 i 指导教师签名： 日期 莎( t i b 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使甩学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名：翻文焚 日期：劲r7 ；7 指导教师签名： 日期 少八，l 7 西华大学硕士学位论文 摘要 随着i n t e m e t 的不断发展，互联网上的信息越来越多，互联网也随之成了人们获取 信息的巨大资料库。但是网上的信息错综复杂，人们在搜索信息的时候很容易查到一些 相近却不相关的信息。这些不相关的信息严重影响了人们对准确信息的查找效果。所以， 如何使人们从互联网中快速准确的获取到自己想要的信息，就成为我们必然的研究趋 势。 为了方便用户获取互联网上的信息，研究者推出了搜索引擎。搜索引擎无疑为人们 获取知识提供了方便。然而多数搜索引擎的返回结果的数量十分庞大，而且返回的许多 搜索结果不太符合用户的搜索意图。为了解决这一问题，研究者们经过深入探索，提出 了分类技术。他们将数量庞大的搜索结果分别归类到相应的领域中。当用户从相应的数 据领域中查找所需要的信息时，搜索引擎就会快速高效的返回正确的查询结果。因此， 分类技术已经成为数据挖掘和搜索引擎的重要部分。 在万维网出现以前，分类技术般都应用于普通文档的分类。同时出现了许多针对 文档分类的相关技术，如a t c 等。随着网络的不断发展，网页随之产生。网页作为一 种信息载体，与人类生活变得息息相关。网页分类作为一种搜索引擎的重要技术，被广 泛应用于信息检索、主题搜索、关键字查找以及数字图书馆等领域。 到目前为止，已经出现了多种分类方法。但是很多中文网页分类方法的分类效率和 准确率不太令人满意。为了改善中文网页的分类状况，本文利用形式概念分析的基本知 识，提出一种基于概念格的k n n 分类方法。该方法主要利用先聚类后分类的思想，使 得分类效果更加准确。在运用该思想的过程中，本文将类别概念定义为从概念格中选取 出来的用于分类的所有概念。本文将概念格进行的一次聚类理解为第一次分类，二次分 类是首先将选取出来的类别概念进行归类，建立一个向量空间模型，其中，类别概念对 应向量空间模型中的列向量，类别概念的属性对应向量空间模型中的行向量。同时，待 分类网页也用向量表示，然后结合k n n 分类算法，实现中文网页的分类。在概念格与 k n n 结合的过程中，本文需要处理两个问题：( 1 ) 特征项的选取。( 2 ) 类别概念的提 取。 本文通过基于概念格的k n n 分类方法，不仅降低了向量空间的维数，进而提高了 分类效率，而且提高了网页分类的准确率和召回率。 关键词：网页分类；类别概念；概念格；形式概念分析 基于形式概念分析的中文网页分类研究 a b s t r a c t w i t ht h ed e v d o p m e n to fh t e r n e t ，a sm o r ea n dm o r ei n f o r m a t i o na r i s e so nt h ew e b ， i n t e r n e th a sb e c o m eah u g ed a t a b a s ef o rp e o p l et oo b t a i ni n f o r m a t i o n h o w e v e r , b e c a u s e 也e c o m p l e xo fi n f o r m a t i o no nt h ei n t e r a c t ，i ti se a s yt os e a r c hs o m es i m i l a ra n di r r e l e v a n t i n f o r m a t i o nw h e nw ed os e a r c hw o r k t h e s ei n e l e v a n ti n f o r m a t i o ns e r i o u s l ya f f e c t st h ee f f e c t o fo u rs e a r c h i n gt h ea c c u r a t ei n f o r m a t i o n 缸ar e s u l t h o wt om a k eu st oo b t a i nn e c e s s a r y i n f o r m a t i o nq u i c k l ya n da c c u r a t e l yf r o mt h eh t e m e tw o u l db e c o m ea l li n e v i t a b l er e s e a r c h 仃e n d i no r d e rt og e ti n f o r m 撕o no nt h ei n t c m e tc o n v e n i e n t l y ，r e s e a r c h e r sp r o p o s es e a r c h e n g i n e i ti st r u et h a ts e a r c he n g i n em a k e su sg e tk n o w l e d g em o r ee a s i l y h o w e v e r , m o s to f r e s u l t sf r o ms e a r c he n g i n e sa r eh u g ea sw e l la sn o ta c c o r dw i t hs e a r c hi n t e n t i o no fu s e r t o s o l v et h i sp r o b l e m ，t h er e s e a r c h e r sp r o p o s ec l a s s i f i c a t i o nm e t h o dt h r o u g hd e e p l ye x p l o r a t i o n a n ds t u d y t h e yc l a s s i f yt h eh u g pr e s u l t sf r o mi n t e m e ti n t ot h ea p p r o p r i a t ef i e l d s ；w h e nt h e x l $ e r ss e a r c hn e c e s s a r yi n f o r m a t i o ni nc o r r e s p o n d e n t6 e l d ，s e a r c he n g i n ew i l lr e t u l nr 也e c o r r e c tr e s u l t sq u i c k l ya n da c c u r a t e l y t h e r e f o r e ，t h ee l a s s i f i c a t i o nm e t h o dh a sb e c o m ea n i m p o r t a n tp a r to ft h es e a r c he n g i n ea n dd a t am i n i n gt e c h n o l o g y b e f o r et h ea d v e n to ft h ew o d dw i d ew e b ，c l a s s i f i c a t i o nt e c h n o l o g yi sg e n e r a l l ya p p l i e d i n t ot h ef e l do fd o c u m e n t se l a s s i f i c a t i o n a tt h es a m et i m e ，t h e r eh a v ea p p e a r e dm a n yr e l a t e d t e c h n o l o g i e sf o rd o c u m e n tc l a s s i f i c a t i o n ，s u c ha sa t c e t c a st h ed e v e l o p m e n to fn e t w o r k s ， w e bp a g e sa p p e a r w e ba sa ni n f o r m a t i o nc a r r i e r , i sc l o s e l yr e l a t e dt oh u m a nl i v e s w c bp a g e c l a s s i f i c a t i o na sam a j o rs e a r c he n g i n er e l a t e dt e c h n o l o g yi sw i d e l y u s e di ni n f o r m a t i o n r e t r i e v a l ，s u b j e c ts e a r c h , k e y w o r ds e a r c h ，d i g i t a ll i b r a r i e sa n do t h e rf i e l d s s of a r t h e r eh a v eb e e ns e v e r a le l a s s i f i c a t i o nm e t h o d s b u te 简c i e n c ya n da c c u r a c yo f m a n yc h i n e s ew e bp a g ec l a s s i f i c a t i o nm e t h o di sn o ts a t i s f i e d t oi m p r o v et h es i t u a t i o no f c h i n e s ew c bp a g ec l a s s i f i c a t i o n ，c o n s i d e r i n gt h eb a s i ck n o w l e d g eo ff o r m a lc o n c e p ta n a l y s i s ， w ep r o p o s ek n n b a s e dc l a s s i f i c a t i o nb a s e do nc o n c e p tl a t t i e e t h em a i ni d e ao ft h em e t h o d i sc l a s s i f y i n gt h ew e bp a g e sa f t e rc l u s t e r i n gt h e ma n dt h i sc a nm a k et h ec l u s t e r i n gm o r e a c c u r a t e l y t h ec a t e g o r yc o n c e p t sa r ed e f i n e da st h ec o n c e p t ss e l e c t e df r o mt h ec o n c e p t l a t t i c ef o rc l a s s i f y i n gi nt h em e t h o d i nt h i sp a p e rt h ec l u s t e r i n gb a s e do nc o n c e p tl a t t i c ec a n b et r e a t e da st h ef i r s te l a s s i f i c a t i o n t h ep r o c e s so ft h es e c o n dc l a s s i f i c a t i o ni sa sf o l l o w s ：t h e s e l e c t e dc a t e g o r yc o n c e p t sa r ec l a s s i f i e da n dt h e nw ee s t a b l i s ht h ev e c t o rs p a c em o d e li n w h i c he a c hc a t e g o r y c o n c e p ti sc o r r e s p o n d i n gt o o n ec o l u m n ，a n dt h ea t t r i b u t e so ft h e c a t e g o r yc o n c e p ta r ec o r r e s p o n d i n gt oo n er o w m e a n w h i l e ，t h ew e bp a g e s t ob ec l a s s i f i e da r e r e p r e s e n t e da sv e c t o r s t h e nk n nc l a s s i f i c a t i o na l g o r i t h m i su s e dt oa c h i e v et h e 西华大学硕士学位论文 c l a s s i f i c a t i o no fc h i n e s ew e bp a g e s w es h o u l dd e a lw i t ht w op r o b l e m si nt h ec o m b i n a t i o n t h e ya l e ：( 1 ) t h es e l e c t i o no f t h ef e a t u r ei t e m ( 2 ) t h ee x t r a c t i o no f t h ec a t e g o r yc o n c e p t t h r o u g ht h ek n nc l a s s i f i c a t i o nm e t h o db a s e do nc o n c e p t , t h i sp a p e rn o to n l yr e d u c e s t h ed i m e n s i o no fv e c t o rs p a c er e s u l t i n gi ni n c r e a s i n gc l a s s i f i c a t i o ne f f i c i e n c y , b u ta l s o i m p r o v e st h ep r e c i s i o na n dr e c a l lr a t i oo fw e b c l a s s i f i c a t i o n k e y w o r d s ：p a g ec l a s s i f i c a t i o n ；c a t e g o r yc o n c e p t ；c o n c e p tl a t t i c e ；f o r m a lc o n c e p t a n a l y s i s l - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ 。_ _ _ _ - 。- _ _ _ _ - 。一 基于形式概念分析的中文网页分类研究 目录 摘要i a b s t r a c t i i 1 绪论l 1 1 研究目的及意义1 1 2 研究背景及现状2 1 3 本文主要研究内容4 1 4 本文的结构_ 5 2 预各知识6 2 1 形式概念分析6 2 1 1形式概念分析基本知识6 2 1 2 + 概念格的构建方法一9 2 1 3 概念格的特点。1 1 2 2 文本表示模型11 2 3 传统分类方法1 4 2 4 本文分类思想及流程图1 5 2 5 本章小结17 3中文网页预处理1 8 3 1网页净化1 8 3 1 1 噪音清除o 1 8 3 1 2h t m l 加权1 9 3 2 特征项选取1 9 3 2 1传统特征项选取方法1 9 3 2 2 本文特征项选取方法2 l 3 3 本章小结2 1 4 概念的选取2 2 4 1 概念的选取方法2 2 4 2 概念选取案例2 3 4 3 本章小结2 3 5 概念格与k n n 算法的结合2 4 5 1 本文向量空间模型2 4 i v 西华大学硕士学位论文 5 2 本文的叮n 算法表述2 5 6 实验j 2 6 6 1实验准备_ 2 6 6 2 实验结果及评价2 8 6 2 1 评价指标2 8 6 2 2 实验结果：2 8 结论31 参考文献- j 3 3 攻读硕士学位期间发表的论文及科研成果3 7 致谢3 8 v 西华大学硕士学位论文 1绪论 1 1 研究目的及意义 随着社会的不断进步，网络技术飞速发展。随之产生的互联网信息逐渐增多，而且 种类多样。在我国已经有大部分人通过互联网进行交流，而且大部份信息来源于互联网。 网络逐渐成为人们生活的一个重要组成部分。人们通过互联网能够方便的共享信息和搜 集信息。但是，随着网络信息的共享程度不断增大，人们对互联网的依赖程度与日俱增， 另外，又由于互联网上的信息相对纷繁复杂，这使得用户对从互联网上获得信息的效率 和准确性的要求不断提高。由于互联网上的信息存在许多难以避免的问题，使得用户往 往搜索不到所需要的信息。虽然有的用户搜索到了相关的信息，但是相关信息太多，如 果想从这些较多的搜索结果中找出重要的网页信息，还是比较费时的。因此如何解决这 些问题，就成为网页分类领域的研究者们深入探索的方向。 针对w e b 网上信息纷杂多样的问题，研究者提出了搜索引擎的概念，搜索引擎的 出现极大地满足了用户渴求信息的心理。搜索引擎中有一个关键技术是分类技术，该技 术已经在数据挖掘和信息检索等领域中被广泛应用。同时，随着用户搜索要求的不断提 高，各种分类方法也不断被提出。但是有的分类方法的分类效果不佳，存在一些把应该 属于“军事”类的网页分到“法律”类中等问题。也有的分类方法在网页的特征提取过 程中存在一些缺陷，导致向量空间维数过大，从而影响分类效率。因此，为了提高中文 网页的分类效率，改善网页分类的准确率和召回率，提高用户获得信息的满意程度，本 文对中文网页分类进行深入研究。 中文网页分类作为一个研究方向，有重要的现实意义。当今社会人们面对如此庞大 的网络信息，必须找出如何有效组织和利用这些信息资源的方法。一种好的网页分类方 法，不仅可以有效地组织和检索网络资源，而且能够满足人们渴求知识的心理，更能使 科技发展适应社会飞速发展的步伐。另外，网页分类对于w e b 数据挖掘和搜索引擎都 是非常有意义的。许多搜索引擎大都基于关键词匹配，准确率不是很好。为了解决这一 问题，g o o g l e 搜索引擎采用了p a g e r a n k 等一些特殊方法，试图实现网页的高效搜索， 虽然这些方法在一定程度上改善了分类效果，为用户返回网页的准确率也有所提高，但 是由于中文网页较之英文网页的许多特性，使得返回的搜索结果还是不太尽如人意。对 于问题的出现，研究者们逐渐意识到如果将网页预先分类，然后在此基础上再把网页返 回给用户，不仅可以提高搜索引擎的搜索效率，还可以提高信息返回的准确率。 网页分类在w e b 挖掘领域也有着非常重要的地位。一般而言，w e b 挖掘只是按照 基于形式概念分析的中文网页分类研究 一定的条件针对某些特定的信息进行挖掘，而不是对所有的信息进行搜索。所以要想使 挖掘的w e b 信息既准确又全面，就必须对网页进行合理的分类，因此，对网页分类技 术的研究是一个必不可少的环节。 对网页分类技术的研究既是一种需要，又是一个必然。网页分类可以使因特网上繁 杂多样的信息归于统一，可以解除用户寻求某种信息时面临的困难，还可使网络得到长 足的发展。成熟的分类技术不仅能适用于网页分类，而且还应该适合其它信息检索、数 据挖掘等领域。 本文利用形式概念分析中概念格聚类的特点，将网页作为数据集先进行聚类，然后 完成分类。通过对本课题的研究，不仅能够使形式概念分析很好的应用于网页分类领域， 而且更重要的是能够改善中文网页的分类效率以及准确率和召回率。这种将形式概念分 析与k n n 算法相结合的网页分类方法，有利于提高用户获得信息的速度，最终得到自 己满意的搜索结果。 1 2 研究背景及现状 随着社会信息化速度的加快，网上信息的种类和数量也急剧膨胀，纷杂的网络信息 使用户眼花缭乱。同时人们利用搜索引擎获取信息的时候，经常得到一些与搜索主题不 太相关的信息。因此，为了解决这些问题，网页分类【l 捌就成了一种必然趋势。传统的网 页分类方法一般都是人工完成的，即通过人为分析网页的内容后，把该网页分配到相应 的类别中。这种人工分类网页的形式，既耗费大量的人力，又耗费大量的时间。同时， 不同的人在不同的时间分类，也会产生不同的分类情况。 随着社会节奏的不断加快，网络信息量迅速增加，人们从互联网上获取信息的需求 也越来越大。仅靠人工分方式来处理网页的分类情况显然越来越不实际。为了满足现在 社会用户对信息的需求，必须有种网页自动分类机制，另外也为分类方法的研究提供 了广阔的空间。网页自动分类机制既能节省人力，也能提高分类时间，使得用户能及时 得到信息。网页自动分类技术的出现对整个信息搜索领域产生了很大的影响。到目前为 止，尽管已经出现了许多文档分类方法【”】，但是，由于现在w e b 网上的信息非常繁杂， 而且存在许多相近的网页。所以，有的分类方法并不能达到较高的搜索效率以及较高的 查准率和查全率。针对中文网页分类存在的诸多问题，我们对中文网页的分类技术进行 研究就成为一种必然。 分类技术是指先通过在给定的文本集中构建文本分类器，然后利用该分类器对未知 类别的文本根据其具体特征将其自动归类到某一类别的过程。2 0 世纪8 0 年代末期，文 2 西华大学硕士学位论文 本分类领域出现了基于知识工程的分类方法，并占有主要地位。到了2 0 世纪9 0 年代， 出现了基于机器学习的文本分类方法，并具有重要地位。近年来，随着信息技术的高速 发展，文本分类变得越来越重要。在分类技术领域，已经提出了多种特征选取方法和文 本分类方法，如支撑向量机、回归模型、最大熵模型和k n n 等。一些著名的主题检测跟 踪会议和文本检索会议都把文本分类作为重要的讨论内容，它们一般通过提供比较规范 的语料库对文本分类系统的性能进行评测【6 】。 由于纯文本分类技术比网页分类技术的研究时间相对较早，所以其分类技术比较成 熟，因此在2 0 世纪8 0 年代互联网技术刚刚发展的时候，就有很多研究者试图将纯文本 分类方法直接应用到中文网页领域，使其达到理想的网页分类效果。然而这种做法虽然 在某些方面得到满足，但是总体分类效果不佳。又因为网页较之纯文本有许多自身的特 性。所以在进行网页分类的时候会遇到一些难以解决的问题，如：网页的结构、格式和 噪音等许多问题。这些问题如果处理不好，将会严重影响分类效果。 到目前为止，已经有许多文档或网页分类方法，既有基于理论统计的方法，也有基 于机器学习的方法。如支撑向量机法、类中心法、n a i v e - b a y e s 法、k n n 法等。虽然k n n 分类算法的分类时间比较短而且比较简单，但是该方法对分类样本的分布情况比较敏 感，所以如果待分类样本的分布不太均衡，将会导致网页分类的准确率下降。而支撑向 量机作为一种向量模式的分类方法，虽然在某种程度上被认为是一种比较理想的分类算 法，但是由于网页的结构化设计，又因为该算法只适用于对小规模数据集进行分类，所 ，以支撑向量机在对大规模的待分类网页数据集进行分类的时候，往往显得力不从心。文 献 7 通过分析s 算法和k n n 算法的不同，将两者的分类优势相结合，提出了一种将 两个方法相结合的网页分类算法，该算法以分界面为出发点，以待测样本为对象，将位 于分界面较远的待测样本直接代入支撑向量机进行分类，将位于分界面附近的待测样本 直接代入k n n 算法进行分类，此种思想的提出主要基于两个原因：其一，如果将位于分 界面较近的网页用支撑向量机进行分类，就会产生不好的分类效果。其二，如果将分界 面附近的网页直接代入k n n 分类算法进行分类，则k n n 分类算法在遍历分界面近处的网 页时，就不会经过训练样本的原始空间，而只经过s 组成的特征空间。所以将两种算 法相结合的方法既可以降低计算复杂度，还可以提高网页分类的准确率。现在已经有许 多研究者将网页中的链接信息作为网页分类的关键因素，并提出了相关的分类方法，这 种针对网页链接悼】进行研究的网页分类方法，其主要思想是：先假定网页a 到网页b 有 一个超链接成立，则网页a 的编辑者就认为这两个网页是相关的。然而，网页中的超链 接信息并不一定都是提供有用信息的关键，因为有的超链接会给网页分类提供很大的帮 助，也有的超链接对于网页分类是没有作用的。这些对网页分类无益的超链接一般是作 3 基于形式概念分析的中文网页分类研究 网页噪音而存在的，由于无用的噪音链接不能直接反应出网页之间存在的相关性，所 以，如果只用超链接作为网页分类的基础，就会影响网页的分类效果，因此必须综合考 虑网页的内容信息和链接信息。文献 9 主要侧重于用模糊推理方法来提高在自动检测 和分类领域的模式匹配的潜能。作者利用模糊推理机制，把人体的视觉系统考虑进去， 从而可以提高实际数据的分类效果。文献 1 0 针对k n n 分类算法的时间复杂度随着样本 大小成正比例增长的特点，提出了一种s k n n 算法，该方法是基于语义知识的，它将处 于语义中心的文本作为样本集的代表样本，从而减少了分类的样本数量，因此，可以降 低文本分类的时间复杂度。文献 1 1 在特征选取的基础上，利用对简短文字的统计规则， 将文本进行分类。这种分类方法在应用于文本分类的时候，可以提高分类的召回率。文 献 1 2 ，1 3 用一部分数据作为训练集，然后形成一个训练模型，用来预测待分类样本的 类别。文献 1 4 提出了一种基于遗传算法的k n n 分类方法，该方法通过粗粒度模型的并 行遗传算法，以种群内的遗传、变异和种群间的并行进化特征为基础，得到一个比较理 想的k 值，这使得k n n 分类算法的分类效果更佳。文献 1 5 设计了一个基于s v m 的中文 网页自动分类系统模型，并提出了一种分类方法，这种分类方法是利用预置关键词表进 行网页预分类的一种分类方法，该方法不仅使分类时间大大减少，而且也使得分类的准 确率和召回率显著提高。文献 1 6 中的作者提出了一个基于加权投票机制的s v m 网页分 类方法。该方法从l s a 和w p f s 方法中抽取特征向量，而且还使用四种不同的核心函数 比较了s v m 的性能。实验结果表明，该方法的达到了很好的分类效果。 1 3 本文主要研究内容 本文主要针对中文网页的分类进行研究。将形式概念分析的相关理论应用于网页分 类，目的之一是改善中文网页分类的效率，目的之二是改善中文网页分类方法的准确率 和召回率。 本课题主要研究内容包括以下两个部分： ( 1 ) 特征项选取方法【l 卜冽 一个网页一般由多个要素组成，其中关键的要素有h t m l 标签和特征词。特征选取 是网页分类过程中的一个重要步骤。在中文网页分类过程中，如何从网页中选取出更具 有代表性的特征词是本文的研究内容之一。本文特征选取方法的主要思想是：先对网页 中的h t m l 标签赋予相应权重，使每对标签之间的特征词具有和该标签相同的权重，然 后对该网页内不同h t m l 标签之间的相同特征词的权重求和，并将求和后的值除以该网 页中所有特征词的权重和，最后，将所得结果作为该网页中相应特征词的权重。 4 西华大学硕士学位论文 ( 2 ) 概念格中类别概念的选取及应用 概念格【2 0 2 1 】中类别概念的选取。 概念格是形式概念分析的重要组成部分，也是形式概念分析的核心数据结构【7 1 。概 念格中的每一个概念都由网页集( 对象集) 和关键词集( 属性集) 组成 2 2 2 3 ，因为每一 个概念中的网页具有相同的关键词，所以概念可以使多个相关的网页归为一类，因此概 念格有聚类特性，而这种聚类特性也可以间接的实现网页初次分类。针对概念格的聚类 特性，本文将研究如何从概念格中选取出用于分类的概念( 本文把从概念格中选取的用 于分类的概念称为类别概念) ，作为空间向量模型的向量表示。 概念格与k n n 分类算法的结合 本文将每一个类别概念都用一个向量表示，用所有的类别概念构成向量空间模型。 同时，将每一个待分类网页用向量表示。然后结合k n n 分类算法，实现中文网页的分类。 这种方法大大缩小了向量空间的维数，不仅可以有效的改善对网页分类的效率，而且可 以改善中文网页分类的准确率和召回率。 1 4 本文的结构 本文组织结构如下： 第一章：绪论。该部分介绍了本文的研究目的、背景、研究内容及其意义。 第二章：预备知识。该部分阐述了与研究中文网页分类相关的基础知识，相关知识 包括：形式概念分析，概念格的特点及其构建方法，几种传统文本表示模型，几种传统 的文本分类方法，本文的分类思想及分类流程图。本章介绍这些相关知识，目的在于方 便读者更好的理解本课题的研究内容。 第三章：中文网页预处理。该部分主要是针对中文网页进行的前期处理，包括：网 页净化和特征词选取。一种好的特征选取方法能够提高网页分类的准确率和召回率。 第四章：概念的选取。该部分介绍了概念格的各种特性，尤其是概念格的聚类特性。 并介绍了本文的概念选取方法，用该方法选取出有利于网页分类的类别概念。类别概念 的向量表示可以大大降低向量空间模型的维数。 第五章：概念格与k n n 分类算法的结合。该部分主要是将选取的类别概念用向量 表示，并用多个类别概念构建向量空间模型，然后将向量空间模型应用于k n n 分类算 法，这样可以比简单的k n n 分类算法产生更好的网页分类效果。 第六章：实验。该部分主要阐述整个实验的环境、数据及结果，并通过对实验结果 的分析，对本文分类方法进行客观评价。 基于形式概念分析的中文网页分类研究 2 预备知识 本章主要介绍一些与本文网页分类相关的基础知识。其中主要内容包括：形式概念 分析的基本理论知识，概念格的特点及构建方法，文本分类模型，文本分类方法，本文 的分类思想及分类流程图。 2 。1形式概念分析 2 1 1 形式概念分析基本知识 形式概念分析是基于数学的序理论，它是德国d a r m s t a d t 技术大学的数学教师在2 0 世纪7 0 年代末提出的【2 4 1 。而后由w h i l e 教授于1 9 8 2 年总结性的提出了形式概念分析 ( f o r m a lc o n c e p ta n a l y s i s ，f c a ) 理论【2 5 1 。他在概念格理论中，首次阐述了对象、属 性及其对象和属性之间关系的相互影响。其主要思想是：概念格中的每一个节点都是一 个概念，它有一个重要的聚类特性，即概念格的建格过程就是一个聚类【2 6 琊】的过程。目 前，形式概念分析已经应用于许多领域，并且有很多该领域的研究者对其进行深入探索。 文献【2 9 】主要是在一个模糊直觉形式背景中对形式概念分析进行研究，它将概念格理论中 的一些基本概念扩展到直觉模糊领域，并且提出了两个比较新颖的概念，一个是清晰的 直觉模糊概念，另一个是清晰的直觉模糊概念格概念。这两个概念的提出，主要基于在 形式概念分析中对概念格外延和内涵的定义。文献【3 0 】利用不同的知识将f c a 扩展到不同 的形式概念模型，从而创建了不同的理论思想，分别是有效的形式概念类型扩展的f c a 概念和对象的临近概念格。这些理论的提出都对形式概念分析有着不同的影响。 形式概念分析理论已经应用于很多领域，例如在软件工程、数字图书馆、数据挖掘 以及知识发现等。形式概念分析【3 l 】主要是以数学化的概念和概念层次为基础的数学领 域。它的主要思想是：首先从数据集的形式背景中得到形式概念以及概念之间的关系， 然后构建概念格。概念格中的每一个结点都表示一个概念，每一个概念都由对象集和属 性集组成。概念格中的任何一个概念都是从相关背景中抽取出来的一个子集，在同一子 集中的对象都具有相同的属性。针对属性和对象的分析，实际上就是针对形式背景的分 析。形式概念背景是相关背景的形式化表示，它主要体现了对象之间以及对象和属性之 间的关系。 概念格能够反映对象与属性之间的关系，概念格中的每一个结点都表示一个概念， 每个概念都由两部分组成，即内涵和外延。内涵表示对概念的描述，它刻画了实例的共 同特征，外延表示概念所代表的实例。概念格是形式概念分析的重要组成部分，它能够 6 清楚的表示出对象和属性的特点，还能够直观的显示出对象具有的属性以及属性所依赖 的对象。 根据定义1 ，本文将对象集g 表示网页集合，属性集m 表示网页中的关键词集合。 i 表示g 与m 之间的二元关系。本章用一个例子说明网页形式背景。如实例1 所示。 实例1 表2 1 刻画了网页的形式背景，g = 扣，b ，c ，d ，e ，厂) 是网页集，其中a 、b 、0 、 d 、e 、f 分别代表不同的网页。m = 1 ，2 ，3 ，4 ，5 ，6 ) 是关键词集，其中1 、2 、3 、4 、5 、6 分别代表不同的关键词。本章用“一和“x 表示网页与关键词之间的二元关系， 即如果一个网页中包含相应的关键词，那么此关系在二维表中就用“”表示；如果一 个网页中不包含相应的关键词，那么此关系在二维表中就用“”表示。 表2 1 网页形式背景 t a b 2 1t h ef o r m a lc o n t e x to f t h ep a g e t e r m 123456 p a g e 8 0 - b- j c-t- d e - f - t 7 基于形式概念分析的中文网页分类研究 如果给定一个形式背景f = ( g ，m ，) ，网页x g ，关键词集y m ，那么可定 义两个函数t 与上如公式2 1 所示。 躐p 誊p 鬻g 删yg 岩v t 譬y 麓端， 上： ( m ) _( ) ，= g ； ，( g ，t ) j ) 、7 定义2 【2 5 】一个形式背景f = ( g ，m ，i ) ，如果存在一个序偶( x ，y ) 尸( 回p ) ( x g ，y m ) ，使得x = y 且y = x ，那么序偶( x ，】，) 就是形式背景f c 的一个 形式概念，即概念。其中x 是概念的外延，y 是概念的内涵。 定义3 【2 5 1l ( g ，m ，i ) 是p ( g ) p ( t ) 的子集，它组成了形式背景的所有形式概念。 如果其中的两个形式概念( g l ，m 。) 、( g 2 ，m ：) ，满足g l g 2 ( 或m 。2m ：) 时，有 ( g l ，m 。) ( g ：，m ：) ，其中“ 构成了l ( g ，m ，i ) 的一种偏序关系。那么， ( g ，m ，) ，) 与最大元( l u b ) 和最小元( g l b ) 就构成了形式背景f = ( g ，m ，i ) 的一 个概念格。( l u b ) 与( g l b ) 的表示如公式2 2 所示。 ( 置，】；：) = ( ( u 墨) 仙，n 誓) ， 。 。 ( 2 2 ) 全( 置，z ) = ( n 置，( u z ) ) 实例2以表2 1 所示的形式背景为基础，构建一个概念格，并用h a s s e 图来表示 它，如图2 1 所示。 8 西华大学硕士学位论文 图2 1 根据表2 1 所示的形式背景构建的概念格的h a s s e 图 f i g 2 1c o n c e p tl a t t i c ec o r r e s p o n d i n gt ot a b l e2 1 由图2 1 能够看出，概念格中的每个结点都表示一个概念，每个概念都有外延和内涵 组成，每一个结点外都显示了相应结点的对象和属性。在概念格的h a s s e 图中，可以直 观的找到含有某一对象的结点，如果沿着该结点的上升路径寻找，可以看出，在上升路 径中的每个结点都含有相应的对象。同样的，该对象的属性也可以沿着结点的下降路径 寻找到。从图中还可以看出，从概念格的顶端开始向下的每个结点都包涵其上级结点的 所有属性，概念的属性沿着边向下逐渐增多，对象逐渐减少，但是对象变得更加具体。 2 1 2 概念格的构建方法 在一定的形式背景中，概念格的构建过程实际上是聚类对象的过程。在许多应用中， 一般都需要根据已有的形式概念背景构建出概念格，高效的概念格构建方法是实现应用 的关键。文献口4 】在一定知识的基础上，通过对概念格的渐进式构造过程的分析，提出了 一种针对概念格的组织思想，它采用概念格的树形结构的特点对其进行组织构建，该方 法采用先访问树根后遍历子树的顺序组织概念格。该方法在访问每个概念格结点的时 候，首先识别出每个结点的结构类型，然后对其执行相应的操作，以便达到加速渐进式 建格的作用，结果证明该方法可以达到一定的构建效果。对于概念格的构建，还有许多 其它的构建方法，文献p 5 】是从概念格中每个概念的内涵角度出发，通过对概念格中剩余 元素的内涵集合的分析，将这些内涵集合中的内涵元素的个数进行统计，并将其按照从 9 基于形式概念分析的中文网页分类研究 小到大的顺去进行排序，这样既可以减轻对概念格查找和判断的过程，还可以方便格的 组织构建，因此可以提高概念格构建算法的性能。但是该方法也存在一些不足之处，例 如在形式概念背景中，属性的增加可能会使原来不能区分的对象变得能够区分，而属性 的删除又可能会使概念中原来不属于同一类别的对象归为同一类别。 目前已经有多种构建概念格的方法【3 6 1 。总的来说，概念格的构建算法主要有串行构 建算法和并行构建算法。串行构建算法又可分为增量算法和批处理算法两种。 ( 1 ) 批处理算法 构建概念格的批处理算法一般适用于在静态的数据集中构建概念格。批处理算法对 于在固定背景中构造概念格是非常有效的。该算法的构建过程主要分为两个阶段：a 由 选定的数据集背景中产生概念格结点。b 建立概念格结点之间的父结点和子结点。对于 这两个阶段的完成存在不同的实现方法，一种方法是，在产生概念格的时候，生成数量 不多的概念，然后将这些概念连接到各结点的集合中。适用于这种方式的算法有b o r d a t 算法等。另一种方法是，在选定的数据集的形式背景中生成所有的概念，然后找出这 些概念之间的父子结点。适用于这种方式的算法有c h e i n 算法等。用批处理算法构造概 念格有多种方式： 自项向下算法 该算法是从上到下依次构建概念格，首先构建最上层的全概念结点( 即根结点) ， 然后构建下一级子结点，并以此循环操作，直到构建完成。如o s h a m 算法，b o r d a t 算法等【3 7 3 8 1 。 自底向上算法， 该算法与自顶向下算法不同，它的不同之处在于，下层结点的构建要时刻与其上一 层的序对进行判断合并，然后重复性向上构建概念格结点。如c h e i n 算法等1 3 9 。 枚举算法 该算法是先枚举概念格的所有结点，然后构建