聚类：k-means算法的手动实现

聚类算法概念

聚类算法属于无监督算法，即在没有人为划定标签的情况下对数据进行自动化的分类，使得每类数据的某种相似性尽可能大！

k-means算法的思路

k代表分k类，means是均值的意思，故也叫k均值算法。下面以分2类（k=2）的情况来白话说明该算法的思路。首先在数据集中随机取两个点，记为点a和点b；计算所有其他数据点到这2个点的距离；距离点a比较近的分为一组，距离点b比较近的分为二组；计算所分成的两组的每组的质心点（坐标的平均值；共2个），替代之前的那两个点作为新的参考点；不断重复之前操作使得误差不断减小即可。

k-means算法的实现流程

• 人为指定数据分k类，并随机在数据中取k个点（加入2个点）；—— 唯一需要人为指定的地方！下面进入循环中：
• 计算所有其他数据点，到这2个点的距离；距离点1比较近的分为一组，距离点2比较近的分为另一组；
• 计算分成两组的每组的质心点（共2个），替代之前的那2个点；
• 是否满足误差要求？or 是否循环到结尾了？

k值选取

• 首选：画图看数据点分布情况；二维x,y数据，画图能看出大概分几类；—— 但：高维/多元数据，无法画图！
• 实际任务已知要分几类，或要筛选掉误差/噪声数据；
• 不断尝试分不同类，看模型的误差评价值；—— 例如sklearn包中的metrics模块有多种量化评估的指标，选择在同一标准下看哪个模型（分几类的）的指标值最大/小，就应该选择分几类；

效果感觉

• 一定能按你的划分k组的要求，分出很合理的k类（不存在分错、点交错嵌套那种情况）。但是很有可能得到的分组不是你想要的！！你必须要多试几次才有可能得到你想要的类似情况 —— 因为：每次初始的随机点，对该次最后的分组情况影响很大。—— 因为：数据可以有多种方式的分组，横着分、竖着分、斜着分等都能分成一定数量的类（多解性）！
• 在线体验网站：k-means算法在线体验

致命缺点

• k-means是距离平均算法，因此它对数据的划分是很线性的！即对数据的划分方式就是横着分、竖着分、斜着分！假如数据是类似“多层圆环”的，即各种数据的“质心/圆心”都十分接近！—— 此情况用k-means永远做不到内圆数据是一组，外圆数据是一组这样的划分！后面会有例子进行展示；
• 不太明确的异常值，很难进行精细化聚类（相邻各组的边界数据，在每次重新分组后很有可能归属不同的组）！例如想剔除超过某个阈值的异常值。
• 每次运行程序，分组效果都有可能不同！（可能是整体上大尺度的不同，也可能是边界上的小不同），这种不稳定是无法避免的！—— 只因为：起始随机点的位置！后面按距离进行聚类都是确定的、没有随机的可能。

用途

• 最好的用途：剔除明显的、远离主体数据分布的噪声数据；
• 对数据进行随意分组：只求能正确分组即可，不求按照特别严格的分组要求。

程序实现

用sklearn实现 + 模型评估：

import pandas as pd 
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
mpl.rcParams['font.sans-serif'] = ['SimHei']

# 相当于两类数据：
data1 = pd.DataFrame( {'X':np.random.randint(1,50,100), 'Y':np.random.randint(1,50,100)} )
data2 = data1 + 50
data = pd.concat( [data1, data2] )  # 数据合并

# 画图显示：
plt.scatter(data.X, data.Y)

# 使用sklearn实现：
from sklearn.cluster import KMeans
cluster_predict = KMeans( n_clusters = 2 ).fit_predict(data)  # 分组：就只需这一步
print( cluster_predict )  # 打印分组后，给每个数据点的标定情况

# 画图显示分组后的情况：
# 绘图显示：
plt.scatter( data.X, data.Y, c = cluster_predict )  # c表示颜色，不同标签就有不同颜色

# 对当前分组情况的评价：
from sklearn import metrics  # 各种衡量标准
# 分2类的模型：
metrics.calinski_harabaz_score( data, cluster_predict ) # 值越大越好！

聚类前后效果.png

手动实现如下（换了一组数据）：

import numpy as np
import matplotlib.pyplot as plt

# 数据：我想分4组数据
x1 = np.random.uniform(0, 10, 20)
y1 = np.random.uniform(0, 10, 20)

x2 = np.random.uniform(10, 20, 20)
y2 = np.random.uniform(0, 10, 20)

x3 = np.random.uniform(10, 20, 20)
y3 = np.random.uniform(10, 20, 20)

x4 = np.random.uniform(0, 10, 20)
y4 = np.random.uniform(10, 20, 20)

x = np.concatenate( (x1,x2,x3,x4) )
y = np.concatenate( (y1,y2,y3,y4) )

plt.scatter(x,y)
plt.show()

# 数据初始化：
k = 4  # 分几份，自己决定
data_total = len(x)
# 一开始的k个随机点坐标：把x、y坐标分开记录
range_x = max(x) - min(x)
range_y = max(y) - min(y)
ax = []
ay = []
for i in range(k):
    atmp_x = np.random.uniform(0.001,1) * range_x  # 初始随机值对最后的划分：影响很大！ —— 需要多试几次！
    atmp_y = np.random.uniform(0.001,1) * range_y
    ax.append( atmp_x )
    ay.append( atmp_y )


# 1. 数组分组函数：每一次，对每个点归类：0, 1, 2, ..., k-1
def min_distance_index(each_ax, each_ay):
    clusterx = []
    clustery = []
    distance = np.zeros((k, data_total))

    # 记录“每个点”，到每个大哥点each_a的距离
    for each_a in range(k):
        x_a = np.power(x - each_ax[each_a], 2)  # X
        y_a = np.power(y - each_ay[each_a], 2)  # Y
        distance[each_a] = np.sqrt(x_a + y_a)  # 每行元素：都是数据点到i大哥点的“距离值”

    min_distance_index = np.argmin(distance, axis=0)  # 列最小值索引：每个点距离哪个“大哥点”最近
    for i in range(k):
        index = np.where(min_distance_index == i)  # 归类
        clusterx.append(x[index])
        clustery.append(y[index])

    return clusterx, clustery  # 数据已分组：每个变量里4个元素/分组，每个元素里又是数组


# 2. 每组质心求取函数：每组x、y坐标的均值
def mean_center(clusterx, clustery):
    # 记录每组质心点x、y坐标：
    newa_x = []
    newa_y = []
    # 对“每个组i”进行质心坐标x、y循环求取：
    for i in range(k):
        axtmp = np.mean(clusterx[i])
        aytmp = np.mean(clustery[i])
        newa_x.append(axtmp)
        newa_y.append(aytmp)

    return np.array(newa_x), np.array(newa_y)

# 主体部分：
for i in range(100):
    clusterx, clustery = min_distance_index(ax, ay)  # 分组后数据
    axtmp, aytmp = mean_center(clusterx, clustery)   # 新质心
    # 计算误差：axtmp与ax
    dx = np.power( axtmp - ax, 2 )
    dy = np.power( aytmp - ay, 2 )
    error = np.sum( np.sqrt( dx + dy ) )  # 一定会收敛！
    print('当前误差：', error)
    if error < 0.001:
        print('循环次数：', i, '精度要求已达标，提前结束！')
        break
    else:
        ax = axtmp
        ay = aytmp

# 画图显示：
for i in range(k):
    plt.scatter(clusterx[i], clustery[i])
plt.show()

程序下载地址：k-means程序下载

模型评价标准

说明：没有明确的、唯一的模型评价标准。大体上：每一类的数据越聚集越好！

• 量化方式1：该模型下（分了几类），每类之中的各点，到各类质心的距离的和（一个总值），值越小越好（每类中的数据更聚集）；
• 量化方式2：该模型下（分了几类），每类之外的所有点，到该类的质心的距离和（一个总值），值越大越好（不同类的数据更分散）！√（sklearn默认）

实际中：看需求数据、误差/噪声数据，这两大组有没有很好的分开！★★★
实际的操作可能是：先分2类看看某个量化标准的值是多少，然后分3类再看该指标，然后分4类，依此类推不断尝试各种分组方式，选择其中量化指标最好的那种分组。但是：还是要根据实际问题，量化指标仅仅是一种参考而已，不可迷信它！