（计算机软件与理论专业论文）基于形式概念分析的web搜索结果聚类方法的研究.pdf

西华大学硕士学位论文 基于形式概念分析的w e b 搜索结果聚类方法的研究 计算机软件与理论 研究生王竞指导教师杜亚军 摘要 w e b 搜索引擎是i n t e m e t 信息检索的主要工具，用户通过输入查询词来获取 w e b 搜索结果，在i n t e r n e t 资源中检索得到自己所需的信息。然而，i n t e m e t 上 与用户查询词相关的信息十分丰富，搜索引擎返回的搜索结果数量通常比较庞 大，用户要从数量庞大的w e b 搜索结果中获取自己需要的信息，常常显得很困 难。 改善搜索引擎检索质量的一种有效途径是应用聚类技术将w e b 搜索结果中 相似的w e b 文档聚集成为类簇集，即w e b 搜索结果聚类。对w e b 搜索结果进 行聚类，可以为用户提供易于浏览的w e b 搜索结果主题导航，帮助用户快速定 位符合自己查询需要的主题类别，从而提高用户使用搜索引擎的检索效率。 本文以形式概念分析理论为基础，应用概念格对w e b 搜索结果聚类方法进 行研究，提出了一种基于形式概念分析的w e b 搜索结果聚类方法c l u s t e r f c a 。 c l u s t e r f c a 聚类方法采用自顶向下逐层构建部分概念格的算法来构建w e b 搜索 结果聚类层次，而不是构建概念格的全部层次来实现w e b 搜索结果聚类。这样 不仅可以发挥形势概念分析用于聚类w e b 搜索结果的优势，还降低了形式概念 分析聚类w e b 搜索结果的时间耗费，避免了概念格层次过于复杂对聚类结果可 浏览性造成较大影响。 为了测试c l u s t e r f c a 方法的聚类效果，本文采用c + + 程序设计语言，将 c l u s t e r f c a 方法进行了实验。通过类标签的可读性、类内容的相关性、类内容 覆盖率和类重叠度等指标，来综合评价w e b 搜索结果聚类算法的质量。实验结 第1 页 西华大学硕+ 学位论文 果表明，应用c l u s t e r f c a 方法，截取概念格的第一层、第二层得到的w e b 搜索 结果聚类层次可以获得较好的聚类效果。 然而，对于不同用户提交的同一个查询词，应用一般的w e b 搜索结果聚类 技术，具有不同兴趣的用户得到的聚类结果是相同的，而用户的分类喜好根据 用户兴趣的不同通常具有个体差异。一般的w e b 搜索结果聚类方法仅仅针对 w e b 搜索结果网页内容进行分析处理，并未结合用户兴趣对w e b 搜索结果实现 个性化的聚类。 本文在c l u s t e r f c a 方法的基础上，结合w e b 搜索结果网页内容分析和用户 个人兴趣分析，提出了一种基于形式概念分析的个性化w e b 搜索结果聚类方法 p c f c a 。它动态地对w e b 搜索结果进行个性化聚类，为具有不同兴趣的用户提 供个性化的概念聚类层次。实验结果表明，应用p c f c a 方法，截取概念格的第 二层、第三层得到的w e b 搜索结果聚类层次可以获得良好的个性化聚类效果， 但在类内容覆盖率方面有所欠缺。 关键词：w e b 搜索引擎，w e b 搜索结果聚类，形式概念分析 第1 i 页 r e s e a r c ho fw e bs e a r c hr e s u l tc l u s t e r i n gb a s e do n f o r m a lc o n c e p t a n a l y s i s c o m p u t e rs o f t w a r e & t h e o r y m a s t e rd e g r e ec a n d i d a t e ：w a n gj i n g s u p e r v i s o r ：d uy a j u n a b s t r a c t t h ep r i m a r yt o o lo fs e a r c h i n gi n f o r m a t i o ni sw e bs e a r c he n g i n e au s e rc a n s e a r c ht h eu s e f u li n f o r m a t i o nf r o mi n t e r n e tb yi n p u t t i n gaq u e r ya n dg e t t i n gs o m e w e bs e a r c hr e s u l t s i nf a c t ，t h e r ei sal o to fi n f o r m a t i o nf r o mi n t e r n e tr e l e v a n t e dt o t h eq u e r ya n dt h et o t a ln u mo fs e a r c hr e s u l t si sv e r yl a r g e s o ，i ti sd i f f i c u l tf o ru s e r s t of i n dt h eu s e f u l i n f o r m a t i o ni nt h o s ew e bs e a r c hr e s u l t s a ne f f i c i e n ta p p r o a c ho fi m p r o v i n gr e t r i e v a lp e r f o r m a n c eo fw e bs e a r c he n g i n e i sw e bs e a r c hr e s u l tc l u s t e r i n gw h i c hg a t h e r st h es i m i l a rw e bd o c u m e n t si nt h ew e b s e a r c hr e s u l t st o g e t h e ra n df o r m sac l u s t e r w e bs e a r c hr e s u l tc l u s t e r i n gc a np r o v i d ea n a v i g a t i o no ft o p i c sf o ru s e r sa n dh e l pau s e rf i n dt h et o p i ct h a th en e e d e f f i c i e n c y f o rau s e rt ou s ew e bs e a r c he n g i n ec a l lb ei m p r o v e d b yt h i sw a y t h i st h e s i sp r o p o s e dan e wm e t h o do fw e bs e a r c hr e s u l tc l u s t e r i n gb a s e do n f o r m a lc o n c e p ta n a l y s i sn a m e dc l u s t e r f c a w ec o n s t r u c tap a r t i a lc o n c e p tl a t t i c e l a y e rb yl a y e rf r o mt o pt od o w nr a t h e rt h a naf u l lc o n c e p tl a t t i c et ob u i l dt h e c o n c e p t u a lc l u s t e rh i e r a r c h yo ft h ew e bs e a r c hr e s u l t s ，i no r d e rt or e d u c et h et i m eo f f o r m a lc o n c e p ta n a l y s i sc o m p u t i n ga n dm a k et h ec l u s t e rr e s u l ti s e a s yt ob eb r o w s e d b yu s e r s a na p p r o p r i a t ea l g o r i t h mo fh i e r a r c h i c a lc o n s t r u c t i o no fc o n c e p tl a t t i c ei s a p p l i e dt ob u i l dt h ec l u s t e rh i e r a r c h yi no u rm e t h o d 第1 i i 页 西华大学硕士学位论文 f o rt e s t i n gt h em e t h o di n t h i st h e s i s ，a l le x p e r i m e n tc o d e di nc + + w a s p e r f o r m e d w eu s et h er e a d a b i l i t yo fc l a s sl a b e l s ，t h er e l e v a n c eo fc l a s sc o n t e n t s ，t h e c o v e r a g eo fc l a s s c o n t e n t sa n dt h eo v e r l a po fc l a s st oe v a l u a t et h eq u a l i t yo f a l g o r i t h m t h ee x p e r i m e n t ss h o w e dt h a ti ti so fg o o dc l u s t e rq u a l i t yb yi n t e r c e p t i n g t h ef i r s ta n ds e c o n dl a y e r so fc o n c e p tl a t t i c ea p p l y i n gc l u s t e r f c am e t h o d m o s te x i s t i n gw e bs e a r c hr e s u l tc l u s t e r i n gt e c h n i q u e s ，g e n e r a l l ya n c h o r i n gi n p u r ec o n t e n t - b a s e da n a l y s i s ，g e n e r a t e as i n g l es e to fc l u s t e r sf o ra l li n d i v i d u a l s w i t h o u t t a i l o r i n g t o i n d i v i d u a l s p r e f e r e n c e sa n dt h u s a r eu n a b l et o s u p p o r t p e r s o n a l i z a t i o n t h i st h e s i si n c o r p o r a t e sat a r g e tb s e r sc a t e g o r i z a t i o np r e f e r e n c e si n t ot h ew e b s e a r c hr e s u l tc l u s t e r i n gp r o c e s su s i n gf o r m a lc o n c e p ta n a l y s i s b a s e do nt h em e t h o d o fc l u s t e r f c a ，p e r s o n a l i z e dc o n c e p t u a lc l u s t e r sh i e r a r c h yo fw e bs e a r c hr e s u l tw i l l b eb u i l tc o m b i n i n gc o n t e n ta n a l y s i sa n du s e ri n f o r m a t i o na n a l y s i s t h ee x p e r i m e n t s s h o w e dt h a ti ti so fg o o dp e r s o n a l i z e dc l u s t e rq u a l i t yb yi n t e r c e p t i n gt h es e c o n da n d t h i r dl a y e r so fc o n c e p tl a t t i c e b u t ，i th a sad e f a u l to ft h ec o v e r a g eo fc l a s sc o n t e n t s k e y w o r d s ：s e a r c he n g i n e ，w e bs e a r c hr e s u l tc l u s t e r i n g ，f o r m a lc o n c e p t a n a l y s i s 第页 西华人学硕士学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书丽使焉过的材料。与我一同工作的弱志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下赦得的，论文成 果归西华大学所有，特此声明。 年月 墨 文t 舒f 胃嘭日 第6 2 页 络 毳净毒少飞 凌 名 名 签 签 者 师 佑 导 西华大学硕士学位论文 第1 章绪论 随着i n t e m e t 上信息及用户数量的急剧增长，大多数i n t e m e t 用户使用各种 w 曲搜索引擎( 例如y a h o o t l l 、g o o g l e t 2 1 、百度【3 】) 从i n t e m e t 上检索信息，然 而w e b 搜索引擎的搜索结果质量却并不尽如人意。用户输入查询词，一般都会 得到成千上万的搜索结果，其中有很多都是用户不需要的无关信息。一种有效 的改善w e b 搜索引擎检索质量的途径是w e b 搜索结果聚类，即运用w e b 文档 聚类技术，将w e b 搜索引擎返回的w e b 搜索结果自动归类，并按类标签( 即类 名) 和类内容( 即类包含的文档) 的形式呈现给用户。 本章首先介绍了w e b 搜索结果聚类技术的研究背景；形式概念分析用于 w e b 搜索结果聚类的研究背景；接着概述了本文的研究内容和研究意义；最后 介绍了本文的组织结构。 1 1研究背景 作为i n t e m e t 上信息检索的主要工具，w e b 搜索引擎能够得到普遍应用的关 键在于：用户输入像“j a v a 程序设计”、“菊花栽培技术”这样含义明确的查询词 后，w e b 搜索引擎能够快速检索并返回给用户比较准确的搜索结果。然而，如 果用户输入的查询词含义宽泛，例如“文化”、“长江”等，这时搜索引擎返回的 搜索结果质量常常难以令用户满意。 其主要原因有以下几个方面： ( 1 ) 概括的、简短的查询关键词难以明确表示出用户的检索意图。 ( 2 ) 用户输入的查询关键词具有多义性，现有搜索引擎通常会返回包含多个 主题的搜索结果，而用户可能只对其中的某些主题感兴趣。 ( 3 ) i n t e m e t 上与用户查询相关的信息十分丰富，使得搜索引擎返回的搜索 结果数量庞大。 y a h o o 采用目录的方式把i n t e r n e t 上的w e b 文档进行分类，用户可以根据类 别导航来查找信息。但是w e b 文档更新很快，用人工编辑形成的分类目录不能 适应信息膨胀的i n t e m e t 。 第1 页 西华大学硕士学位论文 解决这些问题的另一种可能途径是使用聚类技术将w e b 搜索结果中相似的 文档聚集成为类簇集。h e a r s t 与p e d e r s e n 的研究已经证明了“聚类假设”( c l u s t e r h y p o t h e s i s t 4 】) ，即与用户查询相关的文档通常会聚得比较靠近，且远离与用户 查询不相关的文档。因此，对w e b 搜索结果进行聚类，可以为用户提供易于浏 览的可视化的搜索结果主题导航，帮助用户快速定位符合自己查询需要的主题 类别，从而改善搜索质量。 事实上，作为一种改善信息检索性能的有效途径，搜索结果聚类在信息检 索领域已经得到了深入的研究。早期的工作始于s c a t t e r g a t h e r 系统【4 】【5 1 。目前， 已经出现了一些应用w e b 搜索结果聚类技术的商业搜索引擎，例如v i v i s i m o 6 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 ) 理论【7j 。作为数据分析和知识处理的有力工具，f c a 目前己被广泛应用于知识 工程、数据挖掘、信息检索、软件工程等领域【8 】。概念格( c o n c e p tl a t t i c e ) 是 f c a 理论中的核心数据结构，构造概念格的过程实际上是概念聚类的过程。一 些研究者将f c a 应用到w e b 搜索结果聚类中【9 】【1 0 】【l l 】，其中比较有代表性的是 c r e d o 聚类系统【9 】【1 2 】。 1 2研究内容和意义 本课题主要对基于形式概念分析的w e b 搜索结果聚类方法进行研究。我们 将在已有的f c a 聚类w e b 搜索结果研究基础之上，重点研究如何改善f c a 聚 类w e b 搜索结果的可浏览性，如何降低f c a 构建w e b 搜索结果聚类层次的计 算开销，以及如何实现基于f c a 的w e b 搜索结果聚类的个性化。 本课题主要研究内容包括以下两个部分： ( 1 ) 截取概念格层次产生聚类结果的算法及其实现研究。 概念格上距离最大格节点越远的节点表示的概念越小，而实际上没有必要 对较小的类别中的文档作进一步聚类。此外，截取概念格层次而不是构建整个 概念格可以降低f c a 的计算开销，并且解决由于概念格节点规模过大造成聚类 结果不易于浏览的问题。本文借用已有的概念格构建方法，构建概念格中靠近 最大格节点的一些层次，舍弃概念格中距离最大格节点比较远的一些层次，从 第2 页 西华大学硕士学位论文 而提高应用f c a 聚类w e b 搜索结果的可浏览性和计算效率。 ( 2 ) 根据用户在线浏览内容实现基于f c a 的个性化w e b 搜索结果聚类方法 研究。 不同的用户具有不同的分类喜好，本文结合截取概念格层次产生聚类结果 的算法，研究如何应用f c a 来实现个性化w e b 搜索结果聚类。在搜索引擎返回 的w e b 搜索结果中，用户点击浏览的网页通常与用户兴趣相关程度较高，我们 将根据用户浏览的网页来获取用户兴趣。我们首先从w e b 搜索结果集中选择与 用户兴趣相关的w e b 文档作为聚类对象集，然后选择能够很好的描述与用户兴 趣相关的w e b 文档集的特征关键词作为属性集，在此基础上应用本文提出的截 取概念格层次的方法进行聚类，最后为用户提供个性化的w e b 搜索结果聚类层 次。 1 3本文的结构 本文剩下的章节将组织如下： 第二章：综述了w e b 搜索结果聚类的研究和应用，形式概念分析的基本知 识及应用，以及基于形式概念分析的w e b 搜索结果聚类的研究和应用。 第三章：提出了一种新的基于f c a 的w e b 搜索结果聚类方法c l u s t e r f c a 。 介绍了概念格的分层及逐层建格法，重点对聚类层次构建算法进行了阐述，并 通过实验对c l u s t e r f c a 方法的聚类效果进行了评价。 第四章：提出了一种基于f c a 的个性化w e b 搜索结果聚类方法p c f c a 。 重点介绍了与用户兴趣相关的w e b 文档的获取以及属性关键词的选择，并通过 实验对p c f c a 方法的聚类效果进行了评价。 第五章：对全文进行了总结，展望了下一步的研究工作。 第3 页 西华大学硕七学位论文 第2 章综述 作为预备知识，本章首先介绍了w e b 搜索结果的表现形式，聚类及文本聚 类；介绍了w e b 搜索结果聚类的特点、聚类搜索引擎和w e b 搜索结果聚类算 法研究；接着阐述了形式概念分析的基本知识、概念格的构建以及形式概念分 析的应用；最后介绍了基于形式概念分析的文档聚类研究和w e b 搜索结果聚类 算法研究。 2 1w e b 搜索结果表现 搜索结果反映了一个搜索引擎质量的好坏，也是用户获取自己所需信息的 入口，返回与查询词最相关的搜索结果一直是所有搜索引擎追求的目标。在搜 索结果一定的情况下，如何更好地组织和表现搜索结果，将直接影响用户查找 信息的效率。搜索结果的表现形式目前主要有评价列表、人工目录和聚类。 ( 1 ) 评价列表 评价列表( r a n k e dl i s t ) 是目前搜索引擎采用的比较常见的方式，它按w e b 文档与查询词的相关程度对w e b 搜索结果进行排序，把最相关的搜索结果显示 在前面。评价列表中的每个搜索结果通常为网页标题、摘要和u r l 构成的一个 文本片段( s n i p p e t ) 。用户通过浏览评价列表的w e b 搜索结果文本片段来判断对 应的网页是否为自己所需的信息，通过点击w e b 搜索结果文本片段可以打开对 应的网页查看详细的网页内容。这种方式存在着一些不足之处【1 3 】【1 4 1 ： ( a ) 用户常常需要浏览较长的w 曲搜索结果评价列表才能找到自己所需信 息： ( b ) w 曲搜索结果文档之间的相关性在评价列表中没有得到体现； ( c ) w e b 搜索结果没有进行合理的分类组织。 这些给用户快速找到自己所需的w e b 文档带来一定困难。 ( 2 ) 人工目录 人工目录( h u m a n m a d ew e bd i r e c t o r i e s ) 方式与图书馆书目编排方式类似， 第4 页 西华大学硕士学位论文 它是完全基于人工分类和编辑，将i n t e m e t 上的w 曲文档按类别存放和显示。 由于人工劳动的局限性，人工目录方式的搜索引擎往往只收录网站和很少的网 页。显然，它的更新速度较慢，而且收录的w e b 文档数量有限，但人工目录类 别中的w e b 文档与类别的相关性较好，用户检索信息的准确率比较高。目前比 较流行的采用了人工目录方式的搜索引擎有y a h o o 1 1 ，l o o k s m a r t 1 5 l 和o p e n d i r e c t o r yp r o j e c t 16 1 。 ( 3 ) w e b 搜索结果聚类 w e b 搜索结果聚类( w e bs e a r c hr e s u l tc l u s t e r i n g ) 是运用w e b 聚类技术， 将搜索引擎返回的搜索结果自动归类，并按类标签( 类名) 和类内容( 类中包 含的文档) 的形式呈现给用户。一般在页面左侧显示类标签，当用户点击其中 一个类标签时，右侧将显示此类标签对应的类内容。它与人工目录方式的本质 区别是：前者运用的是聚类技术，而后者运用的是分类技术，而且是人工分类。 2 2w e b 搜索结果聚类 2 2 1 文本聚类 2 2 1 1 聚类 聚类就是将数据集分成多个簇的过程，使得同一个簇的对象之间具有较高 的相似度、不同簇中的对象差别较大【1 7 】。聚类广泛地应用于模式识别、数据挖 掘、生物信息学等诸多领域，同时也在应用中不断地得到发展。聚类分析的方 法有很多，一般可分为基于层次的方法、基于划分的方法、基于密度的方法、 基于网格的方法和基于模型的方法。 ( 1 ) 基于层次的方法( h i e r a r c h yb a s e dm e t h o d ) 这类方法是对给定数据对象集合进行层次的分解，根据层次分解的形成， 可分为凝聚和分裂两类。例如算法b i r c h 18 1 ，c u r e 19 1 ，c h a m e l e o n 2 0 1 。 ( 2 ) 基于划分的方法( p a r t i t i o n i n gb a s e dm e t h o d ) 首先得到初始的k 个划分，然后采用迭代定位技术，试图通过将对象从一 第5 页 西华人学硕士学位论文 个类转移到另一个类来改进划分的质量。有代表性的划分方法包括k m e a n s 算 法 2 1 】和k 中心点算法【2 2 】。 ( 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 根据密度的概念对分类对象进行聚类，或者根据领域对象的密度或者根据 某种密度函数来生成聚类，d b s c a n t 2 3 1 就是一个有代表性的基于密度的方法。 ( 4 ) 基于网格的方法( g r i d b a s e dm e t h o d ) 是把对象空间量化为有限数目的单元，形成一个网格结构，所有的聚类操 作都在这个网格结构( 即量化的空间) 上进行，s t i n g 2 4 】是基于网格方法的一个典 型例子。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 为每个类假定一个模型寻找数据对给定模型的最佳拟合。神经网络方法【2 5 】 属于基于模型的方法。 目前，基于划分的方法及层次聚类方法应用较多。k m e a n s 方法是一种常用 的基于划分的聚类方法，它根据最终分类的个数k 随机地选取k 个初始的聚类 中心，不断地迭代来得到最终的聚类结果。 2 2 1 2 文本聚类 聚类起源于统计学，主要应用在数值数据上，随着计算机科学和数据挖掘 研究的发展，聚类对象逐渐扩展到文本、多媒体等其他数据上。显然，数据类 型不同，聚类算法也会有很大差异。传统方法是采用一些好的数值数据聚类算 法( 如k m e a n s 算法) 来处理文本类型数据。这些算法通常要求预先定义测量 两物体相似度，相似度也指两物体的“距离”，“距离”近的将被分到同一类中。 “距离 的测量方法比较多，其中基于向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 的夹角余弦法1 2 6 】被普遍采用。一般地，两文档的相似度采用夹角余弦法计算比 较简单。 近年也出现了区别于传统方法的一些新的发展方向，如后缀树聚类算法 ( s u f f i xt r e ec l u s t e r i n g ，s t c ) 1 3 】。后缀树聚类算法通过识别文档集中的共同短 语，并以此为基础建立类。相比传统算法把一个文档看成词的集合，后缀树聚 第6 页 两华大学硕士学位论文 类算法则把文档看成词的有序集：后缀树聚类算法的优点是利用短语不仅可以 发现类，还可以描述类。 2 2 2w e b 搜索结果聚类 2 2 2 1w e b 搜索结果聚类特点 一般的文本聚类方法并不能直接简单的应用到w e b 搜索结果聚类上，这是 因为它有其自身的特点和要求。z a m i ra n de t z i o n i ”1 已对此进行了较好的分析， 并提出w e b 搜索结果聚类应满足以下基本条件： ( 1 ) 聚类的相关性 算法产生的聚类应该使得同一类别的文档内容相似度尽可能大。 ( 2 ) 类标记可读性 算法应该能生成恰当和准确的类标签，以便于用户快速浏览。 ( 3 ) 类重叠 由于一些文档具有多个主题，算法应避免把它们只分到单个类中。 ( 4 ) 速度 算法应该足够快速以便于在线计算，在将查询结果显示给用户前不能有太 大的时间迟延。 2 2 2 2 聚类搜索引擎 目前，已经出现了一些应用w e b 搜索结果聚类技术的商业搜索引擎。其中 有代表性的是v i v i s i m o 6 1 、s r c 2 7 1 、b b m a o t 2 引、g r o k k e r 2 9 1 、a s k 3 们、i b o o g i e 3 1 1 、 k a r t o o 3 2 1 、w i s e n u t 3 3 】等。 v i v i s i m o 采用一种叫做准确描述所有配对( c o n c i s ea l lp a i r sp r o f i l i n g ， c a p p ) 的方法【3 4 1 。它的基本原理是将所有类别成对的进行比较，找出能够将每 一对类别区分开来的特征，然后对那些特征进行组织，形成最后的描述，保证 第7 页 西华人学硕十学位论文 每一对至少有一个特征能够将它和其它对区别出来。 微软的s r c 聚类搜索引擎采用了一种有监督的机器学习方法【3 5 1 。该方法基 于从人工分类的训练数据集进行学习的回归模型来确定显著短语( s a l i e n t p h r a s e s ) ，并把它们作为候选类名；然后将w e b 搜索结果分配给相关联的显著 短语来形成候选类，最后合并类内容重叠程度较高的候选类得到最终聚类结果。 b b m a o 是中国首家商业聚类搜索引擎。成立于2 0 0 5 年的b b m a o 公司在2 0 0 6 年2 月发布了b b m a o ，它主要针对中文w e b 搜索结果进行聚类。 2 2 2 3w e b 搜索结果聚类算法的研究 事实上，作为一种改善信息检索性能的有效途径，w e b 搜索结果聚类在信 息检索领域已经得到了深入的研究。 早期的工作始于s c a t t e r g a t h e r 系统5 1 。它基于b u c k s h o t 和f r a c t i o n a t i o n 两种聚类算法，结合一个传统的检索系统，为用户提供了一个简单的检索结果 分组图形接口。 g r o u p e r 【1 3 是第一个聚类搜索引擎，它通过h u s k y s e a r c h 元搜索引擎获取搜 索结果，采用后缀树聚类的短语分析算法进行聚类。 w e b c a t 3 6 1 【3 7 1 基于k - m e a n s 聚类算法，虽然该方法聚类速度较快，但产生的 类标签可读性较弱，聚类质量不高，并且它自身不能够确定一个最佳聚类数目， 而需要由用户给定。 s h o c 3 8 】和l i n g o c a r r o ts e a r c h t 3 9 儿加】都采用了奇异值分解方法( s i n g u l a r v a l u ed e c o m p o s i t i o n ，s v d ) 来对后缀树聚类算法进行扩展以改善聚类质量。 s n a k e t 4 1 】【4 2 】使用“g a p p e ds e n t e n c e s ( 不一定连续出现在原始s n i p p e t s 中 的关键词组成的句子) 来从搜索结果中抽取可变长度句子作为类标签。 n o o d l e 搜索引擎 4 3 】【4 4 】采用了一种动态s v d 聚类( d y n a m i cs v dc l u s t e r i n g ， d s c ) 技术，应用潜在语义索引( l a t e n ts e m a n t i ci n d e x ，l s i ) 对搜索结果w e b 文档的全部内容进行聚类。 第8 页 西华大学硕士学位论文 2 2 2 4m y c l u s t e r 李战胜等人提出了一个基于短语和潜在语义索引的w e b 搜索结果聚类算法 m y c l u s t e r f 4 5 1 。该方法针对后缀树聚类算法处理中文信息的不足，提出了关键短 语和非关键短语的新概念，并利用它们来构造特征矩阵，然后采用奇异值分解 的方法来发现类内容和归纳类标签，最后采用合并和排序策略对形成的类标签 和类内容进行加工。 m y c l u s t e r 产生的类标签是经过潜在语义索引算法提炼后形成的。它们来自 关键短语和非关键短语，是句子间的共现短语，具有一定的代表性。 文中还提出了w e b 搜索结果聚类的用户评价体系，用来综合评价一个w e b 搜索结果算法质量的好坏。该体系包含了类标签的可读性、类内容的相关性、 类内容覆盖率和类重叠度等指标。 实验结果表明m y c l u s t e r 算法具有以下优点： ( 1 ) 类标签可读性强； ( 2 ) 类内容与类标签的相关性较大。 但m y c l u s t e r 算法也存在着一些不足： ( 1 ) 有时类标签数目过多： ( 2 ) 计算代价过大； ( 3 ) 未被归类的w e b 文档数量比例过大； ( 4 ) 在聚类过程中没有考虑用户兴趣。 现有的w e b 搜索结果聚类技术通常首先对搜索引擎返回的短小的s n i p p e t s 进行分析处理。一个“s n i p p e t ”即是对网页内容进行摘录而形成的一个文本片段， 通常包含标题、网页摘要以及u r l 。仅分析搜索结果s n i p p e t s 而不是分析w 曲文 档全部内容的原因剧4 3 】：通常每一个s n i p p e t 包含的单词数不超过4 0 个，从而 能对它进行快速分析，使得聚类处理步骤不至于对搜索结果返回给用户的响应 时间产生过大影响。当然，为了获得好的聚类质量，s n i p p e t s 要能够较好的表示 第9 页 西华人学硕士学位论文 网页的内容。 目前大部分w e b 搜索结果聚类技术有以下共同点： ( 1 ) 集成一个或多个搜索引擎，即用户提交查询后，系统从一个或多个搜索 引擎上获取搜索结果。 ( 2 ) 仅选取搜索引擎返回的排序列表的前n 个搜索结果。 ( 3 ) 对前n 个搜索结果的s n i p p e t s 进行聚类，而不是网页全部内容。 2 3形式概念分析 2 3 1形式概念分析基本知识 现实世界是由各种各样的对象组成，每个对象都有自己的一组属性或特征。 概念格结构是反映对象与属性之间联系以及概念泛化与特化关系的一种完备的 概念层次结构。概念格是形式概念分析的核心，它将哲学的概念进行数学化描 述，实现了一种概念的形式化描述方法。概念格的构建过程实际上是概念聚类 的过程。对于同一个形式背景所生成的概念格是唯一的，这也是概念格的优点 之一。以下简要介绍了形式概念分析的基本知谢7 】【4 6 】【4 7 】。 定义2 1 一个形式背景( f o r m a lc o n t e x t ) 是一个三元组f c = ( gt ，i ) ，其中 g 、t 是非空有限集合，i c _ g x t 是g 和t 之间的二元关系。g 为对象集合，t 为属性集合。若( g ，t ) g x t ，即( g ，t ) i ，则称对象g 具有属性t 。 一个形式背景实际上与数据库中的一张二维表类似，对象相当于表的记录， 而属性则相当于表的字段，对象与属性之间的关系相当于表中记录与字段的关 系。 在本文的讨论中，g 表示网页的集合，t 表示关键词的集合。i c g x t 表示 网页与关键词之间的一种二元关系。 例2 1g = l ，2 ，3 ，4 ，5 ，6 是网页的集合，t = a ，b ，c ，d ，e ，f ) 是关键词的集 合，其中a 、b 、c 、d 、e 和f 是关键词。若网页与关键词之间的二元关系i c g x t 是一种二值关系，即一个网页要么包含某个关键词( 用“1 ”表示) ，要么不包 含它( 用“o ”表示) ，则可以得到如表2 1 所示的形式背景。 第1 0 页 两华大学硕+ 学位论文 表2 1 一个形式背景 t a b l e2 1af o r m a lc o n t e x t t e n i l abcde f p a g e 1111l10 211o10l 3111101 4 1 l0 0 1 l 5ll1l00 61l0001 给定一个形式背景f c ：( gt i ) ，若网页集合x g ，关键词集合y t ，则 可定义如下两个函数t 与上： j ：p ( ( t g ) ) j - - - p ( ( g t ) ) ，, x 上 ：= te t ；v g ex ，( , ( g g ，, 。t ) ) e ，i ppy g g ；vt y ) ( 2 1 ) 上： ( t ) j( g ) ，上= ，( g ，t ) ， 、 7 定义2 2 给定一个形式背景f c = ( gt ，d ，若一个对象属性序偶( x ，y ) p ( g ) xp ( t ) 使得x t = y 且y l = x ，则序偶( x ，y ) 是形式背景f c 的一个形式概念 ( f o r m a lc o n c e p t ) ，简称概念。其中x 称为形式概念的外延，y 称为形式概念 的内涵。 例2 2 表2 1 所示的形式背景中， l ，3 ，5 ) = a ，b ，c ，d ) ， a ，b ，c ，d o = l ， 3 ，5 ) ，由定义2 2 可知( 1 ，3 ，5 ) ， a ，b ，c ，d ) ) 是一个形式概念。 为了讨论方便，本文对概念进行缩写，如( 1 ，3 ，5 ) ， a ，b ，c ，d ) 缩写为( 1 3 5 ， a b c d ) 。其中1 3 5 是概念的外延，a b c d 是概念的内涵。 p ( g ) p ( t ) 的子集l ( gt ，i ) 形成了形式背景的所有形式概念。若( o l ，p 1 ) 、( 0 2 ， p 2 ) 是其中两个形式概念，当且仅当0 1 0 2 ( 或p 1 p 2 ) 时有( 0 l ，p 1 ) ( 0 2 ，p 2 ) 。“” 第1 1 页 西华大学硕士学位论文 构成了l ( gt ，i ) 的一种偏序关系，( l ( gt i ) ，) 与最大元( l u b ) 和最小元 ( g l b ) 构成了形式背景f c = ( gt ，d 的一个概念格。l u b 与g l b 分别为： 星( 置，鬈) = ( ( 0 _ ) 仙，n i ) ， 台n ( 置，r ) = ( _ ，( 0 r 广) 2 2 例2 3 由表2 1 所示的形式背景可构建概念格，通常可以由h a s s e 图来表 示，如图2 1 所示： ( 1 2 3 5 ，a ( 1 3 5 ，a b c d ) ( 3 ，a b c d f ) ( 1 2 3 4 5 6 ，a b ) ( 2 3 4 6 ，a b f ) ( 4 ，a b e f ) 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 根据表2 1 所示的形式背景构建的概念格的h a s s e 图 西华大学硕士学位论文 2 3 2 概念格的构建 构建概念格的过程实际上是概念聚类的过程。目前提出的构建概念格的算 法主要分为两类：批处理算法和增量算法。增量算法适合于对概念格的更新和 维护，而批处理算法是在初始构建概念格的过程中更有效的方法。 2 3 2 1 批处理算法 批处理算法是在有较多和较完整的数据信息的情况下，进行一次建格的方 法。根据构造概念格的不同方式，批处理算法可分为三类：自顶向下算法、自 底向上算法、枚举算法。 自顶向下算法首先构造格的最上层节点，再逐渐往下。如b o r d a t 算法【4 引， o s h a m 算法【4 9 1 。 自底向上算法则相反，首先构造底部的节点，再向上扩展。如c h e i n 算澍如】。 枚举算法则是按照一定顺序枚举格的所有节点，然后再生成h a s s e 图，即 各节点之间的关系。此类算法如g a n t e r 的算法【5 0 1 ，n o u r i n e 算法【5 u 等。 2 3 2 ，2 增量算法 增量算法针对已建成的概念格，当有少量对象( 属性) 增加或减少时，可 以在已有的概念格上进行更新得到新的概念格，不必重新再次建格。增量算法 的基本思想是将当前要插入的对象和格中所有的概念进行交的操作，根据交的 结果采取不同的行动。典型的增量算法有g o d i n t 5 0 1 ，c a p i n e t o t 5 2 1 。 2 4基于形式概念分析的w e b 搜索结果聚类 2 4 1 基于f c a 的文本聚类 意大利的c a r p i n e t o 建立的g a l o i s v 统t 5 3 】将形式概念分析理论应用到文 第1 3 页 西华大学硕士学位论文 档聚类中。g a l o i s 系统应用了有效的增量概念格构建方法在文档集上构建概 念格。研究表明形式概念分析应用到文档聚类上具有较好的聚类特性，但随着 文档数量的增加，f c a 计算开销和概念格的规模都迅速增长。 文献【5 4 】应用f c a 良好的聚类特性，同时结合k m e a n s 聚类算法速度快的 优点来对文档进行聚类。该文首先应用k m e a n s 的改进方法对文档进行第一次 聚类，然后将得到的类别描述作为形式背景的属性集，类内容作为形式背景的 对象集，在此基础上应用f c a 进行第二次聚类。k m e a n s 聚类算法固有的缺点 对最终聚类结果的质量有一定影响。 文献【5 5 】也结合了f c a 与k m e a n s 聚类算法来进行文档聚类。其主要区别是 通过用类概念合并和类概念分离操作来修正聚类参数k 值的不准确对聚类的影 响。该方法首先由用户给出聚类参数k 的近似值，然后利用k - m e a n s 算法对文 档进行聚类，取对应的聚类中心并对聚类中心建立概念格；接着采用类概念合 并和类概念分离操作来修正聚类中心。 文献【5 6 】根据概念格的定义来从文档集中提取形式概念，生成概念格，得到 聚类结果。该文重点针对形式背景出现高维属性关键词( h i g hd i m