100天搞定机器学习|day44 k均值聚类数学推导与python实现

简介: 100天搞定机器学习|day44 k均值聚类数学推导与python实现


前文推荐

如何正确使用「K均值聚类」?


1、k均值聚类模型

a

给定样本image.png,每个样本都是m为特征向量,模型目标是将n个样本分到k个不停的类或簇中,每个样本到其所属类的中心的距离最小,每个样本只能属于一个类。用C表示划分,他是一个多对一的函数,k均值聚类就是一个从样本到类的函数。


2、k均值聚类策略

k均值聚类的策略是通过损失函数最小化选取最优的划分或函数image.png

首先,计算样本之间的距离,这里选欧氏距离平方。


$$

image.png


然后定义样本与其所属类的中心之间的距离的总和为损失函数

image.png

image.png


3、k均值聚类算法


k均值聚类的算法是一个迭代过程,


首先:


image.png


重复以上两个步骤,知道分化不在改变。


from myUtil import *
def kMeans(dataSet, k):
    m = shape(dataSet)[0]  # 返回矩阵的行数
    # 本算法核心数据结构:行数与数据集相同
    # 列1:数据集对应的聚类中心,列2:数据集行向量到聚类中心的距离
    ClustDist = mat(zeros((m, 2)))
    # 随机生成一个数据集的聚类中心:本例为4*2的矩阵
    # 确保该聚类中心位于min(dataSet[:,j]),max(dataSet[:,j])之间
    clustercents = randCenters(dataSet, k)  # 随机生成聚类中心
    flag = True  # 初始化标志位,迭代开始
    counter = []  # 计数器
    # 循环迭代直至终止条件为False
    # 算法停止的条件:dataSet的所有向量都能找到某个聚类中心,到此中心的距离均小于其他k-1个中心的距离
    while flag:
        flag = False  # 预置标志位为False
        # ---- 1. 构建ClustDist:遍历DataSet数据集,计算DataSet每行与聚类的最小欧式距离 ----#
        # 将此结果赋值ClustDist=[minIndex,minDist]
        for i in xrange(m):
            # 遍历k个聚类中心,获取最短距离
            distlist = [distEclud(clustercents[j, :], dataSet[i, :]) for j in range(k)]
            minDist = min(distlist)
            minIndex = distlist.index(minDist)
            if ClustDist[i, 0] != minIndex:  # 找到了一个新聚类中心
                flag = True  # 重置标志位为True,继续迭代
            # 将minIndex和minDist**2赋予ClustDist第i行
            # 含义是数据集i行对应的聚类中心为minIndex,最短距离为minDist
            ClustDist[i, :] = minIndex, minDist
        # ---- 2.如果执行到此处,说明还有需要更新clustercents值: 循环变量为cent(0~k-1)----#
        # 1.用聚类中心cent切分为ClustDist,返回dataSet的行索引
        # 并以此从dataSet中提取对应的行向量构成新的ptsInClust
        # 计算分隔后ptsInClust各列的均值,以此更新聚类中心clustercents的各项值
        for cent in xrange(k):
            # 从ClustDist的第一列中筛选出等于cent值的行下标
            dInx = nonzero(ClustDist[:, 0].A == cent)[0]
            # 从dataSet中提取行下标==dInx构成一个新数据集
            ptsInClust = dataSet[dInx]
            # 计算ptsInClust各列的均值: mean(ptsInClust, axis=0):axis=0 按列计算
            clustercents[cent, :] = mean(ptsInClust, axis=0)
    return clustercents, ClustDist
相关文章
|
5天前
|
存储 算法 Python
Python中的列表推导式:深入探索与应用
Python中的列表推导式:深入探索与应用
106 1
|
14天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】聚类算法中,如何判断数据是否被“充分”地聚类,以便算法产生有意义的结果?
【5月更文挑战第14天】【机器学习】聚类算法中,如何判断数据是否被“充分”地聚类,以便算法产生有意义的结果?
|
15天前
|
机器学习/深度学习 传感器 算法
【机器学习】在聚类算法中,使用曼哈顿距离和使用欧式距离有什么区别?
【5月更文挑战第12天】【机器学习】在聚类算法中,使用曼哈顿距离和使用欧式距离有什么区别?
|
15天前
|
机器学习/深度学习 算法 数据可视化
【机器学习】比较分层聚类(Hierarchical Clustering)和K-means聚类算法
【5月更文挑战第12天】【机器学习】比较分层聚类(Hierarchical Clustering)和K-means聚类算法
|
15天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】在使用K-means聚类算法时,如何选择K的值?
【5月更文挑战第11天】【机器学习】在使用K-means聚类算法时,如何选择K的值?
|
15天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】K-means聚类的停止标准是什么?
【5月更文挑战第11天】【机器学习】K-means聚类的停止标准是什么?
|
15天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】解释什么是K-means聚类?
【5月更文挑战第11天】【机器学习】解释什么是K-means聚类?
|
15天前
|
机器学习/深度学习 人工智能 算法
【机器学习】K-means聚类有哪些应用?
【5月更文挑战第11天】【机器学习】K-means聚类有哪些应用?
|
15天前
|
分布式计算 调度 异构计算
Python 数学应用(四)(4)
Python 数学应用(四)
17 4
|
15天前
|
消息中间件 Kafka Python
Python 数学应用(四)(3)
Python 数学应用(四)
29 5