Document clustering is an important tool for application such as Web search engines, also enables the user to have a good overall view of the information contained in the documents that he has. However, existing algorithms suffer from various aspects and cannot detect the multiples themes of a document. We propose an efficient soft clustering algorithm based on a given composite similarity measure. The algotithm require two similarity measure for clustering and uses randomization to help made the clustering efficient. Comparison with existing hard clustering algorithms like K-means and its variants shows that our clustering is both effective and efficient.The proposal to be presented as an alternative to traditional methods in Information Retrieval. © 2011 IADIS.