This disclosure describes one or more implementations of a model segmentation system that generates accurate audience segments for client devices/individuals utilizing multi-class decision tree machine-learning models. For example, in various implementations, the model segmentation system generates a customized loss penalty matrix from multiple loss penalty matrices. In particular, the model segmentation system can generate regression mappings of model evaluation metrics for a plurality of decision tree models and combine loss penalty matrices based on the regression mappings to generate a customized loss penalty matrix that best fits an administrator's customized needs of segment accuracy and reach. The model segmentation system then utilizes the customized loss penalty matrix to train a multi-class decision tree machine-learning model to classify client devices into non-overlapping audience segments. Further, in one or more implementations, the model segmentation system refines the multi-class decision tree machine-learning model based on adjusting the tree depth.