K-means 聚类

k-means 算法，也被称为 k-平均 或 k-均值，是一种得到最广泛使用的聚类算法。 它把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。

相异度计算方法：

• 欧几里得距离
• 曼哈顿距离
• 闵可夫斯基距离
• 皮尔逊相关系数

优点

• 简单、快速，可并行计算
• 已经获得防范的应用

缺点

• 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。
• 对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。

k-means算法

输入：簇的数目k和包含n个对象的数据库。
输出：k个簇，使平方误差准则最小。

算法步骤：

1.为每个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心。
2.将样本集中的样本按照最小距离原则分配到最邻近聚类
3.使用每个聚类中的样本均值作为新的聚类中心。
4.重复步骤2.3直到聚类中心不再变化。
5.结束，得到K个聚类

k-means示例

#!/usr/bin/env python
# coding: utf-8
%matplotlib inline
import time
import numpy as np
import tensorflow as tf
import matplotlib.pyplot as plt
from sklearn.datasets.samples_generator import make_blobs
from sklearn.datasets.samples_generator import make_circles
N = 200
K = 4
DATA_TYPE = 'blobs'
MAX_ITERS = 1000
colourindexes = [2, 1, 4, 3]
# k-means不适用于circles数据，2个类足以demo这个问题
if (DATA_TYPE == 'circle'):
    K = 2
    colourindexes = [2, 1]
# 根据聚类中心生成测试数据
centers = [(-2, -2), (-2, 1.5), (1.5, -2), (2, 1.5)]
if (DATA_TYPE == 'circle'):
    data, features = make_circles(
        n_samples=N, shuffle=True, noise=0.01, factor=0.4)
else:
    data, features = make_blobs(n_samples=N, centers=centers,
                                n_features=2, cluster_std=0.8,
                                shuffle=False, random_state=42)
    #fig, ax = plt.subplots()
    #ax.scatter(np.asarray(centers).transpose()[0], np.asarray(
    #    centers).transpose()[1], marker='o', s=250)
    #plt.show()
    fig, ax = plt.subplots()
    ax.scatter(np.asarray(centers).transpose()[0], np.asarray(
        centers).transpose()[1], marker='o', s=250)
    ax.scatter(data.transpose()[0], data.transpose()[
               1], marker='o', s=100, c=features, cmap=plt.cm.coolwarm)
    plt.show()
def bucket_mean(data, bucket_ids, num_buckets):
    total = tf.unsorted_segment_sum(data, bucket_ids, num_buckets)
    count = tf.unsorted_segment_sum(
        tf.ones_like(data), bucket_ids, num_buckets)
    return total / count
start = time.time()
points = tf.Variable(data)
cluster_assignments = tf.Variable(tf.zeros([N], dtype=tf.int64))
centroids = tf.Variable(tf.slice(points.initialized_value(), [0, 0], [K, 2]))
rep_centroids = tf.reshape(tf.tile(centroids, [N, 1]), [N, K, 2])
rep_points = tf.reshape(tf.tile(points, [1, K]), [N, K, 2])
sum_squares = tf.reduce_sum(tf.square(rep_points - rep_centroids),
                            reduction_indices=2)
best_centroids = tf.argmin(sum_squares, 1)
did_assignments_change = tf.reduce_any(
    tf.not_equal(best_centroids, cluster_assignments))
means = bucket_mean(points, best_centroids, K)
with tf.control_dependencies([did_assignments_change]):
    do_updates = tf.group(
        centroids.assign(means),
        cluster_assignments.assign(best_centroids))
changed = True
iters = 0
sess = tf.Session()
sess.run(tf.initialize_all_variables())
while changed and iters < MAX_ITERS:
    iters += 1
    [changed, _] = sess.run([did_assignments_change, do_updates])
    [centers, assignments] = sess.run([centroids, cluster_assignments])
    fig, ax = plt.subplots()
    ax.scatter(sess.run(points).transpose()[0], sess.run(points).transpose()[
               1], marker='o', s=200, c=assignments, cmap=plt.cm.coolwarm)
    ax.scatter(centers[:, 0], centers[:, 1], marker='^',
               s=550, c=colourindexes, cmap=plt.cm.plasma)
    ax.set_title('Iteration ' + str(iters))
    # plt.savefig("kmeans" + str(iters) + ".png")
    plt.show()
fig, ax = plt.subplots()
ax.scatter(sess.run(points).transpose()[0], sess.run(points).transpose()[
           1], marker='o', s=200, c=assignments, cmap=plt.cm.coolwarm)
ax.scatter(np.asarray(centers).transpose()[0], np.asarray(
        centers).transpose()[1], marker='o', s=250, c=colourindexes, cmap=plt.cm.plasma)
plt.show()

end = time.time()
print ("Found in %.2f seconds" % (end - start)), iters, "iterations"
print "Centroids:", centers
print "Cluster assignments:", assignments

Found in 2.15 seconds 8 iterations
Centroids: [[ 1.65289262 -2.04643427]
 [-2.0763623   1.61204964]
 [-2.08862822 -2.07255306]
 [ 2.09831502  1.55936014]]
Cluster assignments: [2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 3 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3]