大數(shù)據(jù)存儲(chǔ)與應(yīng)用數(shù)據(jù)流挖掘課件

1、大數(shù)據(jù)存儲(chǔ)與應(yīng)用數(shù)據(jù)流挖掘課程主頁：/?page_id=397陳一帥chenyishuai內(nèi)容流數(shù)據(jù)模型系統(tǒng)，示例抽樣過濾數(shù)目統(tǒng)計(jì)矩估計(jì)窗口內(nèi)計(jì)數(shù)衰減窗口預(yù)覽谷歌/淘寶是怎么做下面這些事情的取樣比例取樣固定size取樣頻度統(tǒng)計(jì)統(tǒng)計(jì)item發(fā)生的次數(shù)白名單過濾統(tǒng)計(jì)不同查詢的個(gè)數(shù)評(píng)估用戶訪問的均勻性發(fā)現(xiàn)最熱item簡(jiǎn)單的數(shù)據(jù)統(tǒng)計(jì)問題，在大數(shù)據(jù)場(chǎng)合下，新的方法流數(shù)據(jù)模型流數(shù)據(jù)以流的方式進(jìn)入搜索引擎的查詢請(qǐng)求微博更新特點(diǎn)無窮非平穩(wěn)流的到達(dá)速率取決于用戶行為，系統(tǒng)無法控制元素（Element）Tuple大數(shù)據(jù)下的系統(tǒng)限制流源源不斷地來要求實(shí)時(shí)處理系統(tǒng)限制存儲(chǔ)限制，不能存這么多存得多，處理量也大，處理能力

2、限制NSA（美國(guó)棱鏡門）存幾個(gè)月流處理有限存儲(chǔ)情況下，怎么實(shí)時(shí)處理？Online learning問題取樣：隨機(jī)取樣（Sampling）過濾（白名單）：選取特定屬性的元素（Filtering）計(jì)數(shù)（一定窗口內(nèi)）有多少個(gè)不同的元素？（distinct elements)各元素的Popularity？特征：各階矩誰最流行?應(yīng)用Google：查詢流發(fā)現(xiàn)最流行的查詢關(guān)鍵字Yahoo：發(fā)現(xiàn)最流行的頁面微博：發(fā)現(xiàn)最熱的話題找人傳感器網(wǎng)絡(luò)電話記錄美國(guó)，棱鏡門網(wǎng)絡(luò)交換機(jī)流量統(tǒng)計(jì)，優(yōu)化路由檢測(cè)DDoS攻擊抽樣Sampling抽樣兩種抽樣固定比率抽樣1 in 10固定Size抽樣總是保持s個(gè)元素固定比率抽樣應(yīng)用場(chǎng)

3、合搜索引擎，一個(gè)用戶的搜索中，重復(fù)的有多少？存不了全部，可以存1/10最明顯的辦法每來一個(gè)query生成一個(gè)隨機(jī)整數(shù)：09如果是0，就存起來1/10的采樣然后統(tǒng)計(jì)其中的用戶重復(fù)搜索比例對(duì)嗎？有問題假設(shè)：一個(gè)用戶所有搜索字符串中，x個(gè)查詢了一次，d個(gè)查詢了兩次，沒有其他查詢。重復(fù)查詢占比：d/(x+d)隨機(jī)采樣10%后，重復(fù)查詢占比是怎樣的？采樣后，獲得(x+2d)/10個(gè)查詢，其中x/10個(gè)查詢是屬于x，肯定只出現(xiàn)一次針對(duì)d的2d/10個(gè)查詢d中任一查詢，兩次都被抽中的概率為1/101/10 = 1/100所以，平均有d/100個(gè)查詢會(huì)被抽中兩次，占2d/100個(gè)查詢剩下2d/10 2d/10

4、0 = 18d/100次查詢，也只出現(xiàn)一次。結(jié)果不等于d/(x+d)。錯(cuò)誤固定Size抽樣總是保持s個(gè)元素這s個(gè)元素，是對(duì)過去所有元素的均勻取樣即：過去所有元素，進(jìn)入這s個(gè)元素的概率相同直觀方案：全存起來，然后從中隨機(jī)挑s個(gè)大數(shù)據(jù)下，因?yàn)榇鎯?chǔ)空間的限制，不可行流方案進(jìn)來一個(gè)新元素時(shí)，新元素以概率p進(jìn)入s原有的s個(gè)元素按一定的概率從s中剔除新元素進(jìn)入S的概率p假設(shè)已到達(dá)n個(gè)元素，它們以s/n的概率被采樣，組成s個(gè)元素的集合新進(jìn)來一個(gè)元素，一共到達(dá)了n+1個(gè)元素。這n+1元素，以相同概率進(jìn)入s這個(gè)概率： s/(n+1)所以，這個(gè)新元素以s/(n+1)的概率進(jìn)入sp = s/(n+1)滑動(dòng)窗口內(nèi)計(jì)數(shù)

5、Sliding windows 滑動(dòng)窗另一種取樣方式示例N = 6應(yīng)用：統(tǒng)計(jì)滑動(dòng)窗中1的個(gè)數(shù)頻率簡(jiǎn)單方案FIFO，窗口大?。篘存起來然后統(tǒng)計(jì)但是：N太大(Billion)/流太多(Billion)，存不下。怎么辦？近似方案統(tǒng)計(jì)滑動(dòng)窗中1的個(gè)數(shù)如果1均勻分布，容易估計(jì)從流開始時(shí)刻，統(tǒng)計(jì)1/0個(gè)數(shù)：S/Z估計(jì)窗口N內(nèi)1的個(gè)數(shù)：如果1的分布不均勻呢？DGIM方法每個(gè)流，存儲(chǔ) 比特結(jié)果誤差不超過正確結(jié)果的50%可以進(jìn)一步減少DGIMDatar , Gionis, Indyk, Motwani 指數(shù)窗口每個(gè)窗口中包括 i 個(gè)1， i : 2的冪（指數(shù)增長(zhǎng)）同樣i的窗口最多可以有兩個(gè)窗口不重疊，可以不連續(xù)

6、（中間可以隔0） 16 8 8 4 4 2 2 1更新新元素到了如果一個(gè)Bucket的end time已超過當(dāng)前時(shí)刻 - N，drop它如果新元素是0，什么也不做如果是1創(chuàng)建一個(gè)Bucket，size = 1， end time = 當(dāng)前時(shí)間如果有3個(gè)1，就合并為一個(gè)2。依次類推，如果有3個(gè)一樣的小的，就合并為一個(gè)大的。雪崩式前滾示例Error bound：50%假設(shè)最后一個(gè)bucket的size：2r我們?cè)诮y(tǒng)計(jì)中算了它的一半“1”，所以，最多產(chǎn)生2r-1的錯(cuò)誤比它size小的bucket有2r-1，2r-2 ，2r-3 ，1，每種至少有一個(gè)所以，它們包含的“1”的個(gè)數(shù)至少為： 2r-1 +

7、2r-2 + 2r-3 + + 1 = 2r 1.最后一個(gè)bucket在窗口中至少還有1個(gè)“1”，所以， “1”的個(gè)數(shù)至少為2r 所以，最大的錯(cuò)誤率：2r-1/ 2r = 1/2 = 50%擴(kuò)展同樣size的bucket數(shù)目可以是r或r-1個(gè)。r 2最大Size的bucket，可以有1,r個(gè)錯(cuò)誤的上界1/(r-1)實(shí)踐中，根據(jù)需要選擇r應(yīng)用：窗口內(nèi)整數(shù)的和把整數(shù)的每一個(gè)bit作為一個(gè)stream統(tǒng)計(jì)每一個(gè)stream的1的個(gè)數(shù)，Ci求和：小結(jié)百分比取樣按feature（用戶）取樣固定Size取樣滑動(dòng)窗取樣估計(jì)1的個(gè)數(shù)求整數(shù)和過濾Bloom filter（布隆過濾器）Bloom filterBl

8、oom是一個(gè)人從stream中選擇符合特定條件的元素例1：垃圾郵件檢查白名單例2：Google AlertPub-Sub系統(tǒng)，每個(gè)人可以設(shè)定訂閱的關(guān)鍵詞明顯的方法建立Hash表，查詢，命中大數(shù)據(jù)下，filter太多，數(shù)據(jù)太多，怎么辦？包括10 billion 個(gè)白名單初始化白名單中包括s個(gè)允許的key值s = 1 billionn個(gè)檢查位，n s，初始化為0把這s個(gè)白名字Hash到1,n上對(duì)應(yīng)的bit位設(shè)1最后，n中大約有s個(gè)“1”事實(shí)上小于s個(gè)，因?yàn)闀?huì)重合。到底有幾個(gè)1？一個(gè)白名字，被均勻地撒在n個(gè)比特上撒上概率：1/n一個(gè)比特位，沒有被撒上的概率被1個(gè)白名字錯(cuò)過的概率：1 - 1/n被所有

9、s個(gè)白名字都錯(cuò)過的概率(1-1/n)s = (1-1/n)n(s/n) 近似等于 e-s/n所以，一個(gè)比特位，被撒上的概率1 es/n總共，n(1 es/n)個(gè)比特位被撒上值為“1”檢查來了一個(gè)郵件，把發(fā)件人地址，hash一下，如果對(duì)應(yīng)的比特位為0，肯定不在白名單里，Reject不在白名單里，也會(huì)被均勻撒在n個(gè)比特位上如果那個(gè)比特位碰巧是“1”，就會(huì)passFalse positives - 假陽（FP）Pass：Positive和n中“1”的比例有關(guān)，n(1 es/n)/n = 1 es/n所以，可以通過增加n，降低FP概率s = 109, n = 8109，概率 1 - e1/8 = 0.

10、1185 1/8 = s/n改進(jìn)：多個(gè)hash函數(shù)初始化對(duì)s中任一元素，用k個(gè)獨(dú)立hash函數(shù)，分別撒k次“1”的個(gè)數(shù)：類似前面，只是撒了ks次n(1 eks/n)檢查來一封信，用這k個(gè)hash檢查，全部為“1”才行。False positive率混過去一個(gè)hash函數(shù)，概率(1 eks/n)混過去全部k個(gè)hash檢查，概率(1 eks/n)kK=2， 概率 0.0493 1/20 1/8改進(jìn)了性能K的選擇K不是越大越好對(duì)這個(gè)例子，最優(yōu)的在6的樣子。Bloom Filter總結(jié)只會(huì)false positive不會(huì)false negative錯(cuò)殺概率 = 0適合預(yù)處理先篩選一些適合硬件實(shí)現(xiàn)適合并

11、行Map-reduceDistinct元素統(tǒng)計(jì)統(tǒng)計(jì)出現(xiàn)的不同元素個(gè)數(shù)應(yīng)用爬網(wǎng)站時(shí)，邊爬，邊檢查其網(wǎng)頁中不同單詞的個(gè)數(shù)太多或太少，都表明是一個(gè)作弊的網(wǎng)站統(tǒng)計(jì)一個(gè)用戶，一周內(nèi)，訪問了多少不同的網(wǎng)頁統(tǒng)計(jì)淘寶，上周，賣了多少種不同的商品？明顯的方法建立一個(gè)Distinct元素列表（hash表）進(jìn)來一個(gè)，和列表中已有的元素對(duì)照，如果不同，就加入跟蹤列表Size的變化大數(shù)據(jù)情況下存不下維護(hù)成本很高需要減少存儲(chǔ)要求減小計(jì)算復(fù)雜度Tradeoff：準(zhǔn)確性 實(shí)用性估計(jì)Flajolet-Martin方法啟發(fā)式算法用Hash，把N個(gè)元素，映射到至少log2(N)比特上檢查映射的結(jié)果，看它們尾部連0的個(gè)數(shù)：ri例：1

12、100 - 2 1000 - 3找出最大的 ri例：R = max2,3 = 3估計(jì)不同元素個(gè)數(shù)為2R例：23 = 8直覺證明(Intuition)通過Hash把元素均勻散布到M = log2(N)個(gè)比特上Hash結(jié)果為xxx0的概率為1/2Hash結(jié)果為xx00的概率為1/4當(dāng)我們看到一個(gè)*100時(shí)，很可能已經(jīng)pass過了4個(gè)不同的元素了。估計(jì)：4個(gè)不同元素更形式化的證明一個(gè)元素，hash后，尾部連續(xù)r個(gè)0的概率()r = 2r m個(gè)不同元素hash后的m個(gè)結(jié)果，尾部都不“連續(xù)r個(gè)0”概率：(1 - 2r)m = = 出現(xiàn)連續(xù)r個(gè)0的概率 1 - m 2r，概率為1，即總能得到連續(xù)r個(gè)0的結(jié)

13、果。m 2r，概率為0，即得不到連續(xù)r個(gè)0所以，估計(jì)m = 2r 大致上是合理的。實(shí)際應(yīng)用問題：R加1，2R就漲一倍。E2R無窮大解決辦法用多個(gè)hash函數(shù)，結(jié)果組合起來組合辦法平均：偶爾一個(gè)大值對(duì)結(jié)果的影響很大，不好中值：估計(jì)的結(jié)果總是2的冪次，取值不連續(xù)，也不好解決方案：樣本分組組內(nèi)取平均組間取中值矩估計(jì)Moments矩估計(jì)N個(gè)到達(dá)的元素，統(tǒng)計(jì)各不同元素的流行度(Popularity)不同元素的集合A，各不同元素i出現(xiàn)的次數(shù)mi（流行度）流行度的K階矩物理意義k = 0，A的size，即不同元素的個(gè)數(shù)。 |A|k = 1，N，stream長(zhǎng)度，元素個(gè)數(shù)k = 2，Surprise numb

14、er（奇異數(shù)），Popularity分布均勻的度量Surprise number（奇異數(shù)）Popularity分布的均勻程度的度量例：|A| = 11：11個(gè)視頻N = 100：100次用戶觀看觀看在視頻上的分布Case 1：10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9Surprise S = 910比較均勻Case 2：90, 1, 1, 1, 1, 1, 1, 1 ,1, 1, 1 Surprise S = 8110更不均勻AMS方法Alon, Matias, and Szegedy以k = 2為例隨機(jī)挑一個(gè)時(shí)刻，對(duì)stream采樣采樣獲得的值存在X.el里然后對(duì)后面進(jìn)

15、來的stream中這個(gè)值計(jì)數(shù)，直到stream結(jié)尾計(jì)數(shù)c存在X.val里做多次，對(duì)最后的X.val，乘2，減1，乘n，然后求平均t = 1時(shí)采， X.el = a，結(jié)束時(shí)，有 X.val = mat = 3時(shí)采， X.el = b，結(jié)束時(shí)，有 X.val = mb分析a如果在最后一個(gè)a采，結(jié)束時(shí)，有X.val = 1如果在倒數(shù)第二個(gè)a采，結(jié)束時(shí)，有X.val = 2如果在t = 1時(shí)采，結(jié)束時(shí)，有X.val = ma求這些 n(2*X.val - 1 ) 的均值因?yàn)樗哉俏覀円耐茝V背后是什么？利用了即(i+1)2 i2 = 2i 1同理，求(mi)3，就對(duì)樣本執(zhí)行再做求和平均推廣，求(mi

16、)k應(yīng)用根據(jù)memory大小，盡可能多隨機(jī)取樣，統(tǒng)計(jì)個(gè)數(shù)對(duì)每個(gè)x.val (c) 求分組組內(nèi)平均組間中值局限對(duì)infinite stream，豈不是越加越大，直到無窮？對(duì)Infinite Stream采用前面介紹過的固定Size采樣辦法采樣Size：k當(dāng)?shù)趎個(gè)元素到達(dá)時(shí)，以k/n的概率留下在采樣的k個(gè)樣本中計(jì)算c近似得到一個(gè)對(duì)整個(gè)流的矩估計(jì)k = 2，Surprise number（奇異數(shù)），Popularity分布均勻的度量衰減窗口發(fā)現(xiàn)流行找出過去1個(gè)月內(nèi)，被看次數(shù)超過1000的視頻？DGIM方法對(duì)每個(gè)視頻，建立一個(gè)1/0流，統(tǒng)計(jì)1的個(gè)數(shù)然后挑出超出1000的視頻大數(shù)據(jù)下，太多視頻，每個(gè)視頻

17、一個(gè)streaming不現(xiàn)實(shí)Youtube，billions of videos指數(shù)衰減窗方法（EDW）啟發(fā)式方法我們關(guān)心的是“現(xiàn)在”流行啥？過去的計(jì)數(shù)，讓它們慢慢衰減熱度 = ai：計(jì)數(shù)c：衰減系數(shù)，一般取10-6, 10-9權(quán)重和：等價(jià)于來一個(gè)新的a，把老熱度乘1 - c（即衰減），然后加上這個(gè)新a實(shí)現(xiàn)起來非常方便實(shí)際中，為了減少存儲(chǔ)，設(shè)一個(gè)閾值（如1/2），權(quán)重低于該閾值的，就不跟蹤了估計(jì)要跟蹤多少個(gè)視頻任意時(shí)刻，所有視頻熱度的和來一個(gè)視頻觀看，以前所有視頻觀看帶來的熱度乘（1-c），再給對(duì)應(yīng)視頻的熱度+1所有視頻觀看帶來的熱度的分布，也是一個(gè)等比級(jí)數(shù)，和為因此，得分超過1/2的電影個(gè)數(shù)不會(huì)超過2/c否則，總分將超過1/c所以，最多只需要跟蹤2/c個(gè)視頻的熱度省發(fā)現(xiàn)流行擴(kuò)展到一籃子（項(xiàng)集Itemsets）如何用EDW對(duì)項(xiàng)集流行度進(jìn)行跟蹤呢？來了一籃子元素B把所有已有的元素/項(xiàng)集的熱度乘 1 c （衰減）加新元素籃子里