Nearest hyperdisk methods for high-dimensional classification

ABSTRACT

In high-dimensional classification problems it is infeasible to include enough training samples to cover the class regions densely. Irregularities in the resulting sparse sample distributions cause local classifiers such as Nearest Neighbors (NN) and kernel methods to have irregular decision boundaries. One solution is to "fill in the holes" by building a convex model of the region spanned by the training samples of each class and classifying examples based on their distances to these approximate models. Methods of this kind based on affine and convex hulls and bounding hyperspheres have already been studied. Here we propose a method based on the bounding hyperdisk of each class - the intersection of the affine hull and the smallest bounding hypersphere of its training samples. We argue that in many cases hyperdisks are preferable to affine and convex hulls and hyperspheres: they bound the classes more tightly than affine hulls or hyperspheres while avoiding much of the sample overfitting and computational complexity that is inherent in high-dimensional convex hulls. We show that the hyperdisk method can be kernelized to provide nonlinear classifiers based on non-Euclidean distance metrics. Experiments on several classification problems show promising results.

REFERENCES

• 1: Kristin P. Bennett , Erin J. Bredensteiner, Duality and Geometry in SVM Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.57-64, June 29-July 02, 2000
• 2: Cevikalp, H., Larlus, D., Douze, M., & Jurie, F. (2007). Local subspace classifiers: Linear and nonlinear approaches. IEEE Workshop on Machine Learning for Signal Processing. Thessaloniki, Greece.
• 3: Hakan Cevikalp , Marian Neamtu , Mitch Wilkes , Atalay Barkana, Discriminative Common Vectors for Face Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.1, p.4-13, January 2005 [doi>10.1109/TPAMI.2005.9]
• 4: Cevikalp, H., Triggs, B., Jurie, F., & Polikar, R. (2008). Margin-based discriminant dimensionality reduction for visual recognition. IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
• 5: Gulmezoglu, M. B., Dzhafarov, V., & Barkana, A. (2001). The common vector approach and its relation to principal component analysis. IEEE Trans. Speech Audio Proc., 9, 655--662.
• 6: Hinton, G. E., Dayan, P., & Revow, M. (1997). Modeling the manifolds of images of handwritten digits. IEEE Transactions on Neural Networks, 18, 65--74.
• 7: Laaksonen, J. (1997). Subspace classifiers in recognition of handwritten digits. Doctoral dissertation, Helsinki University of Technology.
• 8: Svetlana Lazebnik , Cordelia Schmid , Jean Ponce, A Maximum Entropy Framework for Part-Based Texture and Object Recognition, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.832-838, October 17-20, 2005 [doi>10.1109/ICCV.2005.10]
• 9: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 10: Nalbantov, G. I., Groenen, P. J. F., & Bioch, J. C. (2007). Nearest convex hull classification (Technical Report). Econometric Institute and Erasmus Research Institute of Management.
• 11: Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.
• 12: Bernhard Schölkopf , Alexander Smola , Klaus-Robert Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, v.10 n.5, p.1299-1319, July 1, 1998 [doi>10.1162/089976698300017467]
• 13: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 14: David M. J. Tax , Robert P. W. Duin, Support Vector Data Description, Machine Learning, v.54 n.1, p.45-66, January 2004 [doi>10.1023/B:MACH.0000008084.60811.49]
• 15: Jakob Verbeek, Learning Nonlinear Image Manifolds by Global Alignment of Local Linear Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.8, p.1236-1250, August 2006 [doi>10.1109/TPAMI.2006.166]
• 16: Vincent, P., & Bengio, Y. (2001). K-local hyperplane and convex distance nearest neighbor algorithms. NIPS.
• 17: Wang, J., Neskovic, P., & Cooper, L. N. (2005). Pattern classification via single spheres. Discovery Science (pp. 241--252).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance