Intelligent Data Analysis: An International Journal

Label noise, which has not been well studied yet, is present in many machine learning problems and would make negative influence to both the classifier and feature selection procedure. To address this issue, we propose a novel mutual information estimator using Parzen window based on a probabilistic label noise model, which could be robust to incorrect label samples. Then we utilize the estimator to achieve a robust feature selection algorithm for label noise. Experimentation is executed over a toy dataset and eight real world datasets. Results after performing classification with a kNN classifier reveal that the proposed approach is sound and able to reduce the influence of label noise effectively and to improve the performance of feature selection in the presence of label noise.

The need to reduce the dimensionality of a dataset whilst retaining its inherent manifold structure is key to many pattern recognition, machine learning, and computer vision problems. This process is often referred to as manifold learning since the structure is preserved during dimensionality reduction by learning the intrinsic low-dimensional manifold that the data lies upon. In this paper a heuristic approach is presented to tackle this problem by approximating the manifold as a set of piecewise linear models. By merging these linear models in an order defined by their global topology a globally stable and locally accurate model of the manifold can be obtained. A detailed analysis of the proposed approach is presented along with comparison with existing manifold learning techniques. Results obtained on both artificial and image based data show that in many cases this heuristic approach to manifold learning is able to out-perform traditional techniques.

Analysis of network traffic, financial transactions, and mobile communications are examples of applications where examining entire samples of a large dataset is computationally expensive, and requires significant memory space. A common approach to address this challenge is to reduce the number of samples without compromising the accuracy of analyzing them. In this paper, we propose a new cluster-based sample reduction method which is unsupervised, geometric, and density-based. The original data is initially divided into clusters, and each cluster is divided into ``portions'' defined as the areas between two concentric circles. Then, using the proposed geometric-based formulas, the selection value of each sample belonging to a specific portion is calculated. Samples are then selected from the original data according to the corresponding calculated selection value. The performance of the proposed method is measured on various datasets and compared with several cluster-based and density-based methods. We conduct various experiments on the NSL-KDD, KDDCup99, and IUSTsip datasets, and evaluate the performance of the proposed method by measuring the cluster validity indices, as well as the accuracy of the classifier applied on the reduced data. We demonstrate that the reduced dataset has similar sample scattering as that of the original dataset. We also demonstrate that, while reducing the sample size of the input dataset in half, the classification accuracy is not reduced significantly, indicating that the proposed method selects the most relevant samples from the original dataset.

Feature selection is an important machine learning topic, especially in high dimensional applications, such as cancer prediction with microarray data. This work addresses the issue of high dimensionality of feature selection for linear and kernel-based Support Vector Machines (SVMs) considering second-order cone programming formulations. These formulations provide a robust and efficient framework for classification, while an adequate feature selection process avoids errors in the estimation of means and covariances. Our approach is based on a sequential backward elimination which uses different linear and kernel-based contribution measures to determine the feature relevance. Experimental results with microarray datasets demonstrate the effectiveness in terms of predictive performance and construction of a low-dimensional data representation.

In the present paper we compare clustering solutions using indices of paired agreement. We propose a new method - IADJUST - to correct indices of paired agreement, excluding agreement by chance. This new method overcomes previous limitations known in the literature as it permits the correction of any index. We illustrate its use in external clustering validation, to measure the accordance between clusters and an a priori known structure. The adjusted indices are intended to provide a realistic measure of clustering performance that excludes agreement by chance with ground truth. We use simulated data sets, under a range of scenarios - considering diverse numbers of clusters, clusters overlaps and balances - to discuss the pertinence and the precision of our proposal. Precision is established based on comparisons with the analytical approach for correction - specific indices that can be corrected in this way are used for this purpose. The pertinence of the proposed correction is discussed when making a detailed comparison between the performance of two classical clustering approaches, namely Expectation-Maximization (EM) and K-Means (KM) algorithms. Eight indices of paired agreement are studied and new corrected indices are obtained.

In clustering, providing an explanation of the results is an important task. Pattern-based clustering algorithms return a set of patterns that describe the objects grouped in each cluster. The most recent algorithms proposed in this approach have a high computational cost in the clustering stage, making them non suitable when a huge amount of patterns are extracted from a dataset. In this paper, we introduce an algorithm for extracting a small subset of patterns useful for clustering. The proposed algorithm extracts patterns from a collection of trees generated through a new induction procedure. Experimental results show that the proposed algorithm extracts significantly less patterns in a significantly less time than recent pattern-based clustering algorithms, but obtaining similar clustering results in terms of F-measure. It makes our algorithm suitable for medium-large datasets where other pattern-based clustering algorithms cannot produce a result in a reasonable time. In addition, our algorithm obtains similar clustering quality results than traditional clustering algorithms.

Using microarray techniques, it is possible to measure the expression levels of thousands of genes under several experimental conditions. Extracting information from microarray data is an important problem in Bioinformatics scope. Producing overlapping clusters is a major issue in clustering methods. While most of the research in this area has focused on clustering using disjoint cluster, many real microarray datasets and as a result many gene regulatory networks have inherently overlapping partitions. Genes have more than one function by coding for proteins that participate in multiple metabolic pathways. So, Overlapped clusters have an important role in discovering the relationship between genes and finding overlap gene regulatory networks. Recent proposed clustering methods rely on the search of optimal disjoint clusters. In this paper, we propose a new density based clustering (OverDBC) with a bound on the number of overlap clusters. OverDBC allows genes membership in a restricted number of clusters where the total number of clusters is unbounded. We define closeness as a new concept for finding core genes along with the density concept. We compare OverDBC with DBscan (a non-overlapping density-based clustering) algorithm. We prove that OverDBC may be significantly better than non-overlapping clustering in microarray data.

The goal of privacy preserving clustering (PPC) is to preserve the privacy of data during clustering analysis. Most of the existing PPC algorithms are based on heuristic notions without provable privacy. Differential privacy is the strong notion of privacy introduced to overcome this problem. However, the lower degree of utility is the serious drawback of the techniques, which preserve differential privacy. In addition, high dimensionality of data is another drawback of the most existing PPC techniques, which leads to low efficiency of them. This paper proposes differential-based algorithms for PPC in horizontally and vertically distributed datasets. To overcome the above two drawbacks, we have used orthogonal discrete wavelet transforms (DWT) for obtaining perturbed data with both low data dimensionality and less noise addition. Our algorithms are implemented and experimented using some well-known datasets. The results show that the proposed algorithms guarantee an appropriate level of both utility and privacy of the published data.

Conformal prediction (CP) is a relatively new framework in which predictive models output sets of predictions with a bound on the error rate, i.e., the probability of making an erroneous prediction is guaranteed to be equal to or less than a predefined significance level. Label-conditional conformal prediction (LCCP) is a specialization of the framework which gives a bound on the error rate for each individual class. For datasets with class imbalance, many learning algorithms have a tendency to predict the majority class more often than the expected relative frequency, i.e., they are biased in favor of the majority class. In this study, the class bias of standard and label-conditional conformal predictors is investigated. An empirical investigation on 32 publicly available datasets with varying degrees of class imbalance is presented. The experimental results show that CP is highly biased towards the majority class on imbalanced datasets, i.e., it can be expected to make a majority of its errors on the minority class. LCCP, on the other hand, is not biased towards the majority class. Instead, the errors are distributed between the classes almost in accordance with the prior class distribution.

The World Wide Web is becoming the most important source to search for information or products. But the size and the unstructured nature of the available information makes the location of the right information a challenging task. Recommender systems and web usage mining techniques are two of the main methods used to overcome information overload. In this paper, we present a framework for the next page prediction that exploits users' access history combined with his semantic interests to generate personalized and accurate recommendations. We are suggesting two different approaches for decision fusion between usage and semantic data. The two proposed techniques offered a 47.3% and 54.3% improvement in prediction accuracy over conventional methods for next page prediction. The suggested framework also employs user clustering to focus the search which reduced the prediction time by an average of 68.7% and 63.4%.

Generalized additive models are well-known as a powerful and palatable predictive modelling technique. Scorecards, the discretized version of generalized additive models, are a long-established method in the industry, due to its balance between simplicity and performance. Scorecards are easy to apply and easy to understand. Moreover, in spite of their simplicity, scorecards can model nonlinear relationships between the inputs and the value to be predicted. In the scientific community, scorecards have been largely overlooked in favor of more recent models such as neural networks or support vector machines. In this paper, we address scorecard development, introducing a new formulation more suitable to support regularization. We tackle both the binary and the ordinal data classification problems. In both settings, the proposed methodology shows advantages when evaluated using real datasets.

Decision tree is a simple and effective method and it can be supplemented with ensemble methods to improve its performance. Random Forest and Rotation Forest are two approaches which are perceived as ``classic'' at present. They can build more accurate and diverse classifiers than Bagging and Boosting by introducing the diversities namely randomly chosen a subset of features or rotated feature space. However, the splitting criteria used for constructing each tree in Random Forest and Rotation Forest are Gini index and information gain ratio respectively, which are skew-sensitive. When learning from highly imbalanced datasets, class imbalance impedes their ability to learn the minority class concept. Hellinger distance decision tree (HDDT) was proposed by Chawla, which is skew-insensitive. Especially, bagged unpruned HDDT has proven to be an effective way to deal with highly imbalanced problem. Nevertheless, the bootstrap sampling used in Bagging can lead to ensembles of low diversity compared to Random Forest and Rotation Forest. In order to combine the skew-insensitivity of HDDT and the diversities of Random Forest and Rotation Forest, we use Hellinger distance as the splitting criterion for building each tree in Random Forest and Rotation Forest respectively. An experimental framework is performed across a wide range of highly imbalanced datasets to investigate the effectiveness of Hellinger distance, information gain ratio and Gini index which are used as the splitting criteria in ensembles of decision trees including Bagging, Boosting, Random Forest and Rotation Forest. In addition, Balanced Random Forest is also included in the experiment since it is designed to tackle class imbalance problem. The experimental results, which contrasted through nonparametric statistical tests, demonstrate that using Hellinger distance as the splitting criterion to build individual decision tree in forest can improve the performances of Random Forest and Rotation Forest for highly imbalanced classification.