大數(shù)據(jù)存儲(chǔ)與應(yīng)用數(shù)據(jù)流挖掘課件_第1頁
大數(shù)據(jù)存儲(chǔ)與應(yīng)用數(shù)據(jù)流挖掘課件_第2頁
大數(shù)據(jù)存儲(chǔ)與應(yīng)用數(shù)據(jù)流挖掘課件_第3頁
大數(shù)據(jù)存儲(chǔ)與應(yīng)用數(shù)據(jù)流挖掘課件_第4頁
大數(shù)據(jù)存儲(chǔ)與應(yīng)用數(shù)據(jù)流挖掘課件_第5頁
已閱讀5頁,還剩59頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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 (衰減)加新元素籃子里

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論