1234512
HOS-Miner: A System for Detecting Outlying Subspaces of High-dimensional Data
We identify a new and interesting high-dimensional outlier detection problem in this paper, that is, detecting the subspaces in which given data points are outliers. We call the subspaces in which a data point is an outlier as its Outlying Subspaces. In this paper, we will propose the prototype of a dynamic subspace search system, called HOS-Miner (HOS stands for High-dimensional Outlying Subspaces), that utilizes a sample-based learning process to effectively identify the outlying subspaces of a given point.
60677377
Towards outlier detection for high-dimensional data streams using projected outlier analysis strategy
Outlier detection is an important research problem in data mining that aims to discover useful abnormal and irregular patterns hidden in large data sets. Most existing outlier detection methods only deal with static data with relatively low dimensionality. Recently, outlier detection for high-dimensional stream data became a new emerging research problem. A key observation that motivates this research is that outliers in high-dimensional data are projected outliers, i.e., they are embedded in lower-dimensional subspaces. Detecting projected outliers from high-dimensional stream data is a very challenging task for several reasons. First, detecting projected outliers is difficult even for high-dimensional static data. The exhaustive search for the outlying subspaces where projected outliers are embedded is a NP problem. Second, the algorithms for handling data streams are constrained to take only one pass to process the streaming data with the conditions of space limitation and time criticality. The currently existing methods for outlier detection are found to be ineffective for detecting projected outliers in high-dimensional data streams. 
In this thesis, we present a new technique, called the Stream Project Outlier deTector (SPOT), which attempts to detect projected outliers in high-dimensional data streams. SPOT employs an innovative window-based time model in capturing dynamic statistics from stream data, and a novel data structure containing a set of top sparse subspaces to detect projected outliers effectively. SPOT also employs a multi-objective genetic algorithm as an effective search method for finding the outlying subspaces where most projected outliers are embedded. The experimental results demonstrate that SPOT is efficient and effective in detecting projected outliers for high-dimensional data streams. The main contribution of this thesis is that it provides a backbone in tackling the challenging problem of outlier detection for high-dimensional data streams. SPOT can facilitate the discovery of useful abnormal patterns and can be potentially applied to a variety of high demand applications, such as for sensor network data monitoring, online transaction protection, etc.
37278978
PC-Filter: A Robust Filtering Technique for Duplicate Record Detection in Large Databases
In this paper, we will propose PC-Filter (PC stands for Partitio n Comparison), a robust data filter for approximately duplicate record detection in large databases. PC-Filter distinguishes itself from all of existing methods by using the notion of partition in duplicate detection. It first sorts the whole database and splits the sorted database into a number of record partitions. The Partition Comparison Graph (PCG) is then constructed by performing fast partition pruning. Finally, duplicate records are effectively detected by using internal and external partition comparison based on PCG. Four properties, used as heuristics, have been devised to achieve a remarkable efficiency of the filter based on triangle inequity of record similarity. PC-Filter is insensitive to the key used to sort the database, and can achieve a very good recall level that is comparable to that of the pair-wise record comparison method but only with a complexity of O(N 4/3). Equipping existing detection methods with PC-Filter, we are able to well solve the ”Key Selection” problem, the ”Scope Specification” problem and the ”Low Recall” problem that the existing methods suffer from.
34332782
Generalized Semi-Infinite Optimization and its Application in Robotics' Path Planning Problem
815255
Detecting Projected Outliers in High-Dimensional Data Streams
In this paper, we study the problem of projected outlier detection in high dimensional data streams and propose a new technique, called Stream Projected Ouliter deTector (SPOT), to identify outliers embedded in subspaces. Sparse Subspace Template (SST), a set of subspaces obtained by unsupervised and/or supervised learning processes, is constructed in SPOT to detect projected outliers effectively. Multi-Objective Genetic Algorithm (MOGA) is employed as an effective search method for finding outlying subspaces from training data to construct SST. SST is able to carry out online self-evolution in the detection stage to cope with dynamics of data streams. The experimental results demonstrate the efficiency and effectiveness of SPOT in detecting outliers in high-dimensional data streams.
16517186
A Color Indexing Scheme Using Two-level Clustering Processing for Effective and Efficient Image Retrieval
[Abstract]: In this paper, we present a clustering-based color indexing scheme for effective amd efficient image retrieval, which is essentially an exploration on the application of clustering technique to image retrieval. In our approach, the color features are clustered automatically using a color clustering algorithm twice (called two-level clustering processing) and two color feature summarizations are obtained, e.g. Local Color Centriods (LCCs) and Global Color Centroids (GCCs). Based upon LCCs and GCCs, a three-level R-tree is bulit for indexing database images and performing effecitve and efficient image retrieval. The experiments show that this indexing scheme is effective and efficient in performing image retrieval.
15885752
Enhancing SQL with Set-Comparison Operators
An apparatus for turning up and down a spectator's seats includes a foot member which is turnably supported within a base frame fixedly mounted on the movable platform. A pair of Y-shaped lock links are supported turnable about a support shaft which extends throught the fore end thereof. The upper portions of the lock links rotatably support a locking and unlocking roller therebetween and this roller serves as a weight. On the other hand, the lower portions of the lock links are formed with a hook respectively. A locking angle is fixedly secured to both the side walls of the base frame at the position located behind foot member in such a manner that the hooks are engaged to the locking angle to firmly hold the foot member in the upright standing posture when the roller is lowered by turning movement. Engagement of the hooks to the locking angle can be released by abutment of the roller against the front nose on the upper movable platform during backward movement of the first-mentioned movable platform. The foot member has a shaft about which it is adapted to turn and the shaft has spring means mounted thereon on both the sides of the foot member to normally turn up the foot member toward the upright standing posture. The base frame is provided with stopper bolts adapted to inhibit the seat from turning backwardly as well as adjustment bolts adapted to inhibit it from turning forwardly.
17362173
A New Heuristic Reduct Algorithm Base on Rough Sets Theory
Real world data sets usually have many features, which increases the complexity of data mining task. Feature selection, as a preprocessing step to the data mining, has been shown very effective in reducing dimensionality, removing irrelevant data, increasing learning accuracy, and improving comprehensibility. To find the optimal feature subsets is the aim of feature selection. Rough sets theory provides a mathematical approach to find optimal feature subset, but this approach is time consuming. In this paper, we propose a novel heuristic algorithm based on rough sets theory to find out the feature subset. This algorithm employs appearing frequency of attribute as heuristic information. Experiment results show in most times our algorithm can find out optimal feature subset quickly and efficiently.
14662457
Framework for Performance Evaluation of Face, Text, and Vehicle Detection and Tracking in Video: Data, Metrics, and Protocol
Common benchmark data sets, standardized performance metrics, and baseline algorithms have demonstrated considerable impact on research and development in a variety of application domains. These resources provide both consumers and developers of technology with a common framework to objectively compare the performance of different algorithms and algorithmic improvements. In this paper, we present such a framework for evaluating object detection and tracking in video: specifically for face, text, and vehicle objects. This framework includes the source video data, ground-truth annotations (along with guidelines for annotation), performance metrics, evaluation protocols, and tools including scoring software and baseline algorithms. For each detection and tracking task and supported domain, we developed a 50-clip training set and a 50-clip test set. Each data clip is approximately 2.5 minutes long and has been completely spatially/temporally annotated at the I-frame level. Each task/domain, therefore, has an associated annotated corpus of approximately 450,000 frames. The scope of such annotation is unprecedented and was designed to begin to support the necessary quantities of data for robust machine learning approaches, as well as a statistically significant comparison of the performance of algorithms. The goal of this work was to systematically address the challenges of object detection and tracking through a common evaluation framework that permits a meaningful objective comparison of techniques, provides the research community with sufficient data for the exploration of automatic modeling techniques, encourages the incorporation of objective evaluation into the development process, and contributes useful lasting resources of a scale and magnitude that will prove to be extremely useful to the computer vision research community for years to come.
31872809
Clustering in Dynamic Spatial Databases
Efficient clustering in dynamic spatial databases is currently an open problem with many potential applications. Most traditional spatial clustering algorithms are inadequate because they do not have an efficient support for incremental clustering.In this paper, we propose DClust, a novel clustering technique for dynamic spatial databases. DClust is able to provide multi-resolution view of the clusters, generate arbitrary shapes clusters in the presence of noise, generate clusters that are insensitive to ordering of input data and support incremental clustering efficiently. DClust utilizes the density criterion that captures arbitrary cluster shapes and sizes to select a number of representative points, and builds the Minimum Spanning Tree (MST) of these representative points, called R-MST. After the initial clustering, a summary of the cluster structure is built. This summary enables quick localization of the effect of data updates on the current set of clusters. Our experimental results show that DClust outperforms existing spatial clustering methods such as DBSCAN, C2P, DENCLUE, Incremental DBSCAN and BIRCH in terms of clustering time and accuracy of clusters found.
1411838
3D Motion Segmentation from Straight-Line Optical Flow
We present a closed form solution to the problem of segmenting multiple 3D motion models from straight-line optical flow. We introduce the multibody line optical flow constraint(MLOFC), a polynomial equation relating motion models and line parameters. We show that the motion models can be obtained analytically as the derivative of the MLOFC at the corresponding line measurement, without knowing the motion model associated with that line. Experiments on real and synthetic sequences are also presented.