A notion of stability for k-means clustering

被引：1

作者：

Le Gouic, T. ^{[1
,2
]}

Paris, Q. ^{[2
,3
]}

机构：

[1] Aix Marseille Univ, CNRS, Cent Marseille, I2M, Marseille, France

[2] Natl Res Univ, Higher Sch Econ, Moscow, Russia

[3] Int Lab Stochast Algorithms & High Dimens Inferen, Moscow, Russia

来源：

ELECTRONIC JOURNAL OF STATISTICS | 2018年 / 12卷 / 02期

关键词：

Clustering; k-means; stability; TRAINING DISTORTION; QUANTIZATION; CONVERGENCE; THEOREM; BOUNDS;

D O I：

10.1214/18-EJS1500

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

In this paper, we define and study a new notion of stability for the k-means clustering scheme building upon the field of quantization of a probability measure. We connect this definition of stability to a geometric feature of the underlying distribution of the data, named absolute margin condition, inspired by recent works on the subject.

引用

页码：4239 / 4263

页数：25

共 23 条

[1] CONVERGENCE OF VECTOR QUANTIZERS WITH APPLICATIONS TO OPTIMAL QUANTIZATION [J].

ABAYA, EF ;

WISE, GL .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1984, 44 (01) :183-189

[2] Improved minimax bounds on the test and training distortion of empirically designed vector quantizers [J].

Antos, A .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (11) :4022-4032

[3] Individual convergence rates in empirical vector quantizer design [J].

Antos, A ;

Györfi, L ;

György, A .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (11) :4013-4022

[4] The minimax distortion redundancy in empirical quantizer design [J].

Bartlett, PL ;

Linder, T ;

Lugosi, G .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1998, 44 (05) :1802-1813

[5] Stability of k-means clustering [J].

Ben-David, Shai ;

Pal, Ddvid ;

Simon, Hans Ulrich .

LEARNING THEORY, PROCEEDINGS, 2007, 4539 :20-+

[6] A sober look at clustering stability [J].

Ben-David, Shai ;

von Luxburg, Ulrike ;

Pal, David .

LEARNING THEORY, PROCEEDINGS, 2006, 4005 :5-19

[7] On the performance of clustering in Hilbert spaces [J].

Biau, Gerard ;

Devroye, Luc ;

Lugosi, Gabor .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (02) :781-790

[8] On Holder fields clustering [J].

Cadre, Benoit ;

Paris, Quentin .

TEST, 2012, 21 (02) :301-316

[9]

Chou PA, 1994, IEEE T INFORM THEORY, P457

[10]

GRAF S., 2000, FDN QUANTIZATION PRO

← 1 2 3 →