Clustering of semantically enriched short texts

Over the last decade, short text clustering has become an active research area in many tasks of Natural Language Processing (NLP). The methods are especially important in grouping the results of information retrieval, mainly in order to reveal various meanings within groups of results. Generally, the methods are based on representing text as a bag-of-words (bow), and grouping texts on the basis of their lexical similarity. Most approaches are focused on documents containing at least the size of few tens of words (Ferragina and Scaiella 2012), or a web snippet (Di Marco and Navigli 2013), or a paragraph (Shrestha et al. 2012).¹

There are various issues that impact clustering quality. Di Marco and Navigli (2013) indicate ambiguity of texts as one of the main problems. Another issue, addressed by Pinto et al. (2007), is the problem with clustering short texts with narrow domain characteristics. In any case, the length of texts seems to be the main issue; therefore the clustering of short texts, such as snippets, micro-blogs, short texts in questionnaires, etc., has recently become an important challenge.

Actually, the difficulties with short text clustering result from text ambiguity and the lack of a significant number of features in document vectors. Solutions for this are usually based on semantics injection, i.e., by expanding features with additional external information or by assigning meaning to the textual layer of documents (see e.g. Metzler et al. (2007)).

The problem is even more difficult with small text collections containing very short texts (Kotlerman et al. 2015, 2017). One can identify various applications that require the clustering of small text collections composed of a few hundred very short texts. Typical examples include the clustering of transcripts of calls in call centers for the analysis of user interactions, or the clustering of incoming stream of short news articles.

Our problem results from practical needs. In particular, a company runs a business, which consists in organizing brain-storming seminars for the staff of their clients. During the seminars, participants answer a series of questions. A back-office application clusters responses so that one can identify problems in the client’s company. The clusters of responses are presented to the audience in almost real time in order for strong ideas and weak signals easily to be identified. Participants can react to the results and create a dialogue. All the participants’ responses are free text answers. The answers are short, often incomplete, and highly biased toward the questions, so establishing a measure of proximity between such texts is a difficult issue.

Although we begin with a specific task, we would like to analyze it in a more general way. Kozlowski and Rybinski (2017b) have shown interesting features of the SnS algorithm, which is a novel text mining approach to sense induction. SnS is a knowledge-poor algorithm, and to a large extent it is a language independent approach. It has been also shown that, based on SnS, it is possible to build an efficient text clustering algorithm, named SnSRC.

This paper is an extension of Kozlowski and Rybinski (2017a), presented on ISMIS ’2017. Here, we provide a detailed description of the SnSRC algorithm, and present its improvements, as compared to the ISMIS version. Additionally, in this paper, we discuss various ways of expanding text features in more detail. We have verified a number of well-known short text clustering approaches, including data-centric, description-centric, and semantically-enhanced ones. Here, we provide more experiments with SnSRC and other clustering algorithms, combining the considered algorithms with data expansion methods, and showing how, in general, the semantic enrichment can influence the quality of clustering algorithms.

The paper is structured as follows: In Section 2 we discuss related work. Section 3 is devoted to presenting general concepts concerning SnSRC. Then in Section 4 we present our approach in more detail. Section 5 discusses the experiments and Section 6 presents the obtained results. The conclusions are in Section 7.

The clustering of short texts is an emerging field of research. Because of the shortness of the texts and the sparsity of the occurrences of terms, short texts suffer from a lack of contextual information, which may lead to their ambiguity. As most words occur only once in a short text, the representation of texts by term frequency-inverse document frequency (tf-idf ) vectors cannot work well in this case. Without any contextual information and with only a small number of words available in the document, achieving semantic comparisons at an acceptable level is a challenge.

The problems with short texts can be analyzed from various points of view. An overview of the issues is presented by Shrestha et al. (2012). Here, the authors consider several classical data mining clustering algorithms (Complete Link, Single Link, Average Link Hierarchical clustering and Spectral clustering), and analyze various quality measures from the point of view of the usability of the clustering results, concluding that the values given by the evaluation methods do not always represent the readability of the clusters.

The issue of similarity measure is discussed by Sahami and Heilman (2006). The authors propose a novel method for measuring the similarity between short text snippets (even those without any overlapping terms) by leveraging web search results to provide a wider context for short texts. Then, a similarity kernel function is defined, so that it works with the use of initial texts and Google search engine.

The issue of similarity measure is also discussed by Metzler et al. (2007). The authors study the problem from an information retrieval perspective. As for short texts the standard text similarity measures perform poorly the authors analyze usefulness of purely lexical measures, stemming, and language modeling-based measures.

One of the approaches to short text clustering is to enrich the representations of texts with semantics. In order to address the problem, some research focuses on the semantic enrichment of the context of data from external knowledge resources (Hu et al. 2009; Hotho et al. 2003). These proposals are still far from helping to achieve high-level quality clustering; therefore we decided to conduct research on semantic enrichment with the use of new semantic-oriented approaches, namely the BabelNet eco-system,² and with neural-network based distributional semantic models.

In general, one can distinguish three main groups of methods: those based on surface representation; sense-enhanced ones; and those based on enriching texts with additional terms from external resources. Below we discuss them in more detail.

In many text-oriented research areas it is common practice to classify words on the basis of their co-occurrence with other words. In fact, this idea is behind the well known distributional hypothesis, which has been explored thoroughly in the field of research in distributional semantics. It says that words with similar contexts will have similar meanings (”you shall know a word by the company it keeps” (Firth 1957)). The related techniques vary, starting from basic word co-occurrence matrices, where a vector associated with a given word is created by counting the words that appear in its immediate context (determined by a window of a certain size), and concluding with latent semantic indexing.

Our approach is also grounded on this hypothesis. So, if a term appears in various texts in a similar context, it probably refers to the same meaning. Additionally, we presume that there is only one meaning of the term in one text, even if the term occurs more than once in the text. This assumption has two implications: Further on, we assume that contexts are expressed by closed frequent sets (Pasquier et al. 1999). The set of all closed sets is the lossless representation of all frequent sets in the sense that it uniquely determines the set of all frequent termsets and their exact frequencies. At the same time, the number of closed frequent sets extracted from a corpus can be orders of magnitude smaller than all frequent sets (i.e., all contexts), which means that the set of all closed sets is a concise representation of all possible contexts. Actually, the idea of closed frequent termset is similar to the notion of concept, originated from the elegant mathematical framework of Formal Concept Analysis (Ganter and Wille 1999). In the area of data mining, closed frequent termsets have (by definition) the feature by which none of their super-sets has the same frequency. So if X and Y are closed termsets, such that X ⊂ Y, we assume that X (more frequent in the corpus than Y ) represents a more general meaning than Y. As a result, we are able to discover hierarchies of senses, instead of a flat list of senses.

Let us define the main notions in a formal way. By R we denote a repository, which is composed of a set of texts \(\mathcal {P}\). Given the repository R, we can extract a dictionary \(\mathcal {D} = \{t_{1}, t_{2},\ldots , t_{m}\}\) composed of terms – either simple terms (one-word terms) or compound terms, usually n-grams. In our experiments dictionary \(\mathcal {D}\) will be used for building contexts of a term for which we look for senses. We consider two cases: (a) we limit the dictionary only to nouns and noun phrases (usually multi-word terms denoting concepts, definite named entities, etc.), and (b) we build the dictionary from all the words except stop-words. The dictionary may contain both, the terms for which we search for senses, and terms that are used for building contexts. Any set \(X \subseteq \mathcal {D}\) of terms will be called termset.

By \(\mathcal {P}(t) \subseteq \mathcal {P} \) we denote a set of all texts containing term t. In other words \(\mathcal {P}(t)\) is a set of texts retrieved by a query t. For termsets X and Y we write XY to denote X ∪ Y. Similarly, for {t}∪ X we just write tX. The statistical significance of a termset X in the text repository R is measured by the number of texts, in which all the terms t ∈ X are present. The number of such texts is called support, and it is denoted by sup(X). Termset X is called frequent if it occurs in more than ε texts in R, where ε is a user-defined support threshold. Additionally, X is called closed frequent termset iff So, X is a closed termset if any of its (proper) supersets has lower support. We say that X is a context of t if sup(tX) > 0 in R.

Now we define a notion of contextual patterns for t. By F(t) we denote a set of all frequent termsets in \(\mathcal {C}(t)\). In addition, by CF(t) we denote closed frequent termsets in \(\mathcal {C}(t)\).

In cases when the corpus is large and representative for the discovered senses, i.e., all the senses of given terms are represented in a sufficient number of texts, sense frames correspond to distinctive senses. In the cases where the corpus is limited, two or more sense frames may refer to the same sense. Therefore, there is a need to compare frames of singletons or less representative senses, and identify similar frames in order to group them into sense clusters. The main idea for merging two or more sense frames is that there are no terms discriminating one sense from the other. Such discriminating terms will be called discriminants. Formally, the notion of discriminant is defined below:

The sense representation S, also called sense cluster, is a set of similar sense frames. Let root(x) denote the root of a sense frame x (the main contextual pattern in a sense frame); and seed(S) denote a sense frame with the highest position in \( \mathcal {S}\mathcal {F}(t)\) (having the root with the highest support) compared to the other sense frames in the sense cluster S. Finally, the sense is defined as a group of similar sense frames, such that either each clustered sense frame x has root(x) ∈ PND(t, root(seed(S))), or it fulfills the expression senseFrameSim(seed(S), x) > σ, where σ is a user-defined threshold, and given sense frames \(x,y \in \mathcal {S}\mathcal {F}(t)\) the function senseFrameSim is defined as cosine similarity:⁷where t2v(x) and t2v(y) denote the mean vectors of the word embeddings from two bows, each obtained as the union of all content words of contextual patterns building sense frames x and y respectively.

As mentioned above, SnSRC is a clustering algorithm using the SnS method, which is knowledge-poor. On the basis of the discovered sense frames, SnSRC maps texts to senses, giving, as a result, final clusters. Below we describe the sense induction algorithm SnS and based on it the clustering algorithm SnSRC.

One of our first tasks was to find the best knowledge-poor clustering method for texts provided by the company. Hence, we tested four algorithms: data-centric (Bisecting k-means), two description-centric algorithms (Lingo by Osinski and Weiss (2005), and STC by Zamir and Oren (1998)), and our solution SnSRC (a sense-enhanced algorithm). Then, we performed experiments aiming at verifying how semantic enrichment can improve short text clustering. For the semantic enrichment of the texts we have used two approaches: (1) Babel eco-system (Babelnet, Babelfy), and (2) neural-network based distributional models, for which we used the Word2vec tool.

As a first step of our experiments, we compared one general-purpose clustering algorithm (Bisecting k-means), and three text-oriented ones (STC, Lingo and SnSRC), all of them run on the company data, and without semantic enrichment. Let us note that Bisecting k-means requires defining a priori the number of resulting clusters, whereas the other algorithms automatically determine the number of clusters. Therefore in this phase we performed two series of experiments: the first one with a limited number of clusters,¹⁸ and the second one with Bisecting k-means run with a predefined limitation k, while Lingo, STC and SnSRC were used in a way where k was defined automatically by the algorithms. Clearly, in the case where the clustering algorithm automatically determines the number of clusters during its run, it is important how much the number of clusters obtained differs from the number of clusters in the gold standard. Therefore, in the results of our experiments we provide both the average number of clusters and the average number of clusters in gold standards.

The results of experiments from this phase are provided in Table 2a and b. Table 2a presents the following results: for Bisecting k-means the number of clusters to be obtained was set to the optimal value k. In the case of STC, Lingo and SnsRC, the evaluations were performed without defining apriori any limitation for the number of resulting clusters. Table 2b shows the results for the case where STC, Lingo, and SnSRC also had a defined limited number of clusters k. As one can see, for French ultra short texts, only text-oriented clustering methods give reasonable results, whereas the clustering quality of Bisecting k-means in these experiments is very low. In addition, SnSRC outperforms STC and Lingo in both cases.

The second series of experiments was performed in order to verify how the text-oriented clustering algorithms work with other data. We applied the algorithms for clustering the AMBIENT and MORESQUE data sets. Let us recall that both sets contain longer texts that are in English (yahoo snippets). In addition, the MORESQUE data set is semantically very heterogeneous, which results in knowledge-poor algorithms that provide much worse results. To this end we tested the algorithms for two combinations of data; namely (a) the AMBIENT + MORESQUE data sets, and (b) the AMBIENT data set only. Table 3a shows the clustering measures for these algorithms for AMBIENT + MORESQUE, while Table 3b presents the measures for AMBIENT data only. This experiment confirms a very low quality of Lingo and STC for heterogeneous texts. SnSRC also reveals lower quality, but it is still much better than Lingo and STC. In addition, even for more advantageous data the SnSRC algorithm outperforms the other tested algorithms.

In the last series of experiments we focused on analyzing how semantic enrichment of texts influences the clustering quality. Here, we experimented with Lingo and SnSRC. The experiments were run on the AMBIENT data (Table 4), and for UltraShortAnswers data (Table 5). For semantic enrichment we used the BabelNet tools, and Word2vec, as described in Sections 5.1.2 and 5.1.3 respectively. In both tables the first row presents the baseline, which corresponds to the algorithm without the semantic enrichment of texts. The next rows present the results obtained with the evaluated types of semantic enrichment of texts – specifically the first four rows with BabelNet tools, and the last two rows with Word2vec:

Table 4 presents the results for Lingo (left table) and SnSRC (right table). As one can see, for both tested algorithms an improvement can be obtained through the approach labeled as Babel-synsets, i.e., consisting in disambiguating texts with the Babelfy tools and adding appropriate synsets to the texts. The relative improvement for Lingo and SnSRC applied on the AMBIENT data sets is some 2,87% and 5,87% respectively. On the other hand, the approaches labeled Babel-categories, Babel-glosses, and Babel-hypernyms do not improve either of the tested algorithms.

Let us also note that both semantic enrichment approaches based on Word2vec improve the original clustering algorithms. What is interesting here is that in both cases the model trained on the corpus (Word2Vec-2) gives essentially better results than the model trained on Wikipedia (i.e., Word2Vec-1).

Finally, we performed tests with SnSRC for the French seminar data. Table 5 shows the results obtained by SnSRC for the French seminar data. Let us note that with the Babel-synset approach the quality of the SnSRC clustering for the UltraShort data set is better, however the improvement is not so meaningful as for AMBIENT. This may result from too short texts in the UltraShort data set. As in the case of AMBIENT + SnSRC and AMBIENT + Lingo, the other BabelNet approaches do not improve the French data set clustering either.

In the case of French data, i.e., the data containing ultra short texts, the experiments also showed that the best clustering results are obtained for texts enriched by Word2Vec-2. The relative improvement against the baseline reached 8,89% in this case.

As can be noted, in all experiments for both Lingo and SnSRC Word2Vec-2 outperforms Word2Vec-1. It seems to result from the fact that the texts enrichments coming from the models built on the domain-oriented texts are more relevant than those built on a general purpose repository, like Wikipedia.¹⁹

We used some tools for French language, namely PoS tagging and spell-checker. Still, some more advanced language-oriented tools could be probably applied, so one may expect an additional improvement with such tools. Our experiments show the value of SnSRC as a knowledge-poor approach, especially suitable for the cases where no advanced language means are available.

In the paper we have presented an approach to clustering small to medium text corpora containing very short texts, which is based on the semantic enrichment of the texts. The semantic enrichment in the preprocessing step is a general-purpose approach. It expands the initial texts with additional features (tokens representing categories, synsets, glosses, hypernyms, or similar words), and does not influence the text clustering methods. The clustering methods still receive texts as an input, which can be interpreted as bag of words, so this methodology can be very easily deployed.

We tested four text enrichment methods that are based on the BabelNet/Babelfy resources, and two methods that are based on neural network based distributional models. The methods were applied for three knowledge-poor text clustering algorithms, namely STC, Lingo, and SnSRC. They represent two various text clustering approaches, namely description centric text clustering (STC and Lingo), and sense-enhanced text clustering (SnSRC).

The first phase of our experiments was devoted to the evaluation of the three text-oriented clustering algorithms, i.e., STC, Lingo and SnSRC, and Bisecting k-means, which is a general purpose clustering algorithm. The algorithms were tested with the ultra-short French texts from brain-storming seminars. It was shown that only text-oriented clustering methods give reasonable results for French ultra short texts, whereas the clustering quality of Bisecting k-means in these experiments is very low. In these experiments we also showed that SnSRC outperforms the other two text-oriented algorithms, especially in the case when the number of clusters is not predefined.

The second phase of experiments was devoted to verifying how the text-oriented clustering algorithms work with other data. In the experiments the algorithms were tested for two cases: (1) the combination of data sets AMBIENT + MORESQUE , and (2) AMBIENT only. Both data sets contained longer snippets (in English). The texts in these experiments are 2-3 times longer than in the case of French data set. Additionally, MORESQUE is the data set that introduces ambiguous texts. The first experiment showed that with the introduced ambiguity the algorithms Lingo and STC do not work properly, whereas SnSRC provides reasonable results. The experiments with the data set limited to AMBIENT showed much better results, with SnSRC still outperforming Lingo and STC.

The last series of experiments were devoted to testing the idea of semantic enrichment. Based on the previous experiments, for this series we chose SnSRC and Lingo. The two algorithms were applied to the AMBIENT data set. In particular, we tested how enhancing short texts with semantic features from BabelNet/Babelfy influences the quality of clustering. Then we performed experiments with the neural network based distributional model.

The experiments concerning semantic enrichment for both data sets showed that among the approaches using BabelNet tools, only the Babel-synsets approach provided better results, whereas the other approaches did not improve the clustering quality. In particular, the enrichment of texts by corresponding categories, hypernyms and glosses reduced the clustering quality for both algorithms when compared to the baseline solutions. On the other hand, the semantic enrichment by Babel-synsets increased the quality of both algorithms. Also, in the case of the AMBIENT data set the results were much better than for the ultra-short French data. This confirms that the results of semantic enrichment are better for longer texts.

The experiments with the neural network based models (implemented by means of Word2vec) showed much better results than other semantic enrichment methods for both algorithms and for both data sets. In particular, the models trained with the texts from the repository to be clustered outperform the models trained on Wikipedia. In the case of data from seminars enriching the texts by Word2Vec-2 increases ARI by 1.44% when compared to the baseline; this is a relative improvement of 8.89% over the baseline. The experiments show that in the case of very short texts and small corpora the SnSRC algorithm outperforms the classical data-centric and description-centric algorithms. Moreover, the semantic enrichment of texts by applying neural networks can additionally improve the clustering quality, especially in the case of a specific domain language.

In the future we plan improving the core steps in the proposed method, namely (1) sense induction method, and (2) automatic summarization method. Recently high attention is given to the possibilities of using deep learning in the context of text processing. For example, Xu et al. (2017) propose a flexible self-taught convolutional neural network framework for short text clustering, which can learn non-biased deep text representation in an unsupervised manner. Generally, the key improvement of deep learning approaches is an essential reduction of data sparsity and the compactness of the lexical representations. This comes, unfortunately, at the expense of flattening information by merging the meanings of ambiguous words into a single vector representation. Therefore, we plan to investigate deep learning based methods, capable of capturing lexical semantics and syntactic relations, coping with the imbalanced semantic distribution. More importantly, a real challenge concerning neural approaches is their explainability. We plan to address this problem, as well.