Intelligent Data Analysis: An International Journal

In this paper we describe novel feature subset selection methods, based on the estimation of feature salience i.e. the quantification of the relative importance of individual features, in the presence of other features, for determining the classes of records in a dataset. We present a definition of what we mean by feature salience and a method for estimating this feature salience. Five synthetic datasets were used to demonstrate the utility of the salience estimation technique. It was found that the estimation techniques produced good approximations to the calculated saliencies in most cases.

The use of feature salience as the basis of three methods of feature subset selection is described. These methods were evaluated on real world data sets by constructing classifiers using all features and comparing these with classifiers constructed using only a selected subset of features. It was found that the results compared well with other state of the art techniques and that the methods were simpler to implement and significantly faster to execute.

On average, applying our best feature subset selection method resulted in trees that used only 49% of the features used by trees constructed with the full set of features. This reduction in number of features used was associated with a 1% improvement in classifier accuracy.

In this paper we study the problem of constructing accurate decision tree models from data streams. Data streams are incremental tasks that require incremental, online, and any-time learning algorithms. One of the most successful algorithms for mining data streams is VFDT. We have extended VFDT in three directions: the ability to deal with continuous data; the use of more powerful classification techniques at tree leaves, and the ability to detect and react to concept drift. VFDTc system can incorporate and classify new information online, with a single scan of the data, in time constant per example. The most relevant property of our system is the ability to obtain a performance similar to a standard decision tree algorithm even for medium size datasets. This is relevant due to the any-time property. We also extend VFDTc with the ability to deal with concept drift, by continuously monitoring differences between two class-distribution of the examples: the distribution when a node was built and the distribution in a time window of the most recent examples. We study the sensitivity of VFDTc with respect to drift, noise, the order of examples, and the initial parameters in different problems and demonstrate its utility in large and medium data sets.

In this paper we investigate an algorithmic extension to the technique of Stacking for regression that prunes the ensemble set before application based on a consideration of the training accuracy and diversity of the ensemble members. We evaluate two variants of this approach in comparison to the standard Stacking algorithm, one of which is a static approach that prunes back the ensemble to the same constant size; the other of which is a variable approach prunes the ensemble to an appropriate level based on measures of accuracy and diversity of the ensemble members. We show that on average both techniques are robust in performance to their non-pruned counterpart, while having the advantage of producing smaller and less complex ensembles. In the latter respect, the static approach proved more effective, but we show that the variable approach lends itself better for further optimization.

We introduce in this paper a generalization of the widely used hidden Markov models (HMM's), which we name “structural hidden Markov models” (SHMM). Our approach is motivated by the need of modeling complex structures which are encountered in many natural sequences pertaining to areas such as computational molecular biology, speech/handwriting recognition and content-based information retrieval. We consider observations as strings that produce the structures derived by an unsupervised learning process. These observations are related in the sense they all contribute to produce a particular structure. Four basic problems are assigned to a structural hidden Markov model: (1) probability evaluation, (2) state decoding, (3) structural decoding, and (4) parameter re-estimation. We have applied our methodology to recognize handwritten numerals. The results reported in this application show that the structural hidden Markov model outperforms the traditional hidden Markov model with a 23.9% error-rate reduction.

The entity and relation recognition, i.e. (1) assigning semantic classes (e.g., person, organization and location) to entities in a sentence, and (2) determining the relations (e.g., born-in and employee-of) held between the corresponding entities, is an important task in areas such as information extraction and question answering. Subtasks (1) and (2) are typically carried out sequentially, and this procedure is problematic: errors made during subtask (1) are propagated to subtask (2) with an accumulative effect; and in many cases information that becomes available only during subtask (2) (e.g., the class of an entity corresponds to the first argument of relation born-in (X, China)) would be helpful for subtask (1) (e.g., the class of the entity cannot be a location but a person). To address problems of this kind, this paper develops a novel method, which allows subtasks (1) and (2) to be linked more closely together. The procedure is separated to three stages. Firstly, employ two classifiers to perform subtasks (1) and (2) independently. Secondly, the semantic class of each entity is determined by taking into account the classes of all the entities in the sentence, as computed during the previous step. This is achieved using a special model dubbed “entity relation propagation diagram” and “entity relation propagation tree”. Thirdly, each relation is then assigned a class by considering the semantic classes of the entities produced at the previous step. Our experimental results show that the method improves not only relation recognition but also entity recognition in some degree.