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

阿里云2000元红包!本站用户参与享受九折优惠!


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、抽象出算法的数学模型

  • 问题描述

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/10.jpg”/></div>


  • 模型建立

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/11.jpg”/></div>


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

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/12.jpg”/></div>


3.4、迭代步骤

  • step1:在数据集里任意选择k 个对象,将每个数据对象代表初始聚类的中心;

  • step2:将剩下的数据划分到和数据本身相距最近的簇心的簇中;

  • step3:重复计算每个簇的均值得到新的簇心值;(簇均值向量迭代更新)

  • step4:重复step2以及step3指导满足收敛条件

算法流程图如下:

<div align=center><img width=45% height=20% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/13.jpg”/></div>


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()
  • 脚本输出结果图,首先是原始样本的散点图:

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/04.png”/></div>


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

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/01.png”/></div>


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

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

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/02.png”/></div>


  • 聚类结果导出(导出excel文件)

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/05.jpg”/></div>


五、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机器学习库实现的迭代结果图如下:

<div align=center><img width=80% height=80% src=”http://pw1af8xl1.bkt.clouddn.com/image/myblog/kmeans/03.png”/></div>


六、总结

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

https://www.jianshu.com/p/3eadac65a022

Python量化投资网携手4326手游为资深游戏玩家推荐:《《我的世界》细致到头发的建筑 大神600天造出“神级”城市

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论