Microblogging platforms like Twitter, Tumblr and Plurk have radically changed our lives. The presence of millions of people has made these platforms a preferred channel for communication. A large amount of User Generated Content, on these platforms, has attracted researchers and practitioners to mine and extract information nuggets. For information extraction, clustering is an important and widely used mining operation. This paper addresses the issue of clustering of micro-messages and corresponding users based on the text content of micro-messages that reflect their primitive interest. In this paper, we performed modification of the Similarity Upper Approximation based clustering algorithm for clustering of micro-messages. We compared the performance of the modified Similarity Upper Approximation based clustering algorithm with state-of-the-art clustering algorithms such as Partition Around Medoids, Hierarchical Agglomerative Clustering, Affinity Propagation Clustering and DBSCAN. Experiments were performed on micro-messages collected from Twitter. Experimental results show the effectiveness of the proposed algorithm.