[读论文]fast-and-provably-good-seedings-for-k-means

fast-and-provably-good-seedings-for-k-means

大家好我是zyy，本人是机器学习和深度学习的初学爱好者，想跟大家一起分享我的学习经验，大家一起交流。我写的东西不一定全对，但肯定是我一步一步走出来的坑，嚼烂了的经验，可以供大家直接“吸收”

我的文章主要会涉及各种机器学习和深度学习算法的推导和轮子的实现，以及一些小的应用demo，偶尔还会有一些论文的算法实现。

文中出现的所有代码都可以在我的GitHub上找到。

[GitHub]

这篇文章是今年，哦不，是去年nips上一篇关于k-means算法改进的文章。

顺便在此祝各位新年快乐，万事如意，身体健康。

顺便抱怨一句，越来越看不懂现在看客们的口味了，那些一篇速成xxx、XXX预测模型（其实就是简单模型套用不知哪来的数据）、一篇文章看懂XXX、简析XXX（翻来覆去的算法来回说）大行其道，真是心凉。所以我决定，从这片开始，封面放小黄图，以吸引各位看官(ง •̀_•́)ง

哦对了，我还要做个广告，我最近翻译了吴恩达Andrew Ng的新书《Machine Learning Yearning》（他还在写，我也还在继续翻译），是一本用在工业界的机器学习参考书，是大家非常好的厕所读物，链接在此。

k-means

先说说最简单的k-means算法。

k-means是最简单的聚类算法之一，主要思想是，随机初始化k个中心点，一个中心点代表一类，计算数据点到各中心点的距离，将离数据点最近的中心点定位该数据点的类别，之后计算每一类点的中心位置，为新的中心点位置，迭代一定次数后，中心点位置会趋于收敛，由此得到聚类的位置。

算法步骤如下：

1. 随机选择k个中心点C=\{c_1,c_2,...,c_k\};
2. 令离c_i最近的数据X为聚类簇C_i，其中i=1,2,3...,k;
3. 令c_i为每个聚类簇的中心c_i=\frac{1}{|C|}\sum_{x\in C_i}{x};
4. 重复2和3直至C不再变化。

k-means算法也算是EM应用，一种特殊的GMM模型，只不过简化了需要估计的参数和对类别的判断，从一个软分类的概率判断（看属于哪个类的概率大）变成了直接找最近的指示函数。话说起来，好像EM那篇还没写完...

咳咳，言归正传。显而易见，我们最初选择的初始位置，会很大程度影响这个算法准确度和收敛程度，所以，我们又有了k-means++。

k-means++

k-means++: The Advantages of Careful Seeding 这篇文章提出了一种基于采样方法的中心点初始化方法。具体做法的思想是选取使各个中心点尽可能地远离，来减少由于中心点相邻而导致的误差（也不算是误差，错误？大概是这个意思，笔者语文学的还不如英语）。

具体的做法就是随机先选取一个初始中心点，然后计算各个数据点到这个中心点的距离，最后用距离做比值，随机抽取一个点，此时抽取的点，有很大概率离初始化的中心点较远，重复此步骤，然后按k-means来迭代，直至收敛。

算法步骤如下：

1. 任意选取一个数据点作为中心点c_1 ;
2. 以\frac{D(x)^2}{\sum_{x\in X}D(x)^2}的概率选取其余的中心点c_i;
3. 重复2直到选满k个中心点
4. 其余步骤与标准k-means相同

这个方法称为

。这么做可以很大程度上避免初始选初始选中心点的问题。

近似k-means++

k-means++的好处我们已经提了，但仍然存在很多问题：计算复杂度。随着k的增加和样本数量的增大，在计算距离的时候，计算量会逐步增加。所以又有人提出了近似k-means++的算法，Approximate K-Means++ in Sublinear Time这篇文章，用MCMC的方法来近似抽样选择中心点，用Metropolis-Hastings来进行采样中心点。随机选取一个中心点c_1，然后用MCMC的方法采样出长为m的数列，取最后k-1个数作为中心点，采样分布为p(x)=\frac{D(x)^2}{\sum_{x\in X}D(x)^2}，其中提案分布选择q(x)=\frac{1}{n}来简化，剩下部分与传统k-means相同。

具体算法步骤如下：

1. 随机选出第一个中心点c_1；
2. 随机抽取一个数据点x并计算距离d_x；
3. 用MH采样出一个长为m的序列，取最后k-1个作为中心点；
4. 其余步骤与k-means相同。

由此可见，计算复杂度从

到

，这样就允许有更多的数据参与聚类，这在图像领域极为有用。

改进的k-mc^2

终于讲到老大哥了，每次写东西，要讲的东西总是写到最后了，下次开个专题梳理基础。

Fast and Provably Good Seedings for k-Means这篇文章跟上面那篇是同一拨人，恩，同一拨人搞得同一个大事情，挺有才的，一篇发了AAAI，一篇发了nips，不得不说，厉害了我的哥。

这篇也没干别的事情，换了一个提案分布p(x|c_1)=\frac{1}{2}\frac{d(x,c_1)^2}{\sum_{x'\in X}{d(x',c_1)^2}}+\frac{1}{2}\frac{1}{|X|}，可以满足更多数据分布假设下的鲁棒性，同时还有一系列的优点。

不要问我优点是啥，都是理论上的优点以及在数据集上表现好的优点。喜欢理论或者学CS的同学可以自己download下来自己仔细看看，我也不在这仔细说了（我才不会说笔者看不懂这些理论证明呢 (。・`ω´・)，PAC那些还是留给专业人员去琢磨吧，我就不掺和了）。

以及，这两篇文章的作者提供了一个python库，是拿C写的，python可以调，大家可以下下来用一下，这是github地址。

Reference

1. Arthur D, Vassilvitskii S. k-means++: The advantages of careful seeding[C]//Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2007: 1027-1035.
2. Bachem O, Lucic M, Hassani S H, et al. Approximate K-Means++ in Sublinear Time[C]//AAAI. 2016: 1459-1467.
3. Bachem O, Lucic M, Hassani H, et al. Fast and Provably Good Seedings for k-Means[C]//Advances in Neural Information Processing Systems. 2016: 55-63.
4. Celebi M E, Kingravi H A, Vela P A. A comparative study of efficient initialization methods for the k-means clustering algorithm[J]. Expert Systems with Applications, 2013, 40(1): 200-210.