Semi-Supervised Maximum Margin Clustering with Pairwise Constraints

The pairwise constraints specifying whether a pair of samples should be grouped together or not have been successfully incorporated into the conventional clustering methods such as k-means and spectral clustering for the performance enhancement. Nevertheless, the issue of pairwise constraints has not been well studied in the recently proposed maximum margin clustering (MMC), which extends the maximum margin framework in supervised learning for clustering and often shows a promising performance. This paper therefore proposes a pairwise constrained MMC algorithm. Based on the maximum margin idea in MMC, we propose a set of effective loss functions for discouraging the violation of given pairwise constraints. For the resulting optimization problem, we show that the original nonconvex problem in our approach can be decomposed into a sequence of convex quadratic program problems via constrained concave-convex procedure (CCCP). Subsequently, we present an efficient subgradient projection optimization method to solve each convex problem in the CCCP sequence. Experiments on a number of real-world data sets show that the proposed constrained MMC algorithm is scalable and outperforms the existing constrained MMC approach as well as the typical semi-supervised clustering counterparts.

• Publication year

  2012

• Venue

  IEEE Transactions on Knowledge and Data Engineering

• Publication date

  2012-05-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1109/TKDE.2011.68
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Convex optimization

  2010cited by this paper
• Tighter and Convex Maximum Margin Clustering

  2009cited by this paper
• Improving Classification with Pairwise Constraints: A Margin-Based Approach

  2008influential reference
• Constrained spectral clustering through affinity propagation

  2008cited by this paper
• Maximum Margin Clustering with Pairwise Constraints

  2008influential reference
• Efficient multiclass maximum margin clustering

  2008influential reference
• Large scale manifold transduction

  2008cited by this paper
• Transductive support vector machines for structured variables

  2007influential reference
• Maximum Margin Clustering Made Practical

  2007cited by this paper
• Learning nonparametric kernel matrices from pairwise constraints

  2007cited by this paper
• Learning Distance Metrics with Contextual Constraints for Image Retrieval

  2006cited by this paper
• Convex Analysis and Optimization

  2006cited by this paper
• Training linear SVMs in linear time

  2006cited by this paper
• Joint Cluster Analysis of Attribute Data and Relationship Data: the Connected k-Center Problem

  2006cited by this paper
• Large Scale Transductive SVMs

  2006cited by this paper
• Generalized Maximum Margin Clustering and Unsupervised Kernel Learning

  2006cited by this paper
• Kernel Methods for Missing Variables

  2005cited by this paper
• Semi-supervised clustering with metric learning using relative comparisons

  2005cited by this paper
• Distance Metric Learning for Large Margin Nearest Neighbor Classification

  2005cited by this paper
• Unsupervised and Semi-Supervised Multi-Class Support Vector Machines

  2005cited by this paper
• Semi-supervised graph clustering: a kernel approach

  2005cited by this paper
• Model-based Clustering With Probabilistic Constraints

  2005cited by this paper
• A discriminative learning framework with pairwise constraints for video object classification

  2004cited by this paper
• Maximum Margin Clustering

  2004cited by this paper
• Integrating constraints and metric learning in semi-supervised clustering

  2004influential reference
• A probabilistic framework for semi-supervised clustering

  2004cited by this paper
• Computing Gaussian Mixture Models with EM Using Equivalence Constraints

  2003cited by this paper
• The Concave-Convex Procedure

  2003cited by this paper
• Adjustment Learning and Relevant Component Analysis

  2002cited by this paper
• On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines

  2002cited by this paper
• Cluster Ensembles --- A Knowledge Reuse Framework for Combining Multiple Partitions

  2002cited by this paper
• Distance Metric Learning with Application to Clustering with Side-Information

  2002cited by this paper
• Constrained K-means Clustering with Background Knowledge

  2001cited by this paper
• In Advances in Neural Information Processing Systems

  1996cited by this paper
• OHSUMED: an interactive retrieval evaluation and new large test collection for research

  1994cited by this paper
• Constraints

  1979cited by this paper
• Mathematical Programming manuscript No. (will be inserted by the editor) Pegasos: Primal Estimated sub-GrAdient SOlver for SVM

  year unknowncited by this paper

• A survey on semi-supervised graph clustering

  2024cites this paper
• Robust and compact maximum margin clustering for high-dimensional data

  2024cites this paper
• Semi-Supervised Clustering Under a “Compact-Cluster” Assumption

  2023cites this paper
• Knowledge augmentation-based soft constraints for semi-supervised clustering

  2023cites this paper
• Deep semi-supervised clustering based on pairwise constraints and sample similarity

  2023cites this paper
• Two-stage semi-supervised clustering ensemble framework based on constraint weight

  2022cites this paper
• Semi-Supervised Clustering via Dynamic Graph Structure Learning

  2022cites this paper
• Reductive and effective discriminative information-based nonparallel support vector machine

  2021cites this paper
• Graph-based semi-supervised learning via improving the quality of the graph dynamically

  2021cites this paper
• Similarity-based Classification: Connecting Similarity Learning to Binary Classification

  2020cites this paper
• Semi-Supervised Clustering With Constraints of Different Types From Multiple Information Sources

  2020cites this paper
• Adaptive Regularized Semi-Supervised Clustering Ensemble

  2020cites this paper
• MEGA

  2020influential citation
• A Classification-Based Approach to Semi-Supervised Clustering with Pairwise Constraints

  2020cites this paper
• Grouping Methods for Facilitating Emergency Evacuations

  2020cites this paper
• Semi-Supervised Density Peaks Clustering Based on Constraint Projection

  2020influential citation
• An Algorithmic Framework for Fairness Elicitation

  2020cites this paper
• Improving Attribute Classification with Imperfect Pairwise Improving Attribute Classification with Imperfect Pairwise Constraints Constraints

  2020cites this paper
• Stratified Feature Sampling for Semi-Supervised Ensemble Clustering

  2019cites this paper
• Adaptive Semi-Supervised Classifier Ensemble for High Dimensional Data Classification

  2019cites this paper
• Improving Attribute Classification with Imperfect Pairwise Constraints

  2019cites this paper
• Improving Semi-Supervised Clustering Algorithms with Active Query Selection

  2019cites this paper
• Semi-Supervised Ensemble Clustering

  2019cites this paper
• Pairwise-Constrained Deep Document Clustering

  2019cites this paper
• A Survey on Semi Supervised Clustering For High Dimensional Data Clustering

  2019influential citation
• Imbalance-aware Pairwise Constraint Propagation

  2019cites this paper
• Improved Maximum Margin Clustering via the Bundle Method

  2019cites this paper
• LMMO: A Large Margin Approach for Refining Regulatory Motifs

  2018cites this paper
• Progressive Semisupervised Learning of Multiple Classifiers

  2018cites this paper
• L1-Norm Distance Minimization-Based Fast Robust Twin Support Vector $k$ -Plane Clustering

  2018cites this paper
• Semi-supervised discriminative clustering with graph regularization

  2018cites this paper
• Analysis of k-partite ranking algorithm in area under the receiver operating characteristic curve criterion

  2018cites this paper
• Multiple-Instance Ordinal Regression

  2018cites this paper
• Parallel Semi-Supervised Multi-Ant Colonies Clustering Ensemble Based on MapReduce Methodology

  2018cites this paper
• Semi-Supervised Ensemble Clustering Based on Selected Constraint Projection

  2018cites this paper
• Integrated Semi-Supervised Model for Learning and Classification

  2018cites this paper
• Affinity and Penalty Jointly Constrained Spectral Clustering With All-Compatibility, Flexibility, and Robustness

  2017cites this paper
• Multi-objective artificial immune algorithm for fuzzy clustering based on multiple kernels

  2017influential citation
• Multi-View Matrix Completion for Clustering with Side Information

  2017cites this paper
• Constraint-Based Clustering Algorithm for Multi-density Data and Arbitrary Shapes

  2017cites this paper
• Fast Robust Twin Support Vector Clustering

  2017cites this paper
• Semi-Supervised Clustering for High Dimensional Data Clustering

  2017cites this paper
• Combined constraint-based with metric-based in semi-supervised clustering ensemble

  2017cites this paper
• Prediction of Television Audience Rating Based on Fuzzy Cognitive Maps with Forward Stepwise Regression

  2017cites this paper
• Semi-Supervised Clustering Based on Exemplars Constraints

  2017cites this paper
• Adaptive Ensembling of Semi-Supervised Clustering Solutions

  2017cites this paper
• Incremental Semi-Supervised Clustering Ensemble for High Dimensional Data Clustering

  2016cites this paper
• Bayesian mechanisms in spatial cognition: towards real-world capable computational cognitive models of spatial memory

  2016cites this paper
• Efficient Spectral Clustering for Large Data Set

  2016cites this paper
• Human Centered Computing

  2016influential citation
• Classifying imbalanced data in distance-based feature space

  2016cites this paper
• Outlier factor based partitional clustering analysis with constraints discovery and representative objects generation

  2016cites this paper
• AN EFFICIENT SPECTRAL CLUSTERING ON SOCIAL NETWORK UNSTRUCTURED DATA FOR IMPROVED CLUSTERING ACCURACY

  2016cites this paper
• Decorrelation–Separability-Based Affinity Propagation for Semisupervised Clustering of Hyperspectral Images

  2016cites this paper
• Comparing Clustering with Pairwise and Relative Constraints

  2016cites this paper
• The Generalized Optimization on Scalable Constrained Spectral Clustering Methodology

  2016cites this paper
• Pairwise Constraint-Guided Sparse Learning for Feature Selection

  2016cites this paper
• Image Clustering Using Active-Constraint Semi-Supervised Affinity Propagation

  2016cites this paper
• Multi-manifold Discriminant Isomap for visualization and classification

  2016cites this paper
• Semi-Unsupervised Clustering Using Reinforcement Learning

  2016cites this paper
• A Maximum Margin Approach for Semisupervised Ordinal Regression Clustering

  2016influential citation
• Constraint Co-Projections for Semi-Supervised Co-Clustering

  2016cites this paper
• ENHANCED NEIGHBORHOOD NORMALIZED POINTWISE MUTUAL INFORMATION ALGORITHM FOR CONSTRAINT AWARE DATA CLUSTERING

  2016cites this paper
• A High Dimensional Clustering Algorithm Based on Dynamic P System and Swarm Intelligence

  2016cites this paper
• Unsupervised domain adaptation without source domain training samples: a maximum margin clustering based approach

  2016cites this paper
• A Biometric Key Generation Method Based on Semisupervised Data Clustering

  2015cites this paper
• Level set method for image segmentation based on moment competition

  2015cites this paper
• Comprehensive Study and Analysis of Partitional Data Clustering Techniques

  2015cites this paper
• Optimization and Scalable Constrained Clustering Performances

  2015cites this paper
• Optimal WCDMA network planning by multiobjective evolutionary algorithm with problem-specific genetic operation

  2015cites this paper
• Deep Transductive Semi-supervised Maximum Margin Clustering

  2015influential citation
• An Efficient Semi-Supervised Clustering Algorithm with Sequential Constraints

  2015cites this paper
• Constrained agglomerative hierarchical software clustering with hard and soft constraints

  2015cites this paper
• A semi-supervised clustering ensemble approach integrated constraint-based and metric-based

  2015cites this paper
• Scalable Constrained Spectral Clustering

  2015cites this paper
• Weight evaluation for features via constrained data-pairscan't-linkq

  2014cites this paper
• Learning a mixture model for clustering with the completed likelihood minimum message length criterion

  2014cites this paper
• Semi-Supervised Nonlinear Distance Metric Learning via Forests of Max-Margin Cluster Hierarchies

  2014cites this paper
• Semi-supervised clustering via multi-level random walk

  2014cites this paper
• Modified Constraint Scores for Semi-Supervised Feature Selection

  2014cites this paper
• Contextual Person Identification in Multimedia Data

  2014cites this paper
• Constraint Based Partitional Clustering – a Comprehensive Study and Analysis

  2014cites this paper
• Constraint Neighborhood Projections for Semi-Supervised Clustering

  2014cites this paper
• Multiclass maximum margin clustering via immune evolutionary algorithm for automatic diagnosis of electrocardiogram arrhythmias

  2014cites this paper
• Soft large margin clustering

  2013cites this paper
• Classification partiellement supervisée par SVM : application à la détection d'événements en surveillance audio. (Partially Supervised Classification Based on SVM : application to Audio Events Detection for Surveillance)

  2013cites this paper
• Active Selection of Label Data for Semi-Supervised Learning Algorithm

  2013cites this paper
• Semi-supervised Clustering by Input Pattern Assisted Pairwise Similarity Matrix Completion

  2013cites this paper
• Hierarchical semi-supervised confidence-based active clustering and its application to the extraction of topic hierarchies from document collections

  2013cites this paper
• A study of K-Means-based algorithms for constrained clustering

  2013cites this paper
• Semi-supervised hybrid clustering by integrating Gaussian mixture model and distance metric learning

  2013cites this paper
• Linearithmic Time Sparse and Convex Maximum Margin Clustering

  2012cites this paper
• Semi-supervised clustering with discriminative random fields

  2012cites this paper
• Exemplars-Constraints for Semi-supervised Clustering

  2012cites this paper
• Improving clustering with pairwise constraints: a discriminative approach

  2012influential citation
• Performance based Efficient K-means Algorithm for Data Mining

  2011cites this paper
• Semi Supervised NCC: Introducing Prior Knowledge To Normalized Cut Clustering

  year unknowncites this paper