流數(shù)據(jù)分析技術(shù)全套課件

1、流數(shù)據(jù)分析技術(shù)（引言） 1課程情況2課程目標(biāo)3課程內(nèi)容4考核方式5參考資料有什么差別3計算機科學(xué)與技術(shù)軟件工程計算機網(wǎng)絡(luò)大數(shù)據(jù)軟件硬件多機數(shù)據(jù)科學(xué)軟件所處理的內(nèi)容4V數(shù)據(jù)流數(shù)據(jù)在線數(shù)據(jù)人工智能深度學(xué)習(xí)數(shù)據(jù)科學(xué)4數(shù)學(xué)/統(tǒng)計學(xué)Math/Statistics軟件工程Programming/Hacking領(lǐng)域知識DomainKnowledgeModeling/MLAnalysis ResearchData SoftwareEngineer5我們希望從數(shù)據(jù)中得到什么數(shù)據(jù)信息知識洞察智慧無結(jié)構(gòu)有結(jié)構(gòu)可檢索有關(guān)聯(lián)可檢索相關(guān)性可推理關(guān)系型數(shù)據(jù)庫數(shù)據(jù)庫分布式存儲數(shù)據(jù)挖掘人工智能學(xué)的是什么使同學(xué)們理解大數(shù)據(jù)與流數(shù)

2、據(jù)的區(qū)別大數(shù)據(jù)是什么？流數(shù)據(jù)是什么？流數(shù)據(jù)處理與流計算是一個概念嗎？對流式數(shù)據(jù)處理形成自己的觀點和看法對適合流計算的數(shù)據(jù)處理方式和數(shù)據(jù)處理方法有認(rèn)識和一定的掌握能夠“觸類旁通”的學(xué)習(xí)新的流式數(shù)據(jù)處理方法6知其然，知其所以然7課程內(nèi)容引言第一章 大數(shù)據(jù)與流數(shù)據(jù)第二章 流數(shù)據(jù)處理與流計算流數(shù)據(jù)處理模型概要結(jié)構(gòu)流數(shù)據(jù)處理算法Think More, Think Different8課程內(nèi)容第三章 流數(shù)據(jù)概要結(jié)構(gòu)構(gòu)建技術(shù)第四章 流數(shù)據(jù)頻繁模式挖掘技術(shù)第五章 流數(shù)據(jù)聚類分析技術(shù)第六章 流數(shù)據(jù)分類分析技術(shù)第七章 流數(shù)據(jù)時間序列分析技術(shù)第八章 流數(shù)據(jù)處理框架學(xué)習(xí)的關(guān)鍵是抓住其中的“實時性”9考核方式考試：大作

3、業(yè)難度：中體力要求：較高參考資料10交換與智能控制研究中心 流數(shù)據(jù)分析技術(shù)（大數(shù)據(jù)與流數(shù)據(jù)） 1從物聯(lián)網(wǎng)到信息物理系統(tǒng)2從抽樣數(shù)據(jù)到大數(shù)據(jù)3從大數(shù)據(jù)到人工智能4大數(shù)據(jù)與流數(shù)據(jù)從一個例子開始5實際應(yīng)用場景信息社會的基礎(chǔ)電信網(wǎng)絡(luò)2G（程控交換）下一代網(wǎng)絡(luò)3G（軟交換）IMS/FMC互聯(lián)網(wǎng)IPv4下一代互聯(lián)網(wǎng)IPv6Web 2.0移動互聯(lián)網(wǎng)云計算I 云P 云S 云下下一代網(wǎng)絡(luò)3.9G（LTE）4G（LTE-A）5GLTE：Long Term Evolution（長期演進(jìn)）LTE-A：LTE-Advanced（LTE技術(shù)后續(xù)演進(jìn)）IMS：IP Multimedia Subsystem（IP多媒體子系統(tǒng)

4、）FMC：Fixed-Mobile Convergence（固網(wǎng)移動融合）IOT：Internet of ThingsRFID：Radio Frequency Identification個人電腦臺式機筆記本平板大型機小型機PC服務(wù)器傳感網(wǎng)RFID（射頻識別）現(xiàn)場總線M2M物聯(lián)網(wǎng)（IoT）產(chǎn)業(yè)互聯(lián)網(wǎng)人工智能車聯(lián)網(wǎng)（IoV）工業(yè)4.015IoT 與 CPS物聯(lián)網(wǎng)IoT ：Internet of Things 側(cè)重于機器之間的通信過程通過網(wǎng)絡(luò)設(shè)施實現(xiàn)廣域或大范圍的人與物、物與物之間信息交換信息物理系統(tǒng)CPS：Cyber Physical Systems通過3C技術(shù)的有機融合與深度協(xié)作，實現(xiàn)對物的實

5、時、動態(tài)的信息控制與信息服務(wù)強調(diào)與物理世界交互的感知與反饋控制過程，通過計算進(jìn)程和物理進(jìn)程相互影響實現(xiàn)信息空間與物理空間的密切互動信息采集傳輸匯集 分析 處理存儲應(yīng)用感知組網(wǎng)數(shù)據(jù)挖掘 反饋 控制施效計算(Computation)通信(Communication)控制(Control)大規(guī)模數(shù)據(jù)如何使用1從物聯(lián)網(wǎng)到信息物理系統(tǒng)2從抽樣數(shù)據(jù)到大數(shù)據(jù)3從大數(shù)據(jù)到人工智能4大數(shù)據(jù)與流數(shù)據(jù)從一個例子開始5實際應(yīng)用場景17從小規(guī)模數(shù)據(jù)到大規(guī)模數(shù)據(jù)應(yīng)用平臺服務(wù)G-T級T-P級大規(guī)模互聯(lián)網(wǎng)/物聯(lián)網(wǎng)服務(wù)18從小規(guī)模數(shù)據(jù)到大規(guī)模數(shù)據(jù)規(guī)模大 用戶多 總量大 分布廣變化快種類雜數(shù)據(jù)源多樣數(shù)據(jù)類型多樣數(shù)據(jù)結(jié)構(gòu)多樣價值密

6、度低 數(shù)據(jù)高冗余 數(shù)據(jù)特征不明顯 數(shù)據(jù)信息量低 用戶強交互性 數(shù)據(jù)具有傳播性 傳播行為復(fù)雜大數(shù)據(jù)的4V特征19大數(shù)據(jù)的意義揭示宏觀變化規(guī)律發(fā)現(xiàn)不同事物間的關(guān)聯(lián)關(guān)系規(guī)模大少量數(shù)據(jù)無價值抽取目標(biāo)對象的特征百度通過4億用戶分析提供個性化搜索服務(wù)2008年谷歌通過龐大搜索數(shù)據(jù)訓(xùn)練4.5億個數(shù)學(xué)模型，提前幾周預(yù)測出H1N1流感的爆發(fā)和傳播2008年阿里巴巴提前8-9個月預(yù)測出金融危機短時變化無規(guī)律單一來源無特征20從抽樣數(shù)據(jù)到全量數(shù)據(jù)從抽樣到全樣大數(shù)據(jù)數(shù)量大，數(shù)據(jù)統(tǒng)計特征分布不均勻，傳統(tǒng)采樣方法不適用從精確到非精確大數(shù)據(jù)下精確性不再是絕對追求目標(biāo)，需對宏觀趨勢給出快速預(yù)測從因果到關(guān)聯(lián)僅需知其然，無需知其

7、所以然，用于“發(fā)現(xiàn)事實、預(yù)測未來”傳統(tǒng)數(shù)據(jù)處理：抽樣數(shù)據(jù)精確結(jié)果準(zhǔn)確建模SELECT FROM WHERE ORDER BYSUM( ) GROUP BY Google流感預(yù)測采用搜索數(shù)據(jù)取代抽樣百度地圖給出的交通擁堵狀態(tài)及變化趨勢沃爾瑪啤酒尿布商業(yè)案例數(shù)據(jù)價值密度低數(shù)據(jù)變化快數(shù)據(jù)種類雜Inexact近似性Incremental增量性 Inductive歸納性21舉個例子從你的新聞，到我的新聞只有讓人看到的才是新聞新聞的生產(chǎn)新聞的推送22舉個例子內(nèi)容數(shù)據(jù)內(nèi)容獲取內(nèi)容推薦新聞內(nèi)容相關(guān)性知識行為數(shù)據(jù)行為獲取行為相似性知識1從物聯(lián)網(wǎng)到信息物理系統(tǒng)2從抽樣數(shù)據(jù)到大數(shù)據(jù)3從大數(shù)據(jù)到人工智能4大數(shù)據(jù)與流數(shù)

8、據(jù)從一個例子開始5實際應(yīng)用場景面向大數(shù)據(jù)的數(shù)據(jù)挖掘方法挖掘任務(wù)分類預(yù)測（Predication）：用歷史預(yù)測未來描述（Description）：了解數(shù)據(jù)中潛在的規(guī)律挖掘?qū)ο髨鼍懊嫦蚨嘣础⒎墙Y(jié)構(gòu)化數(shù)據(jù)面向流式數(shù)據(jù)，時空數(shù)據(jù)挖掘方法分類分析聚類分析關(guān)聯(lián)分析搜索分析24Incremental增量性 Inductive歸納性Inexact近似性分類通過學(xué)習(xí)得到目標(biāo)函數(shù)（分類模型）將屬性集X映射到預(yù)定義的類歸納和推論的過程分類模型決策樹分類法基于規(guī)則的分類法神經(jīng)網(wǎng)絡(luò)（ANN：Artificial Neural Network）支持向量機（SVM：Support Vector Machines）貝葉斯分類

9、法25分類（Classification）聚類（Cluster）聚類類型劃分聚類層次聚類劃分聚類的序列模糊聚類完全/部分聚類聚類算法K均值（K-Means）K近鄰（KNN：k-Nearest Neighbor）凝聚的層次聚類DBSCAN26k-means: 非監(jiān)督學(xué)習(xí) KNN: 監(jiān)督學(xué)習(xí)分類和聚類的區(qū)別聚類：最大化簇內(nèi)的相似性、最小化簇間相似性類中的對象具有很高相似性，與其他類中的對象很不相似分類：最大化對象與類的相似性類中的對象與類具有很高相似性，但類中的對象不一定具有很高相似性27關(guān)聯(lián)（Association）反映一個事件和其他事件之間依賴或關(guān)聯(lián)的知識如果兩項或多項屬性之間存在關(guān)聯(lián)，那么其

10、中一項的屬性值就可以依據(jù)其他屬性值進(jìn)行預(yù)測相關(guān)性分析Apriori算法/FP-growth算法（Frequent Pattern Tree）（頻繁項）皮爾遜相關(guān)系數(shù)（Pearson correlation coefficient）（線性相關(guān)）主成分分析（Principal Component Analysis）（多個變量間相關(guān)性）回歸分析線性回歸（Linear Regression）（因變量連續(xù)，回歸線的性質(zhì)是線性的）邏輯回歸（Logistic Regression）（因變量屬于二元類型）28關(guān)聯(lián)規(guī)則的例子：尿布 啤酒牛奶，面包 雞蛋，蛋糕啤酒，面包 牛奶TID項集1面包，牛奶2面包，尿布，啤

11、酒，雞蛋3牛奶，尿布，啤酒，可樂4面包，牛奶，尿布，啤酒5面包，牛奶，尿布，可樂搜索最優(yōu)化算法動態(tài)規(guī)劃（Dynamic Programming）常用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，如最短路徑梯度下降法（Steepest Descent）常用于機器學(xué)習(xí)和人工智能當(dāng)中用來遞歸性地逼近最小偏差模型蒙特卡洛樹搜索（Monte Carlo Tree Search）大數(shù)定律，隨機搜索足夠多的點啟發(fā)式算法（heuristic algorithm)模擬退火法(Simulated Annealing）基于蒙特卡洛進(jìn)行串行搜索優(yōu)化遺傳算法（Genetic Algorithm）基于生物進(jìn)化和遺傳進(jìn)行全局最

12、優(yōu)化蟻群算法（Ant Colony Algorithm）強化學(xué)習(xí)功能的全局性并行優(yōu)化算法29淺層學(xué)習(xí)（Shallow Learning）BP神經(jīng)網(wǎng)絡(luò)存在的問題神經(jīng)網(wǎng)絡(luò)容易過擬合，參數(shù)比較難調(diào)訓(xùn)練速度比較慢，在層次比較少（小于等于3）的情況下效果并不比其它方法更優(yōu)改進(jìn)方法支撐向量機（SVM）Boosting最大熵方法（LR：Logistic Regression 邏輯回歸）等共同特點基本上可以看成帶有一層隱層節(jié)點（如SVM、Boosting），或沒有隱層節(jié)點（如LR）局限性有限樣本和計算單元情況下對復(fù)雜函數(shù)的表示能力有限針對復(fù)雜分類問題其泛化能力受到一定制約30深度學(xué)習(xí)（Deep Learnin

13、g）提出2006年，加拿大多倫多大學(xué)教授Geoffrey Hinton和他的學(xué)生Ruslan Salakhutdinov提出一種基于無監(jiān)督特征學(xué)習(xí)和特征層次結(jié)構(gòu)的學(xué)習(xí)方法特點采用多隱層的人工神經(jīng)網(wǎng)絡(luò)深度神經(jīng)網(wǎng)絡(luò)（多層的好處是可以用較少的參數(shù)表示復(fù)雜的函數(shù)）可通過學(xué)習(xí)一種深層非線性網(wǎng)絡(luò)結(jié)構(gòu)，實現(xiàn)復(fù)雜函數(shù)逼近，表征輸入數(shù)據(jù)分布式表示通過“逐層初始化”（Layer-wise Pre-training）來克服訓(xùn)練上的難度（通過無監(jiān)督學(xué)習(xí)）本質(zhì)“深度模型”是手段“特征學(xué)習(xí)”是目的31通過構(gòu)建具有很多隱層的機器學(xué)習(xí)模型和海量的訓(xùn)練數(shù)據(jù)，來學(xué)習(xí)更有用的特征人工神經(jīng)網(wǎng)絡(luò)的第三次興起32從淺層學(xué)習(xí)向深度學(xué)習(xí)演進(jìn)

14、大數(shù)據(jù)算力1從物聯(lián)網(wǎng)到信息物理系統(tǒng)2從抽樣數(shù)據(jù)到大數(shù)據(jù)3從大數(shù)據(jù)到人工智能4大數(shù)據(jù)與流數(shù)據(jù)從一個例子開始5實際應(yīng)用場景一個例子一些實際問題判斷特定IP是不是第一次訪問網(wǎng)站？訪問了多少次？數(shù)據(jù)庫高速緩存網(wǎng)站高速緩存Web服務(wù)MySQL數(shù)據(jù)庫Redis緩存瀏覽器查詢緩存查詢結(jié)果數(shù)據(jù)庫查詢變長數(shù)據(jù)內(nèi)容哈希哈希（Hash）把任意長度輸入通過Hash算法變換成固定長度輸出代表算法：MD5, SHA128, SHA256（32/128/256Bytes）一般是壓縮映射，不可逆映射挑戰(zhàn)如果實際數(shù)據(jù)需求遠(yuǎn)遠(yuǎn)超過內(nèi)存大小？如：200,000,000量級32bit整數(shù)： 200,000,0004Bytes 763

15、MBytesMD5數(shù)字字串：200,000,00016Bytes 3GBytesMD5文本字串：200,000,00032Bytes 6GBytes0230c58281e3661b854e6f480e703d60f7173baa68212ee5fc06db4099f76454687b4aec753c2727cf66ed15d9f4eedf哈希映射？/c/7qvDJ5HbryS快速查詢哈希表哈希表（Hash Map）利用線性表存儲集合元素利用Hash函數(shù)計算元素對應(yīng)的地址Entry，并在對應(yīng)的區(qū)域存儲該元素實際查找通過先hash計算Entry，再匹配元素是否相同（哈希值匹配）優(yōu)勢解決沖突查找復(fù)雜

16、（拉鏈法等）準(zhǔn)確率100%問題填充稀疏為避免沖突，填充率50%均衡空間與效率布隆過濾器布隆過濾器 BF（Bloom Filter）1970年Burton Bloom在論文Space/time trade-offs in hash coding with errors中提出核心思想用一系列隨機映射函數(shù)解決一個映射函數(shù)的沖突問題用一個很長的二進(jìn)制向量來解決存儲空間爆炸問題準(zhǔn)確率換空間思想延伸優(yōu)點空間效率和查詢時間都遠(yuǎn)超過一般的算法缺點有一定的誤識別率，刪除困難應(yīng)用用于檢索一個元素是否在一個集合中布隆過濾器設(shè)計思想用一個很長的二進(jìn)制向量來解決存儲空間爆炸問題用一個包含m位的二進(jìn)制位數(shù)組存儲BITMA

17、P12345678mHashData1Data2m-1m-2m-3m-4m-5m-6m-7BITMAP00010000000000000000100000000000如果沖突怎么辦？Data30000100000000000布隆過濾器設(shè)計思想用一系列隨機映射函數(shù)解決一個映射函數(shù)的沖突問題K個相互獨立的哈希函數(shù)映射到1,m的范圍12345678mH1H2H3HkData10001001001000100m-1m-2m-3m-4m-5m-6m-7Data20001001000010010BITMAP布隆過濾器的使用使用判斷數(shù)據(jù) y 是否在集合 S=x1, x2,xn 中存在計算y的k個哈希函數(shù)的取

18、值判斷BITMAP相應(yīng)的位置取值是否為1400110111001110110BITMAPH1H2H3HkData3Data40110布隆過濾器的問題存在誤報哈希函數(shù)存在沖突BITMAP中的每一位是k個哈希函數(shù)映射結(jié)果的疊加410111111001110111BITMAPH1H2H3HkData1Data2Data3假陽性 FP（False Positive） 計數(shù)型布隆過濾器BF/SBF（Standard Bloom Filter）m長BITMAP的每一個槽位只有1位，只能表示0, 1，代表“有”或“無”缺點：無法刪除數(shù)據(jù)計數(shù)型布隆過濾器 CBF（Counting Bloom Filter）將

19、m長BITMAP的每一個槽位修改為多位，形成COUNTER_MAP，如3位，則可以表示0,1,7優(yōu)點：可以刪除數(shù)據(jù)插入數(shù)據(jù)時，Counter自增；刪除數(shù)據(jù)時，Counter自減流數(shù)據(jù)最重要的特點43數(shù)據(jù)的持續(xù)抵達(dá)數(shù)據(jù)的高基數(shù)數(shù)據(jù)的特征變化 1從物聯(lián)網(wǎng)到信息物理系統(tǒng)2從抽樣數(shù)據(jù)到大數(shù)據(jù)3從大數(shù)據(jù)到人工智能4大數(shù)據(jù)與流數(shù)據(jù)從一個例子開始5實際應(yīng)用場景行為學(xué)習(xí)：基于用戶通信記錄（含：主被叫、通話時間、通話頻度、通話行為、特殊號碼類型等）進(jìn)行無監(jiān)督和有監(jiān)督的學(xué)習(xí)，建立行為特征模式分類器訓(xùn)練：基于行為特征模式，訓(xùn)練電信詐騙鑒別分類器電信詐騙識別：通話記錄進(jìn)入分類器，識別潛在的電信詐騙風(fēng)險號碼45結(jié)合通信

20、記錄的電信詐騙鑒別基于移動軌跡大數(shù)據(jù)的模式挖掘發(fā)現(xiàn)移動對象在一定時空約束下共同行使所形成的行為模式，以識別潛在的異常根據(jù)交通大數(shù)據(jù)挖掘潛在的出行規(guī)律、需求，及相應(yīng)的變化趨勢46移動聚集模式挖掘算法城市交通結(jié)構(gòu)挖掘算法 駕車出行模式公交出行模式城市交通熱點聚集模式發(fā)現(xiàn)城市交通結(jié)構(gòu)T3T1&2四惠(walk, cycle, bus, subway, car)( 0, 0, 44.40, 40.25, 15.35)%基于移動軌跡大數(shù)據(jù)的規(guī)劃與調(diào)度47基于公交軌跡大數(shù)據(jù)的公交車到站時間預(yù)測算法電動汽車有序充電路線規(guī)劃與調(diào)度算法分時租賃站點規(guī)劃與車輛調(diào)度算法智能排班路線規(guī)劃、建設(shè)規(guī)劃特種車隊運控特殊路段

21、聯(lián)控移動群智信息感知與調(diào)度如何基于車聯(lián)網(wǎng)采集并恢復(fù)城市環(huán)境狀態(tài)，以應(yīng)對數(shù)據(jù)的稀疏性48任務(wù)發(fā)布與信息感知過程t-nt-n+1t-2t-1tTime slotLocation基于相鄰加權(quán)條件熵的缺失信息預(yù)測與矩陣補全按照序列相似性聚類，進(jìn)行誤差分析與糾錯基于稀疏數(shù)據(jù)的環(huán)境狀態(tài)認(rèn)知智慧城市感知節(jié)點部署數(shù)量不足，數(shù)據(jù)不能反映全局狀況，難以支撐決策路網(wǎng)監(jiān)控設(shè)施覆蓋不全空氣質(zhì)量采樣點無法全面覆蓋車輛移動過程中監(jiān)控數(shù)據(jù)中斷車聯(lián)網(wǎng)云-端協(xié)同感知與計算引入邊緣和云端，實現(xiàn)車輛群體的群智計算，以滿足信息感知、最優(yōu)決策等需求49垂直切換垂直切換水平交互水平交互邊緣遷移基于鄰近傳播的領(lǐng)導(dǎo)人選舉基于群體博弈的自適應(yīng)決

22、策車聯(lián)網(wǎng)人車、車網(wǎng)協(xié)同模型基于多車協(xié)作的群智認(rèn)知交換與智能控制研究中心 流數(shù)據(jù)分析技術(shù)（流數(shù)據(jù)與流計算綜述） 1流數(shù)據(jù)2流數(shù)據(jù)處理3流數(shù)據(jù)分析方法4流數(shù)據(jù)機器學(xué)習(xí)5小結(jié)設(shè)想一下這些場景云計算AWS 有 810 萬個活躍 IP 地址阿里云有 260 萬個活躍 IP 地址微軟有 171 萬個活躍 IP 地址大規(guī)模云計算如何進(jìn)行管理和維護(hù)？54設(shè)想一下這些場景2014年12月，阿里云抵御的DDoS攻擊峰值流量達(dá)到 453.8Gbps2018年02月，攻擊GitHub的DDoS流量達(dá)到 1.3Tbps2018年03月，攻擊Netscout的DDoS流量達(dá)到 1.7 Tbps2020年02月，亞馬遜AW

23、S Shield攔截的DDoS攻擊流量 2.3Tbps55分析一下這個攻擊流程劫持肉雞遞歸查詢?nèi)怆u冒充地址向目標(biāo)DNS發(fā)送地址解析請求DNS向目標(biāo)地址反饋DNS解析結(jié)果返回地址記錄在哪里阻斷？56攻擊流量清洗實時判斷流量是否存在異常攔截決策攔截執(zhí)行異常攔截流數(shù)據(jù)處理流數(shù)據(jù)的特點（一）數(shù)據(jù)的持續(xù)抵達(dá)實時性：限定時間完成易失性：不可追溯突發(fā)性：不可預(yù)測無序性：無前后邏輯關(guān)聯(lián)57t0t1t2t3t4t5帶來的要求：處理時間要求數(shù)據(jù)精度與實時性需要平衡數(shù)據(jù)流t0t1t2數(shù)據(jù)流t3t4t5流數(shù)據(jù)處理t0+4t0+3t0+2t0+1流數(shù)據(jù)的特點（一）數(shù)據(jù)的持續(xù)抵達(dá)實時性：限定時間完成易失性：不可追溯突發(fā)性

24、：不可預(yù)測無序性：無前后邏輯關(guān)聯(lián)58數(shù)據(jù)流t0t1t2數(shù)據(jù)流t3t4t5流數(shù)據(jù)處理緩存t1t2帶來的要求：緩存容量要求緩存時效要求數(shù)據(jù)精度與緩存容量需要平衡流數(shù)據(jù)的特點（一）數(shù)據(jù)的持續(xù)抵達(dá)實時性：限定時間完成易失性：不可追溯突發(fā)性：不可預(yù)測無序性：無前后邏輯關(guān)聯(lián)59流數(shù)據(jù)流數(shù)據(jù)處理t0t1t2t7t8t9帶來的要求：數(shù)據(jù)到達(dá)量變化無法預(yù)期最大量數(shù)據(jù)重要度與處理性能需要平衡流數(shù)據(jù)的特點（一）數(shù)據(jù)的持續(xù)抵達(dá)實時性：限定時間完成易失性：不可追溯突發(fā)性：不可預(yù)測無序性：無前后邏輯關(guān)聯(lián)60流數(shù)據(jù)t0t1t2t7t8t9流數(shù)據(jù)處理帶來的要求：不一定有序抵達(dá)不一定存在關(guān)聯(lián)不能依賴數(shù)據(jù)的內(nèi)在長期關(guān)聯(lián)流數(shù)據(jù)的特

25、點（二）數(shù)據(jù)的高基數(shù)（High-Cardinality）高基數(shù)“長尾” 61基數(shù)（Cardinality）：數(shù)據(jù)中不同類別的數(shù)量流數(shù)據(jù)處理緩存IP地址計數(shù)IP110IP288IPn100基數(shù) = n帶來的要求：不一定能完整記錄n個標(biāo)簽成本高壓力大流數(shù)據(jù)的特點（二）數(shù)據(jù)的高基數(shù)（High-Cardinality）高基數(shù)“長尾” 62流數(shù)據(jù)處理緩存IP地址計數(shù)IP110IP25IPm100001IPm+199876IPn-1105IPn172數(shù)量類別帶來的要求：無法預(yù)期誰是“長尾”判斷難度大基數(shù)（Cardinality）：數(shù)據(jù)中不同類別的數(shù)量流數(shù)據(jù)的特點（三）數(shù)據(jù)的統(tǒng)計特征變化63概念漂移（Con

26、cept Drift） 從流數(shù)據(jù)中獲得的統(tǒng)計特征可能隨時間而變化設(shè)：流數(shù)據(jù)是一個狀態(tài)序列 S=S1, S2,. . . ,SN Si 由分布 Di 生成概念漂移可以定義為： 一個由分布變化 Dj=Dj+1 導(dǎo)致的狀態(tài)遷移 Sj Sj+1流數(shù)據(jù)的特點（三）數(shù)據(jù)的統(tǒng)計特征變化64概念漂移（Concept Drift） 從流數(shù)據(jù)中獲得的統(tǒng)計特征可能隨時間而變化8:0012:0018:00例如：基于細(xì)粒度交通數(shù)據(jù)計算交通指標(biāo)（密度、時距等）帶來的要求：數(shù)據(jù)的分布規(guī)律隨時間變化而變?nèi)绾握{(diào)整以適應(yīng)變化Di Si 流數(shù)據(jù)的特點（三）概念漂移（Concept Drift）對學(xué)習(xí)分類邊界的影響變化類型的影響 6

27、5實概念漂移：影響后驗概率/無條件概率密度函數(shù)，影響決策邊界虛概念漂移：影響條件概率密度函數(shù)，不影響決策邊界初始分布實概念漂移虛概念漂移流數(shù)據(jù)的特點（三）概念漂移（Concept Drift）對學(xué)習(xí)分類邊界的影響變化類型的影響 突發(fā)概念漂移（Sudden Concept Drift）漸進(jìn)概念漂移（Gradual Concept Drift）增量概念漂移（Incremental Concept Drift）66DjDj+1 Sj Sj+1Dj Dj+1混合Dj Dj+1緩慢變化Di 流數(shù)據(jù)的特點（三）概念漂移（Concept Drift）對學(xué)習(xí)分類邊界的影響變化類型的影響 經(jīng)常性概念漂移（Rec

28、urring Concept Drift）異常值（Blips）噪聲（Noise）67Dj+1=Dj-k Sj Sj+1偶發(fā)，隨機細(xì)小的波動Di 流數(shù)據(jù)的特點（三）概念漂移（Concept Drift）對學(xué)習(xí)分類邊界的影響變化類型的影響 混合概念漂移（Mixed Concept Drift）68Di 流數(shù)據(jù)定義流數(shù)據(jù)是一種實時到達(dá)的具有規(guī)模大、基數(shù)高、統(tǒng)計特征復(fù)雜變化特性的數(shù)據(jù)流69 t ：時間戳at ：該時間戳到達(dá)的數(shù)據(jù)數(shù)據(jù)的時間序列1流數(shù)據(jù)2流數(shù)據(jù)處理3流數(shù)據(jù)分析方法4流數(shù)據(jù)機器學(xué)習(xí)5小結(jié)離線大數(shù)據(jù)的批處理批處理模型（Batch Data Processing Model） 傳統(tǒng)大數(shù)據(jù)處理模

29、型 核心思想：先存儲，再分析71全量入庫離線分析特點：數(shù)據(jù)處理算法可以按照任意方式對全量數(shù)據(jù)進(jìn)行任意次數(shù)的遍歷離線大數(shù)據(jù)的批處理批處理模型核心思想：先存儲，再分析72Data Warehouse無界數(shù)據(jù)批處理有界數(shù)據(jù)入庫數(shù)據(jù)固定窗口批處理會話窗口批處理a+b+cd+e+fh+i+ja+b+cmapreduce常用批處理方法MapReduce：海量大數(shù)據(jù)分布式處理模型例子計算通話頻度73a+b+cd+e+fh+i+ja+b+cmapreduce用戶通話記錄按時間片分割分別統(tǒng)計合并4565特點：可以通過數(shù)據(jù)遍歷發(fā)現(xiàn)數(shù)據(jù)特征，并據(jù)此分割數(shù)據(jù)塊，以保障map不破壞數(shù)據(jù)的原始特征分布，或reduce能夠

30、恢復(fù)特征流數(shù)據(jù)處理流式處理模型（Stream Data Processing Model） 流計算（Stream Computing） 核心思想：數(shù)據(jù)在線持續(xù)處理74特點：數(shù)據(jù)處理算法僅能對當(dāng)前緩存內(nèi)的數(shù)據(jù)進(jìn)行遍歷，僅能通過概要數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)特征的歷史記憶在線分析數(shù)據(jù)入庫概要存儲與查詢tntn+1流數(shù)據(jù)處理概要數(shù)據(jù)結(jié)構(gòu)（Synopsis Data Structure） 在有限空間條件下存儲的對流數(shù)據(jù)的一種特征描述精度可接受實時響應(yīng)75例如：查詢訪問網(wǎng)站的獨立IP地址共訪問了多少次通過歷史數(shù)據(jù)挖掘：準(zhǔn)確，但需要10分鐘返回結(jié)果通過計數(shù)型布隆過濾器處理：大致準(zhǔn)確，但只需0.1秒返回結(jié)果概要數(shù)據(jù)：

31、流數(shù)據(jù)處理算法的算法緩存和結(jié)果記錄流處理與批處理的對比流處理批處理輸入方式數(shù)據(jù)流數(shù)據(jù)塊數(shù)據(jù)量無界數(shù)據(jù)有界數(shù)據(jù)存儲內(nèi)存緩存，非持久化持久化存儲硬件設(shè)施有限內(nèi)存更多的CPU與內(nèi)存處理方式一次遍歷多次遍歷時間需求秒級，甚至毫秒級長應(yīng)用場景實時類需求應(yīng)用廣泛場景76流式處理與窗口模型77流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類時間無關(guān)型過濾型內(nèi)聯(lián)型78數(shù)據(jù)篩選，對數(shù)據(jù)本身的順序、抵達(dá)時間偏差等不敏感對多源數(shù)據(jù)進(jìn)行關(guān)聯(lián)，對數(shù)據(jù)本身的順序、抵達(dá)時間偏差等不敏感，但需要緩沖數(shù)據(jù)以等待關(guān)聯(lián)流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類窗口型固定窗口滑動窗口會話窗口多尺度窗口79固定窗口（Fixed Window）快照（Snapsh

32、ot）t 不能太大，要滿足 實時性要求流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類窗口型固定窗口滑動窗口會話窗口多尺度窗口80時間滑動窗口（Timebased Sliding Window /Time-Sliding Window）時間窗口大于處理時間間隔 t ti+1 - ti 衰減窗口（Damped Window）通過衰減因子使得窗口內(nèi)不同時間到達(dá)的數(shù)據(jù)對整體的影響不同注意：數(shù)據(jù)可不一定是均勻速率抵達(dá)的流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類窗口型固定窗口滑動窗口會話窗口多尺度窗口81內(nèi)容滑動窗口（ Content based Sliding Window ）按照固定的數(shù)據(jù)量 W 劃分窗口隨著數(shù)據(jù)到達(dá)，超過窗

33、口大小的舊數(shù)據(jù)將會被拋棄，適合對數(shù)據(jù)量有要求的場景衰減窗口（Damped Window）通過衰減因子區(qū)分抵達(dá)時間新舊的影響更要注意：數(shù)據(jù)不一定是均勻速率抵達(dá)流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類窗口型固定窗口滑動窗口會話窗口多尺度窗口82會話窗口（ Session）按照特定條件篩選數(shù)據(jù)形成會話窗口 S會話窗口是一種內(nèi)容滑動窗口主要用于多源混雜數(shù)據(jù)拆分根據(jù)條件形成多個會話，每個會話可形成一個內(nèi)容滑動窗口流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類窗口型固定窗口滑動窗口會話窗口多尺度窗口近似型83固定、滑動、會話窗口的混合應(yīng)用近似型采用一個類似會話窗口的可變窗口，但窗口的邊界確定規(guī)則改為由近似算法確定流式處理與概要

34、結(jié)構(gòu)84常用的概要結(jié)構(gòu)抽樣（Sampling）從原始數(shù)據(jù)集N中抽取小部分樣本形成樣本集S，代表整合數(shù)據(jù)集，從而減小數(shù)據(jù)集規(guī)模直方圖（Histograms）將一個大數(shù)據(jù)集按照一定規(guī)則劃分為小數(shù)據(jù)集（桶，bucket），并通過對每個小數(shù)據(jù)集的特征分析，來刻畫大數(shù)據(jù)集的特征輪廓小波（Wavelets）小波是一種通用的數(shù)字信號處理技術(shù)，類似于傅立葉變換，可根據(jù)輸入的模擬量，變換成一系列的小波參數(shù)草圖（Sketches）使用概率數(shù)據(jù)結(jié)構(gòu)（Probabilistic Data Structures）來抽取流數(shù)據(jù)的特征，以減小內(nèi)存占用并降低處理時延85概要數(shù)據(jù)結(jié)構(gòu)構(gòu)建需求近似查詢估計（Approximate

35、 Query Estimation）實時性和準(zhǔn)確性的平衡抽樣、直方圖、小波和草圖等近似連接估計（Approximate Join Estimation）評估連接的大小、強弱草圖計算聚合（Computing Aggregates）計算頻繁項、分位數(shù)（Quantiles）、命中率（Heavy Hitter）等草圖或直方圖其他數(shù)據(jù)挖掘類應(yīng)用（Data Mining Applications）聚類、分類、異常檢測、回歸預(yù)測等86概要數(shù)據(jù)結(jié)構(gòu)設(shè)計原則適用性概要數(shù)據(jù)結(jié)構(gòu)能夠適用更多場景，避免為每個應(yīng)用計算不同的結(jié)構(gòu)提高概要結(jié)構(gòu)的時間和空間效率單次約束在計算過程中不能多次檢查流的內(nèi)容在一次通過約束下設(shè)計時空

36、效率一些方法（如動態(tài)規(guī)劃）需要超線性的空間和時間，對流數(shù)據(jù)不可接受健壯性由于概要結(jié)構(gòu)只能依據(jù)有限時空數(shù)據(jù)生成，其結(jié)果可能存在偏差需要設(shè)計魯棒性度量（允許的最大誤差度量）進(jìn)化敏感數(shù)據(jù)流不一定存在穩(wěn)定分布，其隨著時間的推移會迅速發(fā)展概要結(jié)構(gòu)需要對數(shù)據(jù)變化有更高敏感度，也可以用于預(yù)測871流數(shù)據(jù)2流數(shù)據(jù)處理3流數(shù)據(jù)分析方法4流數(shù)據(jù)機器學(xué)習(xí)5小結(jié)設(shè)想一個場景用戶刷新新聞的最高頻度是什么？在使用新聞服務(wù)的用戶中，用戶刷新新聞的頻度有什么分布特征？針對某個用戶，其刷新新聞的頻度屬于那種類型？針對某個用戶，或整個服務(wù)系統(tǒng)，是否可以預(yù)測未來的刷新頻度？流數(shù)據(jù)分析方法用戶刷新新聞的最高頻度是什么？在使用新聞服務(wù)

37、的用戶中，用戶刷新新聞的頻度有什么分布特征？針對某個用戶，其刷新新聞的頻度屬于那種類型？針對某個用戶，或整個服務(wù)系統(tǒng)，是否可以預(yù)測未來的刷新頻度？90頻繁項挖掘算法（Frequent Items/Pattern Mining）聚類算法（Clustering）分類算法（Classification）回歸算法（Regression）頻繁項挖掘算法頻繁項（Frequent Items）流數(shù)據(jù)中指定項目出現(xiàn)的頻繁程度核心是計數(shù)問題頻繁模式（Frequent Pattern）流數(shù)據(jù)中頻繁出現(xiàn)的模式或結(jié)構(gòu)項目集合（Item sets）序列（Sequences）樹/子樹（Trees）圖/子圖（Graphs）

38、面臨的挑戰(zhàn)需要具有很高的內(nèi)存效率流數(shù)據(jù)持續(xù)抵達(dá)，不能多次遍歷流數(shù)據(jù)高基數(shù)，搜索空間可能指數(shù)增長需要具有實時性流數(shù)據(jù)存在概念漂移，當(dāng)前頻繁，可能過一段時間就不頻繁了91用戶刷新新聞的最高頻度是什么？聚類算法聚類（Clustering）把數(shù)據(jù)按照一定的規(guī)則分成幾個簇簇內(nèi)對象具有高相似度，簇間對象具有較高相異度面臨的挑戰(zhàn)需要支持聚類中心的動態(tài)迭代流數(shù)據(jù)持續(xù)抵達(dá)，不會對歷史數(shù)據(jù)進(jìn)行持續(xù)保存聚類處理過程必須是增量式的，聚類中心需要動態(tài)計算和迭代離群點影響變大，需要糾偏傳統(tǒng)聚類方法可以通過優(yōu)化中心點選取避免離群點影響流數(shù)據(jù)難以通過對原始數(shù)據(jù)的多次遍歷完成對離群點的糾偏92用戶刷新新聞的頻度具有什么分布特征

39、？分類算法分類（Classification）學(xué)習(xí)一個分類函數(shù)或分類模型并使用該函數(shù)或模型將數(shù)據(jù)項映射到指定類別中的某個類別對象與類具有更近的距離面臨的挑戰(zhàn)難以獲得預(yù)先標(biāo)注的標(biāo)簽如無法預(yù)先標(biāo)注，則需要依賴聚類算法學(xué)習(xí)分簇數(shù)據(jù)流持續(xù)抵達(dá)，難以多次遍歷數(shù)據(jù)傳統(tǒng)分類方法需多次遍歷數(shù)據(jù)以完成最佳分裂值設(shè)置難以應(yīng)用需要全體樣本距離的算法概念漂移導(dǎo)致分類器失效概念漂移導(dǎo)致訓(xùn)練好的分類器有效性短暫93用戶刷新新聞的頻度屬于哪一類？回歸算法回歸（Regression）學(xué)習(xí)一個函數(shù)或模型，估計一個或多個自變量與因變量之間的關(guān)系判斷自變量與因變量是否存在影響，并估計未知參數(shù)的取值對輸入樣本進(jìn)行“擬合”，并保證誤差

40、最小面臨的挑戰(zhàn)數(shù)據(jù)流持續(xù)抵達(dá)，需要動態(tài)增量更新需要在已有函數(shù)基礎(chǔ)上，使用新到達(dá)的數(shù)據(jù)迭代更新離群點影響變大，影響回歸精度流數(shù)據(jù)難以使用長期數(shù)據(jù)過濾離群點離群點訓(xùn)練回歸模型，影響回歸精度概念漂移導(dǎo)致回歸失效概念漂移導(dǎo)致訓(xùn)練好的回歸模型有效性短暫94是否可以估計這類用戶未來的刷新頻度？過去現(xiàn)在將來1流數(shù)據(jù)2流數(shù)據(jù)處理3流數(shù)據(jù)分析方法4流數(shù)據(jù)機器學(xué)習(xí)5小結(jié)機器學(xué)習(xí)機器學(xué)習(xí)（Machine Learning）一種生產(chǎn)算法的算法通過特征的提取，去訓(xùn)練并獲得一個能夠?qū)崿F(xiàn)聚類、分類、回歸等特定目的的算法模型流數(shù)據(jù)環(huán)境下的機器學(xué)習(xí)方法基于流數(shù)據(jù)的窗口機制，在窗口上使用傳統(tǒng)機器學(xué)習(xí)算法優(yōu)點：能夠使用傳統(tǒng)機器學(xué)習(xí)

41、方法缺點：由于流數(shù)據(jù)的窗口限制，難以獲得全面的特征來描述流數(shù)據(jù)根據(jù)流數(shù)據(jù)持續(xù)抵達(dá)的特點，在每一個時間點上，通過算法進(jìn)行動態(tài)預(yù)測，從而支持模型的時間進(jìn)化優(yōu)點：考慮了流數(shù)據(jù)的特點缺點：場景受限96流數(shù)據(jù)機器學(xué)習(xí)分類在線學(xué)習(xí)（Online Learning）根據(jù)線上實時反饋的數(shù)據(jù)進(jìn)行模型調(diào)整，從而提高在線預(yù)測的準(zhǔn)確率主要針對時間序列數(shù)據(jù)，解決基于回歸的預(yù)測問題分類：基于值：針對時間點t獲得的一個觀察樣本和預(yù)測樣本，計算遺憾值（Regret）邊界基于概率：給定參數(shù)先驗，在數(shù)據(jù)到達(dá)后計算后驗，并將其作為下一次預(yù)測的先驗增量學(xué)習(xí)（Incremental Learning）在獲得新數(shù)據(jù)樣本后，在保存大部分已

42、經(jīng)學(xué)習(xí)到的知識基礎(chǔ)上，從新樣本中提取新的知識需要成批的處理增量數(shù)據(jù)，更適合時間窗口式的流數(shù)據(jù)微批處理演化學(xué)習(xí)（Evolutionary Learning）基于演化算法（Evolutionary Algorithms）動態(tài)尋優(yōu)主要是解決參數(shù)優(yōu)化、調(diào)度決策等問題971流數(shù)據(jù)2流數(shù)據(jù)處理3流數(shù)據(jù)分析方法4流數(shù)據(jù)機器學(xué)習(xí)5小結(jié)知識點99知識點100交換與智能控制研究中心 流數(shù)據(jù)分析技術(shù)（流數(shù)據(jù)概要結(jié)構(gòu)） 1流數(shù)據(jù)概要結(jié)構(gòu)2抽樣概要結(jié)構(gòu)3草圖概要結(jié)構(gòu)4直方圖概要結(jié)構(gòu)5小波概要結(jié)構(gòu)流數(shù)據(jù)的概要結(jié)構(gòu)概要數(shù)據(jù)結(jié)構(gòu)（Synopsis Data Structure） 一種按照流數(shù)據(jù)處理模型，使用一定流數(shù)據(jù)分析技術(shù)

43、，構(gòu)建出的一個流數(shù)據(jù)的主要特征集目的對流數(shù)據(jù)關(guān)鍵特征的抽取，以方便應(yīng)用快速查詢?yōu)槠渌疃鹊牧鲾?shù)據(jù)特征挖掘提供基礎(chǔ)104常用的概要結(jié)構(gòu)抽樣（Sampling）從原始數(shù)據(jù)集N中抽取小部分樣本形成樣本集S，代表整合數(shù)據(jù)集，以減小數(shù)據(jù)集規(guī)模保證樣本集與原始數(shù)據(jù)集的同分布，可以將傳統(tǒng)數(shù)據(jù)挖掘處理方法應(yīng)用到概要數(shù)據(jù)結(jié)構(gòu)上草圖（Sketches）用專用數(shù)據(jù)結(jié)構(gòu)抽取流數(shù)據(jù)特征，以快速抽取常用的統(tǒng)計型的指標(biāo)，以減小內(nèi)存占用并降低處理時延在最少的空間占用和最快的查詢速度之間進(jìn)行平衡，加速對流數(shù)據(jù)特征的查詢響應(yīng)速度105常用的概要結(jié)構(gòu)小波（Wavelets）小波是一種通用的數(shù)字信號處理技術(shù)，類似于傅立葉變換，可根

44、據(jù)輸入的模擬量，變換成一系列的小波參數(shù)用多階誤差樹來刻畫原始數(shù)據(jù)，高階系數(shù)反映數(shù)據(jù)的大趨勢，低階系數(shù)反映更局部的趨勢直方圖（Histograms）將大數(shù)據(jù)集按照一定規(guī)則劃分為小數(shù)據(jù)集（桶，bucket），通過對每個小數(shù)據(jù)集的特征分析來刻畫大數(shù)據(jù)集的特征輪廓通過與抽樣、小波、草圖等不同的方法整合，實現(xiàn)對概要結(jié)構(gòu)的不同輪廓的刻畫1061流數(shù)據(jù)概要結(jié)構(gòu)2抽樣概要結(jié)構(gòu)3草圖概要結(jié)構(gòu)4直方圖概要結(jié)構(gòu)5小波概要結(jié)構(gòu)抽樣與抽樣概要結(jié)構(gòu)抽樣（Sampling）從原始數(shù)據(jù)集 N 中抽取小部分樣本形成樣本集 S代表整個數(shù)據(jù)集目的：減小數(shù)據(jù)集規(guī)模，使得傳統(tǒng)數(shù)據(jù)挖掘算法能夠被應(yīng)用到大規(guī)模數(shù)據(jù)集或流數(shù)據(jù)集特點是一種近似

45、技術(shù)能夠提供可證明的無偏估計和誤差保證易于應(yīng)用到高維場景108抽樣的形式化定義設(shè)流數(shù)據(jù)全集為： N數(shù)據(jù)內(nèi)容為： X1Xn 預(yù)期的數(shù)據(jù)挖掘結(jié)果： f(N) 獲得函數(shù)抽樣基于抽樣集合： S獲得抽樣函數(shù)： f(S)條件：能夠通過對函數(shù) f(S) 的均值 和標(biāo)準(zhǔn)差 等的計算 估計函數(shù) f(N)用于估計 f(S) 概率界限的這些不等式被稱為尾界 （Tail Bounds）109抽樣分類均勻抽樣（Uniform Sampling）數(shù)據(jù)集 N 中不同元素入選樣本集合 S 的概率相同如：使用固定的時間間隔進(jìn)行抽樣偏倚抽樣（Biased Sampling）數(shù)據(jù)集 N 中不同元素入選樣本集合 S 的概率不同如：考

46、慮空間網(wǎng)格劃分，基于密度不同設(shè)置不同的概率進(jìn)行抽樣混合抽樣均勻抽樣與偏倚抽樣聯(lián)合110均勻抽樣分類伯努利抽樣（Bernoulli Sampling）設(shè)：數(shù)據(jù)集 N 中各元素 X1Xn 服從伯努利分布（Bernoulli Distribution，或稱0-1分布）入選概率： p(0 , 1落選概率： q=1 - p抽樣概率： P(S; N) = p|S| (1 - p)|N|-|S|優(yōu)點：采樣均勻，過程簡單，時間成本低缺點：需要對數(shù)據(jù)集分布概率需要有預(yù)知水庫抽樣（Reservoir Sampling）設(shè)：樣本集 S 的大小為 s入選：第 n 個抽樣樣本的入選概率為 s/n去除：如果當(dāng)前樣本集合中

47、的樣本量超過抽樣集大小 s，從樣本集合 S 中隨機去除一個樣本優(yōu)點：各元素入選抽樣數(shù)據(jù)集合的概率相同（隨機均勻抽樣）111pppps/ns/ns/ns/n隨機刪除均勻抽樣分類簡明抽樣（Concise Sampling）擴(kuò)展水庫抽樣，每個采樣點一個計數(shù)器入選： 1/ 1/ （ ，概率逐漸變?。┤コ?/優(yōu)點：支持重復(fù)數(shù)據(jù)均勻抽樣鏈?zhǔn)匠闃樱–hain Sampling）針對滑動窗口設(shè)：滑動窗口大小 W 入選：第 n 個抽樣樣本的入選概率 1/min(n,W)替換：從n+1n+W中隨機選擇備選樣本，在抵達(dá)時替換當(dāng)前樣本（隨機選擇）粘性抽樣（Sticky Sampling）有損計數(shù)（Lossy Cou

48、nting）1121/概率刪除1/1/1/1/min(2,W)1/min(3,W)1/min(4,W)n+1n+WW偏倚抽樣分類計數(shù)抽樣（Counting Sampling）設(shè)：樣本集 S 的大小為 s入選：樣本量超過抽樣集大小 s 時，首先將參數(shù) 提高到 ，先以概率 /，之后以概率 1/ 判斷樣本集中的樣本計數(shù)器是否減 1去除：如果樣本計數(shù)器取值減為 0，則刪除樣本有效獲得數(shù)據(jù)集中的熱門元素加權(quán)抽樣（Weighted Sampling）帶權(quán)值的偏倚抽樣將使用率高的小數(shù)據(jù)集賦予更大的權(quán)重，以體現(xiàn)數(shù)據(jù)集的實際分布113/1/普遍命中隨機命中誰被減為0的概率大？60%30%10%混合抽樣分類國會抽

49、樣（Congressional Sampling）將數(shù)據(jù)集進(jìn)行分組，不同分組內(nèi)進(jìn)行獨立的水庫抽樣，不同組之間使用加權(quán)抽樣大組抽樣率比小組高兼顧組內(nèi)的公平性和組間的影響力分層抽樣（Stratified Sampling）利用數(shù)據(jù)分布的歷史經(jīng)驗對數(shù)據(jù)進(jìn)行分層重要的層被設(shè)置為大組，抽取更多的采樣點正確體現(xiàn)數(shù)據(jù)的重要特征11460%30%10%組內(nèi)均勻抽樣高頻組中頻組低頻組組間加權(quán)抽樣伯努利抽樣均勻抽樣115伯努利抽樣（Bernoulli Sampling）均勻抽樣要求：數(shù)據(jù)的抽樣分布與原始分布一致方法：對每個到達(dá)的數(shù)據(jù)按照相同的概率進(jìn)行判斷“去”或“留”116pppp1234567891011121

50、3141516171819202122例如：一個伯努利序列（0-1分布）N 1234567891011S pppppppppppppppppp原始序列 N 的均值 0.5采樣序列 S 的均值 0.545用0.5采樣率能獲得與原始序列相同分布的子序列嗎？伯努利抽樣（Bernoulli Sampling）分析n 為隨機變量個數(shù)，H(n)為 n 次處理出現(xiàn)成功的次數(shù)（真值）TRUE的概率 p，F(xiàn)ALSE的概率 q =1-p （ pn ：預(yù)測值）在 n 次處理過程中，成功次數(shù)不超過 k 次的概率為：當(dāng) k=(p-)n 時Hoeffding不等式當(dāng) k=(p+)n 時Hoeffding不等式合并設(shè) 取值

51、 誤差 的概率邊界117n22 0.37483590.995867865 0.25341930.999526680 0.23404130.99968751150.20312630.9998488n2600.14624380.99997043200.1342610.99998054600.11545020.999990565050.03673941伯努利抽樣該怎樣設(shè)置抽樣率？復(fù)習(xí)一下置信度與置信區(qū)間無法預(yù)計準(zhǔn)確值只能提供一個估計如果有70%樣本落在實際取值中心 正負(fù)偏差 到+ 之間置信度：70%置信區(qū)間： （均值標(biāo)準(zhǔn)差）目標(biāo)：伯努利抽樣的抽樣結(jié)果與原序列具有相同分布的置信度滿足要求11870%基

52、于Hoeffding不等式的采樣率計算設(shè) X 均值（均值 ） 預(yù)期的下界Xi 屬于 ai, bi誤差為 t （標(biāo)準(zhǔn)差 ）對于伯努利分布 Xi 屬于 1, 0均值超出誤差的概率下界為 （1-置信度）為避免均值超出誤差采樣 n 的取值例如輸入序列符合伯努利分布（0-1分布）如果希望t 0.1 0.1119則= 65tn0.10.050.010.165801150.052603204600.016505801011505伯努利抽樣該怎樣設(shè)置抽樣率？120例如：一個伯努利序列（0-1分布）tn0.10.050.010.165801150.052603204600.016505801011505如果希望

53、t 0.05 0.05n 320注意：這里說的是什么問題？必須采樣到320才行？12345678910111213141516171819202122N 1234567891011S 窗口內(nèi)的實際數(shù)據(jù)量要不小于320伯努利抽樣算法121(0,1 隨機數(shù)落選概率向下取整() ：步長=0：選當(dāng)前元素0：跳過元素m=m+1 指示下一個入選點的位置注意：也是入選概率伯努利抽樣算法效果取值0.10.20.30.40.50.60.70.80.90.121.85 10.32 6.46 4.51 3.32 2.51 1.91 1.43 1.00 0.215.28 7.21 4.51 3.15 2.32 1.7

54、6 1.34 1.00 0.70 0.311.43 5.40 3.38 2.36 1.74 1.31 1.00 0.75 0.52 0.48.70 4.11 2.57 1.79 1.32 1.00 0.76 0.57 0.40 0.56.58 3.11 1.94 1.36 1.00 0.76 0.58 0.43 0.30 0.64.85 2.29 1.43 1.00 0.74 0.56 0.42 0.32 0.22 0.73.39 1.60 1.00 0.70 0.51 0.39 0.30 0.22 0.15 0.82.12 1.00 0.63 0.44 0.32 0.24 0.19 0.14

55、 0.10 0.91.00 0.47 0.30 0.21 0.15 0.11 0.09 0.07 0.05 10.000.000.000.000.000.000.000.000.00比例0.12350.23260.35710.45450.55560.66670.76920.83330.9091122隨機數(shù)取值（均勻分布）入選概率取值m = 0m =m + + 1實際步長伯努利抽樣算法的局限需要預(yù)知數(shù)據(jù)的分布特征無法應(yīng)對概念漂移可以支持滑動窗口，但是只能代表窗口內(nèi)數(shù)據(jù)的采樣結(jié)果，并不是整個流數(shù)據(jù)的無偏估計無法預(yù)計流數(shù)據(jù)大小，因此也無法預(yù)計對整個流數(shù)據(jù)的采樣率1231234567891011121

56、3141516171819202122N 1234567S 45678910S 水庫抽樣均勻抽樣124水庫抽樣（Reservoir Sampling）均勻抽樣要求：數(shù)據(jù)的抽樣分布與原始分布一致12512345678910111213141516171819202122N S S 1234567891011121323467910111215161922目標(biāo)：在抽樣完成后，獲得大小為 S 的無偏樣本水庫抽樣（Reservoir Sampling）均勻抽樣目標(biāo)：在抽樣完成后，S 中的每一個元素都是按照 S/N 的概率抽取問題：由于流數(shù)據(jù)的特點，無法預(yù)知 N 的大小12612345678910111

57、213141516171819202122N S 24568911121316192012122以多大的概率入池？以多大的概率將池中的哪個元素刪除？水庫抽樣（Reservoir Sampling）算法思路第1s個元素，按照概率 1 入池后繼第 n 個元素，按照 s/n 概率入池池中元素，按照 1/s 概率刪除12712345678910111213141516171819202122N S 24568911121316192012122s/n1/s1/1313/21s/n13/22概率刪除概率入池水庫抽樣證明128s/N水庫抽樣算法129初始抵達(dá)元素全部入池kU ：0k的隨機數(shù)以 1/k 的概

58、率，用入池的數(shù)據(jù)元素替換掉蓄水池中的原有元素抵達(dá)元素是下一跳元素Data Stream Management：Processing High-Speed Data Streams p21水庫抽樣算法130找到最小的，使其概率恰巧小于U就是必須得入池的步數(shù)s/(n+1) 入池概率1-s/(n+1) 不入池概率(1-s/(n+1) 個都不入池概率使用最優(yōu)化方法避免計算超范圍 * A.M. Law, Simulation Modeling and Analysis, 4th edn. (McGraw-Hill, New York, 2007)簡明抽樣均勻抽樣131簡明抽樣（Concise Sampl

59、ing）均勻抽樣要求：數(shù)據(jù)的抽樣分布與原始分布一致13212345678910111213141516171819202122N S 12345678910111213如果流數(shù)據(jù)中存在大量的重復(fù)元素，水庫抽樣存在的問題：樣本集中需要存儲大量重復(fù)樣本，空間利用率低0, 5簡明抽樣（Concise Sampling）簡明抽樣（精確抽樣）設(shè)：樣本集 S 的大小為 s閾值參數(shù) （初始化取值1）入選：樣本量小于抽樣集大小 s ，以概率 1/ 入選（計數(shù)器+1）樣本量大于抽樣集大小 s ，以概率 1/ 入選（ ）去除：樣本量大于抽樣集大小 s ，以概率 / 選擇樣本集中的樣本，將計數(shù)器減 1（ )直到某一

60、樣本計數(shù)器取值減為 0，刪除樣本特點：隨數(shù)據(jù)流推進(jìn)，抽樣概率逐漸降低適合重復(fù)數(shù)據(jù)較多的情況133刪除操作過程134S110S221S333S411S57S62S715S881021331072158102133107115892031960137以概率 /=0.91選擇樣本=1=1.1以概率 /=0.91選擇樣本-1-1多次迭代，/=0.91，樣本被選中概率很高普遍都減了幾次低頻率的樣本被首先減到0簡明抽樣設(shè)計特點面向具有重復(fù)項的流以概率 / 刪除樣本集元素高頻度的元素更大概率保留低頻度的元素更大概率刪除以概率 1/ 選擇新元素出現(xiàn)新元素的時候，抽樣率降低，抽到低頻新元素的概率也低了低抽樣率對