搜索引擎中的大数据挖掘

1、搜索引擎中的大数据挖掘大数据核心技术之数据挖掘与机器学习技术探索及应用为什么花这么多时间讲搜索引擎？ 搜索引擎是大数据数据挖掘的肇事者和集大成者 1998年：150 millions pages 1.5T 2003年：单月处理3288T数据 2008年：1万亿 pages为什么花这么多时间讲搜索引擎？ 搜索引擎是大数据数据挖掘的肇事者和集大成者大规模检索 大规模文本分析 大规模图算法 百度识图 欠缺的：更复杂的现实世界数据搜索引擎的三个核心体验 相关 权威 命中焦点搜索引擎的三个核心体验 相关搜索引擎的三个核心体验 权威搜索引擎的三个核心体验 命中焦点搜索引擎的三个核心体验相关性权重计算(续)

2、IDF权重：词项的文档频率DF(Document Frequency)：整个文档集合中出现词项的文档数目。DF反映了词项的区分度，DF越高表示词项越普遍，因此其区分度越低，因此权重也越低。逆文档频率(Inverse DF，IDF)：DF的倒数，通常采用如下公式进行计算(N是文档集合中所有文档的数目)：向量空间模型中通常采用TF*IDF的方式计算权重。即词项 i在文档dj中的权重aij=TFij *IDFi例子：我 爱 北京 天安门，天安门 上 太阳 升TF(天安门)=2， DF=20， N=100，于是TFIDF(天安门)=2*100/20=10相似度计算 t1t2dq搜索引擎的三个核心体验相

3、关性aij=TFij *IDFi搜索引擎的三个核心体验相关性 搜索引擎的三个核心体验相关性 IDF=N/Term出现在所有Doc中的数目，怎么算？2008年：1万亿 pages搜索引擎的三个核心体验相关性 IDF=N/Term出现在所有Doc中的数目，怎么算？主机1Page_0000000000000Page_0000000000001Page_0000000000002Page_0000000000003Page_0000000000004Page_0000000000005主机2Page_0000001000000Page_0000001000001Page_0000001000002Pa

4、ge_0000001000003Page_0000001000004Page_0000001000005主机3Page_0000002000000Page_0000002000001Page_0000002000002Page_0000002000003Page_0000002000004Page_0000002000005搜索引擎的三个核心体验相关性 IDF=N/Term出现在所有Doc中的数目，怎么算？搜索引擎的三个核心体验相关性 IDF=N/Term出现在所有Doc中的数目，怎么算？MPI并行计算框架未解决的问题 堆放在成千上万台机器上的文件谁来管理？ 哪些编码细节可以抽象隐藏出来？ 容

5、错处理MPI并行计算框架未解决的问题 堆放在成千上万台机器上的文件谁来管理？ 分布式文件系统：HDFS Blocks Namenode：存储目录、文件、block、datanode的关系 ReplicaMPI并行计算框架未解决的问题 哪些编码细节可以抽象隐藏出来？ 程序部署MPI并行计算框架未解决的问题 哪些编码细节可以抽象隐藏出来？ 程序部署 data和code的localityMPI并行计算框架未解决的问题 哪些编码细节可以抽象隐藏出来？ 程序部署 消息路由MPI并行计算框架未解决的问题 哪些编码细节可以 抽象隐藏出来？ 程序部署 消息路由MPI并行计算框架未解决的问题 容错处理 重新来过

6、？MPI并行计算框架未解决的问题 容错处理MPI并行计算框架未解决的问题 容错处理 心跳机制 消息半持久化 Reducer Failure Mapper FailureMapReduce特点 Move code to data Map-Reduce编程模型 心跳机制+消息半持久化的容错机制MapReduce Demo Framework代码阅读小练习：利用MapReduce Demo Framework实现IDF计算搜索引擎的三个核心体验 相关 权威 命中焦点搜索引擎的三个核心体验权威性 Citation？搜索引擎的三个核心体验权威性 好的网页指向的一定是好的网页 迭代算法 每个网页的PR值初

7、始化为1 每个网页将自己的PR值等分，传给所有指向的网页 每个网页将收到的PR值加和，作为自己的新PR值 以此迭代。搜索引擎的三个核心体验权威性 PageRank的随机浏览模型解释搜索引擎的三个核心体验权威性 PageRank的矩阵解释搜索引擎的三个核心体验权威性 PageRank的MapReduce实现 连续地矩阵相乘搜索引擎的三个核心体验权威性 PageRank的MapReduce实现 连续地矩阵相乘 V0存储在每台机器上 M按列拆分到每台机器上搜索引擎的三个核心体验权威性 PageRank的MapReduce实现 对每一次迭代 Mapper emit：key=i，value=m(i,j)

8、*V0(j) Reducer 把所有key=i的value累加起来，就是V1(j)小练习：用MapReduce实现矩阵乘法搜索引擎的三个核心体验权威性 PageRank的MapReduce实现的问题：重复劳动 每轮迭代都需要进行任务调度 每轮迭代都要重新读取矩阵搜索引擎的三个核心体验权威性 PageRank的更高效实现：Pregel 把节点划分到不同机器上搜索引擎的三个核心体验权威性 PageRank的更高效实现：Pregel 把节点划分到不同worker上 程序运行之初，每个worker载入子图信息搜索引擎的三个核心体验权威性 PageRank的更高效实现：Pregel 把节点划分到不同wo

9、rker上 程序运行之初，每个worker载入子图信息每一次迭代： 接收来自其他节点的消息 计算 发送消息给其他节点搜索引擎的三个核心体验权威性 PageRank的更高效实现：Pregel 容错： 每一次或者几次迭代，将每个节点的计算结果存入硬盘（checkpoint） 出错时从上个checkpoint开始重新运行搜索引擎的三个核心体验权威性 PageRank的更高效实现：Pregel 优势 只需进行一次任务调度 只需载入一次图数据搜索引擎的三个核心体验 相关 权威 命中焦点搜索引擎的三个核心体验命中焦点 如何预测用户的关注点：利用用户行为数据 Click Trhough Rate(CTR)：

10、预估 样本：Click Log搜索引擎的三个核心体验命中焦点 如何预测用户的关注点：利用用户行为数据 Click Trhough Rate(CTR)：预估 样本：Click Log 模型：Logistic Regression搜索引擎的三个核心体验命中焦点 如何预测用户的关注点：利用用户行为数据 Click Trhough Rate(CTR)：预估 样本：Click Log 模型：Logistic Regression 特征： ID特征: 如果url是，则xi=1 组合ID特征: 如果query=天龙八部，url=天龙八部视频，则xi=1 泛化特征：例如tf * idf 所有特征都做离散化大规

11、模机器学习 如何预测用户的关注点：利用用户行为数据 样本：Click Log百亿训练数据 模型：Logistic Regression 特征：ID特征百亿特征 这样的大规模机器学习会有什么不同？大规模机器学习 目标函数L： 对有点击的样本（记为yj=1）， 对没有点击的样本（记为yj=0），大规模机器学习 目标函数L：大规模机器学习 问题的求解：梯度下降法大规模机器学习 问题的求解：梯度下降法 组合ID特征: 如果query=天龙八部，url=天龙八部视频，则xi=1大规模机器学习 问题的求解：梯度下降法 组合ID特征: 如果query=天龙八部，url=天龙八部视频，则xi=1 大规模的模型，是为了更精确地记忆历史小练习：用Python实现梯度下降小练习：用Python实现梯度下降权重X0Bias0.03X1一等舱0.92X2二等舱0.09X3三等舱-0.97X4男性-1.3X5女性1.3大规模机器学习 用MapReduce实现： Mapper： 对每个样本，计算梯度 emit: key=wi, value=梯度 Reduer： 对每个wi，加和所有梯度，更新wi大规模机器学习 用MapReduce实现的问题： wi也是百亿级别的，每次迭代都要读写硬盘开销大 mapper为了计算hj，必须载入所有wi大规模机器学习 P