【Machine Learning】22.K-means聚类

K-means聚类

• 1.导入
• 3.在图像压缩上应用K-means
• 4.课后题

无监督学习的一个代表性问题，聚类，而K-means是聚类算法当中最经典的

1.导入

import numpy as np
import matplotlib.pyplot as plt
from utils import *

%matplotlib inline

2.K-means实现

K-means算法自动聚类相似数据点在一起。将得到一个训练集 { x ( 1 ) , . . . , x ( m ) } \{x^{(1)}, ..., x^{(m)}\} {x(1),...,x(m)}，您需要将数据分组为几个有凝聚力的“集群”。
K-means是一个迭代过程：

• 首先猜测初始质心
• 然后通过以下方式细化此猜测
  • 重复地将示例指定给它们最近的质心，然后
  • 基于assignments重新计算质心centroids。

伪代码如下：

    # Initialize centroids
    # K is the number of clusters
    centroids = kMeans_init_centroids(X, K)
    
    for iter in range(iterations):
        # Cluster assignment step: 
        # Assign each data point to the closest centroid. 
        # idx[i] corresponds to the index of the centroid 
        # assigned to example i
        idx = find_closest_centroids(X, centroids)

        # Move centroid step: 
        # Compute means based on centroid assignments
        centroids = compute_means(X, idx, K)

• 算法的内部循环重复执行两个步骤：
  • 将每个训练示例 x （ i ） x^{（i）} x（i）分配到其最近的质心，以及
  • 使用指定的点重新计算每个质心的平均值。
• K K K-means算法将始终收敛于质心的某个最终均值集。
• 然而，收敛解可能并不总是理想的，这取决于质心的初始设置。
  • 因此，在实践中，K-means算法通常在不同的随机初始化下运行几次。
  • 在来自不同随机初始化的这些不同解之间进行选择的一种方法是选择具有最低代价函数值（失真）的解。

2.1 找到最近的质心

在K-means算法的“聚类分配”阶段算法将每个训练示例 x （ i ） x^{（i）} x（i）分配到其最近的质心，给定质心的当前位置。

练习1

您的任务是完成“find_closest_centroids”中的代码。

• 此函数获取数据矩阵“X”和质心位置

• 它应该向每个训练示例输出一个一维数组“idx”（它的元素数与“X”相同），该数组包含最近质心的索引（一个以 { 1 ， … ， K } \{1，…，K\} {1，…，K}表示的值，其中 K K K是质心的总数）。

• 具体来说，对于我们设置的每个示例 x （ i ） x^{（i）} x（i）

c ( i ) : = j t h a t    m i n i m i z e s ∣ ∣ x ( i ) − μ j ∣ ∣ 2 , c^{(i)} := j \quad \mathrm{that \; minimizes} \quad ||x^{(i)} - \mu_j||^2, c(i):=jthatminimizes∣∣x(i)−μj​∣∣2,
其中

• c （ i ） c^{（i）} c（i）是最接近 x ( i ) x^{(i)} x(i)的执行的索引
• μ j \mu_j μj​是第 j j j个质心的位置（值）。（存储在起始代码的“质心”中）

# UNQ_C1
# GRADED FUNCTION: find_closest_centroids

def find_closest_centroids(X, centroids):
    """
    Computes the centroid memberships for every example
    
    Args:
        X (ndarray): (m, n) Input values      
        centroids (ndarray): k centroids
    
    Returns:
        idx (array_like): (m,) closest centroids
    
    """

    # Set K
    K = centroids.shape[0]

    # You need to return the following variables correctly
    idx = np.zeros(X.shape[0], dtype=int) #此时shape[0]代表点的个数

    ### START CODE HERE ###
    for i in range(X.shape[0]):# 对X中的每个点
        distance = []
        for j in range(centroids.shape[0]):# 在K个初始质心中寻找对应的质心
            norm_ij = np.linalg.norm(X[i] - centroids[j])
            distance.append(norm_ij)
        idx[i] = np.argmin(distance)


    ### END CODE HERE ### 
    
    return idx

加载数据并检验

X = np.load("data/ex7_X.npy")

print("First five elements of X are:\n", X[:5]) 
print('The shape of X is:', X.shape)

First five elements of X are:
 [[1.84207953 4.6075716 ]
 [5.65858312 4.79996405]
 [6.35257892 3.2908545 ]
 [2.90401653 4.61220411]
 [3.23197916 4.93989405]]
The shape of X is: (300, 2)

# Select an initial set of centroids (3 Centroids)
initial_centroids = np.array([[3,3], [6,2], [8,5]])

# Find closest centroids using initial_centroids
idx = find_closest_centroids(X, initial_centroids)

# Print closest centroids for the first three elements
print("First three elements in idx are:", idx[:3])

First three elements in idx are: [0 2 1]

2.2 计算质心

算法根据第一阶段聚类结果重新计算质心

Exercise 2

请完成下面的“compute_centroid”以重新计算每个质心的值

• Specifically, for every centroid μ k \mu_k μk​ we set
  μ k = 1 ∣ C k ∣ ∑ i ∈ C k x ( i ) \mu_k = \frac{1}{|C_k|} \sum_{i \in C_k} x^{(i)} μk​=∣Ck​∣1​i∈Ck​∑​x(i)

  where

  • C k C_k Ck​ 分配给质心k的点集合 is the set of examples that are assigned to centroid k k k
  • ∣ C k ∣ |C_k| ∣Ck​∣ 示例数量 is the number of examples in the set C k C_k Ck​

• Concretely, if two examples say x ( 3 ) x^{(3)} x(3) and x ( 5 ) x^{(5)} x(5) are assigned to centroid k = 2 k=2 k=2,
  then you should update μ 2 = 1 2 ( x ( 3 ) + x ( 5 ) ) \mu_2 = \frac{1}{2}(x^{(3)}+x^{(5)}) μ2​=21​(x(3)+x(5)).

# UNQ_C2
# GRADED FUNCTION: compute_centpods

def compute_centroids(X, idx, K):
    """
    Returns the new centroids by computing the means of the 
    data points assigned to each centroid.
    
    Args:
        X (ndarray):   (m, n) Data points
        idx (ndarray): (m,) Array containing index of closest centroid for each 
                       example in X. Concretely, idx[i] contains the index of 
                       the centroid closest to example i
        K (int):       number of centroids
    
    Returns:
        centroids (ndarray): (K, n) New centroids computed
    """
    
    # Useful variables
    m, n = X.shape
    
    # You need to return the following variables correctly
    centroids = np.zeros((K, n))
    
    ### START CODE HERE ###
    for k in range(K):
        points = X[idx == k]
        centroids[k] = np.mean(points,axis=0) #注意是对列求平均
    ### END CODE HERE ## 
    
    return centroids

调用

K = 3
centroids = compute_centroids(X, idx, K)

print("The centroids are:", centroids)


The centroids are: [[2.42830111 3.15792418]
 [5.81350331 2.63365645]
 [7.11938687 3.6166844 ]]

2.3 查看算法工作

在别的数据集上看看K-means算法的工作

def plot_progress_kMeans(X, centroids, previous_centroids, idx, K, i):
    # Plot the examples
    plt.scatter(X[:, 0], X[:, 1], c=idx)
    
    # Plot the centroids as black 'x's
    plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', c='k', linewidths=3)
    
    # Plot history of the centroids with lines
    for j in range(centroids.shape[0]):
        draw_line(centroids[j, :], previous_centroids[j, :])
    
    plt.title("Iteration number %d" %i)


def run_kMeans(X, initial_centroids, max_iters=10, plot_progress=False):
    """
    Runs the K-Means algorithm on data matrix X, where each row of X
    is a single example
    """
    
    # Initialize values
    m, n = X.shape
    K = initial_centroids.shape[0]
    centroids = initial_centroids
    previous_centroids = centroids    
    idx = np.zeros(m)
    
    # Run K-Means
    for i in range(max_iters):
        
        #Output progress
        print("K-Means iteration %d/%d" % (i, max_iters-1))
        
        # For each example in X, assign it to the closest centroid
        idx = find_closest_centroids(X, centroids)
        
        # Optionally plot progress
        if plot_progress:
            plot_progress_kMeans(X, centroids, previous_centroids, idx, K, i)
            previous_centroids = centroids
            
        # Given the memberships, compute new centroids
        centroids = compute_centroids(X, idx, K)
    plt.show() 
    return centroids, idx

# Load an example dataset
X = load_data()

# Set initial centroids
initial_centroids = np.array([[3,3],[6,2],[8,5]])
K = 3

# Number of iterations
max_iters = 10

centroids, idx = run_kMeans(X, initial_centroids, max_iters, plot_progress=True)

运行结果：黑点表示每次迭代质心的移动

2.4 随机初始化

了解函数“kMeans_init_centroids”是如何实现的。

• 代码首先随机地对示例的索引进行混洗（使用np.random.permutation（））。
• 然后，它基于索引的随机排列来选择前 K K K个示例。
  • 这允许随机选择示例，而不会有两次选择同一示例的风险。

# You do not need to modify this part

def kMeans_init_centroids(X, K):
    """
    This function initializes K centroids that are to be 
    used in K-Means on the dataset X
    
    Args:
        X (ndarray): Data points 
        K (int):     number of centroids/clusters
    
    Returns:
        centroids (ndarray): Initialized centroids
    """
    
    # Randomly reorder the indices of examples
    randidx = np.random.permutation(X.shape[0])
    
    # Take the first K examples as centroids
    centroids = X[randidx[:K]]
    
    return centroids

3.在图像压缩上应用K-means

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

3.1 加载及预处理数据

加载图片

# Load an image of a bird
original_img = plt.imread('bird_small.png')

展示原图片：可视化

# Visualizing the image
plt.imshow(original_img)

看看shape

print("Shape of original_img is:", original_img.shape)


Shape of original_img is: (128, 128, 3)

要调用“run_kMeans”，首先需要将矩阵“original_img”转换为二维矩阵。

*下面的代码重塑了矩阵“original_img”，以创建 m × 3 m\times 3 m×3像素颜色矩阵（其中 m = 16384 = 128 × 128 m=16384=128\times128 m=16384=128×128）

# Divide by 255 so that all values are in the range 0 - 1
original_img = original_img / 255

# Reshape the image into an m x 3 matrix where m = number of pixels
# (in this case m = 128 x 128 = 16384)
# Each row will contain the Red, Green and Blue pixel values
# This gives us our dataset matrix X_img that we will use K-Means on.

X_img = np.reshape(original_img, (original_img.shape[0] * original_img.shape[1], 3))

3.2 在数据上应用模型

# Run your K-Means algorithm on this data
# You should try different values of K and max_iters here
K = 16                       
max_iters = 10               

# Using the function you have implemented above. 
initial_centroids = kMeans_init_centroids(X_img, K) 

# Run K-Means - this takes a couple of minutes
centroids, idx = run_kMeans(X_img, initial_centroids, max_iters) 

print("Shape of idx:", idx.shape)
print("Closest centroid for the first five elements:", idx[:5])


Shape of idx: (16384,)
Closest centroid for the first five elements: [2 2 2 2 2]

3.3 压缩模型

在找到代表图像的顶部 K ＝ 16 K＝16 K＝16颜色后，您现在可以使用find_closest_centroids函数。

• 这允许您使用每个像素的质心指定来表示原始图像。
• 请注意，您已经显著减少了描述图像所需的位数。
• 原始图像的每一个 128 × 128 128\times128 128×128像素位置需要24位，因此总大小为 128 × 128 × 24 = 393216 128\times 128\times24=393216 128×128×24=393216位。
• 新的表示需要以16种颜色的字典形式的一些开销存储，每种颜色需要24位，但图像本身每个像素位置只需要4位。
• 因此，最终使用的比特数为 16 × 24 + 128 × 128 × 4 = 65920 16\times 24+128\times 128\times 4=65920 16×24+128×128×4=65920比特，这对应于将原始图像压缩约6倍。

# Represent image in terms of indices
X_recovered = centroids[idx, :] 

# Reshape recovered image into proper dimensions
X_recovered = np.reshape(X_recovered, original_img.shape) 

4.课后题

无监督学习的概念

c i c_i ci​的概念

是点i对应的质心的索引

随机初始化

选择的是所有初始化中得到的代价J最小的那一次聚类结果

K-means的代价

K-means算法是收敛的，迭代过程中代价只会减小不会增加

elbow方法

有时候不知道应该确定K的值为多少，就采用elbow方法绘制代价随K值变化的函数，这个函数肯定是单调递减的，一般选择这个函数的“拐点”对应的横坐标值作为K值