**大數(shù)據(jù)的存貯和處理趙永祥**大數(shù)據(jù)的存貯和處理趙永祥**課程內(nèi)容概述大規(guī)模文件系統(tǒng)和Mapreduce相似項(xiàng)發(fā)現(xiàn)數(shù)據(jù)流挖掘鏈接分析頻繁項(xiàng)集聚類Web廣告推薦系統(tǒng)**課程內(nèi)容概述教材/~ullman/mmds/book.pdf大數(shù)據(jù)-互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理/**教材/**第一章數(shù)據(jù)挖掘的基本概念1·1數(shù)據(jù)挖掘的定義1.2數(shù)據(jù)挖掘的統(tǒng)計(jì)限制1·3相關(guān)知識(shí)**第一章數(shù)據(jù)挖掘的基本概念1·1數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘是數(shù)據(jù)模型的發(fā)現(xiàn)過(guò)程。什么是模型？統(tǒng)什模型:研究可見數(shù)據(jù)遵從的總體概率分布。如已有一系列數(shù)據(jù)，先猜想服從高斯分布，從數(shù)據(jù)獲取模型參數(shù)，驗(yàn)證與數(shù)據(jù)分布是附合機(jī)器學(xué)習(xí)。將數(shù)據(jù)當(dāng)作某類算法的訓(xùn)練集訓(xùn)練算法。然后再用這個(gè)算法分析未知的數(shù)據(jù)數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘是數(shù)據(jù)模型的發(fā)現(xiàn)過(guò)程。**什么是模型？

機(jī)器學(xué)習(xí)的長(zhǎng)處。當(dāng)對(duì)要在數(shù)據(jù)中尋找的目標(biāo)一無(wú)所知的時(shí)候。如不知道是哪些因素影響人們對(duì)影片的喜好。netflix競(jìng)賽。如目標(biāo)能明確描述，機(jī)器學(xué)習(xí)方法并不成功。如在web上尋找個(gè)人簡(jiǎn)歷。機(jī)器學(xué)習(xí)方法.不如關(guān)鍵詞或者短語(yǔ)更準(zhǔn)確,**什么是模型？

機(jī)器學(xué)習(xí)的長(zhǎng)處。當(dāng)對(duì)要在數(shù)據(jù)中尋找的目標(biāo)一**建模的計(jì)算方法數(shù)據(jù)挖掘已被看成是一個(gè)算法問題。數(shù)據(jù)模型就是提供復(fù)雜查詢的答案。除了統(tǒng)計(jì)建模，其它大部分建模方法可分為如下兩類對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)要匯總從數(shù)據(jù)中抽取最突出的特征來(lái)代替數(shù)據(jù)并將剩余內(nèi)容忽略。**建模的計(jì)算方法數(shù)據(jù)挖掘已被看成是一個(gè)算法問題。數(shù)據(jù)模型就**數(shù)據(jù)匯總pagerank。谷歌成功的關(guān)鍵算法之一。Web的復(fù)雜結(jié)構(gòu)可以由每個(gè)頁(yè)面的pagerank描述，反映了一個(gè)web上的隨機(jī)游走者在任意時(shí)刻處于該頁(yè)面的概率。聚類。數(shù)據(jù)被看成是多維空間的點(diǎn)?？臻g相互鄰近的點(diǎn)被認(rèn)為是相同的類別。每個(gè)類別可以析括表示，如質(zhì)心或者是到質(zhì)心的平均距離。**數(shù)據(jù)匯總pagerank。谷歌成功的關(guān)鍵算法之一。Web******特征抽取從數(shù)據(jù)中尋找某個(gè)現(xiàn)象的特殊樣例，用這些樣例來(lái)表示數(shù)據(jù)。介紹兩種方法：頻繁項(xiàng)集：在很多購(gòu)物籃/訂單里面尋找同時(shí)出現(xiàn)的項(xiàng)集/商品。相似項(xiàng)：數(shù)據(jù)可以描述為一系列的集合。尋找共同元素較多的集合。亞馬遜網(wǎng)站的顧客可以理解為他購(gòu)買商品的集合。尋找相似的集合也就是尋找具有類似興趣的人，把這些人購(gòu)買過(guò)的東西推薦給該顧客。也稱為協(xié)同過(guò)濾**特征抽取從數(shù)據(jù)中尋找某個(gè)現(xiàn)象的特殊樣例，用這些樣例來(lái)表示數(shù)據(jù)挖掘的統(tǒng)計(jì)限制2002年，布什政府提出一項(xiàng)對(duì)所有數(shù)據(jù)進(jìn)行挖掘的計(jì)劃，沒有被國(guó)會(huì)通過(guò)。目的是追逐恐怖活動(dòng)問題：如果能夠獲得所有的數(shù)據(jù)，并且想從中獲得恐怖活動(dòng)的信息。是否會(huì)導(dǎo)致誤報(bào)很多無(wú)辜的行為？**數(shù)據(jù)挖掘的統(tǒng)計(jì)限制2002年，布什政府提出一項(xiàng)對(duì)所有數(shù)據(jù)進(jìn)行Bonferroni’sPrinciple隨著數(shù)據(jù)規(guī)模的增加，任何數(shù)據(jù)都會(huì)顯現(xiàn)出一些不同尋常的特征，這些特征看上去非常重要，實(shí)際上卻并不重要。Bonferroni’sPrinciple。在數(shù)據(jù)隨機(jī)性假設(shè)的基礎(chǔ)上，計(jì)算所尋找的事件的發(fā)生的期望值，如果該期望值大于找到的真實(shí)事件的數(shù)目，則所找到的事件是假象。**Bonferroni’sPrinciple隨著數(shù)據(jù)規(guī)模的增13關(guān)于整體情報(bào)預(yù)警的故事設(shè)有一群壞人會(huì)偶爾在酒店聚會(huì)策劃陰謀想找出那些同一天在同一個(gè)酒店至少出現(xiàn)兩次的人群.13關(guān)于整體情報(bào)預(yù)警的故事設(shè)有一群壞人會(huì)偶爾在酒店聚會(huì)策劃陰14假設(shè)109

可疑人.1000days.每個(gè)人去酒店的概率1%(1000天里住10天酒店).酒店容納100人(有105

個(gè)酒店).每個(gè)人行為都是隨機(jī)的。數(shù)據(jù)挖掘能發(fā)現(xiàn)可疑行為嗎？14假設(shè)109可疑人.15Calculations–(1)人員

p

和人員

q

同一天在同一個(gè)酒店出現(xiàn)的概率:1/1001/10010-5=10-9.人員p

和

q

在d1

和

d2

出現(xiàn)在同一個(gè)酒店的概率:10-9

10-9=10-18.1000天任意兩天的排列組合:5105.patsomehotelqatsomehotelSamehotel15Calculations–(1)人員p和人員16Calculations–(2)人員p

和

q

在任意兩天出現(xiàn)在同一個(gè)酒店的概率:5105

10-18=510-13.可能的人數(shù)是10億，任意兩個(gè)人的排列組合是:51017.平均可疑的人員對(duì)的數(shù)目:51017510-13=250,000.實(shí)際上他們是純隨機(jī)導(dǎo)致的巧合16Calculations–(2)人員p和q在17結(jié)論假設(shè)真的有10對(duì)壞人在同一個(gè)酒店出現(xiàn)兩次.需要掃描250,010對(duì)候選人才能找出這10對(duì)壞人.這個(gè)方法好嗎？17結(jié)論假設(shè)真的有10對(duì)壞人在同一個(gè)酒店出現(xiàn)兩次.18小結(jié)尋找某個(gè)性質(zhì)的事件的時(shí)候(如,“兩個(gè)人在同一個(gè)旅館出現(xiàn)了兩次”),需要考慮純隨機(jī)性是否會(huì)產(chǎn)生多個(gè)具有這個(gè)性質(zhì)的事件。18小結(jié)尋找某個(gè)性質(zhì)的事件的時(shí)候(如,“兩個(gè)人在同一個(gè)旅19RhineParadox–(1)JosephRhine是1950年代的心理學(xué)家，他猜想某些人有超感知能力.他設(shè)計(jì)了一個(gè)實(shí)驗(yàn)：要求實(shí)驗(yàn)對(duì)象猜10張隱藏的卡片的顏色：–紅

或者

藍(lán)？他發(fā)現(xiàn)1000個(gè)人里面有1個(gè)具有超感知能力–能猜對(duì)所有10張卡片的顏色!19RhineParadox–(1)JosephRh20RhineParadox–(2)他告訴這些人他們有超能力，并要求他們?cè)僮鲆淮瓮瑯拥膶?shí)驗(yàn).這些人都失去了他們的超能力.為什么?見下一個(gè)幻燈片.20RhineParadox–(2)他告訴這些人他們有21RhineParadox–(3)這個(gè)心理學(xué)家總結(jié)道：你不能告訴人們他們具有超能力，否則他們就會(huì)失去超能力.21RhineParadox–(3)這個(gè)心理學(xué)家總結(jié)道22Moral理解了Bonferroni’s原理，能夠使你不犯那個(gè)心理學(xué)家的錯(cuò)誤22Moral理解了Bonferroni’s原理，能夠使你1.3相關(guān)知識(shí)1.3.1詞語(yǔ)在文檔中的重要性根據(jù)文檔的主題對(duì)文檔進(jìn)行分類主題是通過(guò)一些能夠表現(xiàn)主題的詞語(yǔ)進(jìn)行刻畫。例如棒球、球、跑等。并不是出現(xiàn)頻率高的詞最重要。如the,and等，這些常見的詞（數(shù)百個(gè)）應(yīng)該去掉事實(shí)上，描述主題的詞都比較罕見。**1.3相關(guān)知識(shí)1.3.1詞語(yǔ)在文檔中的重要性**TF.IDF假定有N篇文檔，fij為詞i在文檔j中出現(xiàn)的頻率（次數(shù)），詞項(xiàng)i在文檔j中的詞項(xiàng)頻率Tfij定義為Tfij=fij/maxkfkj其實(shí)就是fij除以在該文檔出現(xiàn)次數(shù)最多的詞的頻率*TF.IDF假定有N篇文檔，fij為詞i在文檔j中出現(xiàn)的頻率TF.IDF假定詞項(xiàng)i在文檔集的ni篇文檔中出現(xiàn)，詞項(xiàng)i的IDF定義如下IDFi=log2(N/ni)最后，詞項(xiàng)i在文檔j中的得分定義為Tfij*IDFi**TF.IDF假定詞項(xiàng)i在文檔集的ni篇文檔中出現(xiàn)，詞項(xiàng)i的ITF.IDF例1.3如果有1048576個(gè)文檔，詞w在1024個(gè)文檔中出現(xiàn)。對(duì)于文檔j，w出現(xiàn)了20次，也是該文檔中出現(xiàn)的最高頻率。Tfij*IDFi=log(1048576/1024)*1=10其他條件同上，但是在文檔k中，此w出現(xiàn)一次，而該文檔中出現(xiàn)最多的詞的頻率是20.則Tfij*IDFi=log(1048576/1024)*1/20=1/2**TF.IDF例1.3如果有1048576個(gè)文檔，詞w在10哈希函數(shù)哈希函數(shù)的輸入是一個(gè)哈希鍵值(hash-key），輸出是一個(gè)桶編號(hào)(bucketnumber）。哈希函數(shù)將哈希鍵值隨機(jī)化如果哈希鍵值隨機(jī)地從某個(gè)合理可能的哈希鍵分布中抽樣而成，函數(shù)h把數(shù)目近似相等的哈希鍵值映射到相同的桶編號(hào)。**哈希函數(shù)哈希函數(shù)的輸入是一個(gè)哈希鍵值(hash-key），輸一個(gè)哈希函數(shù)例子H(x)=xmodB如果x是隨機(jī)的整數(shù)值，則x將被均勻分配到每個(gè)桶中，即0到B-1的整數(shù)如果X只是偶數(shù)，且B=10，則答案只有0，2，4，6，8.答案不夠均勻如果X只是偶數(shù)，且B=11，則答案均勻如果大部分x與B具有公因式，則答案不均勻。通常取B為素?cái)?shù)。**一個(gè)哈希函數(shù)例子H(x)=xmodB**哈希函數(shù)如果輸入數(shù)據(jù)類型是有比特位構(gòu)成，則把比特位轉(zhuǎn)換為整數(shù)字符串轉(zhuǎn)換為ASCII,在解釋為整數(shù)等等**哈希函數(shù)如果輸入數(shù)據(jù)類型是有比特位構(gòu)成，則把比特位轉(zhuǎn)換為整數(shù)索引通常的數(shù)據(jù)對(duì)象是記錄。每個(gè)記錄包括多個(gè)字段。在某個(gè)字段上面建立索引。索引一種高效的數(shù)據(jù)查找結(jié)構(gòu)。例如，哈希函數(shù)就是一種實(shí)現(xiàn)方法。如圖1-2所示。**索引通常的數(shù)據(jù)對(duì)象是記錄。每個(gè)記錄包括多個(gè)字段。******二級(jí)存儲(chǔ)器從磁盤讀入數(shù)據(jù)的時(shí)間是從內(nèi)存讀入數(shù)據(jù)的100000倍。磁盤讀入數(shù)據(jù)的時(shí)間大約是10毫秒。如果需要讀取的數(shù)據(jù)在磁盤上的一個(gè)柱面上，則讀入一批數(shù)據(jù)時(shí)不需要轉(zhuǎn)動(dòng)磁頭，則讀入每塊數(shù)據(jù)的時(shí)間可以小于10毫秒。**二級(jí)存儲(chǔ)器從磁盤讀入數(shù)據(jù)的時(shí)間是從內(nèi)存讀入數(shù)據(jù)的1000001.3.6冪律分布隨機(jī)變量的概率分布可以寫為Y=cXa

Logy=b+alog(x)

變量的橫軸和縱軸取對(duì)數(shù)后，是一條直線**1.3.6冪律分布隨機(jī)變量的概率分布可以寫為**1.3.6冪律分布Web圖中的節(jié)點(diǎn)度商品的銷量Web網(wǎng)站的大小詞在文檔中的分布**1.3.6冪律分布Web圖中的節(jié)點(diǎn)度**1.3.6冪律分布原因來(lái)自于馬太效應(yīng)某網(wǎng)站有較多的輸入鏈接，將導(dǎo)致更多的人找到他，從而獲得更多的輸入鏈接**1.3.6冪律分布原因來(lái)自于馬太效應(yīng)****大數(shù)據(jù)的存貯和處理趙永祥**大數(shù)據(jù)的存貯和處理趙永祥**課程內(nèi)容概述大規(guī)模文件系統(tǒng)和Mapreduce相似項(xiàng)發(fā)現(xiàn)數(shù)據(jù)流挖掘鏈接分析頻繁項(xiàng)集聚類Web廣告推薦系統(tǒng)**課程內(nèi)容概述教材/~ullman/mmds/book.pdf大數(shù)據(jù)-互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理/**教材/**第一章數(shù)據(jù)挖掘的基本概念1·1數(shù)據(jù)挖掘的定義1.2數(shù)據(jù)挖掘的統(tǒng)計(jì)限制1·3相關(guān)知識(shí)**第一章數(shù)據(jù)挖掘的基本概念1·1數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘是數(shù)據(jù)模型的發(fā)現(xiàn)過(guò)程。什么是模型？統(tǒng)什模型:研究可見數(shù)據(jù)遵從的總體概率分布。如已有一系列數(shù)據(jù)，先猜想服從高斯分布，從數(shù)據(jù)獲取模型參數(shù)，驗(yàn)證與數(shù)據(jù)分布是附合機(jī)器學(xué)習(xí)。將數(shù)據(jù)當(dāng)作某類算法的訓(xùn)練集訓(xùn)練算法。然后再用這個(gè)算法分析未知的數(shù)據(jù)數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘是數(shù)據(jù)模型的發(fā)現(xiàn)過(guò)程。**什么是模型？

機(jī)器學(xué)習(xí)的長(zhǎng)處。當(dāng)對(duì)要在數(shù)據(jù)中尋找的目標(biāo)一無(wú)所知的時(shí)候。如不知道是哪些因素影響人們對(duì)影片的喜好。netflix競(jìng)賽。如目標(biāo)能明確描述，機(jī)器學(xué)習(xí)方法并不成功。如在web上尋找個(gè)人簡(jiǎn)歷。機(jī)器學(xué)習(xí)方法.不如關(guān)鍵詞或者短語(yǔ)更準(zhǔn)確,**什么是模型？

機(jī)器學(xué)習(xí)的長(zhǎng)處。當(dāng)對(duì)要在數(shù)據(jù)中尋找的目標(biāo)一**建模的計(jì)算方法數(shù)據(jù)挖掘已被看成是一個(gè)算法問題。數(shù)據(jù)模型就是提供復(fù)雜查詢的答案。除了統(tǒng)計(jì)建模，其它大部分建模方法可分為如下兩類對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)要匯總從數(shù)據(jù)中抽取最突出的特征來(lái)代替數(shù)據(jù)并將剩余內(nèi)容忽略。**建模的計(jì)算方法數(shù)據(jù)挖掘已被看成是一個(gè)算法問題。數(shù)據(jù)模型就**數(shù)據(jù)匯總pagerank。谷歌成功的關(guān)鍵算法之一。Web的復(fù)雜結(jié)構(gòu)可以由每個(gè)頁(yè)面的pagerank描述，反映了一個(gè)web上的隨機(jī)游走者在任意時(shí)刻處于該頁(yè)面的概率。聚類。數(shù)據(jù)被看成是多維空間的點(diǎn)?？臻g相互鄰近的點(diǎn)被認(rèn)為是相同的類別。每個(gè)類別可以析括表示，如質(zhì)心或者是到質(zhì)心的平均距離。**數(shù)據(jù)匯總pagerank。谷歌成功的關(guān)鍵算法之一。Web******特征抽取從數(shù)據(jù)中尋找某個(gè)現(xiàn)象的特殊樣例，用這些樣例來(lái)表示數(shù)據(jù)。介紹兩種方法：頻繁項(xiàng)集：在很多購(gòu)物籃/訂單里面尋找同時(shí)出現(xiàn)的項(xiàng)集/商品。相似項(xiàng)：數(shù)據(jù)可以描述為一系列的集合。尋找共同元素較多的集合。亞馬遜網(wǎng)站的顧客可以理解為他購(gòu)買商品的集合。尋找相似的集合也就是尋找具有類似興趣的人，把這些人購(gòu)買過(guò)的東西推薦給該顧客。也稱為協(xié)同過(guò)濾**特征抽取從數(shù)據(jù)中尋找某個(gè)現(xiàn)象的特殊樣例，用這些樣例來(lái)表示數(shù)據(jù)挖掘的統(tǒng)計(jì)限制2002年，布什政府提出一項(xiàng)對(duì)所有數(shù)據(jù)進(jìn)行挖掘的計(jì)劃，沒有被國(guó)會(huì)通過(guò)。目的是追逐恐怖活動(dòng)問題：如果能夠獲得所有的數(shù)據(jù)，并且想從中獲得恐怖活動(dòng)的信息。是否會(huì)導(dǎo)致誤報(bào)很多無(wú)辜的行為？**數(shù)據(jù)挖掘的統(tǒng)計(jì)限制2002年，布什政府提出一項(xiàng)對(duì)所有數(shù)據(jù)進(jìn)行Bonferroni’sPrinciple隨著數(shù)據(jù)規(guī)模的增加，任何數(shù)據(jù)都會(huì)顯現(xiàn)出一些不同尋常的特征，這些特征看上去非常重要，實(shí)際上卻并不重要。Bonferroni’sPrinciple。在數(shù)據(jù)隨機(jī)性假設(shè)的基礎(chǔ)上，計(jì)算所尋找的事件的發(fā)生的期望值，如果該期望值大于找到的真實(shí)事件的數(shù)目，則所找到的事件是假象。**Bonferroni’sPrinciple隨著數(shù)據(jù)規(guī)模的增48關(guān)于整體情報(bào)預(yù)警的故事設(shè)有一群壞人會(huì)偶爾在酒店聚會(huì)策劃陰謀想找出那些同一天在同一個(gè)酒店至少出現(xiàn)兩次的人群.13關(guān)于整體情報(bào)預(yù)警的故事設(shè)有一群壞人會(huì)偶爾在酒店聚會(huì)策劃陰49假設(shè)109

可疑人.1000days.每個(gè)人去酒店的概率1%(1000天里住10天酒店).酒店容納100人(有105

個(gè)酒店).每個(gè)人行為都是隨機(jī)的。數(shù)據(jù)挖掘能發(fā)現(xiàn)可疑行為嗎？14假設(shè)109可疑人.50Calculations–(1)人員

p

和人員

q

同一天在同一個(gè)酒店出現(xiàn)的概率:1/1001/10010-5=10-9.人員p

和

q

在d1

和

d2

出現(xiàn)在同一個(gè)酒店的概率:10-9

10-9=10-18.1000天任意兩天的排列組合:5105.patsomehotelqatsomehotelSamehotel15Calculations–(1)人員p和人員51Calculations–(2)人員p

和

q

在任意兩天出現(xiàn)在同一個(gè)酒店的概率:5105

10-18=510-13.可能的人數(shù)是10億，任意兩個(gè)人的排列組合是:51017.平均可疑的人員對(duì)的數(shù)目:51017510-13=250,000.實(shí)際上他們是純隨機(jī)導(dǎo)致的巧合16Calculations–(2)人員p和q在52結(jié)論假設(shè)真的有10對(duì)壞人在同一個(gè)酒店出現(xiàn)兩次.需要掃描250,010對(duì)候選人才能找出這10對(duì)壞人.這個(gè)方法好嗎？17結(jié)論假設(shè)真的有10對(duì)壞人在同一個(gè)酒店出現(xiàn)兩次.53小結(jié)尋找某個(gè)性質(zhì)的事件的時(shí)候(如,“兩個(gè)人在同一個(gè)旅館出現(xiàn)了兩次”),需要考慮純隨機(jī)性是否會(huì)產(chǎn)生多個(gè)具有這個(gè)性質(zhì)的事件。18小結(jié)尋找某個(gè)性質(zhì)的事件的時(shí)候(如,“兩個(gè)人在同一個(gè)旅54RhineParadox–(1)JosephRhine是1950年代的心理學(xué)家，他猜想某些人有超感知能力.他設(shè)計(jì)了一個(gè)實(shí)驗(yàn)：要求實(shí)驗(yàn)對(duì)象猜10張隱藏的卡片的顏色：–紅

或者

藍(lán)？他發(fā)現(xiàn)1000個(gè)人里面有1個(gè)具有超感知能力–能猜對(duì)所有10張卡片的顏色!19RhineParadox–(1)JosephRh55RhineParadox–(2)他告訴這些人他們有超能力，并要求他們?cè)僮鲆淮瓮瑯拥膶?shí)驗(yàn).這些人都失去了他們的超能力.為什么?見下一個(gè)幻燈片.20RhineParadox–(2)他告訴這些人他們有56RhineParadox–(3)這個(gè)心理學(xué)家總結(jié)道：你不能告訴人們他們具有超能力，否則他們就會(huì)失去超能力.21RhineParadox–(3)這個(gè)心理學(xué)家總結(jié)道57Moral理解了Bonferroni’s原理，能夠使你不犯那個(gè)心理學(xué)家的錯(cuò)誤22Moral理解了Bonferroni’s原理，能夠使你1.3相關(guān)知識(shí)1.3.1詞語(yǔ)在文檔中的重要性根據(jù)文檔的主題對(duì)文檔進(jìn)行分類主題是通過(guò)一些能夠表現(xiàn)主題的詞語(yǔ)進(jìn)行刻畫。例如棒球、球、跑等。并不是出現(xiàn)頻率高的詞最重要。如the,and等，這些常見的詞（數(shù)百個(gè)）應(yīng)該去掉事實(shí)上，描述主題的詞都比較罕見。**1.3相關(guān)知識(shí)1.3.1詞語(yǔ)在文檔中的重要性**TF.IDF假定有N篇文檔，fij為詞i在文檔j中出現(xiàn)的頻率（次數(shù)），詞項(xiàng)i在文檔j中的詞項(xiàng)頻率Tfij定義為Tfij=fij/maxkfkj其實(shí)就是fij除以在該文檔出現(xiàn)次數(shù)最多的詞的頻率*TF.IDF假定有N篇文檔，fij為詞i在文檔j中出現(xiàn)的頻率TF.IDF假定詞項(xiàng)i在文檔集的ni篇文檔中出現(xiàn)，詞項(xiàng)i的IDF定義如下IDFi=log2(N/ni)最后，詞項(xiàng)i在文檔j中的得分定義為Tfij*IDFi**TF.IDF假定詞項(xiàng)i在文檔集的ni篇文檔中出現(xiàn)，詞項(xiàng)i的ITF.IDF例1.3如果有1048576個(gè)文檔，詞w在1024個(gè)文檔中出現(xiàn)。對(duì)于文檔j，w出現(xiàn)了20次，也是該文檔中出現(xiàn)的最高頻率。Tfij*IDFi=log(1048576/1024)*1=10其他條件同上，但是在文檔k中，此w出現(xiàn)一次，而該文檔中出現(xiàn)最多的詞的頻率是20.則Tfij*IDFi=log(1048576/1024)*1/20=1/2**TF.IDF例1.3如果有1048576個(gè)文檔，詞w在10哈希函數(shù)哈希函數(shù)的輸入是一個(gè)哈希鍵值(hash-key），輸出是一個(gè)桶編號(hào)(bucketnumber）。哈希函數(shù)將哈希鍵值隨機(jī)化如果哈希鍵值隨機(jī)