i
Documen Clus e ing as an app oach o empla e
ex ac ion
And é Miguel Fe nandes Rod igues
Disse a ion p esen ed as pa ial equi emen o ob aining
he Mas e ’s deg ee in In o ma ion Managemen
i
NOVA In o ma ion Managemen School
Ins i u o Supe io de Es a ís ica e Ges ão de In o mação
Uni e sidade No a de Lisboa
DOCUMENT CLUSTERING AS AN APPROACH TO TEMPLATE
EXTRACTION
by
And é Miguel Fe nandes Rod igues
Disse a ion p esen ed as pa ial equi emen o ob aining he Mas e ’s deg ee in In o ma ion
Managemen , Specializa ion in Knowledge Managemen and Business In elligence
Ad iso : P o esso a Dou o a Ma iana Sá Co eia Lei e de Almeida
Co Ad iso : Rica do Cos a Dias Rei
July 2021
ii
ACKNOWLEDGEMENTS
I wan o exp ess my g a e ulness o my ad iso s Ma iana Almeida and Rica do Rei, o Cle e ly o he
oppo uni y, o my iends, and o my amily.
This p ojec has ecei ed unding om he Eu opean Union’s Ho izon 2020 esea ch and inno a ion
p og am unde g an ag eemen No 873904.
iii
ABSTRACT
A g ea pa o cus ome suppo is done ia he exchange o emails. As he numbe o emails
exchanged daily is cons an ly inc easing, companies need o ind app oaches o ensu e i s e iciency.
One common s a egy is he usage o empla e emails as an answe . These answe s empla es a e
usually ound by a human agen h ough he epe i i e usage o he same answe . In his wo k, we
use a clus e ing app oach o ind hese answe empla es. Se e al clus e ing algo i hms a e
esea ched in his wo k, wi h a ocus on he k-means me hodology, as well as o he clus e ing
componen s such as simila i y measu es and p e-p ocessing s eps. As we a e dealing wi h ex da a,
se e al ex ep esen a ion me hods a e also compa ed. Due o he peculia i y o he p o ided da a,
we a e able o design me hodologies o ensu e he easibili y o his ask and de elop s a egies o
ex ac he answe empla es om he clus e ing esul s.
KEYWORDS
Documen Clus e ing; Simila i y Measu es; Tex Rep esen a ion; Templa e; Na u al Language
P ocessing
i
INDEX
1. In oduc ion .................................................................................................................. 1
1.1. Mo i a ion ............................................................................................................. 1
1.2. Goal and Con ibu ions ......................................................................................... 1
2. Backg ound ................................................................................................................... 3
2.1. Supe ised Machine Lea ning ............................................................................... 3
2.1.1. Pe cep on ...................................................................................................... 3
2.1.2. Mul i-Laye Pe cep on .................................................................................. 4
2.1.3. T ans ome s .................................................................................................... 5
2.2. Unsupe ised Machine Lea ning ........................................................................... 7
2.2.1. Pa i ioning Algo i hms .................................................................................. 8
2.2.1.1. K-means ................................................................................................................... 8
2.2.1.2. K-medoids ................................................................................................................ 9
2.2.1.3. K-means++ ............................................................................................................... 9
2.2.1.4. Sphe ical K-means ................................................................................................... 9
2.2.2. Hie a chical Clus e ing ................................................................................. 10
2.2.3. Densi y-Based Clus e ing Algo i hms ........................................................... 11
2.3. Clus e E alua ion ................................................................................................ 12
2.3.1. Ex e nal Clus e E alua ion .......................................................................... 12
2.3.1.1. F-measu e and Rand Index .................................................................................... 12
2.3.1.2. En opy and Pu i y ................................................................................................. 14
2.3.1.3. V-measu e ............................................................................................................. 14
2.3.2. In e nal Quali y Measu es ............................................................................ 15
2.4. Tex Rep esen a ion ............................................................................................ 17
2.4.1. Spa se Models .............................................................................................. 17
2.4.2. Dense Models ............................................................................................... 18
2.4.3. BERT .............................................................................................................. 18
2.5. Simila i y Measu es and Tex Compa ison .......................................................... 20
2.5.1. Simila i y Measu es ...................................................................................... 20
2.5.2. Tex dis ances ............................................................................................... 20
3. Rela ed Wo k .............................................................................................................. 22
3.1. Clus e ing Me hodology ...................................................................................... 22
3.2. BERT-Based models ............................................................................................. 23
3.3. Documen Clus e ing ........................................................................................... 24

3.3.1. Spam Fil e .................................................................................................... 24
3.3.2. Templa e Finde ........................................................................................... 25
4. Co pus and Da a Analysis ........................................................................................... 26
4.1. Cle e ly Co pus .................................................................................................... 26
4.2. C ea ed Co po a .................................................................................................. 27
4.2.1. Sil e Co pus ................................................................................................. 27
4.2.2. Anno a ed Pai s o Templa es ...................................................................... 27
4.3. E alua ion Tasks .................................................................................................. 28
4.3.1. Tasks and Expe imen s ................................................................................. 28
4.3.1.1. G ouping Task ........................................................................................................ 29
4.3.1.2. Rela ionship be ween Me ics .............................................................................. 30
4.3.2. Tex P e-p ocessing and Algo i hm E alua ion ............................................ 31
4.3.2.1. Tex P ep ocessing ................................................................................................ 31
4.3.2.2. Clus e ing Ex e nal E alua ion............................................................................... 32
5. Resul s and Discussion ................................................................................................ 34
5.1. Expe imen al Se up ............................................................................................. 34
5.1.1. Op imal K-means .......................................................................................... 35
5.1.2. Cosine Algo i hm .......................................................................................... 35
5.2. Templa e Ex ac ion ............................................................................................ 36
5.2.1. Pa i ion Analysis .......................................................................................... 37
5.2.2. Candida es Quali y and Templa e Ex ac ion ............................................... 37
6. Conclusion .................................................................................................................. 39
7. Limi a ions and Fu u e Wo k ...................................................................................... 40
8. Bibliog aphy ................................................................................................................ 41
i
LIST OF FIGURES
Figu e 2.1: Rep esen a ion o an MLP wi h wo hidden laye s. ................................................ 4
Figu e 2.2: G aphical ep esen a ion o an RNN. Taken om h ps:// inyu l.comm/4jkgusp 5
Figu e 2.3: G aphical Rep esen a ion o he T ans o me s model a chi ec u e. Taken om
(Vaswani, e al., 2017). ....................................................................................................... 6
Figu e 2.4: G aphical ep esen a ion o ha d clus e ing s so clus e ing. Taken om
h ps:// inyu l.com/19 ic4a ............................................................................................. 7
Figu e 2.5: Example o K-means algo i hm wi h k=3. Taken om
h ps:// inyu l.com/3mxykbu9 .......................................................................................... 8
Figu e 2.6: Example o a Dend og am. Taken om h ps:// inyu l.com/c alh7qq ................. 10
Figu e 2.7: BERT inpu ep esen a ion. Taken om (De lin, Chang, Lee, & Tou ano a, 2018)
.......................................................................................................................................... 19
Figu e 3.1 - SBERT a chi ec u e a in e ence, aken om (Reime s & Gu e ych, 2019) ......... 24
Figu e 4.1: Dis ibu ion o human simila i y sco e in auxilia y co pus .................................... 28
ii
LIST OF TABLES
Table 2.1: Decision Meaning .................................................................................................... 13
Table 4.1: Co pus S a is ics ...................................................................................................... 26
Table 4.2: Anno a ion c i e ia .................................................................................................. 27
Table 4.3: G ouping Task E alua ion ........................................................................................ 29
Table 4.4: Co ela ion be ween me ics .................................................................................. 30
Table 4.5: Di e ences be ween S emming and Lemma iza ion .............................................. 32
Table 4.6: A e age ARI in di e en p e-p ocessing combina ions .......................................... 33
Table 4.7: A e age V-measu e in di e en p e-p ocessing combina ions .............................. 33
Table 5.1: A e age Silhoue e Sco e pe Numbe o Clus e s ................................................. 35
Table 5.2: Top 5 clus e s wi h highe a e age silhoue e sco e .............................................. 38
iii
LIST OF ABBREVIATIONS AND ACRONYMS
AI A i icial In eligence
Seq2Seq Sequence- o-Sequence
RNN Recu en Neu al Ne wo ks
DBSCAN Densi y-based spa ial clus e ing o applica ions wi h noise
ARI Adjus ed Rand Index
BoW Bag-o -Wo ds
TF-IDF Te m F equency-In e se Documen F equency
CBOW Con inuous Bag-o -Wo ds
BERT Bidi ec ional Encode Rep esen a ions om T ans o me s
KLD Kullback-Leible Di e gence
SVM Suppo Vec o Machines
KNN K nea es neighbo s
7
2.2. UNSUPERVISED MACHINE LEARNING
Unsupe ised Machine Lea ning algo i hms di e om Supe ised ones in ha he a ge a iables a e
no known. The e o e, his lea ning consis s in disco e ing a s uc u e o ela ionship be ween he
di e en inpu s.
Al hough he e a e se e al me hods o Unsupe ised Machine Lea ning, he mos known algo i hms
a e ela ed o Clus e ing which is he main ocus o his wo k.
Clus e ing is he ask o sepa a ing da a in o g oups o simila poin s. (Kau man & Rousseew, 1990)
s a e i as “ he a o inding g oups in da a”. These esul ing g oups a e called clus e s. One goal when
clus e ing is o make poin s belonging o a clus e simila be ween hemsel es (i.e., ha e a high in a-
clus e simila i y) and educe he simila i y be ween poin s om o he clus e s (i.e., ha e a low in e -
clus e simila i y). Simila i y is a measu e o he ela ionship be ween wo poin s.
Clus e ing algo i hms can be di ided in wo main ca ego ies: ha d clus e ing and so clus e ing. The
di e ence be ween hem is ha while in ha d clus e ing each poin belongs solely o one clus e , in
so clus e ing a poin can be pa o mo e han one clus e .
Figu e 2.4: G aphical ep esen a ion o ha d clus e ing s so clus e ing. Taken om
h ps:// inyu l.com/19 ic4a
In his wo k, we will be ocusing on ha d clus e ing.
As men ioned be o e in Sec ion 1.2, he clus e ing esul s depend on he ep esen a ion o each poin ,
he simila i y measu e and he clus e ing algo i hm used (Jain, Mu y, & Flynn, 1999). I is wo hy o
no e ha while li e a u e o e s a la ge po olio o clus e ing algo i hms, he e is no uni e sal
me hodology ha applies pe ec ly o e e y case and da ase .
Th ee ypes o clus e ing algo i hms can be dis inguished, which will be discussed and gi en examples
in his chap e :
- Pa i ioning Algo i hms
- Hie a chical Algo i hms
- Densi y-based Algo i hms
While each ca ego y aims o ha e a clus e ing esul ha sa is ies he simila i y cons ain , hey all do
i di e en ly. The pa i ion algo i hm c ea es a la pa i ion o a speci ied numbe o clus e s based on

8
a simila i y measu e. Hie a chical algo i hms aim o c ea e a hie a chical ee o clus e s (dend og am).
And densi y-based algo i hms as he name sugges s, inds clus e s by using he dense egion o da a
poin s and u ilizes he low-densi y egions as bounda ies be ween clus e s.
2.2.1. Pa i ioning Algo i hms
Pa i ion clus e ing algo i hms aim o op imize a ce ain c i e ion unc ion o sepa a e (o pa i ion)
he da a objec s in o a numbe o k clus e s, based on a simila i y measu e. A common disad an age
o hese ypes o algo i hms is ha , depending on he ini ializa ion, hey can each di e en solu ions.
2.2.1.1. K-means
Pe haps he mos well-known clus e ing algo i hm, K-means was i s used by Macqueen (1967). I s
popula i y is due o i s simplici y and abili y o be used o any ype o p oblems. The idea behind k-
means is ha a clus e can be ep esen ed by a cen al poin . This algo i hm uses he concep o
cen oid which is he mean poin o he elemen s o a clus e .
The k-means algo i hm begins by se ing k ini ial andom cen oids. A e wa ds, each poin is assigned
o i s close cen oid, based on a simila i y measu e usually being he squa ed Euclidean dis ance. The
cen oids a e hen ecalcula ed by a e aging all he poin s in each clus e , and he i e a ion begins
anew. This algo i hm keeps unning un il con e gence is ob ained which is when no eassignmen o
he cen oid occu s o when he maximum numbe o i e a ions has occu ed.
Figu e 2.5: Example o K-means algo i hm wi h k=3. Taken om h ps:// inyu l.com/3mxykbu9
The wo main disad an ages o k-means a e as ollows: 1) he need o indica e he k numbe o clus e s
be o e he clus e ing (which may b ing bad clus e ing accu acy). Ou lie s can also g ea ly dis u b he
compu a ion o he cen oid. 2) he ac ha he ini ial clus e cen oids may be a bad choice which in
u n can ge he cen oid o be apped in a local minimum.
To mi iga e hese disad an ages, he e a e some me hods ha can be applied, which will be discussed
in his wo k.
9
2.2.1.2. K-medoids
K-medoids is a a ia ion o k-means ha ins ead o using he mean (cen oid) uses he median
(medoid). To no e ha in k-means he cen oid a ely co esponds o an ac ual da a elemen while he
medoid in k-medoids mus be an elemen o he da a ( o example a documen in documen clus e ing)
which makes he in e p e a ion easie . This ea u e o k-medoids migh be g ea in his p ojec as we
wan o ex ac om each clus e a eal documen ha ep esen s i . The k-medoids algo i hm is also
less sensi i e o ou lie s and noise.
2.2.1.3. K-means++
K-means++ algo i hm is a a ian o k-means p oposed by (A hu & Vassil i skii, 2007). This a ia ion
seeks o lessen i s o iginal’s disad an age o possible bad ini ializa ion by al e ing i s ini ial condi ions.
Le 𝑑(𝑥) ep esen he minimal dis ance om da a poin 𝑥 o a clus e cen e al eady chosen. The
algo i hm o cen e ini ializa ion is as ollows:
1. Randomly choose one o he da a poin s as a clus e cen e 𝑐1.
2. Fo each da a poin 𝑥, de e mine 𝑑(𝑥).
3. Choose he nex clus e cen e 𝑐𝑖, based on he 𝑥 wi h highes p obabili y 𝑑(𝑥)2
∑𝑑(𝑥)2
𝑥𝜖𝑋
4. Repea s eps 2 and 3 un il k cen e s ha e been selec ed.
5. P oceed wi h he s anda d k-means algo i hm.
The K-means++ is as such designed o enhance he clus e cen e ini ializa ion o k-means.
2.2.1.4. Sphe ical K-means
In an e o o exploi he spa si y o ex da a ( he ype o da a we will explo e in his wo k) and
d awing insigh s o i s dis ibu ion in high-dimension spaces, (Dhillon & Modha, 2001) p opose a
a ian o he well-known “Euclidean” k-means by using cosine simila i y as i s simila i y measu e.
Fi s ly, his algo i hm has he assump ion ha he documen ec o s ha e been no malized o ha e
uni 𝐿2 no m ( o each da a poin 𝑧, ‖𝑧‖=1) which in u n means hey can be ep esen ed as poin s
on a high-dimension uni sphe e (hence he name sphe ical k-means). As such, documen s wi h
di e en leng hs bu wi h equi alen subjec s will be ega ded as simila ec o -wise.
The cosine simila i y can be de i ed om he Euclidean do p oduc o mula and is ep esen ed as
such:
𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦=cos(𝜃)= 𝐴∗𝐵
||𝐴|| ||𝐵||= ∑𝐴𝑖𝐵𝑖
𝑛𝑖=1
√∑𝐴𝑖2
𝑛𝑖=1 √∑𝐵𝑖2
𝑛𝑖=1
Howe e , i he elemen ( o example documen s) ec o s a e no malized, he cosine simila i y can be
ep esen ed simply as he do p oduc be ween he ec o s.
10
The sphe ical k-means algo i hm ollows he same pa e n as egula k-means wi h small di e ences:
1. Randomly selec k documen ec o s as he concep ec o s (which in egula k-means would
be named cen oid)
2. Fo each documen ec o 𝑥𝑖, compu e he closes concep ec o in cosine simila i y and
assign 𝑥𝑖 o i s clus e .
3. Compu e he new concep ec o s as he no malized mean in each clus e .
4. Repea s eps 2 and 3 un il some s opping c i e ia is achie ed.
2.2.2. Hie a chical Clus e ing
Dis inc ly om pa i ion clus e ing me hods, hie a chical clus e ing seeks o build a ee o clus e
usually ep esen ed by a dend og am. These me hods can be u he ca ego ized as agglome a i e o
di isi e depending on how he clus e ing ee is buil . While he agglome a i e app oach begins wi h
each poin being an indi idual clus e and is p og essi ely joined wi h i s nex mos simila clus e in a
bo om-up ashion un il all poin s a e in one clus e , he di isi e app oach begins wi h all he poin s
oge he in one clus e and i e a i ely spli s hem un il single poin s, in a op-down low.
Figu e 2.6: Example o a Dend og am. Taken om h ps:// inyu l.com/c alh7qq
One main ad an age o e p e ious clus e ing algo i hms is he ac ha he e is no need o speci y he
numbe o clus e s. In con as , hese ypes o algo i hms can ha e bad ou pu s i w ong me ges o
spli s a e made as hose s eps a e i e e sible.
11
Agglome a i e hie a chical clus e ing algo i hms a e usually as ollows:
1. Take each poin as a single clus e .
2. Compu e he simila i y be ween each o he clus e o ind he closes (mos simila ) pai .
3. Me ge he simila clus e o c ea e a new clus e .
4. Repea s eps 2) and 3) un il he e is only one clus e .
The mos impo an s ep in his kind o algo i hm is made be ween s ep 1 and 2 which is o choose
how o calcula e he simila i y be ween wo clus e s. The e a e many ways o calcula e his simila i y
be ween hem such as: min, whe e he simila i y be ween wo clus e s is he minimum dis ance
be ween wo poin s om di e en clus e s; max, whe e he simila i y is gi en by he maximum
dis ance be ween wo poin s in di e en clus e s; o a e age, whe e he simila i y is he calcula ed
a e age o all he dis ances be ween all poin s om he i s clus e wi h all he o he s om he second
one.
Di isi e hie a chical clus e ing wo ks as he opposi e o Agglome a i e algo i hms, whe e i begins wi h
one clus e and keeps on spli ing un il clus e s a e single da a poin s.
Bisec ing k-means is an example o di isi e hie a chical clus e ing. As he name en ails, i is a a ian
o K-means. This me hod’s main idea is o keep applying he k-means algo i hm o each pa i ion. The
algo i hm is as ollows:
1. All documen s a e placed in o one Clus e .
2. Pick a clus e o spli .
3. Apply K-means wi h k=2. (Bisec ing s ep)
4. Repea s eps 2 and 3 un il he desi ed numbe o clus e k is achie ed.
In s ep 2, he e a e se e al app oaches o choose which clus e o spli , i could be he one wi h he
leas o e all simila i y, he la ges clus e , o a mix u e o bo h c i e ia. Acco ding o (S einbach,
Ka ypis, & Kum a , 2000) he e a e no signi ican di e ences in esul s be ween he c i e ions. They
also conclude ha he bisec ing K-means echnique is be e han he s anda d K-means app oach and
is as good o be e han he usual hie a chical algo i hms.
2.2.3. Densi y-Based Clus e ing Algo i hms
Densi y-based clus e ing algo i hms ins ead o using p oximi y o g oup objec s, a e based on he
no ion o densi y. The co e concep is o keep me ging poin s wi h a clus e as long as he densi y
emains high.
Densi y Based Spa ial Clus e ing o Applica ion wi h Noise o DBSCAN is he mos well-known algo i hm
o his ype. Like Hie a chical Clus e ing, i does no need he numbe o clus e s as an inpu pa ame e .
I has howe e wo use de ined pa ame e s: he epsilon (ε) and he minimum numbe o sample M.
Rega ding ε, wo poin s a e conside ed neighbo s i he dis ance be ween hem is smalle han epsilon.
M is he minimum numbe o neighbo s a ce ain poin mus ha e o be ca ego ized as a co e poin .
The e a e h ee classi ica ions o poin s: co e, bo de , and ou lie .
12
A co e poin has a leas m poin s in i s neighbo hood (including i sel ). A bo de poin does no ha e
a leas m poin s in i s neighbo hood bu is he icini y o a co e poin . Finally, an ou lie o noise poin
is a poin ha does no belong o he neighbo hood o a co e poin .
The s anda d DBSCAN algo i hm s a s wi h no p e-selec ed clus e s and can be seen as:
1. Pick a andom poin ha has no been assigned o a clus e and is no assigned as an ou lie .
Analyze he neighbo hood acco ding o M. I he poin is a co e poin , i is a new clus e . I i is
no , assign as an ou lie and pick ano he poin .
2. Add he neighbo hood poin s o he co e poin o he clus e . Check he neighbo hood poin s
o co e poin s and add i s neighbo hood o he clus e . Repea un il no mo e new poin s a e
added o he clus e . P e iously assigned ou lie s may be now assigned as bo de poin s.
3. Repea s ep 1 and 2 un il e e y poin has been isi ed and hey a e ei he pa o a clus e o
an ou lie .
As he name s a es, his algo i hm is esis an o noise and can handle ou lie s. Howe e , i is does no
handle high dimensional da a oo well, which is a p oblem in documen clus e ing.
2.3. CLUSTER EVALUATION
We ha e p esen ed di e en algo i hms and me hods o be used in da a clus e ing. Howe e , as i is
an unsupe ised lea ning ask, in eal p oblems he e a e usually no a p io i in o ma ion abou he
da ase . This makes he alida ion o he clus e ing esul s a challenging phase when applying a
clus e ing algo i hm and o en ega ded as impo an as he clus e ing i sel (Hassani & Seidl, 2017).
One ype o in o ma ion no usually known is he numbe o clus e s. Algo i hms like K-means (sec ion
2.2.1.1.) depend on such pa ame e and he sea ch o he op imal k is a highly non- i ial ask. Hence,
many clus e alidi y me hods ha e been in oduced in li e a u e o sol e hese p oblems and o
e alua e he pa i ions o he da a o ep esen i s o iginal s uc u e.
Two main ypes o e alua ion measu es can be dis inguished: ex e nal e alua ion and in e nal
e alua ion. Along his subchap e we will be going h ough each o hem, gi e some examples and
s a e hei ad an ages and disad an ages.
2.3.1. Ex e nal Clus e E alua ion
Ex e nal Valida ion Measu es a e based on p e ious knowledge abou da a. This usually means o
compa e he esul s o a clus e ing algo i hm o a p o ided labeled pa i ion o he da a. I s in en is
o measu e how simila he clus e labels ma ch a se o p ede ined classes deemed as he ue clus e s
(commonly e e ed o as he gold s anda d).
2.3.1.1. F-measu e and Rand Index
E alua ion measu es used o usually e alua e classi ica ion me hods can be applied o pa e n
ecogni ion when he g ound u h is known. The mos common measu es a e Recall, P ecision and i s
ha monic mean, F1-measu e. These e alua ion measu es usually use he concep s o T ue Posi i e

13
(TP), T ue Nega i e (TN), False Posi i e (FP) and False Nega i e (FN) in i s calcula ion and a e calcula ed
o e pai s o poin s. Gi en wo documen s, hey a e conside ed as a TP decision i hey a e simila and
we e assigned o he same clus e . I he documen s a e no simila and we e assigned o di e en
clus e s, hey a e conside ed a TN decision. On he o he hand, i wo no simila documen s a e
assigned o he same clus e , i is a FP decision. Finally, a FN decision is when wo simila documen s
a e assigned o di e en clus e s. By knowing he g ound u h, we can asce ain i wo documen s a e
simila i hey belong o he same class (o label). Table 2.1 illus a es hese concep s.
Table 2.1: Decision Meaning
Assigned Same Clus e
Assigned di e en clus e s
Belong same class
TP
FN
Belong di e en classes
FP
TN
As we will be using hese concep s in a clus e ing p oblem, he P ecision and Recall can be w i en as
he ollowing:
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛(𝑖,𝑗)= 𝑇𝑃
𝑇𝑃+𝐹𝑃=𝑛𝑖𝑗
𝑛𝑖
𝑅𝑒𝑐𝑎𝑙𝑙(𝑖,𝑗)=𝑇𝑃
𝑇𝑃+𝐹𝑁= 𝑛𝑖𝑗
𝑛𝑗
Whe e 𝑛𝑖𝑗 is he numbe o elemen s o label 𝑖 ha a e in clus e 𝑗; 𝑛𝑖 is he numbe o elemen s in
label 𝑖 and 𝑛𝑗 is he numbe o objec s in clus e 𝑗.
As he F-Measu e is he ha monic mean o he p e ious concep s, i is gi en by he ollowing equa ion:
𝐹(𝑖,𝑗)= 2 ∗ 𝑅𝑒𝑐𝑎𝑙𝑙(𝑖,𝑗)∗𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛(𝑖,𝑗)
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛(𝑖,𝑗)+𝑅𝑒𝑐𝑎𝑙𝑙(𝑖,𝑗)
Label 𝑖 has he F-measu e equi alen o he maximum alue a any clus e . The o e all F-measu e o
he clus e ing is gi en by he weigh ed a e age o all he labels’ F-measu e:
𝐹= ∑𝑛𝑖
𝑛max𝐹(𝑖,𝑗)
𝑖
One o he i s clus e ing alida ion measu es was he Rand Index, also known as accu acy. P esen ed
by (Rand, 1971),i is calcula ed as he p opo ion o accu a e assignmen s o e all assignmen s. Using
he p e ious no ions, i is de ined as:
𝑅𝐼= 𝑇𝑃+𝑇𝑁
𝑇𝑃+𝐹𝑃+𝐹𝑁+𝑇𝑁
14
An imp o emen on his index was de eloped named Adjus ed Rand Index (ARI). One o i s ad an ages
o e i s p edecesso is i s abili y o compa e pa i ions o he da a wi h di e en numbe o clus e s.
Using he p e ious no ions, i can be de ined as (San os & Emb ech s, 2009):
𝐴𝑅𝐼=(𝑛2) (𝑇𝑃+𝑇𝑁)−[(𝑇𝑃+𝐹𝑃)(𝑇𝑃+𝐹𝑁)(𝐹𝑁+𝑇𝑁)(𝐹𝑃+𝑇𝑁)]
(𝑛2)2−[(𝑇𝑃+𝐹𝑃)(𝑇𝑃+𝐹𝑁)+(𝐹𝑁+𝑇𝑁)(𝐹𝑃+𝑇𝑁)]
G ea e alues in hese measu es sugges highe quali y o he clus e ing esul .
2.3.1.2. En opy and Pu i y
En opy measu es how sp ead a dis ibu ion is. I all clus e s ha e only objec s o a single label, he
calcula ed en opy will be 0. As he a ie y o labels pe clus e inc eases he wo se he clus e ing is
and he highe he en opy. Using he p e ious no a ion, he p obabili y o a membe o clus e j
belonging o he label I is 𝑝𝑖𝑗=𝑛𝑖𝑗
𝑛𝑗. The en opy o each clus e j is calcula ed as:
𝐸𝑖= ∑𝑝𝑖𝑗∗ log𝑝𝑖𝑗
𝐿𝑖=1
Whe e L is he numbe o labels. The en opy o he clus e esul s is gi en as he weigh ed a e age o
each clus e by he size o each clus e .
𝐸𝑛𝑡𝑟𝑜𝑝𝑦= ∑𝑑𝑗
𝑑∗𝐸𝑗
𝑘
𝑖=1
Whe e k is he numbe o clus e s, d he numbe o elemen s in he da ase used o clus e ing and 𝑑𝑗
he size o he clus e j.
Pu i y measu es how g ea ly clus e s con ain elemen s o a single label. The pu i y o a clus e is gi en
by he highes p obabili y 𝑝𝑖𝑗 in he gi en clus e j. Using p e ious e minology, i is ep esen ed as
𝑝𝑢𝑟𝑖𝑡𝑦𝑗=max𝑝𝑖𝑗. Simila ly o he o e all en opy, he o e all pu i y o he clus e ing is gi en as:
𝑃𝑢𝑟𝑖𝑡𝑦= ∑𝑑𝑗
𝑑∗𝑝𝑢𝑟𝑖𝑡𝑦𝑗
𝑘
𝑖=1
2.3.1.3. V-measu e
Based on en opy, (Rosenbe g & Hi schbe g, 2007) p esen ed V-measu e which is an ex e nal clus e
e alua ion measu e cen e ed a ound he ideas o homogenei y and comple eness.
The homogenei y c i e ia’s basis is ha clus e ing mus assign only da apoin s ha belong o a single
label belong o a single clus e . Assuming he e a e 𝑁 da a samples, 𝐶 di e en classes, 𝐾 di e en
clus e s and 𝑛𝑐𝑘 ep esen s he numbe o elemen s ha belong o class 𝑐 and clus e 𝑘, he
homogenei y can be de ined as:
ℎ=1 − 𝐻(𝐶,𝐾)
𝐻(𝐶)
15
Whe e:
𝐻(𝐶,𝐾)= −∑ ∑ 𝑛𝑐𝑘
𝑁log ( 𝑛𝑐𝑘
∑𝑛𝑐𝑘
𝐶𝑐=1 )
𝐶𝑐=1
𝐾
𝑘=1
And:
𝐻(𝐶)= −∑ ∑𝑛𝑐𝑘
𝐾
𝑘=1
𝐶log (∑𝑛𝑐𝑘
𝐾
𝑘=1
𝐶)
𝐶𝑐=1
While bo h p e ious Pu i y and En opy measu es ep esen e alua ions o homogenei y o clus e ing
esul s, hey do no add ess he comple eness concep . Acco ding o (Rosenbe g & Hi schbe g, 2007),
all elemen s ha belong o a single class mus be assigned o a single clus e so ha comple eness is
achie ed. Conside ing p e ious no a ions, comple eness can be seen as:
𝑐=1 − 𝐻(𝐾,𝐶)
𝐻(𝐾)
Whe e:
𝐻(𝐾,𝐶)= −∑ ∑ 𝑛𝑐𝑘
𝑁log ( 𝑛𝑐𝑘
∑𝑛𝑐𝑘
𝐾
𝑘=1 )
𝐾
𝑘=1
𝐶𝑐=1
And:
𝐻(𝐾)= −∑ ∑𝑛𝑐𝑘
𝐶𝑐=1
𝐶log (∑𝑛𝑐𝑘
𝐶𝐶=1
𝐶)
𝐾
𝑘=1
The V-measu e is he compu ed weigh ed ha monic mean o hese wo concep s and can be gi en as
such:
𝑉= (1+𝛽)∗ℎ∗𝑐
(𝛽∗ℎ)+𝑐
Whe e β can be gi en di e en alues o a ibu e di e en weigh s in he calcula ions.
2.3.2. In e nal Quali y Measu es
As opposed o ex e nal quali y measu es, in e nal quali y measu es aim o assess how good a
clus e ing esul is using only ea u es and in insic in o ma ion om he da a se (Hassani & Seidl,
2017), meaning wi hou espec o ex e nal “gold” in o ma ion ega ding he co ec clus e s. These
measu es y o quan i y p e iously shown clus e p ope ies: clus e cohesion, meaning how simila
a e wo objec s in a clus e ; and clus e sepa a ion, meaning how dissimila a e clus e s om one
ano he .
A commonly used measu e is he Sum o Squa ed E o (SSE). I can be used o measu e cohesion by
compa ing each elemen o a clus e o i s cen oid. Wi h a simila concep , he sepa a ion o a clus e
can be measu ed by compa ing each cen oid o he cen oid o he da ase which we will call Be ween
clus e sum o squa es (BSS). They can be de ined as ollows:
16
𝑆𝑆𝐸= ∑∑(𝑥− 𝑚𝑖)2
𝑥𝜖𝐶𝑖
𝑖
𝐵𝑆𝑆= ∑|𝐶𝑖|(𝑚−𝑚𝑖)2
𝑖
Whe e 𝐶𝑖 ep esen s clus e 𝑖 wi h |𝐶𝑖| being i s size; 𝑚𝑖 ep esen ing he cen oid o clus e 𝑖, and 𝑚
he cen oid o he whole da ase .
One measu e ha combines bo h cohesion and sepa a ion ideas is he Silhoue e Coe icien . I is a
sample-based coe icien and is de ined as:
𝑠(𝑖)= 𝑏(𝑖)−𝑎(𝑖)
max (𝑎,𝑏)
Whe e 𝑎(𝑖) is he a e age dis ance be ween sample 𝑖 and all o he poin s in he same clus e , and 𝑏(𝑖)
is he minimum a e age dis ance be ween sample 𝑖 and poin s belonging o ano he clus e . The
coe icien esul anges om -1 o 1 and we can in e he ollowing: i 𝑠(𝑖) is close o 0 he sample is
be ween wo clus e s. I close o -1 hen he sample should be assigned o o he clus e s while i close
o 1, hen he sample likely belongs o he co ec clus e . This coe icien can be u he applied by
compu ing he a e age o each clus e o o all he da ase , which can gi e some gene al insigh s
when analyzing he clus e ing esul s.
Ano he measu e ha also conside s bo h cohesion and sepa a ion p ope ies is he Da ies-Bouldin
Index (DBI). P esen ed by (Da ies & Bouldin, 1979) i aimed o “in e he app op ia eness o da a
pa i ions” while “no depend(an ) on ei he he numbe o clus e s analyzed no he me hod o
pa i ioning”. This index uses he concep o clus e simila i y be ween wo clus e s 𝑖 and 𝑗 de ined as
ollows:
𝑅𝑖𝑗= 𝑠𝑖+ 𝑠𝑗
𝑑𝑖𝑗
Whe e 𝑠𝑖 is he a e age dis ance be ween he clus e ’s cen oid and each poin belonging o i - also
known as he clus e diame e ; and 𝑑𝑖𝑗 is he dis ance be ween he cen oids o clus e 𝑖 and 𝑗. The
DBI hen akes he maximum clus e simila i y o each clus e and a e ages i :
𝐷𝐵𝐼= 1𝑘 ∑max
𝑖≠𝑗 𝑅𝑖𝑗
𝑘
𝑖=1
As i akes he highes simila i y o each clus e , he smalle he index, he mo e dis inc he clus e s
a e om each o he , he e o e he be e he pa i ion is.
23
Each clus e ing echnique is hen applied o he da ase and e alua ed in e iciency a e and i s
calcula ed mean silhoue e index. When using only he signi ican wo ds, he k-medoids algo i hm has
he bes e iciency a e while k-means has he bes silhoue e index. By adding he gene al wo ds o
he ep esen a ion o he documen s and e alua ing he esul s, he hie a chical clus e ing has be e
esul s in bo h e alua ion measu es. The au ho concludes ha while he k-means me hods show he
mos signi ican silhoue e index, i is sensi i e o gene al wo ds and as such, he hie a chical clus e ing
me hod is deemed o be he be e ex clus e ing me hod as i achie es g ea esul s while no being
sensi i e o he addi ion o gene al wo ds.
The pu pose o (Balaban a ay, Sa ma, & Jha, 2015) was o compa e he k-medoids and k-means
clus e ing algo i hms. 100 documen s equally dis ibu ed be ween 5 domains we e p e-p ocessed.
Tokeniza ion, s op-wo ds emo al and TF-IDF ans o ma ions we e applied o he da a. The k-means
and k-medoids algo i hm we e hen applied and e alua ed wi h an e iciency a e. I was obse ed ha
he k-means algo i hm yields be e esul han he k-medoids.
3.2. BERT-BASED MODELS
A e he elease o BERT, a ious BERT-based models ha e eme ged. One o hem is Sen ence-BERT
(Reime s & Gu e ych, 2019). Sen ence-BERT o SBERT is a modi ica ion o he BERT ne wo k ha uses
Siamese s uc u e and iple ne wo ks o de i e seman ically meaning ul sen ence embeddings
(meaning ha seman ically simila sen ences a e close in ec o space). This enabled BERT o be used
in asks which we e no applicable o BERT such as clus e ing and la ge-scale seman ic simila i y
compa ison. In p e ious chap e s, we s a ed ha in documen clus e ing, a common me hod is o map
each sen ence o a ec o space. The clus e ing algo i hm would hen g oup close ec o s as
seman ically simila sen ences. Using egula BERT, a way o ge his ec o space embeddings is o
inpu indi idual sen ences in o BERT and use he ou pu laye as embeddings. In an e o o u he
inc ease he quali y o hese embeddings, SBERT was de eloped.
The a chi ec u e o SBERT is as ollows. Fi s ly, SBERT adds a pooling laye o he ou pu o BERT o
c ea e a ixed size sen ence embedding. Se e al s a egies such as using he ou pu o he [CLS] oken
and he mean all ou pu ec o s we e expe imen ed. Secondly, o ine- une BERT, SBERT uses a
Siamese neu al ne wo k ha uses he same weigh s while wo king in pa allel on wo di e en inpu
ec o s so ha he p oduced embeddings can be compa ed. This ne wo k objec i e unc ion depends
on he a ailable aining da a. In he pape , hey p esen h ee di e en objec i e unc ions: he
classi ica ion objec i e Func ion, whe e he wo sen ence embeddings a e conca ena ed and
mul iplied by a ainable weigh and he c oss-en opy is hen op imized; he eg ession objec i e
unc ion, whe e he cosine simila i y o he wo sen ence embeddings is compu ed and he mean-
squa ed-e o loss is op imized; and he iple objec i e unc ion, whe e gi en he sen ence a, a
sen ence p and a sen ence n wi h posi i e and nega i e in en ega ding a, he iple unc ion unes
he ne wo k so ha he dis ance be ween a and n is g ea e han a and p.
SBERT is ained on he combina ion o he SNLI and he Mul i-Gen e NLI da ase . Toge he hey add
up o one million sen ence pai s anno a ed wi h he ollowing labels: con adic ion, en ailmen and
neu al. This SBERT e sion is ine- uned wi h he Classi ica ion Objec i e Func ion.
Th oughou he pape , SBERT is e alua ed in di e en asks agains o he models speci ically such as
Uni e sal Sen ence Encode and BERT i sel . SBERT is able o achie e imp o emen s o e o he s a e-

24
o -a sen ence embeddings me hods in asks such as Seman ic Tex ual Simila i y (STS). In hese STS
asks, he da ase p o ides a label be ween 0 and 5 on he seman ic ela edness o sen ence pai s.
When checking he co ela ion be ween he cosine simila i y o sen ence ep esen a ions and he gold
labels o a ious STS he imp o emen is qui e signi ican ega ding o he models.
Apa om SBERT using BERT as he base o he model, he au ho s also use RoBERTa (Liu, e al., 2019)
as he base ans o me encode , c ea ing he SRoBERTa model. Acco ding o hem, using RoBERTa
ins ead o BERT did no yield a signi ican imp o emen in he expe imen s.
Ano he g ea ad an age s a ed by he au ho s is he ac ha SBERT is compu a ionally e icien , being
able o compu e sen ence embeddings as e han o he me hods which will be ele an in his wo k.
Figu e 3.1 - SBERT a chi ec u e a in e ence, aken om (Reime s & Gu e ych, 2019)
3.3. DOCUMENT CLUSTERING
The ollowing wo ks ha e clus e ing as a majo componen in hei me hodology. They p esen
di e en s a egies whe e documen clus e ing is ele an and se ed as inspi a ion o he p esen
wo k.
3.3.1. Spam Fil e
Emails ha e become a a ge o spam a acks due o i s popula i y and necessi y. As such, a need o
de elop mo e complex spam il e ing me hods o coun e hese a acks has s a ed o g ow. The
ollowing wo ks applied di e en algo i hms in di e en ways.
Documen clus e ing has been also applied o de ec spam emails. Tha is he case o (Sasaki & Shinnou,
2005), ha uses he Ling-Spam co pus wi h 481 spam messages ou o 2893 emails. A e ep esen ing
he documen in a ec o space, he email se is di ided in o k g oups by he sphe ical k-means
algo i hm. Then, o each c ea ed clus e , a label is assigned. I he a io o spam email o all email in
he clus e is highe han 70%, he clus e is conside ed spam. Cen oid ec o s o each clus e a e
calcula ed and used as he clus e ep esen a ion. New emails a e hen compa ed o each cen oid ia
cosine simila i y. The new email gains he same label as i s mos ele an clus e .
25
The au ho s also e alua e he impac o p e-p ocessing echniques such as lemma iza ion and s op
wo ds emo al, as well as he ep esen a ion o he documen s ia Te m F equency o TF-IDF is
expe imen ed. Classi ica ion me hods such as Suppo Vec o Machines (SVM) a e also used o
compa ison. All hese expe imen s a e e alua ed ia he p ecision o spam and non-spam assignmen .
While SVM esul s a e highe , he a ious expe imen s using his clus e ing me hod achie e
app oxima ely simila esul s as mos a ia ions o he expe imen achie e nea 100% p ecision o
bo h spam and non-spam. The au ho s conclude ha is i as e ec i e me hod o de ec ing spam.
3.3.2. Templa e Finde
In (Mo a, Ma ins, & Coheu , 2013) he aim is o build an Answe Templa e Re ie al Sys em. This
sys em e ie es a eply om a co pus o email/ eply pai s o be used by a human agen as he co e o
he esponse o a new email. As he a ailable co pus did no ha e anno a ions, such as labeling o he
email/ eply pai s, he sys em mus be able o pe o m ano he ask apa om he answe e ie al.
This ask is he iden i ica ion o simila answe s o be used as empla es. To pe o m such ask, a
clus e -based me hodology was conside ed. The idea consis s o iden i ying simila answe s using a
modi ied e sion o Jacca d Dis ance c ea ed o his p oblem named Edi Pe cen age. This measu e
dic a es how much o a gi en email mus be edi ed o be ans o med in o ano he one. The au ho s
conside wo emails o be in he same clus e i he edi Pe cen age is a mos 10%. Gi en emails A and
B which ha e an edi pe cen age lowe han 10% o email B, he au ho s conside ed A and B o be in
he same clus e e en i hei edi pe cen age is highe han 10%. Clus e s wi h only one elemen we e
emo ed. F om he 12k email/ eply pai s, 1150 clus e s we e ound. The au ho s hen de ined he
e ie al ask as a classi ica ion p oblem and as such es ed se e al algo i hms (Logis ic Reg ession, k
nea es neighbo s (KNN), and o he s) wi h a 5- old c oss alida ion. Due o he good esul s and
e iciency o KNN, u he expe imen a ion was done wi h such algo i hm. Using he p ecision@10
me ic ( he igh clus e mus be in a lis o 10 possibili ies), he bes esul was 62%.
26
4. CORPUS AND DATA ANALYSIS
In his chap e we will p esen he co pus, ha e an in-dep h analysis, and explain all he p ocessing
s ages applied o i . Due o he na u e o he da ase , some auxilia y co po a a e c ea ed and used in
some alida ion asks.
4.1. CLEVERLY CORPUS
The main goal o he hesis is o s udy unsupe ised machine lea ning me hods o disco e new email
empla es. Fo ha pu pose, we used a p op ie a y co pus o cos ume suppo ha was p o ided by
Cle e ly a e being anonymized. The co pus comp ises in o ma ion ega ding emails as well as a se
o exis ing empla es o equen eplies.
The a iables a e as ollows: Ti le, Tex _Ques ion and Tex _Answe which ep esen he i le o he
email, he con en o he sen email and he con en o he esponse email, espec i ely. The
Templa e_Numbe a iable which indica es which empla e has been used in his answe and is a null
alue i no empla e was assigned. The Templa e_Ti le a iable ep esen s he i le o he empla e
and can be seen as a small summa y o he ex . Templa e_Tex is he co e ex o he empla e and
used as basis in he Tex _Answe esponse.
In 1.1 we men ioned ha one o he s a egies o enhance cus ome suppo would be he usage o
empla es, we also s a ed some companies may al eady be using empla es and his is one o hose
cases.
When analyzing he da a, some inconsis encies and p oblems we e ound, he e o e he ollowing
ans o ma ions and il e ing we e done: some emails we e ei he blank o had non impac ul ex
(emails comp ised o only a link o a wo d o we e incomple e) and so emails wi h less han 20 wo ds
we e emo ed; when looking a he Templa e_Numbe a iable, some emails had mo e han one
empla e assigned o i . This could ha e di e en meanings, like he empla es used we e di e en
e sions o he same answe o he answe was buil ou o mo e han one empla e. As we wan o
ind new empla es, en ies ha had mo e han one empla e assigned o i we e emo ed. The
inconsis ency whe e Templa e a iable being T ue while ha ing no assigned Templa e_Numbe was
also add essed. This lea es us wi h a da ase o 54723 emails.
Nº o Emails
Nº o Answe s
wi hou Templa e
Nº o Answe s
wi h Templa e
Nº o Di e en
Templa es
54723
29937
24786
721
Table 4.1: Co pus S a is ics
As ep esen ed in Table 4.1, a ound hal o he da ase has an assigned empla e. This does no
necessa ily mean no empla es we e used on emails wi hou an assigned empla e. They could jus no
ha e been documen ed. Howe e , we know o ce ain ha emails wi h an assigned empla e we e
w i en wi h i as i s basis.
27
4.2. CREATED CORPORA
The e exis se e al me hods o e alua e clus e ing esul s (sec ion 2.3). While some me hods depend
on he in a and in e dis ance be ween clus e s, o he s depend on he g ound u h. In he p esen
wo k, we belie e ha we canno ake he emails wi h assigned empla es as a pe ec g ound u h.
Ne e heless, we can howe e use a subg oup o emails o use me ics ha ely on g ound u h. The e
is also he need o e alua e he p esen ed simila i y measu es in he gi en p oblem and unde s and i
hey achie e conclusions simila o he human agen . As such, we c ea ed wo new co po a.
4.2.1. Sil e Co pus
This de elopmen co pus is comp ised only by he emails ha ha e an assigned empla e. This new
da ase was dubbed Sil e Da ase (allusion o gold s anda d) and consis s o he 24786 emails wi h
721 di e en empla es.
This co pus will be used mainly o alida e esul s.
4.2.2. Anno a ed Pai s o Templa es
Templa es a e c ea ed om he cons an usage o simila emails. They could be ound h ough luck
and epe i ion o h ough he usage o simila i y me ics o connec simila emails. To be able o
e alua e he e aci y o his me ics and complemen his wo k, we c ea ed a da ase based on ou
no ion o simila i y.
Due o he g ea numbe o emails in he da ase , i a human agen decided o compa e e e y pai o
emails, besides un easible, mos o hese pai ed emails would be ex emely di e en om one
ano he . By using empla es, he numbe o possible compa isons is g ea ly educed and as such a
mo e no able ange o di e ences is allowed. The e o e, he basis o his new co pus is he lis o
empla es. Since we ha e 721 empla es, he e a e 259560 possible pai combina ions. We selec ed
146 andom compa isons (i.e., 146 di e en pai s o empla es) and ga e hem a sco e o how simila
i s ex s a e o each o he . This sco e goes om 0 o 4 and i s c i e ia is as ollows:
0
Comple ely di e en Templa es
1
No e y Simila Templa es
2
Rela ed Templa es
3
Ve y ela ed Templa es bu di e in a small de ail
4
Equal Templa es
Table 4.2: Anno a ion c i e ia
28
As his co pus was c ea ed by one pe son, hese anno a ions canno be seen as he u h and/o
pe ec . Howe e , hey can be used o e alua e he quali y o simila i y measu es. The sco e
dis ibu ion can be seen in igu e 4.1. Templa es a e mos ly di e en om one ano he as hey end
o espond o di e en subjec s. This can be seen in he dis ibu ion as mos o he pai s we e no
ela ed a all. On he o he hand, he le el 4 o simila i y was g an ed o 14% o he pai s, meaning ha
in he opinion o he e alua ion agen , some empla es a e essen ially he same and could be me ged
in o one.
Figu e 4.1: Dis ibu ion o human simila i y sco e in auxilia y co pus
4.3. EVALUATION TASKS
In he p esen wo k, we know he e a leas 721 clus e s, which a e ep esen ed by he known
empla es. We ha e howe e no knowledge o how many empla es a e in he emaining emails. I he
numbe o empla es is di ec ly p opo ional o he numbe o emails, and since abou hal o ou
da ase has a empla e, we could be looking a doubling ou numbe o known empla es. On he o he
hand, his numbe could be small, and mos o he unlabeled emails belong o an al eady known
empla e. This issue is especially ele an o algo i hms like k-means whe e we need o inpu he
numbe o clus e s o ind. To u he inc ease ou amilia i y wi h he p esen ed measu es and
algo i hms we pe o m di e en expe imen s on he da a o gain insigh s o he p oblem a hand. As
such, we will c ea e asks wi h he goal o inding he mos app op ia e combina ion o me ics and
me hods o use in ou inal app oach.
4.3.1. Tasks and Expe imen s
Th oughou chap e s 2 and 3 we p esen ed di e en ways o ep esen ing and compa ing ex . We
chose ou o hem o compa e and analyze. The i s one is TF-IDF due o i s simplici y and popula i y
in o he wo ks. In sec ion 2.4, con ex ualized wo d embeddings we e p esen ed, and g ea impo ance
was gi en o he BERT model. In sec ion 3.2, a as e , mo e e icien model han BERT in some simila i y
asks was p esen ed. Acco ding o (Reime s & Gu e ych, 2019), his SBERT model can c ea e sen ence
0
20
40
60
80
100
120
0 1 2 3 4
Dis ibu ion o human simila i y sco e

29
embeddings which a e compa able wi h cosine simila i y. Mos wo ks co e ed in sec ion 3 use cosine
simila i y as he simila i y measu e. We decided o use cosine simila i y o compa ing bo h TF-IDF and
SBERT ex ep esen a ions. Finally, we chose wo o he ex compa ison echniques, Edi dis ance and
Jacca d dis ance o e alua e i s e ec i eness in he gi en p oblem. Fo he sake o cla i y, when
e e ing o TF-IDF and SBERT me ics, we a e e e ing o he usage o cosine simila i y join ly wi h he
TF-IDF and SBERT ep esen a ions.
4.3.1.1. G ouping Task
The Sil e co pus was c ea ed om he p o ided Email Co pus as an e o o ha e a ep esen a ion
close o eali y. While no a pe ec ep esen a ion, i is as close as possible o he g ound u h. To
be e unde s and i his co pus can be used as an accu a e ep esen a ion o eali y, we c ea ed he
ollowing algo i hm on he basis ha a gi en email has g ea e simila i y o emails belonging o he
same empla e han o emails belonging o di e en empla es. The algo i hm is as ollows:
- S ep 1: Choose a g oup o emails ep esen ed by a unique empla e which has no been
analyzed ye .
- S ep 2: Pick a andom elemen e in ha g oup ha has no been chosen.
- S ep 3: Pick ano he andom elemen a in ha g oup, and a andom elemen b ou side he
g oup.
- S ep 4: Use he simila i y measu e o compa e he elemen chosen in s ep 2 wi h he
elemen s chosen in s ep 3.
- S ep 5: Acco ding o he chosen measu e, i e and a and mo e simila (highe alue) han e
and b, add 1 o he coun o co ec g ouping.
- S ep 6: Repea s eps 3-5 un il all elemen s o he chosen g oup ha e been conside ed.
- S ep 7: Repea s eps 1-6 un il all g oups ha e been analyzed.
- S ep 8: Compu e he sco e o co ec g ouping by di iding he coun o co ec g ouping
by he numbe o possible g oupings.
Wi h his algo i hm, we can e alua e how well he ou chosen me ics and ep esen a ions accu a ely
compa e ex in he gi en p oblem. By ob aining a high esul in his expe imen , we can assume he
Sil e da a is co ec ly buil and he me ics used can be used when clus e ing. To u he analyze he
iabili y o his Sil e Da a, we compu ed he A e age Simila i y be ween all g oups as well as lowes
and highes simila i y in he gi en me ic. This may p o ide u he unde s anding o which me ic o
use.
Me ic
G ouping Task
A e age Sim
TFIDF
0.9952
0.228
SBERT
0.995
0.651
Edi Dis ance
0.98
0.264
Jacca d Dis ance
1
0.652
Table 4.3: G ouping Task E alua ion
30
Table 4.3 ep esen s he abo e-men ioned expe imen s. The g ouping ask p esen s an as ic esul s
o all di e en me ics, wi h he Jacca d Dis ance s a ing ha he g ouping is pe ec . Al hough he
o he esul s do no ha e an objec i ely be e me ic, he TF-IDF and Edi Dis ance me ics may be
used mo e in ui i ely by humans as hey ha e bigge in e al o simila i y. We conclude ha he Sil e
Da a has g ea iabili y and will be used in expe imen s o es he e ec i eness o o he componen s
o he Clus e ing p ocess.
4.3.1.2. Rela ionship be ween Me ics
We ha e asce ained ha he Sil e da a is a good ep esen a ion o he g ound u h, and he me ics
can be used o compa e emails. In he nex expe imen we wan o es i he simila i y seen by he
me ics is close o ha o a human agen . Meaning ha he ela ionship and compa ison o ex wi h
he gi en me ics should ha e simila esul s o hose o a human agen .
The co pus c ea ed in sec ion 4.2.2 should help analyze such ela ionships as i p o ides an in ui i e
app oach o compa ing he me ics wi h ou p e iously labeled simila i y sco e. We measu ed he
Spea man co ela ion be ween he alues gi en by he human agen and each o he measu es in he
gi en pai ing.
Co ela ion
TFIDF
SBERT
Edi Dis ance
Jacca d
TFIDF
SBERT
0.49
Edi Dis ance
0.156
0.202
Jacca d
0.159
0.216
0.441
Human Sco e
0.822
0.812
0.801
0.783
Table 4.4: Co ela ion be ween me ics
In Table 4.4 we p esen such esul s. To no e while he me ics ha e low co ela ion be ween
hemsel es, hey all ha e high co ela ion wi h he human sco e me ic.
When conside ing he wo p e ious asks ega ding me ics, we concluded hey do no ha e a
signi ican di e ence be ween one ano he . F om his poin on we decided o use only TF-IDF and
SBERT me ics o u u e expe imen s. The eason being Jacca d dis ance has he lowes co ela ion o
he human simila i y sco e while Edi dis ance akes much longe han he o he me ics o compu e.
The emaining me hods can be used o e alua e i con ex ual wo d embeddings like SBERT a e be e
in cases like he p esen one when compa ed o mo e simple ex ep esen a ion me hods such as TF-
IDF.
31
4.3.2. Tex P e-p ocessing and Algo i hm E alua ion
In he p e ious sec ions, di e en app oaches we e conduc ed o ind di e ences in he chosen
me ics. Due o ela ed wo k p esen ed in chap e 3 and o p e ious expe imen s, we ha e es ablished
ha he e a e only mino di e ences in he p esen ed simila i y measu es. In his subsec ion, we aim
o selec he op imal me hod o each o he o he componen s.
We ha e es ed he iabili y o he Sil e Da ase as he eal ep esen a ion o he empla e g ouping
and de e mined i was a good ep esen a ion. This has wo consequences: i s ly, i enables he use o
Ex e nal Quali y Measu es (sec ion 2.3.1.) o clus e ing esul s since we ha e a ep esen a ion o he
o iginal da a s uc u e (o g ound u h); secondly, a a e case o clus e ing p oblem whe e he exac
numbe o clus e s is known is p esen ed. In consequence, we can es di e en combina ions o ex
ep esen a ion, simila i y measu es and documen p e-p ocessing echniques in an objec i ely easy o
e alua e en i onmen . While his will no di ec ly achie e he objec i e o inding new empla es in
he da a, we a e unde he assump ion ha i we ind a clus e ing me hodology capable o ha ing high
e alua ion in his sub da ase , he same me hodology will ansla e compa able esul s when clus e ing
wi h all he da a.
Some Clus e ing Algo i hms may use he numbe o clus e s as an op ional pa ame e ; howe e , he
k-means amily o clus e ing algo i hms need only he numbe o clus e s o be execu ed. Wi h one o
i s main issues sol ed, we can make use o his unique case o igu e ou he op imal ype o k-means
algo i hm o be used in he inal app oach whe e he only issue would be inding he op imal numbe
o clus e s.
Since we a e ha ing his app oach o dec ease he numbe o pa ame e s o op imize, we a e ocusing
on k-means ela ed algo i hms and some hie a chical algo i hms. Thus, clus e ing me hods ha use
o he pa ame e s will no be used in his e alua ion as he numbe o clus e s in he esul o hese
me hods may g ea ly di e om he numbe o ac ual clus e s p esen in he da ase and hus would
beha e poo ly wi h g ound u h ela ed e alua ions.
4.3.2.1. Tex P ep ocessing
B ie ly men ioned in sec ion 3.1., ex p ep ocessing is a common module used in mos NLP asks. The
ac o spli ing he ex in o wo ds is called okeniza ion and is applied o all expe imen s. Se e al
p ep ocessing echniques can be applied o he ex documen s. These ans o ma ions may educe
he high dimensionali y o he ea u e space, as hey educe he numbe o wo ds in he ocabula y.
As hey emo e noisy ea u es, hey a e expec ed o imp o e he clus e ing esul , e iciency, and
pe o mance.
Wo ds p esen in nea ly all ex documen s do no add ele ancy o he documen . Examples o hese
wo ds a e p eposi ions, p onouns, and a icles such as you, you , as and is. This g oup o wo ds is
commonly e e ed as s opwo ds. They do no con ibu e o he seman ic alue o ex as hei
appea ance in one documen does no help di e en ia e om he o he s. Commonly s o ed in a lis ,
he emo al o s opwo ds is conside ed a p ep ocessing s ep.
Wo ds ha sha e a common lemma (canonical o m o a se o wo ds) can be ep esen ed wi h he
same e m. This p ocess o aking in o conside a ion he mo phological s uc u e o wo ds and
32
ans o m hem back o hei lemma is called lemma iza ion. This is achie ed by ha ing a de ailed
dic iona y whe e he algo i hm can connec a wo d o i s lemma.
S emming algo i hms on he o he hand emo e pa s o a gi en wo d by conside ing p e ixes and
su ixes usually ound in in lec ed wo ds. This new e m is no necessa ily a eal wo d.
P e-p ocessing me hod
O iginal Wo d
S emming
Lemma iza ion
is
is
Be
Change
Chang
Change
changing
chang
Change
densely
dens
Densely
popula ed
popul
popula ed
Table 4.5: Di e ences be ween S emming and Lemma iza ion
Lemma iza ion has he capabili y o p oducing eal wo ds which may be an ad an age bu akes longe
han s emming o compu e.
Taking ad an age o he si ua ion ega ding clus e ing e alua ion, we will expe imen di e en
combina ions o hese echniques and pe o m a compa ison o i s impac on he esul s.
4.3.2.2. Clus e ing Ex e nal E alua ion
A e p esen ing di e en me hodologies, we will be now e alua ing i s e ec wi h he Ex e nal Quali y
Measu es men ioned in 2.3.1. The expe imen s will go as such:
- Apply di e en combina ions o p ep ocessing echniques o he co pus.
- Rep esen he documen s wi h TFIDF and SBERT, he wo emaining ep esen a ions o
ex .
- Run he k-means, k-medoid and agglome a i e clus e ing algo i hms wi h numbe o
clus e s se o he same as he numbe o empla es in he Sil e Da a (721).
- Use ARI and he V-measu e (sec ion 2.3.1.) o e alua e he clus e ing esul s.
In his expe imen , we also had an i e a ion whe e apa om okeniza ion, no p ep ocess was applied.
Due o he p ep ocessing, he dimensionali y o he ep esen a ions su e ed mino modi ica ions.
While he SBERT ep esen a ion has he same dimensionali y, 512, since i is a ixed ec o ; he
dimensionali y o he TF-IDF ep esen a ions we e educed by a small ma gin.
39
6. CONCLUSION
The goal o his p ojec was o de elop a me hodology capable o ex ac ing unknown empla es om
a g oup o cus ome suppo esponse emails. To do so, we p opose a solu ion based on clus e ing
echniques. As he ocus o his wo k, we ex ensi ely esea ched and analyzed hese echniques. Th ee
main componen s could be ga he ed: he clus e ing algo i hm, he documen ep esen a ion, and he
simila i y measu e.
In he da a p o ided o us, some emails al eady had an assigned empla e. Due o his uniqueness o
he da a, a smalle da ase wi h known g ound u h was ex ac ed. This enabled he use o ex e nal
clus e alida ion measu es. In addi ion, an anno a ed da ase was c ea ed. This con ibu ion u he
enabled he e alua ion o clus e ing componen s. Pa icula ly, high co ela ion was obse a ion
be ween mos simila i y measu es and he e alua ion o he human agen .
To ep esen he documen s in o eadable da a by he algo i hms, some echniques we e conside ed.
TF-IDF ep esen a ions had be e pe o mance when compa ed wi h con ex ualized wo d
embeddings, such as SBERT. Likewise, we compa ed di e en simila i y measu es, wi h cosine
simila i y achie ing be e esul s.
Se e al clus e ing algo i hms we e e alua ed du ing his esea ch. In ini ial expe imen s, be e esul s
we e achie ed by hie a chical clus e ing algo i hms and medoid based algo i hms. These ypes o
algo i hms a e be e sui ed o documen clus e ing. While e alua ing di e en clus e ing algo i hms,
we also es ed he impac o di e en ex p ep ocessing echniques such as s opwo ds emo al and
s emming. O e all, he impac was non-signi ican .
These insigh s we e hen applied o he ull da ase . While we ocused on he pa i ion wi h be e
silhoue e sco e, u he analysis led o belie e ha almos e e y clus e ing pa i ion could be used o
gi e insigh s o he p oblem a hand. While we did ind some unknown empla es, as hey had e y
high sco es, we ha e no easible way o e alua ing e e y single clus e .
As mos empla e candida es we e comp ised o a ious ypes o emails, we conclude ha u he
clus e ing could be done, ei he wi h by ini ializing k-means wi h a highe numbe o clus e s o
applying hie a chical clus e ing wi h a speci ic cu o .

40
7. LIMITATIONS AND FUTURE WORK
One o he limi a ions o his p ojec is inhe en o i s app oach. As men ioned by (Hassani & Seidl,
2017), clus e ing e alua ion is o en as much o mo e di icul han he clus e ing i sel . While in his
case we had he ad an age o ha ing some emails wi h assigned empla es and used his pa icula i y
o e i y he i clus e ing algo i hm was able o de ec some o he known empla es, an op imal
solu ion o e alua e he clus e ing esul s o he ull da a is s ill di icul wi hou he need o human
in e en ion.
Ano he limi a ion is ha we we e unable o apply some o he algo i hms o he ull da ase . When
applied o he sil e da ase , hey achie ed sligh ly be e esul s han algo i hms applied o he ull
da ase . As such i would be use ul o explo e me hods o applying such algo i hms o a highe quan i y
o da ase , pe haps in an implemen a ion by ba ches.
Fu u e app oaches could include he explo a ion o o he known clus e ing algo i hms such as uzzy
clus e ing, o pe haps he c ea ion o cus om algo i hms based on he insigh s gi en by his wo k.
I would also be in e es ing o measu e he impac o o he da a p e-p ocessing echniques. While
SBERT embeddings ha e ixed dimensionali y, ep esen a ions based on bag-o -wo ds ha e
dimensionali y ha depend on he numbe o wo ds in he gi en ocabula y. Using only speci ic wo ds,
such as he mos used o he leas used, could be in e es ing. Fu he mo e, p ocesses o da a
dimensionali y educ ion such as P incipal Componen Analysis and La en Di ichle Alloca ion could
be applied.
Mos esponse emails can be di ided in h ee main pa s: he g ee ing, which is he beginning o he
message, whe e we usually ind he name o whom he gi en email is add essed o and a small opening
in oduc ion (such as Hello o Thank you o eaching ou ); he body, whe e he main con en o he
mail is; and he signo , which con ains a closing s a emen . Con en wise, he g ee ings and he signo
o e no alue o he email. While ep esen a ions like TF-IDF somewha coun e his by assigning
smalle weigh s o e ms ha appea in many di e en documen s (which would be he case o wo ds
belonging o hese wo pa s o he email), hei emo al om he documen could u he enhance
he documen ep esen a ion phase o he wo k.
On an ending no e, while we had issues ully e alua ing new empla es, we con i med ha some
known empla es we e also co ec ly iden i ied. As such i would also be in e es ing o apply his
me hodology o di e en da ase s.
41
8. BIBLIOGRAPHY
A i , N. M., Baka , M. A., & Rahman, M. I. (2018). Compa a i e s udy o documen clus e ing
algo i hms. In e na ional Jou nal o Enginee ing and Technology (UAE), 7(4), 246-251.
A hu , D., & Vassil i skii, S. (2007). k-means++: he ad an ages o ca e ul seeding. Socie y o
Indus ial and Applied Ma hema ics, 1027-1035.
Bahdanau, D., Cho, K., & Bengio, Y. (2015). Neu al machine ansla ion by join ly lea ning o align and
ansla e. Re ie ed om h ps://a xi .o g/abs/1409.0473
Balaban a ay, R. C., Sa ma, C., & Jha, M. (2015). Documen clus e ing using k-means and k-medoids.
Re ie ed om h ps://a xi .o g/abs/1502.07938
Cho, K., Van Me iënboe , B., Bahdanau, D., & Bengio, Y. (2014). On he p ope ies o neu al machine
ansla ion: Encode -decode app oaches. Re ie ed om h ps://a xi .o g/abs/1409.1259
Cho owski, J., Bahdanau, D., Se dyuk, D., Cho, K., & Bengio, Y. (2015). A en ion-based models o
speech ecogni ion. Re ie ed om h ps://a xi .o g/abs/1506.07503
Da ies, D. L., & Bouldin, D. W. (1979). A clus e sepa a ion measu e. IEEE ansac ions on pa e n
analysis and machine in elligence, (2), 224-227.
De lin, J., Chang, M. W., Lee, K., & Tou ano a, K. (2018). Be : P e- aining o deep bidi ec ional
ans o me s o language unde s anding. Re ie ed om h ps://a xi .o g/abs/1810.04805
Dhillon, I. S., & Modha, D. S. (2001). Decomposi ions o La ge Spa se Tex Da a Using Clus e ing.
Machine Lea ning, 143-175. doi:10.1023/A:1007612920971
Hassani, M., & Seidl, T. (2017). Using in e nal e alua ion measu es o alida e he quali y o di e se
s eam clus e ing algo i hms. Vie nam Jou nal o Compu e Science, 4(3), 171-183.
Huang, A. (2008). Simila i y measu es o ex documen clus e ing. P oceedings o he six h new
zealand compu e science esea ch s uden con e ence (NZCSRSC2008), 4, pp. 9-56.
Jain, A. K., Mu y, M. N., & Flynn, P. J. (1999). Da a clus e ing: a e iew. ACM compu ing su eys
(CSUR), 31(3), 264-323. doi:10.1145/331499.331504
Kau man, L., & Rousseew, P. J. (1990). Finding G oups in Da a: An In oduc ion o Clus e Analysis.
John Wiley & Sons. doi:10.1002/9780470316801
Liu, Y., O , M., Goyal, N., Du, J., Joshi, M., Chen, D., . . . S oyano , V. (2019). RoBERTa: A Robus ly
Op imized BERT P e aining App oach. Re ie ed om h ps://a xi .o g/abs/1907.11692
Luong, T., Pham, H., & Manning, C. D. (2015). E ec i e app oaches o a en ion-based neu al
machine ansla ion. P oceedings o he 2015 Con e ence on Empi ical Me hods in Na u al
Language P ocessing, (pp. 1412-1421). doi:10.18653/ 1/D15-1166
42
Ma in, L., Mulle , B., Suá ez, P. J., Dupon , Y., Roma y, L., de la Cle ge ie, É. V., . . . Sago , B. (2019).
CamemBERT: a Tas y F ench Language Model. Re ie ed om
h ps://a xi .o g/abs/1911.03894
Mikolo , T., Chen, K., Co ado, G., & Dean, J. (2013). E icien es ima ion o wo d ep esen a ions in
ec o space. Re ie ed om h ps://a xi .o g/abs/1301.3781
Mi chell, T. M. (1997). Machine Lea ning.
Mo a, P., Ma ins, B., & Coheu , L. (2013). Designing an answe empla e e ie al sys em. Technical
Repo 35, INESC-ID.
Pe e s, M. E., Neumann, M., Iyye , M., Ga dne , M., Cla k, C., Lee, K., & Ze lemoye , L. (2018). Deep
con ex ualized wo d ep esen a ions. Re ie ed om h ps://a xi .o g/abs/1802.05365
Rand, W. M. (1971). Objec i e c i e ia o he e alua ion o clus e ing me hods. Jou nal o he
Ame ican S a is ical associa ion, 66(336), 846-850.
Reime s, N., & Gu e ych, I. (2019). Sen ence-be : Sen ence embeddings using siamese be -
ne wo ks. Re ie ed om h ps://a xi .o g/abs/1908.10084
Rosenbe g, A., & Hi schbe g, J. (2007). V-measu e: A condi ional en opy-based ex e nal clus e
e alua ion measu e. P oceedings o he 2007 join con e ence on empi ical me hods in
na u al language p ocessing and compu a ional na u al language lea ning (EMNLP-CoNLL),
(pp. 410-420).
Rosenbla , F. (1958). The pe cep on: a p obalis ic model o in o ma ion s o age and o ganiza ion in
he b ain. Psychological Re iew, 65(6), 386-408.
San os, J. M., & Emb ech s, M. (2009). On he use o he adjus ed and index as a me ic o
e alua ing supe ised classi ica ion. In e na ional con e ence on a i icial neu al ne wo ks,
175-184. doi:10.1007/978-3-642-04277-5_18
Sasaki, M., & Shinnou, H. (2005). Spam de ec ion using ex clus e ing. 2005 In e na ional Con e ence
on Cybe wo lds (CW'05), (pp. 4-pp).
Shale -Shwa z, S., & Ben-Da id, S. (2014). Unde s anding machine lea ning: F om heo y o
algo i hms. Camb idge: Camb idge Uni e si y P ess. doi:10.1017/CBO9781107298019
S einbach, M., Ka ypis, G., & Kum a , V. (2000). A compa ison o documen clus e ing echniques.
Su ske e , I., Vinyals, O., & Le, Q. V. (2014). Sequence o sequence lea ning wi h neu al ne wo ks.
Ad ances in neu al in o ma ion p ocessing sys ems, 3104-3112.
Vaswani, A., Shazee , N., Pa ma , N., Uszko ei , J., Jones, L., Gomez, A. N., . . . Polosukhin, I. (2017).
A en ion Is All You Need. Ad ances in neu al in o ma ion p ocessing sys ems, (pp. 5998-
6008).
43
Wu, Y., Schus e , M., Chen, Z., L, Q. V., M. N., Mache ey, W., . . . Dean, J. (2016). Google’s neu al
machine ansla ion sys em: B idging he gap be ween. Re ie ed om
h ps://a xi .o g/abs/1609.08144 2
Zhu, Y., Ki os, R., Salakhu dino , R., U asun, R., To alba, A., & Filde , S. (2015). Aligning books and
mo ies: Towa ds s o y-like isual explana ions by wa ching mo ies and eading books.
P oceedings o he IEEE in e na ional con e ence on compu e ision, (pp. 19-27).
44