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

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

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

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

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

5、時、動態(tài)的信息控制與信息服務強調與物理世界交互的感知與反饋控制過程，通過計算進程和物理進程相互影響實現(xiàn)信息空間與物理空間的密切互動信息采集傳輸匯集 分析 處理存儲應用感知組網(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實際應用場景17從小規(guī)模數(shù)據(jù)到大規(guī)模數(shù)據(jù)應用平臺服務G-T級T-P級大規(guī)?；ヂ?lián)網(wǎng)/物聯(lián)網(wǎng)服務18從小規(guī)模數(shù)據(jù)到大規(guī)模數(shù)據(jù)規(guī)模大 用戶多 總量大 分布廣變化快種類雜數(shù)據(jù)源多樣數(shù)據(jù)類型多樣數(shù)據(jù)結構多樣價值密

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

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

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

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

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

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

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

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

14、大數(shù)據(jù)算力1從物聯(lián)網(wǎng)到信息物理系統(tǒng)2從抽樣數(shù)據(jù)到大數(shù)據(jù)3從大數(shù)據(jù)到人工智能4大數(shù)據(jù)與流數(shù)據(jù)從一個例子開始5實際應用場景一個例子一些實際問題判斷特定IP是不是第一次訪問網(wǎng)站？訪問了多少次？數(shù)據(jù)庫高速緩存網(wǎng)站高速緩存Web服務MySQL數(shù)據(jù)庫Redis緩存瀏覽器查詢緩存查詢結果數(shù)據(jù)庫查詢變長數(shù)據(jù)內容哈希哈希（Hash）把任意長度輸入通過Hash算法變換成固定長度輸出代表算法：MD5, SHA128, SHA256（32/128/256Bytes）一般是壓縮映射，不可逆映射挑戰(zhàn)如果實際數(shù)據(jù)需求遠遠超過內存大?。咳纾?00,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ù)計算元素對應的地址Entry，并在對應的區(qū)域存儲該元素實際查找通過先hash計算Entry，再匹配元素是否相同（哈希值匹配）優(yōu)勢解決沖突查找復雜

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

17、P12345678mHashData1Data2m-1m-2m-3m-4m-5m-6m-7BITMAP00010000000000000000100000000000如果沖突怎么辦？Data30000100000000000布隆過濾器設計思想用一系列隨機映射函數(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相應的位置取值是否為1400110111001110110BITMAPH1H2H3HkData3Data40110布隆過濾器的問題存在誤報哈希函數(shù)存在沖突BITMAP中的每一位是k個哈希函數(shù)映射結果的疊加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ù)抵達數(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實際應用場景行為學習：基于用戶通信記錄（含：主被叫、通話時間、通話頻度、通話行為、特殊號碼類型等）進行無監(jiān)督和有監(jiān)督的學習，建立行為特征模式分類器訓練：基于行為特征模式，訓練電信詐騙鑒別分類器電信詐騙識別：通話記錄進入分類器，識別潛在的電信詐騙風險號碼45結合通信

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

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

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

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

24、：不可預測無序性：無前后邏輯關聯(lián)58數(shù)據(jù)流t0t1t2數(shù)據(jù)流t3t4t5流數(shù)據(jù)處理緩存t1t2帶來的要求：緩存容量要求緩存時效要求數(shù)據(jù)精度與緩存容量需要平衡流數(shù)據(jù)的特點（一）數(shù)據(jù)的持續(xù)抵達實時性：限定時間完成易失性：不可追溯突發(fā)性：不可預測無序性：無前后邏輯關聯(lián)59流數(shù)據(jù)流數(shù)據(jù)處理t0t1t2t7t8t9帶來的要求：數(shù)據(jù)到達量變化無法預期最大量數(shù)據(jù)重要度與處理性能需要平衡流數(shù)據(jù)的特點（一）數(shù)據(jù)的持續(xù)抵達實時性：限定時間完成易失性：不可追溯突發(fā)性：不可預測無序性：無前后邏輯關聯(lián)60流數(shù)據(jù)t0t1t2t7t8t9流數(shù)據(jù)處理帶來的要求：不一定有序抵達不一定存在關聯(lián)不能依賴數(shù)據(jù)的內在長期關聯(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個標簽成本高壓力大流數(shù)據(jù)的特點（二）數(shù)據(jù)的高基數(shù)（High-Cardinality）高基數(shù)“長尾” 62流數(shù)據(jù)處理緩存IP地址計數(shù)IP110IP25IPm100001IPm+199876IPn-1105IPn172數(shù)量類別帶來的要求：無法預期誰是“長尾”判斷難度大基數(shù)（Cardinality）：數(shù)據(jù)中不同類別的數(shù)量流數(shù)據(jù)的特點（三）數(shù)據(jù)的統(tǒng)計特征變化63概念漂移（Con

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

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

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

29、型 核心思想：先存儲，再分析71全量入庫離線分析特點：數(shù)據(jù)處理算法可以按照任意方式對全量數(shù)據(jù)進行任意次數(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、恢復特征流數(shù)據(jù)處理流式處理模型（Stream Data Processing Model） 流計算（Stream Computing） 核心思想：數(shù)據(jù)在線持續(xù)處理74特點：數(shù)據(jù)處理算法僅能對當前緩存內的數(shù)據(jù)進行遍歷，僅能通過概要數(shù)據(jù)結構存儲數(shù)據(jù)特征的歷史記憶在線分析數(shù)據(jù)入庫概要存儲與查詢tntn+1流數(shù)據(jù)處理概要數(shù)據(jù)結構（Synopsis Data Structure） 在有限空間條件下存儲的對流數(shù)據(jù)的一種特征描述精度可接受實時響應75例如：查詢訪問網(wǎng)站的獨立IP地址共訪問了多少次通過歷史數(shù)據(jù)挖掘：準確，但需要10分鐘返回結果通過計數(shù)型布隆過濾器處理：大致準確，但只需0.1秒返回結果概要數(shù)據(jù)：

31、流數(shù)據(jù)處理算法的算法緩存和結果記錄流處理與批處理的對比流處理批處理輸入方式數(shù)據(jù)流數(shù)據(jù)塊數(shù)據(jù)量無界數(shù)據(jù)有界數(shù)據(jù)存儲內存緩存，非持久化持久化存儲硬件設施有限內存更多的CPU與內存處理方式一次遍歷多次遍歷時間需求秒級，甚至毫秒級長應用場景實時類需求應用廣泛場景76流式處理與窗口模型77流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類時間無關型過濾型內聯(lián)型78數(shù)據(jù)篩選，對數(shù)據(jù)本身的順序、抵達時間偏差等不敏感對多源數(shù)據(jù)進行關聯(lián)，對數(shù)據(jù)本身的順序、抵達時間偏差等不敏感，但需要緩沖數(shù)據(jù)以等待關聯(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）通過衰減因子使得窗口內不同時間到達的數(shù)據(jù)對整體的影響不同注意：數(shù)據(jù)可不一定是均勻速率抵達的流數(shù)據(jù)處理模型流數(shù)據(jù)處理模型分類窗口型固定窗口滑動窗口會話窗口多尺度窗口81內容滑動窗口（ Content based Sliding Window ）按照固定的數(shù)據(jù)量 W 劃分窗口隨著數(shù)據(jù)到達，超過窗

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

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

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

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

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

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

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

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

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

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

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

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

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

46、慮空間網(wǎng)格劃分，基于密度不同設置不同的概率進行抽樣混合抽樣均勻抽樣與偏倚抽樣聯(lián)合110均勻抽樣分類伯努利抽樣（Bernoulli Sampling）設：數(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ù)集分布概率需要有預知水庫抽樣（Reservoir Sampling）設：樣本集 S 的大小為 s入選：第 n 個抽樣樣本的入選概率為 s/n去除：如果當前樣本集合中

47、的樣本量超過抽樣集大小 s，從樣本集合 S 中隨機去除一個樣本優(yōu)點：各元素入選抽樣數(shù)據(jù)集合的概率相同（隨機均勻抽樣）111pppps/ns/ns/ns/n隨機刪除均勻抽樣分類簡明抽樣（Concise Sampling）擴展水庫抽樣，每個采樣點一個計數(shù)器入選： 1/ 1/ （ ，概率逐漸變小）去除： /優(yōu)點：支持重復數(shù)據(jù)均勻抽樣鏈式抽樣（Chain Sampling）針對滑動窗口設：滑動窗口大小 W 入選：第 n 個抽樣樣本的入選概率 1/min(n,W)替換：從n+1n+W中隨機選擇備選樣本，在抵達時替換當前樣本（隨機選擇）粘性抽樣（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）設：樣本集 S 的大小為 s入選：樣本量超過抽樣集大小 s 時，首先將參數(shù) 提高到 ，先以概率 /，之后以概率 1/ 判斷樣本集中的樣本計數(shù)器是否減 1去除：如果樣本計數(shù)器取值減為 0，則刪除樣本有效獲得數(shù)據(jù)集中的熱門元素加權抽樣（Weighted Sampling）帶權值的偏倚抽樣將使用率高的小數(shù)據(jù)集賦予更大的權重，以體現(xiàn)數(shù)據(jù)集的實際分布113/1/普遍命中隨機命中誰被減為0的概率大？60%30%10%混合抽樣分類國會抽

49、樣（Congressional Sampling）將數(shù)據(jù)集進行分組，不同分組內進行獨立的水庫抽樣，不同組之間使用加權抽樣大組抽樣率比小組高兼顧組內的公平性和組間的影響力分層抽樣（Stratified Sampling）利用數(shù)據(jù)分布的歷史經驗對數(shù)據(jù)進行分層重要的層被設置為大組，抽取更多的采樣點正確體現(xiàn)數(shù)據(jù)的重要特征11460%30%10%組內均勻抽樣高頻組中頻組低頻組組間加權抽樣伯努利抽樣均勻抽樣115伯努利抽樣（Bernoulli Sampling）均勻抽樣要求：數(shù)據(jù)的抽樣分布與原始分布一致方法：對每個到達的數(shù)據(jù)按照相同的概率進行判斷“去”或“留”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 ：預測值）在 n 次處理過程中，成功次數(shù)不超過 k 次的概率為：當 k=(p-)n 時Hoeffding不等式當 k=(p+)n 時Hoeffding不等式合并設 取值

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

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

53、t 0.05 0.05n 320注意：這里說的是什么問題？必須采樣到320才行？12345678910111213141516171819202122N 1234567891011S 窗口內的實際數(shù)據(jù)量要不小于320伯努利抽樣算法121(0,1 隨機數(shù)落選概率向下取整() ：步長=0：選當前元素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實際步長伯努利抽樣算法的局限需要預知數(shù)據(jù)的分布特征無法應對概念漂移可以支持滑動窗口，但是只能代表窗口內數(shù)據(jù)的采樣結果，并不是整個流數(shù)據(jù)的無偏估計無法預計流數(shù)據(jù)大小，因此也無法預計對整個流數(shù)據(jù)的采樣率1231234567891011121

56、3141516171819202122N 1234567S 45678910S 水庫抽樣均勻抽樣124水庫抽樣（Reservoir Sampling）均勻抽樣要求：數(shù)據(jù)的抽樣分布與原始分布一致12512345678910111213141516171819202122N S S 1234567891011121323467910111215161922目標：在抽樣完成后，獲得大小為 S 的無偏樣本水庫抽樣（Reservoir Sampling）均勻抽樣目標：在抽樣完成后，S 中的每一個元素都是按照 S/N 的概率抽取問題：由于流數(shù)據(jù)的特點，無法預知 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初始抵達元素全部入池kU ：0k的隨機數(shù)以 1/k 的概

58、率，用入池的數(shù)據(jù)元素替換掉蓄水池中的原有元素抵達元素是下一跳元素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ù)中存在大量的重復元素，水庫抽樣存在的問題：樣本集中需要存儲大量重復樣本，空間利用率低0, 5簡明抽樣（Concise Sampling）簡明抽樣（精確抽樣）設：樣本集 S 的大小為 s閾值參數(shù) （初始化取值1）入選：樣本量小于抽樣集大小 s ，以概率 1/ 入選（計數(shù)器+1）樣本量大于抽樣集大小 s ，以概率 1/ 入選（ ）去除：樣本量大于抽樣集大小 s ，以概率 / 選擇樣本集中的樣本，將計數(shù)器減 1（ )直到某一

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