Research story · Clustering
How do we find groups in data that we can trust?
Cluster analysis looks for groups of similar observations. This line of work began with existing methods applied to real problems, continued with a semi-supervised method, NeSSC, that lets an outcome variable guide the groups, and now asks whether a partition, and the method behind it, can be trusted.
At a glance
- Period
- 2017 to the present
- Threads
- Clustering in applied problems; semi-supervised clustering (NeSSC); validation of partitions
- Selected collaborators
- Claudio Conversano, Giulia Contu, Francesco Mola, Marco Ortu, Maurizio Romano, Andrea Carta. All authors are listed with each publication.
- Now
- Principal investigator of a project on clustering in non-Euclidean spaces (Fondazione di Sardegna)
The question
Clustering looks for groups of similar observations without knowing them in advance, and two questions follow. First, “similar” depends on what we care about: customers can be grouped by age, by spending or by the places they visit, and each choice gives different groups. Second, different algorithms, or the same algorithm with different settings, return different partitions of the same data. Which one should we trust?
Groups from the predictors only
Groups guided by the outcome
Clustering in applied problems 2017–2019
The first works used and compared existing methods on real problems. In a study of reverse logistics for food that stores can no longer sell, clustering algorithms divided the test area, the province of Cagliari, into collection sectors: the first of two modules of a management scheme, the second of which plans the collection routes (Transportation Research Procedia, 2017 (opens in a new tab)).
We compared two methods for binary data, monothetic analysis and model-based co-clustering, on a UNESCO data set of 58 binary variables on the use of the Internet to promote World Heritage sites (Springer, 2018 (opens in a new tab)). A chapter dealt with four community detection algorithms for direct and indirect graphs (2019): detecting communities in a network is also the last step of the method described next.
Groups guided by an outcome 2018–2022
Often a variable of interest is available: a satisfaction score, a price, a clinical outcome. It is not the cluster structure we are looking for, but it can be a good proxy of it, a noisy surrogate. Network-based semi-supervised clustering (NeSSC), which we developed, uses it in three phases:
- a classification or regression tree is trained on many resampled versions of the data, with the outcome as response;
- together, the fitted models give a matrix of pairwise affinities: how similar each pair of observations is with respect to the outcome;
- the matrix becomes a network, in which observations are nodes and affinities are links, and an existing community detection algorithm (Louvain, label propagation or Walktrap) finds groups of densely connected nodes: the clusters.
1 · Data and outcome
2 · Pairwise affinity
3 · Network
4 · Clusters
The article that introduced NeSSC (Applied Stochastic Models in Business and Industry, 2021 (opens in a new tab)) specifies the method with trees and the three community detection algorithms above, discusses when to stop and how to choose the final partition, and shows on real and simulated data that its results are easier to interpret than those of three alternative semi-supervised clustering methods. The network is more than a computational device: it shows how observations are related to each other. Before the article, two conference contributions had dealt with semi-supervised clustering through recursive partitioning and complex networks (ECDA 2018) and with network-based semi-supervised clustering (y-BIS 2019).
Later conference papers applied NeSSC to time series (CLADAG 2021 (opens in a new tab)) and described its algorithm in an invited session (ISBIS 2022).
Choosing the partition for a numeric outcome 2024
When the outcome is numeric, which of the candidate partitions should NeSSC return? We proposed to choose it by how little the distributions of the outcome overlap across clusters, with a penalty for the number of clusters (Computational Statistics, 2024 (opens in a new tab)). On artificial data and 20 real data sets, compared with three popular semi-supervised clustering methods for numeric outcomes, NeSSC with this criterion worked particularly well when there were few, well-localized clusters.
Grouping texts by their sentiment 2022–2023
NeSSC is also the last step of semi-supervised sentiment clustering, which we developed (Statistical Methods and Applications, 2023 (opens in a new tab)). Sentiment analysis first labels texts as positive or negative; a threshold-based naive Bayes classifier then estimates the overall sentiment of each text and gives a sentiment value to its topics; finally, NeSSC groups the texts. On reviews written by customers of Booking.com, the clusters were distinct and homogeneous in their overall sentiment, and the network representation helped to interpret them. A conference paper applied semi-supervised clustering to electronic word of mouth (SIS 2022).
Another semi-supervised method: maritime accidents 2021
Not all the semi-supervised work uses NeSSC. In a study of 1,079 sea accidents recorded by the International Maritime Organization, existing semi-supervised recursively partitioned mixture models were used to identify and categorize causal themes, with special attention to the human element (Transportation Research Procedia, 2021 (opens in a new tab)).
Can a partition be trusted? 2023–2025
More recent contributions, presented at conferences, address the second question of this page:
- a method to validate clustering partitions (CLADAG 2023);
- an approach to choose between clustering methods, presented in an invited session of the World Statistics Congress, which combines internal and relative validation criteria with machine learning algorithms to rank candidate partitions, also for high-dimensional data (ISI 2025);
- local optimization-based clustering (CLADAG 2025).
Current work
The research continues in the project Clustering in non-Euclidean spaces: theoretical foundations and alternative approaches, funded by the Fondazione di Sardegna (call for basic research projects 2025), of which I am principal investigator.
Publications in this line
2026
Selecting Between Clustering Methods: An Innovative Approach
Book of Abstracts of ISI 2025, p. 17
Cite
@inproceedings{frigau2026selecting, author = {Frigau, L. and Contu, G. and Carta, A. and Ortu, M. and Mola, F.}, title = {Selecting Between Clustering Methods: An Innovative Approach}, booktitle = {Book of Abstracts of ISI 2025}, year = {2026}, pages = {17}, isbn = {978-9-073592-43-8}, }
2025
Local Optimization-Based Clustering
CLADAG VOC 2025 - Book of Abstract, p. 258
Cite
@inproceedings{frigau2025local, author = {Frigau, L.}, title = {Local Optimization-Based Clustering}, booktitle = {CLADAG VOC 2025 - Book of Abstract}, year = {2025}, pages = {258}, isbn = {978-8-899594-24-4}, }
2024
Overlapping coefficient in Network-based Semi-Supervised Clustering (opens in a new tab)
Computational Statistics, 39(7): 3831–3854
For numeric outcomes, the final partition is chosen by how little the distributions of the outcome overlap across clusters; tested on 20 real data sets.
doi:10.1007/s00180-024-01457-6 (opens in a new tab)Cite
@article{conversano2024overlapping, author = {Conversano, C. and Frigau, L. and Contu, G.}, title = {Overlapping coefficient in Network-based Semi-Supervised Clustering}, journal = {Computational Statistics}, year = {2024}, volume = {39}, number = {7}, pages = {3831--3854}, doi = {10.1007/s00180-024-01457-6}, issn = {1613-9658}, }
2023
Semi-Supervised Sentiment Clustering on Natural Language Texts (opens in a new tab)
Statistical Methods and Applications, 32(4): 1239–1257
Groups texts, such as hotel reviews, into clusters that are homogeneous in their overall sentiment, combining sentiment analysis, a naive Bayes classifier and network-based clustering.
doi:10.1007/s10260-023-00691-4 (opens in a new tab)Cite
@article{frigau2023semi, author = {Frigau, L. and Romano, M. and Ortu, M. and Contu, G.}, title = {Semi-Supervised Sentiment Clustering on Natural Language Texts}, journal = {Statistical Methods and Applications}, year = {2023}, volume = {32}, number = {4}, pages = {1239--1257}, doi = {10.1007/s10260-023-00691-4}, issn = {1613-981X}, }A Method to Validate Clustering Partitions
CLADAG 2023 Book of Abstracts and Short Papers, pp. 473–476
Cite
@inproceedings{frigau2023method, author = {Frigau, L. and Contu, G. and Ortu, M. and Carta, A.}, title = {A Method to Validate Clustering Partitions}, booktitle = {CLADAG 2023 Book of Abstracts and Short Papers}, year = {2023}, pages = {473--476}, isbn = {978-88-919-3563-2}, }
2022
A semi-supervised clustering method to extract information from the electronic Word Of Mouth
SIS 2022 Book of the Short Papers, pp. 1558–1563
Cite
@inproceedings{contu2022semi, author = {Contu, G. and Frigau, L. and Romano, M. and Ortu, M.}, title = {A semi-supervised clustering method to extract information from the electronic Word Of Mouth}, booktitle = {SIS 2022 Book of the Short Papers}, year = {2022}, pages = {1558--1563}, isbn = {978-88-919-3231-0}, }The Algorithm of NeSSC for Semisupervised Clustering
ISBIS 2022 Book of Short Papers, p. 49
Cite
@inproceedings{frigau2022algorithm, author = {Frigau, L. and Contu, G. and Ortu, M.}, title = {The Algorithm of NeSSC for Semisupervised Clustering}, booktitle = {ISBIS 2022 Book of Short Papers}, year = {2022}, pages = {49}, isbn = {979-12-210-1389-4}, }
2021
Network-based Semi Supervised Clustering (opens in a new tab)
Applied Stochastic Models in Business and Industry, 37(2): 182–202
Introduces network-based semi-supervised clustering (NeSSC): trees guided by an outcome estimate pairwise affinities, and community detection on the resulting network finds the clusters.
doi:10.1002/asmb.2618 (opens in a new tab)Cite
@article{frigau2021network, author = {Frigau, L. and Contu, G. and Mola, F. and Conversano, C.}, title = {Network-based Semi Supervised Clustering}, journal = {Applied Stochastic Models in Business and Industry}, year = {2021}, volume = {37}, number = {2}, pages = {182--202}, doi = {10.1002/asmb.2618}, issn = {1526-4025}, }Transportation Research Procedia, 52: 252–259
doi:10.1016/j.trpro.2021.01.029 (opens in a new tab)Cite
@article{fadda2021investigating, author = {Fadda, P. and Fancello, G. and Frigau, L. and Mandas, M. and Medda, A. and Mola, F. and Pelligra, V. and Porta, M. and Serra, P.}, title = {Investigating the Role of the Human Element in Maritime Accidents using Semi-Supervised Hierarchical Methods}, journal = {Transportation Research Procedia}, year = {2021}, volume = {52}, pages = {252--259}, doi = {10.1016/j.trpro.2021.01.029}, issn = {2352-1465}, }Network-based Semi-supervised Clustering of Time Series Data (opens in a new tab)
CLADAG 2021 Book of Abstracts and Short Papers, pp. 62–63. Firenze University Press
doi:10.36253/978-88-5518-340-6 (opens in a new tab)Cite
@inproceedings{conversano2021network, author = {Conversano, C. and Contu, G. and Frigau, L. and Cappelli, C.}, title = {Network-based Semi-supervised Clustering of Time Series Data}, booktitle = {CLADAG 2021 Book of Abstracts and Short Papers}, editor = {Porzio, G. C. and Rampichini, C. and Bocci, C.}, publisher = {Firenze University Press}, address = {Florence}, year = {2021}, pages = {62--63}, doi = {10.36253/978-88-5518-340-6}, isbn = {978-88-5518-340-6}, }
2019
Four community detection algorithms for direct and indirect graphs
In Il Mondo che cambia, pp. 250–262. FrancoAngeli
Cite
@incollection{contu2019four, author = {Contu, G. and Frigau, L. and Romano, M.}, title = {Four community detection algorithms for direct and indirect graphs}, booktitle = {Il Mondo che cambia}, publisher = {FrancoAngeli}, address = {Milan}, year = {2019}, pages = {250--262}, isbn = {9788891798701}, }Network-based Semisupervised Clustering
Proceedings of y-BIS 2019, p. 44. Mimar Sinan Fine Arts University Publications
Cite
@inproceedings{contu2019network, author = {Contu, G. and Frigau, L. and Conversano, C.}, title = {Network-based Semisupervised Clustering}, booktitle = {Proceedings of y-BIS 2019}, publisher = {Mimar Sinan Fine Arts University Publications}, address = {Istanbul}, year = {2019}, pages = {44}, isbn = {978-605-5005-95-5}, }
2018
Comparison of Cluster Analysis Approaches for Binary Data (opens in a new tab)
In Classification, (Big) Data Analysis and Statistical Learning, pp. 155–162. Springer
doi:10.1007/978-3-319-55708-3_17 (opens in a new tab)Cite
@incollection{contu2018comparison, author = {Contu, G. and Frigau, L.}, title = {Comparison of Cluster Analysis Approaches for Binary Data}, booktitle = {Classification, (Big) Data Analysis and Statistical Learning}, series = {Studies in Classification, Data Analysis, and Knowledge Organization}, publisher = {Springer}, address = {Cham}, year = {2018}, pages = {155--162}, doi = {10.1007/978-3-319-55708-3_17}, isbn = {978-3-319-55708-3}, }Semisupervised Clustering through Recursive Partitioning and Complex Networks
Book of Abstracts of ECDA 2018
Cite
@inproceedings{conversano2018semisupervised, author = {Conversano, C. and Contu, G. and Frigau, L. and Mola, F.}, title = {Semisupervised Clustering through Recursive Partitioning and Complex Networks}, booktitle = {Book of Abstracts of ECDA 2018}, year = {2018}, }
2017
Transportation Research Procedia, 25: 695–715
doi:10.1016/j.trpro.2017.05.452 (opens in a new tab)Cite
@article{fancello2017new, author = {Fancello, G. and Mola, F. and Frigau, L. and Serra, P. and Mancini, S. and Fadda, P.}, title = {A new management scheme to support reverse logistics processes in the agrifood distribution sector}, journal = {Transportation Research Procedia}, year = {2017}, volume = {25}, pages = {695--715}, doi = {10.1016/j.trpro.2017.05.452}, issn = {2352-1465}, }
More research stories
- Decision trees and classificationHow can a prediction rule be both reliable and easy to read?
- Text mining and topic modelingWhat can statistics learn from what people write?
- Counts and rounded answersWhat do rounded answers hide?
- Statistical image analysisHow can we get reliable information from images?