KULCQ: An Unsupervised Keyword-based Utterance Level Clustering Quality Metric

For a given object x belonging to cluster y, the Silhouette coefficient Rousseeuw (1987) is defined as a combination of its intra-cluster metric and inter-cluster metric. The intra-cluster measure is defined as $a(i)=$ average dissimilarity of x to all other objects of cluster y. The inter-cluster metric is defined as:

$$b(x)=min_{i\in C,i\neq y}d(x,i)$$

in which $C=\{1,2,...,N\}$ is the set of all clusters and $d(x,i)$ is defined as: $d(x,i)=$ average dissimilarity of object x to all objects of cluster i. Finally, $a(x)$ and $b(x)$ are aggregated as:

$$silhouette(x)=\frac{b(x)-a(x)}{max\{a(x),b(x)\}}$$

Similar to the Silhouette method, the KULCQ score is a combination of an intra-cluster measure, and an inter-cluster measure. Let us say we have a set of $N$ clusters $C=\{1,2,...,N\}$. Each cluster $i$ includes the set of utterances $U_{i}$. First, we extract keywords from each utterance. The keywords from each utterance are a combination of keywords extracted from the utterance using two libraries - KeyBERT¹¹1https://github.com/MaartenGr/KeyBERT and YakeCampos et al. (2020). KeyBERT defines keywords as the words that are most similar to the document as a whole in terms of embeddings, the similarity metric being cosine similarity. Yake on the other hand uses statistical features to identify and rank the most important keywords. Thus, we use a combination of these two methods to get the keywords from each utterance. A keyword can either be a unigram or bigram. Based on the utterance keywords over the entire cluster, we find the top $n$ most frequent keywords in each cluster ($K(cluster_{i})$ denotes the top $n$ most frequent keywords for cluster $i$, $i\in C$). A centroid for each cluster $i$ ($c_{i}$) is calculated as the weighted average of its utterances:

$$c_{i}=\sum_{j\in U_{i}}{w_{i}^{j}\times R(u_{j})},$$

in which $U_{i}$ is the set of utterances belonging to cluster $i$ and $R(u_{j})$ is the representation of $u_{j}$ using an embedding method. Weight of utterance $j$ for calculating the centroid of the cluster $i$ is the proportion of the top $n$ frequent keywords appearing in the utterance. More precisely:

$$w_{i}^{j}=\frac{K(cluster_{i})\cap K(utt_{j})}{|K(cluster_{i})|}.$$

The intra-cluster score is calculated for the cluster as a whole, which is then assigned as the intra-cluster score to each of the utterances in the cluster. The intra-cluster metric is defined as the average of of the distances from each utterance to the centroid which was calculated for the cluster.

$$a(x)=\frac{1}{|U_{i}|}\sum_{j\in U_{i}}{D(R(u_{j}),R(c_{i}))},$$

in which $D$ is a distance function (we use cosine distance in our experiments). The inter-cluster metric for utterance $x$ which belongs to cluster $y$ is defined as the weighted average of distances of utterance $x$ to the centroids of other clusters:

$$b(x)=\sum_{i\in C,i\neq y}{{w^{\prime}_{i}}^{y}\times D(R(x),R(c_{i}))}.$$

We calculate ${w^{\prime}_{i}}^{y}$ as the reciprocal of the number of overlapping top $n$ frequent keywords between the clusters $i$ and $y$,

$${w^{\prime}_{i}}^{y}=\frac{1}{K(cluster_{i})\cap K(cluster_{y})}.$$

By using the reciprocal of the number of overlapping keywords between clusters as a weight while calculating the inter-cluster distance, we discourage different clusters from having a similar set of the most important keywords, and encourage different clusters to be far away from each other - in terms of the most important keywords of each cluster. Finally, the KULCQ score for an utterance is calculated by combining the inter- and intra-cluster scores of the utterance, similar to Silhouette:

$$KULCQ(x)=\frac{b(x)-a(x)}{max\{a(x),b(x)\}}$$

We conducted this experiment to test the correctness of KULCQ. We observe the values given by the Silhouette and KULCQ metrics when different amounts of noise are injected into the clusters. Noise here is defined as the perturbation to a cluster by taking utterances from its correctly assigned cluster and putting it into a different(wrong) cluster, and vice versa. Given the annotated clusters, we perturb the cluster of each utterance with probability $p$. In figure 1 we observe that both the KULCQ and Silhouette scores drop as we inject more noise. This validates the behavior of our metric, and proves that it follows the trends of standard metrics. The result of this experiment also validates that our proposed metric reflects the noise in the clustering. Moreover, we can see in figure 1, that the KULCQ metric is more sensitive to noise injection in a cluster. The drop in KULCQ values are much more as compared to the drop in Silhouette values when the probability of perturbing each utterance’s label is increased.

Here we depict the scenario where having a clustering evaluation metric specific to conversational or text data such as KULCQ is more helpful compared to a domain agnostic metric such as the Silhouette score. We specifically focus on clusters whose utterances due to minor differences in the words present, end up far from each other in the embedding space. In figure 2 we show the cluster “supported cards and currencies" from Finance dataset as a TSNE van der Maaten and Hinton (2008) plot. At first glance it does not seem to be a great cluster, because its utterances have been divided into three regions. The Silhouette coefficient reflects this immediate conclusion, and gives us a low average Silhouette score for utterances of this cluster, based purely on the geometry of the cluster. The Silhouette score for this cluster is $-0.05$ which is the second lowest score among the $77$ clusters of the Finance dataset. However, based on the KULCQ scores, this cluster ranks as the $26th$ highest. KULCQ’s judgement turns out to be more reasonable as we look at the cluster and its utterances more closely. We observe that region A includes utterances that talk purely about credit cards (e.g. “What US cards do you accept?", “Do you accept US credit cards?"), region B includes the utterances that talk purely about currencies (e.g. “What currencies can I use?", “Do you have a list of the cards and currencies supported?") and region C’s most important keyword is a specific bank’s name (e.g. “Is American Express supported for adding funds?", “How do I use American Express to top up my account?"). The annotators of the dataset have assigned all such utterances to the same cluster because despite the minor differences, the intent of the utterances in the cluster remain the same. KULCQ, by leveraging the importance of keywords in representing the intent of the utterances, is able to gain information beyond what meets the eye at first glance - the geometry of the cluster.

We also evaluate a scenario where the Silhouette metric does not penalize certain kinds of clusters enough for containing highly varied utterances, which can in turn lead to difficulties in conversational settings. Contrarily, KULCQ metric results in a bad score for the same clusters, thus providing an advantage in conversational AI problems.

One example can be seen in the AskUbuntu dataset, for the cluster - "Software Recommendation". The Silhouette metric gives this cluster a small positive score of 0.04, whereas the KULCQ metric gives this a score of -0.01. Clearly the KULCQ metric penalizes this cluster much more severely as compared to the Silhouette metric. As seen in Table 2, the utterances of this cluster are widely varied, and it is highly unlikely that these utterances will be clustered together by any automatic intent discovery algorithm. Moreover, in many conversational AI problems, it may not be a wise idea to cluster utterances that are as varied as the ones in Table 2 into one cluster with a general intent. Consider an application of conversational AI such as a chatbot: a slight change in intent can require a completely different action by the bot. In scenarios such as this, it is important that the utterances are clustered in more specific intents as opposed to a highly general one. Keeping this in mind, it is important that clusters such as the "Software Recommendation" cluster are penalized significantly in a conversational setting. By leveraging keywords, KULCQ is able to reward tightly-knit, specific clusters, and penalize the generic and varied ones, which can offer a great advantage for conversational AI applications.

Additionally, we performed clustering over all utterances across datasets using HDBScanCampello et al. (2013) and K-meansMacqueen (1967) and observed similar patterns depicted in Figure 1 and Figure 2. Since the clusters obtained aren’t manually labeled, we conclude our findings solely based on the ground truth intent labels.