【doc】 搜索引擎中基于Bayes分类的网页更新研究

【doc】 搜索引擎中基于Bayes分类的网页更新研究 搜索引擎中基于Bayes分类的网页更新研究 搜索引擎中基于Bayes分类的网页更新研究——赵新慧63 搜索引擎中基于Bayes分类的网页更新研究 赵新慧 (辽宁石油化工大学抚顺113001) 摘要在网络无限扩张的同时,网页也在频繁地变化,搜索引擎往往要定期更新它所检索 的网页,需耗费大量时间和系统资源,因此提高更新效率是搜索引擎技术的关键.文章比较了目前 存在的两种更新方法:统一更新方法和个体更新方法,指出两种方法优劣所在,提出一种改进的基 于Bayes分类的网页更新方法. 关键词搜索引擎;更新度;更新策略 中图分类号:TP391文献标识码:A Abstract:TheWebishugeandtheWebpagesareupdatedfrequently.Theindex maintained byasearchenginehastorefreshWebpagesperiodically.Thisisextremelytime andresource consumingbecausethesearchengineneedstocrawltheWebanddownloadW ebpagestorefresh itsindex.Therefore,improvingtherefreshefficiencyisthekeytechnologyoft hesearchengine. Thispapercomparesuniformrefreshpolicyandproportionalrefreshpolicy,a ndpointsouttheir advantagesanddisadvantages.Finally,thispaperpresentsareformedmethod calledclassified refreshpolicybasedonBayesTheory. Keywords:searchengine;freshness;refreshpolicy 0引言 随着网络的发展,信息源增加,但有时阻碍了 有用信息的传递交流,利用搜索引擎技术可解决 这一问题?.搜索引擎依靠机器人(crawler)浏 览Web网,Crawler被给定URL开始集,并从网 络中检索这些网页.Crawler提取被检索网页中 出现的URI,继续进行本地索引,直到没有新的 URL出现.Crawler保存检索过的网页,形成一 个大型的本地网页库. 网上的信息资源不断变化,Crawler需不断 更新它所访问过的网页.而不同的网页其改变速 度也不相同,因此,Crawler必须判断访问哪些网 页,用怎样的频率去访问,这些决定都会影响被检 图5基于电子商务的信息组织与集成模式 物,发展现代物流业离不开完善的信息系统的支 持,在规范物流运作的基础上,加快信息化建设的 步伐,实现物流业务的网上及时跟踪和查询,网上 交易和资源配置等,提高企业的服务水平和对客 户以及市场的快速反应能力成为信息技术进入物 流业的切入点.通过采用电子商务方式,企业能从 收稿日期:2005—04—21 供应链整合中更快,更有效地获得大量利益点一 减少成本,增加灵活性,提高反应速度.在未来的 几年里,我们将会看到,那些利用电子商务重新定 义供应链整合的公司会大幅度提高效率和获得比 它们的竞争对手更强的竞争优势. 参考文献 1李必强,胡浩.集成化供应链与供应链管理.武汉理 工大学,2003,25(6):101,104 2乌云高娃.一种数据库中间件的设计与实现.计算机 应用与软件,2004,25(4):27,28 3饶卫进,李振武,白彩英.网络性能参数的测量方法及 实现.计算机应用与软件,2004,25(4):55,56 4薛华成.信息资源管理.北京:高等教育出版社,2002. 76,85 交通与计算机2005年第5期第23卷(总第126期) 索网页集合的更新度.由于系统资源有限, Crawler只能下载并更新有限的网页集合,网页 更新方法在很大程度上决定了网页更新的效果. 1网页更新的基本概念 1.1更新度 一 旦Crawler检索了某些重要的网页,它就 要定期地更新这些页面.下面将定义更新度及网 页”年龄”的概念. C一{尸一,)是张网页的本地集合,本地 网页尸在t时刻的更新度为[3] U(Pi)一f,如果在时刻更新(1) 10,否则. 更新是指本地网页中的内容等于真实世界中 网页的内容,于是,本地集合C在t时刻的更新度 为 (C)一((尸)+…+U(尸))/n一 耋… 事实上,更新度就是本地集合中更新过的页 面占集合中总页面的百分比. 1.2网页更新方法 目前,网页更新方法]可归为以下两类,不同 的更新方法会得到不同的更新结果. 1)统一更新方法.Crawler以相同频率厂访 问所有网页,不考虑网页的改变频率. 2)个体更新方法.不同网页其改变频率也不 同,Crawler根据个体页面的改变频率来重访各 页面,网页的改变频率与访问频率的比率对任何 个体网页来说都是相等的. 使用统一更新方法,Crawler每隔一段时间 从头开始重新搜索一遍整个因特网,对先前保存 在网页库中的所有网页进行一遍更新.这种方式 对程序的效率和硬件设备要求很高,而且对某些 网页更新不及时,不能有目的地爬行某些重要网 页.对于个体更新方法(在网络容量过大的情况 下,系统无法实现个体更新方法),实际应用中采 用Crawler每次有目的地爬行更新部分网页,而 不是对所有网页库中网页重新爬行一遍.这种方 式能提高搜索引擎的效率,提高网页库的新鲜度, 但会使网页库中存在许多非常陈旧的网页. 2基于Bayes分类的网页更新 单纯使用统一更新方法或个体更新方法,其 结果均难令人满意,因此,在统一更新方法和个体 更新方法的基础上提出一种改进方案,在此称之 为基于Bayes分类的网页更新方法. 2.1基本思想 通过网页的历史改变来评估其改变频率,将 网页分为两类:更新较快网页子集和更新较慢网 页子集,然后以不同的频率访问这两类网页,这就 是分类更新的基本思想.如在实际应用中, Crawler除了每月统一更新所有网页之外,同时 每星期还更新1次改变频率较大的网页子集.具 体实现方法如下: 为了说明方便,假设把网页分成两类(两类以 上类似):?1周更新1次的(c);?1月更新1 次的(C).对于每个网页,保存两个可能性值P {?C)(属于C类的可能性)和尸{?C) (属于C类的可能性).最开始时,可以设置这 两个可能性值相等并取为o.5,然后随着定期对网 页进行访问,根据访问时网页是否发生了变化来 更新这两个可能性值.最终,如果尸{WEC)>尸 {?C),那么认为网页属于C类,反之,网 页属于C类. 假设每5天对网页进行1次检查,若第1次检 查时网页发生了变化,则应该修正尸{?C}和尸 {?C).直观上应该增大尸{?C),减小 尸{?C),因为网页在1周内发生了变化.具体 增减方法为,可以用Bayes公式来处理,设E表示 检查时发现网页发生变化这一事件,现在就是求 P{?ClE)和P{?ClE},根据Bayes公式 有 P{u,?C.IE}= !I垦!!垦 P{EIu,?C,)P{u,?)+P{Elu,?C}P{W?cm) (3) 式中:尸{EI?C)和尸{EI?C)可以在泊松 分布模型(由于网页的改变是随机并彼此独立的, 因此服从泊松分布)下算出.在泊松分布模型下, 两次事件的时间间隔服从指数分布,所以可以得 到在时间间隔(O,,)内发生变化的概率 尸{丁?t)一le一dt一1一e一(4) J0 所以有 尸{?CIE)一 丽丽?n7705e-S/05es/05. (1一).+(1一一..)., 搜索引擎中基于Bayes分类的网页更新研究——赵新慧65 P{?ClE}一 ?o.23051 es/7051e--5/305. (,一).+(一)0., 即属于C的概率是0.77,而属于C的概 率是0.23,如果5天之后又到发生了变化, 再用式(3),不过这次P{?C}一0.77,P{W? c)一0.23.通过计算,这时,P{?C)增加到了 0.92,P{W6C}降到了0.08.同理,如果检测到 没有发生变化,也就是E没有发生,那么就计 算尸{?Cl}和P{?ClE}来更新P{ ?C}和P{?C}. 下面讨论这种分类法的准确度.图1所示为 用这种分类法,在每20d检查1次的情况下,不同 变化率的网页在不同的检查次数下被归人c的 可能性. 图1Bayes分类法的准确性 从图1中可以看出,当?1/月时,只需访问3 次,把归入C类的可能性就超过76,访问7 次时,超过86.另外,当?1/周时,只需访问3 次,把归入C类的可能性大约是81(P{W? C}?19),访问7次时,大约是93(P{? C}?79/5).可见这种分类法是比较准确的,而且 随着检查次数的增加,结果会更准确. 2.2检查周期的确定 在Bayes分类法中选取怎样的检查周期会得 到更精确的结果,为了解答这个问题,通过计算当 访问次数为3时,在不同的检查周期下,不同变化 周期的网页被归人C类的概率,结果如表1所 列. 由表1可以看出,当访问周期为15d时,变化 周期为30d的网页被归人C类的可能性最大,当 访问周期为19d时,变化周期为7d的网页被归 表1在不同的检查周期下不同变化周期的网页 被归入C类的概率(访问次数为3时) 分类更新方法结合统一更新方法和个体更新 方法的优点,不会将系统资源耗费在过度更新改 变过于频繁的网页上,也不会过多访问改变换慢 的网页,而是均衡的分配系统资源.实际上,分类 更新方法的基本思想可以继续扩展,在实际应用 中,网络容量日益膨胀,网页改变速度各不相同, 统一更新方法不能适应用户对信息更新度的要 求,因此,可以根据网页的改变速度把网络化分为 不同子集,再根据各子集的改变频率来更新网页 集合,以满足用户对某些网页集合的特殊要求. 参考文献 1宋聚平,王永成,尹中航,等.面向主题的网页搜索系 统.上海交通大学,2003,37(3):401,403 2张领,叶允明.一种高性能分布式WEBCRAWLER 的设计与实现.上海交通大学,2004,38(1):59, 61 3ChoJ,GarciaMolinaH.Synchronizingadatabaseto improvefreshness.In:Proc.of2000ACMInt1.Conf. onManagementofdata(Slgmod)conf.Dallas,Texas, UnitedStates,2000,1l7,128 4ArasuA,ChoJ,GarciaMolinaH,eta1.Searchingthe web.ACMTrans.onInternetTechnology,2001,1 (1):2,43 49494175一可【.8899O112一i.nOOOO1111一 ????????_?!『0OOOOOOOO一, O815O478一一欠. ,一一,,,,,一一一,22211111一-e 一.r(????????_:6}OOOOOOOO一/.?COO4831O3一l_’3468147O一 喇;.18766544一.,,,一,,,,一,一一一6OO98641一?_1一 HI一57766666一l,打一矗77777777一.r,????????i{,一一一一一一 一一一锹釉雌12729O45一:!l-13713678一有I1#IJ?7OO11111一『_v 五亡89999999一百:.I}1日??????????,:??一一一,一一一一一一 一,一撕一人生M”.l扪