十大机器学习算法之K-means聚类

2019.jpg

一、前言

博主准备系统的学习机器学习相关的基础算法，因此会持续的更新文章来记录学习过程。之所以写的第一篇机器学习文章是关于Kmeans算法，主要是因为博主接触到第一个机器学习算法就是Kmeans算法。而且在参加的一些竞赛中，经常用到过这个算法，但是从来没有自己编程实现这个算法，只是套用一些现成的库实现，这样是没有真正掌握一个算法的。

立个FLAG：以后相关的机器学习算法都要自己编程实现，然后和相关的库函数实现做一个对比。

二、实验环境

python3.6.4
IDE：Pycharm 2018
操作系统：windows10
实验源数据下载
依赖库：scipy，matplotlib， numpy，pandas，sklearn

三、K-means聚类的基本原理

3.1、分类与聚类

机器学习中有两类的大问题，一个是分类，一个是聚类。分类是根据一些给定的已知类别标号的样本，训练某种学习机器，使它能够对未知类别的样本进行分类。这属于supervised learning（监督学习）。

而聚类指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，这在机器学习中被称作 unsupervised learning （无监督学习）。在这篇文章中中，我们关注其中一个比较简单的聚类算法：k-means算法。k-means算法是聚类算法中比较简便，经典，有效的一种。

3.2、算法简介

通常，人们根据样本间的某种距离或者相似性来定义聚类，即把相似的（或距离近的）样本聚为同一类，而把不相似的（或距离远的）样本归在其他类。

K-means算法是非监督学习（unsupervised learning）中最简单也是最常用的一种聚类算法，具有的特点是:

对初始化敏感。初始点选择的不同，可能会产生不同的聚类结果
最终会收敛。不管初始点如何选择，最终都会收敛。（因此有可能收敛到局部最优解，聚类结果和直观观察差别很大）

3.3、抽象出算法的数学模型

问题描述

模型建立

EM算法求解模型，推导迭代公式

3.4、迭代步骤

step1：在数据集里任意选择k 个对象，将每个数据对象代表初始聚类的中心；
step2：将剩下的数据划分到和数据本身相距最近的簇心的簇中；
step3：重复计算每个簇的均值得到新的簇心值；（簇均值向量迭代更新）
step4：重复step2以及step3指导满足收敛条件

算法流程图如下：

K均值算法采用贪心策略，通过迭代优化来近似求解优化目标，根据上述流程，迭代一定次数就可以得到较好的聚类结果。

四、K-means算法的编程实现（python）

算法实现的脚本如下：


#!/usr/bin/env python

# -*- coding:utf-8 -*-

import scipy.io as sio # load mat

import matplotlib.pyplot as plt

# import seaborn as sns

import pandas as pd

import numpy as np

from sklearn.cluster import KMeans

# 这两句代码用来正确显示图中的中文字体，后续都要加上

plt.rcParams['font.sans-serif']=['SimHei'] #用来正常显示中文标签

plt.rcParams['axes.unicode_minus']=False #用来正常显示负号

#从本地导入聚类样本数据，并且绘制散点图

mat = sio.loadmat(r'C:\Users\13109\Desktop\机器学习\machine-learning-ex7\ex7\ex7data2.mat')

# print(mat.keys())

data = pd.DataFrame(mat.get('X'),columns=['x', 'y'])

# print(data)

data.plot.scatter(y='y',x='x',color='#44cef6')

plt.show()

'''

实现k-means聚类的脚本

'''

# 随机初始化k个中心(使用pandas的sample()方法)

# print(m),print(n)

def random_init(data, k):

    return data.sample(k).as_matrix() #as_matrix(): 转换成array

# 随机初始化k个中心(使用np花式索引方法)

def random_init(data,k):

    m,n = data.shape

    centroids = np.zeros((k,n))

    randindex = np.random.choice(m,k)

    centroids = data.values[randindex,:]

    return centroids

# print(random_init(data,3))

def Distance(A,B):

    return np.sqrt(np.sum(np.square(A-B)))

#为每一个数据集找到最近的质心，返回每个点的聚类结果

def find_cluster(data,centroids):

    k = centroids.shape[0]#聚类数

    m = data.shape[0]#样本量

    idx = np.zeros((m,1))#每个数据点的归类矩阵，初始0矩阵

    for i in range(m):

        mindist = np.inf

        minindex = -1

        for j in range(k):

            dist = Distance(data.values[i,:],centroids[j,:])

            if dist < mindist:

                mindist = dist

                minindex = j

        idx[i,:]=minindex

    return idx

# idx = find_cluster(data,random_init(data,3))

# print(idx)

#簇均值向量迭代更新

def change_centroids(data,idx,k):

    m,n = data.shape

    centroids = np.zeros((k,n))

    for i in range(k):

        index = np.where(idx ==i )[0]#索引到不同类对应的索引位置

        centroids[i] = np.mean(data.values[index],axis=0)

    return centroids

#定义损失函数(优化的目标)

def cost(data,centroids,idx):

    k = centroids.shape[0]  # 聚类数

    m,n=data.shape

    datacentroids = np.zeros((m,n))#获取每个点的中心簇坐标数组（初始化m*n的零矩阵）

    for i in range(m):

        for j in range(k):

            if idx[i] == j:

                datacentroids[i,:] = centroids[j,:]

    distance = np.square(data.values - datacentroids)

    return distance.sum()/m

#定义k均值聚类函数

def kmeans_1(data,k,max = 100):

    centroids = random_init(data,k)

    # 记录一下每个质心的变化

    cent0 = np.zeros((max, centroids.shape[1]))

    cent1 = np.zeros((max, centroids.shape[1]))

    cent2 = np.zeros((max, centroids.shape[1]))

    # 记录下每次迭代的损失

    cost_progress = []

    for i in range(max):#设置最大迭代次数

        idx = find_cluster(data,centroids)

        centroids = change_centroids(data,idx,k)

        cent0[i,:] = centroids[0,:]

        cent1[i,:] = centroids[1,:]

        cent2[i,:] = centroids[2,:]

        cost_progress.append(cost(data,centroids,idx))

        #设置迭代停止阈值

        if len(cost_progress)>1:

            if np.abs(cost_progress[-1]-cost_progress[-2])<0.001:

                break

    return idx,centroids,cent0,cent1,cent2,cost_progress[-1]

#肘部法则来确定k值的一种方法

# def elbow_rule(n):

#    idxlist = []

#    centroidslist = []

#    costlist = []

#    for k in range(2,n):

#        idx, centroids, cost = kmeans_1(data, k, max=100)

#        idxlist.append(idx)

#        centroidslist.append(centroids)

#        costlist.append(cost)

#    return costlist

# costlist = elbow_rule(10)

# print(costlist)

# plt.plot([i for i in range(2,10)], costlist, 'bo-', markersize=10)

# plt.xlabel('k值')

# plt.ylabel('代价函数')

# plt.show()

idx,centroids,cent0,cent1,cent2,cost_progress = kmeans_1(data,3,max=100)

idx0 = np.where(idx.ravel()==0)

idx1 = np.where(idx.ravel()==1)

idx2 = np.where(idx.ravel()==2)

plt.scatter(data.values[idx0,0],data.values[idx0,1],marker='x',color = 'r',label='第一类')

plt.scatter(data.values[idx1,0],data.values[idx1,1],marker='*',color = 'g',label='第二类')

plt.scatter(data.values[idx2,0],data.values[idx2,1],marker='+',color = 'y',label='第三类')

cent0 = cent0[cent0[:,0]>0]

cent1 = cent1[cent1[:,0]>0]

cent2 = cent2[cent2[:,0]>0]

plt.plot(cent0[:,0],cent0[:,1],"b-o")

plt.plot(cent1[:,0],cent1[:,1],"r-o")

plt.plot(cent2[:,0],cent2[:,1],"g-o")

plt.xlabel('X')

plt.ylabel('Y')

plt.legend()

plt.show()

脚本输出结果图，首先是原始样本的散点图：

肘部法则确定k值的折线图：

根据上图可以看出，当k=3是整体的代价函数下降幅度最大，从而确定出最优的聚类数为3

最终的聚类结果以及簇心迭代路线图；

聚类结果导出（导出excel文件）

五、K-means算法的scikit-learn库实现


#!/usr/bin/env python

# -*- coding:utf-8 -*-

import scipy.io as sio # load mat

import matplotlib.pyplot as plt

# import seaborn as sns

import pandas as pd

import numpy as np

from sklearn.cluster import KMeans

# 这两句代码用来正确显示图中的中文字体，后续都要加上

plt.rcParams['font.sans-serif']=['SimHei'] #用来正常显示中文标签

plt.rcParams['axes.unicode_minus']=False #用来正常显示负号

#从本地导入聚类样本数据，并且绘制散点图

mat = sio.loadmat(r'C:\Users\13109\Desktop\机器学习\machine-learning-ex7\ex7\ex7data2.mat')

# print(mat.keys())

data = pd.DataFrame(mat.get('X'),columns=['x', 'y'])

# print(data)

data.plot.scatter(y='y',x='x',color='#44cef6')

plt.show()

'''

使用scikit-learnj机器学习库  sklearn.cluster.KMeans

'''



# data中增加一列聚类标签

def combineData(data, C):

    dataC = data.copy()

    dataC['sk_kmeans.labels_'] = C

    return dataC

sk_kmeans = KMeans(n_clusters=3)

sk_kmeans.fit(data)

skdata = combineData(data,sk_kmeans.labels_)

fig, ax = plt.subplots()

# print(sk_kmeans.inertia_)

# print(sk_kmeans.cluster_centers_)

# print(sk_kmeans.labels_)

print(skdata),print(data)

ax.scatter(skdata['x'], skdata['y'], s=50, c=sk_kmeans.labels_, cmap='Accent', label='data')

ax.scatter(x=sk_kmeans.cluster_centers_[:,0],y=sk_kmeans.cluster_centers_[:,1], s=100, c=['r'], label='centroids')

ax.legend()

ax.set_xlabel('x')

ax.set_ylabel('y')

ax.annotate('第一类', xy=(2, 5), xytext=(2.3, 4.2),

            arrowprops=dict(facecolor='black', shrink=0.01))

ax.annotate('第二类', xy=(3, 1), xytext=(0.7, 1.8),

            arrowprops=dict(facecolor='black', shrink=0.01))

ax.annotate('第三类', xy=(6, 3), xytext=(6.3, 1.6),

            arrowprops=dict(facecolor='black', shrink=0.01))

plt.show()

使用scikit-learnj机器学习库实现的迭代结果图如下：

十大机器学习算法之K-means聚类

十大机器学习算法之K-means聚类

一、前言

二、实验环境

三、K-means聚类的基本原理

3.1、分类与聚类

3.2、算法简介

3.3、抽象出算法的数学模型

3.4、迭代步骤

四、K-means算法的编程实现（python）

五、K-means算法的scikit-learn库实现

六、总结

七、参考文章链接和推荐的教程