A characterization of nearest-neighbor rule decision surfaces and a new approach to generate them. (English) Zbl 0372.68024
The paper considers generating nearest-neighbor rule decision surfaces as an application of a maxmin problem. The maxmin problem is to locate a point in a given convex polyhedron which maximizes the minimum distance from a given set of points in the polyhedron. A characterization of the decision surfaces in \(n\)-dimensions is given, and the difficulty involved in generating the decision surfaces in higher dimensional spaces is brought out through this characterization. However, a novel method is presented to generate the surfaces in three dimensions using the algorithm for the maxmin problem.
MSC:
| 68T10 | Pattern recognition, speech recognition |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 68W99 | Algorithms in computer science |
References:
| [1] | Mangasarian, O. L., Linear and nonlinear separation of patterns by linear programming, Ops Res., 13, 444-452 (1965) · Zbl 0127.36701 |
| [2] | Greenberg, H. G.; Konheim, A. G., Linear and nonlinear methods in pattern classification, IBM J. Res. Dev., 8, 299-307 (1964) · Zbl 0199.22401 |
| [3] | Mangasarian, O. L., Multisurface method of pattern separation, IEEE Trans. Inf. Theory, 14, 801-810 (1968) · Zbl 0169.51108 |
| [4] | Cover, T. M.; Hart, P. E., Nearest-neighbor pattern classification, IEEE Trans. Inf. Theory, 13, 21-27 (1967) · Zbl 0154.44505 |
| [5] | Chow, C. K., Recognition method using neighbor dependence, IRE Trans. elect. Comput., 112, 683-690 (1962) · Zbl 0118.13804 |
| [6] | Dasarathy, B., Some maxmin location and pattern separation problems: theory and algorithms, (Ph.D. Dissertation (1975), The Ohio State University) |
| [7] | B. Dasarathy and L. J. White, A maxmin location problem involving a Euclidean distance: applications and algorithms, submitted for publication.; B. Dasarathy and L. J. White, A maxmin location problem involving a Euclidean distance: applications and algorithms, submitted for publication. |
| [8] | Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar set, (Inf. Proc. Lett., 1 (1972)), 132-133 · Zbl 0236.68013 |
| [9] | Shamos, M. I., Geometric complexity, (ACM Symp. on Theory of Computing (1975)), 224-233 · Zbl 0357.68046 |
| [10] | Busacker, R. G.; Saaty, T. L., Finite Graphs and Networks: An Introduction with Applications (1965), McGraw-Hill: McGraw-Hill New York · Zbl 0146.20104 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
