Browse Prior Art Database

IDENTITY CONDITIONS FOR NEAREST-NEIGHBOR AND POTENTIAL FUNCTION CLASSIFIERS

IP.com Disclosure Number: IPCOM000128595D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 12 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

SARGUR N. SRIHARI: AUTHOR [+5]

Abstract

The nearest-neighbor rule and the potential function classifier are nonparametric discrimination methods that require the storage of-a set of sample pat-terns. Here, a relationship between the two-methods in terms of subclasses and superclasses is developed. Consider-ing an exponential potential function, necessary and sufficient conditions for identity of their decision surfaces are obtained. Based on these conditions, an algorithm forestablishing identity is introduced. IndexTerms: nearest-neighbor rule, potential function classifie tric methods, decision r.., nonpaTame surfaces, identity determination

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

IDENTITY CONDITIONS FOR NEAREST-NEIGHBOR AND POTENTIAL FUNCTION CLASSIFIERS*

SARGUR N. SRIHARI Department of Computer Science SUNY at Buffalo,Amherst, NY 14226

LEE J. WHITE Dept. of Computer 'and Information Science The Ohio State Univ., Columbus, GH 43210 and

THOMAS SNABB Dept. -of Mathematics and Statistics Univ. of Michigan, Dearborn,.MI 48128

Correspondence Address: Sargur N. Srihari Dept. of Computek.Sciehce SUNY/Buffalo .4226 Ridge Lea Road Amherst,.NY .14226

*This research was supported in part by APOSR-174-2611-

ABSTRACT

The nearest-neighbor rule and the potential function classifier are nonparametric discrimination methods that require the storage of-a set of sample pat-terns. Here, a relationship between the two-methods in terms of subclasses and superclasses is developed. Consider-ing an exponential potential function, necessary and sufficient conditions for identity of their decision surfaces are obtained. Based on these conditions, an algorithm forestablishing identity is introduced.

IndexTerms: nearest-neighbor rule, potential function classifie tric methods, decision r.., nonpaTame surfaces, identity determination

1 INTRODUCTION

The nearest-neighbor decision rule [1), [2], and the potential function classifier [31,, (41 are two nonparametric classification methods. There exists little published analytical work concern- ing conditions under which the performance of the two classifiers are identical, with the exception of a heuristic comparison of their Ole decision surfaces given in (5]. Here we demonstrate.d relationship .between the two methods, and obtain conditions under which their two-class decision surfaces are identical. These conditions pro- vide the basis for an algorithm that determines from the design samples whether the two classifiers will result in identical decision surfaces.- 2. PRELIMINARIES Consider the discrimination problem with classes C I and C V where class C i has,n subc1asses C ij. Let w i denote the pri or probability of Cis, Wij the prior probability of subclass C ij when C i is true, and pij(x) the subclass-conditional probability density function of the d-component pattern x. Let D I and D 2 be two parametric decision rules designed for the above problem as follows. D assigns x to the class associated with the subclass with the maximum a posteriori probability, and D 2 assigns x to the, class with the maximum a posteriori probability. That is, D l' chooses class C i corresponding to maxeee and D,2 chooses class C corresponding to maxeee In general, D and D have different decision

(Equation Omitted)

State University of New York at Buffalo Page 1 Dec 31, 1978

Page 2 of 12

IDENTITY CONDITIONS FOR NEAREST-NEIGHBOR AND POTENTIAL FUNCTION CLASSIFIERS

boundaries, as shown in Fig.. 1 for particular univariate Gaussian.

pij(x) with mean.aiP and a common variance. The locations of a.. -13 are such that D assigns the interval (

(Equat...