External beam radiotherapy is one of the standard treatments for prostate cancer. Despite advanced radiotherapy techniques allowing precise dose delivery on cancer targets, efficiency of the treatment is limited by the risk of side-effects due to the irradiation to the surrounding organs. Characterizing the local dose–toxicity relationship is crucial to provide new recommendations for treatment planning. Standing on a voxel wise analysis, in this paper we proposed a new method, named Discriminant Nonnegative Matrix Factorization (DNMF), for classifying patients at risk of presenting rectal bleeding. Comparative studies with a classical Nonnegative Matrix Factorization (NMF) algorithm and principal component analysis (PCA) based method are also given. The features extracted by the proposed method for different rank values are used to classify the planned dose distribution images into rectal-bleeding and non-rectal-bleeding. The sensitivity and specificity obtained on 118 patients (  and  ) show the DNMF as a promising method for predicting the toxicity-related side-effect in the rectum following prostate radiotherapy.