Evolutive Algorithms applied to the Straight Line Segment Classifier

Author(s)

Rosario Alejandra Medina Rodríguez

• Document type: Master's Dissertation
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Defense date: 2012-07-03

Examining board members

Ronaldo Fumio Hashimoto; Roberto Hirata Junior; Anna Helena Reali Costa

• Advisor: Ronaldo Fumio Hashimoto

Abstract

During the past years, the use of machine learning techniques have become into one of the most frequently performed tasks, due to the large amount of pattern recognition applications such as: voice recognition, text classification, face recognition, medical image diagnosis, among others. Thus, a great number of techniques dealing with this kind of problem have been developed until now. In this work, we propose an alternative training algorithm to improve the accuracy of the SLS binary Classifier, which produces good results that can be compared to Support Vector Machines. In that classifier, the Gradient Descent method has been used to optimize the final positions of two sets of straight line segments that represent each class. Although, this method quickly converges to an optimum, it is possible that the algorithm stops at a local optimum region, which does not guarantee a global minimum. Given that problem, we combine evolutive optimization algorithms with the gradient descent method to improve the accuracy of the SLS Classifier. In addition to our proposal of using evolutive algorithms, we also developed two proposals: (i) we explore the use of different number of straight line segments to represent the data distribution. Since the original SLS classifier algorithm uses the same number of segments for each class, which could lead to a loss of accuracy or straight line segments overlapping. So, using different number of segments could be the way to improve the accuracy; (ii) estimate the best combination of straight line segments to represent each class. Finding an optimal combination, can be a very difficult problem, so we propose the X-Means algorithm to determine the number of segments. The proposed methodology showed good results which can be used to solve some other real problems with the SLS classifier using the proposed hybrid training algorithm. (AU)

• FAPESP's process: 09/12253-5 - Theoretical and Practical Aspects of the Classifier Based on Straight Line Segments in Multiclassification Problems
• Grantee: Rosario Alejandra Medina Rodríguez
• Support Opportunities: Scholarships in Brazil - Master