经验|fast-and-provably-good-seedings-for-k-means
社群用户来源包含：麻省理工学院 斯坦福大学 牛津大学 卡内基梅隆大学 剑桥大学 加州大学伯克利分校 苏黎世联邦理工学院 新加坡国立大学 普林斯顿大学 多伦多大学 帝国理工学院 墨尔本大学 香港科技大学 加州大学洛杉矶分校 清华大学 洛桑联邦理工学院 香港大学 爱丁堡大学 东京大学 香港中文大学 北京大学 复旦大学 武汉大学 南开大学 中科院等数百所名牌大学的研究生、博士以及教授；NVidia Facebook Line 微软 IBM 谷歌 Bosch Amazon Tesla Motors 百度 华为 英特尔 腾讯 阿里巴巴 蚂蚁金服 科大讯飞 旷视科技 碳云智能 地平线 软银投资 红杉资本等上千家全球一流AI相关企业的工程师以及技术专家。
本文来源：知乎，作者：Mr.张，以获授权转载。
大家好我是zyy，本人是机器学习和深度学习的初学爱好者，想跟大家一起分享我的学习经验，大家一起交流。我写的东西不一定全对，但肯定是我一步一步走出来的坑，嚼烂了的经验，可以供大家直接“吸收”。
我的文章主要会涉及各种机器学习和深度学习算法的推导和轮子的实现，以及一些小的应用demo，偶尔还会有一些论文的算法实现。
文中出现的所有代码都可以在我的[GitHub]上找到（https://github.com/YuyangZhangFTD/zyy_ML-DL）。
这篇文章是今年，哦不，是去年nips上一篇关于k-means算法改进的文章。
顺便在此祝各位新年快乐，万事如意，身体健康。
顺便抱怨一句，越来越看不懂现在看客们的口味了，那些一篇速成xxx、XXX预测模型（其实就是简单模型套用不知哪来的数据）、一篇文章看懂XXX、简析XXX（翻来覆去的算法来回说）大行其道，真是心凉。所以我决定，从这片开始，封面放小黄图，以吸引各位看官(ง •̀_•́)ง
哦对了，我还要做个广告，我最近翻译了吴恩达Andrew Ng的新书《Machine Learning Yearning》（他还在写，我也还在继续翻译），是一本用在工业界的机器学习参考书，是大家非常好的厕所读物，链接在此：https://github.com/YuyangZhangFTD/Trans_MachineLearningYearning/blob/master/MLY/main.pdf。
k-means
先说说最简单的k-means算法。
k-means是最简单的聚类算法之一，主要思想是，随机初始化k个中心点，一个中心点代表一类，计算数据点到各中心点的距离，将离数据点最近的中心点定位该数据点的类别，之后计算每一类点的中心位置，为新的中心点位置，迭代一定次数后，中心点位置会趋于收敛，由此得到聚类的位置。
算法步骤如下：
随机选择k个中心点
; 令离
最近的数据X为聚类簇 ，其中 ; 令为每个聚类簇的中心
; 重复2和3直至C不再变化。
k-means算法也算是EM应用，一种特殊的GMM模型，只不过简化了需要估计的参数和对类别的判断，从一个软分类的概率判断（看属于哪个类的概率大）变成了直接找最近的指示函数。话说起来，好像EM那篇还没写完...
咳咳，言归正传。显而易见，我们最初选择的初始位置，会很大程度影响这个算法准确度和收敛程度，所以，我们又有了k-means++。、
k-means++
k-means++: The Advantages of Careful Seeding 这篇文章提出了一种基于采样方法的中心点初始化方法。具体做法的思想是选取使各个中心点尽可能地远离，来减少由于中心点相邻而导致的误差（也不算是误差，错误？大概是这个意思，笔者语文学的还不如英语）。
具体的做法就是随机先选取一个初始中心点，然后计算各个数据点到这个中心点的距离，最后用距离做比值，随机抽取一个点，此时抽取的点，有很大概率离初始化的中心点较远，重复此步骤，然后按k-means来迭代，直至收敛。
算法步骤如下：
任意选取一个数据点作为中心点
; 以
的概率选取其余的中心点 ; 重复2直到选满k个中心点
其余步骤与标准k-means相同
这个方法称为
近似k-means++
k-means++的好处我们已经提了，但仍然存在很多问题：计算复杂度。随着
具体算法步骤如下：
随机选出第一个中心点
; 随机抽取一个数据点
并计算距离 ; 用MH采样出一个长为m的序列，取最后
-1个作为中心点； 其余步骤与k-means相同。
由此可见，计算复杂度从
改进的k-mc^2
终于讲到老大哥了，每次写东西，要讲的东西总是写到最后了，下次开个专题梳理基础。
Fast and Provably Good Seedings for k-Means这篇文章跟上面那篇是同一拨人，恩，同一拨人搞得同一个大事情，挺有才的，一篇发了AAAI，一篇发了nips，不得不说，厉害了我的哥。
这篇也没干别的事情，换了一个提案分布
不要问我优点是啥，都是理论上的优点以及在数据集上表现好的优点。喜欢理论或者学CS的同学可以自己download下来自己仔细看看，我也不在这仔细说了（我才不会说笔者看不懂这些理论证明呢 (。・`ω´・)，PAC那些还是留给专业人员去琢磨吧，我就不掺和了）。
以及，这两篇文章的作者提供了一个python库，是拿C写的，python可以调，大家可以下下来用一下，这是github地址：https://github.com/obachem/kmc2。
Reference
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.
Bachem O, Lucic M, Hassani S H, et al. Approximate K-Means++ in Sublinear Time[C]//AAAI. 2016: 1459-1467.
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.
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.
AI商学院 特聘导师 招募
AI商学院的三大教育体系：导师指导班+专业技术班+全球博士班。充分满足不同导师的时间安排和资源需求，以及不同学生的学习需求和商业需求 。
招募要求：全球高校AI相关教授，副教授，博导；全球名校在读AI相关专业博士以上；全球企业AI相关技术主管以上；全球知名企业CEO，董事长；全球投资公司合伙人以上。
义务和权利：①义务：每年至少出席1次AI商学院的主要活动，如 开学典礼、毕业典礼、全球AI发展博士论坛、全球AI名企巡回拜访学习等系列活动、作为AI商学院学生的导师；②权利：有偿指导AI商学院的学生；对接全球商业合作资源；免费开放AI商学院部分全球资源使用。
联系方式：bushyu（微信）
全球人工智能近期经典文章推荐