9200586
Scalable Inductive Learning on Partitioned Data
With the rapid advancement of information technology, scalability has become a necessity for learning algorithms to deal with large, real-world data repositories. In this paper, scalability is accomplished through a data reduction technique, which partitions a large data set into subsets, applies a learning algorithm on each subset sequentially or concurrently, and then integrates the learned results. Five strategies to achieve scalability (Rule-Example Conversion, Rule Weighting, Iteration, Good Rule Selection, and Data Dependent Rule Selection) are identified and seven corresponding scalable schemes are designed and developed. A substantial number of experiments have been performed to evaluate these schemes. Experimental results demonstrate that through data reduction some of our schemes can effectively generate accurate classifiers from weak classifiers generated from data subsets. Furthermore, our schemes require significantly less training time than that of generating a global classifier.
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.
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.
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.
14899560
Dealing with Predictive-but-Unpredictable Attributes in Noisy Data Sources
Attribute noise can affect classification learning. Previous work in handling attribute noise has focused on those predictable attributes that can be predicted by the class and other attributes. However, attributes can often be predictive but unpredictable. Being predictive, they are essential to classification learning and it is important to handle their noise. Being unpredictable, they require strategies different from those of predictable attributes. This paper presents a study on identifying, cleansing and measuring noise for predictive-but-unpredictable attributes. New strategies are accordingly proposed. Both theoretical analysis and empirical evidence suggest that these strategies are more effective and more efficient than previous alternatives.
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.
29079880
Graphs of Large Girth with Prescribed Partial Circular Colourings
Abstract.This paper completes the constructive proof of the following result: Suppose p/q≥2 is a rational number, A is a finite set and f1,f2,···,fn are mappings from A to {0,1,···,p−1}. Then for any integer g, there is a graph G=(V,E) of girth at least g with such that G has exactly n (p,q)-colourings (up to equivalence) g1,g2,···,gn, and each gi is an extension of fi. A probabilistic proof of this result was given in [8]. A constructive proof of the case p/q≥3 was given in [7].
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.
10041607
Comparison of Modularization Methods in Application to Different Biological Networks
Most biological networks have been proposed to possess modular organization, which increases the robustness, flexibility, and stability of networks. Many clustering methods have been used in mining biological data and partitioning complex networks into functional modules. Most of these methods require presetting the number of modules and therefore can potentially obtain biased results. The Markov clustering method (MCL) and the simulated annealing module-detection method (SA) eliminate this requirement and can objectively separate relatively dense subgraphs. In this paper, we compared these two module-detection methods for three types of biological data: protein family classification, microarray clustering, and modularity of metabolic networks. We found that these two methods show differential advantages for different biological networks. In the case of the gene network based on Affymetrix microarray spike data, MCL exactly identified the same number of groups and same contents in each group set by the spike data. In the case of the gene network derived from actual expression data, although neither of the two methods can perfectly recover the natural classification, MCL performs slightly better than SA. However, with increased random noise added to the gene expression values, SA generates better modular structures with higher modularity. Next we compared the modularization results of MCL and SA for protein family classification and found the modules detected by SA could not be well matched with the Structural Classification of Proteins (SCOP database), which suggests that MCL is ideally suited to the rapid and accurate detection of protein families. In addition, we used both methods to detect modules in the metabolic network of E. coli. MCL gives a trivial clustering, which generates biologically insignificant modules. In contrast, SA detects modules well corresponding to the KEGG functional classification. Moreover the modularity for several other metabolic networks detected by SA is also much higher than that by MCL. In summary, MCL is more suited to modularize relatively complete and definite data, such as a protein family network. In contrast, SA is less sensitive to noise such as experimental error or incomplete data and outperforms MCL when modularizing gene networks based on microarray data and large scale metabolic networks constructed from incomplete databases.
42953989
The game coloring number of pseudo partial k-trees
Abstract This paper introduces a new class of graphs: (a,b)-pseudo partial k-trees. In some sense, the parameters (a,b) measure a graph's deviation from being a partial k-tree. In particular, a (0,0)-pseudo partial k-tree is just a partial k-tree. We discuss the game coloring number (as well as the game chromatic number) of (a,b)-pseudo partial k-trees, and prove that the game coloring number of an (a,b)-pseudo partial k-tree is at most 3k+2a+b+2. In particular, the game coloring number of a partial k-tree is at most 3k+2. This reduces considerably the previous known upper bound for the game chromatic number of a partial k-tree. Then we describe another strategy for Alice for playing the game, which gives a better upper bound for the game coloring number of (a,b)-pseudo partial 2-trees. Namely, we prove that the game coloring number of an (a,b)-pseudo partial 2-tree is at most a+b+8. By using this result, we prove that the game coloring number of a graph embeddable on an orientable surface of genus g⩾1 is at most ⌊ 1 2 (3 1+48g +23)⌋. This is the first upper bound for the game coloring number of such graphs, and it also improves considerably the previous known upper bound for the game chromatic number of such graphs. Moreover, the strategy for Alice introduced in this paper for playing the game can be considered as a common generalization of the previous known strategies for playing the game on forests, interval graphs, outerplanar graphs and planar graphs.
15233730
Circulant Distant Two Labeling and Circular Chromatic Number
Let G be a graph and d,d 0 be positive integers, d 0 d. An m-(d,d 0 )-circular distance two labeling is a function f : V (G) ! {0,1,2,···,m 1} such that |f(u) f(v)|m d if u and v are adjacent; and |f(u) f(v)|m d 0 if u and v are distance two apart, where |x|m := min{|x|,m| x|}. The minimum m such that there exists an m-(d,d 0 )-circular labeling for G is called the d,d0-number of G and denoted by d,d 0(G). The d,d 0-numbers for trees can be obtained by a first-fit algorithm. In this article, we completely determine the d,1-numbers for cycles. In addition, we show connections between generalized circular distance labeling and circular chromatic number.