【试读】《大数据:互联网大规模数据挖掘与分布式处理(第2版)》

dwng

贡献于2015-07-27

字数:0 关键词: 机器学习

内 容 提 要 本书由斯坦福大学“Web 挖掘”课程的内容总结而成,主要关注极大规模数据的挖掘。主要内容包括 分布式文件系统、相似性搜索、搜索引擎技术、频繁项集挖掘、聚类算法、广告管理及推荐系统、社会网 络图挖掘和大规模机器学习等。其中每一章节有对应的习题,以巩固所讲解的内容。读者更可以从网上获 取相关拓展材料。 本书适合本科生、研究生及对数据挖掘感兴趣的读者阅读。 定价:79.00元 读者服务热线:(010)51095186转600 印装质量热线:(010)81055316 反盗版热线:(010)81055315 广告经营许可证:京崇工商广字第 0021 号 著    [美] Jure Leskovec [美] Anand Rajaraman      [美] Jeffrey David Ullman 译    王 斌 责任编辑 岳新欣 责任印制 杨林杰 人民邮电出版社出版发行  北京市丰台区成寿寺路11号 邮编 100164  电子邮件 315@ptpress.com.cn 网址 http://www.ptpress.com.cn 北京      印刷 开本:800×1000 1/16 印张:24.25 字数:573千字 2015年 7 月第 2 版 印数:40 001 — 45 000册 2015年 7 月北京第 1 次印刷 著作权合同登记号 图字:01-2015-3276号 ◆ ◆ ◆ 错误!文档中没有指定样式的文字。 1 1 2 3 4 5 12 6 7 8 9 10 11 版 权 声 明 Mining of Massive Datasets second edition (978-1-107-07723-2) by Jure Leskovec, Anand Rajaraman and Jeffrey David Ullman first published by Cambridge University Press 2014. All rights reserved. This simplified Chinese edition for the People’s Republic of China is published by arrangement with the Press Syndicate of the University of Cambridge, Cambridge, United Kingdom. © Cambridge University Press & Posts & Telecom Press 2015. This book is in copyright. No reproduction of any part may take place without the written permission of Cambridge University Press and Posts & Telecom Press. This edition is for sale in the People’s Republic of China (excluding Hong Kong SAR, Macao SAR and Taiwan Province) only. 此版本仅限在中华人民共和国境内(不包括香港、澳门特别行政区及台湾地区)销售。 译 者 序 1 1 2 3 4 5 12 6 7 8 9 10 11 译 者 序 很高兴本书的第2版能和读者见面,和第1版相比,这一版增加了第10、11、12章。第10章介 绍了近年来十分流行的社会网络分析技术,第11章对高维数据空间的降维技术进行了阐述,第12 章则介绍了大规模数据下的机器学习方法。除此之外,这一版第2章也对第1版的内容进行了扩充, 主要增加了对MapReduce算法的复杂度分析理论。除了内容的变化,本书的作者也从原来的两位 增加到三位,在学术界(特别是社交网络挖掘领域)如日中天的斯坦福大学年轻帅哥Jure Leskovec 博士,也加入到本书的作者行列。 本书第1版出版之后,获得了不少读者的积极反馈,这些反馈也在第2版中有所体现。需要指 出的是,本书是一本面向大数据挖掘的技术而非概念性图书,需要反复研读认真实践才能真正理 解。还有,本书主要基于MapReduce框架来介绍分布式挖掘算法的实现。目前大数据包罗万象、 实现框架众多,数据挖掘并不是唯一关键技术,MapReduce也不是唯一可选框架。读者可以通过 阅读其他书籍进行补充。 我曾于2009年翻译了《信息检索导论》一书。在我的理解体系下,信息检索是一门跨众多学 科领域的研究方向,其主要的应用形式包括搜索、推荐和挖掘三种。如果说先前翻译的《信息检 索导论》注重信息检索的基本理论和搜索应用,那么本书则关注了推荐和挖掘应用。在这个意义 上说,这两本书可以互为补充。这也是我选择本书进行翻译的原因之一。另一个原因在于本书集 中关注大数据处理这个极具研究和应用前景的话题,一想到它可以为很多人带来帮助就让我欣慰 不已。 本书主要以Web上的数据为对象介绍大规模情况下的数据挖掘。除了传统的聚类、频繁项发 现及链接分析等内容外,它还介绍了数据流挖掘、互联网广告、推荐系统、社会网络分析及分布 式机器学习等近年来被广泛关注的话题。特别地,本书专门介绍了支持大规模数据挖掘的分布式 文件系统及MapReduce分布式计算框架。和《信息检索导论》相比,本书在理论上虽然可能不如 前者深入,但是它在简明扼要阐明基本原理的基础上,更侧重大数据环境下的实际算法实现。具 体地,本书给出了在面对大规模数据时基于MapReduce框架的多个算法实现。换句话说,它的算 法可以在大数据环境下真正“落地”,这无疑给想要或致力于大数据挖掘的读者带来理解和实现 上的巨大裨益。 虽然我的很多学生都对本书内容有较深的理解,但是为了保持翻译风格的一致性并对本书翻 译负全部责任,在出版社的建议下我还是与前一本书一样选择了自己独立翻译。感谢复旦大学黄 萱菁教授、中科院自动化所赵军研究员、中科院软件所孙乐研究员、中科院研究生院何苯博士等 2 译 者 序 人对本书第1版及第2版提出的建设性意见和建议。对他们的无私帮助,我表示由衷的感谢。感谢 图灵公司的武卫东、傅志红、李松峰、岳新欣等人为本书付出的努力,感谢人民邮电出版社杨海 玲女士的大力引荐。通过翻译,我也认识了图灵公司及图灵社区的众多朋友,并从他们身上学到 了很多宝贵的东西。感谢对我译书给予支持和鼓励的李锦涛研究员、孟丹研究员、郭莉研究员、 刘群研究员、贺劲博士、虎嵩林博士等领导、朋友和同事。感谢我的学生们作为最早的读者给予 的建议和意见,其中李佩佳、叶邦宇、洪洁等提出了许多十分宝贵的意见。感谢我的家人,他们 总是无怨无悔地给我最大的支持和包容,让我能够全身心投入到工作和翻译当中。由于翻译基本 在业余时间尤其是晚间完成,因此晚睡便成了家常便饭。我的儿子心心知道我要翻译便会按时睡 觉不再打扰我,这让我感到欣慰并给我力量。翻译过程中,我和原书作者Jeffrey David Ullman进 行了邮件交流,澄清了理解上的一些误区,并更正了原书中一些错误。我的翻译也得到了对方的 热情鼓励。 因本人各方面水平有限,现有译文中肯定存在许多不足。希望读者能够和我联系,提出疑问 和勘误,以便能够不断改进本书质量。来信请联系wbxjj2008@gmail.com,本书勘误会及时公布在 图灵社区网站www.ituring.com.cn上。原书的初稿电子版等信息也可以从网站http://mmds.org下载。 王 斌 2014年12月15日于中关村 前 言 1 1 2 3 4 5 12 6 7 8 9 10 11 前 言 本书根据Anand Rajaraman和Jeff Ullman于斯坦福大学教授多年的一门季度课程的材料汇编 而成。该课程名为“Web挖掘”(编号CS345A),尽管它已经成为高年级本科生能接受并感兴趣 的课程之一,但其原本是一门为高年级研究生设计的课程。Jure Leskovec到斯坦福大学任职后, 我们对相关材料进行了重新组织。他开设了一门有关网络分析的新课程CS224W并为CS345A增加 了一些内容,后者重新编号为CS246。三位作者也开设了一门大规模数据挖掘的项目课程CS341。 目前本书包含了所有三门课程的教学内容。 本书内容 简单来说,本书是关于数据挖掘的。但是,本书主要关注极大规模数据的挖掘,“极大规模” 的意思是说这些数据大到无法在内存中存放。由于重点强调数据的规模,所以本书的例子大都来 自Web本身或者Web上导出的数据。另外,本书从算法的角度来看待数据挖掘,即数据挖掘是将 算法应用于数据,而不是使用数据来“训练”某种类型的机器学习引擎。 本书的主要内容包括: (1) 分布式文件系统以及已成功应用于大规模数据集并行算法构建的MapReduce工具; (2) 相似性搜索,包括最小哈希和局部敏感哈希的关键技术; (3) 数据流处理以及面对快速到达、须立即处理、易丢失的数据的专用处理算法; (4) 搜索引擎技术,包括谷歌的PageRank、链接作弊检测及计算网页导航度(hub)和权威度 (authority)的HITS方法; (5) 频繁项集挖掘,包括关联规则挖掘、购物篮分析、A-Priori及其改进算法; (6) 大规模高维数据集的聚类算法; (7) Web应用中的两个关键问题:广告管理及推荐系统; (8) 对极大规模的图(特别是社会网络图)的结构进行分析和挖掘的算法; (9) 通过降维来获得大规模数据集的重要性质的技术,包括SVD分解和隐性语义索引; (10) 可以应用于极大规模数据的机器学习算法,包括感知机、支持向量机和梯度下降法。 先修课程 为了让读者完全领会本书内容,我们推荐如下先修课程: 2 前 言 (1) 数据库系统入门,包括SQL及相关编程系统; (2) 大二的数据结构、算法及离散数学课程; (3) 大二的软件系统、软件工程及编程语言课程。 习题 本书包含大量的习题,基本每节都有对应习题。较难的习题或其中较难的部分都用惊叹号“!” 来标记,而最难的习题则标有双惊叹号“!!”。 Web上的支持 读者可以从下列网址获得CS345A课程提供的更多材料:http://mmds.org。 在该网址下,读者可以找到课件、课后作业、项目作业等材料,某些情况下可能还有试题。 Gradiance自动化作业 本书使用www.gradiance.com/services提供的Gradiance根问题技术,提供了一些自动化习题。学生 可以在网站上通过创建账号来访问公开课,并通过代码1EDD8A1D访问该课程。授课老师可以建立 账号,然后将登录账号、学院名称及MMDS材料请求信息发给support@gradiance.com。 致谢 本书封面由Scott Ullman设计。 感谢Foto Afrati、Arun Marathe和Rok Sosic精心阅读本书初稿并提出建设性的意见。 感谢Apoorv Agarwal、Aris Anagnostopoulos、Atilla Soner Balkir、Robin Bennett、Susan Biancani、 Amitabh Chaudhary、Leland Chen、Anastasios Gounaris、Shrey Gupta、Waleed Hameid、Ed Knorr、 Haewoon Kwak、Ellis Lau、 Ethan Lozano、Michael Mahoney、Justin Meyer、Brad Penoff、Philips Kokoh Prasetyo、Qi Ge、Angad Singh、Sandeep Sripada、Dennis Sidharta、Krzysztof Stencel、Mark Storus、Roshan Sumbaly、Zack Taylor、Tim Triche Jr.、Wang Bin、Weng Zhen-Bin、Robert West、 Oscar Wu、Xie Ke、Nicolas Zhao及Zhou Jingbo指出了本书中的部分错误。当然,其余错误均由 我们负责。 J. L. A. R. J. D. U. 加利福尼亚州帕洛阿尔托 2014 年 3 月 目 录 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 目 录 第 1 章 数据挖掘基本概念 ......................... 1 1.1 数据挖掘的定义........................................... 1 1.1.1 统计建模 .......................................... 1 1.1.2 机器学习 .......................................... 1 1.1.3 建模的计算方法............................... 2 1.1.4 数据汇总 .......................................... 2 1.1.5 特征抽取 .......................................... 3 1.2 数据挖掘的统计限制................................... 4 1.2.1 整体情报预警................................... 4 1.2.2 邦弗朗尼原理................................... 4 1.2.3 邦弗朗尼原理的一个例子............... 5 1.2.4 习题.................................................. 6 1.3 相关知识 ...................................................... 6 1.3.1 词语在文档中的重要性................... 6 1.3.2 哈希函数 .......................................... 7 1.3.3 索引.................................................. 8 1.3.4 二级存储器 ...................................... 9 1.3.5 自然对数的底 e.............................. 10 1.3.6 幂定律 ............................................ 11 1.3.7 习题................................................ 12 1.4 本书概要 .................................................... 13 1.5 小结............................................................ 14 1.6 参考文献 .................................................... 15 第 2 章 MapReduce 及新软件栈...............16 2.1 分布式文件系统......................................... 17 2.1.1 计算节点的物理结构..................... 17 2.1.2 大规模文件系统的结构................. 18 2.2 MapReduce................................................. 19 2.2.1 Map 任务 ........................................ 20 2.2.2 按键分组 ........................................ 20 2.2.3 Reduce 任务.................................... 21 2.2.4 组合器 ............................................ 21 2.2.5 MapReduce 的执行细节................. 22 2.2.6 节点失效的处理............................. 23 2.2.7 习题................................................ 23 2.3 使用MapReduce 的算法............................ 23 2.3.1 基于MapReduce 的矩阵—向量 乘法实现........................................ 24 2.3.2 向量v 无法放入内存时的处理..... 24 2.3.3 关系代数运算 ................................ 25 2.3.4 基于MapReduce 的选择运算........ 27 2.3.5 基于MapReduce 的投影运算........ 27 2.3.6 基于MapReduce 的并、交和差 运算................................................ 28 2.3.7 基于MapReduce 的自然连接 运算................................................ 28 2.3.8 基于MapReduce 的分组和聚 合运算............................................ 29 2.3.9 矩阵乘法 ........................................ 29 2.3.10 基于单步 MapReduce 的矩阵 乘法.............................................. 30 2.3.11 习题.............................................. 31 2.4 MapReduce 的扩展 .................................... 31 2.4.1 工作流系统 .................................... 32 2.4.2 MapReduce 的递归扩展版本......... 33 2.4.3 Pregel 系统 ..................................... 35 2.4.4 习题................................................ 35 2.5 通信开销模型 ............................................ 36 2.5.1 任务网络的通信开销..................... 36 2.5.2 时钟时间 ........................................ 37 2.5.3 多路连接 ........................................ 38 2 目 录 2.5.4 习题................................................ 41 2.6 MapReduce 复杂性理论 ............................ 41 2.6.1 Reducer 规模及复制率................... 41 2.6.2 一个例子:相似性连接................. 42 2.6.3 MapReduce 问题的一个图模型..... 44 2.6.4 映射模式 ........................................ 45 2.6.5 并非所有输入都存在时的处理..... 46 2.6.6 复制率的下界 ................................ 46 2.6.7 案例分析:矩阵乘法..................... 48 2.6.8 习题................................................ 51 2.7 小结............................................................ 51 2.8 参考文献 .................................................... 53 第 3 章 相似项发现 .................................. 55 3.1 近邻搜索的应用 ........................................ 55 3.1.1 集合的 Jaccard 相似度................... 55 3.1.2 文档的相似度 ................................ 56 3.1.3 协同过滤——一个集合相似 问题................................................ 57 3.1.4 习题................................................ 58 3.2 文档的 shingling......................................... 58 3.2.1 k-shingle.......................................... 58 3.2.2 shingle 大小的选择 ........................ 59 3.2.3 对shingle 进行哈希 ....................... 59 3.2.4 基于词的 shingle............................ 60 3.2.5 习题................................................ 60 3.3 保持相似度的集合摘要表示..................... 61 3.3.1 集合的矩阵表示............................. 61 3.3.2 最小哈希 ........................................ 62 3.3.3 最小哈希及 Jaccard 相似度........... 62 3.3.4 最小哈希签名 ................................ 63 3.3.5 最小哈希签名的计算..................... 63 3.3.6 习题................................................ 66 3.4 文档的局部敏感哈希算法......................... 67 3.4.1 面向最小哈希签名的 LSH ............ 67 3.4.2 行条化策略的分析......................... 68 3.4.3 上述技术的综合............................. 69 3.4.4 习题................................................ 70 3.5 距离测度 .................................................... 70 3.5.1 距离测度的定义............................. 71 3.5.2 欧氏距离 ........................................ 71 3.5.3 Jaccard 距离.................................... 72 3.5.4 余弦距离 ........................................ 72 3.5.5 编辑距离 ........................................ 73 3.5.6 海明距离 ........................................ 74 3.5.7 习题................................................ 74 3.6 局部敏感函数理论..................................... 75 3.6.1 局部敏感函数 ................................ 76 3.6.2 面向Jaccard 距离的局部敏感 函数族............................................ 77 3.6.3 局部敏感函数族的放大处理......... 77 3.6.4 习题................................................ 79 3.7 面向其他距离测度的 LSH 函数族 ........... 80 3.7.1 面向海明距离的 LSH 函数族 ....... 80 3.7.2 随机超平面和余弦距离................. 80 3.7.3 梗概................................................ 81 3.7.4 面向欧氏距离的 LSH 函数族 ....... 82 3.7.5 面向欧氏空间的更多 LSH 函数族............................................ 83 3.7.6 习题................................................ 83 3.8 LSH 函数的应用........................................ 84 3.8.1 实体关联 ........................................ 84 3.8.2 一个实体关联的例子..................... 85 3.8.3 记录匹配的验证............................. 86 3.8.4 指纹匹配 ........................................ 87 3.8.5 适用于指纹匹配的 LSH 函数族............................................ 87 3.8.6 相似新闻报道检测......................... 88 3.8.7 习题................................................ 89 3.9 面向高相似度的方法................................. 90 3.9.1 相等项发现 .................................... 90 3.9.2 集合的字符串表示方法................. 91 3.9.3 基于长度的过滤............................. 91 3.9.4 前缀索引 ........................................ 92 3.9.5 位置信息的使用............................. 93 3.9.6 使用位置和长度信息的索引......... 94 3.9.7 习题................................................ 96 3.10 小结.......................................................... 97 3.11 参考文献 .................................................. 98 目 录 3 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 第 4 章 数据流挖掘 .................................100 4.1 流数据模型 .............................................. 100 4.1.1 一个数据流管理系统................... 100 4.1.2 流数据源的例子........................... 101 4.1.3 流查询 .......................................... 102 4.1.4 流处理中的若干问题................... 103 4.2 流当中的数据抽样................................... 103 4.2.1 一个富于启发性的例子............... 104 4.2.2 代表性样本的获取....................... 104 4.2.3 一般的抽样问题........................... 105 4.2.4 样本规模的变化........................... 105 4.2.5 习题.............................................. 106 4.3 流过滤 ...................................................... 106 4.3.1 一个例子 ...................................... 106 4.3.2 布隆过滤器 .................................. 107 4.3.3 布隆过滤方法的分析................... 107 4.3.4 习题.............................................. 108 4.4 流中独立元素的数目统计....................... 109 4.4.1 独立元素计数问题....................... 109 4.4.2 FM 算法........................................ 109 4.4.3 组合估计 ...................................... 110 4.4.4 空间需求 ...................................... 111 4.4.5 习题.............................................. 111 4.5 矩估计 ...................................................... 111 4.5.1 矩定义 .......................................... 111 4.5.2 二阶矩估计的 AMS 算法 ............ 112 4.5.3 AMS 算法有效的原因 ................. 113 4.5.4 更高阶矩的估计........................... 113 4.5.5 无限流的处理............................... 114 4.5.6 习题.............................................. 115 4.6 窗口内的计数问题................................... 116 4.6.1 精确计数的开销........................... 116 4.6.2 DGIM 算法................................... 116 4.6.3 DGIM 算法的存储需求 ............... 118 4.6.4 DGIM 算法中的查询应答 ........... 118 4.6.5 DGIM 条件的保持 ....................... 119 4.6.6 降低错误率 .................................. 120 4.6.7 窗口内计数问题的扩展............... 120 4.6.8 习题.............................................. 121 4.7 衰减窗口 .................................................. 121 4.7.1 最常见元素问题........................... 121 4.7.2 衰减窗口的定义........................... 122 4.7.3 最流行元素的发现....................... 123 4.8 小结.......................................................... 123 4.9 参考文献 .................................................. 124 第 5 章 链接分析 .................................... 126 5.1 PageRank.................................................. 126 5.1.1 早期的搜索引擎及词项作弊....... 126 5.1.2 PageRank 的定义.......................... 128 5.1.3 Web 结构...................................... 130 5.1.4 避免终止点 .................................. 132 5.1.5 采集器陷阱及“抽税”法........... 134 5.1.6 PageRank 在搜索引擎中的 使用.............................................. 136 5.1.7 习题.............................................. 136 5.2 PageRank 的快速计算.............................. 137 5.2.1 转移矩阵的表示........................... 137 5.2.2 基于MapReduce 的 PageRank 迭代计算...................................... 138 5.2.3 结果向量合并时的组合器 使用.............................................. 139 5.2.4 转移矩阵中块的表示................... 140 5.2.5 其他高效的 PageRank 迭代 方法.............................................. 141 5.2.6 习题.............................................. 142 5.3 面向主题的 PageRank ............................. 142 5.3.1 动机.............................................. 142 5.3.2 有偏的随机游走模型................... 143 5.3.3 面向主题的 PageRank 的使用..... 144 5.3.4 基于词汇的主题推断................... 144 5.3.5 习题.............................................. 145 5.4 链接作弊 .................................................. 145 5.4.1 垃圾农场的架构........................... 145 5.4.2 垃圾农场的分析........................... 147 5.4.3 与链接作弊的斗争....................... 147 5.4.4 TrustRank...................................... 148 5.4.5 垃圾质量 ...................................... 148 5.4.6 习题.............................................. 149 5.5 导航页和权威页 ...................................... 149 4 目 录 5.5.1 HITS 的直观意义......................... 150 5.5.2 导航度和权威度的形式化........... 150 5.5.3 习题.............................................. 153 5.6 小结.......................................................... 153 5.7 参考文献 .................................................. 155 第 6 章 频繁项集.....................................157 6.1 购物篮模型 .............................................. 157 6.1.1 频繁项集的定义........................... 157 6.1.2 频繁项集的应用........................... 159 6.1.3 关联规则 ...................................... 160 6.1.4 高可信度关联规则的发现........... 161 6.1.5 习题.............................................. 162 6.2 购物篮及 A-Priori 算法 ........................... 163 6.2.1 购物篮数据的表示....................... 163 6.2.2 项集计数中的内存使用............... 164 6.2.3 项集的单调性 .............................. 165 6.2.4 二元组计数 .................................. 166 6.2.5 A-Priori 算法 ................................ 166 6.2.6 所有频繁项集上的 A-Priori 算法.............................................. 168 6.2.7 习题.............................................. 169 6.3 更大数据集在内存中的处理................... 170 6.3.1 PCY 算法...................................... 171 6.3.2 多阶段算法 .................................. 172 6.3.3 多哈希算法 .................................. 174 6.3.4 习题.............................................. 175 6.4 有限扫描算法 .......................................... 177 6.4.1 简单的随机化算法....................... 177 6.4.2 抽样算法中的错误规避............... 178 6.4.3 SON 算法...................................... 179 6.4.4 SON算法和 MapReduce.............. 179 6.4.5 Toivonen 算法 .............................. 180 6.4.6 Toivonen 算法的有效性分析....... 181 6.4.7 习题.............................................. 181 6.5 流中的频繁项计数................................... 182 6.5.1 流的抽样方法 .............................. 182 6.5.2 衰减窗口中的频繁项集............... 183 6.5.3 混合方法 ...................................... 183 6.5.4 习题.............................................. 184 6.6 小结.......................................................... 184 6.7 参考文献 .................................................. 186 第 7 章 聚类............................................ 187 7.1 聚类技术介绍 .......................................... 187 7.1.1 点、空间和距离........................... 187 7.1.2 聚类策略 ...................................... 188 7.1.3 维数灾难 ...................................... 189 7.1.4 习题.............................................. 190 7.2 层次聚类 .................................................. 190 7.2.1 欧氏空间下的层次聚类............... 191 7.2.2 层次聚类算法的效率................... 194 7.2.3 控制层次聚类的其他规则........... 194 7.2.4 非欧空间下的层次聚类............... 196 7.2.5 习题.............................................. 197 7.3 k-均值算法 ............................................... 198 7.3.1 k-均值算法基本知识 ................... 198 7.3.2 k-均值算法的簇初始化................ 198 7.3.3 选择正确的 k 值........................... 199 7.3.4 BFR 算法...................................... 200 7.3.5 BFR 算法中的数据处理 .............. 202 7.3.6 习题.............................................. 203 7.4 CURE 算法............................................... 204 7.4.1 CURE算法的初始化 .................... 205 7.4.2 CURE 算法的完成....................... 206 7.4.3 习题.............................................. 206 7.5 非欧空间下的聚类................................... 207 7.5.1 GRGPF 算法中的簇表示............. 207 7.5.2 簇表示树的初始化....................... 207 7.5.3 GRGPF 算法中的点加入............. 208 7.5.4 簇的分裂及合并........................... 209 7.5.5 习题.............................................. 210 7.6 流聚类及并行化 ...................................... 210 7.6.1 流计算模型 .................................. 210 7.6.2 一个流聚类算法........................... 211 7.6.3 桶的初始化 .................................. 211 7.6.4 桶合并 .......................................... 211 7.6.5 查询应答 ...................................... 213 7.6.6 并行环境下的聚类....................... 213 7.6.7 习题.............................................. 214 目 录 5 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 7.7 小结.......................................................... 214 7.8 参考文献 .................................................. 216 第 8 章 Web 广告....................................218 8.1 在线广告相关问题................................... 218 8.1.1 广告机会 ...................................... 218 8.1.2 直投广告 ...................................... 219 8.1.3 展示广告的相关问题................... 219 8.2 在线算法 .................................................. 220 8.2.1 在线和离线算法........................... 220 8.2.2 贪心算法 ...................................... 221 8.2.3 竞争率 .......................................... 222 8.2.4 习题.............................................. 222 8.3 广告匹配问题 .......................................... 223 8.3.1 匹配及完美匹配........................... 223 8.3.2 最大匹配贪心算法....................... 224 8.3.3 贪心匹配算法的竞争率............... 224 8.3.4 习题.............................................. 225 8.4 adwords 问题............................................ 225 8.4.1 搜索广告的历史........................... 226 8.4.2 adwords 问题的定义 .................... 226 8.4.3 adwords 问题的贪心方法 ............ 227 8.4.4 Balance 算法................................. 228 8.4.5 Balance 算法竞争率的一个 下界.............................................. 228 8.4.6 多投标者的 Balance 算法............ 230 8.4.7 一般性的 Balance 算法................ 231 8.4.8 adwords 问题的最后论述 ............ 232 8.4.9 习题.............................................. 232 8.5 adwords 的实现 ........................................ 232 8.5.1 投标和搜索查询的匹配............... 233 8.5.2 更复杂的匹配问题....................... 233 8.5.3 文档和投标之间的匹配算法....... 234 8.6 小结.......................................................... 235 8.7 参考文献 .................................................. 237 第 9 章 推荐系统.....................................238 9.1 一个推荐系统的模型............................... 238 9.1.1 效用矩阵 ...................................... 238 9.1.2 长尾现象 ...................................... 239 9.1.3 推荐系统的应用........................... 241 9.1.4 效用矩阵的填充........................... 241 9.2 基于内容的推荐 ...................................... 242 9.2.1 项模型 .......................................... 242 9.2.2 文档的特征发现........................... 242 9.2.3 基于Tag 的项特征获取............... 243 9.2.4 项模型的表示 .............................. 244 9.2.5 用户模型 ...................................... 245 9.2.6 基于内容的项推荐....................... 246 9.2.7 分类算法 ...................................... 247 9.2.8 习题.............................................. 248 9.3 协同过滤 .................................................. 249 9.3.1 相似度计算 .................................. 249 9.3.2 相似度对偶性 .............................. 252 9.3.3 用户聚类和项聚类....................... 253 9.3.4 习题.............................................. 254 9.4 降维处理 .................................................. 254 9.4.1 UV 分解........................................ 255 9.4.2 RMSE ........................................... 255 9.4.3 UV 分解的增量式计算................ 256 9.4.4 对任一元素的优化....................... 259 9.4.5 一个完整 UV 分解算法的构 建.................................................. 259 9.4.6 习题.............................................. 261 9.5 NetFlix 竞赛 ............................................. 262 9.6 小结.......................................................... 263 9.7 参考文献 .................................................. 264 第 10 章 社会网络图挖掘........................ 265 10.1 将社会网络看成图................................. 265 10.1.1 社会网络的概念....................... 265 10.1.2 将社会网络看成图................... 266 10.1.3 各种社会网络的例子............... 267 10.1.4 多类型节点构成的图............... 268 10.1.5 习题.......................................... 269 10.2 社会网络图的聚类................................. 269 10.2.1 社会网络图的距离计算........... 269 10.2.2 应用标准的聚类算法............... 270 10.2.3 中介度 ...................................... 271 10.2.4 Girvan-Newman 算法............... 271 10.2.5 利用中介度来发现社区........... 274 6 目 录 10.2.6 习题.......................................... 275 10.3 社区的直接发现..................................... 275 10.3.1 团的发现 .................................. 276 10.3.2 完全二部图 .............................. 276 10.3.3 发现完全二部子图................... 277 10.3.4 完全二部子图一定存在的 原因.......................................... 277 10.3.5 习题.......................................... 279 10.4 图划分 .................................................... 280 10.4.1 图划分的好坏标准................... 280 10.4.2 归一化割 .................................. 280 10.4.3 描述图的一些矩阵................... 281 10.4.4 拉普拉斯矩阵的特征值........... 282 10.4.5 其他图划分方法....................... 284 10.4.6 习题.......................................... 284 10.5 重叠社区的发现..................................... 285 10.5.1 社区的本质 .............................. 285 10.5.2 极大似然估计........................... 286 10.5.3 关系图模型 .............................. 287 10.5.4 避免成员隶属关系的离散式 变化.......................................... 288 10.5.5 习题.......................................... 290 10.6 Simrank................................................... 290 10.6.1 社会网络上的随机游走者....... 290 10.6.2 带重启的随机游走................... 291 10.6.3 习题.......................................... 293 10.7 三角形计数问题..................................... 293 10.7.1 为什么要对三角形计数........... 294 10.7.2 一个寻找三角形的算法........... 294 10.7.3 三角形寻找算法的最优性....... 295 10.7.4 基于MapReduce 寻找三 角形.......................................... 295 10.7.5 使用更少的 Reduce 任务......... 297 10.7.6 习题.......................................... 297 10.8 图的邻居性质 ........................................ 298 10.8.1 有向图和邻居........................... 298 10.8.2 图的直径 .................................. 299 10.8.3 传递闭包和可达性................... 300 10.8.4 基于MapReduce 的传递闭包 求解.......................................... 301 10.8.5 智能传递闭包........................... 303 10.8.6 基于图归约的传递闭包........... 304 10.8.7 邻居规模的近似计算............... 305 10.8.8 习题.......................................... 306 10.9 小结........................................................ 307 10.10 参考文献 .............................................. 310 第 11 章 降维处理................................... 312 11.1 特征值和特征向量................................. 312 11.1.1 定义.......................................... 312 11.1.2 特征值与特征向量计算........... 313 11.1.3 基于幂迭代方法的特征对 求解.......................................... 315 11.1.4 特征向量矩阵........................... 317 11.1.5 习题.......................................... 317 11.2 主成分分析 ............................................ 318 11.2.1 一个示例 .................................. 318 11.2.2 利用特征向量进行降维........... 321 11.2.3 距离矩阵 .................................. 322 11.2.4 习题.......................................... 323 11.3 奇异值分解 ............................................ 323 11.3.1 SVD 的定义.............................. 323 11.3.2 SVD 解析.................................. 325 11.3.3 基于SVD 的降维..................... 326 11.3.4 将较低奇异值置为 0 后有 效的原因 .................................. 327 11.3.5 使用概念进行查询处理........... 328 11.3.6 矩阵SVD 的计算..................... 329 11.3.7 习题.......................................... 330 11.4 CUR 分解 ............................................... 331 11.4.1 CUR 的定义 ............................. 331 11.4.2 合理选择行和列....................... 332 11.4.3 构建中间矩阵........................... 333 11.4.4 完整的 CUR 分解..................... 334 11.4.5 去除重复行和列....................... 335 11.4.6 习题.......................................... 335 11.5 小结........................................................ 336 11.6 参考文献 ................................................ 337 第 12 章 大规模机器学习........................ 338 12.1 机器学习模型 ........................................ 338 目 录 7 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 12.1.1 训练集 ...................................... 338 12.1.2 一些例子 .................................. 339 12.1.3 机器学习方法........................... 341 12.1.4 机器学习架构........................... 342 12.1.5 习题.......................................... 344 12.2 感知机 .................................................... 344 12.2.1 训练阈值为 0 的感知机........... 344 12.2.2 感知机的收敛性....................... 347 12.2.3 Winnow 算法............................ 347 12.2.4 允许阈值变化的情况............... 349 12.2.5 多类感知机............................... 350 12.2.6 变换训练集............................... 351 12.2.7 感知机的问题........................... 351 12.2.8 感知机的并行实现................... 353 12.2.9 习题.......................................... 354 12.3 支持向量机 ............................................ 354 12.3.1 支持向量机的构成................... 354 12.3.2 超平面归一化........................... 356 12.3.3 寻找最优逼近分界面............... 357 12.3.4 基于梯度下降法求解 SVM ..... 359 12.3.5 随机梯度下降........................... 363 12.3.6 SVM 的并行实现 ..................... 363 12.3.7 习题.......................................... 363 12.4 近邻学习 ................................................ 364 12.4.1 近邻计算的框架....................... 364 12.4.2 最近邻学习 .............................. 365 12.4.3 学习一维函数........................... 365 12.4.4 核回归 ...................................... 367 12.4.5 处理高维欧氏空间数据........... 368 12.4.6 对非欧距离的处理................... 369 12.4.7 习题.......................................... 369 12.5 各种学习方法的比较............................. 370 12.6 小结........................................................ 371 12.7 参考文献 ................................................ 372 1.1 数据挖掘的定义 1 1 2 3 4 5 12 6 7 8 9 10 11 数据挖掘基本概念 本章为全书的导论部分,首先阐述数据挖掘的本质,并讨论其在多个相关学科中的不同理解。 接着介绍邦弗朗尼原理(Bonferroni’s principle),该原理实际上对数据挖掘的过度使用提出了警 告。本章还概述了一些非常有用的思想,它们未必都属于数据挖掘的范畴,但是却有利于理解数 据挖掘中的某些重要概念。这些思想包括度量词语重要性的TF.IDF权重、哈希函数及索引结构的 性质、包含自然对数底e的恒等式等。最后,简要介绍了后续章节所要涉及的主题。 1.1 数据挖掘的定义 最广为接受的定义是,数据挖掘(data mining)是数据“模型”的发现过程。而“模型”却 可以有多种含义。下面介绍在建模方面最重要的几个方向。 1.1.1 统计建模 最早使用“data mining”术语的人是统计学家。术语“data mining”或者“data dredging”最 初是贬义词,意指试图抽取出数据本身不支持的信息的过程。1.2节给出了这种挖掘情况下可能 犯的几类错误。当然,现在术语“data mining”的意义已经是正面的了。目前,统计学家认为数 据挖掘就是统计模型(statistical model)的构建过程,而这个统计模型指的就是可见数据所遵从 的总体分布。 例1.1 假定现有的数据是一系列数字。这种数据相对于常用的挖掘数据而言显得过于简 单,但这只是为了说明问题而采用的例子。统计学家可能会判定这些数字来自一个高斯分布(即 正态分布),并利用公式来计算该分布最有可能的参数值。该高斯分布的均值和标准差能够完 整地刻画整个分布,因而成为上述数据的一个模型。 1.1.2 机器学习 有些人将数据挖掘看成是机器学习的同义词。毫无疑问,一些数据挖掘方法中适当使用了机 器学习算法。机器学习的实践者将数据当成训练集来训练某类算法,比如贝叶斯网络、支持向量 机、决策树、隐马尔可夫模型等。 第1章 2 第1 章 数据挖掘基本概念 某些场景下上述的数据利用方式是合理的。机器学习擅长的典型场景是人们对数据中的寻找 目标几乎一无所知。比如,我们并不清楚到底是影片的什么因素导致某些观众喜欢或者厌恶该影 片。因此,在Netflix竞赛要求设计一个算法来预测观众对影片的评分时,基于已有评分样本的机 器学习算法获得了巨大成功。在9.4节中,我们将讨论此类算法的一个简单形式。 另一方面,当挖掘的目标能够更直接地描述时,机器学习方法并不成功。一个有趣的例子 是,WhizBang!实验室①曾试图使用机器学习方法在Web上定位人们的简历。但是不管使用什么 机器学习算法,最后的效果都比不过人工设计的直接通过典型关键词和短语来查找简历的算 法。由于看过或者写过简历的人都对简历包含哪些内容非常清楚,Web页面是否包含简历毫无 秘密可言。因此,使用机器学习方法相对于直接设计的简历发现算法而言并无任何优势。 1.1.3 建模的计算方法 近年来,计算机科学家已将数据挖掘看成一个算法问题。这种情况下,数据模型仅仅就是复 杂查询的答案。例如,给定例1.1中的一系列数字,我们可以计算它们的均值和标准差。需要注 意的是,这样计算出的参数可能并不是这组数据的最佳高斯分布拟合参数,尽管在数据集规模很 大时两者非常接近。 数据建模有很多不同的方法。前面我们已经提到,数据可以通过其生成所可能遵从的统计过 程构建来建模。而其他的大部分数据建模方法可以描述为下列两种做法之一: (1) 对数据进行简洁的近似汇总描述; (2) 从数据中抽取出最突出的特征来代替数据并将剩余内容忽略。 在接下来的内容中,我们将探究上述两种做法。 1.1.4 数据汇总 一种最有趣的数据汇总形式是PageRank,它也是使谷歌成功的关键算法之一,我们将在第5 章对它进行详细介绍。在这种形式的Web挖掘当中,Web的整个复杂结构可由每个页面所对应的 一个数字归纳而成。这种数字就是网页的PageRank值,即一个Web结构上的随机游走者在任意给 定时刻处于该页的概率(这是极其简化的一种说法)。PageRank的一个非常好的特性就是它能够 很好地反映网页的重要性,即典型用户在搜索时期望返回某个页面的程度。 另一种重要的数据汇总形式是聚类,第7章将予以介绍。在聚类中,数据被看成是多维空间 下的点,空间中相互邻近的点将被赋予相同的类别。这些类别本身也会被概括表示,比如通过类 别质心及类别中的点到质心的平均距离来描述。这些类别的概括信息综合在一起形成了全体数据 集合的数据汇总结果。 —————————— ① 该初创实验室试图使用机器学习方法来进行大规模数据挖掘,并且雇用了大批机器学习高手来实现这一点。遗憾 的是,该实验室并没有能够生存下来。 1.1 数据挖掘的定义 3 1 2 3 4 5 12 6 7 8 9 10 11 例1.2 一个利用聚类来解决问题的著名实例发生在很久以前的伦敦,在整个问题的解决中 并没有使用计算机①。内科医生John Snow在处理霍乱爆发时在城市地图上标出了病例的发生地 点。图1-1给出了该图的一个小片段,展示了病例的传播情况。 图1-1 在伦敦市地图上标出的霍乱病例的传播情况示意图 图中显示,病例聚集在某些交叉路口。这些路口的水井已经被污染,离这些水井最近的居民 染上了疾病,而清洁的水井附近的居民则没有染病。如果没对这些数据进行聚类,Snow就难以 揭开霍乱的病因。 1.1.5 特征抽取 典型的基于特征的模型会从数据中寻找某个现象的最极端样例,并使用这些样例来表示数 据。熟悉机器学习的一个分支——贝叶斯网络(并不在本书的讨论范围内)的读者应该会知道, 在贝叶斯网络中,可以利用寻找对象间的最强统计依赖来表示所有统计关联,从而表示出对象之 间的复杂关系。我们将要介绍大规模数据集下的一些重要的特征抽取类型,它们包括以下两种。 (1) 频繁项集(frequent itemset) 该模型适用于多个小规模项集组成的数据,就像我们将在 第6章讨论的购物篮问题(market-basket problem)一样。我们寻找那些在很多购物篮中同时出现 的小规模项集,这些频繁项集就是我们要找的刻画数据的特征。这种挖掘的原始应用的的确确发 生在真实的购物篮场景下:在商店或者超市收银台结账的时候确实会发现某些物品会被顾客同时 购买,例如汉堡包和番茄酱,这些物品就组成所谓的项集。 (2) 相似项(similar item) 很多时候,数据往往看上去相当于一系列集合,我们的目标是寻 找那些共同元素比例较高的集合对。一个例子是将在线商店(如Amazon)的顾客看成是其已购 买的商品的集合。为了使Amazon能够向某顾客推荐他可能感兴趣的其他商品,Amazon可以寻找 —————————— ① 参考http://en.wikipedia.org/wiki/1854_Broad_Street_cholera_outbreak。 4 第1 章 数据挖掘基本概念 与该顾客相似的顾客群,并把他们当中大部分人购买过的商品也推荐给他。该过程称为协同过滤 (collaborative filtering)。如果顾客的兴趣都很单一,即他们只购买某一类的商品,那么将顾客聚 类的方法可能会起作用。然而,由于顾客大都对许多不同的商品感兴趣,因此对每个顾客而言, 寻找兴趣相似的那部分顾客并根据这些关联对数据进行表示的做法会更有用。我们将在第3章讨 论相似性。 1.2 数据挖掘的统计限制 一类常见的数据挖掘问题涉及在大量数据中发现隐藏的异常事件。本节主要讨论这个问题, 并介绍对数据挖掘的过度使用进行警告的邦弗朗尼原理。 1.2.1 整体情报预警 2002年,美国布什政府提出了一项针对所有可获得的数据进行挖掘的计划,目的用于追踪恐 怖活动,这些数据包括信用卡收据、酒店记录、旅行数据以及许多其他类型的情报。该计划被称 为整体情报预警(Total Information Awareness,TIA)。TIA计划无疑在隐私倡导者当中受到了极 大关注,虽然最终它并没有被国会通过,但其实我们并不清楚这种计划是否已被冠以其他名称而 得以真正实施。隐私和安全的折中困难姑且不在本书的讨论目的之列,然而,TIA或类似系统若 想进一步发展,在其可行性和所依赖假设的现实性方面还需做更多的技术改进。 很多人关心的是,如果浏览了这么多数据,并且想从这些数据当中发现疑似的恐怖行为,那 么难道最终就不会找出很多无辜的行为?乃至虽然非法但不是恐怖行为的行为?这些发现会导 致警察的登门造访甚至更糟的情形。答案取决于所定义行为的严密程度。统计学家已经发现了该 问题的各种伪装形式,并且提出了一个理论。该理论将在下一节介绍。 1.2.2 邦弗朗尼原理 假定人们有一定量的数据并期望从该数据中找到某个特定类型的事件。即使数据完全随机, 也可以期望该类型事件会发生。随着数据规模的增长,这类事件出现的数目也随之上升。任何随 机数据往往都会有一些不同寻常的特征,这些特征看上去虽然很重要,但是实际上并不重要,除 此之外,别无他由,从这个意义上说,这些事件的出现纯属“臆造”。统计学上有一个称为邦弗 朗尼校正(Bonferroni correction)的定理,该定理给出一个在统计上可行的方法来避免在搜索数 据时出现的大部分“臆造”正响应。这里并不打算介绍定理的统计细节,只给出一个非正式的称 为邦弗朗尼原理的版本,该原理可以帮助我们避免将随机出现看成真正出现。在数据随机性假设 的基础上,可以计算所寻找事件出现次数的期望值。如果该结果显著高于你所希望找到的真正实 例的数目,那么可以预期,寻找到的几乎任何事物都是臆造的,也就是说,它们是在统计上出现 的假象,而不是你所寻找事件的凭证。上述观察现象是邦弗朗尼原理的非正式阐述。 以寻找恐怖分子为例,可以预期在任何时候都几乎没有恐怖分子在活动。按照邦弗朗尼原理, 1.2 数据挖掘的统计限制 5 1 2 3 4 5 12 6 7 8 9 10 11 只需要寻找那些几乎不可能出现在随机数据中的罕见事件来发现恐怖分子即可。下一节将给出一 个扩展的例子。 1.2.3 邦弗朗尼原理的一个例子 假设我们确信在某个地方有一群恶人,目标是把他们揪出来。再假定我们有理由相信,这些 恶人会定期在某个宾馆聚会来商讨他们的作恶计划。为限定问题的规模,我们再给出如下假设。 (1) 恶人数目可能有10亿。 (2) 每个人每100天当中会有一天去宾馆。 (3) 一个宾馆最多容纳100个人。因此,100 000个宾馆已足够容纳10亿人中的1%在某个给定 的日子入住宾馆。 (4) 我们将对1000天的宾馆入住记录进行核查。 为了在上述数据中发现恶人的踪迹,我们可以找出那些在两个不同日子入住同一宾馆的人。 但是假设并没有恶人,也就是说,给定某一天,对每个人来说,他们都是随机地确定是否去宾馆 (概率为0.01),然后又是随机地从105个宾馆中选择一个。从上述数据中,我们能否推断出某两个 人可能是恶人? 接下来我们做个简单的近似计算。给定某天,任意两个人都决定去宾馆的概率为0.000 1,而 他们入住同一宾馆的概率应该在0.000 1基础上除以105(宾馆的数量)。因此,在给定某天的情况 下,两个人同时入住同一宾馆的概率是109。而在任意给定的不同的两个日子,两人入住同一宾 馆的概率就是109的平方,即1018。需要指出的是,上述推理中只需要两人两次中每次住的宾馆 相同即可,并不需要两次都是同一家宾馆①。 基于上述计算,我们必须要考虑到底事件出现多少次才意味着作恶事件的发生。上例中,“事 件”的含义是指“两个人在两天中的每一天入住相同宾馆”。为简化数字运算,对于较大的n, 2 n  大概等于n2/2。下面我们都采用这个近似值。因此在109中的人员组对个数为 910 2    =5×1017,而 在1000天内任意两天的组合个数为 1000 2   =5×105。疑似作恶事件的期望数目应该是上述两者的 乘积再乘上“两个人在两天中的每一天入住相同宾馆”的概率,结果为 5 × 1017 × 5 × 105 × 1018 = 250 000 也就是说,大概有25万对人员看上去像恶人,即使他们根本不是。 现在假定实际上只有10对人员是真正的恶人。警察局需要调查25万对人员来寻找他们。除了 会侵犯近50万无辜人们的生活外,所需的工作量非常大,以至于上述做法几乎是不可行的。 —————————— ① 如第一天大家都住A,第二天都住B。但A可以不等于B。——译者注 6 第1 章 数据挖掘基本概念 1.2.4 习题 习题1.2.1 基于1.2.3节的信息,如果对数据做如下改变(其他数据保持不变),那么可能的 嫌疑人员对的数目是多少? (1) 观察的天数从1000天增加到2000天。 (2) 要观察的总人员数目上升到20亿(因此需要200 000个宾馆)。 (3) 只有在不同的三天内的同一时刻两个人入住相同宾馆的情况下,才进行嫌疑报告。 !习题1.2.2 假定有1亿人的超市购物记录,每个人每年都会去超市100次,每次都会买超市中 1000种商品中的10种。我们相信,两个恐怖分子会在一年中的某个时段购买相同的10种商品(比 如制造炸弹的材料)。如果对购买相同商品集合的人员对进行搜索,那么能否期望我们发现的任 何这类人员都是真正的恐怖分子?① 1.3 相关知识 本节中,我们将简要介绍一些有用的主题,读者可能在其他课程的研究中接触过或者根本没 有接触过这些主题,但是它们却对于数据挖掘的研究相当有益。这些主题包括: (1) 用于度量词语重要性的TF.IDF指标; (2) 哈希函数及其使用; (3) 二级存储器(磁盘)及其对算法运行时间的影响; (4) 自然对数的底e及包含它的一系列恒等式; (5) 幂定律。 1.3.1 词语在文档中的重要性 数据挖掘的不少应用都会涉及根据主题对文档(词语的序列)进行分类的问题。一般来说, 文档的主题主要通过找到一些特定的能够体现主题的词语来刻画。例如,有关棒球(baseball) 的文章当中往往会出现类似“ball”(球)、“bat”(球棒)、“pitch”(投球)以及“run”(跑垒)之 类的词语。一旦将文档分到确实是关于棒球的主题类中,不难发现上述词语在文档当中的出现往 往十分频繁。但是,在没有分类之前,并不能确定这些词语就刻画了棒球的主题类别。 因此,分类的第一步往往是考察文档并从中找出重要的词语。为达到这个目的,我们首先猜 测文档中最频繁出现的词语应该最重要。但是,这个直觉和实际情况恰恰相反。出现最频繁的大 部分词语肯定都是那些类似于“the”或者“and”的常见词,这些词通常都用于辅助表达但本身 不携带任何含义。实际上,英语中几百个最常见的词(称为停用词)往往都在文档分类之前就被 去掉。 事实上,描述主题的词语往往都相对罕见。但是,并非所有罕见词在做指示词时都同等重要。 —————————— ① 也就是说,假定恐怖分子一定会在一年中的某个时段购买相同的10件商品。这里不考虑恐怖分子是否必须要这样做。 1.3 相关知识 7 1 2 3 4 5 12 6 7 8 9 10 11 一方面,某些在整个文档集合中极少出现的词语(如“notwithstanding”或“albeit”)并不能提供 多少有用的信息。另一方面,某个如“chukker”(马球比赛中的一局)的词虽然和上述词语一样 罕见,但是该词语却能提示我们文档明显和马球运动有关。上述两类罕见词的区别与它们是否在 部分文档中反复出现有关。也就是说,类似“albeit”的词语在文档中出现并不会增加它多次出 现的可能性。但是,如果一篇文章有一次提到“chukker”,那么文档可能会提到“first chukker” (第一局)发生什么,接着提到“second chukker”(第二局)发生什么,以此类推。也就是说, 如果这类词在文档中出现那么它们很可能会反复出现。 这种度量给定词语在少数文档中反复出现程度的形式化指标称为TF.IDF(TF指词项频率,是 Term Frequency的缩写;IDF指逆文档频率,是Inverse Document Frequency的缩写;TF.IDF表示词 项频率乘以逆文档频率)。它通常采用如下方式计算。假定文档集中有N篇文档,fij为词项i在文档 j中出现的频率(即次数),于是,词项i在文档j中的词项频率TFij定义为 TF max ij ij kkj f f 也就是词项i在文档j中的词项频率fij归一化结果,其中归一化通过fij除以同一文档中出现最多 的词项(可能不考虑停用词的频率)的频率来计算。因此,文档j中出现频率最大的词项的TF值 为1,而其他词项的TF值都是分数①。 假定词项i在文档集的ni篇文档中出现,那么词项i的IDF定义如下: 2IDF logi i N n 于是,词项i在文档j中的得分被定义为TFij×IDFi,具有最高TF.IDF得分的那些词项通常都是 刻画文档主题的最佳词项。 例1.3 假定文档集中有220 = 1 048 576 篇文档,假定词语w在其中的210 = 1024篇文档中出现, 那么IDFw = log2(220/210) = log2(210) = 10。考虑一篇文档j,w在该文档中出现20次,这也是文档当 中出现最多的词(停用词可能已经去掉)。那么TFwj =1,于是w在文档j中的TF.IDF得分为10。 假定在文档k中,词语w出现一次,而该文档中任一词语最多出现20次。于是有TFwk = 1/20, w在文档k中的TF.IDF得分为1/2。 1.3.2 哈希函数 读者或许听说过哈希表,也可能在Java类或类似软件包当中使用过哈希表。实现哈希表的哈 希函数在多个数据挖掘算法中都是核心要素,不过在这些数据挖掘算法中,哈希表却和一般常见 的形式有所不同。下面我们将介绍哈希函数的基本知识。 首先,哈希函数h的输入是一个哈希键值(hash-key),输出是一个桶编号(bucket number)。 假定桶的个数为整数B,则桶编号通常是0到B1之间的整数。哈希键值可以是任何类型的数据。 哈希函数的一个直观性质是它们将哈希键值“随机化”(randomize)。更精确地说,如果哈希键 —————————— ① 因为都是两个正整数词频相除。——译者注 8 第1 章 数据挖掘基本概念 值随机地从某个合理的可能的哈希键分布中抽样而成,那么函数h将会把数目近似相等的哈希键 值分配到每个桶中。这一点有可能做不到,比如当所有可能的哈希键值数目少于桶数目B时就是 如此。当然我们可以认为该总体不具有“合理”分布。然而,可能存在更细微的原因导致哈希函 数的结果不能近似均匀地分布。 例1.4 假设所有的哈希键都是正整数。一个普遍且简单的哈希函数是h(x) = x mod B,即x 除以B之后的余数。如果哈希键的总体是所有的正整数,那么上述哈希函数产生的结果会非常均 匀,即1/B的整数将被分到每个桶中。但是,如果哈希键只能是偶数值,并且如果B=10,那么h(x) 的结果只能是0、2、4、6和8,也就是说,此时哈希函数的行为明显不够随机。另一方面,如果 选择B=11,那么会有1/11的偶数会分到每个桶中,这时候哈希函数的效果又会很好。 对上例进行一般化,当哈希键都是整数时,如果选用一个与所有可能的哈希键(或者大部 分)都具有公因子的B时,将会导致分配到桶中的结果不随机。因此,通常都首选将B取为素数。 尽管这种情况下我们还必须要考虑所有的哈希键以B为因子的可能性,但是上述选择方法减少了 非随机行为的可能性。当然,还有很多其他类型的哈希函数并不基于取模运算。这里也并不打 算概括所有可能的哈希函数类型,但是在最后一节的参考文献讨论当中也提到了一些相关的信 息来源。 如果哈希键不是整数,要如何处理呢?在某种意义上说,所有数据类型的值都由比特位组成, 而比特位序列常常可以解释成整数。但是,有一些简单的规则可以将通用的类型转化成整数。例 如,如果哈希键是字符串,那么可以将每个字符转换成其对应的ASCII码或Unicode码,每个码可 以解释为一个小整数。在除以B之前可以将这些整数求和,只要B小于字符串总体中各字节字符 码的典型求和结果,那么最后对B取模的结果相对还是比较均匀的。如果B更大,那么可以将字 符串拆分成多个组,每个组包含多个字符,一组字符可以连在一起看成一个整数。然后,将每组 字符对应的整数求和之后对B取模。比如,如果B在10亿上下或者说230,那么每四个字符合成一 组对应一个32位的整数,多个32位整数的求和结果将会相当均匀地分配到10亿个桶中去。  对于更复杂的数据类型,可以对上述字符串转化为整数的思路进行扩展来递归式处理。  对于记录型数据,记录中每个字段都有自己的类型,那么可以采用适合该类型的算法将 每个字段递归地转换成整数,然后将所有字段转换出的整数求和,最后对B取模来将整数 分配到不同桶中去。  对于数组型、集合型或包(bag)型①数据,数据中的每一个元素都是相同类型。可以先 将每个元素的值转换成整数,然后求和并对B取模。 1.3.3 索引 给定某种对象的一个或多个元素值,索引是一种能够支持对象高效查找的数据结构。最常见 的一种情况是对象都是记录,而索引按照记录中的某个字段来建立。给定该字段的值v,基于索 引能够快速返回该字段值等于v的所有记录。例如,假定有一个由一系列三元组<姓名, 地址, 电话 —————————— ① 一种允许集合中元素重复的数据类型。——译者注 1.3 相关知识 9 1 2 3 4 5 12 6 7 8 9 10 11 号码>组成的档案记录表以及基于电话号码字段建立的索引。当给定一个电话号码时,基于索引 就能快速找到包含该号码的一条或者多条记录。 实现索引的方法有很多,这里并不打算给出全面的介绍。参考文献部分给出了扩展阅读的建 议。但是,哈希表是一种简单的索引构建方法。哈希函数的输入键是用于建立索引的一个或者多 个字段。对于某条记录来说,哈希函数会基于其中哈希键的值进行计算,然后将整条记录分配到 某个桶中,而桶的号码取决于哈希函数的结果。举例来说,这里的桶可以是内存或磁盘块中的一 个记录表①。 于是,给定一个哈希键值,我们可以先求哈希函数的值,然后根据该值寻找相应的桶,最后 只须在该桶中寻找包含给定哈希键值的记录即可。如果我们选取的桶数目B和档案中所有记录的 数目大体相当,那么分配到每个桶的记录数目都会较小,这样在桶内部的搜索速度就会很快。 例1.5 图1-2给出了包含姓名(name)、地址(address)和电话号码(phone)字段的记录的 内存索引结构的大概样子。这里,索引基于电话号码字段构建,而桶采用链表结构。图中展示电 话号码800-555-1212所对应的哈希到桶号码为17。对于桶头(bucket header)构成的数组,其第i 个元素实际上是第i个桶对应链表的头指针。图中展开了链表中的一个元素,它包含姓名、地址 和电话号码字段的一条记录。事实上,该元素对应记录包含的电话号码正好是800-555-1212,但 是该桶中的其他记录可能包含也可能不包含这个电话号码,我们只知道这些记录中的电话号码经 过哈希变换之后结果都是17。 图1-2 一个使用哈希表的索引,其中电话号码经过哈希函数映射到不同桶中, 桶的编号就是哈希结果值 1.3.4 二级存储器 当处理大规模数据时,数据一开始在磁盘还是在内存那么计算的时间开销相差很大,很好地 —————————— ① 由于多条记录可能会哈希到同一个桶中,因此每个桶通常由多条记录所组成的表构成。——译者注 10 第1 章 数据挖掘基本概念 理解这一点相当重要。磁盘的物理特性是另外一个话题,对于这个话题有说不完的内容,但是本 书当中只给出一点点介绍,感兴趣的读者可以按照参考文献的提示查阅相关资料。 磁盘组织成块结构,每个块是操作系统用于在内存和磁盘之间传输数据的最小单元。例如, Windows操作系统使用的块大小为64 KB(即216=65 536字节)。需 要 大 概 10毫秒的时间来访问(将 磁头移到块所在的磁道并等待在该磁头下进行块旋转)和读取一个磁盘块。相对于从内存中读取 一个字的时间,磁盘的读取延迟大概要慢5个数量级(即存在因子105)。因此,如果只需要访问 若干字节,那么将数据放在内存中将具压倒性优势。实际上,假如我们要对一个磁盘块中的每个 字节做简单的处理,比如,将块看成哈希表中的桶,我们要在桶的所有记录当中寻找某个特定的 哈希键值,那么将块从磁盘移到内存的时间会大大高于计算的时间。 我们可以将相关的数据组织到磁盘的单个柱面(cylinder)上,因为所有的块集合都可以在 磁盘中心的固定半径内可达,因此可以不通过移动磁头就可以访问,这样可以以每块显著小于10 ms 的速度将柱面上的所有块读入内存。假设不论数据采用何种磁盘组织方式,磁盘上数据到内存的 传送速度不可能超过100 MB/s。当数据集规模仅为1 MB时,这不是个问题,但是,当数据集在 100 GB或者1 TB规模时,仅仅进行访问就存在问题,更何况还要利用它来做其他有用的事情了。 1.3.5 自然对数的底e 常数e = 2.718 281 8 · · · 具有一些非常有用的特性。具体来讲,e是当x趋向于无穷大时, 11 x x  的极限。当x分别等于1、2、3和4时,上式的值分别近似为2、2.25、2.37和2.44,很容易相信该 序列的极限大概在2.72左右。 一些看上去比较复杂的表达式可以通过代数公式来得到近似值。考虑(1+a)b,其中a很小 (a > 0)。该式子可以重写成(1+a)(1/a)(ab),于是可以将a替换为1/x,即x=1/a,得到 ()11 x ab x  ,即 11 abx x  由于已经假定a很小,所以x很大,因此 11 x x  接近极限e,于是上式可以通过eab来近似。 当a为负值时,类似的等式也成立。也就是说,当x趋向无穷大时, 11 x x  的极限为1/e。于 是,当a是一个绝对值很小的负数时,(1+a)b仍然近似等于eab。换句话说,当a很小b很大时(a > 0), (1a)b近似等于eab。 一些其他有用的等式来自ex的泰勒展开公式,即ex= i=0 !ix i 或者说ex=1+x+x2/2+x3/6+ x4/24+…。当x很大时,上述数列收敛速度较慢。当然对于任何常数x,由 于 n!会比xn增长得快得多, 所以该数列一定会收敛。然而,当x较小时,不论它是正是负,上述数列都会快速收敛,也就是 1.3 相关知识 11 1 2 3 4 5 12 6 7 8 9 10 11 说不需要计算太多项就可以得到较好的近似值。 例1.6 令x=1/2,有 1 2 11 1 1e12 8 48 384     或约为e1/2=1.648 44。 令x = −1,有 1 11 1 1 1 1e112 6 24 120 720 5040         或约为e−1=0.367 86。 1.3.6 幂定律 在很多现象中,两个变量之间通过幂定律(power law,也称幂律)关联起来,也就是说, 两个变量在对数空间下呈现出线性关系。图1-3给出了这样的一种关系。该图中横坐标x和纵坐标 y之间的关系为log10y = 62log10x。 图1-3 一个斜率为2的幂定律关系图 例1.7 我们来考察Amazon.com上的图书销售情况,令x表示图书的销量排名,y对应的是销 售排名为x的畅销图书在某个时间段的销量。图1-3表明,销售排行第1位的图书的销量是1 000 000 册,而排行第10位的图书的销量为10 000册,排行第100位的图书销量为100册,以此类推可以得 出排名中所有图书的销量。从图中可以看到,排名超过1000的图书的销量是一个分数,这有些极 端,实际上我们预测排名远远超过1000的图书销量的曲线应该变得比较平。 12 第1 章 数据挖掘基本概念 马太效应 当幂值大于1时,幂定律的存在往往通过马太效应(Matthew effect)来解释,在《圣经·马 太福音》中,存在关于“富者越富”的一段话。很多现象都表现出类似特性,即一旦在某个特 性获得高价值,那么会导致该特性获得更大的价值。例如,如果某个Web网页有很多入链,那 么人们更可能找到该网页并从他们自己的某个网页链向它。另一个例子是,如果一本书在 Amazon上卖得很好,那么它很可能会登广告,而当顾客访问Amazon网站时会看到这则广告, 其中的一些人会选择购买这本书,从而造成销量的继续增长。 关于x和y的幂定律的一般形式为logy=b+alogx,如果增大对数的底(实际上没有影响),比如 采用自然对数e作为方程两边的值,则有y=ebealog x=ebxa,由于eb是一个常数,所以可以用常数c代 替,于是幂定律可以写成y=cxa ,其中a和c都是常数。 例1.8 在图1-3中,当x=1时y=106,当x=1000时y=1。第一次代入后有106=c,第二次代入 后有1=c(1000)a,我们知道c=106 ,通过第二次代入后,得出1=106(1000)a,于是 a=2。也就是说, 图1-3表示的幂定律可以表示为 y=106x−2或 y=106/x2。 本书中将有多处数据都满足幂定律,举例如下。 (1) Web图当中节点的度 按照网页的入链数对所有网页排序,令x为网页在排序结果的序 号,y为序号为x的网页的入链数。则y和x之间的关系和图1-3非常类似,只是这里的幂要稍大于图 中的幂2,已经发现在这种现象中的幂值接近2.1。 (2) 商品的销量 将商品(如Amazon.com上的图书)按照去年一年的销量多少来排序,假定 销量第x位的商品的实际销量为y。那 么y和x的函数关系和图1-3也类似。在9.1.2节中,我们将讨论 这种销量分布的影响,那时我们还会提到其中的“长尾”现象。 (3) Web网站的大小 计算Web站点上的网页数目,根据该数目对网站排序。假定第x个网 站的网页数目为y,那么函数y(x)也服从幂定律。 (4) Zipf定律 该幂定律最初来源于文档集中的词频统计。如果将词语按照出现频率排序,y 表示排名第x位的词出现的次数,则可以得到一个幂定律,不过其坡度比图1-3的要平缓得多。Zipf 的观察结果为y = cx1/2。有趣的是,有不少其他类型的数据也满足这个特定的幂定律。比如,如 果将美国的州按照人口数量排序,令y为人口第x多的州的人口数,则y和x近似地满足Zipf定律。 1.3.7 习题 习题1.3.1 假定一个由1000万篇文档组成的文档集,如果单词出现在(a)40篇或(b)10 000篇 文档中,那么它的IDF值是多少(给出最接近的整数值)? 习题1.3.2 假定一个由1000万篇文档组成的文档集,某个词w出现在其中的320篇文档中。 且在一篇具体的文档d中,出现最多的词出现了15次,那么w出现(a)1次或(b)5次情况下的TF.IDF 得分分别是多少? !习题1.3.3 假定哈希键都来自某个常数c的所有非负整数倍,而哈希函数为h(x)= x mod 15, 1.4 本书概要 13 1 2 3 4 5 12 6 7 8 9 10 11 那么常数c取何值时,h是一个合适的哈希函数?也就是说,此时大量随机的哈希键选择能够近 乎均匀地分到不同桶当中。 习题1.3.4 基于e的形式来近似表示下列数值。 (a) (1.01)500 (b) (1.05)1000 (c) (0.9)40 习题1.3.5 采用ex的泰勒展开公式计算下列表达式直到小数点后3位小数。 (a) e1/10 (b) e−1/10 (c) e2 1.4 本书概要 本节主要给后续章节做一个简单的总结。 就其本身而言,第2章本身的内容与数据挖掘无关。更确切地说,第2章主要介绍用于云计算 框架(由处理器互联的很多机架构成)下并行处理的MapReduce方法。有理由相信,当分析的数 据量非常大的时候,云计算特别是MapReduce将会成为数据计算的常规做法。在后续章节当中一 个普遍的话题就是基于MapReduce方法来实现书中介绍的算法。 第3章的主题是相似项发现。一开始每个项都表示成多个元素的集合,而相似集合就是具有 大部分公共元素的集合。第3章还解释了最小哈希和局部敏感哈希技术,这些技术应用很广,并 且往往给那些大数据集上看似不可能解决的问题带来出奇高效的解决方案。 第4章考虑数据流或者叫流数据。流数据和数据库的区别在于如果不及时处理流数据那么这 些数据将会丢失。流数据的一些重要例子包括搜索引擎上的搜索查询或者某个热门Web网站上 的点击数据等。本章将介绍哈希技术的几个令人惊讶的应用,在这些应用当中,哈希技术使得流 数据的管理成为可能。 第5章仅仅致力于PageRank计算这个应用。PageRank的计算是Google脱颖而出的一个重要思 想,并且PageRank仍然是搜索引擎知道用户最想访问哪些网页的关键。PageRank的扩展形式在反 网页垃圾中(制造网页垃圾的另一个委婉的说法是“搜索引擎优化”①)也非常重要,我们将介 绍该思想在反垃圾领域的一种最新扩展形式。 第6章介绍数据的购物篮模型、最典型的关联规则问题及频繁项集发现算法。在购物篮模型 中,数据由大量购物篮组成,每个购物篮中包含少量项组成的项集。本章将给出一系列频繁项对 发现的算法,其中频繁项对指的是那些同时出现在多个购物篮中的项。另外,本章还给出一系列 用于发现大部分频繁项集②(比频繁项对大)的高效算法。 第7章考察聚类问题。假定有一个项集,两个项的远近可以通过某个距离指标来定义。聚类 的目标是将大量的数据项划分到子集合(称为簇)中,使得簇内数据项的距离较近,而簇间的数 据项距离较远。 第8章主要考察在线广告及由其引发的计算问题。本章将介绍在线算法的概念,即必须立即 —————————— ① 搜索引擎优化(Search Engine Optimization, SEO)是通过各种方法来提高网页排名的做法。需要指出的是,SEO 并不都是通过制造网页垃圾的手段来实现的。这里作者的说法有点绝对,并不代表译者的观点。——译者注 ② 频繁项对考虑两个项共现,频繁项集可能考虑3个或者更多项的共现。——译者注 14 第1 章 数据挖掘基本概念 给出一个好的回复而不需要一直等到看见全部数据集才回复。竞争率(competitive ratio)是本章 中的另一个重要概念,它是在线算法所保证的性能和最优算法性能的比率,所谓最优算法指的是 允许在看到所有数据之后再做决策的算法。上述概念用于设计良好的算法,当用户在搜索引擎输 入查询时,这些算法能够与广告商的出价匹配来显示相应的广告。 第9章介绍推荐系统。很多Web应用中都有给用户推荐其感兴趣的数据项的功能。Netflix竞赛 就是一个例子,该竞赛期望对用户感兴趣的电影进行预测。而Amazon希望根据顾客的购买兴趣 来推荐一款商品。推荐主要有两种方法。一种方法是,我们可以将数据项通过其特征来刻画,比 如电影中的明星,然后推荐与已知的用户喜欢的物品具有同样特征的物品。另一种方法是,我们 可以考察那些与当前用户具有相似爱好的用户,根据他们喜欢的物品来向当前用户推荐(该技术 通常称为协同过滤)。 第10章介绍社会网络及分析算法。最典型的社会网络的例子是Facebook的朋友关系图,其中 节点代表人,而两个人如果是朋友的话,他们之间就有边相连。而像Twitter上的粉丝关注构成的 有向图也可以看成社会网络。社会网络中一个要解决的普遍问题是识别其中的“社区”,即一个 个小规模的节点集合,但是集合内节点之间却有大量的边将它们连接起来。社会网络的其他问题 也是图的一般性问题,比如传递闭包或图直径的计算,但是在网络规模如此巨大的情况下问题也 变得十分困难。 第11章介绍降维技术。给定一个极大的、通常比较稀疏的矩阵。我们可以将该矩阵想象为两 类实体之间的关系表示,比如观众对影片的评级关系。直观上看,只会存在很少量的概念,而且 概念的数目会比影片或观众的数目少很多,这些概念可以解释为什么某些观众喜欢某些影片。我 们提供了多个将矩阵简化为多个矩阵的乘积的算法,简化后的矩阵某一维要小很多。其中,一个 矩阵将一类实体与这些少量的概念相关联,另一个矩阵将概念和另一类实体相关联。如果处理正 确的话,这些小矩阵的乘积会十分接近原始矩阵。 最后,第12章讨论极大规模数据集上的机器学习算法。其中的技术包括感知机、支持向量机、 基于梯度下降的模型求解、近邻模型和决策树等。 1.5 小结  数据挖掘 这个术语是指从数据中提取有用模型的过程。提出的模型有时可以是数据的 一个汇总结果,而有时可以是数据中极端的特征所组成的集合。  邦弗朗尼原理 在考察数据时,如果将某些对象视为数据的有趣特征,而这些对象中的 许多实例都可能会在随机数据中出现,那么这些显著的特征就不可依赖。对于那些实际 中并不充分罕见的特征来说,上述观察结果限制了从这些数据特征中进行挖掘的能力。  TF.IDF指标 TF.IDF可以帮助我们确定文档集中哪些词语对于确定每篇文档主题有用。 如果某个词在少量文档当中频繁出现时,那么它在文档中的TF.IDF值较高。  哈希函数 哈希函数可以将某种数据类型的哈希键映射为整型的桶编号。好的哈希函数 能够将所有可能的哈希键值相对均匀地分到不同的桶中。哈希函数能够对任意数据类型 1.6 参考文献 15 1 2 3 4 5 12 6 7 8 9 10 11 进行处理。  索引 索引是在给定一个或多个字段值时进行高效记录存取和检索的一种数据结构。哈 希是构建索引的一种方式。  磁盘存储 当数据必须存储在磁盘(二级存储器)时,期望的数据项的访问时间会大大 高于同样的数据存储在内存中的访问时间。当数据很大时,算法应该尽量将所需数据放 入内存,这一点相当重要。  幂定律 也称幂律。很多现象都服从一个可表示成 y = cxa 的定律,其中a是幂,一个通 常的取值是在2左右。包括销量排名第x位的图书销量或排名第x位的网页的入链数等在 内的数据都服从幂定律。 1.6 参考文献 文献[7]是一部非常清晰的介绍数据挖掘基础知识的文献。文献[2]主要从机器学习和统计学 的角度来介绍数据挖掘。 对于哈希函数和哈希表的构建,可以参考文献[4]。TF.IDF指标的计算细节以及文档处理的其 他相关知识可以参考文献[5]。索引管理、哈希表和磁盘数据处理的相关知识可以参考文献[3]。 文献[1]探讨了Web图结构所满足的一些幂定律。马太效应最早见于文献[6]。 [1] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Weiner, “Graph structure in the web,” Computer Networks 33:1–6, pp. 309–320, 2000. [2] M.M. Gaber, Scientific Data Mining and Knowledge Discovery – Principlesand Foundations, Springer, New York, 2010. [3] H. Garcia-Molina, J.D. Ullman, and J. Widom, Database Systems: The Complete Book Second Edition, Prentice-Hall, Upper Saddle River, NJ, 2009. [4] D.E. Knuth, The Art of Computer Programming Vol. 3 (Sorting and Searching), Second Edition, Addison-Wesley, Upper Saddle River, NJ, 1998. [5] C.P. Manning, P. Raghavan, and H. Schüutze, Introduction to Information Retrieval, Cambridge University Press, 2008. [6] R.K. Merton, “The Matthew effect in science,” Science 159:3810, pp. 56–63, Jan. 5, 1968. [7] P.-N. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining, Addison-Wesley, Upper Saddle River, NJ, 2005. 10.1 将社会网络看成图 265 1 2 3 4 5 12 6 7 8 9 10 11 社会网络图挖掘 通过分析来自社会网络的大规模数据可以获得大量信息。最著名的社会网络的例子是诸如 Facebook之类的网站上的“朋友”关系。然而,正如我们将要看到的那样,还有很多其他数据源 将人或其他实体连接在一起。 本章将介绍这种网络的分析技术。社会网络中的一个重要问题是识别“社区”。而 所 谓 的“ 社 区”,是指具有非同寻常的强连通性的节点子集(节点可以是构成网络的人或其他实体)。有些社 区识别技术与第7章所讨论的聚类技术十分类似。但是,社区并非要将网络节点截然分开,事实 上它们之间通常存在交集。举例来说,你可能属于多个朋友或校友社区。同一社区的人通常互相 认识,而不同社区的人很少会认识对方。你可能不希望自己只属于一个社区,而将你所在各个社 区的所有人归入一类也是不合理的。 本章还会探讨图的其他性质的高效发现算法。我们将讨论simrank算法,它用于计算图中节 点之间的相似度。我们将通过三角形计数来度量社区的连通性(connectedness)。我们会给出图 节点邻居大小(neighborhood size)的高效精确或近似度量算法。最后将考察传递闭包的高效计 算算法。 10.1 将社会网络看成图 下面通过引入一个图模型来展开社会网络的讨论。并非所有的图都适合于表示我们直观所认 为的社会网络。因此,我们会讨论一种所谓“局部性”(locality)的思想。这里的局部性指社会 网络的节点和边趋向于聚为社区的这种性质。本节还会介绍实际中几种类型的社会网络。 10.1.1 社会网络的概念 当我们考虑社会网络时,往往会想起Facebook、Twitter、Google+或者其他被称为“社交网 络”的网站。实际上,这类网络确实是一大类被称为“社会网络”的网络的典型代表。社会网络 的基本特点如下。 (1) 一大堆实体参与了网络的构成。通常,这些实体是人,但是完全也可以是其他的对象。 10.1.3节会讨论一些其他对象的例子。 (2) 网络实体之间至少存在一种关系。在Facebook及同类网站当中,这种关系称为“朋友” 第10章 266 第10 章 社会网络图挖掘 关系。有时这种关系要么存在要么不存在,比如两个人要么是朋友要么不是。然而在其他一些社 会网络的例子当中,关系存在一个度数(degree)。这个度数可以是离散型数据,比如在Google+ 中的朋友、家人、熟人等关系或者没有关系。度数也可以是一个实数值,一个例子就是两个人聊 天的日平均用时比率。 (3) 对于社会网络有一个非随机性或局部性假设。该条件最难形式化,其直观意义是关系倾 向于聚团。也就是说,如果实体A与B和C都关联,那么B和C相互关联的概率会高于平均值。 10.1.2 将社会网络看成图 社会网络可以很自然地采用图来建模,该图有时也称为社会图(social graph)。其中,图的 节点为实体,如果节点之间存在刻画该网络的关系,那么节点之间有一条边。如果关系存在强弱 之分,那么每条边上还标识出关系的强弱程度。社会图通常是无向图,比如Facebook中的朋友图。 但是,社会图也可以是有向图,比如Twitter或Google+中的粉丝关注图。 例10.1 图10-1是一个微型社交网络的例子。实体从A编号到G。其中可以想象为“朋友” 的关系用边来表示。比如,B与A、C、D都是“朋友”。 图10-1 一个微型社会网络的例子 那么,从能否展示关系的局部性这个意义上来说,上图能否看成一个典型的社会网络呢?首 先,上图包含9条边,而节点之间所有可能的边数为 7 212  。假 设X、Y、Z是图10-1的三个节点, 其中X、Y及X、Z之间都有连边,那么Y和Z之间存在连边的期望概率是多少?如果图很大,那么 上述概率会十分接近于所有可能节点对中存在连边的比例,即上图中该概率为9/21=0.429。然 而 , 由于上图很小,真实概率和所有可能节点对中连边的比例之间存在显著差异。由于已知存在边 (X,Y)和(X,Z),因此只剩余7条边。这7条边可以存在于剩余的19对节点①中任意一对之间。因此, (Y,Z)之间存在边的概率是7/19=0.368。 下面,我们必须计算图10-1中存在边(X,Y)和(X,Z)时边(Y,Z)也存在的概率。我们不需要担心哪 个节点是Y哪个是Z,只需要实际数一下可能是Y和Z的节点对数即可。如果X是A,那么Y和Z肯定 分别是B和C或者C和B。由于边(B,C)存在,A贡献了一个正例(即存在边)并且没有贡献任何反 例(即不存在边)。X分别为C、E、G时的情况本质上和为A时相同。每种情况下,X只有两个邻 —————————— ① 因为图中总共有9条边,除去(X,Y)和(X,Z)这两条边之后,还剩下7条边,当然也就剩下212=19对节点。 ——译者注 10.1 将社会网络看成图 267 1 2 3 4 5 12 6 7 8 9 10 11 居节点,且这两个邻居节点之间存在连边。因此,迄今为止我们有4个正例和0个反例。 接下来考虑X=F的情况。F有3个邻居节点D、E、G。在三对邻居节点之间存在两条边,但是 G和E之间不存在连边。因此,这里增加了2个正例,同时也增加了第一个反例。当X=B时,仍然 有3个邻居节点,其中只有一对邻居节点A和C之间有边。因此,这里又增加了2个反例和1个正例。 于是到此为止我们得到7个正例和3个反例。最后,当X=D时,有4个邻居节点,而在6对邻居之间 只有两条边。 因此,上图中的正例总数为9,反例总数为7。回到图10-1,于是第三条边存在的比例为 9/16=0.563。该比例显著高于期望值0.368。所以,我们的结论是,图10-1确实表现出社会网络中 期望出现的局部性。 10.1.3 各种社会网络的例子 存在各种各样的社会网络而不仅限于“朋友”网络。下面,我们列举其他一些同样存在关系 局部性的网络的例子。 1. 电话网络 在该网络中节点是电话号码,代表一系列真实的个体。如果在某个固定时段内(比如上个月 或者“曾经”)两个电话之间通过话,那么两个电话号码之间就有边。边的权重可以通过时段内 的通话次数来表示。电话网络中的社区由通话频繁的人群组成,例如朋友、俱乐部会员或公司同 事构成的社区。 2. 电子邮件网络 该网络中的节点是电子邮件地址,同样也代表一系列个体。边表示在两个地址之间至少单方 向发送过至少一封电子邮件。另一种做法是只有在双方互发过邮件时才放置一条边。这种做法可 以避免将垃圾邮件发送者看成他们发送对象的“朋友”。还有一种做法是将边标识为弱关系或强 关系。其中强关系标识双方互发过邮件,而弱关系表示只有单方向的邮件发送。电子邮件网络中 的社区和刚才提到的电话网络基本相同。一个与电子邮件网络十分类似的网络是手机短信网络。 3. 合作网络 该网络中的每个节点代表发表论文的一个作者。如果两个作者联合发表一篇或者多篇论文, 那么这两个作者之间有连边。一种可选的做法是将两者共同发表的论文数目标识在边上。该网络 中的社区是研究某个特定主题的研究人员集合。 对相同数据也可以采用另一种视角,即图中的节点由论文构成。如果两篇论文至少有一名作 者相同,则建立连边。这种网络下的社区是有关同一主题的论文集合。 还有一些其他类型的数据也能构成和上述类似的两个网络。例如维基百科文章的编辑人员或 他们所编辑的文章本身。如果两个编辑人员编辑过同一篇文章,则他们之间有连边。这里的社区 则是对同一话题感兴趣的编辑人员的集合。类似地,也可以构建以文章为节点的网络,如果两篇 文章被同一人员编辑过,则它们之间有连边。这样构建得到的网络社区则是有关相似或相关话题 的文章集合。 268 第10 章 社会网络图挖掘 实际上,第9章给出的协同过滤数据往往也可以看成一对网络,其中一个是顾客网络,而另 一个是产品网络。购买同类产品(如科幻小说)的顾客构成一个社区,类似地,相同顾客购买的 产品也构成一个社区(如所有的科幻小说)。 4. 其他社会网络的例子 很多其他现象也会产生具有局部性的类似社会网络图的图,比如信息网络(文档、Web图、 专利)、基础设施网络(道路、航线、水管、电网)、生物网络(基因、蛋白、动物之间的食物链) 以及其他类型的网络,例如商品团购网络(如Groupon)。 10.1.4 多类型节点构成的图 有些社会现象会涉及多个不同类型的实体。我们在“合作网络”部分刚刚提到,有些网络实 际由两类节点构成。论文作者网络可以看成包含作者节点和论文节点的网络。上面的讨论中,我 们摒除一类节点而只基于另一类节点来构建网络,但是并不一定要那么做。相反,我们可以将结 构看成一个整体。 下面给出一个更复杂的网络的例子,该例子中用户在诸如deli.cio.us的网站上放置Web网页的 标签。于是,这里存在三类实体:用户、标签和网页。如果用户倾向于频繁使用相同标签,或者 倾向于标注相同网页,则可以认为用户之间存在某种程度的关联。类似地,如果标签出现在相同 网页中或者被相同用户所使用,则可以认为它们之间有关系。而网页之间如果共享很多相同标签 或者被很多相同用户所标注,则认为它们相似。 表达上述信息的一个自然的方式是k部图(k-partite graph),其中k为大于1的整数。在8.3节我 们曾经遇到过二部图,即k=2时的k部图。一般而言,一个k部图包含k个不相交的节点集合,其中 同一节点集合内的节点之间没有连边。 例10.2 图10-2给出了一个三部图(即k=3时的k部图)的例子。其中包含三个节点集合:用 户集合{U1, U2}、标签集合{ T1, T2, T3}及网页集合{ W1, W2, W3}。注意,这里所有的边连接了来自 不同集合的节点。我们假设图10-2代表三类实体的信息。例如,边(U1, T2)表示用户U1至少在一个网 页中给出了标签T2。需要注意的是,这张图忽略了一个可能十分重要的信息:谁对哪个网页标注了 什么标签?为表达这种三元信息,可能需要一个三列分别对应用户、标签和网页的数据库关系。 图10-2 一个包含用户、标签和Web网页三类节点的三部图 10.2 社会网络图的聚类 269 1 2 3 4 5 12 6 7 8 9 10 11 10.1.5 习题 习题10.1.1 可以将图G的边看成是另一个图G'的节点。具体地,可以采用如下的对偶构 建法(dual construction)将G转换为G'。 (1) 如果(X,Y)是G的一条边,则XY构成的无序集合为G'的一个节点。这里要注意的是,XY和 YX在G'中代表同一节点而不是两个不同的节点。 (2) 如果(X,Y)和(X,Z)是G的两条边,那么G'中存在一条从XY到XZ的边。也就是说,如果G中 有两条边共享同一节点,那么这两条边对应的G'中的节点之间有一条边。 (a) 如果将上述构建法用于某个朋友网络,那么结果图中的边代表什么含义? (b) 将上述构建法应用于图10-1。 !(c) G'中的节点XY的度与G中节点X和Y的度之间有什么关系? !!(d) G'中的边数和G中节点的度之间存在某种关系,试推导出该关系公式。 !(e) 上述转换虽然称为对偶构建法,但并不是一个真正的对偶法。这是因为对G'应用上述转 换并不一定能得到一个与G同构的图。试给出两个G的例子,前一个例子中对G'应用上述转换能 够得到与G同构的图,而后一个例子中做同样处理却得不到与G同构的图。 10.2 社会网络图的聚类 社会网络的一个重要性质是图中包含实体社区,每个社区由很多边互连而成。例如,学校中 的朋友圈或者对相同主题感兴趣的研究人员就是典型的社区代表。本节将考察用于社区识别的图 聚类算法。事实表明,第7章学过的技术通常并不适用于社会网络图的聚类问题。 10.2.1 社会网络图的距离计算 如果我们将常规的聚类算法用于社会网络图,那么第一步就是定义距离。当边上有权重标识 时,这些标识也许可以用于距离计算,当然这取决于这些标识所代表的具体含义。但是,当这些 边上并不存在标识时(比如“朋友”网络图),那么要定义合适的距离我们所能做的就不多。 第一直觉就是,如果两个节点之间有边,则假定它们之间的距离近,否则假定它们之间的距 离远。因此,我们可以说如果存在边(x,y),那么距离d(x,y)为0,否则d(x,y)为1。我们也可以用其 他的两个值来代表上述两种情况,只要满足存在边时距离近的条件即可,比如1和∞。 上述两组二值“距离”,即01和1∞都不是真正意义上的“距离”。其原因在于,当三个节点 之间存在两条边时上述定义都违背了三角不等式。也就是说,如果存在边(A,B)和(B,C),但不存 在边(A,C),那么按照上述定义,A到C的距离将大于A到B的距离与A到C的距离之和。对于该问题 我们通过某种方式来解决,比如有边时距离定义为1,否则定义为1.5。但是在下一节我们将会看 到,基于二值定义的距离并不仅仅违反三角不等式。 270 第10 章 社会网络图挖掘 10.2.2 应用标准的聚类算法 我们还记得,7.1.2节中将聚类分成两类一般性方法,一类是层次(凝聚)法,另一类是点分 配法。下面将考虑如何在社会网络上运行这两类方法。首先考虑7.2节介绍的层次方法。具体说 来,在聚类算法中假定两个簇之间的距离为两个簇间所有节点的最短距离。 对社会网络图进行层次聚类,首先将两个有边连接的节点聚成一类。随后,不在同一簇内节 点之间的边将被随机选出,来合并这两个节点所属的簇。这个过程将反复进行下去。上述选择之 所以随机,是因为每条边所代表的距离都一样。 例10.3 再回头考虑图10-1,这里将该图复制为图10-3。我们先就社区的构成达成一致。在 最高层次上来说,看上去存在两个社区{A,B,C}和{D,E,F,G}。然而,我们也可以将{D,E,F}和{D,F,G} 看成{D,E,F,G}的子社区,这两个子社区之间共享了一个成员。而采用纯聚类算法永远不可能识 别出这种重叠社区。最后,尽管不太有趣,但是我们可以将任意存在连边的节点看成一个2元素 社区。 图10-3 图10-1的复制图 对类似图10-3中的图进行层次聚类的一个问题就是,在某个点我们可能想将B和D合并,尽管 它们实际属于两个簇。可能将B和D进行合并的原因在于,D或者任意包含D的簇与B或任意包含B 的簇的距离,与A和C到B的距离一样近。甚至有1/9的概率首先将B和D合并。 有一些办法可以降低发生错误的概率。我们可以运行多次层次聚类算法,选择最具紧致性 (coherent)的聚类结果。我们也可以选择一个更复杂的方式来计算多于一个节点的簇之间的距离 (参考7.2.3节)。不管如何处理,在一个有多个社区的大型图当中,在初始阶段都很有可能使用某 些不属于任一大社区的两个节点构成的边。 下面考虑使用点分配方法对社会网络进行聚类。同样,所有的边等距离这一事实会引入一系 列随机因素,这些因素会导致节点的错误聚类结果。下面给出了一个例子。 例10.4 假定采用k均值方法来对图10-3进行聚类。我们假定输出结果为2个簇,即设定k=2。 如果随机地选择两个起始节点,那么它们有可能属于同一簇。如果采用7.3.2节中的方法,即先随 机选择一个节点,然后选择一个离它尽可能远的节点,结果也不会好太多。于是我们可能选择出 任意一对没有互连的节点,比如图10-3中的E和G。 然而,假定我们确实找到了两个合适的初始节点,比如说B和F。然后将A和C分配给B,将E 和G分配给F。但是,由于D与B的距离等于其与F的距离,因此尽管D“明显”属于F,但D既可 以分配给B也可以分配给F。 10.2 社会网络图的聚类 271 1 2 3 4 5 12 6 7 8 9 10 11 如果先分配某些其他的点之后再决定D的归属的话,那么就有可能将D归于正确的簇。例如, 如果将节点分配给到簇内所有节点平均距离最短的那个簇,那么只要不在其他任一节点分配之前 分配D,就能将D分配给F簇。但是,在大型图当中,开始的某些节点肯定会发生分配错误。 10.2.3 中介度 由于使用传统的聚类算法对社会网络进行聚类会存在不少问题,有人提出了多种发现社会网 络社区的专用聚类技术。本节将讨论其中最简单的一种,该方法寻找那些至少可能属于同一社区 的边。 一条边(a,b)的中介度(betweenness)定义为节点对(x,y)的数目,其中(a,b)处于x和y的最短路 径上。更精确地说,由于x和y之间可能存在多条最短路径,边(a,b)的贡献记为这些路径中通过边 (a,b)的比例。如同高尔夫一样,高分意味着成绩差。如果边(a,b)的得分高,那么意味着它处于两 个社区之间,也就是说a和b不属于同一社区。 例10.5 图10-3中边(B,D)的中介度最高,这一点任何人都不会惊讶。实际上,这条边位 于A、B、C中任意一点到D、E、F、G中任意一点之间的最短路径上。因此,其中介度为3× 4=12。与此形成对照的是,边(D,F)只在4条最短路径上,即A、B、C和D分别到F。 10.2.4 Girvan-Newman算法 为了利用边的中介度,必须要计算所有边上的最短路径数目。下面将介绍一个称为 Girvan-Newman(简称GN)的算法,该算法访问每个节点X一次,计算X到其他连接节点的最短 路径数目。算法首先从节点X开始对图进行宽度优先搜索(BFS)。注意在BFS表示中,每个节点 的深度就是该节点到X的最短路径长度。因此,处于同一深度的两个节点之间的边永远都不可能 处于X到其他点的最短路径上。 不同深度节点之间的边称为DAG(Directed Acyclic Graph,有向无环图)边。每条DAG边将 至少处于一条到根节点X的最短路径上。如果存在一条DAG边(Y,Z),其中Y在Z上一层(即Y离根 节点更近),那么就把Y称为Z的父节点而把Z称为Y的子节点。需要指出的是,DAG中的父节点并 不一定像树结构中那样只有唯一的一个。 例10.6 图10-4是图10-3的一个以节点E开始的宽度优先表示结果。实线边表示DAG边,而 虚线边连接的是同层的节点。 GN算法的第二步是将每个节点用根节点到它的最短路径的数目来标记。首先,将根节点标 记为1,然后从上往下,将每个节点Y标记为其所有父节点上的标记值之和。 例10.7 图10-4给出了每个节点的标识值。首先,根节点E标识为1。第一层的两个节点D和 F的父节点都只是E,因此它们都标为1。第二层的节点是B和G,B的父节点只有D,因此B和D的 标记一样都是1。而G的父节点为D和F,因此其标记为D和F的标识之和,即2。最后,第三层中 的节点A和C的父节点都仅为B,因此它们与B的标记一样,都是1。 272 第10 章 社会网络图挖掘 图10-4 GN算法第一步的结果示意图 GN算法的第三步也是最后一步是对每条边e,对所有节点Y,计 算 Y到根节点X经过e的最短路 径比例之和。上述计算包括自下而上对节点和边的求和过程。除去根节点之外的每个点都给个分 值1,表示到该节点的最短路径。由于到该节点可能存在多条最短路径,上述分值可能被上面的 节点和边所瓜分。整个计算的规则如下: (1) DAG中的每个叶节点(叶节点指的是那些与下层节点之间不存在DAG边的节点)都赋予 分值1。 (2) 每个非叶节点给的分值是1加上从该节点到其下层节点的所有DAG边的分值之和。 (3) 从上层节点到达下层节点Z的DAG边上的分值为Z的分值乘上从根节点到Z的最短路径中 包含e的比例。形式上,假定Z的父节点为Y1, Y2, …, Yk,再假定从根节点到Yi的最短路径数目为pi, 该值在第二步计算得到,图10-4给出了计算的示意图。于是,边(Yi,Z)的分值为Z乘上pi除以 1 k jj p 。 当将每个节点都作为根节点计算一遍之后,将每条边的分值求和。由于每条最短路径会重复 发现两次(其中每一次分别以不同节点为根节点),因此最后每条边的分值还要再除以2。 例10.8 下面对图10-4的BFS表示进行分值计算。我们从第三层开始自下而上进行计算。首 先,叶节点A和C会得到分值1。由于这两个节点的父节点都只有1个,因此将它们的分值分别赋 予边(B,A)和(B,C)。 第2层中,G是叶节点,因此其分值为1。B不是叶节点,因此其分值为1加上下层到达B的DAG 边的分值之和。由于下层到达B的两条DAG边的分值均为1,因此,B的分值为3。很直观,3表示 E到A、B、C的最短路径都经过B这个事实。图10-5展示了迄今为止的分值分配情况。 接下来处理第一层。B只有一个父节点D,于是边(D,B)获得B的全部分值3。但是,G有两个 父节点D和F,因此需要将G的分值1分给边(D,G)和(F,G)。那么这里分配的比例如何呢?如果考察 图10-4中的标识值,会发现D和F的标识值都是1,这表明从E到D和F都有一条最短路径。因此, 将G的分值均分给这两条边,即每条边上分配1/(1+1)=0.5。如果图10-4中D和F上的标识值分别为 5和3的话,那么意味着有5条最短路径到D,而只有3条到F,于是边(D,G)上将会分配5/8的分值, 10.2 社会网络图的聚类 273 1 2 3 4 5 12 6 7 8 9 10 11 而边(F,G)上只分配3/8的分值。 图10-5 GN算法的最后一步:第3层和第2层的结果 现在我们可以给第一层的节点分配分值。D等于1加上下一层到它的两条边上的分值3和 0.5。于是D的分值最终为4.5。而F的分值为1加上边(F,G)的分值,结果为1.5。最后,由于D和F 都只有一个父节点,因此,边(E,D)和(E,F)上分别接受D和F的分值。所有这些分值的结果展示在 图10-6中。 图10-6 GN算法的最后一步:所有分值计算的结果示意图 图10-6中每条边上的分值代表的是从E出发的最短路径来计算的中介度贡献值。例如,边(E,D) 的贡献值为4.5。 为完成中介度计算,我们必须以每个节点为根节点重复上述计算过程,并对计算得到的贡献 值求和。最后,必须要将这些和除以2才能得到真正的中介度值,这是因为每条最短路径都计算 了两次,每次分别以路径的一个端点作为根节点。 274 第10 章 社会网络图挖掘 10.2.5 利用中介度来发现社区 图中边上的中介度有点像节点之间的距离。由于它在无连接边的两个节点上没有定义,并且 即使定义也可能不满足三角不等式,因此它并不是严格意义上的距离。然而,我们可以按照中介 度升序对边进行聚类处理并将它们逐次加到图中。每一步中,图的连通分量构成某些簇。所允许 的中介度越大,得到的边就越多,获得的簇也越大。 更常见的做法是将上述想法表示成一个去边过程。从一个包含全部边的图开始,不断去掉具 有最高中介度的边,直到图分裂为合适数目的连通分量为止。 例10.9 假定对图10-1进行处理。图10-7中只列出了图中每条边的中介度,而具体的计算过 程留给读者。数值中唯一微秒的部分在于,我们观察到E和G之间存在两条最短路径,一条经过D 而另一条经过F。因此,边(D,E)、(E,F)、(D,G)和(G,F)上的得分值都是其对应最短路径的一半。 图10-7 图10-1中所示图上所有边的中介度 很显然,边(B,D)的中介度最高,因此首先去掉这条边。这样处理之后得到了我们感觉最具 意义的两个社区:{A,B,C}和{D,E,F,G}。接下来我们可以继续进行去边处理。按照中介度高低, 依次去除的是两条5分的边(A,B)和(B,C),然后是两条4.5分的边(D,E)和(D,G),再之后是4分的边 (D,F)。于是,剩下的图如图10-8所示。 图10-8 去除中介度不小于4的边之后的图 图10-8得到的“社区”看上去有点奇怪。该图意味着相对于B而言,A和C之间关系更加紧密。 也就是说,由于B在社区{A,B,C}外有一个朋友D,因此它在某种意义上是该社区的“背叛者”。 同理,D也可以看成社区{D,E,F,G}的“背叛者”,这也是在图10-8中这几个节点之间只有E、F和 G仍然连通的原因。 10.3 社区的直接发现 275 1 2 3 4 5 12 6 7 8 9 10 11 中介度计算的加速处理 如果利用10.2.4节的方法对有n个节点e条边的图进行处理,那么计算所有边的中介度需要 O(ne)的时间。也就是说,从单个节点出发采用BFS需要O(e)的时间来进行两步标识。而我们必 须从每个节点出发,因此在10.2.4节中需要n次计算过程。 如果图很大(在O(ne)的计算复杂度下,即使100万节点都算大),那么我们无法承受上述 计算过程。然而,如果我们随机选择某个节点子集作为深度优先搜索的根节点,那么就可以得 到每条边中介度的近似结果,这种做法在很多应用中被实际采用。 10.2.6 习题 习题10.2.1 图10-9给出了一个社会网络图的例子。利用GN算法寻找从以下节点开始经过 每条边的最短路径的数目: (a) A (b) B 图10-9 习题中用的图 习题10.2.2 利用对称性计算习题10.2.1中所有边的中介度。 习题10.2.3 利用习题10.2.2中计算出的中介度,对图10-9进行去边处理,在某个阈值上得 到合理的社区结果。 10.3 社区的直接发现 前面一节当中,我们通过划分社会网络中的节点来得到社区。虽然这种做法相对比较高效, 但是它有很多局限性。它不可能把一个节点分配到两个社区中,这导致每个节点最终都分配到各 自社区中。本节将会介绍一种通过寻找有很多连边的节点子集直接发现社区的技术。有趣的是, 在大规模图上应用该技术会涉及第6章讨论的大规模频繁项集的发现过程。

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 2 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档

相关文档