吴恩达机器学习课后习题ex7 K-means（python实现）

K-means

在本练习中，您将实现K-means算法并将其用于图像压缩。您将首先从一个示例2D数据集开始，它将帮助您获得K-means算法如何工作的直觉。之后，您将使用K-means算法对图像进行压缩，方法是将图像中出现的颜色数量减少到该图像中最常见的颜色。这部分练习你将使用ex7.m。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.io import loadmat
mat=loadmat('ex7data2.mat')
data=pd.DataFrame(mat['X'],columns=['x1','x2'])
fig,ax=plt.subplots(figsize=(12,8))
ax.scatter(data2['x1'],data2['x2'])
ax.set_xlabel('x1')
ax.set_ylabel('x2')
plt.show()

簇分配，为每个x寻找离他最近的聚类点

def find_centers(x,centros):
  idx=np.zeros(len(x))
  for i in range(len(x)):
  #x[n,2] centros(k,2)
    mindist=1000000
    for j in range(len(centros)):
      dis=np.sum((x[i,:]-centros[j,:])**2)
      if dis<mindist:
        mindist=dis
        idx[i]=j
  return idx
      

然后重新计算聚类中心的位置

def compute_centros(x,idx,k):
  centros=[] #(k,2)
  for i in range(k):
    centros_i=np.mean(x[idx==i],axis=0)
    centros.append(centros_i)
  return np.array(centros)

最后重复进行前两步骤

centros=np.array([[3,3],[6,2],[8,5]])
def run_kmeans(x,centros,iters):
  for i in range(iters):
    idx=find_centers(x,centros)
    centros=compute_centros(x,idx,3)
  return idx

#画出可视化图像
x=data.values
idx=run_kmeans(x,centros,10)
cluster0=x[idx==0]
cluster1=x[idx==1]
cluster2=x[idx==2]
fig,ax=plt.subplots(figsize=(12,8))
ax.scatter(cluster0[:,0],cluster0[:,1],color='r', label='Cluster 1')
ax.scatter(cluster1[:,0],cluster1[:,1],color='g', label='Cluster 2')
ax.scatter(cluster2[:,0],cluster2[:,1],color='b', label='Cluster 3')
ax.legend()
plt.show()

随机初始化聚类中心点

def init_centros(x,k):
#直接选取x中k各点是常用方法
#选取索引值
  index=np.random.randint(0,len(x),k)
  return x[index]

#画图观察不同初始聚类中心点对结果的影响
for i in range(5):
  idx=run_kmeans(x,init_centros(x,3),10)
  cluster0=x[idx==0]
cluster1=x[idx==1]
cluster2=x[idx==2]
fig,ax=plt.subplots(figsize=(12,8))
ax.scatter(cluster0[:,0],cluster0[:,1],color='r', label='Cluster 1')
ax.scatter(cluster1[:,0],cluster1[:,1],color='g', label='Cluster 2')
ax.scatter(cluster2[:,0],cluster2[:,1],color='b', label='Cluster 3')
ax.legend()
plt.show()

有一个结果是这样的，说明初始值的选取对分类结果产生了影响。

图片压缩

在图像的直接24位颜色表示中，每个像素被表示为三个8位无符号整数（范围从0到255），指定红色、绿色和蓝色强度值。这种编码常被称为RGB编码。我们的图像包含数千种颜色，在这部分练习中，您将把颜色的数量减少到16种颜色。通过这样的减少，可以有效地表示（压缩）照片。具体来说，您只需要存储16种选定颜色的RGB值，对于图像中的每个像素，您现在只需要在该位置存储颜色的索引（其中仅需要4位来表示16种可能性）。在本练习中，您将使用K-means算法来选择将用于表示压缩图像。具体地说，您将把原始图像中的每个像素作为一个数据示例，并使用K-mean算法来查找16种颜色，这些颜色最适合对三维RGB空间中的像素进行分组（聚类）。计算完图像上的簇质心后，将使用16种颜色替换原始图像中的像素。

import skimage.io as io

img = io.imread("bird_small.png")
plt.imshow(img)

mat3=loadmat('bird_small.mat')
mat3
x=mat3['A']
x.shape #（128，128，3）

#归一化
x=x/255
x=x.reshape(-1,3)
#以前每个像素点用8bit来表示
#现在只需要16种颜色，也就是只需要4bit表示
#运行k-means
idx=run_kmeans(x,init_centros(x,16),20)
centros=compute_centros(x,idx,16) 

然后将每个像素位置指定给其最近的质心。这允许您使用每个像素的质心指定来表示原始图像。

原始图像的128×128像素位置中的每一个都需要24位，因此总大小为128×128×24=393216位。新的表示法需要以16种颜色的字典形式进行一些开销存储，每种颜色需要24位，但是图像本身只需要每个像素位置4位。因此，最终使用的位数是16×24+128×128×4=65920位，相当于将原始图像压缩约6倍。

#将每个像素位置指定给其最近的质心
im=np.zeros(x.shape)
for i in range(16):
  im[idx==i]=centros[i]
im=im.reshape(128,128,3)
plt.imshow(im)

使用sklearn的kmeans函数

from sklearn.cluster import KMeans
model=KMeans(n_clusters=16, n_init=100)
model.fit(x)
idx=model.predict(x)
centros=model.cluster_centers_
im=np.zeros(x.shape)
for i in range(16):
  im[idx2==i]=centros2[i]
im=im.reshape(128,128,3)
plt.imshow(im)