Inducing decision trees with an ant colony optimization algorithm

Decision trees have been widely used in data mining and machine learning as a comprehensible knowledge representation. While ant colony optimization (ACO) algorithms have been successfully applied to extract classification rules, decision tree induction with ACO algorithms remains an almost unexplored research area. In this paper we propose a novel ACO algorithm to induce decision trees, combining commonly used strategies from both traditional decision tree induction algorithms and ACO. The proposed algorithm is compared against three decision tree induction algorithms, namely C4.5, CART and cACDT, in 22 publicly available data sets. The results show that the predictive accuracy of the proposed algorithm is statistically significantly higher than the accuracy of both C4.5 and CART, which are well-known conventional algorithms for decision tree induction, and the accuracy of the ACO-based cACDT decision tree algorithm.     

FURIA: an algorithm for unordered fuzzy rule induction

This paper introduces a novel fuzzy rule-based classification method called FURIA, which is short for Fuzzy Unordered Rule Induction Algorithm. FURIA extends the well-known RIPPER algorithm, a state-of-the-art rule learner, while preserving its advantages, such as simple and comprehensible rule sets. In addition, it includes a number of modifications and extensions. In particular, FURIA learns fuzzy rules instead of conventional rules and unordered rule sets instead of rule lists. Moreover, to deal with uncovered examples, it makes use of an efficient rule stretching method. Experimental results show that FURIA significantly outperforms the original RIPPER, as well as other classifiers such as C4.5, in terms of classification accuracy.     

A greedy classification algorithm based on association rule

Classification and association rule discovery are important data mining tasks. Using association rule discovery to construct classification systems, also known as associative classification, is a promising approach. In this paper, a new associative classification technique, Ranked Multilabel Rule (RMR) algorithm is introduced, which generates rules with multiple labels. Rules derived by current associative classification algorithms overlap in their training objects, resulting in many redundant and useless rules. However, the proposed algorithm resolves the overlapping between rules in the classifier by generating rules that does not share training objects during the training phase, resulting in a more accurate classifier. Results obtained from experimenting on 20 binary, multi-class and multi-label data sets show that the proposed technique is able to produce classifiers that contain rules associated with multiple classes. Furthermore, the results reveal that removing overlapping of training objects between the derived rules produces highly competitive classifiers if compared with those extracted by decision trees and other associative classification techniques, with respect to error rate.     

Constrained dynamic rule induction learning

One of the known classification approaches in data mining is rule induction (RI). RI algorithms such as PRISM usually produce If-Then classifiers, which have a comparable predictive performance to other traditional classification approaches such as decision trees and associative classification. Hence, these classifiers are favourable for carrying out decisions by users and therefore they can be utilised as decision making tools. Nevertheless, RI methods, including PRISM and its successors, suffer from a number of drawbacks primarily the large number of rules derived. This can be a burden especially when the input data is largely dimensional. Therefore, pruning unnecessary rules becomes essential for the success of this type of classifiers. This article proposes a new RI algorithm that reduces the search space for candidate rules by early pruning any irrelevant items during the process of building the classifier. Whenever a rule is generated, our algorithm updates the candidate items frequency to reflect the discarded data examples associated with the rules derived. This makes items frequency dynamic rather static and ensures that irrelevant rules are deleted in preliminary stages when they don't hold enough data representation. The major benefit will be a concise set of decision making rules that are easy to understand and controlled by the decision maker. The proposed algorithm has been implemented in WEKA (Waikato Environment for Knowledge Analysis) environment and hence it can now be utilised by different types of users such as managers, researchers, students and others. Experimental results using real data from the security domain as well as sixteen classification datasets from University of California Irvine (UCI) repository reveal that the proposed algorithm is competitive in regards to classification accuracy when compared to known RI algorithms. Moreover, the classifiers produced by our algorithm are smaller in size which increase their possible use in practical applications.     

A correlation-based ant miner for classification rule discovery

In recent years, a few sequential covering algorithms for classification rule discovery based on the ant colony optimization meta-heuristic (ACO) have been proposed. This paper proposes a new ACO-based classification algorithm called AntMiner-C. Its main feature is a heuristic function based on the correlation among the attributes. Other highlights include the manner in which class labels are assigned to the rules prior to their discovery, a strategy for dynamically stopping the addition of terms in a rule’s antecedent part, and a strategy for pruning redundant rules from the rule set. We study the performance of our proposed approach for twelve commonly used data sets and compare it with the original AntMiner algorithm, decision tree builder C4.5, Ripper, logistic regression technique, and a SVM. Experimental results show that the accuracy rate obtained by AntMiner-C is better than that of the compared algorithms. However, the average number of rules and average terms per rule are higher.     

Data mining with an ant colony optimization algorithm

The paper proposes an algorithm for data mining called Ant-Miner (ant-colony-based data miner). The goal of Ant-Miner is to extract classification rules from data. The algorithm is inspired by both research on the behavior of real ant colonies and some data mining concepts as well as principles. We compare the performance of Ant-Miner with CN2, a well-known data mining algorithm for classification, in six public domain data sets. The results provide evidence that: 1) Ant-Miner is competitive with CN2 with respect to predictive accuracy, and 2) the rule lists discovered by Ant-Miner are considerably simpler (smaller) than those discovered by CN2     

基于蚁群优化分类规则挖掘的遥感图像分类研究

蚁群优化算法作为群智能理论的主要算法之一,已经成功应用在众多研究领域的优化问题上,但是在遥感数据处理领域还是一个新的研究课题。蚁群优化具有自组织、合作、通信等智能化优点,对数据无需统计分布参数的先验知识,因此在遥感数据处理领域具有很大的潜在优势。介绍了将蚁群优化分类规则挖掘算法应用到遥感图像分类研究领域的理论与算法流程。并采用北京地区的CBERS遥感数据作为实验数据,通过蚁群优化算法构造分类规则,对选择的遥感数据进行了分类实验,并和最大似然分类方法进行对比,实验结果表明,蚁群优化分类规则挖掘算法为遥感图像的分类提供了一种新方法。     

A Gaussian mixture model based discretization algorithm for associative classification of medical data

Knowledge-based systems such as expert systems are of particular interest in medical applications as extracted if-then rules can provide interpretable results. Various rule induction algorithms have been proposed to effectively extract knowledge from data, and they can be combined with classification methods to form rule-based classifiers. However, most of the rule-based classifiers can not directly handle numerical data such as blood pressure. A data preprocessing step called discretization is required to convert such numerical data into a categorical format. Existing discretization algorithms do not take into account the multimodal class densities of numerical variables in datasets, which may degrade the performance of rule-based classifiers. In this paper, a new Gaussian Mixture Model based Discretization Algorithm (GMBD) is proposed that preserve the most frequent patterns of the original dataset by taking into account the multimodal distribution of the numerical variables. The effectiveness of GMBD algorithm was verified using six publicly available medical datasets. According to the experimental results, the GMBD algorithm outperformed five other static discretization methods in terms of the number of generated rules and classification accuracy in the associative classification algorithm. Consequently, our proposed approach has a potential to enhance the performance of rule-based classifiers used in clinical expert systems.     

Evaluating Six Candidate Solutions for the Small-Disjunct Problem and Choosing the Best Solution via Meta-Learning

A set of classification rules can be considered as a disjunction of rules, where each rule is a disjunct. A small disjunct is a rule covering a small number of examples. Small disjuncts are a serious problem for effective classification, because the small number of examples satisfying these rules makes their prediction unreliable and error-prone. This paper offers two main contributions to the research on small disjuncts. First, it investigates six candidate solutions (algorithms) for the problem of small disjuncts. Second, it reports the results of a meta-learning experiment, which produced meta-rules predicting which algorithm will tend to perform best for a given data set. The algorithms investigated in this paper belong to different machine learning paradigms and their hybrid combinations, as follows: two versions of a decision-tree (DT) induction algorithm; two versions of a hybrid DT/genetic algorithm (GA) method; one GA; one hybrid DT/instance-based learning (IBL) algorithm. Experiments with 22 data sets evaluated both the predictive accuracy and the simplicity of the discovered rule sets, with the following conclusions. If one wants to maximize predictive accuracy only, then the hybrid DT/IBL seems to be the best choice. On the other hand, if one wants to maximize both predictive accuracy and rule set simplicity -- which is important in the context of data mining -- then a hybrid DT/GA seems to be the best choice.     

结合改进密度峰值聚类和共享子空间的协同训练算法

针对协同训练算法在迭代过程中加入的无标记样本的有用信息不足和多分类器对样本标记不一致导致的分类错误累积问题,提出结合改进密度峰值聚类和共享子空间的协同训练算法。该算法先采取属性集合互补的方式得到两个基分类器,然后基于虹吸平衡法则进行改进密度峰值聚类,并从簇中心出发来推进式选择相互邻近度高的无标记样本交由两个基分类器进行分类,最后利用多视图非负矩阵分解算法得到的共享子空间来确定标记不一致样本的最终类别。该算法利用改进密度峰值聚类和相互邻近度选择出更具空间结构代表性的无标记样本,并采用共享子空间来修订标记不一致的样本,解决了因样本误分类造成的分类精度低的问题。在9个UCI数据集上的多组对比实验证明了该算法的有效性,实验结果表明所提算法相较于对比算法在7个数据集上取得最高的分类正确率,在另2个数据集取得次高的分类正确率。     

CAIM discretization algorithm

The task of extracting knowledge from databases is quite often performed by machine learning algorithms. The majority of these algorithms can be applied only to data described by discrete numerical or nominal attributes (features). In the case of continuous attributes, there is a need for a discretization algorithm that transforms continuous attributes into discrete ones. We describe such an algorithm, called CAIM (class-attribute interdependence maximization), which is designed to work with supervised data. The goal of the CAIM algorithm is to maximize the class-attribute interdependence and to generate a (possibly) minimal number of discrete intervals. The algorithm does not require the user to predefine the number of intervals, as opposed to some other discretization algorithms. The tests performed using CAIM and six other state-of-the-art discretization algorithms show that discrete attributes generated by the CAIM algorithm almost always have the lowest number of intervals and the highest class-attribute interdependency. Two machine learning algorithms, the CLIP4 rule algorithm and the decision tree algorithm, are used to generate classification rules from data discretized by CAIM. For both the CLIP4 and decision tree algorithms, the accuracy of the generated rules is higher and the number of the rules is lower for data discretized using the CAIM algorithm when compared to data discretized using six other discretization algorithms. The highest classification accuracy was achieved for data sets discretized with the CAIM algorithm, as compared with the other six algorithms.     

A multi-objective genetic optimization of interpretability-oriented fuzzy rule-based classifiers

The paper presents a multi-objective genetic approach to design interpretability-oriented fuzzy rule-based classifiers from data. The proposed approach allows us to obtain systems with various levels of compromise between their accuracy and interpretability. During the learning process, parameters of the membership functions, as well as the structure of the classifier's fuzzy rule base (i.e., the number of rules, the number of rule antecedents, etc.) evolve simultaneously using a Pittsburgh-type genetic approach. Since there is no particular coding of fuzzy rule structures in a chromosome (it reduces computational complexity of the algorithm), original crossover and mutation operators, as well as chromosome-repairing technique to directly transform the rules are also proposed. To evaluate both the accuracy and interpretability of the system, two measures are used. The first one – an accuracy measure – is based on the root mean square error of the system's response. The second one – an interpretability measure – is based on the arithmetic mean of three components: (a) the average length of rules (the average number of antecedents used in the rules), (b) the number of active fuzzy sets and (c) the number of active inputs of the system (an active fuzzy set or input means a set or input used by at least one fuzzy rule). Both measures are used as objectives in multi-objective (2-objective in our case) genetic optimization approaches such as well-known SPEA2 and NSGA-II algorithms. Moreover, for the purpose of comparison with several alternative approaches, the experiments are carried out both considering the so-called strong fuzzy partitions (SFPs) of attribute domains and without them. SFPs provide more semantically meaningful solutions, usually at the expense of their accuracy. The operation of the proposed technique in various classification problems is tested with the use of 20 benchmark data sets and compared to 11 alternative classification techniques. The experiments show that the proposed approach generates classifiers of significantly improved interpretability, while still characterized by competitive accuracy.     

Ensembles of jittered association rule classifiers

The ensembling of classifiers tends to improve predictive accuracy. To obtain an ensemble with N classifiers, one typically needs to run N learning processes. In this paper we introduce and explore Model Jittering Ensembling, where one single model is perturbed in order to obtain variants that can be used as an ensemble. We use as base classifiers sets of classification association rules. The two methods of jittering ensembling we propose are Iterative Reordering Ensembling (IRE) and Post Bagging (PB). Both methods start by learning one rule set over a single run, and then produce multiple rule sets without relearning. Empirical results on 36 data sets are positive and show that both strategies tend to reduce error with respect to the single model association rule classifier. A bias–variance analysis reveals that while both IRE and PB are able to reduce the variance component of the error, IRE is particularly effective in reducing the bias component. We show that Model Jittering Ensembling can represent a very good speed-up w.r.t. multiple model learning ensembling. We also compare Model Jittering with various state of the art classifiers in terms of predictive accuracy and computational efficiency.     

Combining models from neural networks and inductive learning algorithms

The knowledge-based artificial neural network (KBANN) is composed of phases involving the expression of domain knowledge, the abstraction of domain knowledge at neural networks, the training of neural networks, and finally, the extraction of rules from trained neural networks. The KBANN attempts to open up the neural network black box and generates symbolic rules with (approximately) the same predictive power as the neural network itself. An advantage of using KBANN is that the neural network considers the contribution of the inputs towards classification as a group, while rule-based algorithms like C5.0 measure the individual contribution of the inputs one at a time as the tree is grown. The knowledge consolidation model (KCM) combines the rules extracted using KBANN (NeuroRule), frequency matrix (which is similar to the Naïve Bayesian technique), and C5.0 algorithm. The KCM can effectively integrate multiple rule sets into one centralized knowledge base. The cumulative rules from other single models can improve overall performance as it can reduce error-term and increase R-square. The key idea in the KCM is to combine a number of classifiers such that the resulting combined system achieves higher classification accuracy and efficiency than the original single classifiers. The aim of KCM is to design a composite system that outperforms any individual classifier by pooling together the decisions of all classifiers. Another advantage of KCM is that it does not need the memory space to store the dataset as only extracted knowledge is necessary in build this integrated model. It can also reduce the costs from storage allocation, memory, and time schedule. In order to verify the feasibility and effectiveness of KCM, personal credit rating dataset provided by a local bank in Seoul, Republic of Korea is used in this study. The results from the tests show that the performance of KCM is superior to that of the other single models such as multiple discriminant analysis, logistic regression, frequency matrix, neural networks, decision trees, and NeuroRule. Moreover, our model is superior to a previous algorithm for the extraction of rules from general neural networks.     

Fuzzy rule weight modification with particle swarm optimisation

The most challenging problem in developing fuzzy rule-based classification systems is the construction of a fuzzy rule base for the target problem. In many practical applications, fuzzy sets that are of particular linguistic meanings, are often predefined by domain experts and required to be maintained in order to ensure interpretability of any subsequent inference results. However, learning fuzzy rules using fixed fuzzy quantity space without any qualification will restrict the accuracy of the resulting rules. Fortunately, adjusting the weights of fuzzy rules can help improve classification accuracy without degrading the interpretability. There have been different proposals for fuzzy rule weight tuning through the use of various heuristics with limited success. This paper proposes an alternative approach using Particle Swarm Optimisation in the search of a set of optimal rule weights, entailing high classification accuracy. Systematic experimental studies are carried out using common benchmark data sets, in comparison to popular rule based learning classifiers. The results demonstrate that the proposed approach can boost classification performance, especially when the size of the initially built rule base is relatively small, and is competitive to popular rule-based learning classifiers.     

A hierarchical multiple classifier learning algorithm

This paper addresses the classification problem for applications with extensive amounts of data and a large number of features. The learning system developed utilizes a hierarchical multiple classifier scheme and is flexible, efficient, highly accurate and of low cost. The system has several novel features: (1) It uses a graph-theoretic clustering algorithm to group the training data into possibly overlapping cluster, each representing a dense region in the data space; (2) component classifiers trained on these dense regions are specialists whose probabilistic outputs are gated inputs to a super-classifier. Only those classifiers whose training clusters are most related to an unknown data instance send their outputs to the super-classifier; and (3) sub-class labelling is used to improve the classification of super-classes. The learning system achieves the goals of reducing the training cost and increasing the prediction accuracy compared to other multiple classifier algorithms. The system was tested on three large sets of data, two from the medical diagnosis domain and one from a forest cover classification problem. The results are superior to those obtained by several other learning algorithms.     

Cost Complexity-Based Pruning of Ensemble Classifiers

In this paper we study methods that combine multiple classification models learned over separate data sets. Numerous studies posit that such approaches provide the means to efficiently scale learning to large data sets, while also boosting the accuracy of individual classifiers. These gains, however, come at the expense of an increased demand for run-time system resources. The final ensemble meta-classifier may consist of a large collection of base classifiers that require increased memory resources while also slowing down classification throughput. Here, we describe an algorithm for pruning (i.e., discarding a subset of the available base classifiers) the ensemble meta-classifier as a means to reduce its size while preserving its accuracy and we present a technique for measuring the trade-off between predictive performance and available run-time system resources. The algorithm is independent of the method used initially when computing the meta-classifier. It is based on decision tree pruning methods and relies on the mapping of an arbitrary ensemble meta-classifier to a decision tree model. Through an extensive empirical study on meta-classifiers computed over two real data sets, we illustrate our pruning algorithm to be a robust and competitive approach to discarding classification models without degrading the overall predictive performance of the smaller ensemble computed over those that remain after pruning. Received 30 August 2000 / Revised 7 March 2001 / Accepted in revised form 21 May 2001     

基于各类支持度阈值独立挖掘的关联改进算法

关联分类及较多的改进算法很难同时既具有较高的整体准确率又有较好的小类分类性能。针对此问题,提出了一种基于类支持度阈值独立挖掘的关联分类改进算法—ACCS。ACCS算法的主要特点是:(1)根据训练集中各类数量大小给出每个类类支持度阈值的设定方法,并基于各类的类支持度阈值独立挖掘该类的关联分类规则,尽量使小类生成更多高置信度的规则;(2)采用类支持度对置信度相同的规则排序,提高小类规则的优先级;(3)用综合考虑置信度和提升度的新的规则度量预测未知实例。在多个数据集上的实验结果表明,相比多种关联分类改进算法,ACCS算法有更高的整体分类准确率,且在不平衡数据上也能取得较好的小类分类性能。     

一种基于关联分类的增量更新算法

针对现有关联分类技术的不足,提出了一种适用于关联分类的增量更新算法IUAC。该算法是基于频繁模式树挖掘和更新关联规则的,并使用一种树形结构来存储最终用于分类的关联规则。同时,增加了对分类规则的约束条件,进一步控制了用于分类的关联规则的数量。最后,对算法整体进行了分析和讨论。     

A coevolutionary algorithm for rules discovery in data mining

One of the major challenges in data mining is the extraction of comprehensible knowledge from recorded data. In this paper, a coevolutionary-based classification technique, namely COevolutionary Rule Extractor (CORE), is proposed to discover classification rules in data mining. Unlike existing approaches where candidate rules and rule sets are evolved at different stages in the classification process, the proposed CORE coevolves rules and rule sets concurrently in two cooperative populations to confine the search space and to produce good rule sets that are comprehensive. The proposed coevolutionary classification technique is extensively validated upon seven datasets obtained from the University of California, Irvine (UCI) machine learning repository, which are representative artificial and real-world data from various domains. Comparison results show that the proposed CORE produces comprehensive and good classification rules for most datasets, which are competitive as compared with existing classifiers in literature. Simulation results obtained from box plots also unveil that CORE is relatively robust and invariant to random partition of datasets.