用一种数据挖掘的方法来解决网络拥挤的问题

用一种数据挖掘的方法来解决网络拥挤的问题

摘要

随着互联网的迅速发展，上网的人越来越多，网络也越来越拥挤，很多时候，人们坐在电脑前面等着页面下载。如果我们能够确定一些典型的进入模式的话，网站服务器就可以把一些用户可能要的东西预先发到用户的浏览器里或者是代理服务器上。在这篇文章里，我们提出这种预先存储的概念，那么什么样的网页是用户最有可能想看的，也就是需要预先发送的呢？这个就需要根据一些从Web日志中得到的关联规则来决定了，比如有这样一个规则“A�>B”已经被确认了，那么假如某用户向服务器请求看A 网页，我们就考虑B是否要发给用户。


引言：

每个互联网用户在上网的时候总要化费一段时间来等待网页被下载到本地来，许多作

者都曾考虑过用服务器预先存储的方法来解决下载缓慢的问题。实际上，通过研究Web log，

Web Agent,每个用户的进入模式都是可以预料的。也就是说，我们可以将一些网页预先放

在用户端，省去了用户再次请求时再重新下载的麻烦与延迟。

在这篇文章里，我们利用关联规则来实现预先存储，其中哪个网页该预先被放到客户

端由我们得到的关联规则来决定。


我们使用的方法：


从进入Log里面来挖掘关联规则。

进入日志一些记录组成的，它记录包括哪部分（被请求浏览的URLs）被谁（由IP地址决定）请求浏览的情况。我们用“Session”的概念来表示一个用户在一段时间内访问某个网站的网页的有序集合。我们可以根据某段时间内（比如一天，一周）的所有“Session”，得到一些规则，例如Di�>Dj，这儿Di,Dj都是（URLs）。对于这个规则的理解是如果当Di被请求了以后，过了一段时间很可能Dj 就会被请求，因为历史情况记录的是如此。这条规则的有效性可以用“可信度”来衡量，“可信度”的意义就是如果Di被浏览了，那么Dj被浏览的可能是多少。可信度可以用Support(Di…Dj)/support(Di)来计算，Support(Di )表示所有Session里面含有Di的概率，

support(Di…Dj)表示所有Session里含有Di…Dj这一序列的概率。首先，我们找到所有支持度大于某一个门限值的网页D，我们只对浏览这些网页利用关联规则预存取。然后，再计算所得的的关联规则可信度，我们只取可信度大于某个门限值的规则。


实现服务器预存取。

通过上面的步骤，我们可以得到一些规则，下面我们来了解一下怎么来利用这些规

则。当一个用户请求浏览Di网页的时候，如果有规则Di�>Dj存在，这儿的Dj可以

有很多个，我们只选择可信度最大的那个Dj，这其中的道理是可以理解的。那么，也

就是说，对于每一个Di，我们只保留可信度最大的那个规则。预存取的意思是在用户

没有请求Dj的情况下，如果有规则Di�>Dj，那么我们可以预料Dj会被请求，于是

我们可以在用户请求 Di以后，将Dj发送给用户端。那么当用户再请求Dj的时候，Dj

很快就会得到了，他就可以发现“网速”变快了。

这个方法也可以“循环”使用。如果同时也有规则Dj�>Dk（有最大的可信度）存

在，那么我们可以把Dk与Dj也同时发送给用户，根据同样的规则也就可以以此类推

了。我们这种方法有个参数叫做“存取长度”，它定义了与Di同时发送给用户的网页

的最多个数，如果为0就表示是没有采用这种方法的标准的传输协议。如果存取长度

定义得很大的话，就会造成过大的带宽消耗，从而引起流量的增加，使得服务器的负

担加重。

服务器流量的增加除了与取的网页的个数有关，还与网页的的大小有关，因此我们

在这儿应该考虑网页大小的因素相对应地我们提出第二种策略叫做“网页重量”的概

念。在第一步考虑取哪个网页的时候,我们就不仅仅考虑可信度的大小，而将它与网页

的大小综合起来考虑。在这儿我们提出一个函数f(C,S) =C/S,其中C代表可信度，S代

表网页重量。对于每一个符合Di�>Dj的Dj我们计算它的F(C,S)来决定该选取哪些网

页放到用户端。通过这个函数我们可以看出，当可信度增大的时候，那个网页也就越

有可能被选中的，当网页的“重量”增大的时候，其被选中的概率也就减小了，因为

“重量”越大，越会给服务器带来越大的负担。


运行的环境。

我们考虑三种不同的情况：

第一种：我们假定客户端是本地缓存被部分禁用的Web Browser，这样的情况我们仍然可以用上面的方法来实现网页预存取。

第二种：我们考虑这样一个事实，就是先前浏览过的网页仍然保存在用户浏览器的缓存里面，我们假定这些网页和需要预存取的网页都能够被保存在缓存里（缓存足够大），这样我们就不用考虑需要覆盖的情况了。

第三种：我们考虑客户是通过代理服务器登陆到网站的，在这儿我们仍然相信服务器的缓存是足够大的，我们假定100个用户共用一个代理服务器。在这儿与上述两种情况不同的是一个用户所浏览的网页和预存取的网页都放在代理服务器的缓存里面，也都能够被其他的用户所利用。

下面，对于这三种情况我们我们分别用上面提到的两种方法来进行实验。第一种方法，我们根据最大可信度和得到的关联规则来决定预存取的网页。第二种我们则采用可信度与网页重量结合起来考虑的方法来做。这儿我们就采用上面讲的函数。