Modeling and implementation of classification rule discovery by ant colony optimisation for spatial land-use suitability assessment

This paper presents an integrated modeling method for multi-criteria land-use suitability assessment (LSA) using classification rule discovery (CRD) by ant colony optimisation (ACO) in ArcGIS. This new attempt applies artificial intelligent algorithms to intelligentise LSA by discovering suitability classification rules. The methodology is implemented as a tool called ACO-LSA. The tool can generate rules which are straightforward and comprehensible for users with high classification accuracy and simple rule list in solving CRD problems. A case study in the Macintyre Brook Catchment of southern Queensland in Australia is proposed to demonstrate the feasibility of this new modeling technique. The results have addressed the major advantages of this novel approach.     

A novel multiple rule sets data classification algorithm based on ant colony algorithm

Ant colony optimization (ACO) algorithms have been successfully applied in data classification, which aim at discovering a list of classification rules. However, due to the essentially random search in ACO algorithms, the lists of classification rules constructed by ACO-based classification algorithms are not fixed and may be distinctly different even using the same training set. Those differences are generally ignored and some beneficial information cannot be dug from the different data sets, which may lower the predictive accuracy. To overcome this shortcoming, this paper proposes a novel classification rule discovery algorithm based on ACO, named AntMiner_mbc, in which a new model of multiple rule sets is presented to produce multiple lists of rules. Multiple base classifiers are built in AntMiner_mbc, and each base classifier is expected to remedy the weakness of other base classifiers, which can improve the predictive accuracy by exploiting the useful information from various base classifiers. A new heuristic function for ACO is also designed in our algorithm, which considers both of the correlation and coverage for the purpose to avoid deceptive high accuracy. The performance of our algorithm is studied experimentally on 19 publicly available data sets and further compared to several state-of-the-art classification approaches. The experimental results show that the predictive accuracy obtained by our algorithm is statistically higher than that of the compared targets.     

Utilizing multiple pheromones in an ant-based algorithm for continuous-attribute classification rule discovery

The cAnt-Miner algorithm is an Ant Colony Optimization (ACO) based technique for classification rule discovery in problem domains which include continuous attributes. In this paper, we propose several extensions to cAnt-Miner. The main extension is based on the use of multiple pheromone types, one for each class value to be predicted. In the proposed μcAnt-Miner algorithm, an ant first selects a class value to be the consequent of a rule and the terms in the antecedent are selected based on the pheromone levels of the selected class value; pheromone update occurs on the corresponding pheromone type of the class value. The pre-selection of a class value also allows the use of more precise measures for the heuristic function and the dynamic discretization of continuous attributes, and further allows for the use of a rule quality measure that directly takes into account the confidence of the rule. Experimental results on 20 benchmark datasets show that our proposed extension improves classification accuracy to a statistically significant extent compared to cAnt-Miner, and has classification accuracy similar to the well-known Ripper and PART rule induction algorithms.     

A belief classification rule for imprecise data

The classification of imprecise data is a difficult task in general because the different classes can partially overlap. Moreover, the available attributes used for the classification are often insufficient to make a precise discrimination of the objects in the overlapping zones. A credal partition (classification) based on belief functions has already been proposed in the literature for data clustering. It allows the objects to belong (with different masses of belief) not only to the specific classes, but also to the sets of classes called meta-classes which correspond to the disjunction of several specific classes. In this paper, we propose a new belief classification rule (BCR) for the credal classification of uncertain and imprecise data. This new BCR approach reduces the misclassification errors of the objects difficult to classify by the conventional methods thanks to the introduction of the meta-classes. The objects too far from the others are considered as outliers. The basic belief assignment (bba) of an object is computed from the Mahalanobis distance between the object and the center of each specific class. The credal classification of the object is finally obtained by the combination of these bba’s associated with the different classes. This approach offers a relatively low computational burden. Several experiments using both artificial and real data sets are presented at the end of this paper to evaluate and compare the performances of this BCR method with respect to other classification methods.     

On optimal rule discovery

In machine learning and data mining, heuristic and association rules are two dominant schemes for rule discovery. Heuristic rule discovery usually produces a small set of accurate rules, but fails to find many globally optimal rules. Association rule discovery generates all rules satisfying some constraints, but yields too many rules and is infeasible when the minimum support is small. Here, we present a unified framework for the discovery of a family of optimal rule sets and characterize the relationships with other rule-discovery schemes such as nonredundant association rule discovery. We theoretically and empirically show that optimal rule discovery is significantly more efficient than association rule discovery independent of data structure and implementation. Optimal rule discovery is an efficient alternative to association rule discovery, especially when the minimum support is low.     

Automatic rule discovery for field work in anthropology

This paper deals with the problem of discovering rules that govern social interactions and relations in preliteral societies. Two older computer programs are first described which can receive data, possibly incomplete and redundant, representing kinship relations among named individuals. The programs then establish a knowledge base in the form of a directed graph, which the user can query in a variety of ways. Another program, written on the top of these (rewritten in LISP), can form concepts of various properties, including kinship relations, of and between the individuals. The concepts are derived from the examples and non-examples of a certain social pattern, such as inheritance, succession, marriage, class (tribe, moiety, clan, etc.) membership, domination-subordination, incest and exogamy. The concepts become hypotheses about the rules, which are corroborated, modified or rejected by further examples and non-examples.Dedicated to Claude Levi-StraussNicholas Findler is Research Professor of Computer Science, Director of the Artificial Intelligence Laboratory and Adjunct Professor of Mathematics at Arizona State University. He has worked in various areas of Artificial Intelligence since 1957 and has authored many articles and books. The two most recent books are Contributions to a Computer-Based Theory of Strategies (New York: Springer-Verlag) and An Artificial Intelligence Technique for Information and Fact Retrieval — An Application in Medical Knowledge Processing (Cambridge, MA: MIT Press). His current interests include Artificial Intelligence, Simulation of Cognitive Behavior, Heuristic Programming, Decision Making under Uncertainty and Risk, Theory of Strategies, Computational Linguistics, Information Retrieval, and Expert Systems     

一种防火墙规则冲突检测算法

在入侵检测系统和状态检测防火墙等应用中,规则冲突检测及冲突解析算法是影响安全性及服务质量的关键。首先对防火墙过滤规则之间的关系进行了建模和分类。然后在过滤规则关系分类的基础上提出了一种冲突检测算法。该算法能够自动检测、发现规则冲突和潜在的问题,并且能够对防火墙过滤规则进行无冲突的插入、删除和修改。实现该算法的工具软件能够显著简化防火墙策略的管理和消除防火墙的规则冲突。     

基于属性重要性的关联分类方法

提出了基于属性重要性的关联分类方法.与传统算法不同的是根据属性重要性程度生成类别关联规则;并且在构造分类器时改进了CBA算法中对于具有相同支持度、置信度规则选择时的随机性.实验结果证明,用该方法得到的分类规则与传统的关联分类算法相比,复杂度低,且有效提高了分类效果.     

A neural network and fuzzy rule base hybrid for pattern classification

 This paper presents a novel hybrid of the two complimentary technologies of soft computing viz. neural networks and fuzzy logic to design a fuzzy rule based pattern classifier for problems with higher dimensional feature spaces. The neural network component of the hybrid, which acts as a pre-processor, is designed to take care of the all-important issue of feature selection. To circumvent the disadvantages of the popular back propagation algorithm to train the neural network, a meta-heuristic viz. threshold accepting (TA) has been used instead. Then, a fuzzy rule based classifier takes over the classification task with a reduced feature set. A combinatorial optimisation problem is formulated to minimise the number of rules in the classifier while guaranteeing high classification power. A modified threshold accepting algorithm proposed elsewhere by the authors (Ravi V, Zimmermann H.-J. (2000) Eur J Oper Res 123: 16–28) has been employed to solve this optimization problem. The proposed methodology has been demonstrated for (1) the wine classification problem having 13 features and (2) the Wisconsin breast cancer determination problem having 9 features. On the basis of these examples the results seem to be very interesting, as there is no reduction in the classification power in either of the problems, despite the fact that some of the original features have been completely eliminated from the study. On the contrary, the chosen features in both the problems yielded 100% classification power in some cases.     

Evolutionary-modified fuzzy nearest-neighbor rule for pattern classification

This paper presents an improved version of the well-established k nearest neighbor (k-NN) and fuzzy NN (FNN), termed the multi-objective genetic-algorithm-modified FNN (MOGA-MFNN). The MFNN design problem is converted into a multi-modal objective maximization problem constrained by four objective functions. Thereafter, the associated parameter set of the MFNN and the feature attributes can be determined optimally and automatically via the non-dominated sorting genetic algorithm II. We introduce two new objective functions termed the Margin-I and Margin-II, which are used to improve the generalization capability of the MFNN for the unknown data, along with two existing performance functions: the geometric mean and the area under the receiver-operated characteristic curve for the training accuracy. Moreover, we proposed a novel data-dependent weight-assignment technique for local class membership functions of the MFNN. The technique enables the MFNN to determine its local neighbors adaptively through the MOGA algorithm. To expedite the classification, the MOGA-MFNN is implemented on a graphical processing unit (GPU), which significantly increases the computation speed. Furthermore, the local class-membership function of the MFNN can be computed in advance, rather than delaying it to the classification stage. This again can improve the classification speed. The MOGA-MFNN is evaluated on 20 datasets obtained from the repository of the University of California, Irvine (UCI). The experiments with rigorous statistical significance tests demonstrate that the proposed method performs competitively with the existing methods.     

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.     

一种用于历史疫灾分级的退火蚂蚁聚类方法

针对历史疫灾记录量化程度低、社会关联性强的问题,提出了一种结合模拟退火和蚂蚁算法的历史疫灾分级方法。利用单只蚂蚁对疫灾数据进行自动聚类并通过模拟退火算法对聚类准则进行优化,以获得疫灾聚类的全局最优解。通过与其他聚类方法的性能对比,实验结果证明该方法具有较高的精确性和实用性。     

A genetic programming method for protein motif discovery and protein classification

Proteins can be grouped into families according to some features such as hydrophobicity, composition or structure, aiming to establish common biological functions. This paper presents MAHATMA—memetic algorithm-based highly adapted tool for motif ascertainment—a system that was conceived to discover features (particular sequences of amino acids, or motifs) that occur very often in proteins of a given family but rarely occur in proteins of other families. These features can be used for the classification of unknown proteins, that is, to predict their function by analyzing their primary structure. Experiments were done with a set of enzymes extracted from the Protein Data Bank. The heuristic method used was based on genetic programming using operators specially tailored for the target problem. The final performance was measured using sensitivity, specificity and hit rate. The best results obtained for the enzyme dataset suggest that the proposed evolutionary computation method is effective in finding predictive features (motifs) for protein classification.     

A stock recommendation system exploiting rule discovery in stock databases

This paper addresses an approach that recommends investment types to stock investors by discovering useful rules from past changing patterns of stock prices in databases. First, we define a new rule model for recommending stock investment types. For a frequent pattern of stock prices, if its subsequent stock prices are matched to a condition of an investor, the model recommends a corresponding investment type for this stock. The frequent pattern is regarded as a rule head, and the subsequent part a rule body. We observed that the conditions on rule bodies are quite different depending on dispositions of investors while rule heads are independent of characteristics of investors in most cases. With this observation, we propose a new method that discovers and stores only the rule heads rather than the whole rules in a rule discovery process. This allows investors to impose various conditions on rule bodies flexibly, and also improves the performance of a rule discovery process by reducing the number of rules to be discovered. For efficient discovery and matching of rules, we propose methods for discovering frequent patterns, constructing a frequent pattern base, and its indexing. We also suggest a method that finds the rules matched to a query from a frequent pattern base, and a method that recommends an investment type by using the rules. Finally, we verify the effectiveness and the efficiency of our approach through extensive experiments with real-life stock data.     

Multi-level knowledge discovery from rule bases

The discovery of multi-level knowledge is important to allow queries at and across different levels of abstraction. While there are some similarities between our research and that of others in this area, the work reported in this paper does not directly involve databases and is differently motivated. Our research is interested in taking data in the form of rule-bases and finding multi-level knowledge. This paper describes our motivation, our preferred technique for acquiring the initial knowledge known as Ripple-Down Rules, the use of Formal Concept Analysis to develop an abstraction hierarchy, and our application of these ideas to knowledge bases from the domain of chemical pathology. We also provide an example of how the approach can be applied to other prepositional knowledge bases and suggest that it can be used as an additional phase to many existing data mining approaches.     

Sentimental causal rule discovery from Twitter

Social media, especially Twitter is now one of the most popular platforms where people can freely express their opinion. However, it is difficult to extract important summary information from many millions of tweets sent every hour. In this work we propose a new concept, sentimental causal rules, and techniques for extracting sentimental causal rules from textual data sources such as Twitter which combine sentiment analysis and causal rule discovery. Sentiment analysis refers to the task of extracting public sentiment from textual data. The value in sentiment analysis lies in its ability to reflect popularly voiced perceptions that are stated in natural language. Causal rules on the other hand indicate associations between different concepts in a context where one (or several concepts) cause(s) the other(s). We believe that sentimental causal rules are an effective summarization mechanism that combine causal relations among different aspects extracted from textual data as well as the sentiment embedded in these causal relationships. In order to show the effectiveness of sentimental causal rules, we have conducted experiments on Twitter data collected on the Kurdish political issue in Turkey which has been an ongoing heated public debate for many years. Our experiments on Twitter data show that sentimental causal rule discovery is an effective method to summarize information about important aspects of an issue in Twitter which may further be used by politicians for better policy making.     

Action rule discovery from incomplete data

Action rule is an implication rule that shows the expected change in a decision value of an object as a result of changes made to some of its conditional values. An example of an action rule is ‘credit card holders of young age are expected to keep their cards for an extended period of time if they receive a movie ticket once a year’. In this case, the decision value is the account status, and the condition value is whether the movie ticket is sent to the customer. The type of action that can be taken by the company is to send out movie tickets to young customers. The conventional action rule discovery algorithms build action rules from existing classification rules. This paper discusses an agglomerative strategy that generates the shortest action rules directly from a decision system. In particular, the algorithm can be used to discover rules from an incomplete decision system where attribute values are partially incomplete. As one of the testing domains for our research we take HEPAR system that was built through a collaboration between the Institute of Biocybernetics and Biomedical Engineering of the Polish Academy of Sciences and physicians at the Medical Center of Postgraduate Education in Warsaw, Poland. HEPAR was designed for gathering and processing clinical data on patients with liver disorders. Action rules will be used to construct the decision-support module for HEPAR.