前言：
机器学习----聚类算法的应用很广泛，属于非监督学习的它在无法提前定义标签的前提下将训练数据聚类。我们今天讨论其中比较简单的一种算法k-means算法。
k-means算法
每当你观察某些数据源时，很可能会发现数据会以某种形式形成聚类（cluster） 。如下图：
我们很容易看出来这些数据点可以聚成三类，但具体怎么聚，中心点在哪，数据多了以后还会出现聚几类的问题。这时我们就改用k-means算法了。
我们先举几个生活中的例子：
例如，每个输入可以是博客文章的标题（我们可以设法用数字向量来表示它） ，那么在这种情况下，我们的目标可能是对相似的文章进行聚类，也可能是了解用户都在写什么博客内容。或者，假设我们有一张包含数千种（红、绿、蓝）颜色的图片，但是我们需要一个5 色版本来进行丝网印刷。这时，聚类分析不仅可以帮助我们选出 5 种颜色，并且还能将“色差”控制在最小的范围之内。
k-均值算法（k-means）是一种最简单的聚类分析方法，它通常需要首先选出聚类 k 的数目，然后把输入划分为集合 S 1 ，…，S k ，并使得每个数据到其所在聚类的均值（中心对象）的距离的平方之和(即欧式距离)最小化。由于将 n 个点分配到 k 个聚类的方法非常多，所以寻找一个最优聚类方法是一件非常困难的事情。一般情况下，为了找到一个好的聚类方法，我们可以借助于迭代算法。
具体步骤：
1.首先从 d 维空间中选出选择 k 个数据点作为初始聚类的均值（即中心）。
2.计算每个数据点到这些聚类的均值（即聚类中心）的距离，然后把各个数据点分配给离它最近的那个聚类。
3.如果所有数据点都不再被重新分配，那么就停止并保持现有聚类。
4.如果仍有数据点被重新分配，则重新计算均值，并返回到第 2 步。
写具体的代码之前，我们先自己写个计算向量的工具类，方便以后使用：
from __future__ import division
import re, math, random
#
# functions for working with vectors
#
def vector_add(v, w):
return [int(v_i) + int(w_i) for v_i, w_i in zip(v,w)]
def vector_subtract(v, w):
return [int(v_i) - int(w_i) for v_i, w_i in zip(v,w)]
def vector_sum(vectors):
return reduce(vector_add, vectors)
def scalar_multiply(c, v):
return [c * v_i for v_i in v]
def vector_mean(vectors):
n = len(vectors)
return scalar_multiply(1/n, vector_sum(vectors))
def dot(v, w):
"""v_1 * w_1 + ... + v_n * w_n"""
return sum(int(v_i) * int(w_i) for v_i, w_i in zip(v, w))
def sum_of_squares(v):
"""v_1 * v_1 + ... + v_n * v_n"""
return dot(v, v)
def magnitude(v):
return math.sqrt(sum_of_squares(v))
def squared_distance(v, w):
return sum_of_squares(vector_subtract(v, w))
def distance(v, w):
return math.sqrt(squared_distance(v, w))
def shape(A):
num_rows = len(A)
num_cols = len(A[0]) if A else 0
return num_rows, num_cols
def get_row(A, i):
return A[i]
def get_column(A, j):
return [A_i[j] for A_i in A]
def make_matrix(num_rows, num_cols, entry_fn):
return [[entry_fn(i, j) for j in range(num_cols)]
for i in range(num_rows)]
def is_diagonal(i, j):
return 1 if i == j else 0
这样我们计算欧氏距离显得方便了很多。
class KMeans:
def __init__(self, k):
self.k = k
self.means = None
def classify(self, input):
#求input的值里那个cluster最近，返回下标
return min(range(self.k),
key=lambda i: vector.squared_distance(input, self.means[i]))
def train(self, inputs):
self.means = random.sample(inputs, self.k)
assignments = None
while True:
new_assignments = map(self.classify, inputs)
#结束条件
if assignments == new_assignments:
return
#继续训练
assignments = new_assignments
for i in range(self.k):
i_points = [p for p, a in zip(inputs, assignments) if a == i ]
if i_points:
self.means[i] = vector.vector_mean(i_points)
图片的重新分配底色
有了k-means，我们来简单实现下上文提到的丝网印刷(5),
def recolor_image(input_file, k=5):
img = mpimg.imread(input_file)
pixels = [pixel for row in img
for pixel in row]
clusterer = KMeans(k)
clusterer.train(pixels)
def recolor(pixel):
cluster = clusterer.classify(pixel)
return clusterer.means[cluster]
new_img = [[recolor(pixel) for pixel in row]
for row in img]
plt.imshow(new_img)
plt.axis('off')
plt.show()
if __name__ == '__main__':
input_file = "image/test.jpg"
recolor_image(input_file, k=5)
我们来看看效果：
效果还行，有点像照片底片~
- tips:测试时不要上传太大的图片哦，我这个是500 X 500的，跑了大概1min30s(4核CPU)，笔记本风扇嗡嗡的~ - _ -
结束语
还有很多聚类的算法，这里只写出一个，欢迎留言给我，求告知除k-means和knn以外的算法哦~共同学习。
