Paraphrase Extraction involves the discovery of equivalent text segments from large corpora and finds application in tasks such as multi-document summarization and document clustering. Semantic similarity identification is a challenging problem which is further compounded by the large size of the corpus. In this paper a two-stage approach which involves clustering followed by Paraphrase Recognition has been proposed for extraction of sentence-level paraphrases from text collections. In order to handle the ambiguity and inherent variability of natural language a fuzzy hierarchical clustering approach which combines agglomeration based on verbs and division on nouns has been used. Sentences within each resultant cluster are then processed by a machine-learning based Paraphrase Recognizer to discover the paraphrases. The two-stage approach has been applied on the Microsoft Research Paraphrase Corpus and a subset of the Microsoft Research Video Description Corpus. The performance has been evaluated against an existing k-means clustering approach as well as cosine-similarity technique and Fuzzy C-Means clustering and the two-stage system has consistently demonstrated better performance. 
Paraphrase Extraction using fuzzy hierarchical clustering