天天看点

数学之美:搜索引擎的反作弊问题

最早作弊手段是重复罗列关键词。后来随着PageRank算法出现后,又出现专门买卖链接的作弊手段。搜索反作弊的方法也分成两种境界:术和道。术的方法就是分析作弊案例,找出规律,然后清除它;道则是透过作弊问题,追本溯源找到作弊动机和本质,从本质上解决问题。

搜索引擎作弊的本质是人为的对搜索排序算法的信息加入噪声。一种解决办法是提高算法的抗噪声能力;另一种则是像通信原理中一样除去噪声,还原本来排名。如果在发动机很吵的汽车里打电话,对方会听不清,但如果捕获发动机频率,叠加一个频率相同,幅度相反的信号,则会很容易消除噪声影响。搜索引擎中的作弊者可以理解成人为的加入噪声,这种噪声通过一定时间的统计,就能分析出规律。从广义上讲只要噪声不是完全随机并且前后有相关性,就可以检测并消除。但如果是随机不相关的高斯白噪音就很难消除了。

从动机上讲,作弊者无法想要提高搜索排名。因此针对商业相关搜索,就是用一套抗干扰强的算法,就如同在高噪音环境下采用抗干扰麦克风一样;对信息类搜索,就采用敏感算法,如同在安静环境下采用敏感麦克风一样。而且如果是买卖链接的网站,其出链数目可以作为一个向量作为网站固有特征;通过计算余弦距离,会发现有些网站的出链向量之间余弦距离几乎为1,这通常是一个人建立的。

反作弊另一个工具就是图论,作弊网站通常需要两两互联,这就形成了图论中的Clique。图论中有专门算法发现Clique。