While supervised learning of over-parameterized neural networks achieved state-of-the-art performance in image classification, it tends to over-fit the labeled training samples to give inferior generalization ability. Output regularization deals with over-fitting by using soft targets as additional training signals. Although clustering is one of the most fundamental data analysis tools for discovering general-purpose and data-driven structures, it has been ignored in existing output regularization approaches. In this article, we leverage this underlying structural information by proposing Cluster-based soft targets for Output Regularization (CluOReg). This approach provides a unified way for simultaneous clustering in embedding space and neural classifier training with cluster-based soft targets via output regularization. By explicitly calculating a class relationship matrix in the cluster space, we obtain classwise soft targets shared by all samples in each class. Results of image classification experiments under various settings on a number of benchmark datasets are provided. Without resorting to external models or designed data augmentation, we get consistent and significant reductions in classification error compared with other approaches, demonstrating that cluster-based soft targets effectively complement the ground-truth label.