聚类算法之k-means算法图像像素重新处理

前言：

机器学习----聚类算法的应用很广泛，属于非监督学习的它在无法提前定义标签的前提下将训练数据聚类。我们今天讨论其中比较简单的一种算法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以外的算法哦~共同学习。