Abstract

Regression algorithms are used for prediction (including forecasting of time-series data), inference, hypothesis testing, and modeling of causal relationships. Statistical approaches although popular, are are not generic in that they require the user to make an intelligent guess about the form of the regression equation. In this paper we present a new regression algorithm GEAR – Generic, Efficient, Accurate kNN-based Regression. In addition to this, GEAR is simple and outlier-resilient. These desirable features make GEAR a very attractive alternative to existing approaches. Our experimental study compares GEAR with fourteen other algorithms on five standard real datasets, and shows that GEAR is more accurate than all its competitors.

Abstract

This paper presents Perturbed Frequent Itemset based Classification Technique (PERFICT),a novel associative classification approach based on perturbed frequent itemsets. Most of the existing associative classifiers work well on transactional data where each record contains a set of boolean items.They are not very effective in general for relational data that typically contains real valued attributes.In PERFICT, we handle real attributes by treating items as (attribute,value) pairs, where the value is not the original one, but is perturbed by a small amount and is a range based value. We also propose our own similarity measure which captures the nature of real valued attributes and provide effective weights for the itemsets. The probabilistic contributions of different itemsets is taken into considerations during classification. Some of the applications where such a technique is useful are in signal classification, medical diagnosis and handwriting recognition. Experiments conducted on the UCI Repository datasets show that PERFICT is highly competitive in terms of accuracy in comparison with popular associative classification methods.

Abstract

Uncertainty is inherently present in many real-world domains like images. Analyses of such uncertain data using traditional certain-data-oriented techniques do not achieve best possible accuracy. UACI introduces the concept of representing images in the form of a probabilistic or uncertain model using interest points in images. This model is an uncertain-data-based adaptation of Bag of Words, with each image not only represented by the visual words that it contains, but also their respective probabilities of occurrence in the image. UACI uses an Associative Classification approach to leverage latent frequent patterns in images for the identification of object classes. Unlike most image classifiers, which rely on positive and negative class sets (generally very vague) for training, UACI uses only positive class images for training. We empirically compare UACI with three other state-of-the-art image classifiers, and show that UACI performs much better than the other classifying approaches.

Abstract

We describe improved mechanisms to accurately clas-sify days when news for topics receive unexpectedly high amount of coverage. We further investigate the factors which influence this classification using ‘Pres-idential Elections’ as the topic of interest. This help sin bringing out useful trends and relations between days with hot topics by varying variables like history window size,van-ratio etc. We also propose a statisti-cal scheme to approximate major events related to the topic. We then try to approximate the chain of event srelated to the major events. This can support a news alert service and also serve the purpose of automati-cally tracking news which follow up major events.

Abstract

In this paper we consider the problem of extracting the spe-cial properties of any given record in a dataset. We are interested in determining what makes a given record unique or different from the ma-jority of the records in a dataset. In the real world, records typically represent objects or people and it is often worthwhile to know what spe-cial properties are present in each object or person, so that we can make the best use of them. This problem has not been considered earlier inthe research literature. We approach this problem using ideas from clus-tering, attribute oriented induction (AOI) and frequent itemset mining.Most of the time consuming work is done in a preprocessing stage and the online computation of the uniqueness of a given record is instantaneous

Abstract

The problem of search and retrieval of images using relevance feedback has attracted tremendous attention in recent years from the research community. A real-world-deployable interactive image retrieval system must (1) be accurate, (2) require minimal user-interaction, (3) be efficient, (4) be scalable to large collections (millions) of images, and (5) support multi-user sessions. For good accuracy, we need effective methods for learning the relevance of image features based on user feedback, both within a user-session and across sessions. Efficiency and scalability require a good index structure for retrieving results. The index structure must allow for the relevance of image features to continually change with fresh queries and user-feedback. The state-of-the-art methods available today each address only a subset of these issues. In this paper, we build a complete system FISH - Fast Image Search in Huge databases. In FISH, we integrate selected techniques available in the literature, while adding a few of our own. We perform extensive experiments on real datasets to demonstrate the accuracy, efficiency and scalability of FISH. Our results show that the system can easily scale to millions of images while maintaining interactive response time.

Abstract

An important problem in biological data analysis is to pre-dict the family of a newly discovered sequence like a pro-tein or DNA sequence, using the collection of available se-quences. In this paper we tackle this problem and presentREBMEC, a Repeat Based Maximum Entropy Classifier of biological sequences. Maximum entropy models are known to be theoretically robust and yield high accuracy,but are slow. This makes them useful as benchmarks to evaluate other classifiers. Specifically, REBMEC is based on the classical Generalized Iterative Scaling (GIS) al-gorithm and incorporates repeated occurrences of subse-quences within each sequence. REBMEC uses maximal frequent subsequences as features but can support other types of features as well. Our extensive experiments on two collections of protein families show that REBMEC performs as well as existing state-of-the-art probabilistic classifiers for biological sequences without using domain-specific background knowledge such as multiple align-ment, data transformation and complex feature extraction methods. The design of REBMEC is based on genericideas that can apply to other domains where data is orga-nized as collections of sequences.

Abstract

In this paper, we present RBNBC, a Repeat Based Naive Bayes Classifier of bio-sequences that uses maximal fre-quent subsequences as features. RBNBC’s design is based on generic ideas that can apply to other domains where the data is organized as collections of sequences. Specifically,RBNBC uses a novel formulation of Naive Bayes that incor-porates repeated occurrences of subsequences within each sequence. Our extensive experiments on two collections of protein families show that it performs as well as existing state-of-the-art probabilistic classifiers for bio-sequences.This is surprising as it is a pure data mining based generic classifier that does not require domain-specific background knowledge. We note that domain-specific ideas could fur-ther increase its performance.

Abstract

In this paper, we consider the problem of finding the k most similar objects given a query object, in large multimedia datasets. We focus on scenarios where the similarity measure itself is not fixed, but is continuously being refined with user feedback. Conventional database techniques for efficient similarity search are not effective in this environment as they take a specific similarity/distance measure as input and build index structures tuned for that measure. Our approach works effectively in this environment as validated by the experimental study where we evaluate it over a wide range of datasets. The experiments show it to be efficient and scalable. In fact, on all our datasets, the response times were within a few seconds, making our approach suitable for interactive applications.

Abstract

Joins on set-valued attributes (set joins) have numerous database applications. In this paper we propose PRETTI (PREfix Tree based seT joIn) – a suite of set join algorithms for containment, overlap and equality join predicates.Our algorithms use prefix trees and inverted indices. These structures are constructed on-the-fly if they are not already precomputed. This feature makes ouralgorithms usable for relations without indices and when joining intermediate results during join queries with more than two relations. Another feature of ouralgorithms is that results are output continuously during their execution and notjust at the end. Experiments on real life datasets show that the total executiontime of our algorithms is significantly less than that of previous approaches, even when the indices required by our algorithms are not precomputed.