Fast Unsupervised Online Drift Detection Using Incremental Kolmogorov-Smirnov Test

Author(s)

dos Reis, Denis ; Flach, Peter ; Matwin, Stan ; Batista, Gustavo ; Assoc Comp Machinery

• Document type: Journal article
• Source: KDD'16: PROCEEDINGS OF THE 22ND ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING; v. N/A, p. 10-pg., 2016-01-01.

Abstract

Data stream research has grown rapidly over the last decade. Two major features distinguish data stream from batch learning: stream data are generated on the fly, possibly in a fast and variable rate; and the underlying data distribution can be non-stationary, leading to a phenomenon known as concept drift. Therefore, most of the research on data stream classification focuses on proposing efficient models that can adapt to concept drifts and maintain a stable performance over time. However, specifically for the classification task, the majority of such methods rely on the instantaneous availability of true labels for all already classified instances. This is a strong assumption that is rarely fulfilled in practical applications. Hence there is a clear need for efficient methods that can detect concept drifts in an unsupervised way. One possibility is the well-known Kolmogorov-Smirnov test, a statistical hypothesis test that checks whether two samples differ. This work has two main contributions. The first one is the Incremental Kolmogorov-Smirnov algorithm that allows performing the Kolmogorov-Smirnov hypothesis test instantly using two samples that change over time, where the change is an insertion and/or removal of an observation. Our algorithm employs a randomized tree and is able to perform the insertion and removal operations in O(log N) with high probability and calculate the Kolmogorov-Smirnov test in O(1), where N is the number of sample observations. This is a significant speed-up compared to the O(N log N) cost of the non-incremental implementation. The second contribution is the use of the Incremental Kolmogorov-Smirnov test to detect concept drifts without true labels. Classification algorithms adapted to use the test rely on a limited portion of those labels just to update the classification model after a concept drift is detected. (AU)

• FAPESP's process: 15/01701-8 - Data stream analysis and evaluation under the presence of verification latency
• Grantee: Denis Moreira dos Reis
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• FAPESP's process: 13/50379-6 - Research on geo-spatial marine biology data mining using time series, text mining and visualization
• Grantee: Gustavo Enrique de Almeida Prado Alves Batista
• Support Opportunities: Regular Research Grants
• FAPESP's process: 14/12333-7 - Data stream classification with concept drift and extreme verification latency
• Grantee: Denis Moreira dos Reis
• Support Opportunities: Scholarships in Brazil - Master