k均值 机器学习实战_机器学习实战 第八章 回归 计算误差估计值的均值 - CSDN
  • 机器学习实战K-Means(K-均值)聚类算法 聚类是一种无监督的学习,它将相似的对象归到同一个簇中。它有点像全自动分类。聚类 方法几乎可以应用于所有对象,簇内的对象越相似,聚类的效果越好。本章要学习一种称为...

    机器学习实战:K-Means(K-均值)聚类算法

    一、聚类

    聚类,简单来说,就是将一个庞杂数据集中具有相似特征的数据自动归类到一起,称为一个簇,簇内的对象越相似,聚类的效果越好。它是一种无监督的学习(Unsupervised Learning)方法,不需要预先标注好的训练集。聚类与分类最大的区别就是分类的目标事先已知,例如猫狗识别,你在分类之前已经预先知道要将它分为猫、狗两个种类;而在你聚类之前,你对你的目标是未知的,同样以动物为例,对于一个动物集来说,你并不清楚这个数据集内部有多少种类的动物,你能做的只是利用聚类方法将它自动按照特征分为多类,然后人为给出这个聚类结果的定义(即簇识别)。例如,你将一个动物集分为了三簇(类),然后通过观察这三类动物的特征,你为每一个簇起一个名字,如大象、狗、猫等,这就是聚类的基本思想。

    至于“相似”这一概念,是利用距离这个评价标准来衡量的,我们通过计算对象与对象之间的距离远近来判断它们是否属于同一类别,即是否是同一个簇。至于距离如何计算,科学家们提出了许多种距离的计算方法,其中欧式距离是最为简单和常用的,除此之外还有曼哈顿距离和余弦相似性距离等。

    欧式距离,它的定义为:
    对于x点(坐标为(x1,x2,x3,…,xn))和 y点(坐标为(y1,y2,y3,…,yn)),两者的欧式距离为
    在二维平面,它就是我们初中时就学过的两点距离公式

    二、K-Means 算法

    1、K-Means 概述

    K-Means 是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值 是因为它可以发现 K 个不同的簇, 且每个簇的中心采用簇中所含值的均值计算而成.
    簇个数 K 是用户指定的, 每一个簇通过其质心(centroid), 即簇中所有点的中心来描述.
    聚类与分类算法的最大区别在于, 分类的目标类别已知, 而聚类的目标类别是未知的.

    优点:

    • 属于无监督学习,无须准备训练集
    • 原理简单,实现起来较为容易
    • 结果可解释性较好

    缺点:

    • 需手动设置k值。 在算法开始预测之前,我们需要手动设置k值,即估计数据大概的类别个数,不合理的k值会使结果缺乏解释性
    • 可能收敛到局部最小值, 在大规模数据集上收敛较慢
    • 对于异常点、离群点敏感

    使用数据类型 : 数值型数据

    2、K-Means 场景

    kmeans,如前所述,用于数据集内种类属性不明晰,希望能够通过数据挖掘出或自动归类出有相似特点的对象的场景。其商业界的应用场景一般为挖掘出具有相似特点的潜在客户群体以便公司能够重点研究、对症下药。

    例如,在2000年和2004年的美国总统大选中,候选人的得票数比较接近或者说非常接近。任一候选人得到的普选票数的最大百分比为50.7%而最小百分比为47.9% 如果1%的选民将手中的选票投向另外的候选人,那么选举结果就会截然不同。 实际上,如果妥善加以引导与吸引,少部分选民就会转换立场。尽管这类选举者占的比例较低,但当候选人的选票接近时,这些人的立场无疑会对选举结果产生非常大的影响。如何找出这类选民,以及如何在有限的预算下采取措施来吸引他们? 答案就是聚类(Clustering)。

    那么,具体如何实施呢?首先,收集用户的信息,可以同时收集用户满意或不满意的信息,这是因为任何对用户重要的内容都可能影响用户的投票结果。然后,将这些信息输入到某个聚类算法中。接着,对聚类结果中的每一个簇(最好选择最大簇 ), 精心构造能够吸引该簇选民的消息。最后, 开展竞选活动并观察上述做法是否有效。

    另一个例子就是产品部门的市场调研了。为了更好的了解自己的用户,产品部门可以采用聚类的方法得到不同特征的用户群体,然后针对不同的用户群体可以对症下药,为他们提供更加精准有效的服务。

    3、K-Means 术语

    • 簇: 所有数据的点集合,簇中的对象是相似的。
    • 质心: 簇中所有点的中心(计算所有点的均值而来).
    • SSE: Sum of Sqared Error(误差平方和), 它被用来评估模型的好坏,SSE 值越小,表示越接近它们的质心. 聚类效果越好。由于对误差取了平方,因此更加注重那些远离中心的点(一般为边界点或离群点)。详情见kmeans的评价标准。

    有关 质心 术语更形象的介绍, 请参考下图:
    在这里插入图片描述

    4、K-Means 工作流程

    1. 首先, 随机确定 K 个初始点作为质心(不必是数据中的点)。
    2. 然后将数据集中的每个点分配到一个簇中, 具体来讲, 就是为每个点找到距其最近的质心, 并将其分配该质心所对应的簇. 这一步完成之后, 每个簇的质心更新为该簇所有点的平均值.
    3. 重复上述过程直到数据集中的所有点都距离它所对应的质心最近时结束。

    上述过程的 伪代码 如下:

    创建k个点作为起始质心(经常是随机选择) 
    当任意一个点的簇分配结果发生改变时 
    	对数据集中的每个数据点 
    		对每个质心 
    			计算质心与数据点之间的距离 
    		将数据点分配到距其最近的簇 
    	对每一个簇,计算簇中所有点的均值并将均值作为质心 
    

    K-均值聚类的一般流程:

    1. 收集数据:使用任意方法
    2. 准备数据:需要数值型数据类计算距离, 也可以将标称型数据映射为二值型数据再用于距离计算
    3. 分析数据:使用任意方法
    4. 训练算法:不适用于无监督学习,即无监督学习不需要训练步骤
    5. 测试算法:应用聚类算法、观察结果.可以使用量化的误差指标如误差平方和(后面会介绍)来评价算法的结果.
    6. 使用算法:可以用于所希望的任何应用.通常情况下, 簇质心可以代表整个簇的数据来做出决策.

    评价标准

    k-means算法因为手动选取k值和初始化随机质心的缘故,每一次的结果不会完全一样,而且由于手动选取k值,我们需要知道我们选取的k值是否合理,聚类效果好不好,那么如何来评价某一次的聚类效果呢?也许将它们画在图上直接观察是最好的办法,但现实是,我们的数据不会仅仅只有两个特征,一般来说都有十几个特征,而观察十几维的空间对我们来说是一个无法完成的任务。

    因此,我们需要一个公式来帮助我们判断聚类的性能,这个公式就是SSE (Sum of Squared Error, 误差平方和 ),它其实就是每一个点到其簇内质心的距离的平方值的总和,这个数值对应kmeans函数中clusterAssment矩阵的第一列之和。 SSE值越小表示数据点越接近于它们的质心,聚类效果也越好。 因为对误差取了平方,因此更加重视那些远离中心的点。

    一种肯定可以降低SSE值的方法是增加簇的个数,但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。

    算法函数

    # 从文本中构建矩阵,加载文本文件,然后处理
    def loadDataSet(fileName):  # 通用函数,用来解析以 tab 键分隔的 floats(浮点数)
        dataSet = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float, curLine))  # 映射所有的元素为 float(浮点数)类型
            dataSet.append(fltLine)
        return dataSet
    
    
    # 计算两个向量的欧式距离(可根据场景选择)
    def distEclud(vecA, vecB):
        return sqrt(sum(power(vecA - vecB, 2)))  # la.norm(vecA-vecB)
    
    
    # 为给定数据集构建一个包含 k 个随机质心的集合。随机质心必须要在整个数据集的边界之内,这可以通过找到数据集每一维的最小和最大值来完成。然后生成 0~1.0 之间的随机数并通过取值范围和最小值,以便确保随机点在数据的边界之内。
    def randCent(dataMat, k):
        n = shape(dataMat)[1]  # 列的数量
        centroids = mat(zeros((k, n)))  # 创建k个质心矩阵
        for j in range(n):  # 创建随机簇质心,并且在每一维的边界内
            minJ = min(dataMat[:, j])  # 最小值
            rangeJ = float(max(dataMat[:, j]) - minJ)  # 范围 = 最大值 - 最小值
            centroids[:, j] = mat(minJ + rangeJ * random.rand(k, 1))  # 随机生成
        return centroids
    
    
    # k-means 聚类算法
    # 该算法会创建k个质心,然后将每个点分配到最近的质心,再重新计算质心。
    # 这个过程重复数次,直到数据点的簇分配结果不再改变位置。
    # 运行结果(多次运行结果可能会不一样,可以试试,原因为随机质心的影响,但总的结果是对的, 因为数据足够相似,也可能会陷入局部最小值)
    def kMeans(dataMat, k, distMeas=distEclud, createCent=randCent):
        m = shape(dataMat)[0]  # 行数
        clusterAssment = mat(zeros(
            (m, 2)))  # 创建一个与 dataMat 行数一样,但是有两列的矩阵,一列记录簇索引值,第二列存储误差。这里的误差是指当前点到簇质心的距离,后边 会使用该误差来评价聚类的效果。
        centroids = createCent(dataMat, k)  # 创建质心,随机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, :],
                                      dataMat[i, :])
                    if distJI < minDist:  # 如果距离比 minDist(最小距离)还小,更新 minDist(最小距离)和最小质心的 index(索引)
                        minDist = distJI
                        minIndex = j
                if clusterAssment[i, 0] != minIndex:  # 簇分配结果改变
                    clusterChanged = True  # 簇改变
                    clusterAssment[
                        i, :] = minIndex, minDist**2  # 更新簇分配结果为最小质心的 index(索引),minDist(最小距离)的平方
            print(centroids)
            for cent in range(k):  # 更新质心
                ptsInClust = dataMat[nonzero(
                    clusterAssment[:, 0].A == cent)[0]]  # 获取该簇中的所有点
                centroids[cent, :] = mean(
                    ptsInClust, axis=0)  # 将质心修改为簇中所有点的平均值,mean 就是求平均值的
        return centroids, clusterAssment
    

    算法缺陷

    在 k-Means 的函数测试中,可能偶尔会陷入局部最小值(局部最优的结果,但不是全局最优的结果)
    局部最小值的的情况如下:
    在这里插入图片描述
    出现这个问题有很多原因,可能是k值取的不合适,可能是距离函数不合适,可能是最初随机选取的质心靠的太近,也可能是数据本身分布的问题。

    为了解决这个问题,我们可以对生成的簇进行后处理,一种方法是将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-均值算法,令k设为2。

    为了保持簇总数不变,可以将某两个簇进行合并。从上图中很明显就可以看出,应该将上图下部两个出错的簇质心进行合并。那么问题来了,我们可以很容易对二维数据上的聚类进行可视化, 但是如果遇到40维的数据应该如何去做?

    有两种可以量化的办法:合并最近的质心,或者合并两个使得SSE增幅最小的质心。 第一种思路通过计算所有质心之间的距离, 然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程,直到找到合并最佳的两个簇为止。

    因为上述后处理过程实在是有些繁琐,所以有更厉害的大佬提出了另一个称之为二分K-均值(bisecting K-Means)的算法.

    5、二分 K-Means 聚类算法

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

    二分 K-Means 聚类算法伪代码:

    将所有点看成一个簇 
    当簇数目小于k时 
    	对于每一个簇 
    		计算总误差 
    		在给定的簇上面进行K-均值聚类(k=2) 
    		计算将该簇一分为二之后的总误差 
    	选择使得误差最小的那个簇进行划分操作   
    

    另一种做法是选择 SSE 最大的簇进行划分,直到簇数目达到用户指定的数目位置。 接下来主要介绍该做法的python2代码实现

    算法代码

    # 二分 KMeans 聚类算法, 基于 kMeans 基础之上的优化,以避免陷入局部最小值
    def biKMeans(dataMat, k, distMeas=distEclud):
        m = shape(dataMat)[0]
        clusterAssment = mat(zeros((m, 2)))  # 保存每个数据点的簇分配结果和平方误差
        centroid0 = mean(dataMat, axis=0).tolist()[0]  # 质心初始化为所有数据点的均值
        centList = [centroid0]  # 初始化只有 1 个质心的 list
        for j in range(m):  # 计算所有数据点到初始质心的距离平方误差
            clusterAssment[j, 1] = distMeas(mat(centroid0), dataMat[j, :])**2
        while len(centList) < k:  # 当质心数量小于 k 时
            lowestSSE = inf
            for i in range(len(centList)):  # 对每一个质心
                ptsInCurrCluster = dataMat[nonzero(
                    clusterAssment[:, 0].A == i)[0], :]  # 获取当前簇 i 下的所有数据点
                centroidMat, splitClustAss = kMeans(
                    ptsInCurrCluster, 2, distMeas)  # 将当前簇 i 进行二分 kMeans 处理
                sseSplit = sum(splitClustAss[:, 1])  # 将二分 kMeans 结果中的平方和的距离进行求和
                sseNotSplit = sum(
                    clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0],
                                   1])  # 将未参与二分 kMeans 分配结果中的平方和的距离进行求和
                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)  # 调用二分 kMeans 的结果,默认簇是 0,1. 当然也可以改成其它的数字
            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]  # 更新原质心 list 中的第 i 个质心为使用二分 kMeans 后 bestNewCents 的第一个质心
            centList.append(
                bestNewCents[1, :].tolist()[0])  # 添加 bestNewCents 的第二个质心
            clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[
                0], :] = bestClustAss  # 重新分配最好簇下的数据(质心)以及SSE
        return mat(centList), clusterAssment
    

    上述函数可以运行多次,聚类会收敛到全局最小值,而原始的 kMeans() 函数偶尔会陷入局部最小值。
    运行参考结果如下:
    在这里插入图片描述

    三、小结

    聚类是一种无监督的学习方法。所谓无监督学习是指事先并不知道要寻找的内容,即没有目标变量。聚类将数据点归到多个簇中,其中相似数据点处于同一簇,而不相似数据点处于不同簇中。聚类中可以使用多种不同的方法来计算相似度。
    一种广泛使用的聚类算法是K-均值算法,其中k是用户指定的要创建的簇的数目。K-均值聚类算法以k个随机质心开始。算法会计算每个点到质心的距离。每个点会被分配到距其最近的簇质心,然后紧接着基于新分配到簇的点更新簇质心。以上过程重复数次,直到簇质心不再改变。 这个简单的算法非常有效但是也容易受到初始簇质心的影响。为了获得更好的聚类效果,可以使用另一种称为二分K-均值的聚类算法。二分K-均值算法首先将所有点作为一个簇,然后使用K均值算法(k = 2)对其划分。下一次迭代时,选择有最大误差的簇进行划分。该过程重复直到 k 个簇创建成功为止。二分K-均值的聚类效果要好于K-均值算法。
    K-均值算法以及变形的K-均值算法并非仅有的聚类算法,另外称为层次聚类的方法也被广泛使用。下一章将介绍在数据集中查找关联规则的Apriori算法。

    资料来源

    https://github.com/apachecn/AiLearning
    https://github.com/apachecn/AiLearning/tree/master/docs/ml
    机器学习实战(作者: Peter Harrington 出版社: 人民邮电出版社原作名: Machine Learning in Action译者: 李锐 / 李鹏 / 曲亚东 / 王斌 )

    展开全文
  • 2、K均值聚类的优点  算法简单容易实现  缺点:  可能收敛到局部最小值,在大规模数据上收敛速度较慢 3、K-均值算法算法流程以及伪代码  首先随机选择k个初始点作为质心。然后将数据集中的每个点分配到一个...

    1、聚类是一种无监督学习,他讲相似的对象放到同一簇下,有点像自动分类。聚类方法几乎可以用到任何对象上,簇内的对象越相似,聚类结果就越好。

    2、K均值聚类的优点

      算法简单容易实现

      缺点:

      可能收敛到局部最小值,在大规模数据上收敛速度较慢

    3、K-均值算法算法流程以及伪代码

      首先随机选择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))
            #print(fltLine)
            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, distMeans = distEclud, createCent = randCent):
        m = shape(dataSet)[0]
        #建立一个m*2的矩阵位置0记录聚类的索引,位置1记录到聚类质心的距离
        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 = distMeans(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):
                #通过数组过滤来获得给定簇的所有样本,nozero返回一个0/1矩阵,然后取第一列的索引列
                ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]]
                centroids[cent, :] = mean(ptsInClust, axis = 0)
        return centroids, clusterAssment
    #print(loadDataSet('testSet.txt'))
    dataMat = mat(loadDataSet('testSet.txt'))
    myCentroids, clustAssing = Kmeans(dataMat, 4)
    print(myCentroids)
    print(clustAssing)
    K-均值算法

    4、使用后处理提高聚类的性能

      K均值算法中的K是用户给出的,如何衡量在给定K个聚类的情况下聚类的性能。对于K均值算法可能会收敛到局部最小,而不能收敛到全局最小,因此可能聚类效果不好。在上边的代码中clusterAssment保存了每个数据点的簇标号以及点到簇质心的误差(就是距离)。那么可以使用SSE(sum of squared Erro,误差平方和)作为衡量聚类性能的指标,SSE的数值越小就表示数据点越接近他们的质心聚类效果也就越好,同时由于对误差取了平方所以越远的点在SSE中就越受重视。

      怎么降低SSE?一种简单的方法是增加簇的数量,但是这样不好啊,你是去聚类了你弄了和数据集一样的簇,那还聚个啥。因此需要在不改变簇的数目的前提下降低SSE。一种可行的办法是选择SSE最大的簇,然后对其继续进行K均值算法。同时为了保证簇的数目不变,可以将簇与簇进行合并。

      合并的方法:质心之间距离最近的合并;合并两个簇然后计算总的SSE,合并可以使SSE最小的簇。

    5、二分 K均值算法

      为了克服K均值算法收敛于局部最小的问题,有人提出了一个二分K均值的算法。回来继续

    转载于:https://www.cnblogs.com/daguankele/p/6562117.html

    展开全文
  • 机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记,包含对其中算法的理解和算法的Python代码实现 另外博主这里有机器学习实战这本书的所有算法源代码和算法所用到的源文件,有需要的留言 ...

     

    ============================================================================================
    《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记,包含对其中算法的理解和算法的Python代码实现
     
    另外博主这里有机器学习实战这本书的所有算法源代码和算法所用到的源文件,有需要的留言
    ============================================================================================

     

    Scikit-learn 实现的K-Means 算法请参考 :点击阅读

    二分K-Means算法请参考:点击阅读

            机器学习中有两类的大问题,一个是分类,一个是聚类。分类是根据一些给定的已知类别标号的样本,训练某种学习机器,使它能够对未知类别的样本进行分类。这属于supervised learning(监督学习)。而聚类指事先并不知道任何样本的类别标号,希望通过某种算法来把一组未知类别的样本划分成若干类别,这在机器学习中被称作 unsupervised learning (无监督学习)。在本文中,我们关注其中一个比较简单的聚类算法:k-means算法。 

            k-means算法是一种很常见的聚类算法,它的基本思想是:通过迭代寻找k个聚类的一种划分方案,使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

    其Python实现的代码如下:

    #encoding:utf-8
    from numpy import *
    
    def loadDataSet(filename):
    	dataMat = []          #创建元祖
    	fr = open(filename)
    	for line in fr.readlines():
    		curLine = line.strip().split("\t")
    		fltLine = map(float,curLine) #使用map函数将curLine里的数全部转换为float型
    		dataMat.append(fltLine)
    	return dataMat
    
    def distEclud(vecA,vecB):          #计算两个向量的欧式距离
    	return sqrt(sum(power(vecA-vecB,2)))
    
    def randCent(dataSet,k):            #位给定数据集构建一个包含k个随机质心的集合
    	n = shape(dataSet)[1]   #shape函数此时返回的是dataSet元祖的列数
    	centroids = mat(zeros((k,n)))       #mat函数创建k行n列的矩阵,centroids存放簇中心
    	for j in range(n):
    		minJ = min(dataSet[:,j])           #第j列的最小值
    		rangeJ = float(max(dataSet[:,j]) - minJ)
    		centroids[:,j] = minJ + rangeJ * random.rand(k,1)  #random.rand(k,1)产生shape(k,1)的矩阵
    	return centroids
    
    def kMeans(dataSet,k,disMeas = distEclud,createCent = randCent):
    	m = shape(dataSet)[0] #shape函数此时返回的是dataSet元祖的行数
    	clusterAssment = mat(zeros((m,2)))      #创建一个m行2列的矩阵,第一列存放索引值,第二列存放误差,误差用来评价聚类效果
    	centroids = createCent(dataSet,k)  #创建k个质心,调用createCent()函数
    	clusterChanged =True #标志变量,若为true则继续迭代
    	print "质心位置更新过程变化:"
    	while clusterChanged:
    		clusterChanged = False
    		for i in range(m):
    			minDist = inf #inf为正无穷大
    			minIndex = -1  #创建索引
    			for j in range(k):
    				#寻找最近的质心
    				disJI = disMeas(centroids[j,:],dataSet[i,:]) #计算每个点到质心的欧氏距离
    				if disJI(array([0, 0, 1]), array([0, 2, 0]))
    				#print array(nonzero(b2))
    				#=>[[0, 0, 1],[0, 2, 0]]
    				centroids[cent,:] = mean(ptsInClust,axis=0)  #计算所有点的均值,选项axis=0表示沿矩阵的列方向进行均值计算
    	return centroids,clusterAssment  #返回所有的类质心与点分配结果
    	
    
    datMat = mat(loadDataSet('data.txt'))
    myCentroids,clustAssing = kMeans(datMat,2)
    print "最终质心:\n",myCentroids
    print "索引值和均值:\n",clustAssing
    (array([0, 0, 1]), array([0, 2, 0]))
    				#print array(nonzero(b2))
    				#=>[[0, 0, 1],[0, 2, 0]]
    				centroids[cent,:] = mean(ptsInClust,axis=0)  #计算所有点的均值,选项axis=0表示沿矩阵的列方向进行均值计算
    	return centroids,clusterAssment  #返回所有的类质心与点分配结果
    	
    
    datMat = mat(loadDataSet('data.txt'))
    myCentroids,clustAssing = kMeans(datMat,2)
    print "最终质心:\n",myCentroids
    print "索引值和均值:\n",clustAssing
    

      k-means算法比较简单,但也有几个比较大的缺点:
    1)k值的选择是用户指定的,不同的k得到的结果会有挺大的不同,如下图所示,左边是k=3的结果,这个就太稀疏了,蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果,可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的:

    2)对k个初始质心的选择比较敏感,容易陷入局部最小值。例如,我们上面的算法运行的时候,有可能会得到不同的结果,如下面这两种情况。K-means也是收敛了,只是收敛到了局部最小值:

    3)存在局限性,如下面这种非球状的数据分布就搞不定了

    4)数据库比较大的时候,收敛会比较慢.

     

      K均值聚类中簇的值k是用户预先定义的一个参数,那么用户如何才能知道k的选择是否正确?如何才能知道生成的簇比较好?在计算的过程中保留了每个点的误差,即该点到簇质心的距离平方值,下面将讨论利用该误差来评价聚类质量好坏的方法,引入度量聚类效果的指标SSE(sum of squared Error,误差平方和),SSE值越小,越接近于他们的质心,聚类效果也越好,有一种可以肯定减小SSE值得方法是增加k的数目,但这个违背了聚类的目标,聚类的目标是在保持簇数目不变的情况下提高簇的质量。

    接下来要讨论的是利用簇划分技术得到更好的聚类效果——二分K-均值算法


    搜索与推荐Wiki

    扫一扫 关注微信公众号!号主 专注于搜索和推荐系统,尝试使用算法去更好的服务于用户,包括但不局限于机器学习,深度学习,强化学习,自然语言理解,知识图谱,还不定时分享技术,资料,思考等文章!


                                 【技术服务】,详情点击查看:https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg


    外包服务

    展开全文
  • K-均值算法试图将一系列样本分割成K个不同的类簇(其中K是模型的输入参数),其形式化的目标函数称为类簇内的方差和(within cluster sum of squared errors,WCSS)。K-均值聚类的目的是最小化所有类簇中的方差之和...


    引言

    K-均值算法试图将一系列样本分割成K个不同的类簇(其中K是模型的输入参数),其形式化的目标函数称为类簇内的方差和(within cluster sum of squared errors,WCSS)。K-均值聚类的目的是最小化所有类簇中的方差之和。标准的K-均值算法初始化K个类中心(为每个类簇中所有样本的平均向量)


    原理

    k-均值聚类算法

    创建K个点作为起始质点(经常是随机选择)
    进行迭代
      将每个数据点分配到离他距离最近的质点的簇。
      全部分配后,用各个簇中的数据点的位置均值来更新质点的位置
    直到达到迭代次数,或者所有的数据点所在的簇不发生改变

    这意味着需要某种距离运算。数据集上k-均值算法的性能会受到所选距离计算方法的影响。我们可列出k-均值聚类支持函数:

    def loadDataSet(fileName):      #general function to parse tab -delimited floats
        dataMat = []                #assume last column is target value
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = map(float,curLine) #map all elements to float()
            dataMat.append(fltLine)
        return dataMat
    
    def distEclud(vecA, vecB):
        return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)
    
    def randCent(dataSet, k):
        n = shape(dataSet)[1]
        centroids = mat(zeros((k,n)))#create centroid mat
        for j in range(n):#create random cluster centers, within bounds of each dimension
            minJ = min(dataSet[:,j]) 
            rangeJ = float(max(dataSet[:,j]) - minJ)
            centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))
        return centroids

    第一个函数的功能是进行数据导入,第二个函数的功能是计算两个向量的欧氏距离,最后一个函数是为给定数据集构建一个包含k个随机之心的集合。
    然后便是k-均值聚类算法:

    def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
        m = shape(dataSet)[0]
        clusterAssment = mat(zeros((m,2)))#create mat to assign data points 
                                          #to a centroid, also holds SE of each point
        centroids = createCent(dataSet, k)
        clusterChanged = True
        while clusterChanged:
            clusterChanged = False
            for i in range(m):#for each data point assign it to the closest centroid
                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):#recalculate centroids
                ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
                centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean 
        return centroids, clusterAssment

    实例分析

    可以对它进行一些测试,测试集采用如下测试集
    这里写图片描述
                  一个书中自带的测试集

    输入如下命令:

    datMat=mat(loadDataSet('testSet.txt'))
    myCentroids,clustAssing=kMeans(datMat,4)

    得到如下结果,进行了四次迭代后算法收敛
    这里写图片描述

    二分k-均值算法

    将所有点看成一个簇
    当簇数目小于k时
       对于每一个簇:
        计算总误差
        在给定的簇上面进行K-均值聚类k=2
      计算将该簇一分为二后的总误差
      选择使得误差最小的那个簇进行划分操作

    代码如下

    def biKmeans(dataSet, k, distMeas=distEclud):
        m = shape(dataSet)[0]
        clusterAssment = mat(zeros((m,2)))
        centroid0 = mean(dataSet, axis=0).tolist()[0]
        centList =[centroid0] #create a list with one centroid
        for j in range(m):#calc initial Error
            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],:]#get the data points currently in cluster i
                centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
                sseSplit = sum(splitClustAss[:,1])#compare the SSE to the currrent minimum
                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) #change 1 to 3,4, or whatever
            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]#replace a centroid with two best centroids 
            centList.append(bestNewCents[1,:].tolist()[0])
            clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE
        return mat(centList), clusterAssment

    实例分析

    在上述测试集中进行测试
    输入

    datMat=mat(loadDataSet('testSet.txt'))
    CentList,MyNewAssments=biKmeans(datMat,4)
    print(CentList)

    得到聚类结果
    这里写图片描述
    也可用一个较难的数据集

    这里写图片描述
                  一个书中自带的测试集

    输入

    datMat=mat(loadDataSet('testSet2.txt'))
    CentList,MyNewAssments=biKmeans(datMat,3)
    print(CentList)

    得到聚类结果

    这里写图片描述


    实例

    运用经典的iris数据集进行分类

    这里写图片描述
    使用经典的k-均值算法进行分类

    datMat=mat(loadDataSet('iris.txt'))
    CentList,MyNewAssments=kMeans(datMat,3)

    可得到迭代结果

    这里写图片描述
    经过10次迭代,算法收敛最后的聚类中心

    这里写图片描述
    以及最后的聚类集

    这里写图片描述
                  部分聚类集


    代码

    from numpy import *
    import matplotlib.pyplot as plt 
    
    def loadDataSet(fileName):      #general function to parse tab -delimited floats
        dataMat = []                #assume last column is target value
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float,curLine)) #map all elements to float()
            dataMat.append(fltLine)
        return dataMat
    
    def distEclud(vecA, vecB):
        return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)
    
    def randCent(dataSet, k):
        n = shape(dataSet)[1]
        centroids = mat(zeros((k,n)))#create centroid mat
        for j in range(n):#create random cluster centers, within bounds of each dimension
            minJ = min(dataSet[:,j]) 
            rangeJ = float(max(dataSet[:,j]) - minJ)
            centroids[:,j] = mat(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)))#create mat to assign data points 
                                          #to a centroid, also holds SE of each point
        centroids = createCent(dataSet, k)
        clusterChanged = True
        while clusterChanged:
            clusterChanged = False
            for i in range(m):#for each data point assign it to the closest centroid
                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):#recalculate centroids
                ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
                centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean 
        return centroids, clusterAssment
    
    def biKmeans(dataSet, k, distMeas=distEclud):
        m = shape(dataSet)[0]
        clusterAssment = mat(zeros((m,2)))
        centroid0 = mean(dataSet, axis=0).tolist()[0]
        centList =[centroid0] #create a list with one centroid
        for j in range(m):#calc initial Error
            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],:]#get the data points currently in cluster i
                centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
                sseSplit = sum(splitClustAss[:,1])#compare the SSE to the currrent minimum
                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) #change 1 to 3,4, or whatever
            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]#replace a centroid with two best centroids 
            centList.append(bestNewCents[1,:].tolist()[0])
            clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss#reassign new clusters, and SSE
        return mat(centList), clusterAssment

    参考文献

    《机器学习实战》

    展开全文
  • 最近在看《机器学习实战》这本书,书中的机器学习算法都很经典,写的也很详细,是一本不错的书,适合夯实基础,不过有一点缺陷就是书中使用的Python2的编译器代码,多多少少会与当前主流的Python3有些出入,所以小编...
  • ===================================================================== 《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记也包含一些其他python实现的机器学习算法 算法实现均采用pyth...
  • 聚类算法包括:K均值聚类(K-Means)、层次聚类(Hierarchical Clustering)和混合高斯模型(Gaussian Mixture Model)。K均值聚类(K-Means)算法的核心思想是:对于给定的样本集,按照样本之间的距离大小,将样本集划分为K...
  • 概述:本章开始进入无监督学习的内容。聚类方法将相似的对象分到同一个簇中。
  • 注:此系列文章里的部分算法和深度学习笔记系列里的内容有重合的地方,深度学习笔记里是看教学视频做的笔记,此处文章是看《机器学习实战》这本书所做的笔记,虽然算法相同,但示例代码有所不同,多敲一遍没有坏处,...
  • 机器学习实战》之二分K-均值聚类算法的python实现上面博文介绍了K-均值聚类算法及其用python实现,上篇博文中的两张截图,我们可以看到,由于K-均值聚类算法中由于初始质心的选取,会造成聚类的局部最优,并不是...
  • 一、引言聚类是一种无监督学习二、K均值聚类算法2.1 算法过程:随机确定K个初始点为质心(簇个数k由用户给定)然后将数据集中的每个点寻找距其最近的质心,分配到对应的簇中,完成后,每个簇的质心更新为该簇所有点的...
  • 本篇的数据和代码参见:...K-均值聚类是每个类别簇都是采用簇中所含值的均值计算而成。聚类与分类的区别在于分类前目标已知,而聚类为无监督分类。 K-均值算法的伪代码如下:创建k个点作为起始质心(通常
  • K-均值聚类算法,它可以发现K个不同的簇,且每个簇的中心采用簇中所含值的均值计算而成。簇识别概念:假定有一些数据,现在将相似数据归到一起,簇识别会告诉我们这些簇到底都是些什么,聚类与分类的最大不同在于,...
  • K-Means聚类算法属于无监督...python实现(机器学习实战) import numpy as np import matplotlib.pyplot as plt def loadDataSet(filename): dataMat=[] fr=open(filename) for line in fr.readlines(): cur...
  • 目录 0. 前言 ...学习完机器学习实战K-means,简单的做个笔记。文中部分描述属于个人消化后的理解,仅供参考。 本篇综合了先前的文章,如有不理解,可参考: 吴恩达机器学习(十一)K-means 所有...
  • 今天给大家介绍一本以 Python 为基础的机器学习实战编程书籍:《机器学习实战》。 本书特色: 本书的目录如下: 本书第一部分主要介绍机器学习基础,以及如何利用算法进行分类,并逐步介绍了多种经典的监督学习算法...
  • K-Means是发现给定数据集的K个簇的聚类算法,之所以称之为 “K-均” 值是因为它可以发现K个不同的簇,且每个簇的中心采用的所含值的均值计算而成。 簇个数K是用户指定的,每一个簇通过其质心(centroid),即簇中所有...
  • 本篇博客意在记录学习机器学习实战中算法的过程,首先申明一下,博主是一个小白,刚开始接触机器学习,所以每学完一个算法,就会进行一次总结,写一篇博客。每篇博客仅是个人理解而写,如...机器学习实战(四)k-近...
  • 一,K均值聚类算法 1,特点 优点:容易实现。 缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢。 适用数据类型:数值型数据。 2,伪代码 创建k个点作为起点质心(经常是随机选择) 当任意一个点...
1 2 3 4 5 ... 20
收藏数 3,564
精华内容 1,425
关键字:

k均值 机器学习实战