A new, cellular automaton-based, nearest neighbor patternclassifier and its VLSI implementation

摘要

A new, parallel, nearest-neighbor (NN) pattern classifier, basednon a 2D Cellular Automaton (CA) architecture, is presented in thisnpaper. The proposed classifier is both time and space efficient, whenncompared with already existing NN classifiers, since it does not requirencomplex distance calculations and ordering of distances, and storagenrequirements are kept minimal since each cell stores information onlynabout its nearest neighborhood. The proposed classifier producesnpiece-wise linear discriminant curves between clusters of points ofncomplex shape (nonlinearly separable) using the computational geometrynconcept known as the Voronoi diagram, which is established through CAnevolution. These curves are established during an “off-line”noperation and, thus, the subsequent classification of unknown patternsnis achieved very fast. The VLSI design and implementation of a nearestnneighborhood processor of the proposed 2D CA architecture is alsonpresented in this paper