# Towards a fully Unsupervised framework for intent induction in Customer
Support Dialogues

Rita Costa
INOV/Instituto Superior Técnico,
<EMAIL_ADDRESS>&Bruno Martins
INESC-ID/Instituto Superior Técnico,
<EMAIL_ADDRESS>&Sérgio Viana
Xpand-it,
<EMAIL_ADDRESS>&Luisa Coheur
INESC-ID/Instituto Superior Técnico,
<EMAIL_ADDRESS>
###### Abstract

State of the art models in intent induction require annotated datasets.
However, annotating dialogues is time-consuming, laborious and expensive. In
this work, we propose a completely unsupervised framework for intent induction
within a dialogue. In addition, we show how pre-processing the dialogue
corpora can improve results. Finally, we show how to extract the dialogue
flows of intentions by investigating the most common sequences. Although we
test our work in the MultiWOZ dataset, the fact that this framework requires
no prior knowledge make it applicable to any possible use case, making it very
relevant to real world customer support applications across industry.

##  1 Introduction

The evolution of technology has allowed the automation of several processes
across diversified engineering industry fields, such as customer support
services, which have drastically evolved with the advances in Natural Language
Processing and Machine Learning. One of the major challenges of these systems
is to identify users intentions, a complex Natural Language Understanding
task, that vary across domains. With the evolution of Deep Learning
architectures, recent works focused on modelling intentions and creating a
taxonomy of intents, so they can be fed to powerful supervised clustering
algorithms (Haponchyk et al.,, 2020; Chatterjee and Sengupta,, 2021).

However, these systems have the bottleneck of requiring the existence of
labelled data to be trained and deployed, and, thus, they can not be easily
transferred to real world customer support services, where the available data
for a commercial chatbot usually consists in no more than a dataset of
interactions between clients and operators. As labeling hundreds of utterances
with intent labels can be time-consuming, laborious, expensive and, sometimes,
even requires someone with expertise, it is not straightforward to apply
current state of the art supervised models to new domains (Chatterjee and
Sengupta,, 2020).

In this work, we propose a totally unsupervised intent induction framework and
apply it to the MultiWOZ dataset (Budzianowski et al.,, 2018). Previous
unsupervised intent induction works have used methods which perform clustering
of user query utterances in human-human conversations (Perkins and Yang,,
2019; Haponchyk et al.,, 2020; Chatterjee and Sengupta,, 2020). Popular
clustering algorithms for practical applications include centroid-based
algorithms, such as the K-Means algorithm (Lloyd,, 1982), and density based
algorithms, namely DBSCAN (Daszykowski and Walczak,, 2009) and HDBSCAN
(McInnes and Healy,, 2017). An advantage of the density-based algorithms is
not requiring to define the number of clusters a priori (Ghaemi and Farnaghi,,
2019), being more efficient for detecting clusters with arbitrary shapes from
a noisy dataset, particularly for a case where the number of dialogue
intentions is not known a priori. By using HDBSCAN, we also do not require the
prior definition of the density threshold used to create the clusters
(contrary to DBSCAN), which is more suitable for this application. Moreover,
we show that text pre-processing techniques, such as performing named entity
recognition, can improve the clustering process of dialogue utterances.
Finally, we complement this experiment with an analysis of the most common
dialogue flows, based on the detected intents.

In summary, the main contributions of this work are:

  * •

the application of a fully unsupervised method for extracting intents within a
dialogue, requiring no prior information about its content, and hence avoiding
the time-consuming task of manually analysing user questions and identifying
the intents (both intra- and inter-domain studies are conducted);

  * •

an exploratory analysis of the dataset, motivating the usage of general text
processing techniques to optimize the intent extraction process, that can be
applied to any corpora;

  * •

an informal analysis of the most common flows of discovered intentions.

As there is no required prior knowledge of any dataset specificities or
deployment details, our proposal is applicable to any type of data and use
case, making it relevant for a huge variety of applications, such as customer
support applications.

This paper is organized as follows: in Section 2 we present related work, in
Section 3 we present a data analysis, and in Section 4 the experimental
results. Then, in Section 5 we present the main conclusions and some future
work.

##  2 Related Work

This section gives an overview of the tools used in the development of this
work. In Section 2.1, we present the MultiWOZ dataset, a task-oriented
collection of dialogues whose utterances are used for the experiments in
Section 4. Before feeding these sentences into an algorithm, it is required to
transform them in a space representation, for which an overview is given in
Section 2.2. In Section 2.3, we present HDBSCAN and motivate the choice of
this clustering algorithm. Finally, the method for analysis of dialogue flows
is presented in Section 2.4.

###  2.1 MultiWOZ Dataset

The MultiWOZ dataset (Budzianowski et al.,, 2018) is a labelled human-human
collection of goal-oriented dialogues, simulating natural conversations
between a tourist and an assistant from an information center in a touristic
city. The corpus has conversations spanning over 7 domains — attraction,
hospital, police, hotel, restaurant, taxi, train — with diverse complexity of
tasks, going from a simple information query about an attraction, to booking a
night at a hotel, a restaurant reservation and a taxi to connect both places.
The dataset is composed of 10438 dialogues, which can be either single domain
or multi-domain. The average number of turns per dialogue is 8.93 and 15.39,
for single and multi-domain, respectively.

One particularity about this dataset is the richness in annotations at two
levels for each utterance: domain and intent. This information will allows us
to conduct the experiments with a reference of ground truth, helping
validating the used approach. In Figure 1, it is possible to see an example of
a part of a dialogue, with the corresponding domains and intents for each
utterance. Besides the possible conversation domains, an utterance can also
belong to two broader domains: the booking domain — if it refers to the act of
booking an entitiy — or to the general domain — if it is a greeting, an
acknowledgement, etc. In addition to the dialogues and their annotations, the
dataset is also composed of 7 database files, one for each possible domain of
conversation.

A further exploratory analysis of this dataset can be found in Section 3.

Figure 1: A dialogue example with domains and intents.

###  2.2 Text Representation

An important part of Natural Language Processing is how to represent sentences
such that it is possible to build algorithms on them. Initially, the focus was
in representing words independently. The most basic approach was to represent
text through a one-hot vector, with value 1 assigned to a word that is
present, and 0 corresponding to not present. The impossibility to transmit the
similarity between words gave rise to what are now called word embeddings,
which represent a word in a low dimensional vector space, where similar words
take similar parts of the modelling space. Popular word embeddings techniques
include Word2Vec (Mikolov et al.,, 2013) and GloVe (Pennington et al.,, 2014).
The need to solve ambiguities around words meanings and represent them with
respect to the sentence they are inserted led to the evolution of contextual
word embeddings, such as ELMo (Peters et al.,, 2018). The representations move
beyond word-level semantics, in that each word has a representation which is a
function of the entire input sequence, being able to capture syntax and
semantics. The evolution of text representation techniques opened the door to
more complex language models, with transformer architectures that use
attention to learn embeddings, such as GPT (Radford and Salimans,, 2018) and
BERT Devlin et al., (2019). In tasks such as clustering and semantic search, a
common method is to map each sentence such that semantically similar sentences
are close, as proposed in Sections 2.2.1 and 2.2.2.

####  2.2.1 Sentence-BERT

BERT related models have the state-of-the-art performance on sentence-pair
regression tasks like semantic textual similarity. However, to compute the
similarity between two sentences requires that they are both fed into the
model, which makes it too expensive for pair regression tasks, such as
semantic similarity search and clustering, due to too many possible
combinations. To make this task more efficient, Sentence-BERT (SBERT) (Reimers
and Gurevych,, 2020) uses siamese and triplet network structures to derive
semantically meaningful sentence embeddings. These techniques represent entire
sentences and their semantic information as vectors, making semantically
similar sentences close in the vector space. This helps the machine in
understanding the context, intention, and other nuances in the entire text.
Then, by using a similarity measure like cosine-similarity or euclidean
distance, it is possible to find semantically similar sentences. SBERT is
available in the Sentence-Transformer framework111https://www.sbert.net/, with
pre-trained models of sentence embeddings tuned for various tasks, in more
than 100 languages.

####  2.2.2 Dimensionality Reduction

After using SBERT for utterance representation, we obtain embeddings with
dimension of 768. Since high dimensionality embeddings lead to a loss of
robustness in clustering algorithms, we trade the loss of information for a
more robust clustering by reducing the dimensionality of the embeddings before
feeding them to the clustering algorithm.

There are a few alternatives of methods for dimensionality reduction, such as
t-Distributed Stochastic Neighbor Embedding (t-SNE) (van der Maaten and
Hinton,, 2008), and Uniform Manifold Approximation and Projection (UMAP)
(McInnes et al.,, 2018). Both were designed to predominantly preserve the
local structure, by grouping neighbouring data points together, which provides
a very informative visualization of the heterogeneity present in the data.
UMAP is more adequate for this context, since t-SNE produces unstable
embeddings, making the experiences non reproducible.

###  2.3 HDBSCAN for unsupervised clustering

Clustering is an unsupervised Machine Learning technique that consists of
grouping data points such that those with similar features are classified with
the same group, meaning that data points belonging to different groups should
have more dissimilar properties. Depending on the notion of what defines a
cluster, there are a variety of diversified clustering algorithms: some of
them are centroid based, such as the K-Means (Lloyd,, 1982), where the
clustering is done based on some randomly initialized points and the minimum
distance from a point to others; others are density based, such as DBSCAN
(Daszykowski and Walczak,, 2009), where points are clustered based on their
densities in a particular region. Density based clustering is particularly
relevant for problems where little is known about the dataset, since they do
not require the a priori definition of the amount of clusters.

In most density-based clustering algorithms, such as DBSCAN, it is necessary
to define a density threshold to make a cluster. This parameter is specially
difficult to adjust for higher dimensional data, posing a problem for
obtaining clusters with varying densities. To solve this problem, the
Hierarchical Density-Based Spatial Clustering of Applications with Noise
(HDBSCAN) (Campello et al.,, 2015) was developed, not requiring the prior
definition of this density threshold. The algorithm first builds a hierarchy
to figure out which peaks end up merging together and in what order. Then, for
each cluster, it evaluates if it is more beneficial to keep that cluster or
split it into subclusters, considering the volume of each peak. HDBSCAN uses
soft clustering: unlike most clustering algorithms, data points are not
assigned cluster labels, but rather a vector of probabilities for each
cluster, identified by $c\in\\{0,n_{clusters}-1\\}$, allowing each point to
potentially be a mix of clusters. It is also noise aware, meaning that it has
a notion of data samples that are not assigned to any cluster, to which it
assigns the label -1.

###  2.4 Sequential Pattern Mining for the analysis of dialogue flows

In the context of dialogue interactions, besides identifying utterances
intentions, it is relevant to evaluate the most common interactions, allowing
to discover the flow of the dialogue. To do so, it is possible to use the
sequential pattern mining algorithm Prefix-projected Sequential pattern
(PrefixSpan) (Pei et al.,, 2001), which discovers frequent subsequences as
patterns in a sequence database.

The PrefixSpan implementation222https://pypi.org/project/prefixspan/ to be
used outputs traditional single-item sequential patterns. This library also
includes the frequent closed sequential pattern mining algorithm BIDE (Wang
and Han,, 2004), and the frequent generator sequential pattern mining
algorithm FEAT (Gao et al.,, 2008). To use the algorithm via API, we will
refer to the PrefixSpan class in prefixspan/api.py. In this implementations,
two types of sequences can be obtained: `.frequent(n)` returns the sequences
that appear n times; and `.topk(k)` gives the k most frequent sequences in the
dataset. These methods also support other specificities, which can be found in
the algorithm documentation link.

##  3 Data Analysis

To have a better understanding of the task we have at hand, it is relevant to
perform an analysis of the dialogue utterances. In Section 3.1, the
similarities between embeddings of different utterances are investigated,
motivating the use of an open-source tool for entity identification. In
Section 3.2, we provide an overview of the distribution of the dataset over
domain and intent.

###  3.1 Embeddings representation

As proposed in Section 2.2, the dataset utterances are represented using the a
Sentence-BERT model. These embeddings are obtained using the sentence-
transformer `‘paraphrase-distilroberta-base-v1’` package, that outputs
embeddings with dimension 768 for each utterance.

(a) Similarity between pairs of embeddings.  (b) Similarity between pairs of
embeddings after NER tool from spacy.  (c) Similarity between pairs of
embeddings after adding entities to the NER tool from spacy.

Figure 2: Similarity.

Following Laban et al., (2021), to evaluate the feasibility of this
experience, we measured the similarity between the embeddings of 1000 pairs of
random utterances belonging to the different categories:

  * •

utterances belonging to the same domain, or group of domains (label `domain`);

  * •

utterances belonging to the same domain and the same intent, or groups of
domains and intents (label `domain_intent`);

  * •

subsequent utterances in the dialogue (label `followed`);

  * •

and utterances randomly obtained from the dataset (label `random`).

The plot can be seen in Figure 2a. As the goal is to discover broader intents
for the dialogues utterances, it can be useful to make them more homogeneous,
in order to avoid clusters around entities. For this purpose, we use the spaCy
Named Entity Recognition tool333https://spacy.io/usage/linguistic-features,
which replaces the recognized entities for broader tags, such as general known
numbers (e.g one, thirty-three, two hundred) and places (e.g Cambridge). The
similarity plot for these processed utterances is shown in Figure 2b. In
addition to this, as there is information about specific entities present in
the dataset, such as hotel and restaurants names, we can also remove them from
the dialogues (e.g. In Figure 2c, we can see the similarity between pairs of
utterances with entities from the dataset removed.

From the plots, it is clear that the distribution of similarity between pairs
of embeddings is higher for utterances with common domains and intentions,
suggesting that a clustering experience based on this measure may be
successful. Besides, this difference is higher for utterances where entities
were removed, motivating the use of this tool for improving the clustering
experience.

###  3.2 Domain and intent annotations

As seen in Figure 1, one utterance from the MultiWOZ dataset can belong to
more than one domain. In Figure 3, we present the frequency of each possible
combination of domains (the combinations which were present less than 10 times
were kept out of this plot for the sake of visibility). The highest presence
are for single domain utterances. The highest value is for the general domain,
followed by train, restaurant, hotel, attraction, taxi and booking. The police
and hospital domains have fewer utterances assigned, as they also have less
dialogues.

Figure 3: The possible combinations of domains.

For the generality of domains, the possible intents classifications are
inform, request, recommend, no-offer and select. The booking domain has other
possibilities regarding the booking possibility, book or no-book. The general
domain has its particular intents: greet, welcome, reqmore, thank and bye.
Naturally, it is possible for a utterance to hold more than one intent. As
there are many more possible combinations of intents than domains, we will not
present plots of all domains, but rather exemplify with the representations of
utterances belonging to the hotel domain. In Figure 4, it is possible to see
the 2-D representations of utterances belonging to this domain, using the UMAP
algorithm with dimension 2. Although these are just 2-D representations of way
higher dimensional embeddings, it is still possible to identify some groups of
sentences belonging to the same domain or intent. This can translate the
possibility of performing density clustering in these data points.

Figure 4: 2-D representations of utterances embeddings per intent in the hotel
domain.

##  4 Experimental Results

This section includes an analysis of the experimental results. An introduction
to the evaluation methods is given in Section 4.1. In Section 4.3, we present
and analyse the results of an intra-domain clustering experiment for the hotel
domain. In Section 4.2, an inter-domain clustering experience is conducted.

###  4.1 Evaluation Metrics

To evaluate the results of a clustering experiment, one can use intrinsic
methods (based on properties of the algorithm itself), such as the relative
validity index. This metric measures how close elements from one cluster are
to each other, and how distant they are from elements in other clusters. It is
important to note that the topic of clustering validation is considered one of
the most challenging topics in the clustering literature: since these are
unsupervised algorithms, it is required to resort to internal validity
criteria, calculated solely based on information intrinsic to the data.

In these particular experiences, since we have annotation references from the
dataset, it is also possible to resort to extrinsic methods that compare the
clusters with a pre-existing structure — a ground truth solution. In this
context, BCubed precision and BCubed recall (Bagga and Baldwin,, 1998) are
found to be the only ones that satisfy all the proposed properties/constraints
for clustering evaluation metrics (Amigó et al.,, 2009). The BCubed precision
of an item is the proportion of items in its cluster which have the item’s
category, including itself, related to the amount of items in its cluster. The
BCubed recall is analogous, but related to the amount of items within its
category. The overall BCubed precision and recall are the averaged precision
and recall of all the items.

Naturally, extrinsic methods are not usable when there are no ground truth
references, leaving intrinsic methods as the most relevant for clustering
experiences, since they are the only ones applicable in real world scenarios.

###  4.2 Inter-domain Clustering

Firstly, we present the clustering results for an experience with all the
utterances from the MultiWOZ dataset. In this inter-domain clustering
experience, we have two types of possible labels: domain and intent. To
simplify, we present the possible domains for the utterances, whose 2-D
representations are plotted in Figure 5. As evident in Figure 5, there are
many possible combinations of domain labels for the data points. Hence, we
will refrain from plotting the possible combinations of intents, as there are
even more possibilities than those in Figure 5, and its analysis would be too
exhaustive.

Figure 5: 2-D representations of utterances embeddings per domain.

For these experiences, we opted to remove the utterances from the general
domain. As seen in the plot from Figure 3, these are the most present in the
dataset. The fact that these types of utterances are very repetitive, with a
very low variability, makes the dataset very imbalanced. As the same exact
utterance from the general domain occurs very often, this can damage the
clustering experience by generating clusters for equal utterances only, which
is not aligned with the goals for this task.

When running the HDBSCAN algorithm, there are two important parameters to set:
`min_cluster_size`, defining the smallest size grouping that should be
considered a cluster. The bigger its value, the less clusters will be
obtained; and `min_samples`, which provides a measure of how conservative the
clustering should be. The larger its value, the more conservative the
clustering, and the more points will be considered as noise, being clusters
progressively restricted to more dense areas. By default, it is set to the
value of `min_cluster_size`. We fine tune these values by making `min_samples`
vary from 0 to 100 with a step size of 10, `min_cluster_size` vary from 25 to
300 with a step size of 25 and measuring the relative validity index, as
depicted in Table 1. It is not possible to see a direct relationship between
this value and both of the variables. The best result happens for
$\verb|min_samples|=100$ and $\verb|min_cluster_size|=300$.

Table 1: Grid search of relative validity index over min_cluster_size and
min_samples for all utterances of the MultiWOZ dataset.

| 25 | 50 | 75 | 100 | 125 | 150 | 175 | 200 | 225 | 250 | 275 | 300
---|---|---|---|---|---|---|---|---|---|---|---|---
10 | $3.32\text{\times}{10}^{-2}$ | $4.31\text{\times}{10}^{-2}$ | $3.70\text{\times}{10}^{-5}$ | $2.47\text{\times}{10}^{-5}$ | $2.47\text{\times}{10}^{-5}$ | $2.47\text{\times}{10}^{-5}$ | $3.09\text{\times}{10}^{-6}$ | $3.09\text{\times}{10}^{-6}$ | $3.09\text{\times}{10}^{-6}$ | $3.09\text{\times}{10}^{-6}$ | $3.09\text{\times}{10}^{-6}$ | $3.09\text{\times}{10}^{-6}$
20 | $4.01\text{\times}{10}^{-2}$ | $3.76\text{\times}{10}^{-2}$ | $2.17\text{\times}{10}^{-3}$ | $1.50\text{\times}{10}^{-3}$ | $1.50\text{\times}{10}^{-3}$ | $4.95\text{\times}{10}^{-6}$ | $4.95\text{\times}{10}^{-6}$ | $2.02\text{\times}{10}^{-3}$ | $1.25\text{\times}{10}^{-4}$ | $1.23\text{\times}{10}^{-4}$ | $2.60\text{\times}{10}^{-3}$ | $2.60\text{\times}{10}^{-3}$
30 | $3.30\text{\times}{10}^{-2}$ | $2.67\text{\times}{10}^{-2}$ | $1.01\text{\times}{10}^{-4}$ | $1.38\text{\times}{10}^{-3}$ | $1.38\text{\times}{10}^{-3}$ | $1.38\text{\times}{10}^{-3}$ | $1.15\text{\times}{10}^{-5}$ | $5.46\text{\times}{10}^{-6}$ | $5.46\text{\times}{10}^{-6}$ | $4.38\text{\times}{10}^{-2}$ | $4.38\text{\times}{10}^{-2}$ | $4.15\text{\times}{10}^{-2}$
40 | $1.62\text{\times}{10}^{-2}$ | $1.62\text{\times}{10}^{-2}$ | $5.72\text{\times}{10}^{-5}$ | $8.88\text{\times}{10}^{-4}$ | $4.17\text{\times}{10}^{-6}$ | $1.26\text{\times}{10}^{-2}$ | $1.11\text{\times}{10}^{-2}$ | $9.46\text{\times}{10}^{-3}$ | $4.23\text{\times}{10}^{-2}$ | $4.03\text{\times}{10}^{-2}$ | $4.03\text{\times}{10}^{-2}$ | $4.03\text{\times}{10}^{-2}$
50 | $1.62\text{\times}{10}^{-2}$ | $2.48\text{\times}{10}^{-2}$ | $1.16\text{\times}{10}^{-3}$ | $5.89\text{\times}{10}^{-6}$ | $5.89\text{\times}{10}^{-6}$ | $6.99\text{\times}{10}^{-3}$ | $5.62\text{\times}{10}^{-3}$ | $1.44\text{\times}{10}^{-2}$ | $1.44\text{\times}{10}^{-2}$ | $5.10\text{\times}{10}^{-3}$ | $5.10\text{\times}{10}^{-3}$ | $5.09\text{\times}{10}^{-3}$
60 | $1.82\text{\times}{10}^{-2}$ | $2.06\text{\times}{10}^{-2}$ | $6.17\text{\times}{10}^{-4}$ | $2.42\text{\times}{10}^{-5}$ | $2.42\text{\times}{10}^{-5}$ | $8.76\text{\times}{10}^{-3}$ | $7.50\text{\times}{10}^{-3}$ | $3.88\text{\times}{10}^{-3}$ | $3.88\text{\times}{10}^{-3}$ | $3.88\text{\times}{10}^{-3}$ | $3.88\text{\times}{10}^{-3}$ | $3.87\text{\times}{10}^{-3}$
70 | $2.52\text{\times}{10}^{-5}$ | $2.52\text{\times}{10}^{-5}$ | $1.03\text{\times}{10}^{-3}$ | $1.03\text{\times}{10}^{-3}$ | $1.03\text{\times}{10}^{-3}$ | $2.02\text{\times}{10}^{-2}$ | $1.89\text{\times}{10}^{-2}$ | $1.66\text{\times}{10}^{-2}$ | $1.34\text{\times}{10}^{-2}$ | $1.14\text{\times}{10}^{-2}$ | $1.14\text{\times}{10}^{-2}$ | $3.09\text{\times}{10}^{-2}$
80 | $5.03\text{\times}{10}^{-4}$ | $5.03\text{\times}{10}^{-4}$ | $1.42\text{\times}{10}^{-5}$ | $1.42\text{\times}{10}^{-5}$ | $1.42\text{\times}{10}^{-5}$ | $1.87\text{\times}{10}^{-2}$ | $7.15\text{\times}{10}^{-2}$ | $7.15\text{\times}{10}^{-2}$ | $7.15\text{\times}{10}^{-2}$ | $7.15\text{\times}{10}^{-2}$ | $8.43\text{\times}{10}^{-2}$ | $1.04\text{\times}{10}^{-1}$
90 | $8.46\text{\times}{10}^{-7}$ | $5.81\text{\times}{10}^{-4}$ | $5.81\text{\times}{10}^{-4}$ | $1.14\text{\times}{10}^{-5}$ | $1.14\text{\times}{10}^{-5}$ | $8.93\text{\times}{10}^{-2}$ | $8.81\text{\times}{10}^{-2}$ | $8.57\text{\times}{10}^{-2}$ | $8.57\text{\times}{10}^{-2}$ | $9.97\text{\times}{10}^{-2}$ | $9.77\text{\times}{10}^{-2}$ | $9.80\text{\times}{10}^{-2}$
100 | $3.04\text{\times}{10}^{-6}$ | $3.82\text{\times}{10}^{-6}$ | $3.82\text{\times}{10}^{-6}$ | $3.82\text{\times}{10}^{-6}$ | $3.82\text{\times}{10}^{-6}$ | $1.37\text{\times}{10}^{-1}$ | $1.36\text{\times}{10}^{-1}$ | $1.36\text{\times}{10}^{-1}$ | $1.12\text{\times}{10}^{-1}$ | $1.10\text{\times}{10}^{-1}$ | $1.10\text{\times}{10}^{-1}$ | $1.50\text{\times}{10}^{-1}$

Table 2: Optimal clustering results for each value of min_samples, with BCubed
metrics computed using the domain labels.

|  |  |  | Clusters |  | Soft Clusters |  |
---|---|---|---|---|---|---|---|---
min_samples | min_cluster_size | validity |  | P | R | M |  | P | R | M |  | n clusters
10 | 50 | $4.31\text{\times}{10}^{-2}$ |  | 0.2559 | 0.6323 | 0.3643 |  | 0.5167 | 0.0915 | 0.1555 |  | 105
20 | 25 | $4.01\text{\times}{10}^{-2}$ |  | 0.2302 | 0.7171 | 0.3486 |  | 0.5236 | 0.0905 | 0.1544 |  | 159
30 | 250 | $4.38\text{\times}{10}^{-2}$ |  | 0.2301 | 0.6409 | 0.3386 |  | 0.3884 | 0.3509 | 0.3687 |  | 16
40 | 225 | $4.23\text{\times}{10}^{-2}$ |  | 0.2300 | 0.6583 | 0.3409 |  | 0.3877 | 0.3837 | 0.3857 |  | 15
50 | 50 | $2.48\text{\times}{10}^{-2}$ |  | 0.2096 | 0.7328 | 0.3260 |  | 0.4733 | 0.1999 | 0.2811 |  | 55
60 | 50 | $2.06\text{\times}{10}^{-2}$ |  | 0.2068 | 0.7232 | 0.3217 |  | 0.418 | 0.2506 | 0.3133 |  | 43
70 | 300 | $3.09\text{\times}{10}^{-2}$ |  | 0.2066 | 0.6967 | 0.3187 |  | 0.3665 | 0.3625 | 0.3645 |  | 11
80 | 300 | $1.04\text{\times}{10}^{-1}$ |  | 0.2202 | 0.6869 | 0.3335 |  | 0.3635 | 0.4073 | 0.3841 |  | 10
90 | 250 | $9.97\text{\times}{10}^{-2}$ |  | 0.2293 | 0.6770 | 0.3426 |  | 0.3833 | 0.3987 | 0.3909 |  | 12
100 | 300 | $1.50\text{\times}{10}^{-1}$ |  | 0.2205 | 0.6689 | 0.3317 |  | 0.3473 | 0.4139 | 0.3777 |  | 9

Table 3: Optimal clustering results for each value of min_samples, with BCubed
metrics computed using the intent labels.

|  |  |  | Clusters |  | Soft Clusters |  |
---|---|---|---|---|---|---|---|---
min_samples | min_cluster_size | validity |  | P | R | M |  | P | R | M |  | n clusters
10 | 50 | $4.31\text{\times}{10}^{-2}$ |  | 0.1739 | 0.6529 | 0.2746 |  | 0.3231 | 0.1633 | 0.2170 |  | 105
20 | 25 | $4.01\text{\times}{10}^{-2}$ |  | 0.1521 | 0.7269 | 0.2516 |  | 0.3324 | 0.1574 | 0.2136 |  | 159
30 | 250 | $4.38\text{\times}{10}^{-2}$ |  | 0.1314 | 0.6662 | 0.2196 |  | 0.2008 | 0.4272 | 0.2732 |  | 16
40 | 225 | $4.23\text{\times}{10}^{-2}$ |  | 0.1294 | 0.6825 | 0.2176 |  | 0.1960 | 0.4609 | 0.2751 |  | 15
50 | 50 | $2.48\text{\times}{10}^{-2}$ |  | 0.1242 | 0.7437 | 0.2128 |  | 0.2655 | 0.2634 | 0.2644 |  | 55
60 | 50 | $2.06\text{\times}{10}^{-2}$ |  | 0.1191 | 0.7339 | 0.2050 |  | 0.2345 | 0.3192 | 0.2704 |  | 43
70 | 300 | $3.09\text{\times}{10}^{-2}$ |  | 0.1130 | 0.7161 | 0.1953 |  | 0.1819 | 0.4402 | 0.2574 |  | 11
80 | 300 | $1.04\text{\times}{10}^{-1}$ |  | 0.1049 | 0.7034 | 0.1825 |  | 0.1678 | 0.4697 | 0.2473 |  | 10
90 | 250 | $9.97\text{\times}{10}^{-2}$ |  | 0.1090 | 0.6937 | 0.1885 |  | 0.1756 | 0.4608 | 0.2543 |  | 12
100 | 300 | $1.50\text{\times}{10}^{-1}$ |  | 0.1043 | 0.6910 | 0.1812 |  | 0.1605 | 0.4755 | 0.2400 |  | 9

For a deeper analysis of the possible clustering results, we present the
values for BCubed precision (P), BCubed recall (R) and their harmonic mean
(M), for each value of `min_samples` and the corresponding optimal value of
`min_cluster_size`. the values for BCubed metrics using domains or intents as
labels are presented in Tables 2 and 3, respectively. Besides, we can evaluate
both the clusters and soft clusters, where the latter are obtained by choosing
the cluster with the maximum value of probability. The number of obtained
clusters for each experience is also presented, allowing to have an idea of
how granular the clusters are.

We can draw a few ideas from the results. Firstly, that an increase in the
value of P is usually combined with a decrease in the value of R, supporting
the need for analysing their harmonic mean (M). We can also confirm that we
need to increase both `min_samples` and `min_cluster_size` for the clustering
to become more conservative: for the same value of `min_cluster_size`, an
increase in `min_samples` leads to a lower number of obtained clusters (which
happens for $\verb|min_cluster_size|=50$, for example).

The BCubed metrics results are generally better when using the domain
annotations as labels. In Figure 6, we present the results for the inter-
domain experience with the optimal relative validity index, where the quality
of the clusters can be grasped. In Table 4, we present details about each
cluster: their length, persistence in the spanning tree, and the dataset
reference label, which corresponds to the label from the dataset with more
data points in each cluster. For a better analysis of each clustering
experience, we can also extract the most frequent words in each cluster of
utterances. In this experience, we use the TD-IDF algorithm, treating each
cluster of utterances as a single document444Following
https://towardsdatascience.com/topic-modeling-with-bert-779f7db187e6.

(a) Clusters for min_samples=100 and min_cluster_size=300.

(b) Soft clusters for min_samples=100 and min_cluster_size=300.

Figure 6: Results of clustering domains in MultiWOZ in MultiWOZ using optimal
samples and cluster size by intrinsic measures. Table 4: Details of the
clusters obtained for all the domains.

cluster | length | persistence | top words by TF-IDF | label
---|---|---|---|---
0 | 300 | 0.0829 | postcode, phone, address, number, code | attraction
1 | 300 | 0.0197 | price, range, preference, options, area | hotel
2 | 674 | 0.0578 | train, time, cambridge, leave, leaving | train
3 | 451 | 0.0464 | taxi, need, time, cardinal, contact | taxi
4 | 321 | 0.0586 | guesthouse, hotel, free, parking, star | hotel
5 | 300 | 0.0365 | restaurant, food, centre, town, restaurants | restaurant
6 | 314 | 0.0445 | people, date, cardinal, book, yes | hotel
7 | 300 | 0.0549 | reference, number, booking, successful, booked | booking general
8 | 300 | 0.1402 | fee, gbp, total, station, payable | general train

It is possible to say that the algorithm is successfully identifying different
clusters of domains, as most of the obtained clusters are clearly from the
domain assigned as label. While a few others seem to be more general (clusters
0, 1 and 6), we understand that these types of utterances must have a great
presence in the dataset, and possibly appearing in different types of domain
dialogues. We should underline that, as the amount and variability of dialogue
utterances increase, it is more likely that similar utterances belonging to
different domains appear, leading to utterances with different labels being
clustered together.

###  4.3 Intra-domain Clustering

For this experience, we consider utterances from the MultiWOZ dataset
belonging to the hotel domain. Intra-domain data is the most likely to be
found in a real world scenario, where dialogues that are jointly analyzed
belong to the same broader domain.

In Table 5, the values for the relative validity index are presented when
varying `min_samples` from 5 to 50 with a step size of 5, and
`min_cluster_size` from 10 to 100 with a step size of 10 — as we are in the
presence of a smaller amount of data, the range of values for the variables
have also been decreased. The best score of relative validity index is for the
combination of $\verb|min_samples|=50$ and $\verb|min_cluster_size|=80$.

Table 5: Grid search over min_cluster_size and min_samples for the hotel
domain.

| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100
---|---|---|---|---|---|---|---|---|---|---
5 | $5.91\text{\times}{10}^{-2}$ | $5.45\text{\times}{10}^{-2}$ | $5.77\text{\times}{10}^{-5}$ | $2.89\text{\times}{10}^{-5}$ | $2.89\text{\times}{10}^{-5}$ | $1.35\text{\times}{10}^{-5}$ | $1.35\text{\times}{10}^{-5}$ | $1.35\text{\times}{10}^{-5}$ | $1.35\text{\times}{10}^{-5}$ | $1.35\text{\times}{10}^{-5}$
10 | $4.29\text{\times}{10}^{-2}$ | $5.36\text{\times}{10}^{-2}$ | $1.23\text{\times}{10}^{-3}$ | $2.92\text{\times}{10}^{-5}$ | $2.96\text{\times}{10}^{-5}$ | $2.96\text{\times}{10}^{-5}$ | $2.96\text{\times}{10}^{-5}$ | $2.96\text{\times}{10}^{-5}$ | $2.96\text{\times}{10}^{-5}$ | $5.88\text{\times}{10}^{-5}$
15 | $3.14\text{\times}{10}^{-2}$ | $2.78\text{\times}{10}^{-2}$ | $2.86\text{\times}{10}^{-2}$ | $2.27\text{\times}{10}^{-2}$ | $2.25\text{\times}{10}^{-2}$ | $4.92\text{\times}{10}^{-5}$ | $3.21\text{\times}{10}^{-5}$ | $3.21\text{\times}{10}^{-5}$ | $3.21\text{\times}{10}^{-5}$ | $3.21\text{\times}{10}^{-5}$
20 | $3.36\text{\times}{10}^{-2}$ | $2.69\text{\times}{10}^{-2}$ | $1.02\text{\times}{10}^{-5}$ | $1.02\text{\times}{10}^{-5}$ | $1.02\text{\times}{10}^{-5}$ | $4.21\text{\times}{10}^{-3}$ | $4.21\text{\times}{10}^{-3}$ | $1.41\text{\times}{10}^{-6}$ | $1.41\text{\times}{10}^{-6}$ | $1.41\text{\times}{10}^{-6}$
25 | $2.69\text{\times}{10}^{-2}$ | $2.99\text{\times}{10}^{-2}$ | $6.98\text{\times}{10}^{-7}$ | $6.98\text{\times}{10}^{-7}$ | $6.66\text{\times}{10}^{-3}$ | $6.66\text{\times}{10}^{-3}$ | $6.66\text{\times}{10}^{-3}$ | $5.54\text{\times}{10}^{-8}$ | $5.54\text{\times}{10}^{-8}$ | $5.54\text{\times}{10}^{-8}$
30 | $5.41\text{\times}{10}^{-4}$ | $3.52\text{\times}{10}^{-6}$ | $3.92\text{\times}{10}^{-6}$ | $3.92\text{\times}{10}^{-6}$ | $1.35\text{\times}{10}^{-2}$ | $1.35\text{\times}{10}^{-2}$ | $1.35\text{\times}{10}^{-2}$ | $1.09\text{\times}{10}^{-2}$ | $7.53\text{\times}{10}^{-3}$ | $1.79\text{\times}{10}^{-5}$
35 | $5.97\text{\times}{10}^{-4}$ | $1.89\text{\times}{10}^{-6}$ | $6.47\text{\times}{10}^{-3}$ | $6.47\text{\times}{10}^{-3}$ | $6.47\text{\times}{10}^{-3}$ | $6.47\text{\times}{10}^{-3}$ | $6.47\text{\times}{10}^{-3}$ | $1.86\text{\times}{10}^{-7}$ | $1.86\text{\times}{10}^{-7}$ | $1.86\text{\times}{10}^{-7}$
40 | $8.81\text{\times}{10}^{-4}$ | $2.95\text{\times}{10}^{-5}$ | $5.67\text{\times}{10}^{-3}$ | $5.67\text{\times}{10}^{-3}$ | $5.67\text{\times}{10}^{-3}$ | $5.67\text{\times}{10}^{-3}$ | $5.67\text{\times}{10}^{-3}$ | $5.67\text{\times}{10}^{-3}$ | $2.92\text{\times}{10}^{-6}$ | $2.92\text{\times}{10}^{-6}$
45 | $6.33\text{\times}{10}^{-4}$ | $7.52\text{\times}{10}^{-3}$ | $7.52\text{\times}{10}^{-3}$ | $7.52\text{\times}{10}^{-3}$ | $7.52\text{\times}{10}^{-3}$ | $7.53\text{\times}{10}^{-3}$ | $5.17\text{\times}{10}^{-3}$ | $2.70\text{\times}{10}^{-3}$ | $4.46\text{\times}{10}^{-6}$ | $3.48\text{\times}{10}^{-6}$
50 | $2.09\text{\times}{10}^{-5}$ | $2.09\text{\times}{10}^{-5}$ | $2.09\text{\times}{10}^{-5}$ | $2.09\text{\times}{10}^{-5}$ | $2.09\text{\times}{10}^{-5}$ | $2.09\text{\times}{10}^{-5}$ | $1.10\text{\times}{10}^{-2}$ | $3.11\text{\times}{10}^{-1}$ | $3.11\text{\times}{10}^{-1}$ | $4.71\text{\times}{10}^{-6}$

Table 6: Optimal clustering results for each value of min_samples.

|  |  |  | Clusters |  | Soft Clusters |  |
---|---|---|---|---|---|---|---|---
| min_cluster_size | validity |  | P | R | M |  | P | R | M |  | n clusters
5 | 10 | $5.91\text{\times}{10}^{-2}$ |  | 0.5509 | 0.6357 | 0.5903 |  | 0.6527 | 0.0381 | 0.0721 |  | 161
10 | 20 | $5.36\text{\times}{10}^{-2}$ |  | 0.5282 | 0.7183 | 0.6088 |  | 0.6164 | 0.0703 | 0.1262 |  | 59
15 | 10 | $3.14\text{\times}{10}^{-2}$ |  | 0.5200 | 0.7790 | 0.6237 |  | 0.6344 | 0.0525 | 0.0970 |  | 96
20 | 10 | $2.69\text{\times}{10}^{-2}$ |  | 0.5155 | 0.7694 | 0.6173 |  | 0.6038 | 0.0870 | 0.1520 |  | 50
25 | 20 | $2.99\text{\times}{10}^{-2}$ |  | 0.5158 | 0.8127 | 0.6311 |  | 0.5725 | 0.1055 | 0.1781 |  | 28
30 | 50 | $1.35\text{\times}{10}^{-2}$ |  | 0.4994 | 0.5578 | 0.5270 |  | 0.5129 | 0.7407 | 0.6061 |  | 6
35 | 30 | $6.47\text{\times}{10}^{-3}$ |  | 0.4971 | 0.5491 | 0.5218 |  | 0.5117 | 0.7548 | 0.6100 |  | 6
40 | 30 | $5.67\text{\times}{10}^{-3}$ |  | 0.4956 | 0.5368 | 0.5154 |  | 0.5125 | 0.7593 | 0.6120 |  | 6
45 | 20 | $7.52\text{\times}{10}^{-3}$ |  | 0.4964 | 0.5272 | 0.5113 |  | 0.5128 | 0.7743 | 0.6170 |  | 6
50 | 80 | $3.11\text{\times}{10}^{-1}$ |  | 0.4885 | 0.5328 | 0.5097 |  | 0.4921 | 0.8209 | 0.6153 |  | 3

(a) Clusters for min_samples=50 and min_cluster_size=80.

(b) Soft clusters for min_samples=50 and min_cluster_size=80.

(c) Clusters for min_samples=45 and min_cluster_size=20.

(d) Soft clusters for min_samples=45 and min_cluster_size=20.

(e) Clusters for min_samples=25 and min_cluster_size=20.

(f) Soft clusters for min_samples=25 and min_cluster_size=20.

Figure 7: Results of clustering intents in the hotel domain.

Similarly to before, we present the values P, R, and M in Table 6, for each
value of `min_samples` and the corresponding optimal value of
`min_cluster_size`. In what comes to the best performance in BCubed metrics,
there is a mismatch between the results from the clusters and soft clusters:
the former occurs for $\verb|min_samples|=25$ and
$\verb|min_cluster_size|=20$; and the latter is for $\verb|min_samples|=45$
and $\verb|min_cluster_size|=20$. These results are also not in accordance
with the optimal performance for relative validity index, which happens for
$\verb|min_samples|=50$ and $\verb|min_cluster_size|=80$. From these possible
combinations of values, 28 is the amount of obtained clusters which is more in
accordance with the original labels from the dataset.

In Figure 7, we present the results of these three clustering experiences in a
2-D representation, from fewer to greater obtained clusters. The color
gradient on the right side of each graph indicates the number of clusters
present in the plot, where the top indicates the maximum number of clusters
+1. For experiences where fewer clusters are obtained, there is generally a
broader cluster to which most of the data points belong, with a few more
specific ones. Although this can be supported by the nature of the dialogues,
where a lot of utterances are related to searching for a hotel, these results
are not that useful once we want to analyse the flow of intentions in a
dialogue. This fact advocates for the importance of adapting the hyper
parameters to the experience and results we are looking for, regardless of any
computed metric. In Tables 7, 8 and 9, we present details about each cluster,
for each clustering experience of Figure 7.

Table 7: Details of the 3 clusters obtained for the hotel domain.

cluster | length | persistence | top words | label
---|---|---|---|---
0 | 471 | 0.0526 | hotel, guesthouse, date, cardinal, free | hotel-inform
1 | 80 | 0.0213 | range, price, moderate, cheap, don | hotel-inform
2 | 82 | 0.0112 | price, range, options, cardinal, preference | hotel-request

Table 8: Details of the 6 clusters obtained for the hotel domain.

cluster | length | persistence | top words by TF-IDF | label
---|---|---|---|---
0 | 20 | 0.0674 | reference, number, yes, need, book | hotel-request
1 | 20 | 0.0181 | postcode, phone, address, number, code | hotel-request
2 | 20 | 0.0848 | restaurant, taxi, hotel, time, need | hotel-inform
3 | 309 | 0.0397 | cardinal, guesthouse, hotel, date, free | hotel-inform
4 | 20 | 0.0421 | range, price, moderate, cheap, priced | hotel-inform
5 | 24 | 0.0465 | price, range, options, mind, area | hotel-request

Table 9: Details of the 28 clusters obtained for the hotel domain.

cluster | length | persistence | top words by TF-IDF | label
---|---|---|---|---
0 | 20 | $2.00\text{\times}{10}^{-9}$ | yes, does, fine, sounds, matter | hotel-inform
1 | 20 | $1.06\text{\times}{10}^{-7}$ | date, time, try, starting, instead | hotel-inform
2 | 21 | $3.39\text{\times}{10}^{-8}$ | phone, number, postcode, date, help | hotel-inform
3 | 20 | $1.01\text{\times}{10}^{-7}$ | postcode, phone, number, just, address | hotel-request
4 | 20 | $3.28\text{\times}{10}^{-8}$ | address, road, phone, number, town | hotel-request
5 | 21 | $3.81\text{\times}{10}^{-7}$ | restaurant, taxi, hotel, time, need | hotel-inform
6 | 21 | $1.48\text{\times}{10}^{-7}$ | book, reference, number, yes, sounds | hotel-request
7 | 21 | $2.39\text{\times}{10}^{-7}$ | reference, number, yes, need, thank | hotel-request
8 | 20 | $1.57\text{\times}{10}^{-7}$ | range, price, moderate, cheap, priced | hotel-inform
9 | 20 | $1.70\text{\times}{10}^{-7}$ | price, range, options, mind, area | hotel-request
10 | 20 | $2.47\text{\times}{10}^{-8}$ | hotels, hotel, sorry, area, criteria | hotel-nooffer hotel-request
11 | 20 | $2.85\text{\times}{10}^{-8}$ | date, people, starting, room, cardinal | hotel-inform
12 | 46 | $2.28\text{\times}{10}^{-7}$ | date, people, starting, book, cardinal | hotel-inform
13 | 20 | $1.97\text{\times}{10}^{-7}$ | date, people, starting, cardinal, yes | hotel-inform
14 | 26 | $3.99\text{\times}{10}^{-1}$ | wifi, does, free, internet, include | hotel-inform
15 | 22 | $8.29\text{\times}{10}^{-7}$ | parking, free, does, offer, yes | hotel-inform
16 | 21 | $6.88\text{\times}{10}^{-7}$ | area, stay, town, like, prefer | hotel-request
17 | 20 | $8.89\text{\times}{10}^{-8}$ | hotel, prefer, preference, guesthouse, hotels | hotel-inform hotel-request
18 | 22 | $5.30\text{\times}{10}^{-7}$ | place, stay, looking, need, north | hotel-inform
19 | 20 | $8.83\text{\times}{10}^{-8}$ | guesthouse, cardinal, star, like, stars | hotel-inform
20 | 33 | $7.69\text{\times}{10}^{-7}$ | guesthouse, lovely, does, tell, house | hotel-recommend
21 | 22 | $6.40\text{\times}{10}^{-7}$ | called, hotel, looking, guesthouse, information | hotel-inform
22 | 20 | $2.87\text{\times}{10}^{-7}$ | guesthouse, suggest, recommend, prefer, like | hotel-recommend
23 | 20 | $5.23\text{\times}{10}^{-8}$ | guesthouse, book, like, room, recommend | hotel-recommend
24 | 21 | $3.90\text{\times}{10}^{-9}$ | parking, place, stay, free, cheap | hotel-inform
25 | 20 | $3.30\text{\times}{10}^{-7}$ | parking, guesthouse, free, looking, cheap | hotel-inform
26 | 21 | $1.60\text{\times}{10}^{-7}$ | star, cardinal, hotel, free, rating | hotel-inform
27 | 40 | $1.07\text{\times}{10}^{-7}$ | wifi, free, parking, need, hotel | hotel-inform

For the experience with only 3 obtained clusters (Table 7), it is easy to
understand that the two specific clusters are related to the hotel prince
range: cluster 1 (yellow) is probably mostly composed of utterances from the
user, due to the high presence of restrictive words (‘moderate’ and ‘cheap’);
cluster 2 (purple) should be mostly composed of utterances from the assistant
where a ‘preference’ is recurrently being asked. The rest of the utterances
belong to cluster 0 (magenta), where the most frequent words are certainly
directly obtained from the most frequent utterances from the dataset.

In the next experience (Table 8), there are other more specific clusters,
regarding booking (cluster 0 - magenta), hotel details such as postcode,
phone, and address (cluster 1 - orange), and requesting a taxi from the hotel
to the restaurant (cluster 2 - dark yellow).

The last experience results in a higher number of clusters, spanning over more
versatile types of intents: a confirmation (cluster 0), a suggestion of other
time or date (cluster 1), a recognition of the non existence of hotels
following the given criteria (cluster 10), an inquiry about the wifi (cluster
14), etc. The fact that the clusters are more granular also means that the
algorithm can split some clusters that could be broader, such as cluster 11
and 12, which both seem to be about a hotel room booking request. One
possibility can be the fact that one cluster includes more utterances
belonging to user inquiries, and the other to assistant replies.

In the three clustering experiences, most of the clusters are labelled with
either ‘hotel-inform’ or ‘hotel-request’, which are the most frequent labels
of utterances in the hotel domain, as seen in Figure 4. We can understand
that, despite being able to obtain reasonable clusters, it will be difficult
for the algorithm to match the level of granularity with the dataset
annotations, which explains the low results for the BCubed metrics.

###  4.4 Analysis of the dialogue flow

For this part of the experience, we feed the results from the intra-domain
clustering of the hotel domain to the tool for analysis of sequences. In Table
10, the most frequent flows between these 28 clusters are presented, which can
be informally analysed resorting to the most relevant utterances in each
cluster.

Table 10: The most frequent sequences of the identified 28 clusters for the
hotel domain.

n | sequence | frequency
---|---|---
2 | $26\rightarrow 19$ | 767
2 | $19\rightarrow 12$ | 625
2 | $10\rightarrow 19$ | 621
2 | $26\rightarrow 10$ | 574
2 | $27\rightarrow 19$ | 559
2 | $26\rightarrow 12$ | 492
2 | $26\rightarrow 23$ | 492
2 | $19\rightarrow 11$ | 451
2 | $19\rightarrow 23$ | 435
2 | $21\rightarrow 19$ | 420
3 | $26\rightarrow 10\rightarrow 19$ | 249
3 | $26\rightarrow 19\rightarrow 12$ | 204
3 | $10\rightarrow 19\rightarrow 12$ | 166
3 | $27\rightarrow 10\rightarrow 19$ | 162
3 | $27\rightarrow 19\rightarrow 12$ | 161
3 | $26\rightarrow 10\rightarrow 12$ | 156
3 | $27\rightarrow 26\rightarrow 19$ | 155
3 | $10\rightarrow 26\rightarrow 19$ | 151
3 | $26\rightarrow 10\rightarrow 23$ | 141
3 | $26\rightarrow 19\rightarrow 23$ | 141

Figure 8: A dialogue example with the assigned clusters.

Clusters 26 and 27 appear frequently, which are composed of utterances where
the user is asking for a hotel with some specific restrictions: the former
with the intent for a particular star rating, and the latter with parking
or/and wifi restrictions. Afterwards, the most common clusters are 10 and 19:
cluster 10 identifies the lack of domain entities obeying to the given
specifications; and cluster 19 suggests a hotel or guesthouse. Cluster 12 is
also frequent, usually assigned to utterances where the user is starting the
booking process.

Despite being possible to make this correspondence, some cases do not follow
these labels, such as the transition $10\rightarrow 19$, that apparently
matches two subsequent assistant utterances. As the utterances from the user
and assistant are all clustered at the same time, semantically similar
utterances from both of the parts can be assigned the same cluster. However,
this experience was not focused on dividing the utterances between user and
system, as this also does not happen in the dataset reference labels: as an
example, there are a lot of ‘hotel-inform’ subsequent utterances.

As an example, we provide a dialogue example with the assigned clusters, in
Figure 8. The dialogue starts with the transition $26\rightarrow 19$, which is
the most common transition in the dataset. Afterwards, it classifies two
subsequent utterances with the cluster 10, which can be justified by being
semantically close (both present negative sentences). The user comes back to
providing hotel restrictions, which is aligned with what we have seen about
cluster 26. The following suggestion from the assistant (the $6^{th}$
utterance) is also assigned to the cluster 26, which is not aligned with what
we discovered about the clusters — it should probably be assigned with cluster
19. One justification for these errors can be, that as we are forcing the
algorithm to assign one cluster to each utterance (as we used the results from
soft-clustering), very weak classifications are also being considered.
Besides, the most frequent clusters should also be the ones that are not that
specific, and the algorithm has more difficulties in classifying. When it
comes to the booking itself, the algorithm assigns two different clusters for
asking and providing the requirements, 15 and 2, which are in accordance with
the main topics extracted from the clusters: the first one is confirming the
hotel has free parking, and the latter providing the required hotel details.

##  5 Conclusion and Future Work

In this work, we successfully built a framework that is able to identify
dialogue intentions, in an unsupervised manner. To do so, we developed a
clustering tool for dialogue utterances, which groups them according to their
similarity and intention. As seen in the experiments, we were able to obtain
reasonable clusters with different levels of granularity, supporting the idea
that the algorithm parameters should be adapted to each use case and nature of
the data, regardless of how general the algorithm should be.

Besides, the sequence analysis tool proved to be able to find relevant flows
of intentions in a dialogue, which can be helpful for dialogue management
applications. In future work, it would make sense to perform two different
clustering experiences, for user and assistant utterances apart, to ensure
they are not mixed in the same clusters. Depending on the application, this
information could even be available, and an analysis of the sequence of user
requests without the assistant (and vice versa) could be valuable.

Besides, the problem of identifying dialogue flows can be further investigated
by modifying the sequence analysis tool to return sequences obeying to
different specifications, such as a longer length or sequences that do not
include a certain cluster. Regardless of that, these results do already prove
that it is possible to identify relevant clusters in a dialogue application,
and analyse their most common flows in an unsupervised scenario. Other
opportunities of future work are the creation of a taxonomy of intents, and
the comparison with the one provided in the datasets.

## Acknowledgements

This work was conducted within the IAG (Intelligent Agents Generator) project
with the universal code LISBOA-01-0247-FEDER-045385, co-funded by Lisboa 2020,
Portugal 2020, and the European Union, through the European Regional
Development Fund.

## References

  * Amigó et al., (2009) Amigó, E., Gonzalo, J., Artiles, J., and Verdejo, F. 2009\.  A comparison of extrinsic clustering evaluation metrics based on formal constraints.  Information Retrieval, 12(4):461–486.
  * Bagga and Baldwin, (1998) Bagga, A. and Baldwin, B. 1998\.  Entity-Based Cross-Document Coreferencing Using the Vector Space Model.  79\.
  * Budzianowski et al., (2018) Budzianowski, P., Wen, T.-h. H., Tseng, B.-H., Casanueva, I., Ultes, S., Ramadan, O., and Gašić, M. 2018\.  MultiWOZ - A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling.  In Proc. of the Conference on Empirical Methods in Natural Language Processing.
  * Campello et al., (2015) Campello, R. J., Moulavi, D., Zimek, A., and Sander, J. 2015\.  Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection.  ACM Transactions on Knowledge Discovery from Data, 10(1):1–51.
  * Chatterjee and Sengupta, (2020) Chatterjee, A. and Sengupta, S. 2020\.  Intent Mining from past conversations for Conversational Agent.  pp. 4140–4152.
  * Chatterjee and Sengupta, (2021) Chatterjee, A. and Sengupta, S. 2021\.  Intent Mining from past conversations for conversational agent.  arXiv.
  * Daszykowski and Walczak, (2009) Daszykowski, M. and Walczak, B. 2009\.  Density-Based Clustering Methods.  Comprehensive Chemometrics, 2:635–654.
  * Devlin et al., (2019) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. 2019\.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In Proc. of the Conference of the North American Chapter of the Association for Computational Linguistics.
  * Gao et al., (2008) Gao, C., Wang, J., He, Y., and Zhou, L. 2008\.  Efficient mining of frequent sequence generators.  In Proceedings of the 17th International Conference on World Wide Web, WWW ’08, 1051–1052, New York, NY, USA. Association for Computing Machinery.
  * Ghaemi and Farnaghi, (2019) Ghaemi, Z. and Farnaghi, M. 2019\.  A Varied Density-based Clustering Approach for Event Detection from Heterogeneous Twitter Data.  ISPRS International Journal of Geo-Information, 8(2):1–18.
  * Haponchyk et al., (2020) Haponchyk, I., Uva, A., Yu, S., Uryupina, O., and Moschitti, A. 2020\.  Supervised Clustering of Questions into Intents for Dialog System Applications.  Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018, pp. 2310–2321.
  * Laban et al., (2021) Laban, P., Bandarkar, L., and Hearst, M. A. 2021\.  News Headline Grouping as a Challenging NLU Task.
  * Lloyd, (1982) Lloyd, S. P. 1982\.  Least Squares Quantization in PCM.  IEEE Transactions on Information Theory, 28(2):129–137.
  * McInnes and Healy, (2017) McInnes, L. and Healy, J. 2017\.  Accelerated Hierarchical Density Based Clustering.  IEEE International Conference on Data Mining Workshops, ICDMW, 2017-Novem:33–42.
  * McInnes et al., (2018) McInnes, L., Healy, J., and Melville, J. 2018\.  UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction.
  * Mikolov et al., (2013) Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. 2013\.  Distributed Representations of Words and Phrases and their Compositionality.  In Proc. of the International Conference on Neural Information Processing Systems.
  * Pei et al., (2001) Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., and Hsu, M. C. 2001\.  PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth.  Proceedings - International Conference on Data Engineering, pp. 215–224.
  * Pennington et al., (2014) Pennington, J., Socher, R., and Manning, C. 2014\.  GloVe: Global Vectors for Word Representation.  In Proc. of the Conference on Empirical Methods in Natural Language Processing.
  * Perkins and Yang, (2019) Perkins, H. and Yang, Y. 2019\.  Dialog Intent Induction with Deep Multi-View Clustering.  arXiv, pp. 4016–4025.
  * Peters et al., (2018) Peters, M. E., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., and Zettlemoyer, L. 2018\.  Deep Contextualized Word Representations.  In Proc. of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies.
  * Radford and Salimans, (2018) Radford, A. and Salimans, T. 2018\.  Improving Language Understanding by Generative Pre-Training.  OpenAI Blog.
  * Reimers and Gurevych, (2020) Reimers, N. and Gurevych, I. 2020\.  Sentence-BERT: Sentence embeddings using siamese BERT-networks.  EMNLP-IJCNLP 2019 - 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing, Proceedings of the Conference, pp. 3982–3992.
  * van der Maaten and Hinton, (2008) van der Maaten, L. and Hinton, G. 2008\.  Visualizing Data using t-SNE.  Journal of Machine Learning Research 9.
  * Wang and Han, (2004) Wang, J. and Han, J. 2004\.  Bide: Efficient mining of frequent closed sequences.  pp. 79–90.  Proceedings - 20th International Conference on Data Engineering - ICDE 2004 ; Conference date: 30-03-2004 Through 02-04-2004.