Outlier detection has recently become an important problem in many industrial and financial applications. Often, outliers have to be detected from data streams that continuously arrive from data sources. Incremental outlier detection algorithms, aimed at detecting outliers as soon as they appear in a database, have recently become emerging research field. In this paper, we develop an incremental version of connectivity-based outlier factor (COF) algorithm and discuss its computational complexity. The proposed incremental COF algorithm has equivalent detection performance as the iterated static COF algorithm (applied after insertion of each data record), with significant reduction in computational time. The paper provides theoretical and experimental evidence that the number of updates per such insertion/deletion does not depend on the total number of points in the data set, which makes algorithm viable for very large dynamic datasets. Finally, we also illustrate an application of the proposed algorithm on motion detection in video surveillance applications.
Estimation of probability density functions based on available data is important problem arising in various fields, such as telecommunications, machine learning, data mining, pattern recognition and computer vision. In this paper, we consider Kernel-based non-parametric density estimation methods and derive formulae for variable kernel density estimation using generalized, elliptic Gaussian kernels. The proposed technique is verified on simulated data.
1 June 2012 in Applied Mathematics and Computation
We describe application of adaptive filters on water level data. The original dataset is a time series of 57,127 measurements and consists of water levels measured at two locations along the St. Jones River, Delaware. After data cleansing to recover for missing data and reduce periodic components in the dataset, adaptive filters are applied to remove the influence of upstream water level on the levels measured downstream.
We consider the problem of covering hypersphere by a set of spherical hypercaps. This sort of problem has numerous practical applications such as error correcting codes and reverse k-nearest neighbor problem. Using the reduction of non degenerated concave quadratic programming (QP) problem, we demonstrate that spherical coverage verification is NP hard. We propose a recursive algorithm based on reducing the problem to several lower dimension subproblems. We test the performance of the proposed algorithm on a number of generated constellations. We demonstrate that the proposed algorithm, in spite of its exponential worst-case complexity, is applicable in practice. In contrast, our results indicate that spherical coverage verification using QP solvers that utilize heuristics, due to numerical instability, may produce false positives.