ON NEURAL-NETWORK IMPLEMENTATIONS OF K-NEAREST NEIGHBOR PATTERN CLASSIFIERS

The k-nearest neighbor (k-NN) decision rule is the basis of a well-est ablished, high-performance pattern-recognition technique but its seque ntial implementation is inherently slow. More recently, feedforward ne ural networks trained on error backpropagation have been widely used t o solve a variety of pattern-recognition problems. However, it is argu ably unnecessary to learn such a computationally intensive solution wh en one (i.e., the k-NN rule) is effectively available a priori, especi ally given the well-known pitfalls of backpropagation. Accordingly, th ere is some interest in the literature in network implementations of t his rule, so as to combine its known, good performance with the speed of a massively parallel realization. In this paper, we present a novel neural-network architecture which implements the L-NN rule and whose distinctive feature relative to earlier work is its synchronous (i.e., clocked) nature. Essentially, it has a layered, feedforward structure but, in its basic form, also incorporates feedback to control sequent ial selection of the k neighbors. The principal advantages of this new scheme are the avoidance of the stability problems which can arise wi th alternative asynchronous feedback (lateral-inhibition) circuits, th e restriction of analog weights to the first hidden layer and the fact that network design uses noniterative weight calculations rather than iterative backpropagation. Analysis of the network shows that it will converge to the desired solution (faithfully classifying the input pa ttern according to the k-NN rule) within (2k - 1) clock cycles. Apart from minor changes which can be effected externally, the same design s erves for any value of X. The space complexity of the ('brute-force'' network implementation is O(N-2) units, where N is the number of train ing patterns, and it has O(N(2)d) analog weights where d is the dimens ionality of these patterns. Thus, some modifications to reduce the req uired number of units (and, thereby, weighted connections) are conside red. Overall, this paper affords for high-speed, parallel implementati ons of proven pattern-classification techniques.