目录

导言

关于Kmeans

kmeans本质是EM算法的特殊情况

Kmeans收敛性证明

为什么在计算k-means之前要将数据点在各维度上归一化

k-means不适用哪些数据（异常值对聚类中心影响很大，需要离群点检测和剔除）

K值选择

质心选择

时间复杂度

伪代码

具体实现

---

导言

这题是我今年秋招面试字节跳动遇到的题，当时比较紧张，磕磕绊绊写了个大概，面试完后我又整理了一下代码，同时参考了其他一些博客的代码，写了一个我的实现版本供大家参考。

 

关于Kmeans

kmeans其实是一个思想非常简单，但是深究有很多可以提问的算法。

 

kmeans本质是EM算法的特殊情况

对比混合高斯模型和K-means可以发现，混合高斯使用了“软”指定，为每个样例分配的类z(i)是有一定的概率的，同时计算量也变大了，每个样例i都要计算属于每一个类别j的概率。而kmeans使用的是“硬”指定，对于每个样例，它属于一个类的概率是1，而属于其他类的概率是0。

 

Kmeans收敛性证明

这也是面试字节跳动一轮中的一道面试题，当时没有回答出来，感觉字节跳动面试官的水平很高，我回去之后详细的研究了一下kmeans，收获了许多。

最小化E是一个NP难问题，kmeans采用了贪心策略，通过迭代来近似求解，关于收敛性证明我看到最好的解答是百面机器学习上的解答：

上面把kmeans与EM算法对应上了，然后我们只需证明EM算法是收敛的即可，这里具体可见李航老师的统计学习方法。

 

为什么在计算k-means之前要将数据点在各维度上归一化

因为数据点各维度的量级不同。

举例来说，基于RFM模型的会员分群，每个会员分别有R（最近一次购买距今的时长）、F（来店消费的频率）和M（购买金额）。如果这是一家奢侈品商店，你会发现M的量级（可能几万元）远大于F（可能平均10次以下），如果不归一化就算k-means，相当于F这个特征完全无效。如果我希望能把常客与其他顾客区别开来，不归一化就做不到。

 

k-means不适用哪些数据（异常值对聚类中心影响很大，需要离群点检测和剔除）

数据特征极强相关`的数据集，因为会很难收敛（损失函数是非凸函数），一般要用kernal k-means，将数据点`映射到更高维度再分群。

数据集可分出来的簇密度不一，或有很多离群值（outliers），这时候考虑使用密度聚类。

 

K值选择

（1）经验法

一般来说，我们会根据对数据的`先验经验`选择一个合适的k值，如果没有什么先验知识，则可以通过`交叉验证`选择一个合适的k值。　

（2）关于肘部法则

增加簇数有助于降低每个簇的簇内方差之和，给定k>0，计算簇内方差和var(k)，绘制var关于k的曲线，曲线的第一个（或最显著的）拐点暗示正确的簇数。

 

质心选择

（1）KMeans++算法

 1.假设分为K类；

 2.从输入的数据点集合中随机选择一个点作为`第一个聚类中心`；

 3.对于数据集中的每一个点x，计算其与最近的聚类中心(指已选择的聚类中心)的距离D(x);

 4.选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点被选取为聚类中心的概率较大；

 5.重复3和4两个步骤直到`K个聚类中心被选出来`；

 6.利用这K个初始的聚类中心运行标准的K-Means算法；

 简单来说就是选择中心点时各中心点的距离要做到尽可能的远。

（2）二分k均值（bisecting k-means）算法

主要思想：

首先将所有点作为一个簇，然后将该簇`一分为二`，之后选择能最大程度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇，以此进行下去，直到簇的数目等于用户给定的数目k为止。

隐含着一个原则：

因为聚类的误差平方和能够衡量聚类性能，该值越小表示数据点越接近于它们的质心，聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次的划分，因为误差平方和越大，表示该簇聚类越不好，越有可能是多个簇被当成一个簇了，所以我们首先需要对这个簇进行划分。

 

时间复杂度

O(K*N)

 

伪代码

创建 k 个点作为起始质心 (随机选择):当任意一个点的簇分配结果发生改变的时候:对数据集中的每个数据点:对每个质心:计算质心与数据点之间的距离将数据点分配到距其最近的簇对每一个簇:求出均值并将其更新为质心

 

具体实现

# -*- coding: utf-8 -*-
import tensorflow as tf
from random import shuffledef kmeans(data, k, max_iter):""":param data: batch_size*feature_len:param k: k clusters:param max_iter::return:"""n_data = len(data)dim = len(data[0])r_indexs = [i for i in range(len(data))]shuffle(r_indexs)graph = tf.Graph()with graph.as_default():sess = tf.Session()centers = [tf.Variable(data[i]) for i in r_indexs[:k]]# 计算两个样本欧式距离v1 = tf.placeholder(tf.float64, [dim])v2 = tf.placeholder(tf.float64, [dim])euclid_dist = tf.sqrt(tf.reduce_sum(tf.pow(tf.subtract(v1, v2), 2)))# 获得样本所在簇cluster_dists = tf.placeholder(tf.float64, [k])cluster_assignment = tf.argmin(cluster_dists, axis=0)# assignments保存每个样本分簇结果assignments = [tf.Variable(0) for i in range(n_data)]# 更新每个样本分簇结果assignment_value = tf.placeholder(tf.int32)cluster_assigns = []for assignment in assignments:cluster_assigns.append(tf.assign(assignment, assignment_value))# 计算新的簇中心cluster_data = tf.placeholder(tf.float64, [None, dim])mean_op = tf.reduce_mean(cluster_data, axis=0)# 簇中心new_center = tf.placeholder(tf.float64, [dim])# 更新簇中心center_assign = []for center in centers:center_assign.append(tf.assign(center, new_center))'''初始化所有的状态值这会帮助初始化图中定义的所有Variables。Variable-initializer应该定义在所有的Variables被构造之后，这样所有的Variables才会被纳入初始化'''init = tf.global_variables_initializer()sess.run(init)num_iter = 0# 开始迭代while num_iter < max_iter:# E步for idx in range(len(data)):x = data[idx]# 为每个实例计算距离distances = [sess.run(euclid_dist, feed_dict={v1: x, v2: sess.run(center)}) for center in centers]# 获得簇分配assignment = sess.run(cluster_assignment, feed_dict={cluster_dists: distances})# 更新分配结果sess.run(cluster_assigns[idx], feed_dict={assignment_value: assignment})# M步for cluster_idx in range(k):# 收集所有分配给该集群的向量cluster_contain = [data[i] for i in range(len(data)) if sess.run(assignments[i]) == cluster_idx]# 计算新的集群中心点new_location = sess.run(mean_op, feed_dict={cluster_data: cluster_contain})# 更新中心点sess.run(center_assign[cluster_idx], feed_dict={new_center: new_location})num_iter += 1centers = sess.run(centers)assignments = sess.run(assignments)return centers, assignments