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

2、再用這個(gè)算法分析未知的數(shù)據(jù)*什么是模型？ 機(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ì)算方法 數(shù)據(jù)挖掘已被看成是一個(gè)算法問(wèn)題。數(shù)據(jù)模型就是提供復(fù)雜查詢的答案。 除了統(tǒng)計(jì)建模，其它大部分建模方法可分為如下兩類對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)要匯總從數(shù)據(jù)中抽取最突出的特征來(lái)代替數(shù)據(jù)并將剩余內(nèi)容忽略。*數(shù)據(jù)匯總 pagerank。谷歌成功的關(guān)鍵算法之一。Web的復(fù)雜結(jié)構(gòu)可以由每個(gè)頁(yè)面的pagerank描述，反映了一個(gè)web上的隨機(jī)游

3、走者在任意時(shí)刻處于該頁(yè)面的概率。 聚類。數(shù)據(jù)被看成是多維空間的點(diǎn)。空間相互鄰近的點(diǎn)被認(rèn)為是相同的類別。每個(gè)類別可以析括表示，如質(zhì)心或者是到質(zhì)心的平均距離。*特征抽取 從數(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ù)挖掘的統(tǒng)計(jì)限制 2002年，布什政府提出一項(xiàng)對(duì)所有數(shù)據(jù)進(jìn)行挖掘的計(jì)劃，沒(méi)有被國(guó)會(huì)通過(guò)。目的是追逐恐怖活動(dòng) 問(wèn)題

4、：如果能夠獲得所有的數(shù)據(jù)，并且想從中獲得恐怖活動(dòng)的信息。是否會(huì)導(dǎo)致誤報(bào)很多無(wú)辜的行為？*Bonferronis Principle 隨著數(shù)據(jù)規(guī)模的增加，任何數(shù)據(jù)都會(huì)顯現(xiàn)出一些不同尋常的特征，這些特征看上去非常重要，實(shí)際上卻并不重要。 Bonferronis Principle。在數(shù)據(jù)隨機(jī)性假設(shè)的基礎(chǔ)上，計(jì)算所尋找的事件的發(fā)生的期望值，如果該期望值大于找到的真實(shí)事件的數(shù)目，則所找到的事件是假象。*13關(guān)于整體情報(bào)預(yù)警的故事 設(shè)有一群壞人會(huì)偶爾在酒店聚會(huì)策劃陰謀 想找出那些同一天在同一個(gè)酒店至少出現(xiàn)兩次的人群.14假設(shè) 109 可疑人. 1000 days. 每個(gè)人去酒店的概率 1% (1000天

5、里住10天酒店). 酒店容納100 人 (有 105 個(gè)酒店). 每個(gè)人行為都是隨機(jī)的。數(shù)據(jù)挖掘能發(fā)現(xiàn)可疑行為嗎？15Calculations (1) 人員 p 和人員 q 同一天在同一個(gè)酒店出現(xiàn)的概率 :1/100 1/100 10-5 = 10-9. 人員p 和 q 在d1 和 d2 出現(xiàn)在同一個(gè)酒店的概率:10-9 10-9 = 10-18. 1000天任意兩天的排列組合:5105.p atsomehotelq atsomehotelSamehotel16Calculations (2)人員 p 和 q 在任意兩天出現(xiàn)在同一個(gè)酒店的概率:5105 10-18 = 510-13. 可能的人

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

7、發(fā)現(xiàn)1000個(gè)人里面有1個(gè)具有超感知能力 能猜對(duì)所有10張卡片的顏色!20Rhine Paradox (2) 他告訴這些人他們有超能力，并要求他們?cè)僮鲆淮瓮瑯拥膶?shí)驗(yàn). 這些人都失去了他們的超能力. 為什么?見(jiàn)下一個(gè)幻燈片.21Rhine Paradox (3) 這個(gè)心理學(xué)家總結(jié)道：你不能告訴人們他們具有超能力，否則他們就會(huì)失去超能力.22Moral 理解了Bonferronis 原理，能夠使你不犯那個(gè)心理學(xué)家的錯(cuò)誤1.3 相關(guān)知識(shí) 1.3.1 詞語(yǔ)在文檔中的重要性根據(jù)文檔的主題對(duì)文檔進(jìn)行分類主題是通過(guò)一些能夠表現(xiàn)主題的詞語(yǔ)進(jìn)行刻畫(huà)。例如棒球、球、跑等。并不是出現(xiàn)頻率高的詞最重要。如the,an

8、d等，這些常見(jiàn)的詞（數(shù)百個(gè)）應(yīng)該去掉事實(shí)上，描述主題的詞都比較罕見(jiàn)。*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 假定詞項(xiàng)i在文檔集的ni篇文檔中出現(xiàn)，詞項(xiàng)i的IDF定義如下 IDFi=log2(N/ni) 最后，詞項(xiàng)i在文檔j中的得分定義為Tfij*IDFi*TF.IDF 例1.3 如果有1048576個(gè)文檔，詞w在1024個(gè)文檔中出現(xiàn)。對(duì)于文檔j，w出現(xiàn)了20次，也是該文檔中出現(xiàn)的最高頻率。Tfij*IDFi=log(104

9、8576/1024)*1=10 其他條件同上，但是在文檔k中，此w出現(xiàn)一次，而該文檔中出現(xiàn)最多的詞的頻率是20.則 Tfij*IDFi=log(1048576/1024)*1/20=1/2*哈希函數(shù) 哈希函數(shù)的輸入是一個(gè)哈希鍵值(hash-key），輸出是一個(gè)桶編號(hào)(bucket number）。哈希函數(shù)將哈希鍵值隨機(jī)化如果哈希鍵值隨機(jī)地從某個(gè)合理可能的哈希鍵分布中抽樣而成，函數(shù)h把數(shù)目近似相等的哈希鍵值映射到相同的桶編號(hào)。*一個(gè)哈希函數(shù)例子 H(x)=x mod B 如果x是隨機(jī)的整數(shù)值，則x將被均勻分配到每個(gè)桶中，即0到B-1的整數(shù)如果X只是偶數(shù)，且B=10，則答案只有0，2，4，6，8.

10、答案不夠均勻如果X只是偶數(shù)，且B=11，則答案均勻 如果大部分x與B具有公因式，則答案不均勻。 通常取B為素?cái)?shù)。*哈希函數(shù) 如果輸入數(shù)據(jù)類型是有比特位構(gòu)成，則把比特位轉(zhuǎn)換為整數(shù)字符串轉(zhuǎn)換為ASCII,在解釋為整數(shù)等等*索引 通常的數(shù)據(jù)對(duì)象是記錄。每個(gè)記錄包括多個(gè)字段。 在某個(gè)字段上面建立索引。索引一種高效的數(shù)據(jù)查找結(jié)構(gòu)。例如，哈希函數(shù)就是一種實(shí)現(xiàn)方法。 如圖1-2所示。*二級(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毫秒。*1.3.6 冪律分