Investigations on Pattern Matching Approaches Using Ant Colony Optimization for Efficient Classification

Abstract

Machine learning is the development of algorithms that allow computers to learn based on empirical data. The goal of Machine learning is to build computer systems that adapt and learn from their experience. Machine learning can be either supervised or unsupervised. An example of supervised learning is classification. Classification is defined as the task of learning from examples which are described by a set of predictive attributes and a class attribute. The result of learning is a classification model that is capable of accurately predicting the class label of unknown instances based only on the values of the predictive attributes. Classification has been successfully implemented using instance based methods.In recent days, reclassification of objects is considered vital in certain applications including financial sector and e-commerce. Reclassification may be achieved with the help of action rules. Images can also be classified using Point Pattern Matching (PPM). PPMis a task to pair up the points in twoimages of a same scene.Some of the practical applications of PPM include model-based tracking and recognition of a referenced template pattern in images, duplicate image identification, remotely sensed data with applications in civilian, agriculture, geology, oil and mineral exploration, astronomy and militaryapplications.The traditional methods forclassification, action rule mining and image matching using point pattern matching are beset with drawbacks justifying a compelling need to look for better / efficient solutions.In this workthe possibilities of heuristic methods such as Ant Colony Optimization in instance based classification algorithms, action rule mining and point pattern matching in imagesis exploredto obtain efficient solutions.Instance based classifiers have gained popularity due to its simplicity and enhanced performance. In recent years, new instancebased methods based on ivData Gravitation have been proposed.Data Gravitation based Classification (DGC) achieves good classification accuracy than the existing classifiers. Another instance based method called Weighted Data Gravitation based Classification (DGC+) is proved to achieve greater classification accuracythanDGC. However, the computational complexity of DGC+ is considerablyhigher.To overcome the drawbacks of the existing classifiers and to achieve improved classification accuracy, an instance based algorithm called Pattern Matching based Classification (PMC) has been proposed. PMC classifies unlabelled samples based on the similarity between the feature values of the instances in the dataset and the unlabelled sample.To further improve the classification accuracy of PMC algorithm, an Ant Colony Optimization based Feature Selection approach based on the idea of PMC is proposed. The advantage of PMC in comparison with other instance based methods is its simple classification procedure. Also, PMC is competent with the recent instance based algorithms obtaining significantly better results in terms of predictive accuracy and Cohen’s Kappa rate. The computational time of PMC algorithm is less compared to the gravitationbased methods.Another instance based algorithm called Weighted Pattern Matching based Classification (WPMC) is proposed for classification. WPMC classifiesunlabelled samples by computing the absolute difference between the feature values of the instances in the dataset and the unlabelled sample.To further achieve better classification accuracy, anAnt Colony Optimization based Feature and Weight Selection forWPMC (ACOFWSWPMC) is also proposed based on the idea ofWPMC. WPMC is competentwith the recent instance based classifiersand PMC obtaining significantlybetter results in terms of predictive accuracy and Cohen’s Kapparate.Many classifiers that are efficient in classifying high dimensional datasets fail to classify small datasets having few attributes with repeated attribute values. To classify such datasets, an instance based algorithm called