机器学习之K-Means算法

一、聚类算法的简介

  聚类算法是一种典型的无监督学习算法，主要用于将相似的样本自动归到一个类别中。聚类算法与分类算法最大的区别是：聚类算法是无监督的学习算法，而分类算法属于监督的学习算法。

  在聚类算法中根据样本之间的相似性，将样本划分到不同的类别中，对于不同的相似度计算方法，会得到不同的聚类结果，常用的相似度计算方法有欧式距离法。

二、K-Means算法的概述

  K-Means聚类的目的是将n个观测值划分为k个类，使每个类中的观测值距离该类的中心（类均值）比距离其他类中心都近。
  事先确定常数k，常数k意味着最终的聚类类别数，首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度(这里为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质心(即为类中心)，重复这样的过程，知道质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。
  由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-Means算法的收敛速度比较慢。

三、K-Means算法的流程

1、初始化常数K，随机选取初始点为质心
2、重复计算一下过程，直到质心不再改变
 （1）计算样本与每个质心之间的相似度，将样本归类到最相似的类中
 （2）重新计算质心
3、输出最终的质心以及每个类

四、K-Means算法的实现

1、K-Means算法实现代码如下：

import numpy as np
import matplotlib.pyplot as plt

'''
算法思想大致为：先从样本集中随机选取 𝑘 个样本作为簇中心，并计算所有样本与这 𝑘 个“簇中心”的距离，对于每一个样本，
将其划分到与其距离最近的“簇中心”所在的簇中，对于新的簇计算各个簇的新的“簇中心”。
根据以上描述，我们大致可以猜测到实现kmeans算法的主要三点：
（1）簇个数 𝑘 的选择
（2）各个样本点到“簇中心”的距离
（3）根据新划分的簇，更新“簇中心”
'''

def loadDataSet(filename):
    '''
    读取数据集

    Args:
        filename: 文件名
    Returns:
        dataMat: 数据样本矩阵
    '''
    dataMat = []
    with open(filename, 'rb') as f:
        for line in f:
            # 读取的字节流需要先解码成utf-8再处理
            eles = list(map(float, line.decode('utf-8').strip().split('\t')))
            dataMat.append(eles)
    return dataMat

def distEclud(vecA, vecB):
    '''
    计算两向量的欧氏距离

    Args:
        vecA: 向量A
        vecB: 向量B
    Returns:
        欧式距离
    '''
    return np.sqrt(np.sum(np.power(vecA-vecB,2)))

def randCent(dataSet, k):
    '''
    随机生成k个聚类中心

    Args:
        dataSet: 数据集
        k: 簇数目
    Returns:
        centroids: 聚类中心矩阵
    '''
    m, _ = dataSet.shape
    # 随机从数据集中选几个作为初始聚类中心
    centroids = dataSet.take(np.random.choice(80,k), axis=0)
    return centroids


def kMeans(dataSet, k, maxIter=5):
    '''
    K-Means

    Args:
        dataSet: 数据集
        k: 聚类数
    Returns:
        centroids: 聚类中心
        clusterAssment: 点分配结果
    '''
    # 随机初始化聚类中心
    centroids = randCent(dataSet, k)
    init_centroids = centroids.copy()

    m, n = dataSet.shape

    # 点分配结果：第一列指明样本所在的簇，第二列指明该样本到聚类中心的距离
    clusterAssment = np.mat(np.zeros((m, 2)))

    # 标识聚类中心是否仍在变化
    clusterChanged = True

    # 直至聚类中心不再变化
    iterCount = 0
    while clusterChanged and iterCount < maxIter:
        iterCount += 1
        clusterChanged = False
        # 分配样本到簇
        for i in range(m):
            # 计算第i个样本到各个聚类中心的距离
            minIndex = 0
            minDist = np.inf
            for j in range(k):
                dist = distEclud(dataSet[i, :], centroids[j, :])
                if dist < minDist:
                    minIndex = j
                    minDist = dist
            # 任何一个样本的类簇分配发生变化则认为变化
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist ** 2

        # 刷新聚类中心：移动聚类中心点到所有簇的均值位置
        for cent in range(k):
            # 通过数组过滤得到簇中的点
            # matrix.A 是将matrix-->array
            ptsInCluster = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[0]]
            if ptsInCluster.shape[0] > 0:
                # 计算均值并移动
                centroids[cent, :] = np.mean(ptsInCluster, axis=0)
    return centroids, clusterAssment, init_centroids

if __name__ == '__main__':
    dataMat = np.mat(loadDataSet('./testSet.txt'))
    m, n = np.shape(dataMat)
    set_k = 4
    centroids, clusterAssment, init_centroids = kMeans(dataMat, set_k)

    clusterCount = np.shape(centroids)[0]

    # 我们这里只设定了最多四个簇的样式，所以前面如果set_k设置超过了4，后面就会出现index error
    patterns = ['o', 'D', '^', 's']
    colors = ['b', 'g', 'y', 'black']

    fig = plt.figure()
    title = 'kmeans with k={}'.format(set_k)
    ax = fig.add_subplot(111, title=title)
    for k in range(clusterCount):
        # 绘制聚类中心
        ax.scatter(centroids[k, 0], centroids[k, 1], color='r', marker='+', linewidth=20)
        # 绘制初始聚类中心
        ax.scatter(init_centroids[k, 0], init_centroids[k, 1], color='purple', marker='*', linewidth=10)
        for i in range(m):
            # 绘制属于该聚类中心的样本
            ptsInCluster = dataMat[np.nonzero(clusterAssment[:, 0].A == k)[0]]
            ax.scatter(ptsInCluster[:, 0].flatten().A[0], ptsInCluster[:, 1].flatten().A[0], color=colors[k],
                       marker=patterns[k])

    plt.show()

效果图.png

2、sklearn中K-Means算法实现代码如下：

from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt

def loadDataSet(filename):
    '''
    读取数据集

    Args:
        filename: 文件名
    Returns:
        dataMat: 数据样本矩阵
    '''
    dataMat = []
    with open(filename, 'rb') as f:
        for line in f:
            # 读取的字节流需要先解码成utf-8再处理
            eles = list(map(float, line.decode('utf-8').strip().split('\t')))
            dataMat.append(eles)
    return dataMat

dataMat = np.mat(loadDataSet('./testSet.txt'))
kmeans = KMeans(init='random', n_clusters=4, random_state=0).fit(dataMat)
centroids = kmeans.cluster_centers_
clusterAssment = kmeans.labels_

m, n = np.shape(dataMat)
set_k = 4
clusterCount = np.shape(centroids)[0]

# 我们这里只设定了最多四个簇的样式，所以前面如果set_k设置超过了4，后面就会出现index error
patterns = ['o', 'D', '^', 's']
colors = ['b', 'g', 'y', 'black']


fig = plt.figure()
title = 'kmeans with k={}'.format(set_k)
ax = fig.add_subplot(111, title=title)
for k in range(clusterCount):
    # 绘制聚类中心
    ax.scatter(centroids[k, 0], centroids[k, 1], color='r', marker='+', linewidth=20)

    for i in range(m):
        # 绘制属于该聚类中心的样本
        ptsInCluster = dataMat[np.nonzero(clusterAssment == k)[0]]
        ax.scatter(ptsInCluster[:, 0].flatten().A[0], ptsInCluster[:, 1].flatten().A[0], color=colors[k],
                   marker=patterns[k])

plt.show()

分类效果图.png