{'fraction_non_alphanumeric': 0.02996594778660613, 'fraction_numerical': 0.008626560726447218, 'mean_word_length': 4.783807439824946, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cluster Labeling by Word Embeddings and WordNet's Hypernymy

Cluster labeling is the assignment of representative labels to clusters obtained from the organization of a document collection. Once assigned, the labels can play an important role in applications such as navigation, search and document classification. However, finding appropriately descriptive labels is still a challenging task. In this paper, we propose various approaches for assigning labels to word clusters by leveraging word embeddings and the synonymity and hypernymy relations in the WordNet lexical ontology. Experiments carried out using the WebAP document dataset have shown that one of the approaches stand out in the comparison and is capable of selecting labels that are reasonably aligned with those chosen by a pool of four human annotators.


Introduction and Related Work
Document collections are often organized into clusters of either documents or words to facilitate applications such as navigation, search and classification. The organization can prove more useful if its clusters are characterized by sets of representative labels. The task of assigning a set of labels to each individual cluster in a document organization is known as cluster labeling (Wang et al., 2014) and it can provide a useful description of the collection in addition to fundamental support for navigation and search.
In Manning et al. (2008), cluster labeling approaches have been subdivided into i) differential cluster labeling and ii) cluster-internal labeling. The former selects cluster labels by comparing the distribution of terms in one cluster with those of the other clusters while the latter selects labels that are solely based on each cluster indi-vidually. Cluster-internal labeling approaches include computing the clusters' centroids and using them as labels, or using lists of terms with highest frequencies in the clusters. However, all these approaches can only select cluster labels from the terms and phrases that explicitly appear in the documents, possibly failing to provide an appropriate level of abstraction or description (Lau et al., 2011). As an example, a word cluster containing words dog and wolf should not be labeled with either word, but as canids. For this reason, in this paper we explore several approaches for labeling word clusters obtained from a document collection by leveraging the synonymy and hypernymy relations in the WordNet taxonomy (Miller, 1995), together with word embeddings (Mikolov et al., 2013;Pennington et al., 2014).
A hypernymy relation represents an asymmetric relation between a class and each of its instances. A hypernym (e.g., vertebrate) has a broader context than its hyponyms (bird, fishes, reptiles etc). Conversely, the contextual properties of the hyponyms are usually a subset of those of their hypernym(s). Hypernymy has been used extensively in natural language processing, including in recent works such as Yu et al. (2015) and HyperVec (Nguyen et al., 2017) that have proposed learning word embeddings that reflect the hypernymy relation. Based on this, we have decided to make use of available hypernym-hyponym data to propose an approach for labeling clusters of keywords by a representative selection of their hypernyms.
In the proposed approach, we first extract a set of keywords from the original document collection. We then apply a step of hierarchical clustering on the keywords to partition them into a hierarchy of clusters. To this aim, we represent each keyword as a real-valued vector using pre-trained word embeddings (Pennington et al., 2014) and repeatedly apply a standard clustering algorithm. For labeling the clusters, we first look up all the synonyms of the keywords and, in turn, their hypernyms in the WordNet hierarchy. We then encode the hypernyms as word embeddings and use various approaches to select them based on their distance from the clusters' centers. The experimental results over a benchmark document collection have shown that such a distance-based selection is reasonably aligned with the hypernyms selected by four, independent human annotators. As a side result, we show that the employed word embeddings spontaneously contain the hypernymy relation, offering a plausible justification for the effectiveness of the proposed method.

The Proposed Pipeline
The proposed pipeline of processing steps is shown in Figure 1. First, keywords are extracted from each document in turn and accumulated in an overall set of unique keywords. After mapping such keywords to pre-trained word embeddings, hierarchical clustering is applied in a top-down manner. The leaves of the constructed tree are considered as the clusters to be labeled. Finally, each cluster is labeled automatically by leveraging a combination of WordNet's hypernyms and synsets and word embeddings. The following subsections present each step in greater detail.

Keyword Extraction
For the keyword extraction, we have used the rapid automatic keyword extraction (RAKE) of Rose et al. (2010). This method extracts keywords (i.e., single words or very short word sequences) from a given document collection and its main steps can be summarized as: 1. Split a document into sentences using a predefined set of sentence delimiters.
2. Split sentences into sequences of contiguous words at phrase delimiters to build the candidate set.
3. Collect the set of unique words (W ) that appear in the candidate set.
4. Compute the word co-occurrence matrix X |W |×|W | for W .
7. Select the top T scoring candidates as keywords for the document.
Alternatively, RAKE can use other combinations of deg(w) and f req(w) as the word scoring function. The keywords extracted from all the documents are accumulated into a set, C, ensuring uniqueness.

Hierarchical Clustering of Keywords
A top-down approach is used to hierarchically cluster the keywords in C. First, each component word of each keyword is mapped onto a numerical vector using pre-trained GloVe50d 1 word embeddings (Pennington et al., 2014); missing words are mapped to zero vectors. Then, each keyword k is represented with the average vector − → k of its component words. Then, we start from set C as the root of the tree and follow a branch-and-bound approach, where each tree node is clustered into c clusters using the k-means algorithm (Hartigan and Wong, 1979). A node is marked as a leaf if it contains less than n keywords or it belongs to level d, the tree's depth limit. The leaf nodes are the clusters to be named with a set of verbal terms.

Cluster Labeling
As discussed in Section 1, we aim to label each cluster with descriptive terms. The labels should be more general than the cluster's members to abstract the nature of the cluster. To this end, we leverage the hypernym-hyponym correspondences in the lexical ontology. First, for each cluster, we create a large set, L, of candidate labels by including the hypernyms 2 of the component words, expanded by their synonyms, of all the keywords. The synonyms are retrieved from the WordNet's sets of synonyms, called synsets. Then, we apply the four following approaches to select l labels from set L: • FreqKey: Choose the l most frequent hypernyms of the l most frequent keywords.
• CentKey: Choose the l most central hypernyms of the l most central keywords.
• FreqHyp: Choose the l most frequent hypernyms.
• CentHyp: Choose the l most central hypernyms.
Approaches FreqKey and FreqHyp are based on frequencies in the collection. For performance evaluation, we sort their selected labels in descending frequency order. In CentKey and Cen-tHyp, the centrality is computed with respect to the cluster's center in the embedding space as the average vector of all its keywords The distance between hypernym h and the cluster's center is d( h is the average vector of the hypernym's component words. The labels selected by these two approaches are sorted in ascending distance order.

Experiments and Results
For the experiments, we have used the WebAP dataset 3 (Keikha et al., 2014) as the document collection. This dataset contains 6, 399 documents of diverse nature with a total of 1, 959, 777 sentences. For the RAKE software 4 , the hyper-parameters are the minimum number of characters of each keyword, the maximum number of words of each keyword, and the minimum number of times each keyword appears in the text, and they have been left to their default values of 5, 3, and 4, respectively. Likewise, parameter T has been set to its default value of one third of the words in the cooccurrence matrix. For the hierarchical clustering, we have used c = 8, n = 100 and d = 4 based on our own subjective assessment.

Human Annotation and Evaluation
For the evaluation, eight clusters (one from each sub-tree) were chosen to be labeled manually by four, independent human annotators. For this purpose, for each cluster, we provided the list of its keywords, K, and the candidate labels, L, to the annotators, and asked them to select the best l = 10 terms from L to describe the cluster. Initially, Figure 2: Precision at k (P @k) for k = 1, . . . , 10 averaged over the eight chosen clusters for the compared approaches.
we had considered asking the annotators to also select representative labels from K, but a preliminary analysis showed that they were unsuitable to describe the cluster as a whole (Table 1 shows an example). Although the annotators were asked to provide their selection as a ranked list, we did not make use of their ranking order in the evaluation.
To evaluate the prediction accuracy, for each cluster we have considered the union of the lists provided by the human annotators as the ground truth (since |L| was typically in the order of 150 − 200, the intersection of the lists was often empty or minimal). As performance figure, we have decided to report the well-known precision at k (P @k) for values of k between one and ten. We have not used the recall since the ground truth had size 40 in most cases while the prediction's size was kept to l = 10 in all cases, resulting in a highest possible recall of 0.25. Figure 2 compares the average P @k for k = 1, . . . , 10 for the four proposed approaches. The two approaches based on minimum distance to the cluster center (CentKey and CentHyp) have outperformed the other two approaches based on frequencies (FreqKey and Fre-qHyp) for all values of k. This shows that the word embedding space is in good correspondence with the human judgement. Moreover, approach Cen-tHyp has outperformed all other approaches for all values of k, showing that the hypernyms' centrality in the cluster is the key property for their effective selection.

Visualization of Keywords and Hypernyms
Hypernyms are more general terms than the corresponding keywords, thus we expect them to be in larger mutual distance in the word embedding  space. To explore their distribution, we have used two-dimensional multidimensional scaling (MDS) visualizations (Borg and Groenen, 2005) of selected clusters. For each cluster, the keywords set K, the hypernyms set L, and the cluster's center have all been aggregated as a single set before applying MDS. An examples is shown in Figure 3. As can be seen, the hypernyms (blue dots) nicely distribute as a circular crown, external and concentric to the keywords (black dots), showing that the hypernymy relation corresponds empirically to a radial expansion away from the cluster's center. This likely stems from the embedding space's requirement to simultaneously enforce meaningful distances between the different keywords, the keywords and the corresponding hypernyms, and between the hypernyms themselves. The hypernyms selected by the annotators (green and magenta dots) are among the closest to the cluster's center, and thus those selected by CentHyp (red and magenta dots) have the best correspondence (magenta dots alone) among the explored approaches.

A Detailed Example
As a detailed example, Table 1 lists all the keywords of a sample cluster and the hypernyms selected by the four human annotators and CentHyp. Some of the hypernyms selected by more than one annotator (e.g., "electronic communication", "web page" and "computer file") have also been successfully identified by CentHyp. On the other hand, CentHyp has selected at least two terms ("commercial enterprise" and "reference book') that are unrelated to the cluster. Qualitatively, we deem the automated annotation as noticeably inferior to the human annotations, yet usable wherever manual annotation is infeasible or impractical.

Conclusion
This paper has explored various approaches for labeling keyword clusters based on the hypernyms from the WordNet lexical ontology. The proposed approaches map both the keywords and their hypernyms to a word embedding space and leverage the notion of centrality in the cluster. Experiments carried out using the WebAP dataset have shown that one of the approaches (CentHyp) has outperformed all the others in terms of precision at k for all values of k, and it has provided labels which are reasonably aligned with those of a pool of annotators. We plan to test the usefulness of the labels for tasks of search expansion in the near future.