机器学习实战之K-Means聚类

俗话说的好:“物以类聚,人以群分”,今天我们要讲的聚类算法很大程度上可以印证此话。聚类是一种非监督学习,什么是非监督学习?与之前学习的分类和回归不同(监督学习),监督学习是有有label标签的,而非监督学习没有。 我们再回到聚类上,聚类是把相似的对象归到同一簇中,有点像全自动分类。聚类的应用场景有很多,例如在电商行业,通过用户的购买历史进行聚类,针对不同的用户群体推送不同的广告。

K-Means聚类算法

算法流程

K-Means聚类首先随机确定 K 个初始点作为质心(这也是K-Means聚类的一个问题,这个K值的不合理选择会使得模型不适应和解释性差)。然后将数据集中的每个点分配到一个簇中, 具体来讲,就是为每个点找到距其最近的质心(这里算的为欧式距离,当然也可以使用其他距离), 并将其分配该质心所对应的簇;这一步完成之后,每个簇的质心更新为该簇所有点的平均值;重复上述过程直到数据集中的所有点都距离它所对应的质心最近时结束。

算法伪代码
创建 k 个点作为起始质心(随机选择)
当任意一个点的簇分配结果发生改变时(不改变时算法结束)
    对数据集中的每个数据点
        对每个质心
            计算质心与数据点之间的距离
        将数据点分配到距其最近的簇
    对每一个簇, 计算簇中所有点的均值并将均值作为质心
实现代码
from numpy import *

def loadDataSet(filename):
    dataMat = []
    fr = open(filename)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = list(map(float,curLine))
        dataMat.append(fltLine)
    return dataMat   

def distEclud(vecA,vecB):
    return sqrt(sum(power(vecA - vecB,2)))

def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        centroids[:, j] = minJ + rangeJ * random.rand(k,1)
    return centroids

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroids = createCent(dataSet,k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            minDist = inf;minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j,:], dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI;minIndex = j
            if clusterAssment[i,0] != minIndex: clusterChanged=True
            clusterAssment[i,:] = minIndex, minDist**2
        print(centroids)
        for cent in range(k):
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
            centroids[cent,:] = mean(ptsInClust,axis=0)
    return centroids, clusterAssment

聚类结果如图:

缺陷

K-Means算法可能偶尔会陷入局部最小值(局部最优的结果,但不是全局最优的结果),如图所示。

出现这个问题有很多原因,可能是k值取的不合适,可能是距离函数不合适,可能是最初随机选取的质心靠的太近,也可能是数据本身分布的问题。

二分K-Means 聚类算法

为了解决K-Means算法的问题,提出了二分 K-Means 聚类算法。该算法首先将所有点作为一个簇,然后将该簇一分为二。之后选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分时候可以最大程度降低 SSE(平方和误差)的值。上述基于 SSE 的划分过程不断重复,直到得到用户指定的簇数目为止。

代码
def biKmeans(dataSet, k, distMeas=distEclud):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroid0 = mean(dataSet, axis=0).tolist()[0]
    centList = [centroid0]
    for j in range(m):
        clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:]) ** 2
    while (len(centList) < k):
        lowestSSE = inf
        for i in range(len(centList)):
            ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
            sseSplit = sum(splitClustAss[:,1])
            sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
            print("sseSplit, and notSplit: ",sseSplit,sseNotSplit)
            if (sseSplit + sseNotSplit) < lowestSSE: 
                bestCentToSplit = i
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSE = sseSplit + sseNotSplit   
        bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList)
        bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
        print('the bestCentToSplit is: ',bestCentToSplit)
        print('the len of bestClustAss is: ', len(bestClustAss))
        centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]
        centList.append(bestNewCents[1,:].tolist()[0])
        clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss
    return mat(centList), clusterAssment

结果如图所示:

K-Means算法优缺点

  • 优点:容易实现
  • 缺点:可能陷入局部最优解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

收藏 | 机器学习、NLP、Python和Math最好的150余个教程

? 尽管机器学习的历史可以追溯到1959年,但目前,这个领域正以前所未有的速度发展。最近,我一直在网上寻找关于机器学习和NLP各方面的好资源,为了帮助到和我有...

2025
来自专栏mukekeheart的iOS之旅

如何求最小三元组距离

题目描述:   已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素,使得组成的三元组距离最小。   三元组的距离定义是:假设a[i]...

2198
来自专栏osc同步分享

算法基础

分治法的基本思想: 将一个规模为 n 的问题分解为 k 各规模较小的子问题, 这些子问题互相独立且与原问题是同类型问题。 递归地解这些子问题, 然后把各个子问题...

3379
来自专栏专知

【论文推荐】最新5篇图像分割相关论文—条件随机场和深度特征学习、移动端网络、长期视觉定位、主动学习、主动轮廓模型、生成对抗性网络

【导读】专知内容组整理了最近五篇视觉图像分割(Image Segmentation)相关文章,为大家进行介绍,欢迎查看! 1. Conditional Rand...

4058
来自专栏desperate633

详解排序算法--希尔排序希尔排序算法思想步长序列

希尔排序的由来是根据插入排序的。 读者若不了解插入排序,可以参考笔者的详解排序算法--插入排序和冒泡排序.

803
来自专栏Petrichor的专栏

深度学习: Batch Normalization (归一化)

15年2月的论文:Batch Normalization: Accelerating Deep Network Training by Reducing Int...

1143
来自专栏窗户

有限域(2)——理想和商环

  我们上一节介绍了环(ring)、域(field)的概念,并给了一些环、域的实例。比如我们知道整数环、方阵环、有理数域、实数域等。我们知道,域是环的一个种。最...

552
来自专栏aCloudDeveloper

算法导论第八章线性时间排序

一、线性时间排序算法历史概览       计数排序首先是由 Harold H. Seward 于1954年提出,而且他还提出将计数排序和基数排序进行结合的思想;...

2076
来自专栏机器学习、深度学习

物体分割--Deep Watershed Transform for Instance Segmentation

Deep Watershed Transform for Instance Segmentation CVPR2017 https://github.c...

3257
来自专栏Python数据科学

k近邻(KNN)之kd树算法原理

本文介绍一种用于高维空间中的快速最近邻和近似最近邻查找技术——Kd-Tree(Kd树)。Kd-Tree,即K-dimensional tree,是一种高维索引树...

832

扫码关注云+社区