Identifying Similarities in Text Analysis: Hierarchical Clustering (Linkage) versus Network Clustering (Community Detection)

The aim of this paper is to introduce to stylometry the methods allowing for evaluation of classification results obtained with (i) hierarchical clustering methods, with the distinction of performance of individual linkage methods, and (ii) network clustering, with the comparison of community detection techniques. We compare three recognized evaluation measures: AMI, ARI and NMI using 6 model datasets of known clustering, of which three constitute binary problems and three – corpora with a large number (25) of expected internal groups, which were designed for authorship attribution (or similar multiclass problems). Our results show (i) superiority of Ward linkage method as compared to 5 other, (ii) greater performance and stability of Cosine Delta for both hierarchical and network clustering, (iii) Louvain as the most reliable method of community detection, and (iv) usefulness of AMI method for hierarchical clustering, which we propose for general use making our scripts available.

Introduction
For visualizing the stylometric structure of a text corpus, many studies and popular tools like ‘stylo’ (Eder et al., 2016) rely on explanatory methods and intuitively-interpretable visualizations, usually belonging to either tree charts as produced by hierarchical clustering, or network representations. The intuition behind it is that the graphs will group texts of high stylistic similarity close together, thereby allowing the spectator to visually identify multiple levels of groupings instead of simply singling out one nearest neighbour for each individual text. There were even some methodological studies on stylometric distance measures based on evaluating the clusterings they produce (Jannidis et al., 2015).
Despite the popularity dendrograms and networks have in stylometry, there is to this date no systematic investigation on how these methods behave when applied to problems in computational stylistics – research usually focuses on method selection from general pool of classification approaches. In clustering, both fine-grained clusters (e.g. groupings by author) and larger groups containing several texts (e.g. higher level genre-wise groupings of multiple authors) are generated by the method itself – a very reproducible process  – but particular clustering method used is a matter of choice. Most cases rely on the ‘Ward’ linkage method (Ward, 1963) which is the default in ‘stylo’, but its advantages and disadvantages for the research field have not been investigated systematically. E.g., Hoover’s choice of Ward linkage is based on a concise comparison of Ward, complete, and average linkages (Hoover, 2003), but the methodological design of the comparison has not been outlined in the paper.

The case of network analysis is even more problematic, as low and/or high level groups are often/usually only identified visually. The best approach to operationalize
how people perceive group formation in networks is to use community detection.

This study aims to constitute an initial step to the systematic investigation of these issues, which we do by analyzing the quality of grouping achieved by different clustering and community detection algorithms in comparison to known properties of different test corpora.

Corpora
We conducted our study on 6 text corpora, each assembled with an inherent internal structure with groups expected to be stylistically distinct. We used both corpora with a large number (25) of internal groups, and corpora that can be separated into two major stylistic groups.

As examples with a large number of low-level groups, we used three reference corpora for authorship attribution, each composed of 75 novels by 25 authors. These corpora, from English, French and German literature were previously used in various studies on text distance measures (e.g. Jannidis et al. 2015) and are freely available (

).

As examples for problems featuring two major stylistic groups, we took (1) a corpus of 17th century French drama published by Christof Schöch (

), where we removed all texts not clearly labeled comedies or tragedies; (2) a corpus containing Latin verse and prose from the so-called Golden Age; (3) a corpus of Latin historiography containing texts from the very same Golden Age (late first century BCE) on the one hand, and the “Silver Age” on the other. The Latin materials were assembled from the Latin Library (

).

Methods: Clustering quality measures
There are many similarity indices for clustering evaluation (see Albatineh et al. 2006; Wagner and Wagner 2007; Vinh et al. 2010 for their comparison). In this pilot study we focus on three best understood: ARI (Adjusted Rand Index; Hubert and Arabie 1985), AMI (Adjusted Mutual Information) and NMI (Normalized Mutual Information). The first two are adjusted for baseline value in case of random clustering (Vinh et al. 2009, 2010) but not fully for selection bias (i.e. usually bias to select a clustering having higher number of clusters than ground truth; Romano et al. 2014, 2016), while the third one is not adjusted. Standardized Mutual Information (SMI;  Romano et al. 2014) might offer a further improvement in future studies.

Methods: Community detection methods in networks
Community detection methods allow for automatized search for natural division of network into smaller clusters, that is communities. They can be applied to bare distance tables (resulting in complete weighted graphs), or on pruned or otherwise sparse networks (such as consensus networks in Eder 2017). We use “A not so small collection of clustering methods” facilitating consensus clustering (Lancichinetti and Fortunato 2012), which includes such algorithms as  OSLOM (Lancichinetti et al. 2011), Infomap (Rosvall and Bergstrom 2007), label propagation method (Raghavan et al. 2007), and modularity optimization by simulated annealing (Guimera et al. 2004) and by Louvain method (Blondel et al. 2008).

Methods: Experiments
We first conducted a large series of stylometric tests that were later used for evaluation. For each dataset we conducted myriads of tests for a total of 160 basic experimental scenarios, being a combination of the following changing factors of: (i) number of MFWs (100 to 1000, iterated by 100), (ii) distance measure (Classic and Cosine Deltas) and (iii) linkage method (single, complete, average, McQuitty's, Ward in two implementations: “ward.D”, “ward.D2”, "median"  – k-median, and "centroid” – k-means). We then evaluated quality of the clusterings in the results, considering the number of clusters ranging from 2 to the number of texts in the corpus using a script implementing ARI, AMI and NMI indices. E.g.: for any of the 75-book corpora, we would obtain 160 scenarios and test 74 clustering options for each of them, obtaining a total of 11,840 clustering scenarios up for evaluation.

We performed similar experiments utilising networks: in one, we used all the mentioned community detection methods together with consensus networks; in the second experiment, we used distance tables instead. Let us note that modularity optimization is well defined in the case of directed and weighted networks (Arenas et al. 2007) and indeed it is the only one that produces non-trivial clustering of distance tables (since distances are inversely proportional to network weights we chose a transformation – from among the infinitely many
– from one to the other
w=exp(-d)
, yielding weights in the range (0,1). Owing to that we could use consensus clustering over distance tables that were generated by a range of the selected most frequent words (as one does with consensus bootstrap trees).

Results: hierarchical clustering
In all of our tests, Ward’s linkage outperformed other algorithms, both for Classic and Cosine Deltas. Notably, this particular linkage method was designed for large-scale tests of more than 100 samples: the speed, not the optimal clustering was a priority (Ward 1963: 236). Cosine Delta proved superior of the two distances – it systematically scored higher and gave maximal agreement with ground truth at the same number of clusters, even for a small MFW number.

Fig. 1 Clustering quality for the French corpus, Cosine (Wurzburg) Delta distance measure and Ward linkage using different MFW ranges.
An example of clustering assessment, here for the French corpus, is shown in Fig. 1. Vertical dashed line marks the expected number of clusters (here, 25 authorial classes). Each curve represents values of one quality measure for a given number of MFWs, and dots mark their maxima. AMI maximum falls around the expected and intuitive number of authorial clusters. NMI is heavily biased towards a larger number of smaller clusters, in line with its characteristics as described in the method section, proving that it should not be recommended as a quality measure for this type of problems. The conclusions for all considered corpora are qualitatively similar.

Fig. 2 Clustering quality for different linkage methods – Ward performing best, and centroid  worst – at 1000 MFWs. Layout as in Fig. 1.

Results: networks
The results of Louvain method on distance tables indicate that this scenario should be avoided: neither Classic nor Cosine Delta could reach AMI=0.2 on any corpus, which is worse than most of the hierarchical clustering methods (cf Fig. 2). However, a more sophisticated approach involving undirected consensus networks (Eder 2017) offers much better results, see Fig. 3–4: the community detection methods rarely score below AMI=0.4 (on the exemplary French authorial corpus), and the best one scores above AMI=0.6 which contends for the first place with Ward linkage clustering.
While hierarchical clustering typically provides a number of clusters higher than expected, community detection tends to produce a smaller number of larger clusters. This might be caused by the less detailed (and less noisy) information contained in the consensus networks. One should also take into account that hierarchical clustering did not take advantage of the consensus scheme and hence is computationally less demanding.

Fig. 3 Layout analogous to Fig. 1–2. Results of community detection on consensus networks based on Classic Delta. Each community detection method provided one clustering for the consensus network. All methods predict smaller number of clusters than expected. Louvain method typically scores highest.

Fig. 4 Layout as in Fig. 3. Results of community detection on consensus networks based on Cosine Delta.

Conclusion
Our study provided empirical proof for the choice of Ward linkage method in clustering applications on literary text, and further strengthened the argument for the use of Cosine Delta as a method more resistant to changes in the number of used MFWs and factors such as language or size of the corpus. The best community detection methods, which again make use of Cosine Delta, can contend with hierarchical clustering, however, they clearly require previous data filtering, e.g., by means of constructing consensus networks. Interestingly, they offer a complementary more coarse-grained view. Importantly, we also propose introduction of clustering evaluation step into the analysis, in particular AMI method which worked best for all model cases with expected divisions. We will make the evaluation script available in our github repository, encouraging other scholars to use this or similar techniques.
Acknowledgements

JB was partially funded for the research by Poland's National Science Centre (grant number 2017/26/HS2/01019), SP contributed to this research as part of a Short Term Scientific Mission financed by the EU COST Action “Distant Reading” (CA16204), ME was partially funded by the National Science Centre (grant number 2014/12/W/ST5/00592).

Bibliography

Albatineh, A. N., Niewiadomska-Bugaj, M. and Mihalko, D.

(2006). On similarity indices and correction for chance agreement.
Journal of Classification
,
23
(2): 301–13. doi:

10.1007/s00357-006-0017-z

.

Arenas, A., Duch, J., Fernández, A. and Gómez, S.

(2007). Size reduction of complex networks preserving modularity.
New Journal of Physics
,
9
(6): 176.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R. and Lefebvre, E.

(2008). Fast unfolding of communities in large networks.
Journal of Statistical Mechanics: Theory and Experiment
,
2008
(10): P10008.

Eder, M.

(2017). Visualization in stylometry: cluster analysis using networks.
Digital Scholarship in the Humanities
,
32
(1): 50–64.

Eder, M., Rybicki, J. and Kestemont, M.

(2016). Stylometry with R: a package for computational text analysis.
R Journal
,
8
(1): 107–21.

Guimerà, R., Sales-Pardo, M. and Amaral, L. A. N.

(2004). Modularity from fluctuations in random graphs and complex networks.
Physical Review E
,
70
(2): 025101 doi:

10.1103/PhysRevE.70.025101

.

Hoover, D. L.

(2003). Frequent collocations and authorial style.
Literary and Linguistic Computing
,
18
(3): 261–86.

Hubert, L. and Arabie, P.

(1985). Comparing partitions.
Journal of Classification
,
2
(1): 193–218 doi:

10.1007/BF01908075

.

Jannidis, F., Pielström, S., Schöch, C. and Vitt, T.

(2015). Improving Burrows’ Delta – An empirical evaluation of text distance measures.
Digital Humanities 2015: Conference Abstracts
. Sydney, Australia: University of Western Sydney.

(accessed 27 November 2018).

Lancichinetti, A. and Fortunato, S.

(2012). Consensus clustering in complex networks.
Scientific Reports
,
2
: 336.

Lancichinetti, A., Radicchi, F., Ramasco, J. J. and Fortunato, S.

(2011). Finding statistically significant communities in networks.
PLOS ONE
,
6
(4): e18961 doi:

10.1371/journal.pone.0018961

.

Raghavan, U. N., Albert, R. and Kumara, S.

(2007). Near linear time algorithm to detect community structures in large-scale networks.
Physical Review E
,
76
(3): 036106 doi:

10.1103/PhysRevE.76.036106

.

Romano, S., Bailey, J., Nguyen, V. and Verspoor, K.

(2014). Standardized mutual information for clustering comparisons: one step further in adjustment for chance. In Xing, E. P. and Jebara, T. (eds),
Proceedings of the 31st International Conference on Machine Learning
. PMLR: 1143–51.

.

Romano, S., Vinh, N. X., Bailey, J. and Verspoor, K.

(2016). Adjusting for chance clustering comparison measures.
Journal of Machine Learning Research
,
17
(134): 1–32.

Rosvall, M. and Bergstrom, C. T.

(2007). An information-theoretic framework for resolving community structure in complex networks.
Proceedings of the National Academy of Sciences
,
104
(18): 7327–31. doi:

10.1073/pnas.0611034104

.

Shrestha, P., Jacquin, C., Daille, B.

(2012). Clustering Short Text and Its Evaluation. In: Gelbukh, A. (Ed.). Computational Linguistics and Intelligent Text Processing, Lecture Notes in Computer Science. Springer Berlin Heidelberg: 169–180.

Vinh, N. X., Epps, J. and Bailey, J.

(2009). Information theoretic measures for clusterings comparison: is a correction for chance necessary?.
Proceedings of the 26th Annual International Conference on Machine Learning
. Montreal, Quebec, Canada: ACM: 1073–80.

.

Vinh, N. X., Epps, J. and Bailey, J.

(2010). Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance.
Journal of Machine Learning Research
,
11
: 2837–54.

Wagner, S. and Wagner, D.

(2007).
Comparing Clusterings: An Overview
.

.

Ward, J. H.

(1963). Hierarchical grouping to optimize an objective function.
Journal of the American Statistical Association
,
58
(301): 236–44 doi:

10.1080/01621459.1963.10500845

.