Fitting Optimal Piecewise Linear Functions Using Genetic Algorithms,
Abstract
Constructing a model for data in R2 is a common problem in many scientific fields, including pattern recognition, computer vision, and applied mathematics. Often, little is known about the process which generated the data or its statistical properties. For example, in fitting a piecewise linear model the number of pieces as well as the knot locations may be unknown. Hence the method used to build the statistical model should have few assumptions and yet still provide a model that is optimal in some sense. Such methods can be designed through the use of genetic algorithms. In this paper we examine the use of genetic algorithms to fit piecewise linear functions to data in R2. The number of pieces, the location of the knots, and the underlying distribution of the data are assumed to be unknown. We discuss existing methods which attempt to solve this problem and introduce a new method which employs genetic algorithms to optimize the number and location of the linear pieces. We prove theoretically that our method provides near-optimal functions and present the results of extensive experiments which demonstrate that the proposed method provides better results than existing spline based methods. We conclude that our method represents a valuable tool for fitting both robust and non-robust piecewise linear functions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1997
- Accession Number
- ADA332788
Entities
People
- C. A. Murthy
- Jennifer Pittman
Organizations
- Pennsylvania State University