1 简介
K-means称为K-平均算法，简单来讲K-平均聚类算法的目的就是：
把 n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离它最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。
已知观测集 (x1,x2,...,xn)，其中每个观测都是一个 d-维实向量，k-平均聚类要把这 n个观测划分到k个集合中(k≤n),使得组内平方和（WCSS within-cluster sum of squares）最小。换句话说，它的目标是找到使得下式满足的聚类 Si，
其中 μi是 Si中所有点的均值。
2 算法流程
步骤1 分配（Assignment）
将每个观测分配到聚类中，使得组内平方和（WCSS）达到最小。
因为这一平方和就是平方后的欧氏距离，所以很直观地把观测分配到离它最近得均值点即可 。
步骤2 更新（Update）
对于上一步得到的每一个聚类，以聚类中观测值的图心，作为新的均值点。
这一算法经常被描述为“把观测按照距离分配到最近的聚类”。标准算法的目标函数是组内平方和（WCSS），而且按照“最小二乘和”来分配观测，确实是等价于按照最小欧氏距离来分配观测的。如果使用不同的距离函数来代替（平方）欧氏距离，可能使得算法无法收敛。然而，使用不同的距离函数，也能得到k-均值聚类的其他变体，如球体k-均值算法和k-中心点算法。
3 代码实例
# !/usr/bin/env python3 # -*- coding:utf-8 _*- """ @Author:yanqiang @File: k-means.py @Time: 2019/1/17 14:08 @Software: PyCharm @Description: """ # 导入库 import numpy as np import pandas as pd import matplotlib.pyplot as plt # 步骤1：初始化 df = pd.DataFrame({ 'x': [12, 20, 28, 18, 29, 33, 24, 45, 45, 52, 51, 52, 55, 53, 55, 61, 64, 69, 72], 'y': [39, 36, 30, 52, 54, 46, 55, 59, 63, 70, 66, 63, 58, 23, 14, 8, 19, 7, 24] }) np.random.seed(300) # 随机初始化三个聚类中心 k = 3 centroids = {i + 1: [np.random.randint(0, 80), np.random.randint(0, 80)] for i in range(k)} # centroids[i] = [x, y] fig = plt.figure(figsize=(5, 5)) plt.scatter(df['x'], df['y'], color='k') colors = {1: 'b', 2: 'r', 3: 'g'} for i in centroids.keys(): plt.scatter(*centroids[i], color=colors[i]) plt.xlim(0, 80) plt.ylim(0, 80) plt.show() # 画图
初始化
# 步骤2：Assignment 分配 # 将点归类到与聚类中心距离最短的类别 def assignment(df, centroids): for i in centroids.keys(): # sqrt((x1-x2)^2+(y1-y2)^2) df['distance_from_{}'.format(i)] = ( np.sqrt( (df['x'] - centroids[i][0]) ** 2 + (df['y'] - centroids[i][1]) ** 2 ) ) centroids_distance_cols = ['distance_from_{}'.format(i) for i in centroids.keys()] df['closest'] = df.loc[:, centroids_distance_cols].idxmin(axis=1) # ? df['closest'] = df['closest'].map(lambda x: int(x.lstrip('distance_from_'))) df['color'] = df['closest'].map(lambda x: colors[x]) return df df = assignment(df, centroids) print(df.head()) fig = plt.figure(figsize=(5, 5)) plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolors='k') for i in centroids.keys(): plt.scatter(*centroids[i], color=colors[i]) plt.xlim(0, 80) plt.ylim(0, 80) plt.show()
将点归类到与聚类中心距离最短的类别
# 步骤3 ：Update 更新 # 重新计算每个聚类的质心 import copy old_centroids = copy.deepcopy(centroids) def update(k): for i in centroids.keys(): centroids[i][0] = np.mean(df[df['closest'] == i]['x']) centroids[i][1] = np.mean(df[df['closest'] == i]['y']) return k centroids = update(centroids) fig = plt.figure(figsize=(5, 5)) ax = plt.axes() plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='k') for i in centroids.keys(): plt.scatter(*centroids[i], color=colors[i]) plt.xlim(0, 80) plt.ylim(0, 80) for i in old_centroids.keys(): old_x = old_centroids[i][0] old_y = old_centroids[i][1] dx = (centroids[i][0] - old_centroids[i][0]) * 0.75 dy = (centroids[i][1] - old_centroids[i][1]) * 0.75 ax.arrow(old_x, old_y, dx, dy, head_width=2, head_length=3, fc=colors[i], ec=colors[i]) plt.show()
更新聚类中心
# 步骤4 重新分配 Repeat Assigment # 重新将点归类到与新聚类中心距离最短的类别 df = assignment(df, centroids) # 画图 fig = plt.figure(figsize=(5, 5)) plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='k') for i in centroids.keys(): plt.scatter(*centroids[i], color=colors[i]) plt.xlim(0, 80) plt.ylim(0, 80) plt.show()
更新聚类中心之后的聚类分布
# 步骤5 一直重复上面的步骤，直到每个的点所属的聚类中心不再更新 while True: closest_centroids = df['closest'].copy(deep=True) centroids = update(centroids) df = assignment(df, centroids) if closest_centroids.equals(df['closest']): df.to_csv('cal_process.csv') break fig = plt.figure(figsize=(5, 5)) plt.scatter(df['x'], df['y'], color=df['color'], alpha=0.5, edgecolor='k') for i in centroids.keys(): plt.scatter(*centroids[i], color=colors[i]) plt.xlim(0, 80) plt.ylim(0, 80) plt.show()
最终聚类效果
我们将df导出之后可以看到，每个点的所属分类
具体分类
