Click here to start
Table of contents
Approximate geometric clustering in arbitrary dimensions
Clustering Problems (generic)
Slide 3
Applications of Clustering
Distance-based Clustering
Voronoi Daigrams
Slide 7
K-means Clustering: Lloyd’s algorithm
Algorithm vs Heuristics
Hardness of Clustering
Approximation Clustering
Results : k-means
Results : k-medians
Preliminaries: Irreducibility
Class of Clustering Problems
Slide 16
k-Means: Random Sampling Procedure
A first attempt : k-center
Looks OK but ….
Slide 20
The difficulty
A property of optimal clustering
Slide 23
Slide 24
Slide 25
Guessing the size of P’
General Algorithm (High level)
Analysis
Monte Carlo
Discrete K-Means: Random Sampling Procedure
K-Median: Random Sampling Procedure
K-Median: Random Sampling Procedure
Slide 33
Other Results
Open Problems
Thank You
Author:
OpenOfficeorg2.2.1