A discriminative framework for clustering via similarity functions

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Symposium on the Theory of Computing

• Publication date

  2008-05-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1374376.1374474
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering

  2007cited by this paper
• A Theory of Similarity Functions for Clustering

  2007influential reference
• How Good Is a Kernel When Used as a Similarity Measure?

  2007cited by this paper
• Kernels as features: On kernels, margins, and low-dimensional mappings

  2006cited by this paper
• Spectral Clustering by Recursive Partitioning

  2006cited by this paper
• Algorithms, Theory

  2006cited by this paper
• On a theory of learning with similarity functions

  2006influential reference
• The Spectral Method for General Mixture Models

  2005cited by this paper
• A divide-and-merge methodology for clustering

  2005influential reference
• Theory of classification : a survey of some recent advances

  2005cited by this paper
• On learning mixtures of heavy-tailed distributions

  2005cited by this paper
• On Spectral Learning of Mixtures of Distributions

  2005cited by this paper
• Kernel Methods in Computational Biology

  2005cited by this paper
• THEORY OF CLASSIFICATION: A SURVEY OF RECENT ADVANCES

  2004cited by this paper
• On Kernels, Margins, and Low-Dimensional Mappings

  2004cited by this paper
• A spectral algorithm for learning mixture models

  2004cited by this paper
• Correlation Clustering: maximizing agreements via semidefinite programming

  2004cited by this paper
• Kernel Methods for Pattern Analysis

  2004influential reference
• Clustering with qualitative information

  2003cited by this paper
• Approximation schemes for clustering problems

  2003cited by this paper
• Random sampling and approximation of MAX-CSPs

  2003cited by this paper
• Correlation Clustering

  2002cited by this paper
• An Impossibility Theorem for Clustering

  2002cited by this paper
• Diffusion Kernels on Graphs and Other Discrete Input Spaces

  2002cited by this paper
• Diffusion kernels on graphs and other discrete structures

  2002cited by this paper
• Spectral partitioning of random graphs

  2001cited by this paper
• Learning Kernel Classifiers: Theory and Algorithms

  2001cited by this paper
• Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation

  2001cited by this paper
• Learning mixtures of arbitrary gaussians

  2001cited by this paper
• On clusterings-good, bad and spectral

  2000cited by this paper
• A constant-factor approximation algorithm for the k-median problem (extended abstract)

  1999cited by this paper
• Quick Approximation to Matrices and Applications

  1999influential reference
• Learning mixtures of Gaussians

  1999cited by this paper
• Statistical learning theory

  1998influential reference
• Structural Risk Minimization Over Data-Dependent Hierarchies

  1998cited by this paper
• A Spectral Technique for Coloring Random 3-Colorable Graphs

  1997cited by this paper
• A Probabilistic Theory of Pattern Recognition

  1996influential reference
• A theory of the learnable

  1984cited by this paper
• The Art of Computer Programming

  1968cited by this paper

• A Characterization of List Language Identification in the Limit

  2025cites this paper
• Robust Estimation Under Heterogeneous Corruption Rates

  2025cites this paper
• Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics

  2025cites this paper
• (δ, ε)–K Segmentation for Characterizing Well-Clusterable Sets

  2025cites this paper
• Coresets for Clustering Under Stochastic Noise

  2025cites this paper
• Mastering Collaborative Multi-modal Data Selection: A Focus on Informativeness, Uniqueness, and Representativeness

  2024cites this paper
• Cost-Effective Deployment for Fully-Decoupled RAN: A Techno-Economic Approach

  2024cites this paper
• Scalable Algorithms for Individual Preference Stable Clustering

  2024cites this paper
• Robust Mixture Learning when Outliers Overwhelm Small Groups

  2024cites this paper
• LiD-FL: Towards List-Decodable Federated Learning

  2024cites this paper
• Large-Scale K-Clustering

  2024cites this paper
• Clustering-based gradual pattern mining

  2023cites this paper
• A Combinatorial Approach to Robust PCA

  2023cites this paper
• “Intelligent Heuristics Are the Future of Computing”

  2023cites this paper
• Constant Approximation for Individual Preference Stable Clustering

  2023cites this paper
• Private Distribution Learning with Public Data: The View from Sample Compression

  2023cites this paper
• Online Level-wise Hierarchical Clustering

  2023cites this paper
• A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm

  2023cites this paper
• Multi-channel Episodic Memory Building using Recurrent Kernel Machine

  2023cites this paper
• Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation

  2023cites this paper
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering

  2022cites this paper
• Individual Preference Stability for Clustering

  2022influential citation
• A Characterization of List Learnability

  2022cites this paper
• List-decodable covariance estimation

  2022influential citation
• Fitting Metrics and Ultrametrics with Minimum Disagreements

  2022cites this paper
• Estimation Contracts for Outlier-Robust Geometric Perception

  2022cites this paper
• Clustering mixture models in almost-linear time via list-decodable mean estimation

  2021cites this paper
• Statistical Query Lower Bounds for List-Decodable Linear Regression

  2021cites this paper
• Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

  2021cites this paper
• Genetic Programming for Evolving Similarity Functions Tailored to Clustering Algorithms

  2021cites this paper
• Privately Learning Mixtures of Axis-Aligned Gaussians

  2021cites this paper
• Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries

  2021cites this paper
• Large Scale K-Median Clustering for Stable Clustering Instances

  2021cites this paper
• Uniform Concentration Bounds toward a Unified Framework for Robust Clustering

  2021cites this paper
• DAG-Structured Clustering by Nearest Neighbors

  2021cites this paper
• Improving Ultrametrics Embeddings Through Coresets

  2021cites this paper
• Other Topics

  2020cites this paper
• High-Dimensional Space

  2020cites this paper
• Best-Fit Subspaces and Singular Value Decomposition (SVD)

  2020cites this paper
• List-Decodable Mean Estimation in Nearly-PCA Time

  2020cites this paper
• Robustly learning mixtures of k arbitrary Gaussians

  2020cites this paper
• An Effective Boundary Point Detection Algorithm Via k-Nearest Neighbors-Based Centroid

  2020cites this paper
• Algorithms for Massive Data Problems: Streaming, Sketching, and Sampling

  2020cites this paper
• Clustering under Perturbation Stability in Near-Linear Time

  2020cites this paper
• On Efficient Low Distortion Ultrametric Embedding

  2020cites this paper
• Feedback Clustering for Online Travel Agencies Searches: a Case Study

  2020cites this paper
• List Learning with Attribute Noise

  2020cites this paper
• A Notion of Individual Fairness for Clustering

  2020influential citation
• List Decodable Mean Estimation in Nearly Linear Time

  2020cites this paper
• Spherical Classification of Data, a New Rule-Based Learning Method

  2020cites this paper
• An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means

  2020cites this paper
• List-Decodable Subspace Recovery via Sum-of-Squares

  2020cites this paper
• List Decodable Subspace Recovery

  2020cites this paper
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time

  2020cites this paper
• Introduction

  2020cites this paper
• Foundations of Data Science

  2020cites this paper
• Scalable Bottom-Up Hierarchical Clustering

  2020cites this paper
• Scalable Hierarchical Agglomerative Clustering

  2020cites this paper
• Random Walks and Markov Chains

  2020cites this paper
• Wavelets

  2020cites this paper
• Index

  2020cites this paper
• Topic Models, Nonnegative Matrix Factorization, Hidden Markov Models, and Graphical Models

  2020cites this paper
• Scalable Hierarchical Clustering with Tree Grafting

  2019cites this paper
• Background Material

  2019cites this paper
• Analysis of Ward's Method

  2019influential citation
• Efficient Parameter-Free Clustering Using First Neighbor Relations

  2019cites this paper
• A Split-Merge Evolutionary Clustering Algorithm

  2019cites this paper
• List Decodable Learning via Sum of Squares

  2019cites this paper
• List-Decodable Linear Regression

  2019cites this paper
• Gradient-based Hierarchical Clustering using Continuous Representations of Trees in Hyperbolic Space

  2019cites this paper
• Clustering piecewise stationary processes

  2019cites this paper
• Data ultrametricity and clusterability

  2019cites this paper
• Subquadratic High-Dimensional Hierarchical Clustering

  2019cites this paper
• Recent Advances in Algorithmic High-Dimensional Robust Statistics

  2019cites this paper
• List-decodeable Linear Regression

  2019cites this paper
• Bipartite Split-Merge Evolutionary Clustering

  2019cites this paper
• Conditional Sparse ` p -norm Regression With Optimal Probability

  2018cites this paper
• A Fast Two-Level Approximate Euclidean Minimum Spanning Tree Algorithm for High-Dimensional Data

  2018cites this paper
• K-means properties on six clustering benchmark datasets

  2018cites this paper
• ICLR 2019 D 2 KE : From Distance to Kernel and Embedding via Random Features For Structured Inputs

  2018cites this paper
• Universal Multi-Party Poisoning Attacks

  2018cites this paper
• Provably noise-robust k-means clustering

  2018cites this paper
• Low Rank Approximation in the Presence of Outliers

  2018cites this paper
• Evolutionary Clustering Techniques for Expertise Mining Scenarios

  2018cites this paper
• Hierarchical Clustering with Structural Constraints

  2018cites this paper
• D2KE: From Distance to Kernel and Embedding

  2018cites this paper
• A user-satisfaction-based clustering method

  2018cites this paper
• Robust moment estimation and improved clustering via sum of squares

  2018cites this paper
• A PAC-Theory of Clustering with Advice

  2018cites this paper
• Dimensionality Reduction Approach for Many-Objective Vehicle Routing Problem with Demand Responsive Transport

  2017cites this paper
• To Cluster, or Not to Cluster: How to Answer the Question

  2017cites this paper
• Affinity Clustering: Hierarchical Clustering at Scale

  2017cites this paper
• Similarity-Based Segmentation of Multi-Dimensional Signals

  2017cites this paper
• Learning Discrete Distributions from Untrusted Batches

  2017cites this paper
• Streaming Algorithms for High Throughput Massive Datasets

  2017cites this paper
• Hierarchical Clustering Beyond the Worst-Case

  2017cites this paper
• Robust Communication-Optimal Distributed Clustering Algorithms

  2017cites this paper
• Algorithms and Complexity Results for Learning and Big Data

  2017cites this paper
• Hierarchical Clustering

  2017cites this paper
• Better Agnostic Clustering Via Relaxed Tensor Norms

  2017cites this paper