11232317
Cost-constrained data acquisition for intelligent data preparation
Real-world data is noisy and can often suffer from corruptions or incomplete values that may impact the models created from the data. To build accurate predictive models, data acquisition is usually adopted to prepare the data and complete missing values. However, due to the significant cost of doing so and the inherent correlations in the data set, acquiring correct information for all instances is prohibitive and unnecessary. An interesting and important problem that arises here is to select what kinds of instances to complete so the model built from the processed data can receive the "maximum" performance improvement. This problem is complicated by the reality that the costs associated with the attributes are different, and fixing the missing values of some attributes is inherently more expensive than others. Therefore, the problem becomes that given a fixed budget, what kinds of instances should be selected for preparation, so that the learner built from the processed data set can maximize its performance? In this paper, we propose a solution for this problem, and the essential idea is to combine attribute costs and the relevance of each attribute to the target concept, so that the data acquisition can pay more attention to those attributes that are cheap in price but informative for classification. To this end, we will first introduce a unique economical factor (EF) that seamlessly integrates the cost and the importance (in terms of classification) of each attribute. Then, we will propose a cost-constrained data acquisition model, where active learning, missing value prediction, and impact-sensitive instance ranking are combined for effective data acquisition. Experimental results and comparative studies from real-world data sets demonstrate the effectiveness of our method.
3813357
Video data mining: semantic indexing and event detection from the association perspective
Advances in the media and entertainment industries, including streaming audio and digital TV, present new challenges for managing and accessing large audio-visual collections. Current content management systems support retrieval using low-level features, such as motion, color, and texture. However, low-level features often have little meaning for naive users, who much prefer to identify content using high-level semantics or concepts. This creates a gap between systems and their users that must be bridged for these systems to be used effectively. To this end, in this paper, we first present a knowledge-based video indexing and content management framework for domain specific videos (using basketball video as an example). We will provide a solution to explore video knowledge by mining associations from video data. The explicit definitions and evaluation measures (e.g., temporal support and confidence) for video associations are proposed by integrating the distinct feature of video data. Our approach uses video processing techniques to find visual and audio cues (e.g., court field, camera motion activities, and applause), introduces multilevel sequential association mining to explore associations among the audio and visual cues, classifies the associations by assigning each of them with a class label, and uses their appearances in the video to construct video indices. Our experimental results demonstrate the performance of the proposed approach.
16957901
Bridging Local and Global Data Cleansing: Identifying Class Noise in Large, Distributed Data Datasets
To cleanse mislabeled examples from a training dataset for efficient and effective induction, most existing approaches adopt a major set oriented scheme: the training dataset is separated into two parts (a major set and a minor set). The classifiers learned from the major set are used to identify noise in the minor set. The obvious drawbacks of such a scheme are twofold: (1) when the underlying data volume keeps growing, it would be either physically impossible or time consuming to load the major set into the memory for inductive learning; and (2) for multiple or distributed datasets, it can be either technically infeasible or factitiously forbidden to download data from other sites (for security or privacy reasons). Therefore, these approaches have severe limitations in conducting effective global data cleansing from large, distributed datasets.In this paper, we propose a solution to bridge the local and global analysis for noise cleansing. More specifically, the proposed effort tries to identify and eliminate mislabeled data items from large or distributed datasets through local analysis and global incorporation. For this purpose, we make use of distributed datasets or partition a large dataset into subsets, each of which is regarded as a local subset and is small enough to be processed by an induction algorithm at one time to construct a local model for noise identification. We construct good rules from each subset, and use the good rules to evaluate the whole dataset. For a given instance Ik, two error count variables are used to count the number of times it has been identified as noise by all data subsets. The instance with higher error values will have a higher probability of being a mislabeled example. Two threshold schemes, majority and non-objection, are used to identify and eliminate the noisy examples. Experimental results and comparative studies on both real-world and synthetic datasets are reported to evaluate the effectiveness and efficiency of the proposed approach.
5621999
Accelerated Kernel Feature Analysis
A fast algorithm, Accelerated Kernel Feature Analysis (AKFA), that discovers salient features evidenced in a sample of n unclassified patterns, is presented. Like earlier kernel-based feature selection algorithms, AKFA implicitly embeds each pattern into a Hilbert space, H, induced by a Mercer kernel. An \ell-dimensional linear subspace of H is iteratively constructed by maximizing a variance condition for the nonlinearly transformed sample. This linear subspace can then be used to define more efficient data representations and pattern classifiers. AKFA requires O(\elln2) operations, as compared to 0(n^3) for Sch¨olkof, Smola, and M¨uller’s Kernel Principal Component Analysis (KPCA), and O(\ell^2 n^2) for Smola, Mangasarian, and Sch¨olkopf’s Sparse Kernel Feature Analysis (SKFA). Numerical experiments show that AKFA can generate more concise feature representations than both KPCA and SKFA, and demonstrate that AKFA obtains similar classification performance as KPCA for a face recognition problem.
14119292
ACE: an aggressive classifier ensemble with error detection, correction and cleansing
Learning from noisy data is a challenging and reality issue for real-world data mining applications. Common practices include data cleansing, error detection and classifier ensembling. The essential goal is to reduce noise impacts and enhance the learners built from the noise corrupted data, so as to benefit further data mining procedures. In this paper, we present a novel framework that unifies error detection, correction and data cleansing to build an aggressive classifier ensemble for effective learning from noisy data. Being aggressive, the classifier ensemble is built from the data that has been preprocessed by the data cleansing and correcting techniques. Experimental comparisons will demonstrate that such an aggressive classifier ensemble is superior to the model built from the original noisy data, and is more reliable in enhancing the learning theory extracted from noisy data sources, in comparison with simple data correction or cleansing efforts
1977839
Effective classification of noisy data streams with attribute-oriented dynamic classifier selection
Recently, mining from data streams has become an important and challenging task for many real-world applications such as credit card fraud protection and sensor networking. One popular solution is to separate stream data into chunks, learn a base classifier from each chunk, and then integrate all base classifiers for effective classification. In this paper, we propose a new dynamic classifier selection (DCS) mechanism to integrate base classifiers for effective mining from data streams. The proposed algorithm dynamically selects a single “best” classifier to classify each test instance at run time. Our scheme uses statistical information from attribute values, and uses each attribute to partition the evaluation set into disjoint subsets, followed by a procedure that evaluates the classification accuracy of each base classifier on these subsets. Given a test instance, its attribute values determine the subsets that the similar instances in the evaluation set have constructed, and the classifier with the highest classification accuracy on those subsets is selected to classify the test instance. Experimental results and comparative studies demonstrate the efficiency and efficacy of our method. Such a DCS scheme appears to be promising in mining data streams with dramatic concept drifting or with a significant amount of noise, where the base classifiers are likely conflictive or have low confidence.
12394638
Planar Graphs with Circular Chromatic Numbers between 3 and 4
This paper proves that for every rational number r between 3 and 4, there exists a planar graph G whose circular chromatic number is equal to r. Combining this result with a recent result of Moser, we arrive at the conclusion that every rational number r between 2 and 4 is the circular chromatic number of a planar graph.
14278266
Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning
Graph-based methods for semi-supervised learning have recently been shown to be promising for combining labeled and unlabeled data in classification problems. However, inference for graph-based methods often does not scale well to very large data sets, since it requires inversion of a large matrix or solution of a large linear program. Moreover, such approaches are inherently transductive, giving predictions for only those points in the unlabeled set, and not for an arbitrary test point. In this paper a new approach is presented that preserves the strengths of graph-based semi-supervised learning while overcoming the limitations of scalability and non-inductive inference, through a combination of generative mixture models and discriminative regularization using the graph Laplacian. Experimental results show that this approach preserves the accuracy of purely graph-based transductive methods when the data has "manifold structure," and at the same time achieves inductive learning with significantly reduced computational cost.
7395446
Segmenting hands of arbitrary color
Hand segmentation is a prerequisite for many gesture recognition tasks. Color has been widely used for hand segmentation. However, many approaches rely on predefined skin color models. It is very difficult to predefine a color model in a mobile application where the light condition may change dramatically over time. We propose a novel statistical approach to hand segmentation based on Bayes decision theory. The proposed method requires no predefined skin color model. Instead it generates a hand color model and a background color model for a given image, and uses these models to classify each pixel in the image as either a hand pixel or a background pixel. Models are generated using a Gaussian mixture model with the restricted EM algorithm. Our method is capable of segmenting hands of arbitrary color in a complex scene. It performs well even when there is a significant overlap between hand and background colors, or when the user wears gloves. We show that the Bayes decision method is superior to a commonly used method by comparing their upper bound performance. Experimental results demonstrate the feasibility of the proposed method.
32861103
Multiplicativity of Oriented Cycles
We complete the characterization of those oriented cycles C which have the property that the class of digraphs not homomorphic to C is closed under taking the (categorical) product. This is related to Hedetniemi?s conjecture on the chromatic number of the product of undirected graphs. Our main tool is a result concerning the existence of homomorphisms between oriented paths which preserve the initial and terminal vertices. This tool is used to prove that for those cycles C we are interested in, any two oriented paths not homomorphic to C have a common preimage also not homomorphic to C. This "common preimage theorem" implies the multiplicativity of our cycles.
43203424
On sparse graphs with given colorings and homomorphisms
We prove that for every graph H and positive integers k and l there exists a graph G with girth at least l such that for all graphs H' with at most k vertices there exists a homomorphism G → H' if and only if there exists a homomorphism H → H'. This implies (for H = Kk) the classical result of Erdos and other generalizations (such as Sparse Incomparability Lemma). We refine the above statement to the 1-1 correspondence between the set of all homomorphisms G → H' and the set of all homomorphisms H → H'. This in turn yields the existence of sparse uniquely H-colorable graphs and, perhaps surprisingly, provides a characterization of the graphs H for which the analog of Muller's theorem holds for H-colorings.