多Agent主题爬虫协作策略的研究与分析

在多个Web主题爬虫并行爬行中,如何避免重复访问网页并高效地获取与主题相关网页,成为搜索引擎主题爬行的热点研究内容之一。为完成系统爬行任务充分发挥每个爬虫自身能力,文章立足于每个爬虫相对独立爬行、共同协作、彼此竞争的思想,将爬虫的历史爬行网页作为背景知识,分析这些网页文本内容,提取网页中"概念"和概念间的语义关系,探讨不同爬虫背景知识之间的语义相似性,提出基于分层概念背景图的爬虫之间理解方法、协作和竞争策略。该策略包括4个方面的内容:主题爬虫背景知识的分层概念背景图的表示模型、基于分层概念背景图的爬虫语义理解方法、在语义理解模型下同组多个网络爬虫之间协作与竞争机制及实现、在语义理解模型下异组多个爬虫之间协作与竞争机制及实现。

概念格理论中的G-D基蕴涵约简研究

概念格理论中的G-D基是一个形式背景的最小蕴涵基,从G-D基中可以产生一个背景的所有蕴涵,对G-D基的研究对于数据挖掘和规则提取都有很重要的意义。当G-D基中的蕴涵很多时,从它推导出背景中的全部蕴涵就很困难,减小G-D基的尺寸能够节省很多时间。提出了利用概念层次图约简G-D基的尺寸,通过利用Armstrong公理系统比较说明了G-D基的尺寸变小后推导蕴涵的效率明显提高,并提出了恢复G-D基中的蕴涵的一种并行算法,该算法基于可约属性类对G-D基中的蕴涵进行恢复。

利用二部图生成概念格

概念格作为一种有效的知识发现与数据处理的工具,在许多领域得到了广泛应用,概念格的构造在其应用中具有重要的意义。每个概念格的形式背景都可以对应一个二部图,本文通过二部图的极大完全子图的概念来生成概念格,给出了基于二部图的深度优先的概念格的迭代算法。首先,对形式背景进行必要的约简;其次,利用二部图的极大完全子图得到顶层概念的直接子概念;最后,通过求二部图的导出子图来简化形式背景,并得出每个概念的直接子概念和所有子概念,从而生成概念格。

一种基于树图的属性约简算法

针对基于概念格对数据的规则挖掘中,概念格结构的复杂度随着形式背景的复杂化呈指数递增的问题,本文从树图的角度研究决策形式背景的属性约简问题,以树型结构为基础,首先提出了新的强弱背景的判定方法;进一步定义了条件树对象集与决策外延的相关函数,并以此作为启发信息,设计了基于树图的逐层属性约简算法,避免了计算区分矩阵这个既消耗时间又消耗空间的过程;最后在属性约简树的基础上,给出了约简后的概念树生成算法,以简洁、直观的概念树的代替错综复杂的概念格.理论分析和实验结果表明,该算法是有效可行的.

利用二元拟阵K_n图的一种建格方法

由于交通网络纷繁复杂,难以直观分析和直接处理。若出行者根据自己喜好和习惯决定出行策略,则需对出行方案有清楚的了解。针对此问题,建立交通网络图——K_n模型,对具有带环路和重边路的复杂网络结构图,可以完全转化为K_n图处理。通过概念格理论,得到Hasse示图,方便人们对某些属性条件方案的提取,便于后续工作处理。对K_n图进行研究之后发现,在特定的多个属性影响下,会形成一个三角形圈,于是结合拟阵中二元拟阵的标准矩阵的定义,挖掘出一种特殊形式背景。根据这种形式背景的特殊性,给出基于二元拟阵的K_n图的概念格算法。结合生活中的例子,验证该算法可行性。由于模型具有这种普遍性,所有结果可推广到具有类似形式背景的其他领域研究中。

基于概念背景图的主题爬虫设计与实现

为充分利用爬行主题与待访问页面之间的语义关系,提高主题爬虫的整体性能,在研究概念背景图(CCG)主题爬行算法的基础上,提出改进的CCG主题爬行算法。利用HITS算法选取高质量的主题背景知识,根据形式概念分析理论构建概念格模型,将概念格生成CCG用以存储用户查询意向;利用CCG综合父网页、锚文本、链接上下文以及URL自身预测链接主题相关度,过滤不相关页面。实验结果表明,改进的爬行算法有效提高了网页抓取的精度和召回率,具有较强的可行性。

弦二部图的概念格表示

本文首先讨论了二部图中双单纯边与概念格中概念之间的对应关系;其次研究了弦二部图和约简的形式背景的若干性质;最后将概念格中元素的消除理论应用于二部图的研究,给出了弦二部图的概念格刻画.结果表明,一个二部图是弦二部图当且仅当对应的概念格中有一个∨∧—不可约元的完美消除序列.

基于语义概念背景图的主题爬虫的研究与实现

为了提高主题爬虫的性能,在概念背景图(CCG)的基础上加以改进提出了语义概念背景图(SCCG)。从谷歌返回相关主题的网页链接列表中精选出一定数量的网页,根据形式概念分析的知识构建主题形式背景和概念格并最终生成SCCG。通过SCCG指导主题爬虫,将访问页面处理为虚拟形式概念(Virtual Formal Concept,VFC)来计算其与核心概念的概念相关度进行主题相关度预测。通过实验表明,SCCG指导主题爬虫有效提高了网页的F-Measure值,具有较高的可行性。