搜索引擎中的大數(shù)據(jù)挖掘

1、搜索引擎中的大數(shù)據(jù)挖掘大數(shù)據(jù)核心技術(shù)之?dāng)?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)技術(shù)探索及應(yīng)用為什么花這么多時(shí)間講搜索引擎？ 搜索引擎是大數(shù)據(jù)數(shù)據(jù)挖掘的肇事者和集大成者 1998年：150 millions pages 1.5T 2003年：?jiǎn)卧绿幚?288T數(shù)據(jù) 2008年：1萬億 pages為什么花這么多時(shí)間講搜索引擎？ 搜索引擎是大數(shù)據(jù)數(shù)據(jù)挖掘的肇事者和集大成者大規(guī)模檢索 大規(guī)模文本分析 大規(guī)模圖算法 百度識(shí)圖 欠缺的：更復(fù)雜的現(xiàn)實(shí)世界數(shù)據(jù)搜索引擎的三個(gè)核心體驗(yàn) 相關(guān) 權(quán)威 命中焦點(diǎn)搜索引擎的三個(gè)核心體驗(yàn) 相關(guān)搜索引擎的三個(gè)核心體驗(yàn) 權(quán)威搜索引擎的三個(gè)核心體驗(yàn) 命中焦點(diǎn)搜索引擎的三個(gè)核心體驗(yàn)相關(guān)性權(quán)重計(jì)算(續(xù))

2、IDF權(quán)重：詞項(xiàng)的文檔頻率DF(Document Frequency)：整個(gè)文檔集合中出現(xiàn)詞項(xiàng)的文檔數(shù)目。DF反映了詞項(xiàng)的區(qū)分度，DF越高表示詞項(xiàng)越普遍，因此其區(qū)分度越低，因此權(quán)重也越低。逆文檔頻率(Inverse DF，IDF)：DF的倒數(shù)，通常采用如下公式進(jìn)行計(jì)算(N是文檔集合中所有文檔的數(shù)目)：向量空間模型中通常采用TF*IDF的方式計(jì)算權(quán)重。即詞項(xiàng) i在文檔dj中的權(quán)重aij=TFij *IDFi例子：我 愛 北京 天安門，天安門 上 太陽 升TF(天安門)=2， DF=20， N=100，于是TFIDF(天安門)=2*100/20=10相似度計(jì)算 t1t2dq搜索引擎的三個(gè)核心體驗(yàn)相

3、關(guān)性aij=TFij *IDFi搜索引擎的三個(gè)核心體驗(yàn)相關(guān)性 搜索引擎的三個(gè)核心體驗(yàn)相關(guān)性 IDF=N/Term出現(xiàn)在所有Doc中的數(shù)目，怎么算？2008年：1萬億 pages搜索引擎的三個(gè)核心體驗(yàn)相關(guān)性 IDF=N/Term出現(xiàn)在所有Doc中的數(shù)目，怎么算？主機(jī)1Page_0000000000000Page_0000000000001Page_0000000000002Page_0000000000003Page_0000000000004Page_0000000000005主機(jī)2Page_0000001000000Page_0000001000001Page_0000001000002Pa

4、ge_0000001000003Page_0000001000004Page_0000001000005主機(jī)3Page_0000002000000Page_0000002000001Page_0000002000002Page_0000002000003Page_0000002000004Page_0000002000005搜索引擎的三個(gè)核心體驗(yàn)相關(guān)性 IDF=N/Term出現(xiàn)在所有Doc中的數(shù)目，怎么算？搜索引擎的三個(gè)核心體驗(yàn)相關(guān)性 IDF=N/Term出現(xiàn)在所有Doc中的數(shù)目，怎么算？MPI并行計(jì)算框架未解決的問題 堆放在成千上萬臺(tái)機(jī)器上的文件誰來管理？ 哪些編碼細(xì)節(jié)可以抽象隱藏出來？ 容

5、錯(cuò)處理MPI并行計(jì)算框架未解決的問題 堆放在成千上萬臺(tái)機(jī)器上的文件誰來管理？ 分布式文件系統(tǒng)：HDFS Blocks Namenode：存儲(chǔ)目錄、文件、block、datanode的關(guān)系 ReplicaMPI并行計(jì)算框架未解決的問題 哪些編碼細(xì)節(jié)可以抽象隱藏出來？ 程序部署MPI并行計(jì)算框架未解決的問題 哪些編碼細(xì)節(jié)可以抽象隱藏出來？ 程序部署 data和code的localityMPI并行計(jì)算框架未解決的問題 哪些編碼細(xì)節(jié)可以抽象隱藏出來？ 程序部署 消息路由MPI并行計(jì)算框架未解決的問題 哪些編碼細(xì)節(jié)可以 抽象隱藏出來？ 程序部署 消息路由MPI并行計(jì)算框架未解決的問題 容錯(cuò)處理 重新來過

6、？MPI并行計(jì)算框架未解決的問題 容錯(cuò)處理MPI并行計(jì)算框架未解決的問題 容錯(cuò)處理 心跳機(jī)制 消息半持久化 Reducer Failure Mapper FailureMapReduce特點(diǎn) Move code to data Map-Reduce編程模型 心跳機(jī)制+消息半持久化的容錯(cuò)機(jī)制MapReduce Demo Framework代碼閱讀小練習(xí)：利用MapReduce Demo Framework實(shí)現(xiàn)IDF計(jì)算搜索引擎的三個(gè)核心體驗(yàn) 相關(guān) 權(quán)威 命中焦點(diǎn)搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 Citation？搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 好的網(wǎng)頁指向的一定是好的網(wǎng)頁 迭代算法 每個(gè)網(wǎng)頁的PR值初

7、始化為1 每個(gè)網(wǎng)頁將自己的PR值等分，傳給所有指向的網(wǎng)頁 每個(gè)網(wǎng)頁將收到的PR值加和，作為自己的新PR值 以此迭代。搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的隨機(jī)瀏覽模型解釋搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的矩陣解釋搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的MapReduce實(shí)現(xiàn) 連續(xù)地矩陣相乘搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的MapReduce實(shí)現(xiàn) 連續(xù)地矩陣相乘 V0存儲(chǔ)在每臺(tái)機(jī)器上 M按列拆分到每臺(tái)機(jī)器上搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的MapReduce實(shí)現(xiàn) 對(duì)每一次迭代 Mapper emit：key=i，value=m(i,j)

8、*V0(j) Reducer 把所有key=i的value累加起來，就是V1(j)小練習(xí)：用MapReduce實(shí)現(xiàn)矩陣乘法搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的MapReduce實(shí)現(xiàn)的問題：重復(fù)勞動(dòng) 每輪迭代都需要進(jìn)行任務(wù)調(diào)度 每輪迭代都要重新讀取矩陣搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的更高效實(shí)現(xiàn)：Pregel 把節(jié)點(diǎn)劃分到不同機(jī)器上搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的更高效實(shí)現(xiàn)：Pregel 把節(jié)點(diǎn)劃分到不同worker上 程序運(yùn)行之初，每個(gè)worker載入子圖信息搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的更高效實(shí)現(xiàn)：Pregel 把節(jié)點(diǎn)劃分到不同wo

9、rker上 程序運(yùn)行之初，每個(gè)worker載入子圖信息每一次迭代： 接收來自其他節(jié)點(diǎn)的消息 計(jì)算 發(fā)送消息給其他節(jié)點(diǎn)搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的更高效實(shí)現(xiàn)：Pregel 容錯(cuò)： 每一次或者幾次迭代，將每個(gè)節(jié)點(diǎn)的計(jì)算結(jié)果存入硬盤（checkpoint） 出錯(cuò)時(shí)從上個(gè)checkpoint開始重新運(yùn)行搜索引擎的三個(gè)核心體驗(yàn)權(quán)威性 PageRank的更高效實(shí)現(xiàn)：Pregel 優(yōu)勢(shì) 只需進(jìn)行一次任務(wù)調(diào)度 只需載入一次圖數(shù)據(jù)搜索引擎的三個(gè)核心體驗(yàn) 相關(guān) 權(quán)威 命中焦點(diǎn)搜索引擎的三個(gè)核心體驗(yàn)命中焦點(diǎn) 如何預(yù)測(cè)用戶的關(guān)注點(diǎn)：利用用戶行為數(shù)據(jù) Click Trhough Rate(CTR)：

10、預(yù)估 樣本：Click Log搜索引擎的三個(gè)核心體驗(yàn)命中焦點(diǎn) 如何預(yù)測(cè)用戶的關(guān)注點(diǎn)：利用用戶行為數(shù)據(jù) Click Trhough Rate(CTR)：預(yù)估 樣本：Click Log 模型：Logistic Regression搜索引擎的三個(gè)核心體驗(yàn)命中焦點(diǎn) 如何預(yù)測(cè)用戶的關(guān)注點(diǎn)：利用用戶行為數(shù)據(jù) Click Trhough Rate(CTR)：預(yù)估 樣本：Click Log 模型：Logistic Regression 特征： ID特征: 如果url是，則xi=1 組合ID特征: 如果query=天龍八部，url=天龍八部視頻，則xi=1 泛化特征：例如tf * idf 所有特征都做離散化大規(guī)

11、模機(jī)器學(xué)習(xí) 如何預(yù)測(cè)用戶的關(guān)注點(diǎn)：利用用戶行為數(shù)據(jù) 樣本：Click Log百億訓(xùn)練數(shù)據(jù) 模型：Logistic Regression 特征：ID特征百億特征 這樣的大規(guī)模機(jī)器學(xué)習(xí)會(huì)有什么不同？大規(guī)模機(jī)器學(xué)習(xí) 目標(biāo)函數(shù)L： 對(duì)有點(diǎn)擊的樣本（記為yj=1）， 對(duì)沒有點(diǎn)擊的樣本（記為yj=0），大規(guī)模機(jī)器學(xué)習(xí) 目標(biāo)函數(shù)L：大規(guī)模機(jī)器學(xué)習(xí) 問題的求解：梯度下降法大規(guī)模機(jī)器學(xué)習(xí) 問題的求解：梯度下降法 組合ID特征: 如果query=天龍八部，url=天龍八部視頻，則xi=1大規(guī)模機(jī)器學(xué)習(xí) 問題的求解：梯度下降法 組合ID特征: 如果query=天龍八部，url=天龍八部視頻，則xi=1 大規(guī)模的模型，是為了更精確地記憶歷史小練習(xí)：用Python實(shí)現(xiàn)梯度下降小練習(xí)：用Python實(shí)現(xiàn)梯度下降權(quán)重X0Bias0.03X1一等艙0.92X2二等艙0.09X3三等艙-0.97X4男性-1.3X5女性1.3大規(guī)模機(jī)器學(xué)習(xí) 用MapReduce實(shí)現(xiàn)： Mapper： 對(duì)每個(gè)樣本，計(jì)算梯度 emit: key=wi, value=梯度 Reduer： 對(duì)每個(gè)wi，加和所有梯度，更新wi大規(guī)模機(jī)器學(xué)習(xí) 用MapReduce實(shí)現(xiàn)的問題： wi也是百億級(jí)別的，每次迭代都要讀寫硬盤開銷大 mapper為了計(jì)算hj，必須載入所有wi大規(guī)模機(jī)器學(xué)習(xí) P