I.J. Information Engineering and Electronic Business, 2012, 1, 1-9Published Online February 2012 in MECS (/)DOI: 10.5815/ijieeb.2012.01.01Sentence Clustering Using Parts-of-SpeechRichard KhouryDepartment of Software Engineering, Lakehead University, Thunder Bay (ON), CanadaEmail: Richard.Khoury@lakeheadu.caAbstract—Clustering algorithms are used in many Natural Language Processing (NLP) tasks. They have proven to be popular and effective tools to use to discover groups of similar linguistic items. In this exploratory paper, we propose a new clustering algorithm to automatically cluster together similar sentences based on the sentences’ part-of-speech syntax. The algorithm generates and merges together the clusters using a syntactic similarity metric based on a hierarchical organization of the parts-of-speech. We demonstrate the features of this algorithm by implementing it in a question type classification system, in order to determine the positive or negative impact of different changes to the algorithm.Index Terms—natural language processing, Part-of-speech, clustering1. IntroductionClustering algorithms are used in many Natural Language Processing (NLP) tasks, from grouping words [1] and documents [2] to entire languages [3]. They are popular tools to use to group similar items together and discover the links between them. In this exploratory paper, we propose a new clustering algorithm to automatically discover and group together similar sentences based on the sentences’ part-of-speech syntax. As a clustering distance metric, we use a part-of-speech hierarchy which we developed in our past work [4]. We apply this clustering system to the task of discovering the informer spans that Krishnan et al. proposed in their work on question type classification [5], and our experimental results demonstrate that our clustering system generates interesting results relative to that application.The remainder of this paper is organized as follows. In Section 2, we review a representative sample of work done on NLP clustering system and in the task of question type classification, in order to clearly illustrate the nature of our contribution. The theoretical frameworks of our clustering algorithm and of our part-of-speech hierarchy are all presented in Section 3. Our ideas have all been implemented and tested, and experimental results are presented and discussed in Section 4. Finally, we offer some concluding remarks in Section 5.2.BackgroundClustering systems are already being used in several branches of Natural Language Processing (NLP). For example, the authors of [3] designed a spoken language recognition system that clusters spoken utterances based on their spectral features. Preliminary tests of their system showed comparable results to the baseline, which is encouraging given the large range of currently-unexplored refinements they could implement. In parallel, the authors of [6] proposed a language recognition system that works by clustering languages and then dividing them hierarchically into sub-clusters. These authors studied several distance metrics to measure the difference between languages, and finally settled on a fusion of measures. In this context, one could see the methodology presented in this paper as the development of a new distance metric based on parts-of-speech, to be used independently or with others in clustering algorithms. Another popular NLP task sometimes done with clustering is that of document topic identification. This one can be done more directly, by representing documents as word vectors and clustering the vectors according to their Euclidean Distance, Cosine Similarity, Jaccard Coefficient, or any other of the many possible vector distance metrics available [2], [7], or with probabilistic measures such as the Gaussian mixture model [8]. This further demonstrates how natural language text can be converted to a form usable by classical mathematical clustering algorithms. A final example, a little more closely related to this research, is the project on part-of-speech clustering presented in [1]. The author’s intuition is that they could improve on a unigram language model by differentiating between topic words, style words, and general words based on their parts-of-speech. To accomplish this, they developed a probabilistic clustering algorithm to group a set of 90 parts-of-speech into these categories using two corpora of text documents covering several different topics. Their system discovered appropriate clusters, which could then be successfully applied in a large vocabulary speech recognition system. While our project’s aim and clustering technique are different, their work does confirm that parts-of-speech clustering can be applied successfully in NLP applications.The clustering system we are developing in this research will be customized to learn clusters useful for the task of question type classification. Question type (or answer type) classification is the NLP task of determining the correct type of the answer expected to a given query, such as whether the answer should be a person, a place, a date, and so on. This classification task2 Sentence Clustering Using Parts-of-Speechis of crucial importance in question-answering (QA) systems, to allow them to retrieve answers of the correct type and to reject possible answers of the wrong type [9]. In fact, it has been shown that questions that have been classified into the correct type are answered correctly twice as often as misclassified questions [9]. Over the years, many varied approaches to question type classification have been proposed. For example, the authors of [10] used a Naïve Bayes classifier to compute the probability of a query belonging to one of six question types given the prior probability of that type multiplied by the conditional probability of the query’s features (i.e. the words left after stemming and stopword removal) given that type. Going in a different route, a team from the University of Concordia developed a simple but accurate keyword- matching question type classification system with a large manually-built lexicon as part of their QA system for the TREC-2007 competition [9]. The authors of [11] and [12] tried a similar approach using WordNet as a lexicon, but found that their systems could be misled in cases where the query’s syntax affected the meaning and importance of keywords. The authors of [12] took this a step further and added some question syntactic patterns in their system to deal with common problem phrasings. Finally, Zhang and Nunamaker [13] built a pattern-based question type classifier that classifies each user’s query according to a set of simple patterns that combine both the wh-terms (who, what, where, when, why, which, whom, whose, how) and the categories of keywords found in the query. It has been pointed out [5] that a common limiting factor in all these systems is the reliance on large unpublished knowledge bases, be it conditional probability tables, keyword lexicons, or lists of syntactic patterns. For our purposes, the most closely-related project is the one proposed by Krishnan et al. in [5]. They proposed that the patterns used for question type classification could consist simply of a short string of contiguous words found in the query, which may or may not include wh-terms, and which they called the informer span (or simply informer ) of the query. Their work shows clearly that a support vector machine classifier using hand-made informers yields better results than question bigrams, and that informers discovered automatically work almost as well as hand-made ones. Our work is related to theirs in the sense that, as we will explain later on, the centers of the clusters learned by our system correspond to informers that can be used for question type classification.3. MethodologyIn this paper, we develop a new system for sentence clustering based on the idea of informers and on a part-of-speech hierarchy that we present below. The objective of this algorithm, as for any clustering algorithm, is to discover the set of clusters that best represent the data. In general terms, this means having high intra-cluster homogeneity, a high inter-cluster heterogeneity, and a small number of clusters. The application we are dealingwith in this project is question type classification, because it has proven to be a challenging task to automate, as is evidenced by the number of manually-created solutions presented in Section 2, and because of the direct connection with our past work [14]. In this application, the objectives of the clustering algorithm are to learn the smallest set of clusters to allow the best type classification results.3.1 Part-of-Speech HierarchyA part-of-speech (POS) is commonly defined as a linguistic category of lexical items that share some common syntactic or morphological characteristics. However, it is telling that, despite the concept of a POS being thousands of years old, grammarians and linguists still cannot agree on what exactly the shared characteristics are. This question has very real practical consequences: depending on where the line is drawn between common characteristics and distinguishing differences, one can end up with anywhere from the eight parts-of-speech defined in English textbooks to the 198 parts-of-speech of the London-Lund Corpus of Spoken English [15].Our solution to this problem is to organize lexical items not into a single set of parts-of-speech but into a part-of-speech hierarchy. The lower levels of this hierarchy feature a greater number of finely-differentiated parts-of-speech, starting with the Penn Treebank POS tags at the lowest level, while the higher levels contain fewer and more general parts-of-speech, and the topmost level is a single all-language-encompassing “universe” part-of-speech. Another innovation has been the inclusion in our hierarchy of several “blank” parts-of-speech, to represent and distinguish between the absences of different types of words. In total, our hierarchy contains 165 parts of speech organized in six levels. We originally developed it in the context of a keyword-extraction project; a detailed description of the hierarchy can be found in the paper describing that project [4].We can define the semantic importance of different lexical items by assigning weights on the connections between POS in the hierarchy. This allows us to specialize the hierarchy for use in different NLP tasks. In our earlier work on keyword extraction [4], weight was given to verbs and nouns – the typical parts-of-speech of the keywords we were looking for. For question type classification, however, verbs and nouns are not the most semantically important words to take into account. Indeed, Tomuro [11] has shown that question type classification relies mostly on closed-class non-content words. The semantic weight in our hierarchy was thus shifted to the subtrees corresponding to popular query adverbs and pronouns, including wh-terms, and calibrated using queries from the 2007 TREC QA track [16] as examples. The value of each POS in our hierarchy is then computed on the basis of its semantic weight and of the number of descendents it has. The resulting hierarchy, with the value of each POS, is presented in Figure 1.We showed in [4] how using a part-of-speech hierarchy makes it possible to mathematically define several linguistic comparison operations. It is possible to compute the similarity between two words or POS simply as a function of their distance in the hierarchy. This computation takes several factors into account, including the number of levels in the hierarchy that need to be traversed on the path from one POS to the other and the value of each intermediate POS visited. Likewise, we can find a general place-holder POS to represent two words simply by finding the lowest common ancestor of both words in the hierarchy, and the similarity of the place-holder compared to the original two words it represents is again a function of the distance in the hierarchy between each word and the place-holder POS. By extension, we can measure the similarity between two sentences by pairing their words together by similarity; the fact that our hierarchy includes “blank” parts-of-speech means that the two sentences do not need to be of the same length to be compared. And finally, we can merge two sentences by pairing their words together by similarity and replacing each pair by its lowest common ancestor in the hierarchy.It is now straightforward to see how our part-of-speech hierarchy can be used for the task of question type classification. Given a list of informers representing different question types, we can use the hierarchy to compute the similarity between a user-specified query and each informer. The query is then classified to the same type as the informer it is most similar to.Fig 1: The POS hierarchy (POS values are in brackets).We implemented such a system in our work presented in [14]. The question types we used are “person” (who), “date” (when), “physical object” (what), “location” (where), “numeric value” (how many/how much), and “description” (how/why). The results presented in that paper show that a classifier based on our hierarchy can achieve an F-measure of 70% using only 16 basic informers, albeit with a strong bias for precision over recall. This stands in stark contrast to the other systems reviewed in Section 2, which need large sets of patterns, lexicons, or probability tables to work well. The 16 basic informers in that project were defined manually, but they are trivial two-word informers that combine each question type’s wh-term and one higher-level POS from our hierarchy that represents a past-tense verb (vbd), a present-tense verb (vbz), a description adjective (jj), a singular common noun (nn) or a plural common noun (nns). The informers are listed in Figure 2. Finally, it is worth noting a second result from [14], which is that using a learning algorithm to discover more informers allows the classifier to balance precision and recall without reducing F-measure.Who [vbz]Who [vbd]When [vbz]When [vbd]Where [vbz]Where [vbd]What [nn]What [nns]What [vbz]What [vbd]Why [vbz]Why [vbd]How [jj]How [nn]How [vbz]How [vbd]Fig 2: 16 basic informer spans from [14].3.2 Informer-Clustering AlgorithmIn our algorithm, each cluster combines together queries of the same type. The cluster’s center is defined as the generic query obtained by merging all queries in the cluster. Adding a query to the cluster is done by merging that query with the current cluster center. Splitting a cluster is also possible; when the generic query in the center contains a part-of-speech that is higher than a set threshold in the hierarchy, that part-of-speech is discarded and the query is split in two parts at that point. Each part becomes the center of its own new cluster, combining a copy of the set of queries of the original cluster. Given our discussion in the previous section, it can be seen that the cluster centers are the same as the informer spans we want the algorithm to learn.The pseudocode of the clustering algorithm we propose is presented in Figure 3. The algorithm takes in as input a list of training queries, which it will try to cluster. Optionally, we may also want to input some manually-defined application-specific informers, such as the 16 basic informers from our work in [14]. This would allow the system to consider clusters that we know to be valid. The impact of this additional input will be studied in the experiments in Section 4.The algorithm begins by pairing together all queries of each type according to their similarity to each other, with the constraint that each query can only be paired to one other query. The algorithm thus goes through the list of possible pairings, accepting them in order of decreasing similarity, and rejecting those that use queries that are already in more similar pairs. To illustrate, suppose a query type has four queries labeled A, B, C and D. The possible pairings are A-B, A-C, A-D, B-C, B-D and C-D, and the similarities between them (i.e. the distances between them in the POS hierarchy) are 5, 7, 9, 12, 8 and 15 respectively. The algorithm considers these pairs in order of decreasing similarity (increasing distance) starting with the most similar (least distant) pair, A-B. Since neither A nor B has been paired yet, this pair is accepted. The algorithm considers the other pairs in order; however all other pairs except one use either A or B, which is not allowed since they have already beenpaired, and thus are rejected. The last pair considered in order is the one with the lowest similarity (greatest distance), C-D. It is however the most similar acceptable pair for these queries, and is retained by the algorithm. This set of pairs is used by our algorithm as the initial set of clusters. This set will be naturally very large: at least half the size of the initial training set, and more if some of the clusters are split by the method described previously. Moreover, the informers of some of these initial clusters may not be useful to correctly classify queries into question types; they would typically be the result of splitting a cluster into two parts, one of which is irrelevant. For example, imagine two queries that are identical except for a completely different final word before the question mark. Merging these two queries together would give an informer that has a very general part-of-speech instead of the final word, and this informer would in turn be split into two, one that has all the words before the final one, and one that has everything after the final word, which is to say only the question mark at the end. Clearly, a question-mark-only informer is useless for classification! Consequently, the second step of our algorithm is to detect and remove these informers and clusters. This task is implemented by classifying the training set using the list of informers and deleting those informers that lead to more misclassifications than correct classifications, as illustrated in the pseudo-code of Figure 4. This is an optional step, however, since our algorithm can work whether or not it is executed. In our experimental results, we will study the impact of executing or skipping it. Steps 3 to 6 in our algorithm are the cluster merging steps. In this step, the algorithm considers all pairs of clusters, in order of decreasing similarity of their cluster centers. For each pair, the algorithm merges the cluster centers, and then evaluates the merged center. The quality of the merged cluster is evaluated and, if it is found to be better, the original clusters are discarded and the new cluster is added to the list of clusters for consideration. Otherwise, the new cluster is discarded and the two original ones are maintained. Several metrics could be used for this quality evaluation; in this study we will consider the similarity of the queries to the center and the classification results. In the first metric, we are comparing the quality of the new cluster to that of the original clusters. We compute the average similarity of the queries in each cluster to their respective cluster center to get the quality of the original clusters, and likewise the average similarity of the queries to the merged cluster center gives the new cluster’s quality. The cluster with the best average similarity is considered the one with the highest quality. For the second metric, we find the number of training queries that would be classified by the new informer corresponding to the cluster center, and count how many of these queries are correctly classified and how many are not. A cluster whose informer allows more correct classification than incorrect ones is considered to be of good quality. It should be noted that in this second metric, unlike in the first one, a merged cluster is accepted or rejected based on its own performance and not in comparison to the original two clusters it merges together. But either way, the algorithm can use a merger bonus to relax the acceptance criterion and allow the algorithm to accept bad mergers.The final step of the algorithm consists in a filtering task like the one optionally done in step 2. Earlier in the algorithm it was done to detect cluster that are not useful for type classification and eliminate them from consideration in the rest of the algorithm. Now it is done as a final step, to detect and eliminate similarly non-predictive clusters that have been learned through the repetitive merging and splitting of clusters in steps 3 to 6. This is again done using the filtering algorithm of Figure 4.Input: Training queries, initialinformers (optional), bonus1. Pair the training queries bysimilarity to get initial clusters 2. Filter non-predictive initialclusters (optional)3. For each pair of clusters, orderedby similarity4. Merge the two cluster centerstogether5. Evaluate the quality of themerger, and apply bonus6. If the merger is of goodquality, save the mergedcluster and discard theoriginal pair; otherwisediscard the merger and keep theoriginal pair7. Filter non-predictive clustersFig 3: Pseudocode of our clustering algorithm.Input: Training queries, list ofinformers, Threshold1. Do:2. Classify all training queriesto the most similar informer inthe list3. For each informer:4. NCorrect ← The number ofqueries of the correct typeclassified by this informer5. NIncorrect ← The number ofqueries of other typesmisclassified by thisinformer6. If NIncorrect*Threshold >NCorrect, remove informerfrom the list7. While informers are removed instep 6Fig 4: Pseudocode of the filtering step.4. Experimental ResultsFor our experiments, we built a training corpus of queries using the 459 queries from the 2007 TREC QA track [16]. We tagged the words of the queries with their4.1.1 Filtering initial clustersparts-of-speech using the standard Brill tagger, and we manually classified the queries into their correct question types. We used the data to run five-fold tests, breaking the data into five non-overlapping equal-sized sets of queries and successively training the system with four sets and testing with the fifth.One of the first options mentioned in Section 3.2 is whether or not to filter the initial set of clusters with the algorithm of Figure 4 before running the cluster-merging loop. The intuitive justification for this step is that if the system catches and eliminates non-predictive clusters early on, the merging algorithm will then focus on merging useful pairs of clusters together and learn valid general clusters.In each of the experiments, we used the centers of the final clusters generated by the algorithm as informers to classify the queries into each of our six question types, and we computed the precision and recall of the classification using the standard equations given in (1) and (2). We then computed the average precision and recall over all six types, and the average F-measure using equation (3).However, the results obtained in this test tell a different story. In our experiments, ignoring the one fold where the system fails and eliminates all clusters, we find that the initial filtering step takes out 28 clusters on average. As expected, after merging, the remaining clusters are more useful, and on average 22 fewer of them are eliminated by the final filtering step. However, this has no measurable impact on the final results of the algorithm. Compared to the default algorithm of the previous section, the final set of informers learned is almost identical with on average only one extra informer learned by the modified algorithm, and the classification results are absolutely identical. This indicates that the clustering algorithm we propose is resilient in the face of initial data of mixed quality, and that the final filtering step alone is enough to eliminate the bad informers learned. An initial filtering of the clusters is clearly unnecessary.PositiveFalse Positive True Positive True Precision +=(1)NegativeFalse Positive True Positive True Recall +=(2)RecallPrecision Recall Precision 2Measure F +××=− (3)4.1 ExperimentsWe thoroughly tested our clustering algorithm by using it to learn informers from our training corpus while varying one or another of the options we described in Section 3.2 and keeping the other options to their “default” settings. This will make it possible to clearly see the contribution and impact of each option we study. For ease of comparison, we listed the default settings of the algorithm in Table 1. The default version of the classifier learns on 69 clusters on average over the five-fold test, and classifying the final fold of training queries using the informers corresponding to the centers of these clusters gives on average a precision of 0.54, a recall of 0.50, and an F-measure of 0.52. However, it is worth noting that the system failed for one fold, by which we mean that the final filtering loop deleted all informers and left an empty set, which naturally gets 0.00 in all classification statistics. If we ignore that fold, the system learned on average 86 informers, and classifies with a precision of 0.68, a recall of 0.63, and an F-measure of 0.65. 4.1.2 Merged cluster evaluationIn section 3.2 we proposed two methods to evaluate merged clusters and determine whether or not a merger should be kept. The first method uses the part-of-speech hierarchy to compute the average similarity between the clustered queries and the cluster center, and compares it to the similarity in the original clusters to determine if an improvement has been made. The second method finds which queries are classified by the informer at the center of the cluster, and determines whether more correct than incorrect classifications are made. In both cases, we can use a bonus value to allow the merger of bad clusters. The bonus value varies from 0.0 to 1.0. A bonus of 1.0 requires that the merger be strictly an improvement, in the sense that it is either more similar or makes more correct classifications, while a lower bonus value allows some bad clusters, that either have a worse similarity or make more incorrect classifications. We should also note that the algorithm still performs the final filtering step before returning the clusters.Table 1：Default options and settings of the algorithm Option Default Initial informers None Filtering initial clusters Not done Quality evaluation algorithm Similarity Merging quality bonus 1.0 Threshold for final filtering1.0We can compare the two methods in terms of the final number of clusters the algorithm returns and of the f-measure of the classification of the test queries. We begin by considering the number of clusters, presented in Figure 5. It can be seen from this graphic that few clusters are returned at low values of the bonus. In fact, the algorithm is found to fail and return no clusters at all for many of the 5-fold tests in that range. The reason is that, lowering the bonus allows more mergers by tolerating worse and worse mergers. The resulting clusters are bad and taken out by the final filtering step, leading to the many empty sets observed in the results. Good clusters begin to appear and be retained at a bonusof 0.3 using the classification method and 0.4 using the similarity method, and the number of clusters peaks at 0.6 for the classification method and 0.7 for the similarity method. Finally, the number of clusters spikes for both methods at a bonus of 1.0, where the strict criteria prevents a lot of mergers. Overall, we find that the behaviors of both methods are very similar from thispoint of view.Fig 5: Number of clusters returned using different bonus values with the similarity method (black dashed line) and the correct classification method (solid grey line).The second comparison point is the average f-measure of the classification using the rules learned for each fold at each bonus value. That one is presented in Figure 6. The left-hand graph of that figure plots the overall f-measure, including the zeros that come from the folds where the algorithm failed. The varying number of zeros at each threshold causes the apparent instability of the results, and overall the shape of the curve follows closely the shape of Figure 5. To truly compare the performance of both methods, it is more informative to consider only those cases where the algorithm didn’t fail for either one. The average f-measure of those common cases is presented in the right-hand graph of Figure 6. As we can see in that graph, both methods perform about equally well. The differences visible in the left-hand graph are really only due to different numbers of failed folds.Fig 6: Classification f-measure using different bonus values with the similarity method (black dashed line) and the correct classification method (solid grey line) over all folds (top) and for folds that did not fail on both methods (bottom).We can note that the second method uses the same evaluation standard as the final filtering step, namely to use the cluster centers’ informers to classify the training queries and discard informers that do not lead to enough correct classifications. This leads to a final question: is the final filtering step still necessary, or is it redundant after this training? We ran the test again without the final filtering step to check. The first thing that appears from the results is that this version of the system never fails on a fold; there is no case in which the training ends up eliminating all clusters. This is not completely unexpected, since the filtering step is in charge of eliminating non-predictive informers; without this step, nothing gets eliminated and the algorithm is guaranteed to return something. However, the flip side is that the unfiltered set of informers returned is a lot larger than normal: between 80 and 120 informers, compared to the filtered version that returns on average 34 informers and never goes up to 80. This result is clearly at odds with one of our objectives, which is to generate a set of clusters that is as small as possible. The second thing to consider is whether this larger set of informers allows for better or worse classification of the unseen fifth fold of queries. When compared to the results in the left-hand graph of Figure 6, the classification results with the unfiltered set of informers appear to be a lot better. However, this is due to the fact that the comparison is not entirely fair: as we mentioned, the smaller set of informers fails on several folds and the zeros f-measures from these failures lower the average results, while the unfiltered informer set never fails and never returnsIt is interesting that both methods appear to be equivalent in performance, given that they are very different in implementation: one evaluates the cluster based on classification and the other based on similarity, and one compares the merged cluster to the original ones while the other compares it to its own failure cases. The fact that our overall algorithm performs as well using either methods points to the resilience of the entire system.。
