We propose two pre-processing steps to classification that apply convex hull- based algorithms to the training set to help improve the performance and speed of classification. The Class Reconstruction algorithm uses a clustering algorithm combined with a convex hull-based approach that re-labels the dataset with a new and expanded class structure. We demonstrate how this performance- improvement algorithm helps boost the accuracy results of Naive Bayes in some, but not all, cases that use real-world datasets.