In assessing the authenticity of art work it is of high importance from the art expert point of view to understand the reasoning behind it. While complex data mining tools accompanied by large feature sets extracted from the images can bring accuracy in paintings authentication, it is very difficult or not possible to understand their underlying logic. A small feature set linked to a minor classification error seems to be the key to understanding and interpreting the obtained results. In this study the selection of a small feature set for painting classification is done by the means of building an optimal pruned decision tree. The classification accuracy and the possibility of extracting knowledge for this method are analyzed. The results show that a simple small interpretable feature set can be selected by building an optimal pruned decision tree.