The main purpose of this paper is to deal with classification algorithm with feature selection is used to improve the prediction accuracy in the medical data. This paper applies best first search and greedy search as a searching methods and feature evaluator used as CFS. Naive Bayes classification algorithm is used for hepatitis patients’ dataset. It analyzes the data set taken from the UC Irvine machine learning repository. The result of the classification model is time and improved classification accuracy. Finally, it concludes that the proposed methodology performance is better than other classification algorithms.