物以类聚
经典的无监督学习算法 ——K-Means聚类算法

1. K-Means 定义

K-means聚类算法首先是随机选取K个对象作为初始的聚类中心，然后计算每个样本与各个聚类中心之间的距离，把每个样本分配给距离它最近的聚类中心。

聚类中心以及分配给它们的对象就代表一个聚类。每分配一次样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。

终止条件可以是没有（或最小数目）样本被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

2. K-Means 步骤

理论：
1 . 随机生成K个聚类中心。
2 .计算每个样本与每一个聚类中心的距离(欧式距离)，离哪个聚类中心近，就划分到哪个聚类中心所属的集合当中。
3 .重新计算每个集合的聚类中心。
4 .重复2，3步直到收敛。
5 .返回所有的聚类标签。

图解K-Means：

数据集采用的是make_blobs，

① 设置K=2，第一次随机划分了两个聚类，可以看出是非常不平衡的！还没有收敛~

② 计算每个样本与这两个聚类中心的距离(欧式距离)，离哪个聚类中心近，就划分到哪个聚类中心所属的集合当中。

• 如果这个样本点到两个聚类中的距离都是相等的话，就会随机分配到其中一类。
• 那么当这次聚类结束后，两个聚类会重新进行聚类中心点的计算，聚类中心就会改变。
• 那么下一次进行样本点和聚类中心点聚类计算的时候，这个样本点该划分到哪一类就会是哪一类。
• 也就是说这个随机是不影响最终的聚类结果的。

可以换个参考系想想，这两个聚类中心点不断在找自己的样本，就算中间过程中找错了，也不会影响最终的结果，他该有哪些样本点还是哪些样本点

③ 当划分完这一次所有样本点到各个聚类中心之后（即哪个样本点离哪个聚类中心近，就分到哪个聚类中心的集合），重新计算聚类中心的位置，即是黑色点的位置。

下图，红色点是没有计算的，就是上一次的聚类中心点，所以紫色的样本点都是距离右边的红点近的，黄色的样本点都是距离左边的红点近的，黑色点是重新计算后的

然后就通过这个重新计算后的黑色点，继续计算各个样本点到这个黑色点的距离，离左边的聚类中心近的就是黄色区域，离右边聚类中心点近的就是属于右边的一类。

可以看一下这一次聚类的过程： 一共迭代了15次才收敛

3. K-Means 和 KNN 对比

下面两张图来自B站Up五分钟机器学习

4. 小练习

4.1 第一题

Sklearn中的make_circles方法生成数据，用K-Means聚类并可视化。

"""
Sklearn中的make_circles方法生成数据，用K-Means聚类并可视化。
"""
from sklearn.cluster import KMeans
from sklearn.datasets import make_circles
import matplotlib.pyplot as plt
from ex1.clustering_performance import clusteringMetrics  # 导入的老师写的库

fig = plt.figure(1, figsize=(10, 5))
X1, y1 = make_circles(n_samples=400, factor=0.5, noise=0.1)
plt.subplot(121)
plt.title('original')
plt.scatter(X1[:, 0], X1[:, 1], c=y1)
plt.subplot(122)
plt.title('K-means')
kms = KMeans(n_clusters=2, max_iter=400)  # n_cluster聚类中心数 max_iter迭代次数
y1_sample = kms.fit_predict(X1, y1)  # 计算并预测样本类别
centroids = kms.cluster_centers_
plt.scatter(X1[:, 0], X1[:, 1], c=y1_sample)
plt.scatter(centroids[:, 0], centroids[:, 1], s=30, marker='*', c='b')

print(clusteringMetrics(y1, y1_sample))
plt.show()

4.2 第二题

Sklearn中的make_moons方法生成数据，用K-Means聚类并可视化。

"""
Sklearn中的make_moons方法生成数据，用K-Means聚类并可视化。
"""
import numpy as np
import matplotlib.pyplot as plt
import sklearn.datasets as datasets


def create_data():
    X, y = datasets.make_moons(n_samples=400, noise=0.1)
    return X, y

def init_centers(data, k):
    m, n = data.shape
    # m 样本个数，n特征个数
    center_ids = np.random.choice(m, k)
    centers = data[center_ids]
    return centers

def cal_dist(ptA, ptB):
    return np.linalg.norm(ptA - ptB)

def kmeans_process(data, k):
    centers = init_centers(data, k)
    m, n = data.shape
    keep_changing = True
    pred_y = np.zeros((m,))
    iteration = 0
    while keep_changing:
        keep_changing = False
        # 计算剩余样本所属类别
        for i in range(m):
            min_distance = np.inf
            for center in range(k):
                distance = cal_dist(data[i, :], centers[center, :])
                if distance < min_distance:  # 判断离哪个更近
                    min_distance = distance
                    idx = center  # 类别换下
            if pred_y[i] != idx:  # 判断是否发生了改变
                keep_changing = True
            pred_y[i] = idx
        # 更新类别中心点坐标
        for center in range(k):
            cluster_data = data[pred_y == center]
            centers[center, :] = np.mean(cluster_data, axis=0)  # 求相同类别数据点的质心点
        print(centers)
        plt.clf()
        plt.title(f'iteration: iteration')
        plt.scatter(X[:, 0], X[:, 1], s=30, c=pred_y)
        plt.scatter(centers[:, 0], centers[:, 1], s=100, c='k')
        plt.pause(1)
        iteration += 1
    return centers, pred_y

if __name__ == '__main__':
    X, y = create_data()
    plt.ion()
    centers, pred_y = kmeans_process(data=X, k=2)
    plt.ioff()
    plt.show()

4.3 第三题

给定的图像，对其像素进行聚类并可视化

from scipy.cluster.vq import *
from pylab import *
from PIL import Image


def clusterpixels(infile, k, steps):
    im = array(Image.open(infile))
    dx = im.shape[0] / steps
    dy = im.shape[1] / steps
    features = []

    for x in range(steps):  # RGB三色通道
        for y in range(steps):
            R = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 0])
            G = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 1])
            B = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 2])
            features.append([R, G, B])
    features = array(features, 'f')  # make into array
    # 聚类， k是聚类数目
    centroids, variance = kmeans(features, k)
    code, distance = vq(features, centroids)
    codeim = code.reshape(steps, steps)
    codeim = np.array(Image.fromarray(codeim).resize((im.shape[1], im.shape[0])))
    return codeim


# k = 5
infile_Stones = 'stones.jpg'
im_Stones = array(Image.open(infile_Stones))
steps = (50, 100)  # image is divided in steps*steps region

# 显示原图
figure()
subplot(231)
title('original')
axis('off')
imshow(im_Stones)

for k in range(2, 7):
    codeim = clusterpixels(infile_Stones, k, steps[-1])
    subplot(2, 3, k)
    title('K=' + str(k))
    axis('off')
    imshow(codeim)

show()

最后

小生凡一，期待你的关注。