K-nearest neighbor classifier (kNN) is a simple and effective non-parametric classification algorithm. The major drawbacks of the kNN include parameters to be determined manually, its low efficiency in testing phase and suffered effect of “curse of dimensionality”. An efficient method is proposed that constructing a new kNN classifier and Naive Bayes combination classifier. K-means clustering is used to build an optimal set of cluster prototype, reducing storage space while improving the classification efficiency and determining automatically parameters. Using three types of overlapping analysis strategies and fuzzy norms measure are to relieve impacts of “curse of dimensionality”. Experimental results on both synthetic and real-world data sets show that the new classifier has good classification efficiency and classification accuracy.