机器学习 — K-Means、K-Means++ 原理及算法实现

文章目录

  • 机器学习 — K-Means、K-Means++ 原理及算法实现
    • 一、K-Means
      • 1. 概念
      • 2. K-Means算法思想
      • 3. K-Means特点
      • 4.K-Means算法实现
    • 二、K-Means++
      • 1.概念
      • 2.K-Means++算法思想
      • 3.K-Means++特点
      • 4.K-Means++算法实现
    • 三、总结

机器学习 — K-Means、K-Means++ 原理及算法实现

一、K-Means

1. 概念

  • k-means algorithm算法:
    K-均值(K-Means)属于聚类算法,之所以称为K-均值是因为它把n个样本根据它们的属性分为k个簇(k < n),且每个簇的中心采用簇中所含值的均值计算而成。

  • 聚类:
    一种无监督的学习,事先不知道类别,自动将相似的对象归到同一簇中。
    聚类作为一种典型的数据挖掘方法,一直以来都是人工智能领域的一个研究热点,被广泛地应用于人脸图像识别、股票分析预测、搜索引擎、生物信息学等领域中。

2. K-Means算法思想

  1. 随机选择K个中心值
  2. 根据样本数据各点与中心点的距离来进行归簇
  3. 通过各个簇的均值,更新为每个簇的中心值
  4. 重复2、3,直至聚类中心的位置不再变化
    机器学习 — K-Means、K-Means++ 原理及算法实现_第1张图片

3. K-Means特点

  • 适用数据类型:适用于数值型数据

  • 优点:算法原理简单,容易实现。需要调节的超参数就是一个k。

  • 缺点:
    在 K-Means算法中 K需要事先确定,这个 K 值的选定有时候是比较难确定。
    可能收敛到局部最小值;
    在大规模数据集上收敛速度较慢;

4.K-Means算法实现

#!/usr/bin/env python
# encoding: utf-8
'''
@Author  : pentiumCM
@Email   : 842679178@qq.com
@Software: PyCharm
@File    : kmeans.py
@Time    : 2019/12/22 21:42
@desc	 : numpy原生实现
'''

import numpy as np
import matplotlib.pyplot as plt

def load_data_set(fileName):
    '''
    加载测试数据集,返回一个列表,列表的元素是一个坐标
    '''
    dataList = []
    with open(fileName) as fr:
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float, curLine))
            dataList.append(fltLine)
    return dataList


def randCent(dataSet, k):
    '''
    1.随机生成k个初始的聚类中心
    '''
    n = np.shape(dataSet)[1]  # n表示数据集的维度
    centroids = np.mat(np.zeros((k, n)))
    for j in range(n):
        minJ = min(dataSet[:, j])
        rangeJ = float(max(dataSet[:, j]) - minJ)
        centroids[:, j] = np.mat(minJ + rangeJ * np.random.rand(k, 1))
    return centroids


def kMeans(dataSet, k):
    '''
    2.KMeans算法,返回最终的质心坐标和每个点所在的簇已经算法的迭代次数
    '''
    m = np.shape(dataSet)[0]  # m表示数据集的长度(个数)
    clusterAssment = np.mat(np.zeros((m, 2)))

    centroids = randCent(dataSet, k)  # 保存k个初始质心的坐标
    clusterChanged = True
    iterIndex = 1  # 迭代次数
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            minDist = np.inf
            minIndex = -1
            for j in range(k):
                distJI = np.linalg.norm(
                    np.array(centroids[j, :]) - np.array(dataSet[i, :]))
                if distJI < minDist:
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist ** 2
            print(
                "第%d次迭代后%d个质心的坐标:\n%s" %
                (iterIndex, k, centroids))  # 第一次迭代的质心坐标就是初始的质心坐标
            iterIndex += 1
        for cent in range(k):
            ptsInClust = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[
                0]]  # get all the point in this cluster
            centroids[cent, :] = np.mean(ptsInClust, axis=0)
    iters = (iterIndex - 1) / dataSet.shape[0]
    return centroids, clusterAssment, iters


def showCluster(dataSet, k, centroids, clusterAssment, iters):
    '''
    数据可视化,只能画二维的图(若是三维的坐标图则直接返回1)
    '''
    numSamples, dim = dataSet.shape
    if dim != 2:
        return 1

    mark = ['or', 'ob', 'og', 'ok', 'oy', 'om', 'oc', '^r', '+r', 'sr', 'dr', ', 'pr']

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    mark = ['Pr', 'Pb', 'Pg', 'Pk', 'Py', 'Pm', 'Pc', '^b', '+b', 'sb', 'db', ', 'pb']
    # draw the centroids
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=12)

    plt.title('Number of Iterations: %d' % (iters))
    plt.show()


if __name__ == '__main__':
    # 加载数据集
    dataMat = np.mat(load_data_set('./testSet'))  # mat是numpy中的函数,将列表转化成矩阵

    k = 4  # 选定k值,也就是簇的个数(可以指定为其他数)
    cent, clust, iters = kMeans(dataMat, k)

    # 数据可视化处理
    showCluster(dataMat, k, cent, clust, iters)
    

算法运行结果:
机器学习 — K-Means、K-Means++ 原理及算法实现_第2张图片

二、K-Means++

1.概念

  • k-means++ algorithm算法:
    由于 K-means 算法的分类结果会受到初始点的选取而有所区别,因此有提出这种算法的改进: K-Means++ 。

2.K-Means++算法思想

其实这个算法是对初始点的选择有改进,其他步骤都一样。初始质心选取的基本思路就是,初始的聚类中心之间的相互距离要尽可能的远。

  1. 随机选取一个样本作为第一个聚类中心 c1;
  2. 计算每个样本与当前已有类聚中心最短距离(即与最近一个聚类中心的距离),用 D(x)表示;
    这个值越大,表示被选取作为聚类中心的概率较大;
    最后,用轮盘法选出下一个聚类中心ci;
  3. 重复步骤2,直到选出 k 个聚类中心。
    机器学习 — K-Means、K-Means++ 原理及算法实现_第3张图片

3.K-Means++特点

  • 适用数据类型:适用于数值型数据
  • 优点:
    可以确定地初始化聚类中心。
    减少算法的迭代次数,提高算法的收敛速度
  • 缺点:
    K-Means++算法从可扩展性来看,它存在一个缺点,那就是它内在的有序性特性:下一个中心点的选择依赖于已经选择的中心点。

4.K-Means++算法实现

#!/usr/bin/env python
# encoding: utf-8
'''
@Author  : pentiumCM
@Email   : 842679178@qq.com
@Software: PyCharm
@File    : kmeans++.py
@Time    : 2019/12/23 15:09
@desc	 : numpy原生实现K-Means++
'''

import math
import random
import numpy as np
import matplotlib.pyplot as plt


def loadDataSet(fileName):
    '''
    加载测试数据集,返回一个列表,列表的元素是一个坐标
    '''
    dataList = []
    with open(fileName) as fr:
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float, curLine))
            dataList.append(fltLine)
    return dataList


def euler_distance(point1: list, point2: list) -> float:
    """
    计算两点之间的欧拉距离,支持多维
    """
    distance = 0.0
    for a, b in zip(point1, point2):
        distance += math.pow(a - b, 2)
    return math.sqrt(distance)


def get_closest_dist(point, centroids):
    min_dist = math.inf  # 初始设为无穷大
    for i, centroid in enumerate(centroids):
        dist = euler_distance(centroid, point)
        if dist < min_dist:
            min_dist = dist
    return min_dist


def kpp_centers(data_set, k):
    """
    1.从数据集中返回 k 个对象可作为质心
    """

    # 将矩阵转为列表
    data_set = np.matrix.tolist(data_set)

    cluster_centers = []
    cluster_centers.append(random.choice(data_set))
    d = [0 for _ in range(len(data_set))]
    for _ in range(1, k):
        total = 0.0
        for i, point in enumerate(data_set):
            d[i] = get_closest_dist(point, cluster_centers)  # 与最近一个聚类中心的距离
            total += d[i]
        total *= random.random()
        for i, di in enumerate(d):  # 轮盘法选出下一个聚类中心;
            total -= di
            if total > 0:
                continue
            cluster_centers.append(data_set[i])
            break

    cluster_centers = np.mat(cluster_centers)
    return cluster_centers


def kMeans(dataSet, k):
    '''
    2.KMeans算法,返回最终的质心坐标和每个点所在的簇
    '''
    m = np.shape(dataSet)[0]  # m表示数据集的长度(个数)
    clusterAssment = np.mat(np.zeros((m, 2)))

    centroids = kpp_centers(dataSet, k)  # 保存k个初始质心的坐标
    clusterChanged = True
    iterIndex = 1  # 迭代次数
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            minDist = np.inf;
            minIndex = -1
            for j in range(k):
                distJI = np.linalg.norm(np.array(centroids[j, :]) - np.array(dataSet[i, :]))
                if distJI < minDist:
                    minDist = distJI;
                    minIndex = j
            if clusterAssment[i, 0] != minIndex: clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist ** 2
            print("第%d次迭代后%d个质心的坐标:\n%s" % (iterIndex, k, centroids))  # 第一次迭代的质心坐标就是初始的质心坐标
            iterIndex += 1
        for cent in range(k):
            ptsInClust = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[0]]  # get all the point in this cluster
            centroids[cent, :] = np.mean(ptsInClust, axis=0)
    iter = (iterIndex - 1) / dataSet.shape[0]
    return centroids, clusterAssment, iter


def showCluster(dataSet, k, centroids, clusterAssment, iters):
    '''
    数据可视化,只能画二维的图(若是三维的坐标图则直接返回1)
    '''
    numSamples, dim = dataSet.shape
    if dim != 2:
        return 1

    mark = ['or', 'ob', 'og', 'ok', 'oy', 'om', 'oc', '^r', '+r', 'sr', 'dr', ', 'pr']

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    mark = ['Pr', 'Pb', 'Pg', 'Pk', 'Py', 'Pm', 'Pc', '^b', '+b', 'sb', 'db', ', 'pb']
    # draw the centroids
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=12)

    plt.title('Number of Iterations: %d' % (iters))
    plt.show()


if __name__ == '__main__':
    # 加载数据集
    dataMat = np.mat(loadDataSet('./testSet'))  # mat是numpy中的函数,将列表转化成矩阵

    k = 4  # 选定k值,也就是簇的个数(可以指定为其他数)
    cent, clust, iters = kMeans(dataMat, k)

    # 数据可视化处理
    showCluster(dataMat, k, cent, clust, iters)

算法运行结果:
机器学习 — K-Means、K-Means++ 原理及算法实现_第4张图片

三、总结

本次实验都是采用同样的数据集上来进行仿真实验。
由上面两个算法的聚类结果来看,两者是吻合的。从迭代次数上来看,K-Means++的迭代次数明显是少于K-Means算法的。

附录:
两个算法所对应的数据集是都是:testSet

你可能感兴趣的