主题网络爬虫研究综述


收 稿日期 : 2006-08-16; 修 返日期 : 2006-12-06 作 者简介 : 刘金红 ( 1978- ) , 山西 永济人 , 博 士研 究生, 主要 研究 方向为 Web 挖掘 和网络 安全 ( happygold@ sina. com) ; 陆余 良( 1964- ) , 江苏 宜兴 人, 教授, 主要研究方向为数据挖掘和网络安全. 主 题 网 络 爬 虫 研 究 综 述 刘金红, 陆余良 ( 解放军电子工程学院 网络系 , 合肥 230037) 摘 要: 首先给出了主题网络爬虫的定义和研究目标; 然后系统分析了近年来国内外主题爬虫的研究方法和技 术, 包括基于文字内容的方法、基于超链分析的方法、基于分类器预测的方法以及其他主题爬行方法, 并 比 较 了 各种 方法 优缺 点; 最后对未来的研究方向进行了展望。 关键 词: 主 题网 络爬 虫; 信息 检索 ; Web 挖 掘 中图 分类 号: TP391 文 献标 志码: A 文 章编 号: 1001-3695( 2007) 10-0026-04 Survey on topic-focused Web crawler LIU Jin-hong, LU Yu-liang ( Dept. of Network, PLA Electric Engineer Institute, Hefei 230037, China) Abstract: This paper gave the goal of focused crawling, then comprehensively analyzed the recent advances of the relevant re- searches and applications about focused-crawler, included focused crawling methods based on text contents, link analyses’ methods, classifier-guided methods and other focused methods. Finally pointed out the future direction of focused crawling. Key words: topic-focused crawler; information retrieval; Web mining 0 引言 随着网络上海量信息的爆炸式增长, 通用搜索引擎面临着 索引规模、更新速度和个性化需求等多方面的挑战[ 1, 2] 。面 对 这些挑战, 适应特定主题和个性化搜索的主题网络爬虫 ( fo- cused crawler or topical crawler) 应运 而 生[ 3, 4] 。基 于主 题 网 络 爬虫的搜索引擎( 即第四代搜索 引擎) 已经成为当 前搜索引 擎 和 Web 信息挖掘中的一个研究热点和难点。 通用网络爬虫的目标就是尽可能多地采集信息页面, 而在 这一过程中它并不太在意页面采集的顺序和被采集页面的相 关主题。这需要消耗非常多的系统资源和网络带宽, 并且对这 些资源的消耗并没有换来采集页面的较高利用率。主题网络 爬虫则是指尽可能快地爬行、采集尽可能多的与预先定义好的 主题相关的网页。主题网络爬虫可以通过对整个 Web 按 主题 分块采 集, 并将不同块的采集结果整合到一起, 以提 高 整 个 Web 的采集覆盖率和页面利用率。 1 主题爬虫的定义和研究目标 定义 1 网络爬虫是一个自动提取网页的程序, 它为搜 索 引擎从 Web 上下载 网页, 是搜索引擎的重要组成部分。通用 网络爬虫从一个或若干初始网页的 URL 开始, 获 得初 始网 页 上的 URL 列表; 在抓取网页的过程中, 不断从 当前页面上 抽取 新的 URL 放入待爬行队列, 直到满足系统的停止条件。 定义 2 主题网络爬虫就是根据一定的网页分析算法过 滤与主题无关的链接, 保留主题相关的链接并将其放入待抓取 的 URL 队列中; 然后根据一定的搜索策略从队列中选择下一 步要抓取的网页 URL, 并重复上 述过程, 直到 达到系 统的某 一 条件时停止。所有被网络爬虫抓取的网页将会被系统存储, 进 行一定的 分析、过滤, 并建立索引, 对于主 题网络爬虫 来说, 这 一过程所得到的分析结果还可能对后续的抓取过程进行反馈 和指导。 定义 3 如果网页 p 中包含超链接 l, 则 p 称为链接 l 的 父 网页。 定义 4 如果超链接 l 指 向网 页 t, 则 网页 t 称 为子 网页, 又称为目标网页。 主题网络爬虫的基本思路就是按照事先给出的主题, 分析 超链接和已经下载的网页内容, 预 测下 一个 待抓 取的 URL 以 及当前网页的主题相关度, 保证尽可能多地爬行、下载与主题 相关的网页, 尽可能少地下载无关网页。相对于通用网络爬 虫, 主题网络爬虫需要解决以下四个主要问题: a) 如何描述或定义感兴趣的主题( 即抓取目标)? b) 怎样决定待爬行 URL 的访问次序? 许多主题网络爬 虫 根据己下载网页的相关度, 按照一定原则将相关度进行衰减, 分配给该网页中的子网页, 而后将其插入到优先级队列中。此 时的爬行次序就不是简单地以深度优先或广度优先顺序, 而是 按照相关度大小 排 序, 优先 访 问相 关度 大 的 URL。 不同 主 题 网络爬虫之间的区别之一就是如何计算 URL 的爬行次序。 c) 如何判断一个网页是否与主题相关? 对于待 爬行或 己 下载的网页可以获取它的文本内容, 所以可以采用文本挖掘技 术来实现。因此不同主题网络爬虫间的区别之二就是如何计 算当前爬行网页的主题相关度。 第 24 卷 第 10 期 2007 年 10 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 24 No. 10 Oct. 2007 d) 怎样提高主题网络爬虫的覆盖度? 如 何穿过 质量不 好 ( 与主题不相关) 的网页得到与用户感兴趣主题相关的网页, 从而提高主题资源的覆盖度? 对于主题网络爬虫性能的评价, 目 前 主 要是 基 于 harvest rate 来评价。Harvest rate 就是主题相关网页数目占所有抽取 网页总数的比率: harvest rate = numbers of relevant pages/ numbers of all retrival pages ( 1) 2 主题网络爬虫研究进展 为了高效地抓取与主题相关的网络资源, 研究者提出了许 多主题定制爬行策略和相关算法, 使得网络爬虫尽可能多地爬 行主题相关的网页, 尽可能少地爬行无关网页, 并且 确保网 页 的质量。通过对这些方法进行比较分析, 本文将它们分为如下 四类。 2. 1 基于文字内容的启发式方法 基于文字内容的启发策略主要是利 用了 Web 网页文 本内 容、URL 字符串、锚文字等文字内容信息。不同的分析方法构 成了不同的启发式策略和相应的算法。主要包括: a) Best first search 方法。基本思想是给定一个待爬行 URL 队列, 从中挑选最好的 URL 优先爬行。爬行主题采用关 键词集合来描述, 待爬行 URL 的优先级是根据主题词和已爬 行网页 p 的文字内容来计算, 用它们的相关度来估 计 p 所 指向 网页的相关 度。相关 度 大的 网页, 它所指向的网页优先级就 高, 从而决定了待爬 行队 列中 URL 的优先级顺序。如果待爬 行队列的缓冲区满了, 则 将优 先级 最低 的 URL 从 该队 列中 移 去。它采用式( 2) 来计算网页与主题间的相关度。 sim( q, p) = ( k∈q∩P fkq fkp) /( k∈P fkp 2 k∈q fkq 2 ) ( 2) 其中: q 表示 主题; p 表 示抓取 的网页; fkq 表示词 k 在 q 中出 现 的频次; fkp表示词 k 在 p 中出现的频次。 该算法有 url_queue 和 crawled_queue 两个 堆栈, 分别用 来 存储待爬行的 URL 和己爬行的 URL。在主题网络爬虫研 究领 域, 该算法具有一定的竞 争力, 所以很多研究者将其作为算法 性能的比较基 准[ 6] 。J. Cho 等 人[ 7] 将待 爬 行队 列分 成 两个, 即 hot_queue 和 url_queue。如果认为 是相关的, 就将 其压入 队 列 hot_queue; 否则就 压入 url_ queue 中。在 爬行 时, 优先 爬 行 hot_queue 队 列, 只 有 当 hot_ queue 队 列 为 空 时, 才 爬 行 url_ queue。在判断是否相关时, 不是采用式( 1) , 而是作如下判断: 如果在 URL 字符串或其 对应 的锚文 字中 含有 主题 词, 就认 为 是 hot_queue, 将其压入 hot_queue; 否则 就是普 通的 URL, 将 其 压入 url_queue。这种方式的优点是计算量小, 对于 单个 关 键 词的主题( 宽泛 主题), 它的效果还是不错的。但当关键词个 数较多时, 效果就不 是很 好。因为 URL 的文 字和 锚文 字并 不 能很好地反映出多个关键词蕴涵的真实主题。 b) Fish search 方 法。1994 年由学 者 De Bra 等 人[ 8] 提出。 它将在网络上遍历的网络爬虫比喻成海里的一群鱼。当它们 发现食物( 相关 信息) 时, 这 些鱼 就继 续繁 殖, 寻 找新 的 食物; 当没有食物时( 没有相关 信息) 或 水被污 染( 带宽 不够 ) 时, 它 们就死掉。该算法的关键是根据代表用户感兴趣主题的种子 站点和主题关键词, 动态地维护待爬行的 URL 优先级队列。 当一个网页抓取过来后, 抽取它所有的 URL, 这些 URL 所 对应的网页, 称为其孩子网页。如果抓取的网页相关, 孩子 网 页的深度( depth) 设成 一个预 先定义 的值; 否 则孩 子网 页的 深 度设置成一个小于父亲网页深度的值。当这个深度为零时, 该 方向的搜索就停止。 Fish search 算法的入口参数包含种子站点、查询式 ( 主 题)、查询 宽度 width、深度 depth。深 度 大于 0 的 孩 子 网 页 的 URL 按照如下启发策略插入到 url_queue 中: a) 相关网页 的前面 α× width 个孩子( α是 预定义的大 于 1 的常量) 加入到 url_queue 的顶部; b) 无关网页的前 width 个孩子 URL 加入到 url_queue 队 列 中, 紧靠着相关网页孩子节点的后面; c) 剩下的孩子 URL 加入到 url_queue 的尾部( 即只有在 时 间允许的情况下, 才有可能爬行到)。 上述三种情况可以用一个变量 potential_score 来等价描 述 它们。第一种, potential_score 设置为 1; 第二种设置 为 0. 5; 第 三种设置为 0, 待爬行 URL 队列就按照 potential_score 来排序。 该算法是一种基于客户端的搜索算法。因为其模式简单、 动态搜索, 有一定的吸引力, 但存在如下缺点: 只使用简单的字 符串匹配分配 potential_score 的值, 并且 该 值 是离 散 的 ( 只 有 1、0. 5 和 0 三种); 分配的值并不能完全 代表与主题 的相关度。 在 url_queue 中, 优先级值之间的差别太小。当很多 URL( 节 点) 具有相同的优先级并且在爬 行时间 受到限 制时, 可能后 面 更重要的网页被忽略掉了。另外, 使用 width 参数来 调节删 除 网页后面 URL 的个数也有 点过 于武 断, 可能 导致 丢掉 很多 主 题相关的重要资源。 c) Shark search方法[ 9] 。它在 fish search 算法的 基础上 进 行了如下改进: ( a) 在 fish 算法中, 只有是否相关的二值判断, 而在 shark 算法中引入了相似度度量方法, 取值为 0 ~1。 ( b) 在计算 URL 的 potential_ score 上, 不 但继承 了双亲 的 值, 而且充分利用了锚文字和锚文字的上下文。锚文字的上下 文是指围绕在锚文字周围一定距离的文字。 与 fish 算法相比, shark 算法精 度更高, 能更好地保 证爬行 器正确的搜索方向, 提高相关信息的发现率。 2. 2 基于 Web 超链图评价的方法 基于文字内容的算法只是利用网页、URL、锚文字 等文 字 信息, 没有考虑到通 过超 链而形 成的 Web 有 向图 对主 题网 络 爬虫的影响。基于 Web 图的启发策略的基本思想来自于文献 计量学的引文分析理论。尽管引文分析理论的应用环境与 Web 并不相同, 但到目前为 止, 网页之间的超链还是比较有价 值的一种 信息。基 于 Web 超链图评价的爬行算法有以下几 种: a) BackLink。一个网页被其他网页 所引用的次 数越多, 就 说明越重要。待爬行 URL 队列 按照 BackLink 的 数量来 排序, 数量大的优先爬行。 b) PageRank。基于 Web 图, 按照式( 2) 来计算每个网页 的 PageRank 值, 然后对待爬行 URL 队列按照 PageRank 的值进 行 ·72·第 10 期 刘 金红 , 等 : 主 题网 络爬 虫研 究综 述   槡 槡 排序。 PageRank 算法是由 Google 的创始人 S. Brin 和 L. Page 提 出的, 它是一种与查询式无关的算法[ 10] 。 在 PageRank 算 法 中, 一个网页的链入网页数量越大, 它的重要性就越大, 而没有 考虑入链的质量问题。实际上, 不同质量的网页对网页重要性 的贡献是不同的。简单地说, 按照 BackLink 算 法, 要 想提高 某 网页的重要 性, 只要建立许多网页指向它就可以了。 S. Brin 和 L. Page 提出的 PageRank 算法就是为克服 BackLink 的 这种 不足而设计的。这种计算网页权威度的具体计算方法如下: R( i) = ( 1 - d) + d × j∈B( i) ( 3) 其中: B( i) 是指向网页 i 的网页 集合; N( i) 表 示网 页 i 中指 向 其他网页的超链数目; R( i) 表示网页 i 的权威度。d( 0 < d< 1) 是一个衰减因 子, 表示每个网页本身的权威度有 ( 1 - d) 。它 是不用于传递的, 所以每个网页实际用于传递的只是该网页权 威度的 d 部分, 也即该网页权威度的 d 部分被平均传递给该网 页的所有链出网页。S. Brin 和 L. Page 通 过实验 认为 d 的 最 佳值为 0. 85。 每下载 一个网页后, 抽取其 中包含的超 链, Web 图都 需要 作相应的 改变, 相应的优先级也需要重新计算。基于 Web 图 的启发策略计算 量一 般 都很 大, 所以在实际的网络爬虫设计 中, 需要进行缓冲, 只有下载网页的数量达到设定的阈值后, 才 重新计算待爬行队列的优先级值。 基于 Web 超链图评价的启发策略有如下缺点: 存 在很 多 的导 航 用超 链, 顺着这些超链并不能发现更多的主题资源; PageRank 更适合发现权威网页, 而不适 合发现 主题资 源; 基 于 图的启发策略的计算量一般都很大, 严重影响了爬行器的爬行 速度。 2. 3 基于分类器预测的方法 为了克服基于文字内容难以精确描述用户感兴趣的主题, 以及基于 Web 超链图分 析的 低效率, 研 究者 提出 了基 于分 类 器导引的主题网络爬虫[ 11] , 从而可以基于分类模型来描述用 户感兴趣的主题和预测网页的主题相关度。通过文本分类模 型可以从更深的层次来描述用户感兴趣的主题信息, 并可以更 加准确地计算网页的主题相关性, 而不只停留在基于关键词的 匹配上。文本分类技术应用于主题信息搜索中有利于提高主 题搜索的正确率和准 确率。有关 实验结 果[ 12 ~14] 表 明, 使用 主 题分类器来指导网络爬虫爬行主题相关网页的效果要好得多。 Chakrabarti 等人[ 15] 叙述了一些有关主题网络爬虫的实 验。他们的研究目标包括网页的链接关系和半监督式学习等。 该文中网络爬虫使用规范的主题分类, 从用 户指定 的起点 ( 书 签) 开始。用户将感兴趣的网页做上标记, 并将 它们 归 类, 如 同 Yahoo 的目录层次结构。其主题网络爬虫的主要组成部分 包括分类器、过滤器和爬行器。分类器对网页作相关性判断来 决定访问哪些链接; 过滤器决定访问网页的优先级; 爬行器 是 基于链接的分析。其中使用的评价指标称为获取率, 获取率表 示的是获取相关网页的频率, 以及如何有效过滤不相关网页。 Chakrabarti 等人[ 16] 提出了分别基 于两种 不同的 模型来 计 算网页主题相关性和 URL 访问次序。计算网 页主题相关 性的 模型可以是任何二值分类器, 而计算 URL 访问次序的模 型( 简 称为 apprentice) 是通过包含父网页和子网页及其相关度的训 练样本集合在线训练得到的。对于每一个抽取的网页, ap- prentice 模型根据基本分类器( 即二值分类器, 以此确定父网 页 属于某一类别的概率) 和父网页链接周围的特征进行训练, 以 此来预测父网页指向网页的主题相关度。然后基于这些相关 度预测信息对待爬行队列中的 URL 进 行 排序。 实验 结 果 表 明, 爬行错误网页的数目极大地减少了 ( 大 约 减少 了 30% ~ 90% ) 。 傅向华等人[ 12] 将 Web 爬行看做执行序列动作的过程, 结 合改进的快速 Q 学习和半监督贝叶斯分类器, 提出 了一 种 新 的具有在线增量自学习能力的聚焦爬行方法。该方法从获取 的网页中抽取特 征文 本, 根据特征文本评估网页的主题相关 性, 预测链接的 Q 值, 然后基于 Q 值过滤无关链接。当得到主 题相关网页时产生回报, 然后将回报沿链接链路反馈, 更新 链 路上所有链接的 Q 值, 并选择相应的特征文本作为训练样本, 增量地改善主题评估器和 Q 值预测器。实验结果表明, 该 方 法具有很快的自学习能力, 获取的网页数目和精度均优于离线 聚焦爬行方法, 更符合 Web 资源发现的要求。 李盛韬等人[ 17] 在分 析主 题 Web 信 息采 集 基本 问题 的 基 础上, 提出了主题网络爬虫的难点以及相关的解决方案, 并 在 此基础上设计实现了“天达”主题 Web 信息采集系统。李卫 等 人 [ 18] 以全信息理论为支撑, 吸收传统向量空间模型 的思想, 采 用基于概念的向量空间模型, 从词的语义层次对文本进行主题 相关性分析, 研究并实现了一个基于主题的智能信息采集系统 IFWC。其使用扩展元数据 的语 义相 关性 判定 算法, 对 页面 内 的 URL 进行主题相关性预测。 目前国内外对于基于主题分类器来 引导主题 Web 爬虫 的 研究还非常 少[ 13] 。S . Chakrabarti 等人 [ 11] 第 一 次提 出基 于 朴 素贝叶斯分类模型引导主题 Web 爬 虫。Johnson 等人[ 19] 提 出 了基于 SVM( support vector machine, 支 持向 量机) 分类 模型 来 进行主题爬行。文献[ 12, 14] 中 通过实 验对比 表明, 基于线 性 SVM分类模型的主题 Web 爬虫要比朴素贝叶斯分类模型的 主 题爬行效果好很多。 2. 4 其他主题爬行方法 J. Cho 等人[ 7] 提出通过先爬行更重要的网页使得爬行更 有效, 而提出了各种计算网 页重要 性的方 法, 如网页 与查找 项 的相关性、指向该页的网页个数 ( BackLinks) 、该网 页的 Page- Rank值和该网页所处的位置。一个网页的 PageRank 被递归 地 定义为指向该网页所有网页的 PageRank 权值之和。他们使 用 了基于这些重要性测量的排序机制实现了网络爬虫。该网络 爬虫对斯坦福大学的网站( 大约 225 000 个网页) 进 行了测试。 他们发现使用 BackLink 重要性测量的 网络爬虫类 似深度优 先 查找, 在继续访问前先访问 特定簇 里的网 页, 并经常 受起始 点 左右。使用 PageRank 的网 络爬 虫却 不受 起始 点影 响, 并结 合 了宽度优先和广度优先, 能更好地爬行。同时也发现在较小的 网页域中( 如网页的子 集中), 使用 BackLink 计数 的网 络爬 虫 执行效果不好。 文献[ 5] 中对不同的主题爬行策 略进行了 评价, 它为每 一 百个主题建立一个分类器, 用于评价已爬行过的网页。作者认 ·82· 计 算 机 应 用 研 究 第 24 卷  [ R( j) /N( j)] 为一个好的主题网络爬虫在向量空间中也应该保证主题相关。 他们画了一个随时间变化的抛物线图, 根据网络爬虫是否能保 持主题相关来评价一个网络爬虫的性能。文中评价了三种不 同爬行策略的网络爬虫: a) BestFirst 网络爬虫。根据主题和网页的相关性排列 URLs 的优先级队列。 b) PageRank 网络 爬 虫。以 PageRank 的 次序 排 列 URLs, 每 25 个网页重新计算网页的 PageRank 值。 c) InfoSpiders。采用后向传播的中枢神经网络, 考 虑链 接 周围的文本。 最后实验结果发 现, BestFirst 执 行效 果 最好, 其 次 是 Info- spiders, 最后是 PageRank。研究 者 认为 PageRank 在主 题 爬 行 任务中过于全面, 所以效果不好。 M. Diligenti 等人[ 20] 提出了使用上下文图表来引导主题 网络爬虫。作者认为该领域主要的问题是在爬行中把任务分 配给网页。例如, 一些偏离主题的网页指向符合主题的网页, 结果形成页层次结构。基于这些问题, 提出了基于上下文的网 络爬虫。基于上下文的网络爬虫使用一个通用搜索引擎来获 取链接到专门文本的网页, 并为该文本建立上下文图表。该上 下文图表用于训练一组分类器, 根据与目标的链接距离的预测 值将文本归类。每个种子页都有相应的上下文图和分类器, 并 能够逐层建立直到特定的等级。这样网络爬虫能够获取与目 标主题直接或间接相关的内容, 以及通向目标非常简单的路径 模型。与普通的宽度优先和传统的主题网络爬虫相比, 上下文 主题网络爬虫 ( CFC) 的每一层都使用贝叶斯分类器, 最先 使 用最短路径。使用的评价机制是下载的相关网页的比率。实 验表明, CFC 维护了更高的相关性。 C. Aggarwal 等人[ 21] 提出了 Web 主 题管理系 统( WTMS) 。 他们使用主 题 爬行 技 术, 只下载相关网页附近的网页 ( 如 双 亲、孩子和兄弟) 。它基于对网页的向量空间表示, 网络 爬 虫 下载所有包含主题关键词的 URLs。最后, 它为每 个特 定的 类 固定了一个相关性域值。如果相关性值下降到某个特定值, 将 停止下载。该论文的另外一个方面是使用基于 Hubs 和 Au- thorities 对站点进行逻辑分组的方法, 讲述了如何可视化主题。 A. McCallum 等人[ 22] 提出了使用加强学习的方法建立专 门域的搜索引擎。贝叶斯分类器根据整个网页的文本和链接 文本对超链接进行分类。这样为每个链接计算出了奖励值, 用 于通过加强学习的方法来训练网络爬虫。通过对计算机系站 点的测试表明, 与普通的宽度优先网络爬虫相比, 主 题网络 爬 虫在更少的时间里发现了更多的研究论文。 M. Ehrig 等人[ 23] 提出了 一种基 于 ontology 的 相关 度计 算 和主题爬行体系框架。首先经过网页进行预处理后, 从网 页 中抽取实体( 即 ontology 中出现的关键词) 并进行 频率统计; 然 后针对用户选择的感兴趣实体, 在 ontology 图上基于 多种策 略 来计算主题相关度, 即直接匹配方法、类别关系和复杂关系计 算等方法。通过实验与基本的主题爬虫( 即 简 单通 过关 键 词 的布尔匹配来计算主题相关度 ) 进行比较。结果证明该方法 harvest rate 有了很大提高, 但是它没有与其他类型的主题爬虫 进行比较。 3 主题网络爬虫的研究趋势 综上分析可知, 未来主题网络爬虫的研究主要是围绕如何 提高链接主题预测的准确性, 降低 计算的 时空复 杂度, 以及 增 加主题网络爬虫自适应性这几个方面展开。 提高链接价值预测的准确性一直是近年来研究的焦点。 将各类评价方法相结合, 尤其是基于分类器的主题相关度预测 和基于在线训练、反馈的主题爬行方法值得进一步训究。将目 前信息检索领域中的概念检索理论应用于链接价值的计算, 是 一个新的尝试方向。网络爬虫的爬行具有重复性, 如何将 Web 动态变化的规律与先前搜索的统计结果相结合, 以提高价值计 算的准确性, 是一个值得研究的问题。降低网络蜘蛛在训练、 搜索过程中的计算复杂性, 也是有待进一步研究的问题。目前 的网络爬虫通常采用固定的搜索策略, 缺 乏适应 性, 如何提 高 网络爬虫的自适应性有待进一步研究。 4 结束语 随着人们对个性化信息服务需要的日益增长, 基于主题爬 虫的专业搜索引擎的发展将成为搜索引擎发展的主要趋势之 一。主题网络爬虫爬行策略的研究, 对专业搜索引擎的应用和 发展具有重要意义。本文在给出主题网络爬虫的定义和研究 目标的基础上, 对现有的主题爬行策略进行了分类, 系统分 析 了它们的定制方法, 比较了它们的优缺点。最后, 给出 了若 干 值得进一步研究的问题。 参考文献: [ 1 ] URRAY B, MOORE A. Sizing the Internet[ M] . [ S. l. ] : Cyveil- lance Inc, 2000 . [ 2] LAWRENCE S, GILES L. Accessibility and distribution of information on the Web[ J] . Nature, 1999, 4 00( 8) :107-109. [ 3] CHO J, CARCIA M H. The evolution of the Web and implication for an incremental crawler[ C] //Proc of the 26th International Confe- rence on Very Large Databases ( NVLDB-00) . 2000. [ 4 ] BREWINGTON B E, CYBENKO C. How dynamic is the Web[ C] / / Proc of the 9 th International World Wide Web Conference. 2000. [ 5 ] MENCZER F, PANT C, RUIZ M E. Evaluating topic -driven Web crawlers[ C] / /Proc of SIGIR’01. New Orleans, Louisiana: [ s. n. ] , 2001: 241-249. [ 6] MENCZER F, PANT C, SRINIVASAN P. Topic-driven crawlers: ma- chine learning issues[ EB/OL] . (2002-05-15) . http: / /dollar. biz. uiowa. edu/ ~fil/ papers. html. [ 7] CHO J, GARCIA M H, PAGE L. Efficient crawling through URL orde- ring[ J] . Computer Networks and ISDN Systems, 1998, 30 ( 1- 7) : 161-172. [ 8] DeBRA P, HOUBEN G, KORNATZKY Y, et al. Information retrieval in distributed hypertexts[ C] / /Proc of the 4th RIAO Conference. New York: [ s.n. ] ,1994:481-491. [ 9] HERSOVICI M, JACOVI M, MAAREK Y S, et al. The shark-search algorithm: an application: tailored Web site mapping[ C] / /Proc of the 7th International World Wide Web Conference. Brisbane: [ s. n. ] ,1998:65-74. ( 下转第 47 页 ) ·92·第 10 期 刘 金红 , 等 : 主 题网 络爬 虫研 究综 述 据分析的基础上, 有针对性地选取感兴趣区域进行深入分析, 具有交互性的特点。同时, 由于 可在 SOM 的 局部 邻域 内寻 找 k-最近邻居, 根据离群数据定义进行算法的设计与实现, 使 其 具有可扩展性、可预测性、简明性等特征。 参考文献: [ 1] AN J, KAMBER M. Data mining, concepts and technique[ M] . San Francisco: Morgan Kaufmann, 2001. [ 2] ESKIN E, AMOLD A, PRERAV M, et al. A geometric framework for unsupervised anomaly detection: detecting intrusions in unlabeled data [ C] / /Applications of Data Mining in Computer Security. Boston: Klu- wer Academic Pablishers, 2002. [ 3] JIN Wen, TUNG A K H, HAN Jia-wei. Mining top-n local outliers in large databases[ C] / /Proc of ACM SIGKDD Int’l Conf on Knowledge Discovery and Data Mining. San Francisco: [ s. n. ] , 2001. [ 4] YU D, SHEIKHOLESLAMI G, ZHANG A. Findout: finding outliers in large datasets[ J] . Knowledge and Information Systems, 2002 , 4 ( 4) :387-412. [ 5] KNORR E, NG R. Algorithms for mining distance-based outliers in large datasets[ C] / /Proc of Int’l Conf on Very Large Databases. New York: [ s. n.] ,1998:392-403. [ 6] RAMASWAMY S, RASATOGI R, SHIM K. Efficient algorithms for mining outliers from large data sets[ C] / / Proc of ACM Int’l Conf Management of Data. Dallas: [ s. n. ] , 2000: 427 -438. [ 7 ] ANGIULLI F, PIZZUTI C. Outlier mining in large high-dimensional data sets[ J] . IEEE Trans Knowledge and Data Eng, 2005, 17 (2) : 203-215. [ 8] BREUNIG M M, KRIEGEL H, NG R, et al. LOF: identifying density- based local outliers[ C] / /Proc of ACM Int’l Conf on Managment of Data. Dalles: [ s. n. ] , 2000. [ 9] PAPADIMITRIOU S, KITAGAWA, GIBBONS P B. LOCI: fast outlier detection using the local correlation integral[ C] / / Proc of the 19th In- ternational Conference on Data Engineering. Bangalore: [ s. n. ] , 2003: 315-326. [ 10] KOHONEN T. Self-organizing maps[ M] . Berlin: Springer-Verlag, 1997. [ 11] 汪加 才, 陈奇 , 赵 杰煜, 等 . VISMiner: 一个交互式可视化数据挖掘 原型系 统[ J] . 计算 机工 程, 2003, 29( 1) : 17 -19 . [ 12] ULTYSCH A, SIEMON H P. Kohonen’s self-organizing feature maps for exploratory data analysis [ C] / / Proc of INNC’90 , International Neural Network Conference. Dordrecht, Netherlands: [ s. n. ] , 1990: 305- 308 . [ 13] AGGARWAL C, YU P. Outlier detection for high dimensional data [ C] / / Proc of the SIGMOD. Santa Barbara: ACM Press, 2001: 37 -46. ( 上 接第 29 页 ) [ 10 ] RIN S, PAGE L. The anatomy of a large-scale hypertexual Web search engine[ C] / / Proc of the 7th World Wide Web Conference. Brisbane: [ s. n. ] , 1998 . [ 11] CHAKRABARTI S, DOM B, INDYK P. Enhanced hypertext categori- zation using hyperlinks[ C] / /Proc of the ACM SIGMOD International Conference on Management of Data. Seattle: [ s. n. ] , 1998: 307- 318. [ 12] 傅向 华, 冯博 琴, 马兆 丰, 等. 可在线增量自学习的聚焦爬行方法 [ J] . 西安 交通大 学学 报, 2004, 38( 6) :599-602. [ 13] PANT G, SRINIVASAN P. Link contexts in classifier-guided topical crawlers[ J] . IEEE Transactions on Knowledge and Data Engi- neering , 2006 , 18( 1) :107-122. [ 14] PANT G, SRINIVASAN P. Learning to crawl: comparing classification schemes[ J] . ACM Trans Informatio n System s, 2005, 23 ( 4 ) : 430- 462. [ 15] CHAKRABARTI S, BERG M van den, DOM B. Focused crawling: a new approach to topic-specific Web resource discovery[ C] / / Proc of the 8th tnternational Conference. Toronto: [ s. n. ] , 1999. [ 16 ] CHAKRABARTI S, PUNERA K, SUBRAMANYAM M. Accelerated focused crawling through online relevance feedback[ C] / / Proc of the 11th International World Wide Web Conference. Hawaii: [ s. n. ] , 2002. [ 17] 李盛 韬, 赵章 界, 余智华 . 基 于主 题 的 Web 信 息采 集 系 统 的设 计 与实 现[ J] . 计算 机工程 , 2003, 29( 17) :102-104. [ 18] 李卫 , 刘 建毅, 何 华灿, 等. 基于 主题 的 智能 Web 信 息采 集 系统 的 研究 与实 现[ J] . 计算机 应用 研究, 2006, 23( 2) :163-166. [ 19] JOHNSON J, TSIOUTSIOULIKLIS K, GILES C L. Evolving strategies for focused Web crawling[ C] / /Proc of Int’l Conf Machine Lear- ning. 2003. [ 20] DILIGENTI M, COETZEE F, LAWRENCE S, et al. Focused crawling using context graphs[ C] / /Proc of the 26th International Conference on Very Large Databases ( VLDB 2000) . Cairo: [ s. n. ] , 2000. [ 21 ] AGGARWAL C, AL-GARAWI F, YU P. Intelligent crawling on the world wide Web with arbitrary predicates[ C] / /Proc of the 10th In- ternational World Wide Web Conference. Hong Kong: [ s. n. ] , 2001. [ 22] MCALLUM A, NIGAM K, RENNIE J, et al. Building domain-specific search engines with machine learning techniques[ C] / /Proc of 1999 AAAI Spring Symposium on Intelligent Agents in Cyberspace. Stan- ford, CA: Stanford University, 1999 . [ 23] EHRIG M, MAEDCHE A. Ontology-focused crawling of Web docu- ments[ C] / / Proc of ACM Symposium on Applied Computing. 2003. ·74·第 10 期 汪 加才 , 等 : 基 于 SOM 的离群数据挖掘集成框架研究 1 8 9 9 9 7 兹 兹 兹 兹 兹 1 远 圆 兹1圆远 远 远 8 缘 缘 猿 源 兹兹 远 猿 源 源 缘 缘 源 员员员园 1 园 园 园 园 园 兹 兹 兹 兹 兹 园 员 园 兹园园员 员 园 园 园 园 员 员 兹兹 园 园 园 园 园 园 园 员 猿 1 园 园 园 园 园 兹 兹 兹 兹 兹 园 员 园 兹园园员 员 园 园 园 园 员 园 兹兹 园 园 园 园 园 员 园 员 猿 (a) 数据点分布图 (b) Dk 离群点分布图 (c) wk 离群点分布图 图 1 Iris 数据集的 SOM 命中标记图 全域 Dk 蛳离群点 基 于 SOM 的局 域 Dk 蛳离群点 全域 W k蛳离群点 基 于 SOM 的 局 域 W k蛳离群点 (a) Dk 蛳离群点及 Dk 蛳距离 (基于全域及基于 SOM V 集) (b) wk蛳离群点及 wk蛳距离 (基于全域及基于 SOM V 集) 4 3.5 3 2.5 2 1.5 1 0.5 0 离群数据点序号1321184216611191101078688 42132118161106110711910986 2.5 2 1.5 1 0.5 0 离群数据点序号 图 2 Iris 数据集的离群数据及距离
还剩4页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 3 人已下载

下载pdf

pdf贡献者

xydc321217

贡献于2012-03-08

下载需要 5 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf