机器学习之聚类算法（三）KMeans、KMeans++、KMeans||原理介绍及代码实现

K均值聚类（K-means）介绍

历史渊源

虽然其思想能够追溯到1957年的Hugo Steinhaus，术语“k-均值”于1967年才被James MacQueen首次使用。标准算法则是在1957年被Stuart Lloyd作为一种脉冲码调制的技术所提出，但直到1982年才被贝尔实验室公开出版。在1965年，E.W.Forgy发表了本质上相同的方法，所以这一算法有时被称为Lloyd-Forgy方法。更高效的版本则被Hartigan and Wong提出（1975/1979）

介绍

K-Means算法是无监督的聚类算法，算法简单，聚类效果好，即使是在巨大的数据集上也非常容易部署实施。正因为如此，它在很多领域都得到的成功的应用，如市场划分、机器视觉、 地质统计学、天文学和农业等。K-Means算法有大量的变体，包括初始化优化K-Means++以及大数据应用背景下的k-means||和Mini Batch K-Means

实现思想及数学公式

实现思想

• K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
• 优化目标是：使样本点到聚类中心的距离最小化

数学公式

• 计算样本点到聚类中心的距离：
  距离 = （求和（样本点矩阵 - 聚类中心坐标）**2）^1/2
• 重新规划聚类中心：
  聚类中心坐标 = 所有样本点对应相加 / 样本点个数

KMeans代码实现

import numpy as np
# 数据
X = np.array([[1, 2], [2, 2], [6, 8], [7, 8]])
# 随机初始化的聚类中心
C = np.array([[1.0, 2.0], [2.0, 2.0]])

n = 5
for i in range(n):
    # 求每个聚类中心到每个样本的距离
    DIS = []
    for c in C:
        dis = np.sqrt(np.sum((X - c)**2,axis=1))
        DIS.append(dis)
    # 将样本归类
    DIS= np.array(DIS)
    min_index = np.argmin(DIS,axis=0)
    # 重新计算 样本中心
    for l in range(len(C)):
        x = X[min_index == l]
        C[l] = np.mean(x,axis=0)
print(C)

优化KMeans之KMeans++

KMeans的缺点

• 聚类中心的个数K需要事先给定，但在实际中K值的选定是非常困难的，很多时候我们并不知道给定的数据集应该聚成多少个类别才最合适
• k-means算法需要随机地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果，有可能导致算法收敛很慢甚至出现聚类出错的情况
• 针对第一个缺点：很难在k-means算法以及其改进算法中解决，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过“肘方法”选择一个合适的k值
• 针对第二个缺点：可以通过k-means++算法来解决

KMeans++确定质心的步骤

• 第一步：从数据集中随机选择一个样本作为初始聚类中心
• 第二步：计算每个样本到最近聚类中心的距离
• 第三步：每一个样本都有一个长度，长度越大的样本，被选为下一个聚类中心的概率越高。
• 重复二三，直到得到预设的K个初始质心

第三步的代码实现（一）

import random
import pandas as pd
import math
a = [['H',70],['I',500],['J',600],['K',700],['L',800],['M',900],['N',1000],["A",10],["B",20],["C",30],["D",40],['F',50],['G',60]]
# 第二个元素越大，采到的概率越大，请采样1w次，然后统计频率
a.sort(key=lambda x:x[1])
a_sum = sum(i[1] for i in a)

n = []
# 计算每个样本距离占据总距离的百分比，用于后续权重处理
for i in a:
    n.append(math.ceil(i[1]/a_sum * 100))

x = []
# 距离越远，添加次数越多，被随机选到的概率越大
for i in range(len(a)):
    for s in range(n[i]):
        x.append(a[i])

p = []
for i in range(10000):
    p.append(x[random.randint(0,len(x)-1)])

df = pd.DataFrame(p)
df1 = df.groupby(by=[0]).count()
print(df1)
'''
# 效果如下
[1, 1, 1, 1, 2, 2, 2, 11, 13, 15, 17, 19, 21]
      1
0      
A    89
B    99
C    91
D   106
F   188
G   190
H   191
I  1056
J  1198
K  1446
L  1576
M  1807
N  1963
'''

第三步的代码实现（二）

import random
import pandas as pd
'''
	利用随机打点发，0-1的随机数乘以距离总和，打一个点，循环累加样本点的距离，直到距离大于打点距离
	输出当前的样本点，为聚类中心点。
'''
a = [['H',70],['I',500],['J',600],['K',700],['L',800],['M',900],['N',1000],["A",10],["B",20],["C",30],["D",40],['F',50],['G',60]]
# 第二个元素越大，采到的概率越大，请采样1w次，然后统计频率

A = []
for j in range(10000):
    point = random.random()*sum([i[-1] for i in a])
    res = 0
    for i in a:
        res += i[-1]
        if res>point:
            A.append(i[0])
            break
A = pd.Series(A)
print(A.value_counts())
'''
# 效果如下
N    2082
M    1920
L    1629
K    1450
J    1201
I    1112
H     139
G     130
F     116
D     104
C      55
B      39
A      23
'''

优化KMeans++之KMeans||

KMeans++的缺点

• 在初始化质心的过程中，他是一个有序的过程，并且他每一轮只增加一个聚类中心，当k和样本量比较大的时候，计算量很大，导致初始过程很慢。

KMeans||优化步骤

• 确定k值，假设是3000
• 第一步：先从数据集中随机抽取一个样本作为一个质心
• 第二步：计算每个样本到最近聚类中心的距离，依照距离抽取1000个质心
• 循环第二步5次，得到5000个聚类中心，这是一个候选聚类中心集合
• 第三步：计算这5000个候选聚类中心的密度，如果其附近的样本点较多，则给一个较大的值w
• 第四步：使用考虑了密度因素的KMeans++算法，从5000个点中选出3000个点
• 初始化工作完毕，执行KMeans算法

上述三种Kmeans算法的性能对比

Kmeans超参数