Abstract Ensuring fairness when training Machine Learning (ML) models remains a critical challenge, particularly when biases are embedded in the underlying data. This paper presents a fairness-aware graph structure learning framework demonstrating how learning fair graphs leads to fairer data for ML training and, consequently, fairer Artificial Intelligence (AI) decisioning based on such models. Our method incorporates a fairness regularization term into score-based structure learning algorithms, guiding the search towards graph structures that minimize discriminatory pathways while preserving statistical relationships. The learned fair graph structures enable the generation of synthetic datasets with mitigated biases, which can be used to train diverse ML models. This modification is non-trivial, as structure learning algorithms rely on local search strategies, while fairness is a global property that depends on the entire graph structure. Our framework is highly adaptable, compatible with various structure learning algorithms, and seamlessly incorporates different fairness metrics to meet specific contextual needs. Extensive experiments on both real-world and synthetic datasets demonstrate that our approach significantly improves fairness while maintaining competitive predictive performance, offering an interpretable and versatile solution for mitigating bias in AI systems..

Machine learning models often suffer from performance degradation when dealing with class distributions that differ from the training distribution, a scenario commonly referred to as label shift. Addressing this challenge, this paper introduces Match, a novel adjustment approach that maximizes the likelihood of predicted probabilities under class prevalence constraints. Unlike existing methods such as retraining with instance re-weighting and the Bayes update rule, Match ensures that the adjusted class distribution aligns precisely with the prevalence estimates from quantifiers. By formulating the adjustment process as a binary integer linear optimization problem, Match benefits from efficient mixed-integer solvers. Extensive experiments demonstrate that Match outperforms the state-of-the-art in classifier adjustment with statistical significance, particularly in handling scenarios with imbalanced distributions.

An assumption often made in supervised learning is that the training and testing sets have the same label distribution. However, in real-life scenarios, this assumption rarely holds. For example, medical diagnosis result distributions change over time and across locations; fraud detection models must adapt as patterns of fraudulent activity shift; the category distribution of social media posts changes based on trending topics and user demographics. In the task of label shift estimation, the goal is to estimate the changing label distribution pt(y) in the testing set, assuming the likelihood p(x|y) does not change, implying no concept drift. In this paper, we propose a new approach for post-hoc label shift estimation, unlike previous methods that perform moment matching with confusion matrix estimated from a validation set or maximize the likelihood of the new data with an expectation-maximization algorithm. We aim to incrementally update the prior on each sample, adjusting each posterior for more accurate label shift estimation. The proposed method is based on intuitive assumptions on classifiers that are generally true for modern probabilistic classifiers. The proposed method relies on a weaker notion of calibration compared to other methods. As a post-hoc approach for label shift estimation, the proposed method is versatile and can be applied to any black-box probabilistic classifier. Experiments on CIFAR-10 and MNIST show that the proposed method consistently outperforms the current state-of-the-art maximum likelihood-based methods under different calibrations and varying intensities of label shift.

Deep neural networks often produce miscalibrated probability estimates, leading to overconfident predictions. A common approach for calibration is fitting a post-hoc calibration map on unseen validation data that transforms predicted probabilities. A key desirable property of the calibration map is instance-wise monotonicity (i.e., preserving the ranking of probability outputs). However, most existing post-hoc calibration methods do not guarantee monotonicity. Previous monotonic approaches either use an under-parameterized calibration map with limited expressive ability or rely on black-box neural networks, which lack interpretability and robustness. In this paper, we propose a family of novel monotonic post-hoc calibration methods, which employs a constrained calibration map parameterized linearly with respect to the number of classes. Our proposed approach ensures expressiveness, robustness, and interpretability while preserving the relative ordering of the probability output by formulating the proposed calibration map as a constrained optimization problem. Our proposed methods achieve state-of-the-art performance across datasets with different deep neural network models, outperforming existing calibration methods while being data and computation-efficient. Our code is available at https://github.com/YunruiZhang/Calibration-by-Constrained-Transformation

Pedestrian trajectory prediction plays an important role in autonomous driving systems and robotics. Recent work utilizing prominent deep learning models for pedestrian motion prediction makes limited a priori assumptions about human movements, resulting in a lack of explainability and explicit constraints enforced on predicted trajectories. We present a dynamics-based deep learning framework with a novel asymptotically stable dynamical system integrated into a Transformer-based model. We use an asymptotically stable dynamical system to model human goal-targeted motion by enforcing the human walking trajectory, which converges to a predicted goal position, and to provide the Transformer model with prior knowledge and explainability. Our framework features the Transformer model that works with a goal estimator and dynamical system to learn features from pedestrian motion history. The results show that our framework outperforms prominent models using five benchmark human motion datasets.

Internet of Things (IoT) devices have grown in popularity since they can directly interact with the real world. Home automation systems automate these interactions. IoT events are crucial to these systems’ decision-making but are often unreliable. Security vulnerabilities allow attackers to impersonate events. Using statistical machine learning, IoT event fingerprints from deployed sensors have been used to detect spoofed events. Multivariate temporal data from these sensors has structural and temporal properties that statistical machine learning cannot learn. These schemes’ accuracy depends on the knowledge base; the larger, the more accurate. However, the lack of huge datasets with enough samples of each IoT event in the nascent field of IoT can be a bottleneck. In this work, we deployed advanced machine learning to detect event-spoofing assaults. The temporal nature of sensor data lets us discover important patterns with fewer events. Our rigorous investigation of a publicly available real-world dataset indicates that our time-series-based solution technique learns temporal features from sensor data faster than earlier work, even with a 100- or 500-fold smaller training sample, making it a realistic IoT solution.

As the adoption of Internet of Things (IoT) devices continues to rise in enterprise environments, the need for effective and efficient security measures becomes increasingly critical. This paper presents a cost-efficient platform to facilitate the pre-deployment security checks of IoT devices by predicting potential weaknesses and associated attack patterns. The platform employs a Bidirectional Long Short-Term Memory (Bi-LSTM) network to analyse device-related textual data and predict weaknesses. At the same time, a Gradient Boosting Machine (GBM) model predicts likely attack patterns that could exploit these weaknesses. When evaluated on a dataset curated from the National Vulnerability Database (NVD) and publicly accessible IoT data sources, the system demonstrates high accuracy and reliability. The dataset created for this solution is publicly accessible.

Machine learning-based techniques have proven to be effective in Internet-of-Things (IoT) network behavioral inference. Existing works developed data-driven models based on features from network packets and/or flows, but mainly in a static and ad-hoc manner, without adequately quantifying their gains versus costs. In this article, we develop a generic architecture that comprises two distinct inference modules in tandem, which begins with IoT network behavior classification followed by continuous monitoring. In contrast to prior relevant works, our generic architecture flexibly accounts for various traffic features, modeling algorithms, and inference strategies. We argue quantitative metrics are required to systematically compare and efficiently select various traffic features for IoT traffic inference. This article 1 makes three contributions: (1) For IoT behavior classification, we identify four metrics, namely, cost, accuracy, availability, and frequency, that allow us to characterize and quantify the efficacy of seven sets of packet-based and flow-based traffic features, each resulting in a specialized model. By experimenting with traffic traces of 25 IoT devices collected from our testbed, we demonstrate that specialized-view models can be superior to a single combined-view model trained on a plurality of features by accuracy and cost. We also develop an optimization problem that selects the best set of specialized models for a multi-view classification. (2) For monitoring the expected IoT behaviors, we develop a progressive system consisting of one-class clustering models (per IoT class) at three levels of granularity. We develop an outlier detection technique on top of the convex hull algorithm to form custom-shape boundaries for the one-class models. We show how progression helps with computing costs and the explainability of detecting anomalies. (3) We evaluate the efficacy of our optimally selected classifiers versus the superset of specialized classifiers by applying them to our IoT traffic traces. We demonstrate how the optimal set can reduce the processing cost by a factor of six with insignificant impacts on the classification accuracy. Also, we apply our monitoring models to a public IoT dataset of benign and attack traces and show they yield an average true-positive rate of 94% and a false-positive rate of 5%. Finally, we publicly release our data (training and testing instances of classification and monitoring tasks) and code for convex hull-based one-class models.

Quantification research proposes methods to estimate the class distribution in an independent sample. Quantification methods find applications in areas that rely on estimated aggregated quantities, such as epidemiology, sentiment analysis, political research, and ecological surveillance. For instance, epidemiologists are often concerned with the dynamics of the number of disease cases across space and time. Thus, while classification predicts individual subjects, quantifiers are the methods that directly estimate the number of cases. Although quantification is a thriving area of research, with numerous approaches proposed in the last decade, most focus has been on binary-class quantifiers. One common approach for multi-class quantification is the one-versus-all (OVA) approach, but empirical evidence suggests its performance is suboptimal. This paper's first contribution is to elucidate why OVA quantifiers struggle to perform well in multi-class settings due to a distribution shift. To circumvent this problem, our second proposal is two new multi-class quantifiers based on ensemble learning that significantly improve performance for binary and multi-class settings. Our comprehensive experimental setup with 37 state-of-the-art (single and ensemble) quantifiers shows that our ensembles are the best-performing quantifiers and rank first in a recent quantification competition.

Quantification research proposes methods to estimate the class distribution in an independent sample. Many areas, such as epidemiology, sentiment analysis, political research and ecological surveillance, rely on quantification methods to estimate aggregated quantities. For instance, epidemiologists are often concerned with the dynamics of the number of disease cases across space and time. Thus, while classification predicts individual subjects, quantification is the class of methods that directly estimate the number of cases. Quantification is a thriving research area, and the community has proposed several approaches in the last decade. Nevertheless, most quantification research has focused on binary-class quantifiers, expecting these approaches to extend to multi-class using the one-versus-all (OVA) approach. However, there is enough empirical evidence indicating the performance of OVA multi-class quantifiers is subpar. This paper has two main contributions. First, we demonstrate why OVA quantifiers are doomed to underperform in multi- class settings due to a distribution shift they cannot handle. Second, we propose a new class of quantifiers based on ensemble learning that boosts the performance of the base quantifiers in the binary and, more importantly, multi-class settings. In one of the most comprehensive experimental setups ever attempted in quantification research, we show that our ensembles are the best-performing quantifiers compared with 33 state-of-the-art (single and ensemble) quantifiers and rank first in a recent quantification competition.

Millions of vulnerable consumer IoT devices in home networks are the enabler for cyber crimes putting user privacy and Internet security at risk. Internet service providers (ISPs) are best poised to mitigate risks by automatically inferring active IoT devices per household and notifying users of vulnerable ones. Developing a scalable inference method that can perform robustly across thousands of home networks is a nontrivial task. This article focuses on the challenges of developing and applying data-driven inference models when labeled data of device behaviors is limited and the distribution of data changes across time and space domains (concept drifts). Our contributions are fourfold: 1) we collect and analyze more than six million network traffic flows of 24 types of consumer IoT devices from 12 real homes over six weeks to highlight the challenge of temporal and spatial concept drifts in network behaviors of IoT devices—we publicly release our training and testing instances data; 2) we analyze the performance of two inference strategies, namely global inference (a model trained on a combined set of all labeled data from training homes) and contextualized inference (several models each trained on the labeled data from a training home) in the presence of concept drifts; 3) to manage concept drifts, we develop a method that dynamically applies the “best” model (from a set) to network traffic of unseen homes during the testing phase, yielding better performance in a fifth of scenarios when the labels are available for the testing data (ideal but unrealistic settings); and 4) we develop a method to automatically select the best model without needing labels of unseen data (a realistic inference) and show that it can achieve 94% of the ideal model’s accuracy.

The quantification objective is to predict the class distribution of a data sample. Therefore, this task intrinsically involves a drift in the class distribution that causes a mismatch between the training and test sets. However, existing quantification approaches assume that the feature distribution is stationary. We analyse for the first time how score-based quantifiers are affected by concept drifts and propose a novel drift-resilient quantifier for binary classes. Our proposal does not model the different types of concept drifts. Instead, we model the changes that such changes cause in the classification scores. This observation simplifies our analysis since distribution changes can only increase, decrease or maintain the overlap of the positive and negative classes in a rank induced by the scores. Our paper has two main contributions. The first one is MoSS, a model for synthetic scores. We use this model to show that state-of-the-art quantifiers underperform in the occurrence of any concept drift that changes the score distribution. Our second contribution is a quantifier, DySyn, that uses MoSS to estimate the class distribution. We show that DySyn statistically outperforms state-of-the-art quantifiers in a comprehensive comparison with real-world and benchmark datasets in the presence of concept drifts.

Elections are complex activities fundamental to any democracy. The contextualized analysis of election data allows us to understand electoral behavior and the factors that influence it. Multidisciplinary studies have been prioritized the predictive modeling of electoral features from thousands of explanatory features, considering geographic and spatial aspects inherent to the data. When building a model for such a purpose, it must be rigorously evaluated to understand its prediction error in future test cases. Although cross-validation is a widely used procedure for this task, it leads to optimistic results because the spatial independence between test and training data is not ensured in the resampling. On the other hand, alternatives to deal with spatial dependence may fall into a pessimistic scenario by assuming total spatial independence between the test and training sets regardless of the size of the first one, increasing the probability of overfitting. This paper addresses these issues by proposing a graph-based spatial cross-validation approach to assess models learned with selected features from spatially contextualized electoral datasets. Our approach takes advantage of the spatial graph structure provided by the lattice-type spatial objects to define a local training set to each test fold. We generate the local training sets by removing spatially close data that are highly correlated and irrelevant distant data that may interfere with error estimates. Experiments involving the second round of the 2018 Brazilian presidential election demonstrate that our approach contributes to the fair evaluation of models by enabling more realistic and local modeling.

Quantification is a thriving research area that develops methods to estimate the class prior probabilities in an unlabelled set of observations. Quantification and classification share several similarities. For instance, the most straightforward quantification method, Classify & Count (CC), directly counts the output of a classifier. However, CC has a systematic bias that makes it increasingly misestimate the counts as the class distribution drifts away from a distribution it perfectly quantifies. This issue has motivated the development of more reliable quantification methods. Such newer methods can consistently outperform CC at the cost of a significant increase in processing requirements. Yet, for a large number of applications, quantification speed is an additional criterion that must be considered. Frequently, quantification methods need to deal with large amounts of data or fast-paced streams, as it is the case of news feeding, tweets and sensor data. In this paper, we propose Sample Mean Matching (SMM), a highly efficient algorithm able to quantify billions of data instances per second. We compare SMM to a set of 14 established and state-of-the-art quantifiers in an empirical analysis comprising 25 benchmark and real-world datasets. We show that SMM is competitive with state-of-the-art methods with no statistical difference in counting accuracy, and it is orders of magnitude faster than the vast majority of the algorithms.

In the last decades, many companies have taken advantage of knowledge discovery to identify valuable information in massive volumes of data generated at high frequency. Machine learning techniques can be employed for knowledge discovery since they can extract patterns from data and induce models to predict future events. However, dynamic and evolving environments usually generate non-stationary data streams. Hence, models trained in these scenarios may perish over time due to seasonality or concept drift. Periodic retraining can help, but a fixed hypothesis space may no longer be appropriate. An alternative solution is to use meta-learning for regular algorithm selection in time-changing environments, choosing the bias that best suits the current data. In this paper, we present an enhanced framework for data stream algorithm selection based on MetaStream. Our approach uses meta-learning and incremental learning to actively select the best algorithm for the current concept in a time-changing environment. Different from previous work, we use a rich set of state-of-the-art meta-features, and an incremental learning approach in the meta-level based on LightGBM. The results show that this new strategy can improve the recommendation accuracy of the best algorithm in time-changing data.

Quantification is a task similar to classification in the sense that it learns from a labeled training set. However, quantification is not interested in predicting the class of each observation, but rather measure the class distribution in the test set. The community has developed performance measures and experimental setups tailored to quantification tasks. Nonetheless, we argue that a critical variable, the size of the test sets, remains ignored. Such disregard has three main detrimental effects. First, it implicitly assumes that quantifiers will perform equally well for different test set sizes. Second, it increases the risk of cherry-picking by selecting a test set size for which a particular proposal performs best. Finally, it disregards the importance of designing methods that are suitable for different test set sizes. We discuss these issues with the support of one of the broadest experimental evaluations ever performed, with three main outcomes. (i) We empirically demonstrate the importance of the test set size to assess quantifiers. (ii) We show that current quantifiers generally have a mediocre performance on the smallest test sets. (iii) We propose a metalearning scheme to select the best quantifier based on the test size that can outperform the best single quantification method.

Quantification is an expanding research topic in Machine Learning literature. While in classification we are interested in obtaining the class of individual observations, in quantification we want to estimate the total number of instances that belong to each class. This subtle difference allows the development of several algorithms that incur smaller and more consistent errors than counting the classes issued by a classifier. Among such new quantification methods, one particular family stands out due to its accuracy, simplicity, and ability to operate with imbalanced training samples: Mixture Models (MM). Despite these desirable traits, MM, as a class of algorithms, lacks a more in-depth understanding concerning the influence of internal parameters on its performance. In this paper, we generalize MM with a base framework called DyS: Distribution y-Similarity. With this framework, we perform a thorough evaluation of the most critical design decisions of MM models. For instance, we assess 15 dissimilarity functions to compare histograms with varying numbers of bins from 2 to 110 and, for the first time, make a connection between quantification accuracy and test sample size, with experiments covering 24 public benchmark datasets. We conclude that, when tuned, Topsøe is the histogram distance function that consistently leads to smaller quantification errors and, therefore, is recommended to general use, notwithstanding Hellinger Distance’s popularity. To rid MM models of the dependency on a choice for the number of histogram bins, we introduce two dissimilarity functions that can operate directly on observations. We show that SORD, one of such measures, presents performance that is slightly inferior to the tuned Topsøe, while not requiring the sensible parameterization of the number of bins.

Machine Learning (ML) is becoming a ubiquitous technology employed in many real-world applications. In some applications, sensors measure the environment while ML algorithms are responsible for interpreting the data. These systems often face three main restrictions: power consumption, cost, and lack of infrastructure. Therefore, we need highly-efficient classifiers suitable to execute in unresourceful hardware. However, this scenario conflicts to the state-of-practice of ML, in which classifiers are frequently implemented in high-level interpreted languages, make unrestricted use of floating-point operations and assume plenty of resources. In this paper, we present a software tool named EmbML that implements a pipeline to develop classifiers for low-powered embedded systems. It starts with learning a classifier using popular software packages or libraries. Then, EmbML converts the classifier into a carefully crafted C++ code with support for embedded hardware. Our experimental evaluation shows that EmbML classifiers present competitive results in terms of accuracy, time and memory cost.

The choice of the most promising algorithm to model and predict a particular phenomenon is one of the most prominent activities of the temporal data forecasting. Forecasting (or prediction), similarly to other data mining tasks, uses empirical evidence to select the most suitable model for a problem at hand since no modeling method can be considered as the best. However, according to our systematic literature review of the last decade, few scientific publications rigorously expose the benefits and limitations of the most popular algorithms for time series prediction. At the same time, there is a limited performance record of these models when applied to complex and highly nonlinear data. In this paper, we present one of the most extensive, impartial and comprehensible experimental evaluations ever done in the time series prediction field. From 95 datasets, we evaluate eleven predictors, seven parametric and four non-parametric, employing two multi-step-ahead projection strategies and four performance evaluation measures. We report many lessons learned and recommendations concerning the advantages, drawbacks, and the best conditions for the use of each model. The results show that SARIMA is the only statistical method able to outperform, but without a statistical difference, the following machine learning algorithms: ANN, SVM, and kNN-TSPI. However, such forecasting accuracy comes at the expense of a larger number of parameters. The evaluated datasets, as well detailed results achieved by different indexes as MSE, Theil’s U coefficient, POCID, and a recently-proposed multi-criteria performance measure are available online in our repository. Such repository is another contribution of this paper since other researchers can replicate our results and evaluate their methods more rigorously. The findings of this study will impact further research on this topic since they provide a broad insight into models selection, parameters setting, evaluation measures, and experimental setup.

Most algorithms for music data mining and retrieval analyze the similarity between feature sets extracted from the raw audio. A conventional approach to assess similarities within or between recordings is to create similarity matrices. However, this method requires quadratic space for each comparison and typically requires costly post-processing of the matrix. We have recently proposed SiMPle, a powerful representation based on subsequence similarity join, which is applicable in several music analysis tasks. In this paper, we propose SiMPle-Fast a highly efficient method for exact computation of SiMPle that is up to one order of magnitude faster than SiMPle. Furthermore, we demonstrate the utility of SiMPle-Fast in cover music recognition and thumbnailing tasks and show that our method is significantly faster and more accurate than the state-of-the-art.

The recent proposal of the Matrix Profile (MP) has brought the attention of the time series community to the usefulness and versatility of the similarity joins. This primitive has numerous applications including the discovery of time series motifs and discords. However, the original MP algorithm has two prominent limitations: the algorithm only works for Euclidean distance (ED) and it is sensitive to the subsequences length. Is this work, we extend the MP algorithm to overcome both limitations. We use a recently proposed variant of Dynamic Time Warping (DTW), the Prefix and Suffix Invariant DTW (PSI-DTW) distance. The PSI-DTW allows invariance to warp and spurious endpoints caused by segmenting subsequences and has a side-effect of supporting the match of subsequences with different lengths. Besides, we propose a suite of simple methods to speed up the MP calculation, making it more than one order of magnitude faster than a straightforward implementation and providing an anytime feature. We show that using PSI-DTW avoids false positives and false dismissals commonly observed by applying ED, improving the time series motifs and discords discovery in several application domains.

Many real-world applications in the batch and data stream settings with data shift pose restrictions to the access to class labels after the deployment of a classification or quantification model. However, a significant portion of the data stream literature assumes that actual labels are instantaneously available after issuing their corresponding classifications. In this paper, we explore a different set of assumptions without relying on the availability of class labels. We assume that, although the distribution of the data may change over time, it will switch between one of a handful of well-known distributions. Still, we allow the proportions of the classes to vary. In these conditions, we propose the first method that can accurately identify the correct context of data samples and simultaneously estimate the proportion of the positive class. This estimate can be further used to adjust a classification decision threshold and improve classification accuracy. Finally, the method is very efficient regarding time and memory requirements, fitting data stream applications.

Many real-world applications, such as those related to sensors, allow collecting large amounts of inexpensive unlabeled sequential data. However, the use of supervised machine learning methods is frequently hindered by the high costs involved in gath

While there exist a plethora of classification algorithms for most data types, there is an increasing acceptance that the unique properties of time series mean that the combination of nearest neighbor classifiers and Dynamic Time Warping (DTW) is very competitive across a host of domains, from medicine to astronomy to environmental sensors. While there has been significant progress in improving the efficiency and effectiveness of DTW in recent years, in this work we demonstrate that an underappreciated issue can significantly degrade the accuracy of DTW in real-world deployments. This issue has probably escaped the attention of the very active time series research community because of its reliance on static highly contrived benchmark datasets, rather than real world dynamic datasets where the problem tends to manifest itself. In essence, the issue is that DTW's eponymous invariance to warping is only true for the main "body" of the two time series being compared. However, for the "head" and "tail" of the time series, the DTW algorithm affords no warping invariance. The effect of this is that tiny differences at the beginning or end of the time series (which may be either consequential or simply the result of poor "cropping") will tend to contribute disproportionally to the estimated similarity, producing incorrect classifications. In this work, we show that this effect is real, and reduces the performance of the algorithm. We further show that we can fix the issue with a subtle redesign of the DTW algorithm, and that we can learn an appropriate setting for the extra parameter we introduced. We further demonstrate that our generalization is amiable to all the optimizations that make DTW tractable for large datasets.

Time series classification is an important task in data mining that has been traditionally addressed with the use of similarity-based classifiers. The 1-NN DTW is typically considered the most accurate model for temporal data. Nevertheless, some authors have recently proposed ingenious alternatives to the 1-NN DTW by using diversity of time series representation or by using DTW for feature extraction. In this paper, we explore diversity of time series representations and distance functions to obtain distance features, which in turn are used to train an SVM model. We argue that the scientific community has largely neglected a vast body of unconventional distance functions, and we present empirical evidence that distance features are better than the 1-NN DTW with respect to classification accuracy.

One of the widely used algorithms for graph-based semi-supervised learning (SSL) is the Local and Global Consistency (LGC). Such an algorithm can be viewed as a convex optimization problem that balances fitness on labeled examples and smoothness on the graph using a graph Laplacian. In this paper, we provide a novel graph-based SSL algorithm incorporating two normalization constraints into the regularization framework of LGC. We prove that our method has closed-form solution and generalizes two existing methods, being more flexible than the original ones. Through experiments on benchmark data sets, we show the effectiveness of our method, which consistently outperforms the competing methods.

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.

Dynamic Time Warping (DTW) is certainly the most relevant distance for time series analysis. However, its quadratic time complexity may hamper its use, mainly in the analysis of large time series data. All the recent advances in speeding up the exact DTW calculation are confined to similarity search. However, there is a significant number of important algorithms including clustering and classification that require the pairwise distance matrix for all time series objects. The only techniques available to deal with this issue are constraint bands and DTW approximations. In this paper, we propose the first exact approach for speeding up the all-pairwise DTW matrix calculation. Our method is exact and may be applied in conjunction with constraint bands. We demonstrate that our algorithm reduces the runtime in approximately 50% on average and up to one order of magnitude in some datasets.

In the last two decades, with the rise of the Data Mining process, there is an increasing interest in the adaptation of Machine Learning methods to support Time Series non-parametric modeling and prediction. The non-parametric temporal data modeling can be performed according to local and global approaches. The most of the local prediction data strategies are based on the k-Nearest Neighbor (kNN) learning method. In this paper we propose a modification of the kNN algorithm for Time Series prediction. Our proposal differs from the literature by incorporating three techniques for obtaining amplitude and offset invariance, complexity invariance, and treatment of trivial matches. We evaluate the proposed method with six complexity measures, in order to verify the impact of these measures in the projection of the future values. Besides, we face our method with two Machine Learning regression algorithms. The experimental comparisons were performed using 55 data sets, which are available at the ICMC-USP Time Series Prediction Repository. Our results indicate that the developed method is competitive and the use of a complexity-invariant distance measure generally improves the predictive performance.

The majority of evolving data streams classification algorithms assume that the actual labels of the predicted examples are readily available without any time delay just after a prediction is made. However, given the high label costs, dependence of an expert, limitations in data transmission or even restrictions imposed by the problem's nature, there is a large number of real-world applications in which the availability of actual labels is infinitely delayed (never available). In these cases, it is necessary the use of algorithms that does not follow the traditional process of monitoring the error rate to detect changes in data distribution and uses the most recent labeled data to update the classification model. In this paper, we propose the method MClassification to classify evolving data streams with infinitely delayed labels. Our method is inspired on the use of Micro-Cluster representation from online clustering algorithms. Considering the presence of incremental drifts, our approach uses a distance-based strategy to maintain the Micro-Clusters' positions updated. An evaluation in several synthetic and real data shows that MClassification achieves competitive accuracy results to state-of-the-art methods and adequate computational cost. The main advantage of the proposed method is the absence of critical parameters that require user's prior knowledge, as occurs with rival methods.

Throughout the history, insects had been intimately connected to humanity, in both positive and negative ways. Insects play an important part in crop pollination, on the other hand, some of them spread diseases that kill millions of people every year. Effective control of harmful insects while having little impact to beneficial insects and environment is extremely important. Recently, an intelligent trap that uses laser sensors was presented to control the population of target insects. The device could record and analyze sensor signals when an insect passes through the trap and make quick decisions whether to catch it or not. The effectiveness of the trap relies on the correct choice of classification algorithm to perform the insect detection. In this paper, we propose to use a deep neural network with maximum correntropy criterion (MCC) for reliable classification of insects in real-time. Experimental results show that, deep networks are effective for learning stable features from brief insect passage signals. By replacing the mean square error cost with MCC, the robustness of autoencoders against noise is improved significantly and robust features could be learned. The method is tested on five species of insects and a total of 5325 passages. High classification accuracy of 92.1% is achieved. Compared with previously applied methods, better classification performance is obtained using only 10% of the computation time. Therefore, our method is efficient and reliable for online insect detection.

Graph-based semi-supervised learning (SSL) algorithms perform well when the data lie on a low-dimensional manifold. Although these methods achieved satisfactory performance on a variety of domains, they have not been effectively evaluated on time series classification. In this paper, we provide a comprehensive empirical comparison of state-of-the-art graph-based SSL algorithms combined with a variety of graph construction methods in order to evaluate them on time series transductive classification tasks. Through a detailed experimental analysis using recently proposed empirical evaluation models, we show strong and weak points of these classifiers concerning both performance and stability with respect to graph construction and parameter selection. Our results show that some hypotheses raised on previous work do not hold in the time series domain while others may only hold under mild conditions.

Automatic classification of musical instruments is an important task for music transcription as well as for professionals such as audio designers, engineers and musicians. Unfortunately, only a limited amount of effort has been conducted to automatically classify percussion instrument in the last years. The studies that deal with percussion sounds are usually restricted to distinguish among the instruments in the drum kit such as toms vs. snare drum vs. bass drum vs. cymbals. In this paper, we are interested in a more challenging task of discriminating sounds produced by the same percussion instrument. Specifically, sounds from different drums cymbals types. Cymbals are known to have indefinite pitch, nonlinear and chaotic behavior. We also identify how the sound of a specific cymbal was produced (e.g., roll or choke movements performed by a drummer). We achieve an accuracy of 96.59% for cymbal type classification and 91.54% in a classification problem with 12 classes which represent the cymbal type and the manner or region that the cymbals are struck. Both results were obtained with Support Vector Machine algorithm using the Line Spectral Frequencies as audio descriptor. We believe that our results can be useful for a more detailed automatic drum transcription and for other related applications as well for audio professionals.

Data stream classification algorithms for nonstationary environments frequently assume the availability of class labels, instantly or with some lag after the classification. However, certain applications, mainly those related to sensors and robotics, involve high costs to obtain new labels during the classification phase. Such a scenario in which the actual labels of processed data are never available is called extreme verification latency. Extreme verification latency requires new classification methods capable of adapting to possible changes over time without external supervision. This paper presents a fast, simple, intuitive and accurate algorithm to classify nonstationary data streams in an extreme verification latency scenario, namely Stream Classification Algorithm Guided by Clustering – SCARGC. Our method consists of a clustering followed by a classification step applied repeatedly in a closed loop fashion. We show in several classification tasks evaluated in synthetic and real data that our method is faster and more accurate than the state-of-the-art.

In the last decade we have witnessed a huge increase of interest in data stream learning algorithms. A stream is an ordered sequence of data records. It is characterized by properties such as the potentially infinite and rapid flow of instances. However, a property that is common to various application domains and is frequently disregarded is the very high fluctuating data rates. In domains with fluctuating data rates, the events do not occur with a fixed frequency. This imposes an additional challenge for the classifiers since the next event can occur at any time after the previous one. Anytime classification provides a very convenient approach for fluctuating data rates. In summary, an anytime classifier can be interrupted at any time before its completion and still be able to provide an intermediate solution. The popular k-nearest neighbor (k-NN) classifier can be easily made anytime by introducing a ranking of the training examples. A classification is achieved by scanning the training examples according to this ranking. In this paper, we show how the current state-of-the-art k-NN anytime classifier can be made more accurate by introducing diversity in the training set ranking. Our results show that, with this simple modification, the performance of the anytime version of the k-NN algorithm is consistently improved for a large number of datasets.

Graph-based semi-supervised learning (SSL) algorithms perform well on a variety of domains, such as digit recognition and text classification, when the data lie on a low-dimensional manifold. However, it is surprising that these methods have not been effectively applied on time series classification tasks. In this paper, we provide a comprehensive empirical comparison of state-of-the-art graph-based SSL algorithms with respect to graph construction and parameter selection. Specifically, we focus in this paper on the problem of time series transductive classification on imbalanced data sets. Through a comprehensive analysis using recently proposed empirical evaluation models, we confirm some of the hypotheses raised on previous work and show that some of them may not hold in the time series domain. From our results, we suggest the use of the Gaussian Fields and Harmonic Functions algorithm with the mutual k-nearest neighbors graph weighted by the RBF kernel, setting k = 20 on general tasks of time series transductive classification on imbalanced data sets.

Time series are present in many pattern recognition applications related to medicine, biology, astronomy, economy, and others. In particular, the classification task has attracted much attention from a large number of researchers. In such a task, empirical researches has shown that the 1-Nearest Neighbor rule with a distance measure in time domain usually performs well in a variety of application domains. However, certain time series features are not evident in time domain. A classical example is the classification of sound, in which representative features are usually present in the frequency domain. For these applications, an alternative representation is necessary. In this work we investigate the use of recurrence plots as data representation for time series classification. This representation has well-defined visual texture patterns and their graphical nature exposes hidden patterns and structural changes in data. Therefore, we propose a method capable of extracting texture features from this graphical representation, and use those features to classify time series data. We use traditional methods such as Grey Level Co-occurrence Matrix and Local Binary Patterns, which have shown good results in texture classification. In a comprehensible experimental evaluation, we show that our method outperforms the state-of-the-art methods for time series classification.

Abstract This paper addresses the task of automatic extraction of definitions by thoroughly exploring an approach that solely relies on machine learning techniques, and by focusing on the issue of the imbalance of relevant datasets. We obtained a breakthrough in terms of the automatic extraction of definitions, by extensively and systematically experimenting with different sampling techniques and their combination, as well as a range of different types of classifiers. Performance consistently scored in the range of 0.95–0.99 of area under the receiver operating characteristics, with a notorious improvement between 17 and 22 percentage points regarding the baseline of 0.73–0.77, for datasets with different rates of imbalance. Thus, the present paper also represents a contribution to the seminal work in natural language processing that points toward the importance of exploring the research path of applying sampling techniques to mitigate the bias induced by highly imbalanced datasets, and thus greatly improving the performance of a large range of tools that rely on them.

There is a huge increase of interest for time series methods and techniques. Virtually every piece of information collected from human, natural, and biological processes is susceptible to changes over time, and the study of how these changes occur is a central issue in fully understanding such processes. Among all time series mining tasks, classification is likely to be the most prominent one. In time series classification there is a significant body of empirical research that indicates that k-nearest neighbor rule in the time domain is very effective. However, certain time series features are not easily identified in this domain and a change in representation may reveal some significant and unknown features. In this work, we propose the use of recurrence plots as representation domain for time series classification. Our approach measures the similarity between recurrence plots using Campana-Keogh (CK-1) distance, a Kolmogorov complexity-based distance that uses video compression algorithms to estimate image similarity. We show that recurrence plots allied to CK-1 distance lead to significant improvements in accuracy rates compared to Euclidean distance and Dynamic Time Warping in several data sets. Although recurrence plots cannot provide the best accuracy rates for all data sets, we demonstrate that we can predict ahead of time that our method will outperform the time representation with Euclidean and Dynamic Time Warping distances.

Throughout the history, insects have had an intimate relationship with humanity, both positive and negative. Insects are vectors of diseases that kill millions of people every year and, at the same time, insects pollinate most of the world's food production. Consequently, there is a demand for new devices able to control the populations of harmful insects while having a minimal impact on beneficial insects. In this paper, we present an intelligent trap that uses a laser sensor to selectively classify and catch insects. We perform an extensive evaluation of different feature sets from audio analysis and machine learning algorithms to construct accurate classifiers for the insect classification task. Support Vector Machines achieved the best results with a MFCC feature set, which consists of coefficients from frequencies scaled according to the human auditory system. We evaluate our classifiers in multiclass and binary class settings, and show that a binary class classifier that recognizes the mosquito species achieved almost perfect accuracy, assuring the applicability of the proposed intelligent trap.

Classification of time series data is an important problem with applications in virtually every scientific endeavor. The large research community working on time series classification has typically used the UCR Archive to test their algorithms. In this work we argue that the availability of this resource has isolated much of the research community from the following reality, labeled time series data is often very difficult to obtain. The obvious solution to this problem is the application of semi-supervised learning; however, as we shall show, direct applications of off-the-shelf semi-supervised learning algorithms do not typically work well for time series. In this work we explain why semi-supervised learning algorithms typically fail for time series problems, and we introduce a simple but very effective fix. We demonstrate our ideas on diverse real word problems.

In the last decade, class imbalance has attracted a huge amount of attention from researchers and practitioners. Class imbalance is ubiquitous in Machine Learning, Data Mining and Pattern Recognition applications; therefore, these research communities have responded to such interest with literally dozens of methods and techniques. Surprisingly, there are still many fundamental open-ended questions such as "Are all learning paradigms equally affected by class imbalance?", "What is the expected performance loss for different imbalance degrees?" and "How much of the performance losses can be recovered by the treatment methods?". In this paper, we propose a simple experimental design to assess the performance of class imbalance treatment methods. This experimental setup uses real data sets with artificially modified class distributions to evaluate classifiers in a wide range of class imbalance. We employ such experimental design in a large-scale experimental evaluation with twenty-two data sets and seven learning algorithms from different paradigms. Our results indicate that the expected performance loss, as a percentage of the performance obtained with the balanced distribution, is quite modest (below 5%) for the most balanced distributions up to 10% of minority examples. However, the loss tends to increase quickly for higher degrees of class imbalance, reaching 20% for 1% of minority class examples. Support Vector Machine is the classifier paradigm that is less affected by class imbalance, being almost insensitive to all but the most imbalanced distributions. Finally, we show that the sampling algorithms only partially recover the performance losses. On average, typically about 30\% or less of the performance that was lost due to class imbalance was recovered by random over-sampling and SMOTE.

Most time series data mining algorithms use similarity search as a core subroutine, and thus the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms. The difficulty of scaling search to large datasets largely explains why most academic work on time series data mining has plateaued at considering a few millions of time series objects, while much of industry and science sits on billions of time series objects waiting to be explored. In this work we show that by using a combination of four novel ideas we can search and mine truly massive time series for the first time. We demonstrate the following extremely unintuitive fact; in large datasets we can exactly search under DTW much more quickly than the current state-of-the-art Euclidean distance search algorithms. We demonstrate our work on the largest set of time series experiments ever attempted. In particular, the largest dataset we consider is larger than the combined size of all of the time series datasets considered in all data mining papers ever published. We show that our ideas allow us to solve higher-level time series data mining problem such as motif discovery and clustering at scales that would otherwise be untenable. In addition to mining massive datasets, we will show that our ideas also have implications for real-time monitoring of data streams, allowing us to handle much faster arrival rates and/or use cheaper and lower powered devices than are currently possible.

Given the ubiquity of time series data, the data mining community has spent significant time investigating the best time series similarity measure to use for various tasks and domains. After more than a decade of extensive efforts, there is increasing evidence that Dynamic Time Warping (DTW) is very difficult to beat. Given that, recent efforts have focused on making the intrinsically slow DTW algorithm faster. For the similarity-search task, an important subroutine in many data mining algorithms, significant progress has been made by replacing the vast majority of expensive DTW calculations with cheap-to-compute lower bound calculations. However, these lower bound based optimizations do not directly apply to clustering, and thus for some realistic problems, clustering with DTW can take days or weeks. In this work, we show that we can mitigate this untenable lethargy by casting DTW clustering as an anytime algorithm. At the heart of our algorithm is a novel data-adaptive approximation to DTW which can be quickly computed, and which produces approximations to DTW that are much better than the best currently known linear-time approximations. We demonstrate our ideas on real world problems showing that we can get virtually all the accuracy of a batch DTW clustering algorithm in a fraction of the time.

The history of humankind is intimately connected to insects. Insect borne diseases kill a million people and destroy tens of billions of dollars worth of crops annually. However, at the same time, beneficial insects pollinate the majority of crop species, and it has been estimated that approximately one third of all food consumed by humans is directly pollinated by bees alone. Given the importance of insects in human affairs, it is somewhat surprising that computer science has not had a larger impact in entomology. We believe that recent advances in sensor technology are beginning change this, and a new field of Computational Entomology will emerge. We will demonstrate an inexpensive sensor that allows us to capture data from flying insects, and the software that allows us to analyze the data. Moreover, we will distribute both the sensors and software for free, to parties willing to take part in a crowdsourcing project on insect classification.

The ubiquity of time series data across almost all human endeavors has produced a great interest in time series data mining in the last decade. While there is a plethora of classification algorithms that can be applied to time series, all of the current empirical evidence suggests that simple nearest neighbor classification is exceptionally difficult to beat. The choice of distance measure used by the nearest neighbor algorithm depends on the invariances required by the domain. For example, motion capture data typically requires invariance to warping. In this work we make a surprising claim. There is an invariance that the community has missed, complexity invariance. Intuitively, the problem is that in many domains the different classes may have different complexities, and pairs of complex objects, even those which subjectively may seem very similar to the human eye, tend to be further apart under current distance measures than pairs of simple objects. This fact introduces errors in nearest neighbor classification, where complex objects are incorrectly assigned to a simpler class. We introduce the first complexity-invariant distance measure for time series, and show that it generally produces significant improvements in classification accuracy. We further show that this improvement does not compromise efficiency, since we can lower bound the measure and use a modification of triangular inequality, thus making use of most existing indexing and data mining algorithms. We evaluate our ideas with the largest and most comprehensive set of time series classification experiments ever attempted, and show that complexity-invariant distance measures can produce improvements in accuracy in the vast majority of cases.

Predictive performance evaluation is a fundamental issue in design, development, and deployment of classification systems. As predictive performance evaluation is a multidimensional problem, single scalar summaries such as error rate, although quite convenient due to its simplicity, can seldom evaluate all the aspects that a complete and reliable evaluation must consider. Due to this, various graphical performance evaluation methods are increasingly drawing the attention of machine learning, data mining, and pattern recognition communities. The main advantage of these types of methods resides in their ability to depict the trade-offs between evaluation aspects in a multidimensional space rather than reducing these aspects to an arbitrarily chosen (and often biased) single scalar measure. Furthermore, to appropriately select a suitable graphical method for a given task, it is crucial to identify its strengths and weaknesses. This paper surveys various graphical methods often used for predictive performance evaluation. By presenting these methods in the same framework, we hope this paper may shed some light on deciding which methods are more suitable to use in different situations.

Each year, insect-borne diseases kill more than one million people, and harmful insects destroy tens of billions of dollars worth of crops and livestock. At the same time, beneficial insects pollinate three-quarters of all food consumed by humans. Given the extraordinary impact of insects on human life, it is somewhat surprising that machine learning has made very little impact on understanding (and hence, controlling) insects. In this work we discuss why this is the case, and argue that a confluence of facts make the time ripe for machine learning research to reach out to the entomological community and help them solve some important problems. As a concrete example, we show how we can solve an important classification problem in commercial entomology by leveraging off recent progress in shape, color and texture measures.

Most Machine Learning systems target into inducing classifiers with optimal coverage and precision measures. Although this constitutes a good approach for prediction, it might not provide good results when the user is more interested in description. In this case, the induced models should present other properties such as novelty, interestingness and so forth. In this paper we present a research work based in Multi-Objective Evolutionary Computing to construct individual knowledge rules targeting arbitrary user-defined criteria via objective quality measures such as precision, support, novelty etc. This paper also presents a comparison among multi-objective and ranking composition techniques. It is shown that multi-objective-based methods attain better results than ranking-based methods, both in terms of solution dominance and diversity of solutions in the Pareto front.

Most symbolic classifiers aim at building sets of rules with good coverage and precision. While this is suitable for most applications, they tend to neglect other desirable properties, such as the ability to induce novel knowledge or to show new points of view of well-established concepts. An approach to overcome these limitations involves using a multi-objective evolutionary algorithm to build knowledge rules with specific properties specified by the user. In this paper, we report a research work that combined evolutionary algorithms and ranking composition methods for multi-objective optimization. In this approach, candidate solutions are built, evaluated and ranked according to their performance in each individual objective. Then rankings are composed into a single ranking which reflects the candidate solutions' ability to solve the multi-objective problem considering all objectives simultaneously. We investigate the behavior of 5 ranking composition methods. These methods are compared and we conclude that all of the studied ranking composition methods provide good balance of objectives. Moreover, for the 11 datasets analyzed, we conclude condorcet is the only method which performs statistically better than other methods.