Big Data Stream Mining Tutorial

The challenge of deriving insights from big data has been recognized as one of the most exciting and key opportunities for both academia and industry. Advanced analysis of big data streams is bound to become a key area of data mining research as the number of applications requiring such processing increases. Dealing with the evolution over time of such data streams, i.e., with concepts that drift or change completely, is one of the core issues in stream mining. This tutorial is a gentle introduction to mining big data streams. The first part introduces data stream learners for classification, regression, clustering, and frequent pattern mining. The second part discusses data stream mining on distributed engines such as Storm, S4, and Samza.

Transcript

1. Big Data Stream Mining Tutorial Gianmarco De Francisci Morales, Joao Gama, Albert Bifet, Wei Fan! ! IEEE BigData 2014
2. Organizers (1/2) 
 Gianmarco 
 De Francisci Morales 
 
 
 ! 
 
 is a Research Scientist at Yahoo Labs Barcelona. His research focuses on large scale data mining and big data, with a particular emphasis on web mining and Data Intensive Scalable Computing systems. He is an active member of the open source community of the Apache Software Foundation working on the Hadoop ecosystem, and a committer for the Apache Pig project. He is the co-leader of the SAMOA project, an open- source platform for mining big data streams. 
 João Gama is Associate professor at the University of Porto and a senior researcher at LIAAD Inesc Tec. He received his Ph.D. degree in Computer Science from the University of Porto, Portugal. His main interests are machine learning, and data mining, mainly in the context of time-evolving data streams. He authored a recent book in Knowledge Discovery from Data Streams. http://gdfm.me http://www.liaad.up.pt/~jgama 2
3. Organizers (2/2) 
 Albert Bifet ! ! 
 
 
 is a Research Scientist at Huawei. He is the author of a book on Adaptive Stream Mining and Pattern Learning and Mining from Evolving Data Streams. He is one of the leaders of MOA and SAMOA software environments for implementing algorithms and running experiments for online learning from evolving data streams. 
 Wei Fan 
 
 is the associate director of Huawei Noah's Ark Lab. His co-authored paper received ICDM '06 Best Application Paper Award, he led the team that used his Random Decision Tree method to win 2008 ICDM Data Mining Cup Championship. He received 2010 IBM Outstanding Technical Achievement Award for his contribution to IBM Infosphere Streams. Since he joined Huawei in August 2012, he has led his colleagues to develop Huawei Stream. SMART – a streaming platform for online and real-time processing. http://albertbifet.com 3 http://www.weifan.info
4. Outline • Fundamentals of Stream Mining! • Setting • Classification • Concept Drift • Regression • Clustering • Frequent Itemset Mining • Distributed 
 Stream Mining! • Distributed Stream Processing Engines • Classification • Regression • Conclusions 4 https://sites.google.com/site/bigdatastreamminingtutorial
5. Fundamentals of Stream Mining Part I
6. Setting 6
7. Motivation Data is growing
 
 Source: IDC’s Digital Universe Study (EMC), 2011 7
8. Present of Big Data Too big to handle 8
9. – Adam Jacobs, CACM 2009 (paraphrased) “Big Data is data whose characteristics force us to look beyond the tried-and-true methods
 that are prevalent at that time” 9
10. Gather Clean Model Deploy Standard Approach Finite training sets
 Static models 10
11. Importance$of$O •  As$spam$trends$change retrain$the$model$with Pain Points • Need to retrain! • Things change over time! • How often? • Data unused until next update! • Value of data wasted 11
12. Value of Data 12
13. Online Analytics What is happening now? 13
14. Stream Mining • Maintain models online • Incorporate data on the fly • Unbounded training sets • Detect changes and adapts • Dynamic models 14
15. Big Data Streams • Volume + Velocity (+ Variety) • Too large for single commodity server main memory • Too fast for single commodity server CPU • A solution needs to be: • Distributed • Scalable 15
16. Data Sources User clicks Search queries News Emails Tumblr posts Flickr photos
 Finance stocks Credit card transactions Wikipedia edit logs Facebook statuses Twitter updates Name your own… 16
17. Future of Big Data Drinking from a firehose 17
18. Approximation Algorithms • General idea, good for streaming algorithms • Small error ε with high probability 1-δ • True hypothesis H, and learned hypothesis Ĥ • Pr[ |H - Ĥ| < ε|H| ] > 1-δ 18
19. Classification 19
20. Definition Given a set of training examples belonging to nC different classes, a classifier algorithm builds a model that predicts for every unlabeled instance x the class C to which it belongs 20 Examples • Email spam filter • Twitter sentiment analyzer Photo: Stephen Merity http://smerity.com
21. example at a time, it only once (at ed amount of mited amount of predict at any Process • One example at at time,
 used at most once • Limited memory • Limited time • Anytime prediction 21
22. • Based on Bayes’ theorem • Probability of observing feature xi given class C • Prior class probability P(C) • Just counting! Naïve Bayes 22 posterior = likelihood ⇥ prior evidence P ( C | x ) = P ( x | C ) P ( C ) P ( x ) P ( C | x ) / Y xi 2 x P ( xi | C ) P ( C ) C = arg max C P(C | x)
23. Perceptron Attribute 1 Attribute 2 Attribute 3 Attribute 4 Attribute 5 Output h ~ w (~ xi) w 1 w 2 w 3 w 4 w 5 I Data stream: h~ xi, yii I Classical perceptron: h ~ w (~ xi) = ~ wT ~ xi, I Minimize Mean-square error: J(~ w) = 1 2 P (yi h ~ w (~ xi))2 Perceptron • Linear classifier • Data stream: ⟨x ⃗i,yi⟩ • ỹi = hw ⃗(x ⃗i) = σ(w ⃗i T x ⃗i) • σ(x) = 1/(1+e-x) σʹ=σ(x)(1-σ(x)) • Minimize MSE J(w ⃗)=½∑(yi-ỹi)2 • SGD w ⃗i+1 = w ⃗i - η∇J x ⃗i • ∇J = -(yi-ỹi)ỹi(1-ỹi) • w ⃗i+1 = w ⃗i + η(yi-ỹi)ỹi(1-ỹi)x ⃗i 23
24. Perceptron Learning 24 Perceptron PERCEPTRON LEARNING(Stream, ⌘) 1 for each class 2 do PERCEPTRON LEARNING(Stream, class, ⌘) PERCEPTRON LEARNING(Stream, class, ⌘) 1 ⇤ Let w 0 and ~ w be randomly initialized 2 for each example (~ x, y) in Stream 3 do if class = y 4 then = (1 h ~ w (~ x)) · h ~ w (~ x) · (1 h ~ w (~ x)) 5 else = (0 h ~ w (~ x)) · h ~ w (~ x) · (1 h ~ w (~ x)) 6 ~ w = ~ w + ⌘ · · ~ x PERCEPTRON PREDICTION(~ x) 1 return arg maxclass h ~ wclass (~ x)
25. Decision Tree • Each node tests a features • Each branch represents a value • Each leaf assigns a class • Greedy recursive induction • Sort all examples through tree • xi = most discriminative attribute • New node for xi , new branch for each value, leaf assigns majority class • Stop if no error | limit on #instances 25 Road Tested? Mileage? Age? No Yes High ✅ ❌ Low Old Recent ✅ ❌ Car deal?
26. Very Fast Decision Tree • AKA, Hoeffding Tree • A small sample can often be enough to choose a near optimal decision • Collect sufficient statistics from a small set of examples • Estimate the merit of each alternative attribute • Choose the sample size that allows to differentiate between the alternatives 26 Pedro Domingos, Geoff Hulten: “Mining high-speed data streams”. KDD ’00
27. Leaf Expansion • When should we expand a leaf? • Let x1 be the most informative attribute,
 x2 the second most informative one • Is x1 a stable option? • Hoeffding bound • Split if G(x1) - G(x2) > ε = r R2 ln(1/ ) 2n 27
28. HT Induction 28
29. HT Induction 28 Hoeffding Tree or VFDT HT(Stream, ) 1 ⇤ Let HT be a tree with a single leaf(root) 2 ⇤ Init counts nijk at root 3 for each example (x, y) in Stream 4 do HTGROW((x, y), HT, )
30. HT Induction 28 Hoeffding Tree or VFDT HT(Stream, ) 1 ⇤ Let HT be a tree with a single leaf(root) 2 ⇤ Init counts nijk at root 3 for each example (x, y) in Stream 4 do HTGROW((x, y), HT, ) Hoeffding Tree or VFDT HT(Stream, ) 1 ⇤ Let HT be a tree with a single leaf(root) 2 ⇤ Init counts nijk at root 3 for each example (x, y) in Stream 4 do HTGROW((x, y), HT, ) HTGROW((x, y), HT, ) 1 ⇤ Sort (x, y) to leaf l using HT 2 ⇤ Update counts nijk at leaf l 3 if examples seen so far at l are not all of the same class 4 then ⇤ Compute G for each attribute 5 if G(Best Attr.) G(2nd best) > q R2 ln 1/ 2n 6 then ⇤ Split leaf on best attribute 7 for each branch 8 do ⇤ Start new leaf and initiliatize counts
31. Properties • Number of examples to expand node depends only on Hoeffding bound (ε decreases with √n) • Low variance model (stable decisions with statistical support) • Low overfitting (examples processed only once, no need for pruning) • Theoretical guarantees on error rate with high probability • Hoeffding algorithms asymptotically close to batch learner.
 Expected disagreement δ/p (p = probability instance falls into a leaf) • Ties: broken when ε < τ even if ΔG < ε 29
32. Concept Drift 30
33. Definition Given an input sequence ⟨x1,x2,…,xt⟩, output at instant t an alarm signal if there is a distribution change, and a prediction x ̂t+1 minimizing the error |x ̂t+1 − xt+1| 31 Outputs • Alarm indicating change • Estimate of parameter Photo: http://www.logsearch.io
34. orous guarantees of performance (a theorem). We show that these guarantees can be transferred to decision tree learners as follows: if a change is followed by a long enough stable period, the classification error of the learner will tend, and the same rate, to the error rate of VFDT. We test on Section 6 our methods with synthetic datasets, using the SEA concepts, introduced in [22] and a rotating hyperplane as described in [13], and two sets from the UCI repository, Adult and Poker-Hand. We compare our methods among themselves but also with CVFDT, another concept-adapting variant of VFDT proposed by Domingos, Spencer, and Hulten [13]. A one-line conclusion of our ex- periments would be that, because of its self-adapting prop- erty, we can present datasets where our algorithm performs much better than CVFDT and we never do much worse. Some comparison of time and memory usage of our meth- ods and CVFDT is included. - xt Estimator - - Alarm Change Detector - Estimation Memory - 6 6 ? Figure 1: Change Detector and Estimator System justify the election of one of them for our algorithms. Most approaches for predicting and detecting change in streams of data can be discussed as systems consisting of three modules: Application • Change detection on evaluation of model • Training error should decrease with more examples • Change in distribution of training error • Input = stream of real/binary numbers • Trade-off between detecting true changes and avoiding false alarms 32
35. Cumulative Sum • Alarm when mean of input data differs from zero • Memoryless heuristic (no statistical guarantee) • Parameters: threshold h, drift speed v • g0 = 0, gt = max(0, gt-1 + εt - v) • if gt > h then alarm; gt = 0 33
36. Page-Hinckley Test • Similar structure to Cumulative Sum • g0 = 0, gt = gt-1 + (εt - v) • Gt = mint(gt) • if gt - Gt > h then alarm; gt = 0 34
37. Concept Drift Number of examples processed (time) Error rate concept drift p min + s min Drift level Warning level 0 5000 0 0.8 new window Statistical Drift Detection Method (Joao Gama et al. 2004) Statistical Process Control • Monitor error in sliding window • Null hypothesis:
 no change between windows • If error > warning level
 learn in parallel new model
 on the current window • if error > drift level
 substitute new model for old 35 J Gama, P. Medas, G. Castillo, P. Rodrigues: “Learning with Drift Detection”. SBIA '04
38. Concept-adapting VFDT • Model consistent with sliding window on stream • Keep sufficient statistics also at internal nodes • Recheck periodically if splits pass Hoeffding test • If test fails, grow alternate subtree and swap-in
 when accuracy of alternate is better • Processing updates O(1) time, +O(W) memory • Increase counters for incoming instance, 
 decrease counters for instance going out window 36 G. Hulten, L. Spencer, P. Domingos: “Mining Time-Changing Data Streams”. KDD ‘01
39. VFDTc: Adapting to Change • Monitor error rate • When drift is detected • Start learning alternative subtree in parallel • When accuracy of alternative is better • Swap subtree • No need for window of instances 37 J. Gama, R. Fernandes, R. Rocha: “Decision Trees for Mining Data Streams”. IDA (2006)
40. Hoeffding Adaptive Tree • Replace frequency counters by estimators • No need for window of instances • Sufficient statistics kept by estimators separately • Parameter-free change detector + estimator with theoretical guarantees for subtree swap (ADWIN) • Keeps sliding window consistent with 
 “no-change hypothesis” 38 A. Bifet, R. Gavaldà: “Adaptive Parameter-free Learning from Evolving Data Streams” IDA (2009) A. Bifet, R. Gavaldà: “Learning from Time-Changing Data with Adaptive Windowing”. SDM ‘07
41. Regression 39
42. Definition Given a set of training examples with a numeric label, a regression algorithm builds a model that predicts for every unlabeled instance x the value with high accuracy ! y=ƒ(x) 40 Examples • Stock price • Airplane delay Photo: Stephen Merity http://smerity.com
43. Perceptron Attribute 1 Attribute 2 Attribute 3 Attribute 4 Attribute 5 Output h ~ w (~ xi) w 1 w 2 w 3 w 4 w 5 I Data stream: h~ xi, yii I Classical perceptron: h ~ w (~ xi) = ~ wT ~ xi, I Minimize Mean-square error: J(~ w) = 1 2 P (yi h ~ w (~ xi))2 Perceptron • Linear regressor • Data stream: ⟨x ⃗i,yi⟩ • ỹi = hw ⃗(x ⃗i) = w ⃗T x ⃗i • Minimize MSE J(w ⃗)=½∑(yi-ỹi)2 • SGD w ⃗' = w ⃗ - η∇J x ⃗i • ∇J = -(yi-ỹi) • w ⃗' = w ⃗ + η(yi-ỹi)x ⃗i 41
44. Regression Tree • Same structure as decision tree • Predict = average target value or
 linear model at leaf (vs majority) • Gain = reduction in standard deviation (vs entropy) 42 = qX ( ˜ yi yi)2/(N 1)
45. AMRules Rules Rules
    
       Rules • Problem: very large decision trees have context that is complex and
 hard to understand • Rules: self-contained, modular, easier to interpret, no need to cover universe • keeps sufficient statistics to: • make predictions • expand the rule • detect changes and anomalies 43
46. Ensembles of Adaptive Model Rules from High-Speed AMRules Rule sets Predicting with a rule s
             E.g: x = [4, 1, 1, 2] ˆ f( x ) = X Rl 2S( x i ) ✓l ˆ yl, Adaptive Model Rules • Ruleset: ensemble of rules • Rule prediction: mean, linear model • Ruleset prediction • Weighted avg. of predictions of rules covering instance x • Weights inversely proportional to error • Default rule covers uncovered instances 44 E. Almeida, C. Ferreira, J. Gama. "Adaptive Model Rules from Data Streams." ECML-PKDD ‘13
47. Ensembles of Adaptive Model Rules from High-Speed Data Streams AMRules Rule sets Algorithm 1: Training AMRules Input : S: Stream of examples begin R {}, D 0 foreach ( x , y) 2 S do foreach Rule r 2 S( x ) do if ¬IsAnomaly( x , r) then if PHTest(errorr , ) then Remove the rule from R else Update sufficient statistics Lr ExpandRule(r) if S( x ) = ; then Update LD ExpandRule(D) if D expanded then R R [ D D 0 return (R, LD ) AMRules Induction • Rule creation: default rule expansion • Rule expansion: split on attribute maximizing σ reduction • Hoeffding bound ε • Expand when σ1st/σ2nd < 1 - ε • Evict rule when P-H test error large • Detect and explain local anomalies 45 = r R2 ln(1/ ) 2n
48. Clustering 46
49. Definition Given a set of unlabeled instances, distribute them into homogeneous groups according to some common relations or affinities. 47 Examples • Market segmentation • Social network communities Photo: W. Kandinsky - Several Circles (edited)
50. Approaches • Distance based (CluStream) • Density based (DenStream) • Kernel based, Coreset based, much more… • Most approaches combine online + offline phase • Formally: minimize cost function 
 over a partitioning of the data 48
51. Static Evaluation • Internal (validation) • Sum of squared distance (point to centroid) • Dunn index (on distance d)
 D = min(inter-cluster d) / max(intra-cluster d) • External (ground truth) • Rand = #agreements / #choices = 2(TP+TN)/(N(N-1)) • Purity = #majority class per cluster / N 49
52. Streaming Evaluation • Clusters may: appear, fade, move, merge • Missed points (unassigned) • Misplaced points (assigned to different cluster) • Noise • Cluster Mapping Measure CMM • External (ground truth) • Normalized sum of penalties of these errors 50 H. Kremer, P. Kranen, T. Jansen, T. Seidl, A. Bifet, G. Holmes, B. Pfahringer:
 “An effective evaluation measure for clustering on evolving data streams”. KDD ’11
53. Snapshot 25,0 Micro-Clusters • AKA, Cluster Features CF
 Statistical summary structure • Maintained in online phase,
 input for offline phase • Data stream ⟨x ⃗i⟩, d dimensions • Cluster feature vector
 N: number of points
 LSj : sum of values (for dim. j)
 SSj : sum of squared values (for dim. j) • Easy to update, easy to merge • # of micro-clusters ≫ # of clusters 51 Tian Zhang, Raghu Ramakrishnan, Miron Livny: “BIRCH: An Efficient Data Clustering Method for Very Large Databases”. SIGMOD ’96
54. CluStream • Timestamped data stream ⟨ti, x ⃗i⟩, represented in d+1 dimensions • Seed algorithm with q micro-clusters (k-means on initial data) • Online phase. For each new point, either: • Update one micro-cluster (point within maximum boundary) • Create a new micro-cluster (delete/merge other micro-clusters) • Offline phase. Determine k macroclusters on demand: • K-means on micro-clusters (weighted pseudo-points) • Time-horizon queries via pyramidal snapshot mechanism 52 Charu C. Aggarwal, Jiawei Han, Jianyong Wang, Philip S. Yu: “A Framework for Clustering Evolving Data Streams”. VLDB ‘03
55. DBSCAN • ε-n(p) = set of points at distance ≤ ε • Core object q = ε-n(q) has weight ≥ μ • p is directly density-reachable from q • p ∈ ε-n(q) ∧ q is a core object • pn is density-reachable from p1 • chain of points p1,…,pn such that pi +1 is directly d-r from pi • Cluster = set of points that are mutually density-connected 53 Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu: “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”. KDD ‘96
56. DenStream • Based on DBSCAN • Core-micro-cluster: CMC(w,c,r) 
 weight w > μ, center c, radius r < ε • Potential/outlier micro-clusters • Online: merge point into p (or o)
 micro-cluster if new radius r'< ε • Promote outlier to potential if w > βμ • Else create new o-micro-cluster • Offline: DBSCAN 54 Feng Cao, Martin Ester, Weining Qian, Aoying Zhou: “Density-Based Clustering over an Evolving Data Stream with Noise”. SDM ‘06 Figure 1: Representation by of stream, i.e., the number of poin time. In static environment, the cl
57. Frequent Itemset Mining 55
58. Definition Given a collection of sets of items, find all the subsets that occur frequently, i.e., more than a minimum support of times 56 Examples • Market basket mining • Item recommendation
59. Fundamentals • Dataset D, set of items t ∈ D, constant s (minimum support) • Support(t) = number of sets
 in D that contain t • Itemset t is frequent if support(t) ≥ s • Frequent Itemset problem: • Given D and s, find all frequent itemsets 57
60. Example 58 Dataset Example Document Patterns d1 abce d2 cde d3 abce d4 acde d5 abcde d6 bcd Itemset Mining d1 abce d2 cde d3 abce d4 acde d5 abcde d6 bcd Support Frequent d1,d2,d3,d4,d5,d6 c d1,d2,d3,d4,d5 e,ce d1,d3,d4,d5 a,ac,ae,ace d1,d3,d5,d6 b,bc d2,d4,d5,d6 d,cd d1,d3,d5 ab,abc,abe be,bce,abce d2,d4,d5 de,cde minimal support = 3
61. Example 58 Dataset Example Document Patterns d1 abce d2 cde d3 abce d4 acde d5 abcde d6 bcd Itemset Mining d1 abce d2 cde d3 abce d4 acde d5 abcde d6 bcd Support Frequent 6 c 5 e,ce 4 a,ac,ae,ace 4 b,bc 4 d,cd 3 ab,abc,abe be,bce,abce 3 de,cde
62. Variations • A priori property: t ⊆ t' ➝ support(t) ≥ support(t’) • Closed: none of its supersets has the same support • Can generate all freq. itemsets and their support • Maximal: none of its supersets is frequent • Can generate all freq. itemsets (without support) • Maximal ⊆ Closed ⊆ Frequent ⊆ D 59
63. Itemset Streams • Support as fraction of stream length • Exact vs approximate • Incremental, sliding window, adaptive • Frequent, closed, maximal 60
64. Lossy Counting • Keep data structure D with tuples (x, freq(x), error(x)) • Imagine to divide the stream in buckets of size⽷1/ε⽹ • Foreach itemset x in the stream, 
 Bid = current sequential bucket id starting from 1 • if x ∈ D, freq(x)++ • else D ← D ∪ (x, 1, Bid - 1) • Prune D at bucket boundaries: evict x if freq(x) + error(x) ≤ Bid 61 G. S. Manku, R. Motwani: “Approximate frequency counts over data streams”. VLDB '02
65. Moment • Keeps track of boundary below frequent itemsets in a window • Closed Enumeration Tree (CET) (~ prefix tree) • Infrequent gateway nodes (infrequent) • Unpromising gateway nodes (infrequent, dominated) • Intermediate nodes (frequent, dominated) • Closed nodes (frequent) • By adding/removing transactions closed/infreq. do not change 62 Y. Chi , H. Wang, P. Yu , R. Muntz: “Moment: Maintaining Closed Frequent Itemsets over a Stream Sliding Window”. ICDM ‘04
66. FP-Stream • Multiple time granularities • Based on FP-Growth (depth-first search over itemset lattice) • Pattern-tree + Tilted-time window • Time sensitive queries, emphasis on recent history • High time and memory complexity 63 C. Giannella, J. Han, J. Pei, X. Yan, P. S. Yu: “Mining frequent patterns in data streams at multiple time granularities”. NGDM (2003)
67. Distributed 
 Stream Mining Part II
68. Outline • Fundamentals of Stream Mining! • Setting • Classification • Concept Drift • Regression • Clustering • Frequent Itemset Mining • Distributed 
 Stream Mining! • Distributed Stream Processing Engines • Classification • Regression • Conclusions 65
69. Motivation • Datasets already stored on clusters • Don’t want to move everything to single powerful machine • Clusters ubiquitous and cheap (e.g., see TOP500), supercomputers expensive and monolithic • Clusters easily shared, leverage economy of scale • Largest problem solvable by single machine
 constrained by hardware • How fast can you read from disk or network 66
70. Distributed Stream Processing Engines 67
71. A Tale of two Tribes 68 DB DB DB DB DB DB Data App App App Faster Larger Database M. Stonebraker U. Çetintemel: “‘One Size Fits All’: An Idea Whose Time Has Come and Gone”. ICDE ’05
72. A Tale of two Tribes 68 DB DB DB DB DB DB Data App App App Faster Larger Database M. Stonebraker U. Çetintemel: “‘One Size Fits All’: An Idea Whose Time Has Come and Gone”. ICDE ’05
73. A Tale of two Tribes 68 DB DB DB DB DB DB Data App App App Faster Larger Database M. Stonebraker U. Çetintemel: “‘One Size Fits All’: An Idea Whose Time Has Come and Gone”. ICDE ’05
74. A Tale of two Tribes 68 DB DB DB DB DB DB Data App App App Faster Larger Database M. Stonebraker U. Çetintemel: “‘One Size Fits All’: An Idea Whose Time Has Come and Gone”. ICDE ’05
75. SPE Evolution —2003 —2004 —2005 —2006 —2008 —2010 —2011 —2013 Aurora STREAM Borealis SPC SPADE Storm S4 1st generation 2nd generation 3rd generation Abadi et al., “Aurora: a new model and architecture for data stream management,” VLDB Journal, 2003 Arasu et al., “STREAM: The Stanford Data Stream Management System,” Stanford InfoLab, 2004. Abadi et al., “The Design of the Borealis Stream Processing Engine,” in CIDR ’05 Amini et al., “SPC: A Distributed, Scalable Platform for Data Mining,” in DMSSP ’06 Gedik et al., “SPADE: The System S Declarative Stream Processing Engine,” in SIGMOD ’08 Neumeyer et al., “S4: Distributed Stream Computing Platform,” in ICDMW ’10 http://storm.apache.org Samza http://samza.incubator.apache.org 69
76. Actors Model 70 Live Streams Stream 1 Stream 2 Stream 3 PE PE PE PE PE External Persister Output 1 Output 2 Event routing
77. S4 Example 71 status.text:"Introducing #S4: a distributed #stream processing system" PE1 PE2 PE3 PE4 RawStatus null text="Int..." EV KEY VAL Topic topic="S4" count=1 EV KEY VAL Topic topic="stream" count=1 EV KEY VAL Topic reportKey="1" topic="S4", count=4 EV KEY VAL TopicExtractorPE (PE1) extracts hashtags from status.text TopicCountAndReportPE (PE2-3) keeps counts for each topic across all tweets. Regularly emits report event if topic count is above a configured threshold. TopicNTopicPE (PE4) keeps counts for top topics and outputs top-N topics to external persister
78. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing) • Shuffle Grouping
 (round-robin) • All Grouping
 (broadcast) 72
79. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing)! • Shuffle Grouping
 (round-robin) • All Grouping
 (broadcast) 73
80. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing)! • Shuffle Grouping
 (round-robin) • All Grouping
 (broadcast) 73
81. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing)! • Shuffle Grouping
 (round-robin) • All Grouping
 (broadcast) 73
82. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing) • Shuffle Grouping
 (round-robin)! • All Grouping
 (broadcast) 74
83. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing) • Shuffle Grouping
 (round-robin)! • All Grouping
 (broadcast) 74
84. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing) • Shuffle Grouping
 (round-robin)! • All Grouping
 (broadcast) 74
85. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing) • Shuffle Grouping
 (round-robin) • All Grouping
 (broadcast) 75
86. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing) • Shuffle Grouping
 (round-robin) • All Grouping
 (broadcast) 75
87. PE PE PEI PEI PEI PEI Groupings • Key Grouping 
 (hashing) • Shuffle Grouping
 (round-robin) • All Grouping
 (broadcast) 75
88. Classification 76
89. Hadoop AllReduce • MPI AllReduce on MapReduce • Parallel SGD + L-BFGS • Aggregate + Redistribute • Each node computes partial gradient • Aggregate (sum) complete gradient • Each node gets updated model • Hadoop for data locality (map-only job) 77 A. Agarwal, O. Chapelle, M. Dudík, J. Langford: “A Reliable Effective Terascale Linear Learning System”. JMLR (2014)
90. 7 5 1 4 9 3 8 7 13 5 3 4 15 37 37 37 37 37 37 re 1: AllReduce operation. Initially, each node holds its own value. Values are passed up and summed, until the global sum is obtained in the root node (reduce phase). The global en passed back down to all other nodes (broadcast phase). At the end, each node contains al sum. Hadoop-compatible AllReduce AllReduce Reduction Tree Upward = Reduce Downward = Broadcast (All) 78
91. Parallel Decision Trees 79
92. Parallel Decision Trees • Which kind of parallelism? 79
93. Parallel Decision Trees • Which kind of parallelism? • Task 79
94. Parallel Decision Trees • Which kind of parallelism? • Task • Data 79 Data Attributes Instances
95. Parallel Decision Trees • Which kind of parallelism? • Task • Data • Horizontal 79 Data Attributes Instances
96. Parallel Decision Trees • Which kind of parallelism? • Task • Data • Horizontal • Vertical 79 Data Attributes Instances
97. Parallel Decision Trees • Which kind of parallelism? • Task • Data • Horizontal • Vertical 79 Data Attributes Instances Class Instance Attributes
98. Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
99. Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
100. Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
101. Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
102. Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
103. Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
104. Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
105. Single attribute tracked in multiple nodes Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
106. Aggregation to compute splits Stats Stats Stats Stream Histograms Model Instances Model Updates Horizontal Partitioning 80 Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010)
107. Hoeffding Tree Profiling 81 Other 6% Split 24% Learn 70% Training time for
 100 nominal + 100 numeric attributes
108. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
109. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
110. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
111. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
112. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
113. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
114. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
115. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
116. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
117. Stats Stats Stats Stream Model Attributes Splits Vertical Partitioning 82 Single attribute tracked in single node A. Murdopo, A. Bifet, G. De Francisci Morales, N. Kourtellis: “VHT: Vertical Hoeffding Tree”. Working paper (2014)
118. Control Split Result Source (n) Model (n) Stats (n) Evaluator (1) Instance Stream Shuffle Grouping Key Grouping All Grouping Vertical Hoeffding Tree 83
119. Advantages of 
 Vertical Parallelism • High number of attributes => high level of parallelism
 (e.g., documents) • vs. task parallelism • Parallelism observed immediately • vs. horizontal parallelism • Reduced memory usage (no model replication) • Parallelized split computation 84
120. Regression 85
121. Model Aggregator Learner 1 Learner 2 Learner p Predictions Instances New Rules Rule Updates VAMR 86 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14
122. Model Aggregator Learner 1 Learner 2 Learner p Predictions Instances New Rules Rule Updates VAMR • Vertical AMRules 86 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14
123. Model Aggregator Learner 1 Learner 2 Learner p Predictions Instances New Rules Rule Updates VAMR • Vertical AMRules • Model: rule body + head • Target mean updated continuously
 with covered instances for predictions • Default rule (creates new rules) 86 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14
124. Model Aggregator Learner 1 Learner 2 Learner p Predictions Instances New Rules Rule Updates VAMR • Vertical AMRules • Model: rule body + head • Target mean updated continuously
 with covered instances for predictions • Default rule (creates new rules) • Learner: statistics • Vertical: Learner tracks statistics of independent subset of rules • One rule tracked by only one Learner • Model -> Learner: key grouping on rule ID 86 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14
125. HAMR 87 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14
126. HAMR • VAMR single model is bottleneck 87 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14
127. HAMR • VAMR single model is bottleneck • Hybrid AMRules
 (Vertical + Horizontal) 87 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14 Learners Model Aggregator 1 Model Aggregator 2 Model Aggregator r Predictions Instances New Rules Rule Updates Learners Learners
128. HAMR • VAMR single model is bottleneck • Hybrid AMRules
 (Vertical + Horizontal) • Shuffle among multiple
 Models for parallelism 87 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14 Learners Model Aggregator 1 Model Aggregator 2 Model Aggregator r Predictions Instances New Rules Rule Updates Learners Learners
129. HAMR • VAMR single model is bottleneck • Hybrid AMRules
 (Vertical + Horizontal) • Shuffle among multiple
 Models for parallelism • Problem: distributed default rule decreases performance 87 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14 Learners Model Aggregator 1 Model Aggregator 2 Model Aggregator r Predictions Instances New Rules Rule Updates Learners Learners
130. HAMR • VAMR single model is bottleneck • Hybrid AMRules
 (Vertical + Horizontal) • Shuffle among multiple
 Models for parallelism • Problem: distributed default rule decreases performance • Separate dedicate Learner 
 for default rule 87 A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ‘14 Predictions Instances New Rules Rule Updates Learners Learners Learners Model Aggregator 2 Model Aggregator 2 Model Aggregators Default Rule Learner New Rules
131. Conclusions 88
132. Summary • Streaming useful for finding approximate solutions with reasonable amount of time & limited resources • Algorithms for classification, regression, clustering, frequent itemset mining • Single machine for small streams • Distributed systems for very large streams 89
133. SAMOA SAMOA 90 http://samoa-project.net Data Mining Distributed Batch Hadoop Mahout Stream Storm, S4, Samza SAMOA Non Distributed Batch R, WEKA,… Stream MOA G. De Francisci Morales, A. Bifet: “SAMOA: Scalable Advanced Massive Online Analysis”. JMLR (2014)
134. Streaming Vision 91 Distributed
135. Streaming Vision 91 Distributed Big Data Stream Mining
136. Streaming Vision 91 Distributed Big Data Stream Mining
137. Open Challenges • Structured output • Multi-target learning • Millions of classes • Representation learning • Ease of use 92
138. References 93
139. • IDC’s Digital Universe Study. EMC (2011) • P. Domingos, G. Hulten: “Mining high-speed data streams”. KDD ’00 • J Gama, P. Medas, G. Castillo, P. Rodrigues: “Learning with drift detection”. SBIA’04 • G. Hulten, L. Spencer, P. Domingos: “Mining Time-Changing Data Streams”. KDD ‘01 • J. Gama, R. Fernandes, R. Rocha: “Decision trees for mining data streams”. IDA (2006) • A. Bifet, R. Gavaldà: “Adaptive Parameter-free Learning from Evolving Data Streams”. IDA (2009) • A. Bifet, R. Gavaldà: “Learning from Time-Changing Data with Adaptive Windowing”. SDM ’07 • E. Almeida, C. Ferreira, J. Gama. "Adaptive Model Rules from Data Streams”. ECML-PKDD ‘13 • H. Kremer, P. Kranen, T. Jansen, T. Seidl, A. Bifet, G. Holmes, B. Pfahringer: “An effective evaluation measure for clustering on evolving data streams”. KDD ’11 • T. Zhang, R. Ramakrishnan, M. Livny: “BIRCH: An Efficient Data Clustering Method for Very Large Databases”. SIGMOD ’96 • C. C. Aggarwal, J. Han, J. Wang, P. S. Yu: “A Framework for Clustering Evolving Data Streams”. VLDB ‘03 • M. Ester, H. Kriegel, J. Sander, X. Xu: “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”. KDD ‘96 94
140. • F. Cao, M. Ester, W. Qian, A. Zhou: “Density-Based Clustering over an Evolving Data Stream with Noise”. SDM ‘06 • G. S. Manku, R. Motwani: “Approximate frequency counts over data streams”. VLDB '02 • Y. Chi , H. Wang, P. Yu , R. Muntz: “Moment: Maintaining Closed Frequent Itemsets over a Stream Sliding Window”. ICDM ’04 • C. Giannella, J. Han, J. Pei, X. Yan, P. S. Yu: “Mining frequent patterns in data streams at multiple time granularities”. NGDM (2003) • M. Stonebraker U. Çetintemel: “‘One Size Fits All’: An Idea Whose Time Has Come and Gone”. ICDE ’05 • A. Agarwal, O. Chapelle, M. Dudík, J. Langford: “A Reliable Effective Terascale Linear Learning System”. JMLR (2014) • Y. Ben-Haim, E. Tom-Tov: “A Streaming Parallel Decision Tree Algorithm”. JMLR (2010) • A. T. Vu, G. De Francisci Morales, J. Gama, A. Bifet: “Distributed Adaptive Model Rules for Mining Big Data Streams”. BigData ’14 • G. De Francisci Morales, A. Bifet: “SAMOA: Scalable Advanced Massive Online Analysis”. JMLR (2014) • J. Gama: “Knowledge Discovery from Data Streams”. Chapman and Hall (2010) • J. Gama: “Data Stream Mining: the Bounded Rationality”. Informatica 37(1): 21-25 (2013) 95
141. Contacts • https://sites.google.com/site/bigdatastreamminingtutorial • Gianmarco De Francisci Morales
 gdfm@yahoo-inc.com @gdfm7 • João Gama
 jgama@fep.up.pt @JoaoMPGama • Albert Bifet
 abifet@waikato.ac.nz @abifet • Wei Fan
 david.fanwei@huawei.com @fanwei 96