精华内容
下载资源
问答
  • K-means聚类算法原理及python实现

    万次阅读 多人点赞 2019-07-26 11:51:49
    聚类算法二.K-means聚类算法三.K-means算法步骤详解Step1.K值的选择Step2.距离度量2.1.欧式距离2.2.曼哈顿距离2.3.余弦相似度Step3.新质心的计算Step4.是否停止K-means四.K-means算法代码实现1.其伪代码如下2.python...

    一.聚类算法的简介

            对于"监督学习"(supervised learning),其训练样本是带有标记信息的,并且监督学习的目的是:对带有标记的数据集进行模型学习,从而便于对新的样本进行分类。而在“无监督学习”(unsupervised learning)中,训练样本的标记信息是未知的,目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律,为进一步的数据分析提供基础。对于无监督学习,应用最广的便是"聚类"(clustering)。
            "聚类算法"试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集称为一个“簇”(cluster),通过这样的划分,每个簇可能对应于一些潜在的概念或类别。
            我们可以通过下面这个图来理解:

            上图是未做标记的样本集,通过他们的分布,我们很容易对上图中的样本做出以下几种划分。
                    当需要将其划分为两个簇时,即 k=2时:

            当需要将其划分为四个簇时,即 k=4 时:

    二.K-means聚类算法

            kmeans算法又名k均值算法,K-means算法中的k表示的是聚类为k个簇,means代表取每一个聚类中数据值的均值作为该簇的中心,或者称为质心,即用每一个的类的质心对该簇进行描述。
            其算法思想大致为:先从样本集中随机选取 k个样本作为簇中心,并计算所有样本与这 k个“簇中心”的距离,对于每一个样本,将其划分到与其距离最近的“簇中心”所在的簇中,对于新的簇计算各个簇的新的“簇中心”。
            根据以上描述,我们大致可以猜测到实现kmeans算法的主要四点:
              (1)簇个数 k 的选择
              (2)各个样本点到“簇中心”的距离
              (3)根据新划分的簇,更新“簇中心”
              (4)重复上述2、3过程,直至"簇中心"没有移动
            优缺点:

    • 优点:容易实现
    • 缺点:可能收敛到局部最小值,在大规模数据上收敛较慢

    三.K-means算法步骤详解

    Step1.K值的选择

    k 的选择一般是按照实际需求进行决定,或在实现算法时直接给定 k 值。

    说明:
    A.质心数量由用户给出,记为k,k-means最终得到的簇数量也是k
    B.后来每次更新的质心的个数都和初始k值相等
    C.k-means最后聚类的簇个数和用户指定的质心个数相等,一个质心对应一个簇,每个样本只聚类到一个簇里面
    D.初始簇为空

    Step2.距离度量

            将对象点分到距离聚类中心最近的那个簇中需要最近邻的度量策略,在欧式空间中采用的是欧式距离,在处理文档中采用的是余弦相似度函数,有时候也采用曼哈顿距离作为度量,不同的情况实用的度量公式是不同的。

    2.1.欧式距离

    2.2.曼哈顿距离

    2.3.余弦相似度

            A与B表示向量(x1,y1),(x2,y2)
            分子为A与B的点乘,分母为二者各自的L2相乘,即将所有维度值的平方相加后开方。

    说明:
    A.经过step2,得到k个新的簇,每个样本都被分到k个簇中的某一个簇
    B.得到k个新的簇后,当前的质心就会失效,需要计算每个新簇的自己的新质心

    Step3.新质心的计算

            对于分类后的产生的k个簇,分别计算到簇内其他点距离均值最小的点作为质心(对于拥有坐标的簇可以计算每个簇坐标的均值作为质心)

    说明:
    A.比如一个新簇有3个样本:[[1,4], [2,5], [3,6]],得到此簇的新质心=[(1+2+3)/3, (4+5+6)/3]
    B.经过step3,会得到k个新的质心,作为step2中使用的质心

    Step4.是否停止K-means

            质心不再改变,或给定loop最大次数loopLimit

    说明:
    A当每个簇的质心,不再改变时就可以停止k-menas
    B.当loop次数超过looLimit时,停止k-means
    C.只需要满足两者的其中一个条件,就可以停止k-means
    C.如果Step4没有结束k-means,就再执行step2-step3-step4
    D.如果Step4结束了k-means,则就打印(或绘制)簇以及质心

    四.python实现+代码详解

            以下是python得实例代码以及代码的详解,应该可以理解的。

    import random
    import pandas as pd
    import numpy as np
    import matplotlib.pyplot as plt
    
    # 计算欧拉距离
    def calcDis(dataSet, centroids, k):
        clalist=[]
        for data in dataSet:
            diff = np.tile(data, (k, 1)) - centroids  #相减   (np.tile(a,(2,1))就是把a先沿x轴复制1倍,即没有复制,仍然是 [0,1,2]。 再把结果沿y方向复制2倍得到array([[0,1,2],[0,1,2]]))
            squaredDiff = diff ** 2     #平方
            squaredDist = np.sum(squaredDiff, axis=1)   #和  (axis=1表示行)
            distance = squaredDist ** 0.5  #开根号
            clalist.append(distance) 
        clalist = np.array(clalist)  #返回一个每个点到质点的距离len(dateSet)*k的数组
        return clalist
    
    # 计算质心
    def classify(dataSet, centroids, k):
        # 计算样本到质心的距离
        clalist = calcDis(dataSet, centroids, k)
        # 分组并计算新的质心
        minDistIndices = np.argmin(clalist, axis=1)    #axis=1 表示求出每行的最小值的下标
        newCentroids = pd.DataFrame(dataSet).groupby(minDistIndices).mean() #DataFramte(dataSet)对DataSet分组,groupby(min)按照min进行统计分类,mean()对分类结果求均值
        newCentroids = newCentroids.values
     
        # 计算变化量
        changed = newCentroids - centroids
     
        return changed, newCentroids
    
    # 使用k-means分类
    def kmeans(dataSet, k):
        # 随机取质心
        centroids = random.sample(dataSet, k)
        
        # 更新质心 直到变化量全为0
        changed, newCentroids = classify(dataSet, centroids, k)
        while np.any(changed != 0):
            changed, newCentroids = classify(dataSet, newCentroids, k)
     
        centroids = sorted(newCentroids.tolist())   #tolist()将矩阵转换成列表 sorted()排序
     
        # 根据质心计算每个集群
        cluster = []
        clalist = calcDis(dataSet, centroids, k) #调用欧拉距离
        minDistIndices = np.argmin(clalist, axis=1)  
        for i in range(k):
            cluster.append([])
        for i, j in enumerate(minDistIndices):   #enymerate()可同时遍历索引和遍历元素
            cluster[j].append(dataSet[i])
            
        return centroids, cluster
     
    # 创建数据集
    def createDataSet():
        return [[1, 1], [1, 2], [2, 1], [6, 4], [6, 3], [5, 4]]
    
    if __name__=='__main__': 
        dataset = createDataSet()
        centroids, cluster = kmeans(dataset, 2)
        print('质心为:%s' % centroids)
        print('集群为:%s' % cluster)
        for i in range(len(dataset)):
          plt.scatter(dataset[i][0],dataset[i][1], marker = 'o',color = 'green', s = 40 ,label = '原始点')
                                                        #  记号形状       颜色      点的大小      设置标签
          for j in range(len(centroids)):
            plt.scatter(centroids[j][0],centroids[j][1],marker='x',color='red',s=50,label='质心')
            plt.show
    

    五.K-means算法补充

    1.对初始化敏感,初始质点k给定的不同,可能会产生不同的聚类结果。如下图所示,右边是k=2的结果,这个就正好,而左图是k=3的结果,可以看到右上角得这两个簇应该是可以合并成一个簇的。

    改进:
    对k的选择可以先用一些算法分析数据的分布,如重心和密度等,然后选择合适的k

    2.使用存在局限性,如下面这种非球状的数据分布就搞不定了:

    3.数据集比较大的时候,收敛会比较慢

    4.最终会收敛。不管初始点如何选择,最终都会收敛。可是是全局收敛,也可能是局部收敛。

    六.小结

            1. 聚类是一种无监督的学习方法。聚类区别于分类,即事先不知道要寻找的内容,没有预先设定好的目标变量。

            2. 聚类将数据点归到多个簇中,其中相似的数据点归为同一簇,而不相似的点归为不同的簇。相似度的计算方法有很多,具体的应用选择合适的相似度计算方法

            3. K-means聚类算法,是一种广泛使用的聚类算法,其中k是需要指定的参数,即需要创建的簇的数目,K-means算法中的k个簇的质心可以通过随机的方式获得,但是这些点需要位于数据范围内。在算法中,计算每个点到质心得距离,选择距离最小的质心对应的簇作为该数据点的划分,然后再基于该分配过程后更新簇的质心。重复上述过程,直至各个簇的质心不再变化为止。

            4. K-means算法虽然有效,但是容易受到初始簇质心的情况而影响,有可能陷入局部最优解。为了解决这个问题,可以使用另外一种称为二分K-means的聚类算法。二分K-means算法首先将所有数据点分为一个簇;然后使用K-means(k=2)对其进行划分;下一次迭代时,选择使得SSE下降程度最大的簇进行划分;重复该过程,直至簇的个数达到指定的数目为止。实验表明,二分K-means算法的聚类效果要好于普通的K-means聚类算法。

    展开全文
  • K-means聚类算法

    2021-01-07 11:52:25
    K-Means聚类算法 是无监督学习的一种。 K-Means算法是一种简单的迭代型聚类算法,采用距离作为相似性指标,从而发现给定数据集中的K个类,且每个类的中心是根据类中所有数值的均值得到的,每个类的中心用聚类中心来...
  • k-means聚类算法

    2017-05-21 10:36:55
    Java编写的k-means聚类算法,从文件读取数据,可视化界面。
  • K-means聚类算法和模糊C-means聚类算法

    万次阅读 多人点赞 2018-02-05 21:16:47
    K-means聚类算法和模糊C-means聚类算法 1.K-means聚类算法 K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代...

    K-means聚类算法和模糊C-means聚类算法

    1.K-means聚类算法

    K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

    展开全文
  • k-means聚类算法原理简析

    万次阅读 多人点赞 2019-01-26 23:03:17
    k-means聚类算法原理简介概要算法思想算法流程图解代码实现 概要 K-means算法是最普及的聚类算法,也是一个比较简单的聚类算法,所以刚接触的同学不要感到害怕。算法接受一个未标记的数据集,然后将数据聚类成不同...

    概要

    K-means算法是最普及的聚类算法,也是一个比较简单的聚类算法,所以刚接触的同学不要感到害怕。算法接受一个未标记的数据集,然后将数据聚类成不同的组,同时,k-means算法也是一种无监督学习。

    算法思想

    k-means算法的思想比较简单,假设我们要把数据分成K个类,大概可以分为以下几个步骤:

    1. 随机选取k个点,作为聚类中心;
    2. 计算每个点分别到k个聚类中心的聚类,然后将该点分到最近的聚类中心,这样就行成了k个簇;
    3. 再重新计算每个簇的质心(均值);
    4. 重复以上2~4步,直到质心的位置不再发生变化或者达到设定的迭代次数。

    算法流程图解

    下面我们通过一个具体的例子来理解这个算法(我这里用到了Andrew Ng的机器学习教程中的图):
    假设我们首先拿到了这样一个数据,要把它分成两类:
    在这里插入图片描述
    我们人眼当然可以很快的分辨出来,可以在两个聚类间找到一条合理的分界线,那么用k-means算法来解决这个问题会是怎样的呢?
    首先我们随机选取两个点作为聚类中心(因为已经明确是分为两类):
    在这里插入图片描述
    接下来就可以开始计算每个点到红点和蓝点的距离了,离红点近就标记为红色,离蓝点近就标记为蓝色。结果为下图:
    在这里插入图片描述
    很明显,这样完全不是我们想要的结果,接下来我们进行第三步,重新计算聚类中心的位置。
    在这里插入图片描述
    红X和蓝X都向中间靠拢了一点。我们可以看到,聚类中心发生改变后,其他点离两个聚类中心的距离也跟随着发生了变化。然后我们重复第二步,根据每个点到两个聚类中心的距离远近来进行重新分类,离红X近的归为红类,离蓝X近的归为蓝类。
    在这里插入图片描述
    之前站错了队伍的一些点重新进行了调整,现在的分类离我们的目标越来越近了,但还没有达到最佳的分类效果。接下来继续重复上面的步骤,重新计算聚类中心的位置,再重新分类,不断迭代,直至聚类中心的位置不再变化(变化范围达到设定值)或达到迭代次数为止。
    在这里插入图片描述
    这样我们就利用k-means算法把这个数据很好的分为两类啦。
    我们可以看到,在整个过程中,我们都没有去监督算法,告诉他具体是分错了还是对了,只是在开始的时候告诉他要把这个数据分成多少类,然后后面的操作都是由他自己完成,完全没有人为的让他进行分类的学习,也没有帮助他纠正错误,所以k-means算法也是一种无监督学习方法。
    相信看到这里你对k-means算法的原理也有了一个大概的了解啦。下面我们再来看看这个算法的代码实现吧。

    代码实现

    下面就放一个Andrew Ng 机器学习教程的习题答案吧,把k-means算法的具体流程大概实现了一下:

    function [centroids, idx] = runkMeans(X, initial_centroids, ...
                                          max_iters, plot_progress)
    %RUNKMEANS runs the K-Means algorithm on data matrix X, where each row of X
    %is a single example
    %   [centroids, idx] = RUNKMEANS(X, initial_centroids, max_iters, ...
    %   plot_progress) runs the K-Means algorithm on data matrix X, where each 
    %   row of X is a single example. It uses initial_centroids used as the
    %   initial centroids. max_iters specifies the total number of interactions 
    %   of K-Means to execute. plot_progress is a true/false flag that 
    %   indicates if the function should also plot its progress as the 
    %   learning happens. This is set to false by default. runkMeans returns 
    %   centroids, a Kxn matrix of the computed centroids and idx, a m x 1 
    %   vector of centroid assignments (i.e. each entry in range [1..K])
    %
    
    % Set default value for plot progress
    if ~exist('plot_progress', 'var') || isempty(plot_progress)
        plot_progress = false;
    end
    
    % Plot the data if we are plotting progress
    if plot_progress
        figure;
        hold on;
    end
    
    % Initialize values
    [m n] = size(X);
    K = size(initial_centroids, 1);
    centroids = initial_centroids;
    previous_centroids = centroids;
    idx = zeros(m, 1);
    
    % Run K-Means
    for i=1:max_iters
        
        % Output progress
        fprintf('K-Means iteration %d/%d...\n', i, max_iters);
        if exist('OCTAVE_VERSION')
            fflush(stdout);
        end
        
        % For each example in X, assign it to the closest centroid
        idx = findClosestCentroids(X, centroids);
        
        % Optionally, plot progress here
        if plot_progress
            plotProgresskMeans(X, centroids, previous_centroids, idx, K, i);
            previous_centroids = centroids;
            fprintf('Press enter to continue.\n');
            pause;
        end
        
        % Given the memberships, compute new centroids
        centroids = computeCentroids(X, idx, K);
    end
    
    % Hold off if we are plotting progress
    if plot_progress
        hold off;
    end
    
    end
    

    算法优化

    代价函数(Distortion function)

    要是k-means最后的分类结果最好,也就是要是K-均值最小化,是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和,因此我们可以设计 K-均值的代价函数(又称 畸变函数 Distortion function)为:
    在这里插入图片描述
    其中μ c (i)代表与 x (i) 最近的聚类中心点。 我们的的优化目标也就是要找出使得代价函数最小的 c (1) ,c (2) ,…,c (m) 和μ 1 ,μ 2 ,…,μ k 。
    我们再回顾一下刚才给出的 K-means算法的迭代过程,我们知道,第一个步骤(根据聚类中心分类)是用于减小 c (i) 引起的代价,而第二个步骤(重新定位聚类中心)则是用于减小μ i 引起的代价。所以迭代的过程一定会是每一次迭代都在减小代价函数,如果发生迭代之后代价函数反而增加,则很可能是出现了错误。

    如何选取k值

    对于一个给定没有分类的数据集,最后具体应该分为多少类呢?这确实是一个问题,比如我们前面的那个例子,通过人眼观察,很明显可以分为两类,那么我们选取K值为2,可以得到一个比较好的聚类结果。那如果K选择3或者其他值行不行呢?当然也可以。
    比如下图,有一个数据经过统计之后发现随着K值的增加其畸变函数在不断变小,但是我们发现在k=3时,畸变函数随着k值变化的幅度显著降低,在k>3之后所带来的好处并不是特别明显,所以我们可以选择k=3作为我们的聚类数目。由于其形状像我们人类的肘部,我们也称其为“肘部法则”。
    在这里插入图片描述
    但是实际应用中,k值的变换规律都不是和上图一样存在突变点,多数情况如下图所示:
    在这里插入图片描述
    随着k值的增大,其畸变函数也随着不断减小,根本就不存在明显的拐点。那么这种情况,K值的选择主要还是根据经验以及利用k-means聚类的目的来决定

    聚类中心的初始化

    前面提到代价函数的建立,可以方便我们来对k-means算法的结果进行优化,方便我们察觉出算法迭代过程中的收敛问题,是否达到局部最小化,或者检查算法迭代过程中是否出现问题。而通过k值的选取也可能使我们的代价函数尽量的减小,以得到更好的聚类效果。
    那么还有什么其他优化的方法呢?
    我们还可以通过选取更优的聚类中心来优化聚类效果。
    上面的例图是一个简单的二分类问题,并且不同类之间的界限也比较明显,最后我们得到的聚类结果也相对比较理想。但实际上聚类中心选择的不同,最终的聚类结果肯定也是会不一样的。
    比如对于下面这张图:
    在这里插入图片描述在这里插入图片描述
    我把初始的聚类中心选择在这两个不同的位置,最后导致的分类结果和迭代次数都会不一样。聚类中心的选取主要还是以随机为主,并且初始的时候最好是选择数据中的点。
    对于多分类,甚至还会出现下面这种情况:
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    最后很可能仅仅实现了局部最优,把本来不是一类的多个类分为了一类,或者把本来是一类的分成了多个类,这些都是有可能的。那么对于这种情况怎么办呢?
    对于聚类数目K值较小(K<10)的情况下,我们可以多次随机选取不同聚类中心,最后比较各自迭代完成后的畸变函数值,畸变函数越小,则说明聚类效果更优。但是在k值较大的情况下,比如上百类甚至上千万类,这时候重新选取不同的聚类中心可能就没有很好的效果了。

    展开全文
  • k-means聚类算法,实现了不同点的聚类,能够实现
  • K-means 聚类算法

    2018-06-01 04:22:20
    K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求...
  • K-Means聚类算法

    千次阅读 2017-05-27 21:19:21
    K-Means聚类算法K-Means聚类算法是典型的基于距离的非层次聚类算法,在最小化误差的函数的基础上将数据划分为预设的类数K,采用距离作为相似性的评价标准,即认为两个对象的距离越近,其相似度就越大。1.算法过程: ...

    K-Means聚类算法

    K-Means聚类算法是典型的基于距离的非层次聚类算法,在最小化误差的函数的基础上将数据划分为预设的类数K,采用距离作为相似性的评价标准,即认为两个对象的距离越近,其相似度就越大。

    1.算法过程:

    1. 从N个样本数据中随机选取K个对象作为初始的聚类中心。
    2. 分别计算每个样本到各个聚类中心的距离,将对象分配到距离最近的聚类中。
    3. 所有对象分配完成之后,重新计算K个聚类的中心。
    4. 与前一次计算得到的K个聚类中心相比较,如果聚类中心发生了变化,则执行步骤2。否则就转步骤5。
    5. 当聚类中心不发生变化的时停止并输出聚类的结果。

    在所有的对象分配完成后,重新计算K个聚类中心的时候,对于连续数据,聚类中心选择该簇的均值,但是当样本的一些属性是离散(分类变量)时,均值是无定义的,可以使用K-众数方法。

    2距离的计算

    距离的种类,有三种:
    1)样本与样本。
    2)样本与簇(样本与簇中心)。
    3)簇与簇(簇中心和簇中心)。
    连续属性:
    欧几里得距离; 曼哈吨距离; 闵可夫斯基距离;
    欧几里得距离:这里写图片描述
    曼哈吨距离:这里写图片描述
    闵可夫斯基距离:这里写图片描述

    文档数据(以每个单词作为属性,次数为值,组成一个向量)。
    余弦相似性度量:
    这里写图片描述
    其中a,b为两个向量。

    3目标函数

    使用的是平方和SSE作为聚类质量的目标函数,对于两种不同的聚类结果,选择误差平方和最小的分类结果。

    连续属性的SSE计算公式为:
    这里写图片描述
    文本数据的SSE计算公式为:
    这里写图片描述

    下面对上面公式的符号进行说明:
    Ci:簇i的聚类中心
    K:聚类的簇数
    迭代符下的Ci是第i簇
    x:样本

    展开全文
  • 自适应的k-means聚类算法SA-K-means.pdf
  • 介绍了K-means 聚类算法的目标函数、算法流程,并列举了一个实例,指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法,...
  • K-means聚类算法研究.pdf
  • K-Means聚类算法及其改进
  • k-means聚类算法 k-means是发现给定数据集的k个簇的算法,也就是将数据集聚合为k类的算法。 算法过程如下: 1)从N个文档随机选取K个文档作为质心 2)对剩余的每个文档测量其到每个质心的距离,并把它归到最近的质心...
  • K-means聚类算法的研究.pdf
  • K-means聚类算法研究浅析.pdf
  • K-means聚类算法及改进.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,209
精华内容 15,283
关键字:

k-means聚类算法