Trang 1
Fall 2019 IoT Data Analytics Vassilis Christophides christop@csd.uoc.gr http://www.csd.uoc.gr/~hy562 University of Crete, Fall 2019 Fall 2019 The Internet of Things (IoT) Networks of physical objects (aka Things) that are uniquely identifiable in the Internet with embedded sensing and actuating along with item identification programmability capabilities sensors ( nanotechnology ( Information about Things can be • collected and the state of Things can be changed from anywhere, anytime, by anything ! http://www.internet-of-things-research.eu 1 •1
Trang 2
A World of Things Fall 2019 Activity-Based Notification Information-Based SCiO FuelBand BodyTrack FitBit Nest Event-based SmartThings WeMo IFTTT-based Wink User-Activated Automation Pre-Compiled 3 Anything, Everything can be Measured!Fall 2019 https://www.postscapes.com/trackers/video/the-internet- of-things-and-sensors-and-actuators/ 4 •2
Trang 3
The IoT Value Chain Fall 2019 IoT has the potential to transform how and when decisions are made throughout business and our daily lives iff high quality data can be processed efficiently and analyzed effectively! https://www.besanttechnologies.com/iot-training-in-bangalore5 Types of IoT Data Fall 2019 Addresses/Unique Identifiers (nominal) – IP (IPv4, IPv6), Bluetooth, Zigbee, LoRa, RFID Positional Data (continuous) – GPS (Longitude, Latitude, Altitude), WiFi (Longitude, Latitude) Temporal Data (continuous) – Time and Date Sensor Data (numerical) – Output of a device that detects and responds to some type of input from the physical environment (motion, position, environment, mass, biomarker) Descriptive Data (categorical) – Objects, Processes, and Systems 7 •3
Trang 4
Fall 2019 IoT Data: Sensing the Physical World! IoT data is becoming soon “mega” big (i.e. billions of connected Things) – 44EB / months corresponds to ~ 100M hard disks 10 – Processing 44 EB with 100M servers would still take > one hour IoT “data in motion” as opposed to traditional “data at rest” – Data speed is bound by the sensing frequency and connectivity – Data throughput (vs processing) has become the limiting factor! High variety data e.g., from heterogeneous Things, embedded in the environment or wearable by persons High veracity data (dropped or unlivable) as IoT data quality depends on how Things are used and connected in the wild High variability data as Things frequently change behavior dynamically and in ways that are not fully known in advance Data security, privacy, etc. even more important! 8 Fall 2019 IoT Data Analytics Use Cases – Real-time monitoring and control – Failure detection and predictive maintenance Anomaly Detection – Malicious cyber activity detection – Product life-cycle management – Operational efficiency, optimization, self-adaptation Batch and Online Techniques – Descriptive Analytics: aggregation and statistics – Predictive Analytics: Supervised, Semi-Supervised, Unsupervised – Data series analytics: Spatiotemporal – Domain and data type specific: Signal processing 10 •4
Trang 5
Fall 2019 Real Time Anomaly Detection Network and Monitor Monitor Traffic Cyber Security Conditions Detect Intrusion Biomarkers Predictive maintenance, Agriculture Monitor Energy Production safety Pest, Water Consumption Monitoring Control Define alerts, predict faults, detect intrusions & threats 11 Fall 2019 What is Real Time Analytics? Time value of sensor data means that the data you have right now won’t mean as much a week, day or even hour from now ! near real medium- long- historical time term term https://www.slideshare.net/AmazonWebServices/introduction-to-realtime- streaming-data-and-amazon-kinesis-streaming-data-ingestion-with-firehouse13 •5
Trang 6
A 3-tier Architecture for IoT AnalyticsFall 2019 To support analytics with different time horizons (near-real time, medium, long terms), we need to a 3-tier architecture for IoT freshly data historical data data from neighborhood (cohort) devices http://pjtec.info/how-the-internet-of-things-will- shape-the-datacenter-of-the-future-2/iot-20150804/ 14 Fall 2019 Edge Processing/Computing Objective: push data processing away from the core and towards the edge of the network – help ensuring that the right data processing task takes place at the right time and place Motivating factors: 1. Reduce latency: run data computations directly on IoT devices or gateways, and only interact with the Cloud off the critical path (e.g. to continuously train ML models with freshly data) 2. Be robust to connectivity issues: applications are not disrupted in case of limited or intermittent network connectivity 3. Preserve privacy: ensures that sensitive data is pre-processed on- site, and only data that is privacy compliant is sent to the Cloud for further analysis, after having passed through a first layer of anonymizing aggregation Wide range of technologies: Local Cloud/Fog computing, Grid/Mesh Computing, mobile edge computing, cloudlets, etc. 15 •6
Trang 7
A Fog/Edge Computing ArchitectureFall 2019 large compute storage offline larger compute online limited storage l real time compute storage B. Tang, Z. Chen, G. Hefferman, T. Wei, H. He, Q. Yang. A Hierarchical Distributed Fog 16 Computing Architecture for Big Data Analysis in Smart Cities. ASE BD&SI 2015 Fall 2019 So to Recap The Internet of Things Is more About Data, than Things! – data in motion usually with spatiotemporal semantics – produced by several, distributed, heterogeneous devices – in the wild, hence data prone to errors and noise Low-latency, privacy-aware IoT data processing in post-cloud architectures – Edge/fog computing for effectively and efficiently ingesting and analyzing data when and where it is needed Real time IoT Data Analytics requires data streams support – Limited ground truth calls for unsupervised techniques 17 •7
Trang 8
Fall 2019 Data Anomaly Detection 18 Fall 2019 Data Anomalies What are anomalies? – “An outlier is an observation in a dataset that appears to be inconsistent with the remainder of that dataset” [Johnson 1992] – “An outlier is an observation that deviates so much from other observations as to arouse suspicion that it was generated by a different mechanism” [Hawkins 1980] Anomaly, or outlier, or deviation, or novelty detection, aims to measure whether a data point (or a subset) considerably differs than the remainder of the data points – On a scatter plot of the data, they lie far away from other data – Anomalies = Outliers + Novelties http://www.kdd.org/kdd2016/topics/view/outlier-and- anomaly-detection 19 •8
Trang 9
Cause of Data Anomalies Fall 2019 Errors in the data collection or measurement process – Because of human error (intentional or not), a problem with a measuring device or the presence of noise – Insights extracted from “dirty data” are probably erroneous and thus the decisions to be made are likely unsound (e.g., incur a high rate of false positives and false negatives) Changes in the “data generation” process, e.g. some given statistical process (not an error, novelties in data) – Abnormal data deviate from this generating mechanism because it is of a different type – Novel class of observations provide valuable insights 20 Types of Anomalies Fall 2019 Point Anomaly Data point anomalous Detection w.r.t. to the rest of the data Data point anomalous in a Contextual specific context; also Anomaly Detection referred to as conditional anomalies A group of data points is Group Anomaly anomalous; the individual Detection points within a group are not anomalous by themselves Chandola, V., Banerjee, A., & Kumar, V. (2009). Anomaly detection: A survey. ACM Computing Surveys, 41(3), 1–58. 21 •9
Trang 10
Fall 2019 Scope of Anomaly Detection Methods local global o1 o3 N micro-cluster 1 O4 global o2 N2 Swamping: wrongly identifying normal instances as anomalies when normal instances are too close to anomalies Masking : an anomaly is close to another point, anomalous or not M. Goldstein, S. UchidaA Comparative Evaluation of Unsupervised Anomaly Detection Algorithms for Multivariate Data. PLoS One. 2016;11(4) 22 Fall 2019 Example: Most Unusual Objects? screw battery bead block box key penny knob dime eraser https://www.slideshare.net/mlvlc/l14-anomaly-detection23 •10
Trang 11
Fall 2019 Example: How to Distinguish Objects? https://www.slideshare.net/mlvlc/l14-anomaly-detection24 Fall 2019 High-Dimensional Data: Example Object Length/Width Num Surfaces Smooth penny 1 3 true rounddime 1 3 true knob 1 4 true box 1 6 true eraser 2.75 6 true cornersblock 1.6 6 true screw 8 3 true battery 5 3 true skinny key 4.25 3 false bead 1 2 true https://www.slideshare.net/mlvlc/l14-anomaly-detection •11
Trang 12
Multi-Dimensional Anomaly DetectionFall 2019 Anomaly detection in multi-dimensional datasets reveals more accurate behavior of the data but at the same time poses various challenges http://wikistat.fr/pdf/st-m-app-anomalies.pdf 27 Fall 2019 Multi-Dimensional Anomaly Detection – Space concentration of distances: feature-wise distances of i.i.d. data samples approximately converge to a normal distribution – The number of feature subspaces grows exponentially with the increasing dimensionality of data: data density functions not easily computed – Data-snooping bias: given enough features, at least one feature subspace can be found for each data point such that it appears as an anomaly D. L. Donoho, “High-dimensional data analysis: The curses and blessings of dimensionality,” AMS Math Challenges Lecture, pp. 1–32, 2000. 28 •12
Trang 13
Multi-Dimensional Anomaly DetectionFall 2019 Challenge: select a subspace that highlights relevant features, i.e. in which anomalies exhibit significantly different values from normal data – A robust anomaly detector should be able to detect anomalies with a high proportion of irrelevant features creating noise in the input data, which masks the true anomalies L. Wilkinson Visualizing Big Data Outliers through Distributed Aggregation 29 IEEE Trans. Vis. Comput. Graph. 24(1):Jan. 2018. Anomaly Detection Methods Fall 2019 Machine Learning Semi- Supervised Unsupervised Supervised Classification Nearest Neighbor Clustering Ensemble One class HBOS based based based SVM Tree- Distance- Density CBLOF– Isolation PSVM based based based uCBLOF Forest SVDD Hoeffding DB-Outlier LOF COD - Half- Space QSSVM MCOD kth-NN LOCI CESVM RRCF Storm ABOD Streaming Algorithms Goldstein M, Uchida S (2016) A Comparative Evaluation of Unsupervised Anomaly Detection Algorithms for Multivariate Data. PLOS ONE 11(4) 31 •13
Trang 14
Random Trees Fall 2019 Build a decision tree from a random data subsample F T F T Partition feature space using axis-parallel subdivisions – Select the split feature A, randomly and uniformly – Select the split value VA, uniformly as the min(A)+(max(A)–min(A))*rand(1) Grow a random tree until each data point is in its own leaf or the tree reaches a maximum height https://www.slideshare.net/mlvlc/l14-anomaly-detection Fall 2019 Isolation Forest [Liu et al. 2008] To score a data point, find the height of the leaf node – The smaller the height the more anomalous is the data Build an ensemble of decision trees from randomly selected subsamples of size n https://www.slideshare.net/mlvlc/l14-anomaly-detection34 •14
Trang 15
Fall 2019 Isolation Forest Scores Use average height to compute the anomaly score: – 0 (normality) 1 (abnormality) Score – Ensemble average path length to a data point – Normalized by the expected path length of balanced binary search tree https://towardsdatascience.com/a-brief-overview-of- outlier-detection-techniques-1e0b2c19e561 35 Fall 2019 Isolation Forest Scores 12 partitions (not an anomaly) 4 partitions (anomaly) https://www.depends-on-the-definition.com/detecting- network-attacks-with-isolation-forests/ 36 •15
Trang 16
Fall 2019 iForest: Pros and Cons Pros – Very easy to construct (no distance/density function needed) avoiding hard decisions whether a data point is an anomaly or not • assigns an anomalous score to each data point – Achieve a sublinear time-complexity and a small memory-footprint • By exploiting subsampling • By eliminating major computational cost of distance calculation in all the distance-based and density-based AD methods – Can provide anomaly explanations [Siddiqui et al. 2015] Cons – Hyper-parameter tuning (e.g. number/height of trees, sample size) • Large datasets will need more isolation trees (how many?) – Requires a high percentage of relevant features to identify anomalies [Bandaragoda et al. 2018] • In presence of features that do not provide information over the anomaly, iForest increases height randomly by ignoring this fact 40 Fall 2019 Performance Measures of AD Algorithms Confusion Actual Normal Actual Anomalous Matrix Data (nn) Data (na) Predicted Non- TN FN anomalies Predicted FP TP Anomalies Accuracy Rate (ACC) = (TP + TN ) / (TN + FP + FN + TP) False Alarm –Positive– Rate (FAR) = FP/ (FP + TN) True Positive –Detection– Rate (TPR) = TP/ (TP + FN) Receiver Operating Characteristic (ROC)= tradeoff between TPR&FAR Area Under the ROC Curve (AUC): can be computed by a slight modification of the algorithm for constructing ROC curves 45 •16
Trang 17
Fall 2019 ROC Spaces and AUC Ideal ROC curve ROC curves are two dimensional plots ROC curve of Algo B in which the true positive (TP) rate is platen on the Y axis and the false positive (FP) rate on the X axis ROC curve of Algo A Area Under the ROC Curve (AUC) has an important statistical property: – The AUC of a classifier is equivalent (sensitivity) AUC with the probability that the classifier will rank a randomly chosen positive instance higher than a randomly chosen negative instance – When comparing classifiers, the (1- specificity) bigger AUC the better! http://slideplayer.com/slide/5379166/ 47 Summary Fall 2019 AD algorithms usually report different outliers per dataset – they may miss obvious outliers especially in heterogeneous datasets that contain a mixture of numerical and categorical attributes Which anomaly detection method to use depends on – Data characteristics: dimensionality (Univariate, Multivariate) and type (categorical numerical) – Anomaly characteristics: type (Point, Collective), semantics (Set- based, Sequence-based), kind (Binary, Score) – Availability of labels: supervised, unsupervised, semi-supervised – Algorithmic properties: computational cost (exponential vs linear), prior knowledge (parametric, non-parametric), distributional/ incremental computation potential, … How we can automate the selection of the most suitable AD algorithm for a particular dataset with minimal human involvement and within limited computational budgets? 49 •17
Trang 18
Fall 2019 Anomaly Detection in Data Streams 50 Fall 2019 Offline vs Online Anomaly Detection A data stream is a possible infinite series of data points ..., on−2, on−1, on, ..., where data point on is received at time on.t. Offline learning (for finite streams): – All data is stored and can be accessed in multiple passes – Learned model is static – Potentially high memory and processing overhead Online learning (for infinite streams): – Single pass over the data which are discarded after being processed – Learned model is updated : one point at a time or in mini-batches – Low memory and processing overhead 51 •18
Trang 19
Fall 2019 Online Anomaly Detection: Challenges Limited computational resources for unbounded data – window-based algorithms High speed data streams: – the rate of updating a detection model should be higher than the arrival rate of data Online Both normal and anomalous data characteristics ML may evolve in time and hence detector models need to quickly adjust to concept drifts/shifts: – adversarial situations (fraud, insider threats) – diverse set of potential causes (novel device failure modes) – user’s notion of “anomaly” may change with time 52 Fall 2019 Robust Random Cut Forest (RRCF) [Guha et al, ICML 2016] Construct random trees as iForest but incrementally update their binary tree structure using sliding windows – Traverse a tree to Insert a new point to a leaf node, use FIFO to remove the oldest point if this procedure exceeds the max number of leaf nodes – Calculate the Displacement of the new point, as the number of leaf nodes that updated (moved/deleted) in a tree after the insertion Principled definitions of anomalies – Calculate the Collusive Displacement (CD) of a new point in a tree, as the maximal displacement across all nodes traversed in a path from the root – Outliers correspond to points that their average CD in the forest is large, instead of small average tree height Address iForest limitation in case of multiple irrelevant features – Does not uniformly selects the split feature 52 •19
Trang 20
Fall 2019 RRCF : Example Given the following input stream of points 𝑆 Screw Knob Box Penny Key Dime Battery Block Eraser … – Start by collecting the first w = 7 points of 𝑆, as a Initial Training Sample 𝑥={𝑥1,𝑥2,…, 𝑥𝑗} where 𝑥i ∈ 𝑅d, in order to build the initial Tree – Assumption : • all objects within x are considered as inliers 54 Fall 2019 RRCF Tree Construction: Example Object L/W NS S Screw 8 3 0 Consider the value range per feature Dime 1 3 1 li = maxxi − minxi Knob 1 4 1 x x Battery 5 3 1 Box 1 6 1 Pick a spliting feature w.r.t. its Block 1.6 6 1 normalized value range li Penny 1 2 1 σj lj L/W NS S Choose uniformly a splitting value Minimum 1 2 0 X ~Uniform[minx ,maxx ] value i x i x i Maximum 8 6 1 Value Range 7 4 1 Length/Width (L/W), Num Surface (NS),Smooth (S) 55 •20
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!