In the first stage, a classification algorithm is used to select M-type training samples with a small distance from the test samples. And in the second stage, the selected M-type training samples are used as a new training sample set for the second-stage recognition. To increase the recognition speed, an algorithm that can select M-type training samples quickly is proposed. First, a k-means clustering algorithm is used to aggregate the training samples into a large cluster. For a new test sample, the distance between the centers of each large cluster is calculated; then, several large clusters that are closer to the test sample are selected. The categories of these large clusters are included in the new training set. Training samples with the corresponding categories are combined to form a new training sample set that is used for the second-stage recognition. Experiments on different face databases confirm that the proposed algorithm can achieve faster recognition speed based on the slightly improved recognition rate.