Metric learning has been successful in learning new metrics adapted to numerical datasets. However, its development on categorical data still needs further exploration. In this paper, we propose a method, called CPML for categorical projected metric learning, that tries to efficiently (i.e. less computational time and better prediction accuracy) address the problem of metric learning in categorical data. We make use of the Value Distance Metric to represent our data and propose new distances based on this representation. We then show how to efficiently learn new metrics. We also generalize several previous regularizers through the Schatten p-norm and provides a generalization bound for it that complements the standard generalization bound for metric learning. Experimental results show that our method provides state-of-the-art results while being faster.