In this paper, a new approach is developed that focuses on different aspects of uncertainty when clustering categorical instances using possibility theory. Our proposal, called decremental possibilistic k-modes (DPKM), is an uncertain soft-clustering method based on decremental learning. First, it handles uncertain values by defining a possibility distribution for each attribute. Then, as a soft computing method, it computes the degree of belonging of each object to all clusters. After that, it deals with the decremental learning by removing the most dissimilar cluster to the objects. Hence, the proposed approach takes advantages from both uncertain soft-clustering and decremental learning by saving computing time and improving the clustering performance.