In the present day scenario, there are a large number of clustering algorithms available, to group objects having similar characteristics. But, the implementation of most of these algorithms is challenging due to the fact that most of the datasets involve categorical data values. Again, those algorithms which are capable of handling categorical data are mostly unable to handle uncertainty and some of them are involved with the stability issues. This necessitated the development of algorithms for clustering categorical data while handling uncertainty. In an effort to solve these problems an algorithm, termed MMR [1] was proposed in 2007, which uses the basic rough set theory concepts to deal with the above problem in clustering categorical data. Later in 2009, another algorithm, termed MMeR was proposed [2], which is more efficient than MMR and also has the capability of handling heterogeneous data. In this paper, we further improve MMeR and propose an algorithm, which we call SDR (Standard Deviation Roughness) algorithm It is capable of handling heterogeneous data besides taking care of uncertainty. We establish its efficiency over many other algorithms using well known standard data sets for the purpose of testing and the purity ratio as the measure of efficiency. © 2011 IEEE.