Shift of pairwise similarities for data clustering

DOI10.1007/S10994-022-06189-6MaRDI QIDQ6174502zbMATH OpenOpenAlexFDO

Authors Morteza Haghir Chehreghani

Publication date 14 July 2023

Published in Machine Learning (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.13103

zbMATH Keywords

clusteringcorrelation clusteringlocal search optimizationshift of pairwise similaritiesunsupervised learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Several clustering methods (e.g., Normalized Cut and Ratio Cut) divide the Min Cut cost function by a cluster dependent factor (e.g., the size or the degree of the clusters), in order to yield a more balanced partitioning. We, instead, investigate adding such regularizations to the original cost function. We first consider the case where the regularization term is the sum of the squared size of the clusters, and then generalize it to adaptive regularization of the pairwise similarities. This leads to shifting (adaptively) the pairwise similarities which might make some of them negative. We then study the connection of this method to Correlation Clustering and then propose an efficient local search optimization algorithm with fast theoretical convergence rate to solve the new clustering problem. In the following, we investigate the shift of pairwise similarities on some common clustering methods, and finally, we demonstrate the superior performance of the method by extensive experiments on different datasets.

Recommendations

• Pairwise data clustering and applications
• Correlation Clustering
• EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
• \textit{Kernel cuts}: kernel and spectral clustering meet regularization
• A Weight-Adaptive Laplacian Embedding for Graph-Based Clustering

Cites work

• A new approach to the minimum cut problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Adaptive trajectory analysis of replicator dynamics for data clustering
• Correlation clustering
• Correlation clustering in general weighted graphs
• Faster balanced clusterings in high dimension
• scientific article; zbMATH DE number 903638 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• Image Segmentation by Dominant Sets
• Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance
• Introduction to Information Retrieval
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

This page was built for publication: Shift of pairwise similarities for data clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174502)