【Tensorflow】KMeans聚类实践

http://www.tensorfly.cn/ 中文社区
李航-统计学习方法

原理

Kmeans是一种无监督学习的聚类算法，通过多次的迭代使各个样本点到其所属族的距离最小。这个算法主要用于在数据分析前期对数据进行分类处理。
Kmeans的计算流程如下

1. 随机选取k个样本点做为聚类中心
2. 计算其他样本点到聚类中心的距离，并将其划分到最近的中心点一族
3. 重新计算每个类的中心店
4. 反复迭代（2）（3）两步直到中心点稳定不在变化（时间复杂度为O(n)）

距离衡量的方法有以下几种
摄特征空间为X是n维实数向量空间的 Rn$R^n$，xj,xi∈X，xi=(x(2)i,x(1)i,...,x(n)i)T$x_j,x_i\in X，x_i=(x_i^{(2)},x_i^{(1)},...,x_i^{(n)}{)}^T$,
xj=(x(2)j,x(1)j,...,x(n)j)T$x_j=(x_j^{(2)},x_j^{(1)},...,x_j^{(n)}{)}^T$,其中xi,xj$x_i,x_j$的距离Lp$L_p$定义为:
Lp(xi,xj)=(∑nl=1|x(l)i−x(l)j|p)1p$L_p(x_i,x_j)=(\sum _{l=1}^n{{|x_i^{(l)}-x_j^{(l)}|}^p)}^{\frac{1}{p}}$
当p>=1，当p=2时 就变成了我们所认识的欧式距离，也就是二维平面上的直线距离
L2(xi,xj)=(∑nl=1|x(l)i−x(l)j|2)12$L_2(x_i,x_j)=(\sum _{l=1}^n{{|x_i^{(l)}-x_j^{(l)}|}^2)}^{\frac{1}{2}}$
当p=1时，称为曼哈顿距离，也就是街区距离，如果说欧式距离是直角三角形斜边的话，那么曼哈顿距离就是两个直角边的和
L1(xi,xj)=∑nl=1|x(l)i−x(l)j|$L_1(x_i,x_j)=\sum _{l=1}^n|x_i^{(l)}-x_j^{(l)}|$
当p=∞的时候，就变成了各个坐标的最大值
L∞(xi,xj)=max|x(l)i−x(l)j|$L_{\infty }(x_i,x_j)=max|x_i^{(l)}-x_j^{(l)}|$

需要注意的是kmeas是对k值的选取，聚类中心的选择是十分敏感的

1. 随机中心选择
2. 选择彼此间尽可离得远的k个点
3. 选用层次聚类或者canopy算法初始化聚类

总结

• Kmeans对应基于训练集对特征空间的一个划分，当训练集，距离度量，k值与分类决策规则确定以后，其结果是唯一确定的
• Kmeans三要素：距离度量、k值选取和分类决策规则，常用的距离度量是欧式距离及一般的Lp距离，k值越小模型越复杂。k值的选择反映了近似误差预估计误差之间的权衡，通常由交叉验证选择最优的k，常用的分类决策规则是多数表决，对应于经验风险最小化。

代码实现

import tensorflow as tf
import numpy as np
from tensorflow.examples.tutorials.mnist import input_data
from tensorflow.contrib.factorization import KMeans

mnist = input_data.read_data_sets("input_data/", one_hot=True)
full_data_x = mnist.train.images

# 定义超参数
num_steps = 100
batch_size = 1024
k = 25
num_features = 784
num_classes = 10

# 定义输入输出
X = tf.placeholder(tf.float32, shape=[None, num_features])
Y = tf.placeholder(tf.float32, shape=[None, num_classes])

# 使用tensorflow集成的Kmeans方法
kmeans = KMeans(inputs=X, num_clusters=k, distance_metric='cosine', use_mini_batch=True)
# 构建kmeans图
training_graph = kmeans.training_graph()

# tensorflow版本不同所以启用不同参数 tensorflow1.4+多了一个参数
if len(training_graph) > 6:    # Tensorflow 1.4+
    (all_scores, cluster_idx, scores, cluster_centers_initialized,
     cluster_centers_var, init_op, train_op) = training_graph
else:
    (all_scores, cluster_idx, scores, cluster_centers_initialized,
     init_op, train_op) = training_graph

# 将族固定成一个元组
cluster_idx = cluster_idx[0]
# 计算平均距离
avg_distance = tf.reduce_mean(scores)

# 初始化
init_var = tf.global_variables_initializer()
sess = tf.Session()
sess.run(init_var, feed_dict={X: full_data_x})
sess.run(init_op, feed_dict={X: full_data_x})

# 开始训练
for step in range(1, num_steps+1):
    # 得到平均距离和族索引
    _, d, idx = sess.run([train_op, avg_distance, cluster_idx], feed_dict={X: full_data_x})
    print("step %i;平均距离为： %f" % (step, d))

# 将计算的结果k个质心载入真实分类
counts = np.zeros(shape=(k, num_classes))
for i in range(len(idx)):
    counts[idx[i]] += mnist.train.labels[i]
print(counts)

# 选取每个count中最大的映射为label
labels_map = [np.argmax(c) for c in counts]
labels_map = tf.convert_to_tensor(labels_map)

# 按照组内顺序返回cluster_id行
cluster_label = tf.nn.embedding_lookup(labels_map, cluster_idx)

# 计算准确率
correct_prediction = tf.equal(cluster_label, tf.cast(tf.argmax(Y, 1), tf.int32))
accuracy_op = tf.reduce_mean(tf.cast(correct_prediction, tf.float32))

# 测试模型
test_x, test_y = mnist.test.images, mnist.test.labels
print("Test Accuracy:", sess.run(accuracy_op, feed_dict={X: test_x, Y: test_y}))