In this paper we present a minimum sphere covering approach to pattern classification that seeks to construct a minimum number of spheres to represent the training data and formulate it as an integer programming problem. Using soft threshold functions, we further derive a linear programming problem whose solution gives rise to radial basis function (RBF) classifiers and sigmoid function classifiers. In contrast to traditional RBF and sigmoid function networks, in which the number of units is specified a priori, our method provides a new way to construct RBF and sigmoid function networks that explicitly minimizes the number of base units in the resulting classifiers. Our approach is advantageous compared to SVMs with Gaussian kernels in that it provides a natural construction of kernel matrices and it directly minimizes the number of basis functions. Experiments using real-world datasets demonstrate the competitiveness of our method in terms of classification performance and sparsity of the solution.