Background: The use of speech based data in the classification of Parkinson disease (PD) has shown to provide an effect, non-invasive mode of classification in recent years. Thus, there has been an increased interest in speech based methods applicable to Parkinsonism for building predictive tele-diagnosis and tele-monitoring models. One of the obstacles in optimizing classifications is to reduce noise within the collected speech samples, thus ensuring satisfying classification accuracy and stability. While the current methods are effective, the ability on instance selection has been seldom examined until now. Methods: In this study, a PD oriented classification algorithm was proposed and examined that combines Classification and Regression Tree (CART) algorithm and an ensemble-learning algorithm. First, the CART algorithm was applied in selecting optimal training speech samples iteratively, thereby obtaining samples with high separability. Second, an ensemble learning algorithm combining random forest (RF), Support Vector Machines (SVM) and Extreme Learning Machine (ELM) was trained based on the optimized training samples. Lastly, the trained ensemble-learning algorithm was applied to the test samples for classification. This proposed method was examined based on most recent public dataset and compared with other relevant algorithms for verification. Results: Experimental results showed that the proposed algorithm obtained the highest degree of improved classification accuracy (over 30%), sensitivity (over 40%) compared with the other algorithms. The highest accuracy of the ensemble-learning algorithm can reach 90%. Especially, the sensitivity can reach 100%. Moreover, the proposed algorithm was more stable, especially when combining the CART and RF algorithms, the mean classification accuracy can reach 86.5%. Conclusion: This proposed method can improve classification performance of PD with speech data compared with the relevant algorithms. The study can be a reference for the relevant researchers.