化学主题网络爬虫的设计和实现
夏诏杰梁春燕郭力
（中国科学院过程工程所多相实验室，北京１０００８０）
Ｅ－ｍａｉｌ：ｚｊｘｉａ＠ｈｏｍｅ．ｉｐｅ．ａｃ．ｃｎ
摘
要由于通用搜索引擎检索返回的结果过多、主题相关性不强以及随着人们对提供的各项信息服务的要求越来越
高，基于整个Ｗｅｂ的信息采集越来越力不从心。同时它无法及时地采集到足够的最新的Ｗｅｂ信息，也不能满足人们日
益增长的个性化需求。本文通过把Ｉｎｔｅｒｎｅｔ化学资源导航系统所积累的化学知识与搜索引擎的自动采集技术相结合展开了对化学主题网络爬虫开发的研究。结果表明，基于Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的化学主题网络爬虫能有效的采集化学相关的网页。关键词主题爬虫
主题搜索引擎
化学主题网络爬虫Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器
文献标识码Ａ
中图分类号ＴＰ３９３
文章编号１００２－８３３１－（２００６）１０－０２０４－０２
ＤｅｓｉｇｎａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆａＣｈｅｍｉｓｔｒｙＦｏｃｕｓｅｄＷｅｂＣｒａｗｌｅｒ
ＸｉａＺｈａｏｊｉｅＬｉａｎｇＣｈｕｎｙａｎＧｕｏＬｉ
（Ｍｕｌｔｉ－ＰｈａｓｅＲｅａｃｔｉｏｎＬａｂｏｒａｔｏｒｙ，ＩｎｓｔｉｔｕｔｅｏｆＰｒｏｃｅｓｓＥｎｇｉｎｅｅｒｉｎｇ，
ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０）
Ａｂｓｔｒａｃｔ：ＴｈｅｐｏｐｕｌａｒｉｔｙｏｆＷｅｂｈａｓｂｅｅｎｇｒｏｗｉｎｇｒａｐｉｄｌｙｉｎｔｈｅｌａｓｔｆｅｗｙｅａｒｓ．Ｈｏｗｅｖｅｒ，ｆａｃｅｄｗｉｔｈｐｅｏｐｌｅ’ｓ
ｒｅｑｕｉｒｅｍｅｎｔｓｍｏｒｅａｎｄｍｏｒｅｒｉｇｏｒｏｕｓａｎｄｐｒｏｌｉｆｉｃ，ｇｅｎｅｒａｌｓｅａｒｃｈｅｎｇｉｎｅｓｔｉｌｌｃａｎ’ｔｓａｔｉｓｆｙｐｅｒｓｏｎａｌｎｅｅｄａｃｃｕｒａｔｅｌｙ．ＢａｓｅｄｏｎｃｏｍｂｉｎａｔｉｏｎｏｆｉｎｆｏｒｍａｔｉｏｎａｃｃｕｍｕｌａｔｅｄｉｎＩｎｔｅｒｎｅｔｎａｖｉｇａｔｏｒｏｆｃｈｅｍｉｃａｌｒｅｓｏｕｒｃｅｓａｎｄａｕｔｏｍａｔｉｃｃｏｌｌｅｃｔｉｏｎｏｆｗｅｂｃｒａｗｌｅｒ，ｔｈｉｓａｒｔｉｃｌｅｂｒｉｎｇｓｆｏｒｗａｒｄａｓｔｒｕｃｔｕｒｅｄｅｓｉｇｎｍｏｄｅｌｏｆｃｈｅｍｉｓｔｒｙｆｏｃｕｓｅｄｗｅｂｃｒａｗｌｅｒｂａｓｅｄｏｎＷｉｄｒｏｗ－Ｈｏｆｆｃｌａｓｓｉｆｉｅｒａｎｄｖｅｒｉｆｉｅｓｉｔｓａｂｉｌｉｔｙ．
Ｋｅｙｗｏｒｄｓ：ｆｏｃｕｓｅｄｃｒａｗｌｅｒ，ｔｏｐｉｃｓｅａｒｃｈｅｎｇｉｎｅ，ｃｈｅｍｉｓｔｒｙｆｏｃｕｓｅｄｃｒａｗｌｅｒ，Ｗｉｄｒｏｗ－Ｈｏｆｆｃｌａｓｓｉｆｉｅｒ
１引言
经过短短几年的Ｉｎｔｅｒｎｅｔ特别是Ｗｅｂ技术的高速发展，Ｉｎｔｅｒｎｅｔ正在成为化学信息的主要载体，并成为化学工作者快速获取信息的主要途径。然而Ｗｅｂ信息的急速膨胀，又对化学工作者如何有效利用分布在Ｉｎｔｅｒｎｅｔ上的化学资源方面提出了一个巨大的挑战。为此人们发展了对Ｉｎｔｅｒｎｅｔ上的资源建立索引的服务。目前建立索引主要有两种方法，一种是利用一个称为Ｃｒａｗｌｅｒ程序自动地采集资源并建立索引的搜索引擎，如Ｇｏｏｇｌｅ等；另一种是通过人工搜集并判定的方法建立的Ｉｎｔｅｒ－ｎｅｔ导航系统，如Ｙａｈｏｏ！等。在化学领域，已经建立起了几个比较有代表性的化学资源导航系统，如美国印第安纳大学的ＣＨＥＭＩＮＦＯ，英国谢菲尔德大学的ＣｈｅｍＤｅｘ，英国利物浦大学
［１］
的“ＬｉｎｋｓｆｏｒＣｈｅｍｉｓｔｓ”和中国科学院过程工程研究所的
［２］
ＣｈＩＮ。Ｉｎｔｅｒｎｅｔ化学导航系统主要靠人工来搜集资源，可以利用人的化学知识和化学信息源的知识，在信息资源的评价和信息资源的组织方面都可以很好地满足化学家的需要［３］。但是其不足之处是需要投入大量的人力才能适应Ｉｎｔｅｒｎｅｔ化学资源的不断增长的需要，同时人工维护难以反映Ｉｎｔｅｒｎｅｔ资源高度动态的基本特征。通用的搜索引擎基于整个Ｗｅｂ的信息采集，采集的页面数量非常大，同时由于计算机在处理信息的相关性方面还有很大的局限性，这就使检索的结果中包含了大量相关性很小的内容。事实上，专业领域的用户一般只关心和其领域相关的一些资源，这在通用搜索引擎采集的所有资源中只占很少一部分。如果对整个Ｗｅｂ页面分类，按类别采集就可以减少采
基金项目：国家自然科学基金资助项目（编号：２０２７３０７６）
集页面的数量，同时还可以提高检索精度。
网络爬虫作为搜索引擎的基础和组成部分，随着应用的深化和技术的发展，将会发挥越来越重要的作用。本文通过把Ｉｎｔｅｒｎｅｔ化学资源导航系统ＣｈＩＮ所积累的资源与搜索引擎的自动采集技术相结合，进行对化学主题网络爬虫开发的研究。
２化学主题网络爬虫实现策略
主题网络爬虫主要由两个模块组成，一个是分类模块，一个是爬行模块。分类模块通过分类器对采集的网页打分，从网页解析出新的ＵＲＬｓ，并赋予它们相应的网页分值，最后把ＵＲＬｓ插入到按分值大小排序的队列中。爬行模块则从排序队列中取出分值最大的ＵＲＬｓ最先爬行。与广度优先（Ｂｒｅａｔｈ－Ｆｉｒｓｔ）爬虫相比，主题爬虫的爬行策略变为主题相关优先（Ｔｏｐｉｃ－Ｆｉｒｓｔ）。
２．１ＣｈＩＮ简介
ＣｈＩＮ是由中科院过程工程研究所自１９９６年开始建立和维护的Ｉｎｔｅｒｎｅｔ化学资源导航系统，它通过人工方法搜集和组织Ｉｎｔｅｒｎｅｔ上的化学相关资源，并为每条资源建立了反映资源概貌和特征的简介页。到２００４年８月，ＣｈＩＮ已经搜集了超过
［２］
了１００００条化学相关的资源。
２．２化学主题样本网页集
样本网页集是指预先通过人工选取与某一主题相关的网页集合，我们利用ＣｈＩＮ上的搜集的资源作为化学主题的样本网页集。
２．３特征词提取
作者简介：夏诏杰（１９７６－），男，博士生，主要从事Ｗｅｂ信息检索研究。梁春燕（１９７５－），女，博士生，主要从事Ｗｅｂ信息检索研究。郭力（１９６６－），男，
在构建分类器时，存在一个特征向量高维的问题。如果直接用构成文本的词条来表示文本向量，向量的空间就会非常大，进而影响程序的运行效率。另外，构成文本的词条包括一些和此类不相关的词条，如一些停用词，而且数量非常多，因此必须进行特征词的提取。
２．４文本的表示
文本的表示主要采用向量空间模型（ＶＳＭ）。向量空间模型的基本思想是以向量来表示文本：（Ｗ１，Ｗ２，Ｗ３……Ｗｎ），其中Ｗｉ为第ｉ个特征项的权重。本文采用ｔｆ－ｉｄｆ权重算法表示特征词在各文档中的权重。
２．５Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器
Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器是Ｄ．Ｄ．Ｌｅｗｉｓ提出的一个线性分类器，有别于ｋＮＮ，它只需与类的中心向量进行相似度计算来作为分类的依据［４］；而ｋＮＮ必须和类的所有文档向量作比较，因而在时间复杂度上有明显的差别。中心向量通过对所有的训练文档计算得到。
初始时，中心向量Ｇ０为０向量。通过前一个向量ｉ可以推出第ｉ＋１个向量。最后将ｎ个文件的ｎ＋１个向量算出。计算公式如下：
Ｇｉ＋１＝Ｇｉ－２η（ＧｉＩｉ－Ｌｉ）Ｉｉ
Ｉｉ代表第ｉ个文档向量，Ｌｉ∈（１，０），文档是本类时取１，反之为０，η是学习速率，本文优化后取０．２５。相似度计算公式如下：
ＧＱｓｉｍ（Ｇ，Ｑ）＝
#其中Ｇ是样本网页集的中心向量，Ｑ指网页向量。采集过程中，通过Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器对采集网页分类打分，把从此网页中解析出来的ＵＲＬｓ赋予网页相同分值并且插入到按分值排序的待爬行队列中。程序的伪码如下：
ＴｏｐｉｃＦｉｒｓｔ（ｓｅｅｄ＿ｕｒｌｓ）｛
ｓｅｅｄ＿ｕｒｌｓ）｛ｆｏｒｅａｃｈｕｒｌ（
ｅｎｑｕｅｕｅ（ｆｒｏｎｔｉｅｒ，ｕｒｌ）；｝
ｗｈｉｌｅ（ｆｒｏｎｔｉｅｒ＿ｓｉｚｅ＞０）｛ｕｒｌ：＝ｄｅｑｕｅｕｅ＿ｕｒｌ＿ｗｉｔｈ＿ｍａｘ＿ｓｃｏｒｅ（ｆｒｏｎｔｉｅｒ）；ｐａｇｅ：＝ｆｅｔｃｈ（ｕｒｌ）；ｓｃｏｒｅ：＝ｓｉｍ（ｐａｇｅ）；ｆｏｒｅａｃｈｏｕｔｌｉｎｋ（ｅｘｔｒａｃｔ＿ｌｉｎｋｓ（ｐａｇｅ））｛ｅｎｑｕｅｕｅ（ｆｒｏｎｔｉｅｒ，ｏｕｔｌｉｎｋ，ｓｃｏｒｅ）；｝｝｝
Ｔ
获取链向某页面的ＵＲＬｓ，即Ｉｎｌｉｎｋｓ等功能。本文就是通过对各个目标ＵＲＬｓ为参数迭代调用ＩｎｌｉｎｋｓＡＰＩ来选取种子ＵＲＬｓ。迭代调用的次数可以看成种子到目标之间的距离。最后为每个目标选取相应的一个种子，并且保证从种子到目标的通路没有坏链接。
实验中选取了５０个目标ＵＲＬｓ，并且调用ＧｏｏｇｌｅＡＰＩ获得５０个种子ＵＲＬｓ。种子到目标的距离是３，即对每个目标ＵＲＬｓ迭代调用了３次。
图１表示了采用Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的化学主题爬虫Ｔｏｐｉｃ－Ｆｉｒｓｔ）和以广度优先（Ｂｒｅａｔｈ－Ｆｉｒｓｔ）爬虫的爬准率曲线。（
从图中也可以看出，在整个爬行过程中，采用了Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的主题爬虫在爬准率上明显优于广度优先爬虫。
图２则对比了采用Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的化学主题爬虫（Ｔｏｐｉｃ－Ｆｉｒｓｔ）和以广度优先爬虫（Ｂｒｅａｔｈ－Ｆｉｒｓｔ）的爬全率。
３结果和分析
Ｍｅｎｃｚｅ等提出［５］用于评价主题网络爬虫系统的指标同传
统信息检索一样主要有两个：（１）爬准率（Ｐｒｅｃｉｓｉｏｎ）；（２）爬全率（Ｒｅｃａｌｌ）。定义分别如下：
Ｐｒｅｃｉｓｉｏｎ＝采集的目标页面数
Ｒｅｃａｌｌ＝采集的目标页面数
为了便于进行评价，我们预先设定一些种子页面（ＵＲＬｓ）和目标页面（ＵＲＬｓ）。除了利用ＣｈＩＮ上搜集的部分资源作为化学主题的训练样本网页集外，另外选取一些和训练样本网页不重叠的网页作为目标页面。Ｇｏｏｇｌｅ提供了一些基于ＳＯＡＰ和
图２中显示在各自爬行了５０００个页面后，主题爬虫的爬
全率达到４８％，而以广度优先爬虫只有１０％左右。
从上面分析可以看出，采用Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的主题爬虫不管是爬准率还是爬全率上都明显的优于广度优先的爬虫。这也说明利用化学主题爬虫可以明显提高页面采集的质量和效率。
４结论
本文利用ＣｈＩＮ网站上通过人工搜集积累的化学资源作为训练样本网页集和目标页面。通过实验对比评价了化学主题爬虫和广度优先爬虫。实验结果表明拥有Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的主题爬虫不管在爬准率还是在爬全率上都明显地优于广度优先爬虫，这也说明化学主题网络爬虫能有效地采集化学主题相关的网页。今后工作我们将进一步利用其他一些分类器如，ＮａｉｖｅＢａｙｅｓ，支持向量机（ＳＶＭ）等来构建主题爬虫。（收稿日期：２００５年６月）
页）
３．１．２在网格环境中部署运行中心服务的节点
在网格开始使用之前，要首先对网格环境进行初始化，根据网格规模和地理位置人工地部署中心结点。然后随着网格规模的不断扩大或网格的实际运行需要，可以采用网格辅助人工部署中心的办法，也可以采用网格环境自动动态部署中心的办法来实现网格中心的在整个网格环境中的合理部署。
这就需要解决何时需要在网格中部署中心的问题。可以采用设定阈值的方法，该阈值表示了网格允许的资源匹配和任务调度的最低效率。对每一个任务的招标业务所用的时间占该任务的完成时间的比例（在此称为任务的招标消耗率）进行统计，将所有任务的招标消耗率进行平均，如果超过了初始设置的阈值，则表明整个网格花费在资源匹配和任务调度上的开销过多，需要在网格中部署新的中心，降低管理开销在整个网格开销中所占的比例。
设：ＢＴｉｊ（ＢｉｄｄｉｎｇＴｉｍｅ）为任务ｊ在中心ｉ进行招标所用的时间；ＡＴＣＴｊ（ＡｃｔｕａｌＴａｓｋＣｏｍｐｌｅｔｉｏｎＴｉｍｅ）为实际任务ｊ的完成时间；
ＢＣＲｉ（ＢｉｄｄｉｎｇＣｏｓｔＲａｔｅ）为中心ｉ的平均招标消耗率；ｎ为在中心ｉ招标的任务数；则：
ＢＴ! ｉｊ
ｊ＝１ｎ
工作，即将部分招投标业务由重载的中心迁移到轻载的中心去，从而实现快速的资源匹配，提高网格管理效率。解决网格环境中中心节点之间的负载平衡问题可以采用以下三种方法：
第一种方法是用户负责法。在用户招标时，通过用户综合考虑中心的所处的地理位置（用户和中心的网络状况）因素和中心当前的招标消耗率因素，选择一个最佳的中心委托其的招标业务。
第二种方法是中心负责法。事实上，由网格环境中所有的中心节点形成的网络，已经构成了一个专门负责招投标业务的分布式计算环境，因此，中心间的负载平衡问题是典型的分布式系统中负载平衡问题，由于在中心处理的每一个招投标业务都是功能统一、相互独立的任务，这使得负载平衡问题变得相对容易了。我们提出了一种基于任务压力的完全分布式的负载
［８］
平衡算法，在仿真中取得了理想的效果。中心负责的方法是对用户透明的。
第三种方法是用户———中心法。在实现中心的负载平衡策略中，第一和第二种方法同时使用，即首先通过用户选择轻载的中心，如仍然出现中心间负载不平衡时，由中心进一步地进行负载平衡工作。第三种方法同时具有用户负责法和中心负责法的优点，因而是好的方法。
４结论
（１）
本文提出基于资源提供者主动参与的竞标机制的网格资源匹配和任务调度方法，是一种分布式的和通用的方法，采用了与目前主要网格项目不同的资源匹配的方法。通过在网格中建立一个虚拟机构———招投标管理中心（一种在某些节点上运行的特殊网格服务），该中心作为用户和公司进行资源消费和资源提供协商的中介，来解决网格资源的多重管理、网格的资源的发现和匹配、网格任务的调度、提高网格可用性、和负载的平衡等问题。通过将网格管理任务进行划分，即资源的局部自治管理，网格的其他管理任务是通过虚拟机构实现快速的资源匹配和任务调度来实现对整个网格的管理。该分布的管理模式便于降低整个网格的管理开销占总网格开销的比例，能够实现不依靠扩大网格规模却能够得到由于网格规模的扩大带来的绝对性能的提高。（收稿日期：２００５年９月）
ＢＣＲｉ＝
ｊ
设：
ＢＣＲ（ＢｉｄｄｉｎｇＣｏｓｔＲａｔｅ）为网格环境的招标消耗率；ｍ为当前网格中中心的总数。则：
（２）
（１）采用人工的办法是：当网格招标消耗率ＢＣＲ大于初始设定的阈值时，网格环境发出报警，提示需要部署新的中心，并给出各个中心对应的ＢＣＲｉ的变化图。可以人工选择节点作为中心，为其安装并运行中心的系统软件，使其成为中心。中心的系统软件在初始化时具有向网格环境通知本中心成立的功能。
（２）采用网格环境自动动态部署的方法是：当网格招标消耗率ＢＣＲ大于初始设定的阈值时，初始化时部署的中心（在此称为父中心）根据地理位置和可信度等因素与其他网格结点进行协商，选择合适的节点，将中心的招标处理系统软件下载并安装到该结点，该节点运行系统，成为中心（在此称为子中心）。网格环境自动动态部署中心的方法具有网格环境的动态自适应特点，当ＢＣＲ小于初始设定的阈值时，父中心可以动态地停止部分由它部署的子中心的工作，当ＢＣＲ大于初始设定的阈值时，又可以开始子中心的工作。
ＢＣＲ＝
! ＢＣＲ
ｉ＝１
ｍ
ｉ
参考文献
１．［美］ＩａｎＦｏｓｔｅｒ，ＣａｒｌＫｅｓｓｅｌｍａｎ编著．金海，袁平鹏，石柯译．网格计算［Ｍ］．
第二版，北京：电子工业出版社，２００４－１０２．ｈｔｔｐ：／／ｗｗｗ．ｇｌｏｂｕｓｅ．ｏｒｇ
３．ＴｈｅＤａｔａＧｒｉｄＰｒｏｊｅｃｔ．ｈｔｔｐ：／／ｗｗｗ．ｄａｔａ．ｃｎｒ．ｉｔ４．ｈｔｔｐ：／／ｗｗｗ．ｃａｃｔｕｓｃｏｄｅ．ｏｒｇ５．ｈｔｔｐ：／／ｗｗｗ．ｃａｃｒ．ｃａｌｔｅｃｈ．ｅｄｕ／ＳＦＥｘｐｒｅｓｓ６．ｈｔｔｐ：／／ｗｗｗ－ｉｔｇ．ｌｂｌ．ｇｏｖ／ｎｇｉ／７．ＫＣｚａｊｋｏｗｓｋｉ，ＳＦｉｔｚｇｅｒａｌｄ，ＩＦｏｓｔｅｒｅｔａｌ．ＣｒｉｄＩｎｆｏｒｍａｔｉｏｎＳｅｒｖｉｃｅｓｆｏｒＤｉｓｔｒｉｂｕｔｅｄＲｅｓｏｕｒｃｅＳｈａｒｉｎｇ［Ｃ］．Ｉｎ：ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＴｅｎｔｈＩＥＥＥ３ｒｄＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＨｉｇｈ－ＰｅｒｆｏｒｍａｎｃｅＤｉｓｔｒｉｂｕｔｅｄＣｏｍ－ｐｕｔｉｎｇ（ＨＰＤＣ－１０），ＩＥＥＥＰｒｅｓｓ，２００１－０８８．赵宏，杨愚鲁．一种完全分布的网格任务调度算法［Ｊ］．计算机工程与应用，２００５；４１（１３）：１７～１９，３１２００５－０５３．李晓霞，杨章远，许志宏等．Ｉｎｔｅｒｎｅｔ化学资源的发展状况与展望［Ｊ］．计算机和应用化学，１９９９；５：３２５～３２６４．ＤＤＬｅｗｉｓ，ＲＥｃｈａｐｉｒｅ，ＪＰＣａｌｌａｎｅｔａｌ．Ｔｒａｉｎｉｎｇａｌｇｏｒｉｔｈｍｓｆｏｒｌｉｎｅａｒｔｅｘｔｃｌａｓｓｉｆｉｃａｔｉｏｎｓ［Ｃ］．Ｉｎ：ＰｒｏｃＡＣＭＳＩＧＩＲ，１９９６５．ＦＭｅｎｃｚｅｒ，ＧＰａｎｔ，ＭＲｕｉｚｅｔａｌ．Ｅｖａｌｕａｔｉｎｇｔｏｐｉｃ－ｄｒｉｖｅｎｗｅｂｃｒａｗｌｅｒｓ［Ｃ］．２００１３．２中心的负载平衡技术
在网格环境中心节点间的业务量出现不平衡时，即个别中
心招标的业务过多，但网格整体的招标消耗还没有达到必须在网格中部署新的中心的警戒阈值时，由于中心节点间负载的不平衡，会影响整个网格的效率，需要在中心之间进行负载平衡（上接２０５页）
参考文献
１．ＵｎｉｖｅｒｓｉｔｙｏｆＬｉｖｅｒｐｏｏｌ．ＬｉｎｋｓｆｏｒＣｈｅｍｉｓｔｓ．ｈｔｔｐ：／／ｗｗｗ．ｌｉｖ．ａｃ．ｕｋ／Ｃｈｅｍｉｓｔｒｙ／Ｌｉｎｋｓ／ｌｉｎｋｓ．ｈｔｍｌ，２００５－０５
／
化学主题网络爬虫的设计和实现
夏诏杰梁春燕郭力
（中国科学院过程工程所多相实验室，北京１０００８０）
Ｅ－ｍａｉｌ：ｚｊｘｉａ＠ｈｏｍｅ．ｉｐｅ．ａｃ．ｃｎ
摘
要由于通用搜索引擎检索返回的结果过多、主题相关性不强以及随着人们对提供的各项信息服务的要求越来越
高，基于整个Ｗｅｂ的信息采集越来越力不从心。同时它无法及时地采集到足够的最新的Ｗｅｂ信息，也不能满足人们日
益增长的个性化需求。本文通过把Ｉｎｔｅｒｎｅｔ化学资源导航系统所积累的化学知识与搜索引擎的自动采集技术相结合展开了对化学主题网络爬虫开发的研究。结果表明，基于Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的化学主题网络爬虫能有效的采集化学相关的网页。关键词主题爬虫
主题搜索引擎
化学主题网络爬虫Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器
文献标识码Ａ
中图分类号ＴＰ３９３
文章编号１００２－８３３１－（２００６）１０－０２０４－０２
ＤｅｓｉｇｎａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆａＣｈｅｍｉｓｔｒｙＦｏｃｕｓｅｄＷｅｂＣｒａｗｌｅｒ
ＸｉａＺｈａｏｊｉｅＬｉａｎｇＣｈｕｎｙａｎＧｕｏＬｉ
（Ｍｕｌｔｉ－ＰｈａｓｅＲｅａｃｔｉｏｎＬａｂｏｒａｔｏｒｙ，ＩｎｓｔｉｔｕｔｅｏｆＰｒｏｃｅｓｓＥｎｇｉｎｅｅｒｉｎｇ，
ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０）
Ａｂｓｔｒａｃｔ：ＴｈｅｐｏｐｕｌａｒｉｔｙｏｆＷｅｂｈａｓｂｅｅｎｇｒｏｗｉｎｇｒａｐｉｄｌｙｉｎｔｈｅｌａｓｔｆｅｗｙｅａｒｓ．Ｈｏｗｅｖｅｒ，ｆａｃｅｄｗｉｔｈｐｅｏｐｌｅ’ｓ
ｒｅｑｕｉｒｅｍｅｎｔｓｍｏｒｅａｎｄｍｏｒｅｒｉｇｏｒｏｕｓａｎｄｐｒｏｌｉｆｉｃ，ｇｅｎｅｒａｌｓｅａｒｃｈｅｎｇｉｎｅｓｔｉｌｌｃａｎ’ｔｓａｔｉｓｆｙｐｅｒｓｏｎａｌｎｅｅｄａｃｃｕｒａｔｅｌｙ．ＢａｓｅｄｏｎｃｏｍｂｉｎａｔｉｏｎｏｆｉｎｆｏｒｍａｔｉｏｎａｃｃｕｍｕｌａｔｅｄｉｎＩｎｔｅｒｎｅｔｎａｖｉｇａｔｏｒｏｆｃｈｅｍｉｃａｌｒｅｓｏｕｒｃｅｓａｎｄａｕｔｏｍａｔｉｃｃｏｌｌｅｃｔｉｏｎｏｆｗｅｂｃｒａｗｌｅｒ，ｔｈｉｓａｒｔｉｃｌｅｂｒｉｎｇｓｆｏｒｗａｒｄａｓｔｒｕｃｔｕｒｅｄｅｓｉｇｎｍｏｄｅｌｏｆｃｈｅｍｉｓｔｒｙｆｏｃｕｓｅｄｗｅｂｃｒａｗｌｅｒｂａｓｅｄｏｎＷｉｄｒｏｗ－Ｈｏｆｆｃｌａｓｓｉｆｉｅｒａｎｄｖｅｒｉｆｉｅｓｉｔｓａｂｉｌｉｔｙ．
Ｋｅｙｗｏｒｄｓ：ｆｏｃｕｓｅｄｃｒａｗｌｅｒ，ｔｏｐｉｃｓｅａｒｃｈｅｎｇｉｎｅ，ｃｈｅｍｉｓｔｒｙｆｏｃｕｓｅｄｃｒａｗｌｅｒ，Ｗｉｄｒｏｗ－Ｈｏｆｆｃｌａｓｓｉｆｉｅｒ
１引言
经过短短几年的Ｉｎｔｅｒｎｅｔ特别是Ｗｅｂ技术的高速发展，Ｉｎｔｅｒｎｅｔ正在成为化学信息的主要载体，并成为化学工作者快速获取信息的主要途径。然而Ｗｅｂ信息的急速膨胀，又对化学工作者如何有效利用分布在Ｉｎｔｅｒｎｅｔ上的化学资源方面提出了一个巨大的挑战。为此人们发展了对Ｉｎｔｅｒｎｅｔ上的资源建立索引的服务。目前建立索引主要有两种方法，一种是利用一个称为Ｃｒａｗｌｅｒ程序自动地采集资源并建立索引的搜索引擎，如Ｇｏｏｇｌｅ等；另一种是通过人工搜集并判定的方法建立的Ｉｎｔｅｒ－ｎｅｔ导航系统，如Ｙａｈｏｏ！等。在化学领域，已经建立起了几个比较有代表性的化学资源导航系统，如美国印第安纳大学的ＣＨＥＭＩＮＦＯ，英国谢菲尔德大学的ＣｈｅｍＤｅｘ，英国利物浦大学
［１］
的“ＬｉｎｋｓｆｏｒＣｈｅｍｉｓｔｓ”和中国科学院过程工程研究所的
［２］
ＣｈＩＮ。Ｉｎｔｅｒｎｅｔ化学导航系统主要靠人工来搜集资源，可以利用人的化学知识和化学信息源的知识，在信息资源的评价和信息资源的组织方面都可以很好地满足化学家的需要［３］。但是其不足之处是需要投入大量的人力才能适应Ｉｎｔｅｒｎｅｔ化学资源的不断增长的需要，同时人工维护难以反映Ｉｎｔｅｒｎｅｔ资源高度动态的基本特征。通用的搜索引擎基于整个Ｗｅｂ的信息采集，采集的页面数量非常大，同时由于计算机在处理信息的相关性方面还有很大的局限性，这就使检索的结果中包含了大量相关性很小的内容。事实上，专业领域的用户一般只关心和其领域相关的一些资源，这在通用搜索引擎采集的所有资源中只占很少一部分。如果对整个Ｗｅｂ页面分类，按类别采集就可以减少采
基金项目：国家自然科学基金资助项目（编号：２０２７３０７６）
集页面的数量，同时还可以提高检索精度。
网络爬虫作为搜索引擎的基础和组成部分，随着应用的深化和技术的发展，将会发挥越来越重要的作用。本文通过把Ｉｎｔｅｒｎｅｔ化学资源导航系统ＣｈＩＮ所积累的资源与搜索引擎的自动采集技术相结合，进行对化学主题网络爬虫开发的研究。
２化学主题网络爬虫实现策略
主题网络爬虫主要由两个模块组成，一个是分类模块，一个是爬行模块。分类模块通过分类器对采集的网页打分，从网页解析出新的ＵＲＬｓ，并赋予它们相应的网页分值，最后把ＵＲＬｓ插入到按分值大小排序的队列中。爬行模块则从排序队列中取出分值最大的ＵＲＬｓ最先爬行。与广度优先（Ｂｒｅａｔｈ－Ｆｉｒｓｔ）爬虫相比，主题爬虫的爬行策略变为主题相关优先（Ｔｏｐｉｃ－Ｆｉｒｓｔ）。
２．１ＣｈＩＮ简介
ＣｈＩＮ是由中科院过程工程研究所自１９９６年开始建立和维护的Ｉｎｔｅｒｎｅｔ化学资源导航系统，它通过人工方法搜集和组织Ｉｎｔｅｒｎｅｔ上的化学相关资源，并为每条资源建立了反映资源概貌和特征的简介页。到２００４年８月，ＣｈＩＮ已经搜集了超过
［２］
了１００００条化学相关的资源。
２．２化学主题样本网页集
样本网页集是指预先通过人工选取与某一主题相关的网页集合，我们利用ＣｈＩＮ上的搜集的资源作为化学主题的样本网页集。
２．３特征词提取
作者简介：夏诏杰（１９７６－），男，博士生，主要从事Ｗｅｂ信息检索研究。梁春燕（１９７５－），女，博士生，主要从事Ｗｅｂ信息检索研究。郭力（１９６６－），男，
在构建分类器时，存在一个特征向量高维的问题。如果直接用构成文本的词条来表示文本向量，向量的空间就会非常大，进而影响程序的运行效率。另外，构成文本的词条包括一些和此类不相关的词条，如一些停用词，而且数量非常多，因此必须进行特征词的提取。
２．４文本的表示
文本的表示主要采用向量空间模型（ＶＳＭ）。向量空间模型的基本思想是以向量来表示文本：（Ｗ１，Ｗ２，Ｗ３……Ｗｎ），其中Ｗｉ为第ｉ个特征项的权重。本文采用ｔｆ－ｉｄｆ权重算法表示特征词在各文档中的权重。
２．５Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器
Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器是Ｄ．Ｄ．Ｌｅｗｉｓ提出的一个线性分类器，有别于ｋＮＮ，它只需与类的中心向量进行相似度计算来作为分类的依据［４］；而ｋＮＮ必须和类的所有文档向量作比较，因而在时间复杂度上有明显的差别。中心向量通过对所有的训练文档计算得到。
初始时，中心向量Ｇ０为０向量。通过前一个向量ｉ可以推出第ｉ＋１个向量。最后将ｎ个文件的ｎ＋１个向量算出。计算公式如下：
Ｇｉ＋１＝Ｇｉ－２η（ＧｉＩｉ－Ｌｉ）Ｉｉ
Ｉｉ代表第ｉ个文档向量，Ｌｉ∈（１，０），文档是本类时取１，反之为０，η是学习速率，本文优化后取０．２５。相似度计算公式如下：
ＧＱｓｉｍ（Ｇ，Ｑ）＝
#其中Ｇ是样本网页集的中心向量，Ｑ指网页向量。采集过程中，通过Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器对采集网页分类打分，把从此网页中解析出来的ＵＲＬｓ赋予网页相同分值并且插入到按分值排序的待爬行队列中。程序的伪码如下：
ＴｏｐｉｃＦｉｒｓｔ（ｓｅｅｄ＿ｕｒｌｓ）｛
ｓｅｅｄ＿ｕｒｌｓ）｛ｆｏｒｅａｃｈｕｒｌ（
ｅｎｑｕｅｕｅ（ｆｒｏｎｔｉｅｒ，ｕｒｌ）；｝
ｗｈｉｌｅ（ｆｒｏｎｔｉｅｒ＿ｓｉｚｅ＞０）｛ｕｒｌ：＝ｄｅｑｕｅｕｅ＿ｕｒｌ＿ｗｉｔｈ＿ｍａｘ＿ｓｃｏｒｅ（ｆｒｏｎｔｉｅｒ）；ｐａｇｅ：＝ｆｅｔｃｈ（ｕｒｌ）；ｓｃｏｒｅ：＝ｓｉｍ（ｐａｇｅ）；ｆｏｒｅａｃｈｏｕｔｌｉｎｋ（ｅｘｔｒａｃｔ＿ｌｉｎｋｓ（ｐａｇｅ））｛ｅｎｑｕｅｕｅ（ｆｒｏｎｔｉｅｒ，ｏｕｔｌｉｎｋ，ｓｃｏｒｅ）；｝｝｝
Ｔ
获取链向某页面的ＵＲＬｓ，即Ｉｎｌｉｎｋｓ等功能。本文就是通过对各个目标ＵＲＬｓ为参数迭代调用ＩｎｌｉｎｋｓＡＰＩ来选取种子ＵＲＬｓ。迭代调用的次数可以看成种子到目标之间的距离。最后为每个目标选取相应的一个种子，并且保证从种子到目标的通路没有坏链接。
实验中选取了５０个目标ＵＲＬｓ，并且调用ＧｏｏｇｌｅＡＰＩ获得５０个种子ＵＲＬｓ。种子到目标的距离是３，即对每个目标ＵＲＬｓ迭代调用了３次。
图１表示了采用Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的化学主题爬虫Ｔｏｐｉｃ－Ｆｉｒｓｔ）和以广度优先（Ｂｒｅａｔｈ－Ｆｉｒｓｔ）爬虫的爬准率曲线。（
从图中也可以看出，在整个爬行过程中，采用了Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的主题爬虫在爬准率上明显优于广度优先爬虫。
图２则对比了采用Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的化学主题爬虫（Ｔｏｐｉｃ－Ｆｉｒｓｔ）和以广度优先爬虫（Ｂｒｅａｔｈ－Ｆｉｒｓｔ）的爬全率。
３结果和分析
Ｍｅｎｃｚｅ等提出［５］用于评价主题网络爬虫系统的指标同传
统信息检索一样主要有两个：（１）爬准率（Ｐｒｅｃｉｓｉｏｎ）；（２）爬全率（Ｒｅｃａｌｌ）。定义分别如下：
Ｐｒｅｃｉｓｉｏｎ＝采集的目标页面数
Ｒｅｃａｌｌ＝采集的目标页面数
为了便于进行评价，我们预先设定一些种子页面（ＵＲＬｓ）和目标页面（ＵＲＬｓ）。除了利用ＣｈＩＮ上搜集的部分资源作为化学主题的训练样本网页集外，另外选取一些和训练样本网页不重叠的网页作为目标页面。Ｇｏｏｇｌｅ提供了一些基于ＳＯＡＰ和
图２中显示在各自爬行了５０００个页面后，主题爬虫的爬
全率达到４８％，而以广度优先爬虫只有１０％左右。
从上面分析可以看出，采用Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的主题爬虫不管是爬准率还是爬全率上都明显的优于广度优先的爬虫。这也说明利用化学主题爬虫可以明显提高页面采集的质量和效率。
４结论
本文利用ＣｈＩＮ网站上通过人工搜集积累的化学资源作为训练样本网页集和目标页面。通过实验对比评价了化学主题爬虫和广度优先爬虫。实验结果表明拥有Ｗｉｄｒｏｗ－Ｈｏｆｆ分类器的主题爬虫不管在爬准率还是在爬全率上都明显地优于广度优先爬虫，这也说明化学主题网络爬虫能有效地采集化学主题相关的网页。今后工作我们将进一步利用其他一些分类器如，ＮａｉｖｅＢａｙｅｓ，支持向量机（ＳＶＭ）等来构建主题爬虫。（收稿日期：２００５年６月）
页）
３．１．２在网格环境中部署运行中心服务的节点
在网格开始使用之前，要首先对网格环境进行初始化，根据网格规模和地理位置人工地部署中心结点。然后随着网格规模的不断扩大或网格的实际运行需要，可以采用网格辅助人工部署中心的办法，也可以采用网格环境自动动态部署中心的办法来实现网格中心的在整个网格环境中的合理部署。
这就需要解决何时需要在网格中部署中心的问题。可以采用设定阈值的方法，该阈值表示了网格允许的资源匹配和任务调度的最低效率。对每一个任务的招标业务所用的时间占该任务的完成时间的比例（在此称为任务的招标消耗率）进行统计，将所有任务的招标消耗率进行平均，如果超过了初始设置的阈值，则表明整个网格花费在资源匹配和任务调度上的开销过多，需要在网格中部署新的中心，降低管理开销在整个网格开销中所占的比例。
设：ＢＴｉｊ（ＢｉｄｄｉｎｇＴｉｍｅ）为任务ｊ在中心ｉ进行招标所用的时间；ＡＴＣＴｊ（ＡｃｔｕａｌＴａｓｋＣｏｍｐｌｅｔｉｏｎＴｉｍｅ）为实际任务ｊ的完成时间；
ＢＣＲｉ（ＢｉｄｄｉｎｇＣｏｓｔＲａｔｅ）为中心ｉ的平均招标消耗率；ｎ为在中心ｉ招标的任务数；则：
ＢＴ! ｉｊ
ｊ＝１ｎ
工作，即将部分招投标业务由重载的中心迁移到轻载的中心去，从而实现快速的资源匹配，提高网格管理效率。解决网格环境中中心节点之间的负载平衡问题可以采用以下三种方法：
第一种方法是用户负责法。在用户招标时，通过用户综合考虑中心的所处的地理位置（用户和中心的网络状况）因素和中心当前的招标消耗率因素，选择一个最佳的中心委托其的招标业务。
第二种方法是中心负责法。事实上，由网格环境中所有的中心节点形成的网络，已经构成了一个专门负责招投标业务的分布式计算环境，因此，中心间的负载平衡问题是典型的分布式系统中负载平衡问题，由于在中心处理的每一个招投标业务都是功能统一、相互独立的任务，这使得负载平衡问题变得相对容易了。我们提出了一种基于任务压力的完全分布式的负载
［８］
平衡算法，在仿真中取得了理想的效果。中心负责的方法是对用户透明的。
第三种方法是用户———中心法。在实现中心的负载平衡策略中，第一和第二种方法同时使用，即首先通过用户选择轻载的中心，如仍然出现中心间负载不平衡时，由中心进一步地进行负载平衡工作。第三种方法同时具有用户负责法和中心负责法的优点，因而是好的方法。
４结论
（１）
本文提出基于资源提供者主动参与的竞标机制的网格资源匹配和任务调度方法，是一种分布式的和通用的方法，采用了与目前主要网格项目不同的资源匹配的方法。通过在网格中建立一个虚拟机构———招投标管理中心（一种在某些节点上运行的特殊网格服务），该中心作为用户和公司进行资源消费和资源提供协商的中介，来解决网格资源的多重管理、网格的资源的发现和匹配、网格任务的调度、提高网格可用性、和负载的平衡等问题。通过将网格管理任务进行划分，即资源的局部自治管理，网格的其他管理任务是通过虚拟机构实现快速的资源匹配和任务调度来实现对整个网格的管理。该分布的管理模式便于降低整个网格的管理开销占总网格开销的比例，能够实现不依靠扩大网格规模却能够得到由于网格规模的扩大带来的绝对性能的提高。（收稿日期：２００５年９月）
ＢＣＲｉ＝
ｊ
设：
ＢＣＲ（ＢｉｄｄｉｎｇＣｏｓｔＲａｔｅ）为网格环境的招标消耗率；ｍ为当前网格中中心的总数。则：
（２）
（１）采用人工的办法是：当网格招标消耗率ＢＣＲ大于初始设定的阈值时，网格环境发出报警，提示需要部署新的中心，并给出各个中心对应的ＢＣＲｉ的变化图。可以人工选择节点作为中心，为其安装并运行中心的系统软件，使其成为中心。中心的系统软件在初始化时具有向网格环境通知本中心成立的功能。
（２）采用网格环境自动动态部署的方法是：当网格招标消耗率ＢＣＲ大于初始设定的阈值时，初始化时部署的中心（在此称为父中心）根据地理位置和可信度等因素与其他网格结点进行协商，选择合适的节点，将中心的招标处理系统软件下载并安装到该结点，该节点运行系统，成为中心（在此称为子中心）。网格环境自动动态部署中心的方法具有网格环境的动态自适应特点，当ＢＣＲ小于初始设定的阈值时，父中心可以动态地停止部分由它部署的子中心的工作，当ＢＣＲ大于初始设定的阈值时，又可以开始子中心的工作。
ＢＣＲ＝
! ＢＣＲ
ｉ＝１
ｍ
ｉ
参考文献
１．［美］ＩａｎＦｏｓｔｅｒ，ＣａｒｌＫｅｓｓｅｌｍａｎ编著．金海，袁平鹏，石柯译．网格计算［Ｍ］．
第二版，北京：电子工业出版社，２００４－１０２．ｈｔｔｐ：／／ｗｗｗ．ｇｌｏｂｕｓｅ．ｏｒｇ
３．ＴｈｅＤａｔａＧｒｉｄＰｒｏｊｅｃｔ．ｈｔｔｐ：／／ｗｗｗ．ｄａｔａ．ｃｎｒ．ｉｔ４．ｈｔｔｐ：／／ｗｗｗ．ｃａｃｔｕｓｃｏｄｅ．ｏｒｇ５．ｈｔｔｐ：／／ｗｗｗ．ｃａｃｒ．ｃａｌｔｅｃｈ．ｅｄｕ／ＳＦＥｘｐｒｅｓｓ６．ｈｔｔｐ：／／ｗｗｗ－ｉｔｇ．ｌｂｌ．ｇｏｖ／ｎｇｉ／７．ＫＣｚａｊｋｏｗｓｋｉ，ＳＦｉｔｚｇｅｒａｌｄ，ＩＦｏｓｔｅｒｅｔａｌ．ＣｒｉｄＩｎｆｏｒｍａｔｉｏｎＳｅｒｖｉｃｅｓｆｏｒＤｉｓｔｒｉｂｕｔｅｄＲｅｓｏｕｒｃｅＳｈａｒｉｎｇ［Ｃ］．Ｉｎ：ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＴｅｎｔｈＩＥＥＥ３ｒｄＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍｏｎＨｉｇｈ－ＰｅｒｆｏｒｍａｎｃｅＤｉｓｔｒｉｂｕｔｅｄＣｏｍ－ｐｕｔｉｎｇ（ＨＰＤＣ－１０），ＩＥＥＥＰｒｅｓｓ，２００１－０８８．赵宏，杨愚鲁．一种完全分布的网格任务调度算法［Ｊ］．计算机工程与应用，２００５；４１（１３）：１７～１９，３１２００５－０５３．李晓霞，杨章远，许志宏等．Ｉｎｔｅｒｎｅｔ化学资源的发展状况与展望［Ｊ］．计算机和应用化学，１９９９；５：３２５～３２６４．ＤＤＬｅｗｉｓ，ＲＥｃｈａｐｉｒｅ，ＪＰＣａｌｌａｎｅｔａｌ．Ｔｒａｉｎｉｎｇａｌｇｏｒｉｔｈｍｓｆｏｒｌｉｎｅａｒｔｅｘｔｃｌａｓｓｉｆｉｃａｔｉｏｎｓ［Ｃ］．Ｉｎ：ＰｒｏｃＡＣＭＳＩＧＩＲ，１９９６５．ＦＭｅｎｃｚｅｒ，ＧＰａｎｔ，ＭＲｕｉｚｅｔａｌ．Ｅｖａｌｕａｔｉｎｇｔｏｐｉｃ－ｄｒｉｖｅｎｗｅｂｃｒａｗｌｅｒｓ［Ｃ］．２００１３．２中心的负载平衡技术
在网格环境中心节点间的业务量出现不平衡时，即个别中
心招标的业务过多，但网格整体的招标消耗还没有达到必须在网格中部署新的中心的警戒阈值时，由于中心节点间负载的不平衡，会影响整个网格的效率，需要在中心之间进行负载平衡（上接２０５页）
参考文献
１．ＵｎｉｖｅｒｓｉｔｙｏｆＬｉｖｅｒｐｏｏｌ．ＬｉｎｋｓｆｏｒＣｈｅｍｉｓｔｓ．ｈｔｔｐ：／／ｗｗｗ．ｌｉｖ．ａｃ．ｕｋ／Ｃｈｅｍｉｓｔｒｙ／Ｌｉｎｋｓ／ｌｉｎｋｓ．ｈｔｍｌ，２００５－０５
／