A new strategy for Dimensionality Reduction with the aim of providing reduced set with both original and combinations of features is studied. For this purpose, a framework called Minimum Projection error and Minimum Redundancy (MPeMR) to generate orthogonal compound (both original and combinations) features by minimizing both projection error and redundancy among them is proposed. An iterative approximation method under the proposed framework is also presented. Using different measures for projection error, redundancy and representative feature selection, three supervised and three unsupervised methods are considered. Experimental results are compared with both state-of-the-art feature selection and extraction methods, in both supervised and unsupervised cases, and proposed CFG methods outperform these methods. In each stage of the proposed approximation method, pairs of features are considered i.e., NPe is calculated based on two features and removal of redundancy is also based on two features. Instead of (2, 2), one could have considered (2, 3), or (3, 2) or any other such combination of features. Further research is focused along this direction.

Dimensionality reduction is an essential pre-processing technique in many of the data analysis tasks. Popular approaches for dimensionality reduction are Feature Selection (FS) and Feature Extraction (FE). Till now, these approaches are often studied separately or independently so that the final result contains either original or transformed features. In our work, we propose to bridge these two approaches with the aim of finding reduced feature set to contain both kinds (original as well as transformed) of features. A new framework, called Minimum Projection error Minimum Redundancy (MPeMR), is introduced to obtain this result while maintaining orthogonality property among selected original and linear combinations of features. A unified iterative algorithm, for both supervised and unsupervised cases, is also developed under this framework. For each case, the performance of the proposed algorithm is successfully compared with the state-of-the-art methods on real-life data sets.

Detection of normal and anomalous events from sensor signal is a key necessity in today's smart world. Here, we propose a novel mechanism to classify normal and anomalous phenomena by using self-learning of signal, i.e., by discovering its pattern. This is the first step in the long drawn out analysis of signals. We demonstrate a prototype of our proposed method by using a real field quasi-periodic photoplethysmogram (PPG) signal with (or without) motion artifacts, which has an immense impact on cardiac health monitoring, stress, blood pressure, and SPO2 measurement. We have achieved more than 90% accuracy to detect anomalous phenomena in the signal.

The similarity based decision rule computes the similarity between a new test document and the existing documents of the training set that belong to various categories. The new document is grouped to a particular category in which it has maximum number of similar documents. A document similarity ba sed supervised decision rule for text categorization is proposed in this article. The similarity measure determine the similarity between two documents by finding their distances with all the documents of training set and it can explicitly identify two dissimilar documents. The decision rule assigns a test document to the best one among the competing categories, if the best category beats the next competing category by a previously fixed margin. Thus the proposed rule enhances the certainty of the decision. The salient feature of the decision rule is that, it never assigns a document arbitrarily to a category when the decision is not so certain. The performance of the proposed decision rule for text categorization is compared with some well known classification techniques e.g., k-nearest neighbor decision rule, support vector machine, naive bayes etc. using various TREC and Reuter corpora. The empirical results have shown that the proposed method performs significantly better than the other classifiers for text categorization.

The paper addresses the problem of finding top k influential nodes in large scale directed social networks. We propose two new centrality measures, Diffusion Degree for independent cascade model of information diffusion and Maximum Influence Degree. Unlike other existing centrality measures, diffusion degree considers neighbors' contributions in addition to the degree of a node. The measure also works flawlessly with non uniform propagation probability distributions. On the other hand, Maximum Influence Degree provides the maximum theoretically possible influence (Upper Bound) for a node. Extensive experiments are performed with five different real life large scale directed social networks. With independent cascade model, we perform experiments for both uniform and non uniform propagation probabilities. We use Diffusion Degree Heuristic (DiDH) and Maximum Influence Degree Heuristic (MIDH), to find the top k influential individuals. k seeds obtained through these for both the setups show superior influence compared to the seeds obtained by high degree heuristics, degree discount heuristics, different variants of set covering greedy algorithms and Prefix excluding Maximum Influence Arborescence (PMIA) algorithm. The superiority of the proposed method is also found to be statistically significant as per T-test.

In an extension of previous work, here we introduce a second-order optimization method for determining optimal paths from the substrate to a target product of a metabolic network, through which the amount of the target is maximum. An objective function for the said purpose, along with certain linear constraints, is considered and minimized. The basis vectors spanning the null space of the stoichiometric matrix, depicting the metabolic network, are computed, and their convex combinations satisfying the constraints are considered as flux vectors. A set of other constraints, incorporating weighting coefficients corresponding to the enzymes in the pathway, are considered. These weighting coefficients appear in the objective function to be minimized. During minimization, the values of these weighting coefficients are estimated and learned. These values, on minimization, represent an optimal pathway, depicting optimal enzyme concentrations, leading to overproduction of the target. The results on various networks demonstrate the usefulness of the methodology in the domain of metabolic engineering. A comparison with the standard gradient descent and the extreme pathway analysis technique is also performed. Unlike the gradient descent method, the present method, being independent of the learning parameter, exhibits improved results.

Genetic Algorithm (GA) has now become one of the leading mechanisms in providing solution to complex optimization problems. Although widely used, there are very few theoretical guidelines for determining when to stop the algorithm. This article establishes theoretically that the variance of the best fitness values obtained in the iterations can be considered as a measure to decide the termination criterion of a GA with elitist model (EGA). The criterion automatically takes into account the inherent characteristics of the objective function. Implementation issues of the proposed stopping criterion are explained. Its difference with some other stopping criteria is also critically analyzed.

This paper discusses the applications of rough ensemble classifier [27] in two emerging problems of web mining, the categorization of web services and the topic specific web crawling. Both applications, discussed here, consist of two major steps: (1)

We have made a case here for utilizing tensor framework for hypertext mining. Tensor is a generalization of vector and tensor framework discussed here is a generalization of vector space model which is widely used in the information retrieval and web mining literature. Most hypertext documents have an inherent internal tag structure and external link structure that render the desirable use of multidimensional representations such as those offered by tensor objects. We have focused on the advantages of Tensor Space Model, in which documents are represented using sixth-order tensors. We have exploited the local-structure and neighborhood recommendation encapsulated by the proposed representation. We have defined a similarity measure for tensor objects corresponding to hypertext documents, and evaluated the proposed measure for mining tasks. The superior performance of the proposed methodology for clustering and classification tasks of hypertext documents have been demonstrated here. The experiment using different types of similarity measure in the different components of hypertext documents provides the main advantage of the proposed model. It has been shown theoretically that, the computational complexity of an algorithm performing on tensor framework using tensor similarity measure as distance is at most the computational complexity of the same algorithmperforming on vector space model using vector similarity measure as distance.

In the present article, we introduce a new method for identification of metabolic pathways in constraint based models that consider enzyme and substrate concentrations. It generates data on reaction fluxes based on biomass conservation constraint and then a set of constraints is formulated incorporating weighting coefficients corresponding to concentration of enzymes catalyzing reactions in the pathway. Finally, the rate of yield of the target metabolite, starting with a given substrate, is maximized in order to identify an optimal pathway through these weighting coefficients. In an attempt to solve this problem, we have developed a learning technique that optimizes a given objective function to find the optimal pathways. Finally, we propose a modification of the Newton Raphson method and incorporate it to our proposed methodology, which yields more relevant results from the perspective of biology.

The problem of object recognition has been considered here. Color descriptions from distinct regions covering multiple segments are considered for object representation. Distinct multicolored regions are detected using edge maps and clustering. Performance of the proposed methodologies has been evaluated on three data sets and the results are found to be better than existing methods when a small number of training views is considered.

Edge detection is a useful task in low-level image processing. The efficiency of many image processing and computer vision tasks depends on the perfection of detecting meaningful edges. To get a meaningful edge, thresholding is almost inevitable in any edge detection algorithm. Many algorithms reported in the literature adopt ad hoc schemes for this purpose. These algorithms require the threshold values to be supplied and tuned by the user. There are many high-level tasks in computer vision which are to be performed without human intervention. Thus, there is a need to develop a scheme where a single set of threshold values would give acceptable results for many color images. In this paper, an attempt has been made to devise such an algorithm. Statistical variability of partial derivatives at each pixel is used to obtain standardized edge magnitude and is thresholded using two threshold values. The advantage of standardization is evident from the results obtained.

Density estimates based on k-nearest neighbors have useful applications in nonparametric discriminant analysis. In classification problems, optimal values of k are usually estimated by minimizing the cross-validated misclassification rates. However, these cross-validation techniques allow only one value of k for each population density estimate, while in a classification problem, the optimum value of k for a class may also depend on its competing population densities. Further, it is computationally difficult to minimize the cross-validated error rate when there are several competing populations. Moreover, in addition to depending on the entire training data set, a good choice of k should also depend on the specific observation to be classified. Therefore, instead of using a single value of k for each population density estimate, it is more useful in practice to consider the results for multiple values of k to arrive at the final decision. This paper presents one such approach along with a graphical device, which gives more information about classification results for various choices of k and the related statistical uncertainties present there. The utility of this proposed methodology has been illustrated using some benchmark data sets.

Nearest neighbor classification is one of the simplest and most popular methods for statistical pattern recognition. A major issue in k-nearest neighbor classification is how to find an optimal value of the neighborhood parameter k. In practice, this value is generally estimated by the method of cross-validation. However, the ideal value of k in a classification problem not only depends on the entire data set, but also on the specific observation to be classified. Instead of using any single value of k, this paper studies results for a finite sequence of classifiers indexed by k. Along with the usual posterior probability estimates, a new measure, called the Bayesian measure of strength, is proposed and investigated in this paper as a measure of evidence for different classes. The results of these classifiers and their corresponding estimated misclassification probabilities are visually displayed using shaded strips. These plots provide an effective visualization of the evidence in favor of different classes when a given data point is to be classified. We also propose a simple weighted averaging technique that aggregates the results of different nearest neighbor classifiers to arrive at the final decision. Based on the analysis of several benchmark data sets, the proposed method is found to be better than using a single value of k.

A new combinatorial characterization of a gray-tone image called Euler Vector is proposed. The Euler number of a binary image is a well-known topological feature, which remains invariant under translation, rotation, scaling, and rubber-sheet transformation of the image. The Euler vector comprises a 4-tuple, where each element is an integer representing the Euler number of the partial binary image formed by the gray-code representation of the four most significant bit planes of the gray-tone image. Computation of Euler vector requires only integer and Boolean operations. The Euler vector is experimentally observed to be robust against noise and compression. For efficient image indexing, storage and retrieval from an image database using this vector, a bucket searching technique based on a simple modification of Kd-tree, is employed successfully. The Euler vector can also be used to perform an efficient four-dimensional range query. The set of retrieved images are finally ranked on the basis of Mahalanobis distance measure. Experiments are performed on the COIL database and results are reported. The retrieval success can be improved significantly by augmentiong the Euler vector by a few additional simple shape features. Since Euler vector can be computed very fast, the proposed technique is likely to find many applications to content-based image retrieval.

The paper describes a probabilistic active learning strategy for support vector machine (SVM) design in large data applications. The learning strategy is motivated by the statistical query model. While most existing methods of active SVM learning query for points based on their proximity to the current separating hyperplane, the proposed method queries for a set of points according to a distribution as determined by the current separating hyperplane and a newly defined concept of an adaptive confidence factor. This enables the algorithm to have more robust and efficient learning capabilities. The confidence factor is estimated from local information using the k nearest neighbor principle. The effectiveness of the method is demonstrated on real-life data sets both in terms of generalization performance, query complexity, and training time.

Many edge detectors are available in image processing literature where the choices of input parameters are to be made by the user. Most of the time, such choices are made on an ad-hoc basis. In this article, an edge detector is proposed where thresholding is performed using statistical principles. Local standardization of thresholds for each individual pixel (local thresholding), which depends upon the statistical variability of the gradient vector at that pixel, is done. Such a standardized statistic based on the gradient vector at each pixel is used to determine the eligibility of the pixel to be an edge pixel. The results obtained from the proposed method are found to be comparable to those from many well-known edge detectors. However, the values of the input parameters providing the appreciable results in the proposed detector are found to be more stable than other edge detectors and possess statistical interpretation.

PageRank is primarily based on link structure analysis. Recently, it has been shown that content information can be utilized to improve link analysis. We propose a novel algorithm that harnesses the information contained in the history of a surfer to determine the topic of interest on a given page. As the history is unavailable until query time, we guess it probabilistically so that the operations can be performed offline. This leads to a better Web page categorization and, thereby, to a better ranking of Web pages.

The first step in many techniques for processing intensity and saturation in color images keeping hue unaltered is the transformation of the image data from RGB space to other color spaces such as LHS, HSI, YIQ, HSV, etc. Transforming from one space to another and processing in these spaces usually generate a gamut problem, i.e., the values of the variables may not be in their respective intervals. We study enhancement techniques for color images theoretically in a generalized setup. A principle is suggested to make the transformations gamut-problem free. Using the same principle, a class of hue-preserving, contrast-enhancing transformations is proposed; they generalize existing grey scale contrast intensification techniques to color images. These transformations are also seen to bypass the above mentioned color coordinate transformations for image enhancement. The developed principle is used to generalize the histogram equalization scheme for grey scale images to color images.

A combinatorial characterization of a gray-tone image called Euler vector is discussed. The Euler vector comprises a 4-tuple, where each element is an integer representing the Euler number of the partial binary image formed by the four most significant bit planes of the gray-tone image. The vector is topologically invariant and can be used for image indexing and retrieval. The Euler vector for all the images in the database can be arranged using any multidimensional data structure. For retrieval, a query range is to be defined around the query image vector. We use a simple statistical technique to specify the query range. Next, we propose a modification in the Kd-Tree construction to build a simple hybrid tree that supports efficient adaptive clustering and indexing. The same data structure is used for clustering and indexing.

In this article, we describe an unsupervised feature selection algorithm suitable for data sets, large in both dimension and size. The method is based on measuring similarity between features whereby redundancy therein is removed. This does not need any search and, therefore, is fast. A new feature similarity measure, called maximum information compression index, is introduced. The algorithm is generic in nature and has the capability of multiscale representation of data sets. The superiority of the algorithm, in terms of speed and performance, is established extensively over various real-life data sets of different sizes and dimensions. It is also demonstrated how redundancy and information loss in feature selection can be quantified with an entropy measure.

A problem gaining interest in pattern recognition applied to data mining is that of selecting a small representative subset from a very large data set. In this article, a nonparametric data reduction scheme is suggested. It attempts to represent the density underlying the data. The algorithm selects representative points in a multiscale fashion which is novel from existing density-based approaches. The accuracy of representation by the condensed set is measured in terms of the error in density estimates of the original and reduced sets. Experimental studies on several real life data sets show that the multiscale approach is superior to several related condensation methods both in terms of condensation ratio and estimation error. The condensed set obtained was also experimentally shown to be effective for some important data mining tasks like classification, clustering, and rule generation on large data sets. Moreover, it is empirically found that the algorithm is efficient in terms of sample complexity.

The Euler number is a fundamental topological feature of an image, which remains invariant under translation, rotation, scaling, and rubber-sheet transformation of the image. A novel algorithm for computing the Euler number of a binary image is proposed which is based on the properties of runs of 0's and 1's present in the pixel matrix. The algorithm outperforms significantly the existing techniques in terms of both the number of pixel accesses and CPU time. It can be easily parallelized, and a simple on-chip implementation is reported here. Results on a database consisting of 1039 logo images reveal that the Euler number has a strong discriminatory power, and hence can be used for efficient database searching or matching of binary images. The proposed algorithm is very fast and easy to implement, and has potential of wide applicability in image processing.

An algorithm for data condensation using support vector machines (SVM) is presented. The algorithm extracts data points lying close to the class boundaries, which form a much reduced but critical set for classification. The problem of large memory requirements for training SVM in batch mode is circumvented by adopting an active incremental learning algorithm. The learning strategy is motivated from the condensed nearest neighbor classification technique. Experimental results presented show that such active incremental learning enjoy superiority in terms of computation time and condensation ratio, over related methods.

Constructing a model for data in R/sup 2/ is a common problem in many scientific fields, including pattern recognition, computer vision, and applied mathematics. Often little is known about the process which generated the data or its statistical properties. For example, in fitting a piecewise linear model, the number of pieces, as well as the knot locations, may be unknown. Hence, the method used to build the statistical model should have few assumptions, yet, still provide a model that is optimal in some sense. Such methods can be designed through the use of genetic algorithms. We examine the use of genetic algorithms to fit piecewise linear functions to data in R/sup 2/. The number of pieces, the location of the knots, and the underlying distribution of the data are assumed to be unknown. We discuss existing methods which attempt to solve this problem and introduce a new method which employs genetic algorithms to optimize the number and location of the pieces. Experimental results are presented which demonstrate the performance of our method and compare it to the performance of several existing methods, We conclude that our method represents a valuable tool for fitting both robust and nonrobust piecewise linear functions.

A method for pattern classification using genetic algorithms (GAs) has been recently described in Pal, Bandyopadhyay and Murthy (1998), where the class boundaries of a data set are approximated by a fixed number H of hyperplanes. As a consequence of fixing H a priori, the classifier suffered from the limitation of overfitting (or underfitting) the training data with an associated loss of its generalization capability. In this paper, we propose a scheme for evolving the value of H automatically using the concept of variable length strings/chromosomes. The crossover and mutation operators are newly defined in order to handle variable string lengths. The fitness function ensures primarily the minimization of the number of misclassified samples, and also the reduction of the number of hyperplanes. Based on an analogy between the classification principles of the genetic classifier and multilayer perceptron (with hard limiting neurons), a method for automatically determining the architecture and the connection weights of the latter is described.

The technique of image compression using Iterative Function System (IFS) is known as fractal image compression. An extension of IFS theory is called as Partitioned or local Iterative Function System (PIFS) for coding the gray level images. The theory

In this article, the concept of e-optimal stopping time of a genetic algorithm with elitist model (EGA) has been introduced. The probability of performing mutation plays an important role in the computation of the ε-optimal stopping times. Two approa

A new method for fractal image compression is proposed using genetic algorithm (GA) with an elitist model. The self transformation property of images is assumed and exploited in the fractal image compression technique. The technique described utilizes the GA, which greatly decreases the search space for finding the self similarities in the given image. This article presents theory, implementation, and an analytical study of the proposed method along with a simple classification scheme. A comparison with other fractal-based image compression methods is also reported.

A method is described for finding decision boundaries, approximated by piecewise linear segments, for classifying patterns in R(N),N>/=2, using an elitist model of genetic algorithms. It involves generation and placement of a set of hyperplanes (represented by strings) in the feature space that yields minimum misclassification. A scheme for the automatic deletion of redundant hyperplanes is also developed in case the algorithm starts with an initial conservative estimate of the number of hyperplanes required for modeling the decision boundary. The effectiveness of the classification methodology, along with the generalization ability of the decision boundary, is demonstrated for different parameter values on both artificial data and real life data sets having nonlinear/overlapping class boundaries. Results are compared extensively with those of the Bayes classifier, k-NN rule and multilayer perceptron.

Merits of genetic algorithms (GAs), an efficient evolutionary searching paradigm, are utilized for pattern classification in /spl Rfr//sup N/ by fitting hyperplanes to model the decision boundaries in the feature space. Theoretical analysis establishes that as the size of the training set (n) goes towards infinity, the error probability and the decision boundary of the GA based classifier will approach those of Bayes (optimum) classifier.

In this article, the genetic algorithm with elitist model (EGA) is modeled as a finite state Markov chain. A state in the Markov chain denotes a population together with a potential string. Proof for the convergence of an EGA to the best chromosome (string), among all possible chromosomes, is provided here. Mutation operation has been found to be essential for convergence. It has been shown that an EGA converges to the global optimal solution with any choice of initial population.

The present work describes a method of analyzing Indian Remote Sensing (IRS) satellite imagery for detecting various man-made objects, namely, roads, bridges, airports, seaports, city area and town-ship/industrial areas. A multivalued recognition system has initially been used to classify the image pixels into six land cover types by providing multiple choices of classes. In order to identify certain targets, some spatial knowledge about them and their inter-relationships have been incorporated on the clustered image using some heuristic rules. The use of multiple class choices makes the detection procedures effective.

A decade ago, Edelsbrunner et. al. introduced the concept of α-hulls for finding the shape of a planar set. But it still suffers from a major deficiency i.e., the single parameter α must be fine-tuned. The present article initially proposes a selection criterion of α for α-hulls in R2. Then the concept of α-hulls is extended to define the fuzzy α-hulls. The effectiveness of the fuzzy α-hulls and the proposed selection criterion of α is demonstrated on some artificially generated data sets. The convergence (with sample size) of both the crisp and fuzzy α-hulls, based on the proposed selection criterion of α, to the original pattern class has also been verified.

A multivalued (fuzzy) recognition system was formulated by Mandal et. al. which is capable of handling various imprecise inputs and provides multiple class choices to any input. In the present article, an application of the recognition system for detecting road-like structures from Indian Remote Sensing satellite (IRS) imagery has been described. The concept of multiple choices of the recognition system is found to be quite useful here. The results are seen to agree well with the geographical maps when various image frames were considered as input.

Deals with the problem of finding the representative points from a data set /spl subespl Rfrsup 2/. Two algorithms are stated. One of the algorithms can find the local best representative or seed points. The extension of these algorithms for three or more dimensions is also discussed. Experimental results on synthetic and real life data are provided which manifest the utility of these algorithms.>

A multivalued recognition system was formulated by the authors which has the ability of discriminating the nonoverlapping, and overlapping and no-class ( ambiguous/doubtful) regions and of analyzing the associated uncertainties by providing output decisions in four states, namely, single, first-second, combined, and null choices. The single choices correspond to the nonoverlapping regions, whereas the overlapping regions are reflected by the first-second and combined choices. The null choices reflect the portions outside the pattern classes and/or the portions of the pattern classes uncovered by the training samples. A theoretical analysis of these characteristics and of the performance of the recognition system is provided. It is shown theoretically that with the increase in the size of the training samples, the estimates of the overlapping, nonoverlapping, and no-class regions tend to their actual sizes. All analytical findings have been substantiated with experimental results various situations in one and two-dimensional feature spaces. Bayes decision boundaries are always found to lie within the combined choice region as provided by the multivalued recognition system. The present investigation, in turn, establishes analytically the justification of providing multivalued output decisions in four states for managing uncertainties arising from ambiguous regions.>

A connectionist model for learning and recognizing objects (or object classes) is presented. The learning and recognition system uses confidence values for the presence of a feature. The network can recognize multiple objects simultaneously when the corresponding overlapped feature train is presented at the input. An error function is defined, and it is minimized for obtaining the optimal set of object classes. The model is capable of learning each individual object in the supervised mode. The theory of learning is developed based on some probabilistic measures. Experimental results are presented. The model can be applied for the detection of multiple objects occluding each other.

A connectionist network is presented for simultaneous perception of multiple categories. These categories provide an adequate explanation of the input features originating from multiple classes. The network optimises an appropriately defined error function for making the inference. A supervised learning algorithm is presented for learning the association between the features and each individual category.>

A classification method for IRS (Indian Remote Sensing Satellite) images is presented. The image is segmented into six classes using minimum distance classifier where the centres are chosen on the basis of spectral knowledge of the corresponding classes. Two bands (green and infrared) have been used for classification. The results are presented in the form of photographs.>

A recognition system based on fuzzy set theory and approximate reasoning that is capable of handling various imprecise input patterns and providing a natural decision system is described. The input feature is considered to be of either quantitative form, linguistic form, mixed form, or set form. The entire feature space is decomposed into overlapping subdomains depending on the geometric structure and the relative position of the pattern classes found in the training samples. Uncertainty (ambiguity) in the input statement is managed by providing/modifying membership values to a great extent. A relational matrix corresponding to the subdomains and the pattern classes is used to recognize the samples. The system uses L.A. Zadeh's (1977) compositional rule of inference and gives a natural (linguistic) multivalued output decision associated with a confidence factor denoting the degree of certainty of a decision. The effectiveness of the algorithm is demonstrated for some artificially generated patterns and for real-life speech data.>

The mathematical formulation of clustering problems is considered. An attempt is made to define and discover an abstract structure from the data on the basis of finitely many observations that are assumed to be in R/sup 2/ using Euclidean distance as the dissimilarity measure. A consistent estimation and classification estimation procedure is provided for compact regions in R/sup 2/ using a minimal spanning tree.>

The problem of statistical pattern recognition with noisy or imprecise feature measurements is considered. An exact analytical expression is found for the probability of misclassification under this condition, for multiclass multivariate systems. The probability of error exceeds that of the ideal case for the special case of two classes, the a priori conditional probability density functions are assumed to be normal, along with the two cases of feature measurement error, namely normal and uniform probability density functions. Monotonicity of the misclassification probability with measurement error variance is shown. Numerical results are presented for both cases over a workable range of parameters. The study is useful in practical pattern recognition problems.