概念

K-平均算法是一种无监督的聚类算法。无监督学习是一种自由的方式,其训练集不会标明类别,需要算法进行自我归纳。K-平均算法的思想是,对于给定的训练集,按照样本之间距离的大小划分为k个簇。让簇内的点尽量靠在一起,簇与簇之间的距离尽量大。

算法的基本步骤如下:

  1. 确定聚类数K,随机选择k个聚类中心。
  2. 计算训练集中的单个样本到每个聚类中心的距离,认定距离最近的聚类中心为样本的聚类归属。
  3. 计算簇中样本的平均位置,或者说质心,调整聚类中心的位置。
  4. 重复以上步骤直至各个聚类中心的位置不再发生改变。

TensorFlow实现

首先初始化训练数据和聚类中心,训练数据从文件中读取。

data = scio.loadmat('ex7data2.mat')
train_data = data['X'] # 读取名为X的矩阵

samples = tf.constant(train_data) # 初始化训练集
initial_centroids = tf.constant(np.array([[3., 3.], [6., 2.], [8., 5.]])) # 初始化聚类中心

这里的距离计算使用欧式距离。将训练集向量和聚类中心向量做减法。这里用到的一个点是当矩阵和列向量相减时,减法方法subtract会自动扩展两个参数的规模。当前两个参数因规模不匹配无法相减,要做到这一点,需要分别给两个参数添加一个维度。在本例中,训练集向量从(N * 2)变为(1 * N * 2),聚类向量从(3 * 2)变为(3 * 1 * 2)。其中N为训练集的个数。结果的规模为(3 * N * 2)。

def assign_to_nearest(samples, centroids):
    expanded_samples = tf.expand_dims(samples, 0)
    expanded_centroids = tf.expand_dims(centroids, 1) # 添加维度
    distances = tf.reduce_sum( tf.square(
               tf.subtract(expanded_samples, expanded_centroids)), 2) # 计算距离
    return tf.argmin(distances, 0) # 返回distances最小的索引,从矩阵意义上来说为每行最小的数的索引

下一步更新聚类中心的位置。

def update_centroids(samples, nearest_indices, k):
    nearest_indices = tf.to_int32(nearest_indices)
    partitions = tf.dynamic_partition(samples, nearest_indices, k) # 将矩阵依据nearest_indices的不同分为k个部分
    return tf.concat([tf.expand_dims(tf.reduce_mean(partition, 0), 0) for partition in partitions], 0) # 求各个聚类(partition)每一列的平均值,拼接为新的聚类中心

最后进行迭代计算。

iter_num = 10 # 迭代10次
features = 2 # 2个特征值
k = 3 # 聚类为3
with tf.Session() as sess:
    sess.run(tf.global_variables_initializer())
    sample_values = sess.run(samples)
    centroids = initial_centroids # 一开始使用初始的聚类中心
    for _ in range(iter_num):
        nearest_indices = assign_to_nearest(samples, centroids)
        updated_centroids = update_centroids(samples, nearest_indices, k)
        centroids = sess.run(updated_centroids) # 更新聚类中心

初始及最后生成的图像见下,可见聚类中心已经对数据进行了很好的区分。当然,并不是每次都有这样好的运气。初始聚类中心的选择不同,最终得到的结果也会大不相同。

参考资料: Clustering and k-means Python机器学习的练习七:K-Means聚类和主成分分析