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). PPM is a task to pair up the points in two images 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 military applications. The traditional methods for classification, 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 work the possibilities of heuristic methods such as Ant Colony Optimization in instance based classification algorithms, action rule mining and point pattern matching in images is explored to obtain efficient solutions. Instance based classifiers have gained popularity due to its simplicity and enhanced performance. In recent years, new instance based methods based on Data 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 accuracy than DGC. However, the computational complexity of DGC+ is considerably higher. 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 gravitation based methods. Another instance based algorithm called Weighted Pattern Matching based Classification (WPMC) is proposed for classification. WPMC classifies unlabelled 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, an Ant Colony Optimization based Feature and Weight Selection for WPMC (ACOFWSWPMC) is also proposed based on the idea of WPMC. WPMC is competent with the recent instance based classifiers and PMC obtaining significantly better results in terms of predictive accuracy and Cohen’s Kappa rate. 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 Classification by Mining Patterns (CMP) algorithm has been proposed. CMP algorithm mines similar patterns from the dataset to intelligently predict the class labels of the unlabelled instances. The instances in the dataset belonging to the same class that differ by one attribute value are merged to form mined patterns. Classification of unlabelled samples is made by comparing the attribute values of the unlabelled sample with the corresponding attribute values of the mined patterns derived from the dataset. The attributes for comparison is selected using an Ant Colony Optimization based Feature Selection Mined Patterns algorithm based on the idea of CMP algorithm. The advantage of CMP algorithm is its remarkable performance in classifying very small datasets with repeated attribute values. Reclassification of objects is achieved using action rules. The existing algorithms for action rule mining have high computational complexity. Also, certain action rule mining algorithms generate large number of action rules, all of which may not prove useful for reclassification. To generate optimal number of action rules, a Hierarchical Heterogeneous Ant Colony Optimization based Action Rule Mining (HHACOARM) algorithm is proposed. The ant agents at different levels in the hierarchy identify the attributes whose values need to be changed to mine action rules. The advantage of HHACOARM algorithm is that it generates optimal number of minimal cost action rules using a simple pattern matching approach. Also, the computational complexity of HHACOARM algorithm is less compared to the existing action rule mining methods. Point Pattern Matching is an important problem in the field of pattern recognition. Image Matching is achieved using a Point Pattern Matching approach. Algorithms like rigid transformation, Fast Expected Time and Approximate Input Sensitive algorithm have been proposed for Point Pattern Matching. However, the drawback of these algorithms is that the time complexity for Point Pattern Matching is higher. Re-Search algorithm was proposed for image matching to cope with confusing patterns in an indoor environment. The drawback of this algorithm is that the images which are less similar to the query image are ranked higher compared to the images which are more similar to the query image. To overcome these drawbacks, an Ant Colony Optimization based Binary Search Point Pattern Matching (ACOBSPPM) algorithm is proposed. ACOBSPPM algorithm employs a binary search method to find a match between the points in the incoming image point pattern and stored image point pattern. The advantage of ACOBSPPM algorithm is that it is efficient when compared to the existing point pattern matching approaches in terms of time complexity and precision accuracy. The number of comparisons using ACOBSPPM algorithm is much less compared to binary search method. It is very efficient in matching the incoming images that are identical to the stored images. ACOBSPPM algorithm is equally efficient for matching partial, rotated and blurred incoming images where only some point values of the incoming image point pattern matches with the point values of the stored image point pattern.