对判定网页爬虫算法的一点思考
判断网页蜘蛛最简单的一个办法就是设置一个时间段, 然后记录这个时间段内来自某个源的点击数, 再计算其点击频率, 如果点击频率很高, 则认为它是一个爬虫, 反之则是正常访问. 这种做法的缺陷在于:什么样的阈值才算是爬虫的标准呢? 10秒内点击12次, 还是5秒内点击6次? 而且, 对于那些一次性打开多个并发请求的爬虫类型来说(比如突然来个20并发请求的burst), 这个方法可以说是很有效, 但是对于那些周期性的请求爬虫来说(比如每隔1秒请求一个页面), 这种算法就完全失效了, 所以你网站上的信息还是在不知不觉中流失.
对于周期性请求的爬虫, 也有数学方法可以判断, 那就是将每次请求的间隔记录成数组X[ n ], 对这个数组求其方差, 如果方差很小, 那么就可以判断这是一个周期性请求的爬虫, 这又引出了最初的问题, 多大的方差阈值才是爬虫标准?
那么再进一步, 周期性是一种数字的定性规律, 而不是由方差可以定量衡量的. 因为爬虫访问服务器是有规律的, 即频繁且具有一定的周期性, 如果说正常的人类点击可以看成随机分布的话, 那么爬虫的访问数据模型则可以用近似均匀分布来描述. 所以我们可以对请求时间间隔数组X[ n ]求其数学期望e(其实就是均值), 构造另一个数组{Y[ i ] = sum(X[ i : n ]), (i = 0, 1, 2, 3...n)}, 即Y[ i ]为X[ 0 ]到X[ i ]的累加, 再对Y[ n ]和{Z[ i ] = e * i, (i = 0,1,2,3...n)}数组做一元线性回归分析, 对于爬虫来说, 由于X[ n ]接近均匀分布, 那么Z[ i ] = i * e将很有可能约等于Y[ i ], 也就是说Y[ n ]与Z[ n ]数组是线性相关的, 而对于人类点击来说, X[ n ]则更有可能近似于随机分布, 那么Y[ n ]与Z[ n ]则不应该具有线性相关的性质, 基于以上数学基础, 我们通过判断Y[ n ]与Z[ n ]数组是否线性相关, 就可以判断访问是否是爬虫的点击, 即如果得到的直线斜率越接近1 == tan(45'), 则说明其具有周期性规律, 反之则不然. 之所以将回归直线构造到斜率为一的附近, 是根据tan(x)函数的性质, 因为它在离靠近0'时增长缓慢, 而靠近90'时又增长过快, 都不利于性质判定.
下面是我根据上述方法对两个真实iis log记录进行分析的结果(各取300次点击记录, 单位为秒):
图一: ip为222.41.178.219的人类访问记录散点图, x轴为时间线, y轴为两次访问的timespan间隔
图二: 根据上述算法的到的散点图, x轴为Z[ n ]数组, y轴为Y[ n ]数组, 很明显, 他们不具有线性相关的关系
图三: baiduspider的爬虫访问记录散点图, x轴为时间线, y轴为两次访问的timespan间隔(貌似有点规律 :) )
图四: 根据上述算法的到的散点图, x轴为Z[ n ]数组, y轴为Y[ n ]数组, 很显然, 他们具有线性相关的关系
分析: 两组数据都为300次点击的记录, 单位为秒, 其中人类的访问具有一个很明显的特征, 就是会有许多同时的并发访问, 这是因为, 当人类的浏览器载入一个网页时, 它会同时请求这个网页上的所有图片, 脚本和多媒体, activeX插件文件等, 表现在[图一]中, 就是许多timespan都等于0. 而爬虫由于只需要爬网页内容, 所以他们并不需要访问网页上的图片, 而是遍历网页上的所有超链接来进一步爬整个网站! 从matlab画出来的图看, 我提出的这个线性回归分析算法看上去还是相当有效的说, ^_^
Crawler analysis第一阶段实验数据(实验数据, 包含两个真实的log文件, 感兴趣可以拿去玩玩!)
posted on 2007-05-14 15:22:00 by cy 评论(19) 阅读(8071)