Mathematical Approaches and Algorithms for Data Stream Analysis by Arthur Tabatchnic

Data streams can be challenging to analyze on the fly. Hardware constraints, large volumes of data, and rapid changes in patterns can all lead to difficult problems. In this talk, I will provide an overview of the different types of analyses that can be performed on data streams and the theory behind some popular algorithms. We will look at three of the most useful groups of tasks: classification, change diagnosis, and distributed data mining.

Arthur is a full-stack developer at Visma Labs, working on a large payroll system

1. Mathematical Approaches and Algorithms for Data Stream Analysis

2. Topics C lassification Change diagnosis Distributed data mining

3. Classification

4. Problems High speed Unbounded requirements Drift Accuracy vs Efficiency Distributed processing

5. Data-based techniques Sampling Load shedding Aggregation Sketching

6. Classification Algorithms

7. Very Fast Decision Trees Pros Very Fast Memory usage* Cons Quite drifty

8. CluStream/On Demand Classification Pros All of them? Distribute friendly Cons None of them?

9. CluStream/On Demand Classification Continued work DenStream ClusCTA

10. ANNCAD (Adaptive Nearest Neighbor Classification Algorithm for Data Streams) Pros Good with slow drift Cons Bad for real-time Hungry

11. Ensemble Based Classification (Wang) Pros Good with drift Cons Bad for real-time Hungry

12. 2. Change diagnosis

13. Velocity density

14. Goals Find significant changes Dissolution Coagulation Shift Keep the model up-to-date

15. Spatial velocity

16. 3. Distributed data mining

17. Problems Many independent sites of observation Data stream per site Locally non-obvious variable relationships to other sites Performance

18. Bayesian Network Learning

19. Steps Learn local BNs Identify key observations Combine observations and learn a non-local BN Communicate updated probabilities back to local sites Obtain a collective BN

20. BNs Pros Missing data Transparent Cause & effect Causal intervention Resource-friendly Pretty easy Cons Assumptions Assumptions Assumptions

21. Q&A