Algorithms for the Bregman k-Median problem / Marcel R. Ackermann. 2009
Inhalt
[17]1 Introduction
[29]2 Bregman divergences
[57]3 The k-median problem
3.1 The generalized k-median problem
[62]3.2 Bregman k-median clustering
[67]3.3 A simple optimal algorithm for d=1
[71]4 (1+ε)-approximate clustering by uniform sampling
4.1 Algorithm for [γ,δ]-sampleable dissimilarity measures
[74]4.1.1 Superset sampling
[76]4.1.2 The algorithm
[79]4.1.3 Analysis for k=2
[84]4.1.4 Analysis for k≥2
[91]4.1.5 Adaptation for weighted input sets
4.2 Sampling for large classes of dissimilarity measures
[96]4.2.1 Sampling for Mahalanobis distances
[98]4.2.2 Sampling for μ-similar Bregman divergences
[101]4.2.3 Sampling for the Hellinger distance
[103]4.2.4 Sampling for arbitrary metrics with bounded doubling dimension
[112]4.2.5 Sampling for the Hamming distance
[118]4.3 Generalization of the sampling property
[120]4.4 Discussion
[123]5 A practical O(log k)-approximate algorithm
5.1 Algorithm BregMeans++
[127]5.1.1 Non-uniform sampling scheme for -similar Bregman divergences
[128]5.1.2 Proof of Theorem 5.3
5.2 Non-uniform sampling on separable instances
[145]5.3 Discussion
[149]6 Strong coresets for Mahalanobis distances
[151]6.1 Har-Peled-Mazumdar coresets
[152]6.1.1 Euclidean k-means clustering
[154]6.1.2 Mahalanobis k-median clustering
[157]6.1.3 Properties of Har-Peled-Mazumdar coresets
[162]6.2 A new coreset construction based on non-uniform sampling
[167]6.3 Discussion
[169]7 Weak coresets for μ-similar Bregman divergences
7.1 Construction of -weak coresets
[178]7.2 Application to Bregman k-median clustering
[183]7.3 Discussion
[185]8 On the limits of using uniform sampling
[186]8.1 Sampleable Bregman divergences avoid singularities
[190]8.2 Explicit domain bounds for some Bregman divergences
[196]8.3 Discussion
[199]A Applications
[200]A.1 Estimating mixtures of identical Gaussian sources
[203]A.2 Model reduction for data compression
[206]A.3 Codebook generation for vector quantization in speech processing
B Mathematical fundamentals
B.1 The vectorspace ℝd
[211]B.1.1 Vector arithmetic and inner product
[212]B.1.2 Distances and metrics
[213]B.1.3 Convex sets
[213]B.1.4 Relative interior
B.2 Inequalities
[213]B.2.1 Triangle inequality of the reals
[214]B.2.2 Bounds to the binomial coefficient
[214]B.2.3 Bounds on the harmonic number
[215]B.2.4 Chebyshev's sum inequality
B.3 Calculus
[216]B.3.1 Partial derivatives
[217]B.3.2 Mean value theorem
[217]B.3.3 Taylor expansion
[218]B.3.4 Convex functions
[219]B.3.5 Positive definiteness
B.4 Probability theory