Search Engine News Review (May. 11 – May 17, 2010) 后谷歌时代的中国搜索市场 在中国，我们继续维护着所建立的商业关系， 开发中心也在继续运营 Eric Schmidt, Google CEO
Search Engine News Review (May. 11 – May 17, 2010) 搜索引擎流量引导 在市场份额不断流失长达一年之久后，雅虎在美国搜索市场的份额终于有所回升，从3月的%增长至4月份的% 由于添加了这项新的自动搜索功能，雅虎新闻带来的搜索次数从之前的仅仅1700万上升至亿次。
―搜索引擎技术基础”课程讲义 去伪存真：互联网垃圾页面 及垃圾页面识别技术 (下) 对垃圾信息的处理能力，是搜索引擎的核心竞争力。 如果搜索引擎不能打赢与垃圾信息的这场技术战争， 搜索产业就会被垃圾信息摧毁。 —— 百度公司应对“全民医药网”反垄断诉状的声明 刘奕群 清华大学计算机系 智能技术与系统国家重点实验室 2010/05/11 — 2010/05/18
什么是垃圾页面 •垃圾页面的定义 –Web spam are designed to get ―an unjustifiably favorable relevance or importance score‖ from search engines. (Gyongyi et. al. 2005) –垃圾页面是那些通过不正当的手段获取搜索引擎中不应有的较高排名的网页
垃圾网页制作者的自白 •关于垃圾网站如何搞钱这件事 –Zz from 不 是每个人都可以有精力有能力以及有机会做成一个不错的 并能赚到钱的正规网站的。 大部分人都是想着有什么短平快的项目能马上赚到钱 只要能赚钱的东西就是好东西，管他什么垃圾不垃圾的。 有人在网上出售一种“网站SEO生成工具”， 就是通过关键词自动从网上抓取内容来生成网站的程序 生成的速度非常快基本是十分钟一个垃圾站。 所以毫不犹豫马上花几百个大元买了一个带收集功能的群发软件， 自己收集群发地址，然后再去群发。 效果果真是立竿见影，收录速度和数量大幅增加。
垃圾网页制作者的自白 •关于垃圾网站如何搞钱这件事 –Zz from 第一 种方法，就是直接在垃圾站上放臵广告， 把以前SP的代码放到网站里然后从百度把相关的人抢到我的站来定制SP业务。 当然了广告不止这个，还有其他很多，比如弹窗什么的， 或者你有本事的话也可以直接用垃圾站做GOOGLE的广告。 第二种就是把搞来的流量用301直接跳转到其他网站上去 第三种嘛就是放“马”了！ 如做娱乐类型的垃圾站那么IP的价值就相对较低，1万IP给30元-50元就是不错了。 如果是QQ类的站那么1万IP给到80-100元属于正常 至于游戏类的网站，那么价格就要高的多了1万IP在100-200元之间都是可以的。
提要 •垃圾页面的定义 •垃圾页面的分类体系 •垃圾页面识别技术 –垃圾页面识别的效果评价 –基于网页内容的垃圾页面识别 –基于链接关系分析的垃圾页面识别 –基于用户行为特性的垃圾页面识别
基于网页内容的垃圾页面识别 •堆砌关键词类别 (Keyword Farm) 热门内容比例 可见内容比例 关键词压缩比
基于网页内容的垃圾页面识别 •关键词插入与替换 (Keyword Weaving) 语言模型方法
基于网页内容的垃圾页面识别 •作弊内容隐藏型垃圾网页的识别 –作弊内容隐藏： 使用某些基本的作弊方式（如关键词堆砌、关键词替换/插入）引导用户进行对垃圾网页的访问，但实际呈现给用户的网页内容中则尽量避免出现作弊内容。 –吸引用户与作弊页面进行交互 –服务器端页面内容替换 (cloaking) –重定向跳转 (redirecting) –脚本与页面浮动框架隐藏 (script/iframe hiding)
基于网页内容的垃圾页面识别 •服务器端页面内容替换HTTP head (cloaking) –为搜索引擎和用户提供不同内容 –“变色龙” –利用http协议的UserAgent内容 HTTP content
基于网页内容的垃圾页面识别 •服务器端页面内容替换 (Cloaking) 百度快照 原始网页 识别方式：多次抓取，以不同的spider身份抓取，验证不同副本之间的相似度
基于网页内容的垃圾页面识别 •重定向跳转(Redirection) 直接重定向 拼凑字符串构建重定向
基于网页内容的垃圾页面识别 •重定向跳转(Redirection) 编码字符串构建重定向 识别方式：解析Javascript
基于网页内容的垃圾页面识别 •脚本与页面浮动框架隐藏 (script/iframe hiding) 隐藏广告 识别方式：分析页面主体内容是否被其他正资文内容 源内容所遮盖
基于网页内容的垃圾页面识别 •作弊方法众多 –关键词堆砌、关键词插入/替换 –作弊内容隐藏 •见招拆招？ –只能针对某种特定的作弊方式 –时效性难以保证 •寻找其他的反作弊手段
垃圾页面识别技术 •垃圾页面识别的效果评价 •基于网页内容的垃圾页面识别 •基于链接关系分析的垃圾页面识别 •基于用户行为特性的垃圾页面识别
基于链接关系分析的垃圾页面识别 •互联网超链接分析回顾 超链接 <a href="/qhdwzy/"> <img src="/cic_jsp/qhdwzy/index_images/" alt="" width="85" height="39" border="0"></a> 锚信息
基于链接关系分析的垃圾页面识别 •互联网超链接分析回顾 –超链接的内容推荐特性： 页面A链接到页面B，则说明页面A的作者推荐页面B的内容 Recommendation A B
基于链接关系分析的垃圾页面识别 •互联网超链接分析回顾 –超链接的主题相关特性： 页面A链接到页面B，则说明页面A的主题与页面B的主题相关 Topic locality A B
基于链接关系分析的垃圾页面识别 •互联网超链接分析回顾 –PageRank r(q)1r(p)(1 ∆) ƒ ∆ q:(q,p) Eoutdegree(q)N用户点击页面的从指向p的页面获得随机访问 链接以继续其浏的PageRank值 某一页面的概率 览过程的概率 可以根据先验知识 进行估计
基于链接关系分析的垃圾页面识别 •TrustRank算法 –Zoltán Gyöngyi •Graduated from Stanford University •Professor: Hector Garcia-Molina ACM Fellow, Member of the National Academy of Engineering •PHD: 2004 – 2007, Intern in Google & Yahoo! •A number of important articles in Web spam fighting –Web Spam Taxonomy –Combating Web Spam with TrustRank •Research scientist at Google
基于链接关系分析的垃圾页面识别 •TrustRank算法 –目标：计算页面p的“可信度”(Trust Score) –思路： 1.选取确定种子集合，并为种子集合赋以相应的信任度得分 2.从种子集合出发进行信任度 得分的扩散 (垃圾页面有可能链接到好页面) (好页面很少链接到垃圾页面) 3.将Trust得分较低的网页识别为垃圾网页
基于链接关系分析的垃圾页面识别 •TrustRank算法 –种子站点选取 •高PageRank站点 (利用T计算) –强调内容权威度：门户网站、政府网站等 –保证Trust扩散的准确性 •高Reverse PageRank数目站点 (利用U计算) –强调链接权威度：网页目录、专题首页等 –保证Trust扩散的效率 •手工筛选过滤 –避免个别站点造成不良影响： 搜索引擎，站点等
基于链接关系分析的垃圾页面识别 •TrustRank算法 –Trust扩散(Trust Propagation) 1 2 3 4 5 6 7 M=0 1 1 0 M=1 1 1 1 0 M=2 1 1 1 1 0 M=3 1 1 1 1 1 0 1 2 3 个别链接导致4 扩散产生错误 5 6 7
基于链接关系分析的垃圾页面识别 •TrustRank算法 –Trust扩散的衰减(Trust Attenuation) •质量最高的站点基本不会链接到垃圾网页 •质量一般的网页则不能确定是否会连接到垃圾网页 •Trust值的扩散，需要伴随着衰减过程 ββ2 11β36 β2 1 2 3 11136 2 3 β 13衰减因子(dampening) 信任分割(splitting)
基于链接关系分析的垃圾页面识别 •TrustRank算法 –算法输入: •G 万维网链接结构图 •N 链接结构图中包含的页面数量 •L 种子集合规模 •α 用于调节种子集合的初始TrustRank值和扩散出的TrustRank值之间的权重 •TN 迭代次数 –算法输出: •TrustRank得分
基于链接关系分析的垃圾页面识别 TrustRank算法 1.选取种子集合 S 2.对G中的每一个节点n，若 ，则 否则 ，同时令 k = 1, 2, 3, … , TN ； 对G中的每一个节点n， 3.当结果向量未收敛时，返回3继续循环；当收敛时，算法结束，输出所计算出的G中每一个节点n的TR结果。
基于链接关系分析的垃圾页面识别 •TrustRank算法的说明 –算法的收敛性： •迭代次数取决于链接结构图的规模和连通情况 •万维网任意两个网页间的平均距离约为19 个链接 •TN = 20-30 –与PageRank算法的比较 •对“死胡同”网页的处理 •民主 . 信任权威 •有偏的PageRank算法（a biased PageRank variant）
基于链接关系分析的垃圾页面识别 •TrustRank算法结果示例 [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
基于链接关系分析的垃圾页面识别 •TrustRank算法结果示例 [] -20 [] -20 []Spam/Illegal Low-quality Non-GBK High-quality -21 100[s Wonenber iSei-tseosn nweirtihe .] -21 [wthwew z] 3 421445e-21 95 Tr[ csicao-lrieb ] -21 100[] -21 Web Sites with [] -21 [wtwhew lowest 10 79 9 2 ] -21 [] -22 [] -22 [] -22 [] -22 [] -22 [] -22
基于链接关系分析的垃圾页面识别 •TrustRank算法的延伸 –TrustRank算法： 高质量页面不太可能指向垃圾页面 Seedset: 高质量页面/站点 –Anti-TrustRank算法： 指向垃圾页面的也有很大可能是垃圾页面 Seedset: 低质量页面/站点 –在使用用户行为信息过滤后的链接关系图施行TrustRank算法
垃圾页面识别技术 •垃圾页面识别的效果评价 •基于网页内容的垃圾页面识别 •基于链接关系分析的垃圾页面识别 •基于用户行为特性的垃圾页面识别
基于用户行为特性的垃圾页面识别 •垃圾页面 . 搜索引擎 前10位结果中就有3个垃圾网页
基于用户行为特性的垃圾页面识别 •问题: 垃圾页面识别成为了一个永不停息、永无止境的工作 –百度应对李开复“搜索应公正”的声明内容： 百度每天处理作弊及垃圾站点约在3万左右。“垃圾信息制造者每天在制造数以万计的垃圾网站，这些网站包括纯作弊网站、机器采集网站、钓鱼网站等。”这些作弊站点的目的就是为了从搜索引擎获得流量，而每年在反垃圾信息领域的技术投入，百度的资金和人力投入已超过了全球中文搜索引擎市场的总和。 •垃圾页面识别性能不高？
基于用户行为特性的垃圾页面识别 •传统的垃圾页面识别流程 垃圾页面制造者制造垃圾 搜索引擎产品人员发现垃圾页面 搜索引擎技术人员针对垃圾页面设计识别算法 识别算法上线，垃圾页面被识别
基于用户行为特性的垃圾页面识别 •问题1：垃圾页面识别的时效性 –只能在垃圾页面造成较大影响后才开发针对此种垃圾页面的识别算法，周期过长 UV / Profit T1 T2Time
基于用户行为特性的垃圾页面识别 •问题2：垃圾页面识别的通用性 –垃圾页面识别算法针对垃圾页面的作弊方式设计，只能用于识别某种特定类型的垃圾页面 多次页面抓取识别 文本压缩二元语言比例识别模型识别
基于用户行为特性的垃圾页面识别 •解决思路 –垃圾作弊的最终目的 •吸引用户访问他并不想访问的内容 –用户最早发现垃圾的存在 –用户对垃圾的访问方式不同于其对正常页面的访问方式 •访问时间借助用户行为分析 Wisdom of the •交互方式 Crowds •访问来源
基于用户行为特性的垃圾页面识别 •解决思路：用户标注
基于用户行为特性的垃圾页面识别 •解决思路：用户标注（续） –与经济利益密切相关 –群众的话不能不信，也不能全信 –需要借助标注人员的过滤，反馈速度慢
基于用户行为特性的垃圾页面识别 •解决思路：用户群体的行为分析 –隐式反馈与显式反馈 (implicit / explicit feedback) •显式反馈 –用户调查分析 –直接，对用户行为产生影响，少量 •隐式反馈 –用户行为挖掘 –间接，不对用户行为产生影响，大量
基于用户行为特性的垃圾页面识别 •用户行为的载体：日志数据 –查询与点击日志 •用户提交的查询 •用户点击了哪些结果 •其他辅助信息 –结果对应的排序 –时间戳 –用户点击的序列关系 –用户IP –用户Session ID（记录在Cookie里）
基于用户行为特性的垃圾页面识别 •用户行为的载体：日志数据 –互联网访问日志 •用户当前正在访问的网页 •用户从此网页出发下一步访问的网页 •辅助信息 –时间戳 –用户IP –用户Session ID（记录在Cookie里） –用户停留时间
基于用户行为特性的垃圾页面识别 •基于用户行为特性的垃圾页面识别 –搜索引擎引导比率 –页面点击交互比率 –网站停留时间
用户行为特性分析 •搜索引擎引导比率(Search engine oriented visiting rate, SEOV rate) –垃圾页面是那些通过不正当的手段获取搜索引擎中不应有的较高排名的网页 –假设: 大多数对垃圾页面的访问是由搜索引擎引导的 –定义：
PageSpam 用户行为特性分析 •SEOV 分布情况 -1SEOV个别垃圾页面的SEOV值也较低 绝大部分非垃圾页面的访问量并非由搜索引擎引导的 Percentage
用户行为特性分析 •页面点击交互比率(Source page rate, SP rate) –垃圾页面一般会将作弊内容以最明显的方式展现给用户。用户容易辨识出垃圾页面，从而不会与其进一步交互 –假设: 绝大部分用户不会与垃圾页面上的链接发生交互（不会点击垃圾页面上的链接） –定义: SP#()(p) visitsorientedfromp#(pappearsintheWebaccesslogs)
PageSpam 用户行为特性分析 •SP 数值分布 <>极个别用户会点击垃圾页面上的链接 (可能是由于垃圾页面的自动跳转，或被锚文本的内容欺骗) 半数垃圾页面的SP值非常低 Percentage
用户行为特性分析 •网站短期停留比率(Short-time Navigation Rate, SN rate) –时间局部性原理：用户不会在短期内连续被同一种作弊形式欺骗 –假设：大多数用户不会在短时间内连续访问同一垃圾网站 –Definition: N: parameter
PageSpam 用户行为0特.性2分析 •SN 数值分布 (N = 3) -1SN一定数量的非垃圾网站在短期内也不会被用户访问很多次 (重定向站点, 百科站点, …) 极少垃圾网站被同一用户短期内访问2次以上 Percentage
垃圾页面识别效果 •识别性能 –ROC/AUC: 有85%的概率将垃圾页面排在非垃圾页面之前 –P@300: % (垃圾页面%，低质量页面%，死链%，非法站点% )
垃圾页面识别效果 •通用性 –不局限特定作弊形式 –能够发现新出现的作弊形式 •时效性 –2008年3月2日识别出1000个垃圾网站 –其中有723个是垃圾或者低质量站点 –3月6日时，这部分站点在sogou的索引量总和是3400万个页面以上 –3月26日时，索引总量更是超过了5900万个页面
结语 •垃圾页面的定义和盈利方式 •垃圾页面的分类 –基于作弊形式、基于作弊目的 •垃圾页面识别 –垃圾页面识别的效果评价 –基于网页内容的垃圾页面识别 –基于链接关系分析的垃圾页面识别 –基于用户行为特性的垃圾页面识别
参考阅读 •Gyöngyi, Z. and Garcia-Molina, H. Web spam taxonomy. In the First International Workshop on Adversarial Information Retrieval on the Web, 2005. •Ntoulas, A., Najork, M., Manasse, M., and Fetterly, D. 2006. Detecting spam web pages through content analysis. In Proceedings of the 15th International Conference on World Wide Web. WWW '06. ACM Press, New York, NY, 83-92. •Gyöngyi, Z., Garcia-Molina, H., and Pedersen, J. 2004. Combating web spam with trustrank. In Proceedings of the Thirtieth international Conference on Very Large Data Bases - Volume 30. 576-587. •Yiqun Liu, Rongwei Cen, Min Zhang, Shaoping Ma, Liyun Ru. Identifying Web Spam with User Behavior Analysis. In The Fourth International Workshop on Adversarial Information Retrieval on the Web. .
链接结构分析实验讲评 •完成情况基本良好，个别同学态度不认真 •完成情况较好的同学 –计70班 王栋 •强连通分量的分布情况分析 •信息传播在链接结构图上的分析（SNS） –计74班 白杨 •入度、出度联合分布情况分析 –计74班 黄文溢 •PageRank与indegree, outdegree的相关程度分析
Thank you! Questions or comments?
