15136742
Mining Complex Patterns across Sequences with Gap Requirements
The recurring appearance of sequential patterns, when confined by the predefined gap requirements, often implies strong temporal correlations or trends among pattern elements. In this paper, we study the problem of mining a set of gap constrained sequential patterns across multiple sequences. Given a set of sequences S1, S2,., SK constituting a single hypersequence S, we aim to find recurring patterns in S, say P, which may cross multiple sequences with all their matching characters in S bounded by the user specified gap constraints. Because of the combinatorial candidate explosion, traditional Apriori-based algorithms are computationally infeasible. Our research proposes a new mechanism to ensure pattern growing and pruning. When combining the pruning technique with our Gap Constrained Search (GCS) and map-based support prediction approaches, our method achieves a speed about 40 times faster than its other peers.
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.
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.
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.
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.
229019
A Machine Learning Approach to TCP Throughput Prediction
TCP throughput prediction is an important capability for networks where multiple paths exist between data senders and receivers. In this paper, we describe a new lightweight method for TCP throughput prediction. Our predictor uses Support Vector Regression (SVR); prediction is based on both prior file transfer history and measurements of simple path properties. We evaluate our predictor in a laboratory setting where ground truth can be measured with perfect accuracy. We report the performance of our predictor for oracular and practical measurements of path properties over a wide range of traffic conditions and transfer sizes. For bulk transfers in heavy traffic using oracular measurements, TCP throughput is predicted within 10% of the actual value 87% of the time, representing nearly a threefold improvement in accuracy over prior history-based methods. For practical measurements of path properties, predictions can be made within 10% of the actual value nearly 50% of the time, approximately a 60% improvement over history-based methods, and with much lower measurement traffic overhead. We implement our predictor in a tool called PathPerf, test it in the wide area, and show that PathPerf predicts TCP throughput accurately over diverse wide area paths.
34769702
JavaAHP: a web-based decision analysis tool for natural resource and environmental management
Natural resource and environmental management invariably involves multiple issues, multiple criteria and multiple stakeholders. A large amount of social, economic and environmental information needs to be linked to government policies, stakeholder values, public opinions and management goals. A systematic approach to decision analysis involved in natural resource and environmental management is required to improve the quality of the decision and justify the actions to be taken. The Analytical Hierarchy Process (AHP) provides a methodology for multi-criteria analysis and decision making. It allows critical examination of the underlying assumptions, consistency of the judgements, and facilitates the incorporation of qualitative and subjective considerations into quantitative factors for decision making. JavaAHP is a software tool, which implements the AHP. It uses the AHP methodology to model an environmental problem, evaluate relative desirability of alternatives, and organise the information and judgements used in decision making. JavaAHP is deployed on the World Wide Web (WWW) and can be accessed globally. It takes advantages of the WWW with wide availability, Web resource integration and cross-platform capabilities. This paper introduces the major features of JavaAHP and its potential applications in natural resource and environmental management.
205872736
Flatness tolerance evaluation: an approximate minimum zone solution
Abstract This paper is concerned with the problem of flatness tolerance evaluation. First, we introduce the concepts of width and inner radius of point sets, and establish the equivalence between the width of a point set and the inner radius of the convex hull of the self-difference of the set. On this basis, we present an algorithm for calculating the exact minimum zone tolerance of flatness. Second, we prove that an approximation of the inner radius of a convex set can be obtained from the inner radius of the set in fixed direction. On this basis, we present an algorithm for calculating the ‘almost exact’ minimum zone solution. This algorithm is implemented by solving a single linear programming problem, of which the computational complexity is O ( n ). Numerical examples are given to validate the proposed algorithms.
12029215
Multiuser Detection and Channel Estimation in MIMO OFDM Systems via Blind Source Separation
This paper proposes a blind multiuser detection and channel estimation method for multiple-input multiple-output (MIMO) orthogonal frequency-division multiplexing (OFDM) systems based on blind source separation (BSS). Using multiple antennas for transmission and reception the multiuser detection problem can be cast as a BSS problem of linear instantaneous mixtures. The proposed method uses BSS in each subcarrier to detect the user signals. The source order and scaling indeterminacies inherent to BSS methods are overcome by exploiting the cross correlation between the subcarriers introduced by convolutional encoding. Additionally, the method provides an estimate of the channels. It is shown that this method provides significant performance enhancement over previous work.
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.