概念
K-平均算法是一种无监督的聚类算法。无监督学习是一种自由的方式,其训练集不会标明类别,需要算法进行自我归纳。K-平均算法的思想是,对于给定的训练集,按照样本之间距离的大小划分为k个簇。让簇内的点尽量靠在一起,簇与簇之间的距离尽量大。
算法的基本步骤如下:
- 确定聚类数K,随机选择k个聚类中心。
- 计算训练集中的单个样本到每个聚类中心的距离,认定距离最近的聚类中心为样本的聚类归属。
- 计算簇中样本的平均位置,或者说质心,调整聚类中心的位置。
- 重复以上步骤直至各个聚类中心的位置不再发生改变。
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) # 更新聚类中心
初始及最后生成的图像见下,可见聚类中心已经对数据进行了很好的区分。当然,并不是每次都有这样好的运气。初始聚类中心的选择不同,最终得到的结果也会大不相同。