14571890
COBBLER: combining column and row enumeration for closed pattern discovery
The problem of mining frequent closed patterns has received considerable attention recently as it promises to have much less redundancy compared to discovering all frequent patterns. Existing algorithms can presently be separated into two groups, feature (column) enumeration and row enumeration. Feature enumeration algorithms like CHARM and CLOSET+ are efficient for datasets with small number of features and large number of rows since the number of feature combinations to be enumerated is small. Row enumeration algorithms like CARPENTER on the other hand are more suitable for datasets (eg. bioinformatics data) with large number of features and small number of rows. Both groups of algorithms, however, will encounter problem for datasets that have large number of rows and features. In this paper, we describe a new algorithm called COBBLER which can efficiently mine such datasets . COBBLER is designed to dynamically switch between feature enumeration and row enumeration depending on the data characteristic in the process of mining. As such, each portion of the dataset can be processed using the most suitable method, making the mining more efficient. Several experiments on real-life and synthetic datasets show that COBBLER is an order of magnitude better than previous closed pattern mining algorithms like CHARM, CLOSET+ and CARPENTER.
2768791
Finding representative set from massive data
In the information age, data is pervasive. In some applications, data explosion is a significant phenomenon. The massive data volume poses challenges to both human users and computers. In this project, we propose a new model for identifying representative set from a large database. A representative set is a special subset of the original dataset, which has three main characteristics: It is significantly smaller in size compared to the original dataset. It captures the most information from the original dataset compared to other subsets of the same size. It has low redundancy among the representatives it contains. We use information-theoretic measures such as mutual information and relative entropy to measure the representativeness of the representative set. We first design a greedy algorithm and then present a heuristic algorithm that delivers much better performance. We run experiments on two real datasets and evaluate the effectiveness of our representative set in terms of coverage and accuracy. The experiments show that our representative set attains expected characteristics and captures information more efficiently.
9042204
CRD: fast co-clustering on large datasets utilizing sampling-based matrix decomposition
The problem of simultaneously clustering columns and rows (co-clustering) arises in important applications, such as text data mining, microarray analysis, and recommendation system analysis. Compared with the classical clustering algorithms, co-clustering algorithms have been shown to be more effective in discovering hidden clustering structures in the data matrix. The complexity of previous co-clustering algorithms is usually O(m X n), where m and n are the numbers of rows and columns in the data matrix respectively. This limits their applicability to data matrices involving a large number of columns and rows. Moreover, some huge datasets can not be entirely held in main memory during co-clustering which violates the assumption made by the previous algorithms. In this paper, we propose a general framework for fast co-clustering large datasets, CRD. By utilizing recently developed sampling-based matrix decomposition methods, CRD achieves an execution time linear in m and n. Also, CRD does not require the whole data matrix be in the main memory. We conducted extensive experiments on both real and synthetic data. Compared with previous co-clustering algorithms, CRD achieves competitive accuracy but with much less computational cost.
108674
Sample Selection for Maximal Diversity
The problem of selecting a sample subset sufficient to preserve diversity arises in many applications. One example is in the design of recombinant inbred lines (RIL) for genetic association studies. In this context, genetic diversity is measured by how many alleles are retained in the resulting inbred strains. RIL panels that are derived from more than two parental strains, such as the collaborative cross (Churchill et al., 2004), present a particular challenge with regard to which of the many existing lab mouse strains should be included in the initial breeding funnel in order to maximize allele retention. A similar problem occurs in the study of customer reviews when selecting a subset of products with a maximal diversity in reviews. Diversity in this case implies the presence of a set of products having both positive and negative ranks for each customer. In this paper, we demonstrate that selecting an optimal diversity subset is an NP-complete problem via reduction to set cover. This reduction is sufficiently tight that greedy approximations to the set cover problem directly apply to maximizing diversity. We then suggest a slightly modified subset selection problem in which an initial greedy diversity solution is used to effectively prune an exhaustive search for all diversity subsets bounded from below by a specified coverage threshold. Extensive experiments on real datasets are performed to demonstrate the effectiveness and efficiency of our approach.
11841640
Accelerating Profile Queries in Elevation Maps
Elevation maps are a widely used spatial data representation in geographical information systems (GIS). Paths on elevation maps can be characterized by profiles, which describe relative elevation as a function of distance. In this research, we address the inverse of this mapping - given a profile, how to efficiently find paths that could have generated it. This is called the profile query problem. Profiles have a wide variety of uses that include registering tracking information, or even other maps, to a given map. We describe a probabilistic model to characterize the maximal likelihood that a point lying on a path matches the query profile. Propagation of such probabilities to neighboring points can effectively prune the search space. This model enables us to efficiently answer queries of arbitrary profiles with user-specified error tolerances. When compared to existing spatial index methods, our approach supports more flexible queries with orders of magnitude speedup.
765245
CARE: Finding Local Linear Correlations in High Dimensional Data
Finding latent patterns in high dimensional data is an important research problem with numerous applications. Existing approaches can be summarized into 3 categories: feature selection, feature transformation (or feature projection) and projected clustering. Being widely used in many applications, these methods aim to capture global patterns and are typically performed in the full feature space. In many emerging biomedical applications, however, scientists are interested in the local latent patterns held by feature subsets, which may be invisible via any global transformation. In this paper, we investigate the problem of finding local linear correlations in high dimensional data. Our goal is to find the latent pattern structures that may exist only in some subspaces. We formalize this problem as finding strongly correlated feature subsets which are supported by a large portion of the data points. Due to the combinatorial nature of the problem and lack of monotonicity of the correlation measurement, it is prohibitively expensive to exhaustively explore the whole search space. In our algorithm, CARE, we utilize spectrum properties and effective heuristic to prune the search space. Extensive experimental results show that our approach is effective in finding local linear correlations that may not be identified by existing methods.
16672435
Modeling and Learning Vague Event Durations for Temporal Reasoning
This paper reports on our recent work on modeling and automatically extracting vague, implicit event durations from text (Pan et al., 2006a, 2006b). It is a kind of commonsense knowledge that can have a substantial impact on temporal reasoning problems. We have also proposed a method of using normal distributions to model Judgments that are intervals on a scale and measure their interannotator agreement; this should extend from time to other kinds of vague but substantive information in text and commonsense reasoning.
16039054
Feature selection for ranking using boosted trees
Modern search engines have to be fast to satisfy users, so there are hard back-end latency requirements. The set of features useful for search ranking functions, though, continues to grow, making feature computation a latency bottleneck. As a result, not all available features can be used for ranking, and in fact, much of the time, only a small percentage of these features can be used. Thus, it is crucial to have a feature selection mechanism that can find a subset of features that both meets latency requirements and achieves high relevance. To this end, we explore different feature selection methods using boosted regression trees, including both greedy approaches (selecting the features with highest relative importance as computed by boosted trees; discounting importance by feature similarity and a randomized approach. We evaluate and compare these approaches using data from a commercial search engine. The experimental results show that the proposed randomized feature selection with feature-importance-based backward elimination outperforms greedy approaches and achieves a comparable relevance with 30 features to a full-feature model trained with 419 features and the same modeling parameters.
206963453
An improved rate control algorithm for H.264
This paper proposes a new algorithm for H.264 rate control, and aims at improving coding quality of high motion scenes. Firstly, the motion estimations using all the possible modes are performed, and the mode that produces the least mean absolute difference is used to estimate the quantization parameter. Secondly, a new motion complexity measure is defined to represent the amount of motion content between two consecutive frames, and is used to estimate the target bit. Experimental results show that our scheme can effectively improve video quality at scene changes and high motions, and reduce the sharp drops of PSNR as compared with the H.264 adopted rate control algorithm. Moreover, our scheme also achieves an average PSNR gain of 0.129 dB for the test sequences.
15720571
An adaptive rate control algorithm for video coding over personal digital assistants (PDA)
With the recent development of third-generation communication technologies, encoding live video using a PDA and sharing it among friends has become a reality. However, the embedded processor inside a PDA is still not powerful enough and there are two major hurdles to overcome: (1) video coding needs to meet the rigorous constraint of the available computation capacity of a PDA; (2) In a PDA the computing power allocated to video coding may vary drastically (in bursts). In this paper, a new adaptive rate control algorithm is proposed for video coding over a PDA. This adaptive rate control scheme takes into account the time constraint of a PDA, and its bit allocation depends not only on the available data bits, but more importantly, on the available coding time. Experimental results show that, compared to the existing rate control scheme, the new algorithm can always achieve the maximum frame rate, maximize the utilization of the available bandwidth and computing power, increase the average PSNR, and improve the subjective perceptual quality of the reconstructed video.
14993944
Problem difficulty analysis for particle swarm optimization: deception and modality
This paper studies the problem difficulty for a popular optimization method - particle swarm optimization (PSO), particularly for the PSO variant PSO-cf (PSO with constriction factor), and analyzes its predictive measures. Some previous measures and related issues about other optimizers, mainly including deception and modality, are checked for PSO. It is observed that deception is mainly the combination of three factors - the measure ratios of attraction basins, the relative distance of attractors and the relative difference of attractors' altitudes. Multimodality and multi-funnel are proved not to be the essential factors contributing to the problem difficulty for PSO. The counterexamples and comparative experiments in this paper can be taken as a reference for further researches on novel comprehensive predictive measures of problem difficulty for PSO.