k-means 订阅
k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法,其步骤是,预将数据分为K组,则随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小。 展开全文
k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法,其步骤是,预将数据分为K组,则随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小。
信息
提出时间
1967年
提出者
James MacQueen
类    型
聚类算法
中文名
K均值聚类算法
应    用
数据分析,信号处理,机器学习
外文名
k-means clustering algorithm
K均值聚类算法定义
聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程,聚类就是一种发现这种内在结构的技术,聚类技术经常被称为无监督学习。k均值聚类是最著名的划分聚类算法,由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目k,k由用户指定,k均值算法根据某个距离函数反复把数据分入k个聚类中。
收起全文
精华内容
参与话题
问答
  • Kmeans learn URL https://blog.csdn.net/loveliuzz/article/details/78783773

    这里写图片描述
    Kmeans
    learn URL
    https://blog.csdn.net/loveliuzz/article/details/78783773
    spark MLlib kmeans 参数解释:
    https://www.ibm.com/developerworks/cn/opensource/os-cn-spark-practice4/
    这里写图片描述

    优点:
    1、解决聚类问题的经典算法,简单、快速
    2、当处理大数据集时,该算法保持可伸缩性和高效率
    3、当簇近似为高斯分布时,它的效果较好
    缺点:
    1、在簇的平均值可被定义的情况下才能使用,可能不适用于某些应用
    2、必须实现给出k(要生成簇的数目),而且对初值敏感,即对于不同的初值,可能会导致不同结果
    3、不适合非凸形状的簇或者大小差别很大的簇
    4、对噪声和孤立点敏感
    思想
    1,选择K个点作为初始质心
    2,repeat
    将每个点指派到最近的质心,形成K个簇
    重新计算每个簇的质心
    until 簇不发生变化或达到最大迭代次数
    缺陷
    1. K值需要预先给定,属于预先知识,很多情况下K值的估计是非常困难的,对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景,可以进行迭代运算,然后找出Cost Function最小时所对应的K值,这个值往往能较好的描述有多少个簇类。
    2. K-Means算法对初始选取的聚类中心点是敏感的,不同的随机种子点得到的聚类结果完全不同
    3. K均值算法并不是很所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇,银冠指定足够大的簇的个数是他通常可以发现纯子簇。
    4. 对离群点的数据进行聚类时,K均值也有问题

    K-mediods算法
    算法流程:
    a) 首先随机选取一组聚类样本作为中心点集
    b) 每个中心点对应一个簇
    c) 计算各样本点到各个中心点的距离(如欧几里德距离),将样本点放入距离中心点最短的那个簇中
    d) 计算各簇中,距簇内各样本点距离的绝度误差最小的点,作为新的中心点
    e) 如果新的中心点集与原中心点集相同,算法终止;如果新的中心点集与原中心点集不完全相同,返回b)
    举例
    a) 设有(A,B,C,D,E,F)一组样本
    b) 随机选择B、E为中心点
    c) 计算D和F到B的距离最近,A和C到E的距离最近,则B,D,F为簇X1,A,C,E为簇X2
    d) 计算X1发现,D作为中心点的绝对误差最小,X2中依然是E作为中心点绝对误差最小
    e) 重新以D、E作为中心点,重复c)、d)步骤后,不再变换,则簇划分确定。
    优缺点
    a) K-mediods算法具有能够处理大型数据集,结果簇相当紧凑,并且簇与簇之间明显分明的优点,这一点和K-means算法相同。
    b) 该算法也有K-means同样的缺点,如:必须事先确定类簇数和中心点,簇数和中心点的选择对结果影响很大;一般在获得一个局部最优的解后就停止了;对于除数值型以外的数据不适合;只适用于聚类结果为凸形的数据集等。
    c) 与K-means相比,K-mediods算法对于噪声不那么敏感,这样对于离群点就不会造成划分的结果偏差过大,少数数据不会造成重大影响。
    d) K-mediods由于上述原因被认为是对K-means的改进,但由于按照中心点选择的方式进行计算,算法的时间复杂度也比K-means上升了O(n)。
    层次聚类
    great learning URL
    http://home.deib.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html
    http://bluewhale.cc/2016-04-19/hierarchical-clustering.html
    二分K-均值(bisecting K-means)
    一种层次聚类方法
    主要思想是:首先将所有点作为一个簇,然后将该簇一分为二。之后选择能最大程度降低聚类代价函数(也就是误差平方和)的簇划分为两个簇。以此进行下去,直到簇的数目等于用户给定的数目K为止。
    以上隐含着一个原则是:因为聚类的误差平方和能够衡量聚类性能,该值越小表示数据点月接近于它们的质心,聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次的划分,因为误差平方和越大,表示该簇聚类越不好,越有可能是多个簇被当成一个簇了,所以我们首先需要对这个簇进行划分。
    伪代码:
    1)将所有的点看成一个簇
    2)当簇数目小于k时
    对每一个簇:
    计算总误差
    在给定的簇上面进行k-均值聚类k=2
    计算将该簇一分为二后的总误差
    选择使得误差最小的那个簇进行划分操作
    优缺点
    同k-means算法一样,Bisecting k-means算法不适用于非球形簇的聚类,而且不同尺寸和密度的类型的簇,也不太适合。

    基于密度聚类算法的主要特点是:
      (1) 发现任意形状的簇
      (2) 处理噪声
      (3) 一次扫描
      (4) 需要密度参数作为终止条件
      
    DBSCAN
    具有噪声应用的基于密度的空间聚类
    找出核心对象,即其领域稠密的对象。它连接核心对象和它们的领域,形成稠密区域作为簇
    伪代码:
    这里写图片描述
    (1) 首先将数据集D中的所有对象标记为未处理状态
    (2) for(数据集D中每个对象p) do
    (3) if (p已经归入某个簇或标记为噪声) then
    (4) continue;
    (5) else
    (6) 检查对象p的Eps邻域 NEps(p) ;
    (7) if (NEps(p)包含的对象数小于MinPts) then
    (8) 标记对象p为边界点或噪声点;
    (9) else
    (10) 标记对象p为核心点,并建立新簇C, 并将p邻域内所有点加入C
    (11) for (NEps(p)中所有尚未被处理的对象q) do
    (12) 检查其Eps邻域NEps(q),若NEps(q)包含至少MinPts个对象,则将NEps(q)中未归入任何一个簇的对象加入C;
    (13) end for
    (14) end if
    (15) end if
    (16) end for
    优点:
    1. 与K-means方法相比,DBSCAN不需要事先知道要形成的簇类的数量。
    2. 与K-means方法相比,DBSCAN可以发现任意形状的簇类。
    3. 同时,DBSCAN能够识别出噪声点。对离群点有较好的鲁棒性,甚至可以检测离群点。
    4.DBSCAN对于数据库中样本的顺序不敏感,即Pattern的输入顺序对结果的影响不大。但是,对于处于簇类之间边界样本,可能会根据哪个簇类优先被探测到而其归属有所摆动。
    5.DBSCAN被设计与数据库一同使用,可以加速区域的查询。例如 使用R*树
    缺点:
    1. DBScan不能很好反映高维数据。
    2. DBScan不能很好反映数据集以变化的密度。
    3. 输入参数敏感,确定参数Eps , MinPts困难 ,若选取不当 ,将造成聚类质量下降。
    4. 由于经典的DBSCAN算法中参数Eps和MinPts在聚类过程中是不变的,使得该算法难以适应密度不均匀的数据集
    STING统计信息表格
    一个基于网格的多分辨率聚类技术,它将空间区域划分为矩形单元。针对不同级别的分辨率,通常存在多个级别的矩形单元,这些单元形成了一个层次结构:高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息(例如平均值,最大值,和最小值)被预先计算和存储。这些统计变量可以方便下面描述的查询处理使用。 高层单元的统计变量可以很容易地从低层单元的变量计算得到。这些统计变量包括:属性无关的变量 count;属性相关的变量 m(平均值),s(标准偏差),min(最小值),max(最大值),以及该单元中属性值遵循的分布类型 distribution,例如正态的,均衡的,指数的,或无(如果分布未知)。当数据被装载进数据库,最底层单元的变量 count,m,s,min,和 max 直接进行计算。如果分布的类型事先知道,distribution 的值可以由用户指定,也可以通过假设检验来获得。一个高层单元的分布类型可以基于它对应的低层单元多数的分布类型,用一个阈值过滤过程来计算。如果低层单元的分布彼此不同,阈值检验失败,高层单元的分布类型被置为 none。
    网格中常用的参数:
      (1) count 网格中对象数目
      (2) mean网格中所有值的平均值
      (3) stdev网格中属性值的标准偏差
      (4) min 网格中属性值的最小值
      (5) max 网格中属性值的最大值
      (6) distribution 网格中属性值符合的分布类型。如正分布,均匀分布
    优点:
     (1) 基于网格的计算是独立于查询的,因为存储在每个单元的统计信息提供了单元中数据汇总信息,不依赖于查询。
     (2) 网格结构有利于增量更新和并行处理。
     (3) 效率高。STING扫描数据库一次开计算单元的统计信息,因此产生聚类的时间复杂度为O(n),在层次结构建立之后,查询处理时间为)O(g),其中g为最底层网格单元的数目,通常远远小于n。
     缺点:
     (1) 由于STING采用了一种多分辨率的方法来进行聚类分析,因此STING的聚类质量取决于网格结构的最底层的粒度。如果最底层的粒度很细,则处理的代价会显著增加。然而如果粒度太粗,聚类质量难以得到保证。
     (2) STING在构建一个父亲单元时没有考虑到子女单元和其他相邻单元之间的联系。所有的簇边界不是水平的,就是竖直的,没有斜的分界线。降低了聚类质量。
     与其它聚类算法相比,STING有几个优点:
    (1)由于存储在每个单元中的统计信息描述了单元中数据的与查询无关的概要信息,所以基于网格的计算是独立于查询的;
    (2)网格结构有利于并行处理和增量更新;
    (3)该方法的效率很高:STING 扫描数据库一次来计算单元的统计信息,因此产生聚类的时间复杂度是 O(n),n 是对象的数目。

    展开全文
  • 假设,我们的样本如上图分布,准备选择3个初始点,即k=3。 第一,我随机选择了1作为初始点,求所有样本点与已选择的聚类中心中最近聚类中心的距离(现在只有点1),求出其他所有点与点1的距...

    上文原始Kmeans提到,由于Kmeans使用启发式迭代,所以当初始点不当时,导致得不到全局最优。

    Kmeans++

    这个算法思想也很简单,与原始Kmeans唯一不同的是选择初始点的方式。

    如图

     

    假设,我们的样本如上图分布,准备选择3个初始点,即k=3。

    第一,我随机选择了1作为初始点,求所有样本点与已选择的聚类中心中最近聚类中心的距离(现在只有点1),求出其他所有点与点1的距离D(xi),选择最大的。

    第二,我们现在选到了点9作为初始点(与1距离最远),然后所有样本点与已选择的聚类中心中最近聚类中心的距离,对于点2,3,4,5,6应求到1的距离,7,8求到9的距离,取最大的D(x),

    应该是点1到点4最大,那么点4倍被选为初始点。

    那么一共选出了点1,9,4作为初始点。

     可以重复一、二步骤,选出多个初始点。

     

    elkan K-Means

    Kmeans一文我们知道,一次质心的更新需要将所有样本点到质心的距离都算一次,比较耗时

    elkan K-Means的思想是

    针对一个样本点,两个质心,如果提前知道质心之间的距离D(a1,a2),那么

    当2D(x,a1)≤D(a1,a2), 必有D(x,a1)≤D(x,a2),不必计算D(x,a2)

    这一条不太明白,原理是三角形任意一边大于等于其他两边之差,怎么简化计算,不得而知

     

    大样本Mini Batch K-Means

    思想更简单,对大样本进行无放回随机抽样,抽取多次保证准确性。 

     

    Sequential Leader Clustering

    这种方法不用预先设定K值,不需要迭代,只需将数据过一遍。需要设定一个阈值T。

    用下图说明该思想

    第一,任意一个数据点(假如是点1)作为质心,依次算出其他2-9到质心1的距离d,若d<T(阈值),认为这两个点属于一个簇

    第二,若某样本点与现有质心的距离大于阈值T,则将这个点作为另一个质心。

    重复上述两步

    缺点:阈值的设定没有依据。

     

     

     

    参考https://www.cnblogs.com/pinard/p/6164214.html

    https://www.bilibili.com/video/av23933161/?p=30

    转载于:https://www.cnblogs.com/super-yb/p/10862831.html

    展开全文
  • kmeans的计算方法如下: 随机选取k个中心点 遍历所有数据,将每个数据划分到最近的中心点中 计算每个聚类的平均值,并作为新的中心点 重复 2-3 ,直到这k个中线点不再变化(收敛了),或执行了...

    1. K-means 算法原理(距离度量采用欧式距离)

    1. 随机选取k个簇中心点

    2. 遍历所有数据,将每个数据划分到欧式距离最近的中心点中

    3. 计算每个聚类的平均值,并作为新的簇中心点

    4. 重复2-3,直到某个中止条件

    中止条件:
    • 簇中心变化率收敛
    • 足够多的迭代
    • 最小平方误差MSE,非凸,采用迭代逼近局部最优。

    注意,若不是采用欧式距离,簇中心的更新方式也随之不同,比如采用曼哈顿距离(绝对值),则不采用平均值,采用中值

    2. Kmean算法推导

    注意:使用不同的距离度量,簇中心 的跟新公式便不一样。推导如下:
    在这里插入图片描述

    3. kmeans的优缺点

    缺点:
    • K值是用户给定的,且对聚类结果影响很大(一般交叉验证选取)。
    • 对初始的簇中心敏感(由此提出 二分K-means、Kmeans++进行改进)
    • 利群值对模型影响很大(如2,4,6,8,100;这种数据样本可采用K中值算法,即选取中间值作为更新簇)
    • 不适合发现大小差别很大的簇
    优点:
    • 簇类似高斯分布时,效果会不错
    • 简单,容易理解

    4. 二分Kmeans算法 K-means++

    二分K-means、Kmeans++

    Kmeans++ :
    • 并不是随机给定簇中心点,而是先随机选取一个初始簇中心,然后选一个离前k个簇中心较远的另一个点成为下一个簇中心,具体为计算 每一个样本xix_i,离k个簇中心的最短距离 dminid_{min}^i,然后找出最大的dminid_{min}^i .
    二分Kmeans算法
    • 每次从队列中出来一个簇,分成两个字簇,再进队;循环至簇数等于K
    展开全文
  • 之前一直用R,现在开始学python之后就来...有三类比较常见的聚类模型,K-mean聚类、层次(系统)聚类、最大期望EM算法。在聚类模型建立过程中,一个比较关键的问题是如何评价聚类结果如何,会用一些指标来评价。 ....

    之前一直用R,现在开始学python之后就来尝试用Python来实现Kmeans。
    之前用R来实现kmeans的博客:笔记︱多种常见聚类模型以及分群质量评估(聚类注意事项、使用技巧)

    聚类分析在客户细分中极为重要。有三类比较常见的聚类模型,K-mean聚类、层次(系统)聚类、最大期望EM算法。在聚类模型建立过程中,一个比较关键的问题是如何评价聚类结果如何,会用一些指标来评价。
    .


    一、scikit-learn中的Kmeans介绍

    scikit-learn 是一个基于Python的Machine Learning模块,里面给出了很多Machine
    Learning相关的算法实现,其中就包括K-Means算法。

    官网scikit-learn案例地址:http://scikit-learn.org/stable/modules/clustering.html#k-means
    部分来自:scikit-learn 源码解读之Kmeans——简单算法复杂的说
    这里写图片描述

    各个聚类的性能对比:
    这里写图片描述

    优点:
    
    原理简单
    速度快
    对大数据集有比较好的伸缩性
    
    缺点:
    
    需要指定聚类 数量K
    对异常值敏感
    对初始值敏感
    

    1、相关理论

    参考:K-means算法及文本聚类实践

    • (1)中心点的选择

    k-meams算法的能够保证收敛,但不能保证收敛于全局最优点,当初始中心点选取不好时,只能达到局部最优点,整个聚类的效果也会比较差。可以采用以下方法:k-means中心点

    选择彼此距离尽可能远的那些点作为中心点;
    先采用层次进行初步聚类输出k个簇,以簇的中心点的作为k-means的中心点的输入。
    多次随机选择中心点训练k-means,选择效果最好的聚类结果

    • (2)k值的选取

    k-means的误差函数有一个很大缺陷,就是随着簇的个数增加,误差函数趋近于0,最极端的情况是每个记录各为一个单独的簇,此时数据记录的误差为0,但是这样聚类结果并不是我们想要的,可以引入结构风险对模型的复杂度进行惩罚:

    这里写图片描述

    λλ是平衡训练误差与簇的个数的参数,但是现在的问题又变成了如何选取λλ了,有研究[参考文献1]指出,在数据集满足高斯分布时,λ=2mλ=2m,其中m是向量的维度。

    另一种方法是按递增的顺序尝试不同的k值,同时画出其对应的误差值,通过寻求拐点来找到一个较好的k值,详情见下面的文本聚类的例子。

    2、主函数KMeans

    参考博客:python之sklearn学习笔记
    来看看主函数KMeans:

    sklearn.cluster.KMeans(n_clusters=8,
    	 init='k-means++', 
    	n_init=10, 
    	max_iter=300, 
    	tol=0.0001, 
    	precompute_distances='auto', 
    	verbose=0, 
    	random_state=None, 
    	copy_x=True, 
    	n_jobs=1, 
    	algorithm='auto'
    	)
    

    参数的意义:

    • n_clusters:簇的个数,即你想聚成几类
    • init: 初始簇中心的获取方法
    • n_init: 获取初始簇中心的更迭次数,为了弥补初始质心的影响,算法默认会初始10次质心,实现算法,然后返回最好的结果。
    • max_iter: 最大迭代次数(因为kmeans算法的实现需要迭代)
    • tol: 容忍度,即kmeans运行准则收敛的条件
    • precompute_distances:是否需要提前计算距离,这个参数会在空间和时间之间做权衡,如果是True 会把整个距离矩阵都放到内存中,auto 会默认在数据样本大于featurs*samples 的数量大于12e6 的时候False,False 时核心实现的方法是利用Cpython 来实现的
    • verbose: 冗长模式(不太懂是啥意思,反正一般不去改默认值)
    • random_state: 随机生成簇中心的状态条件。
    • copy_x: 对是否修改数据的一个标记,如果True,即复制了就不会修改数据。bool 在scikit-learn 很多接口中都会有这个参数的,就是是否对输入数据继续copy 操作,以便不修改用户的输入数据。这个要理解Python 的内存机制才会比较清楚。
    • n_jobs: 并行设置
    • algorithm: kmeans的实现算法,有:‘auto’, ‘full’, ‘elkan’, 其中 'full’表示用EM方式实现

    虽然有很多参数,但是都已经给出了默认值。所以我们一般不需要去传入这些参数,参数的。可以根据实际需要来调用。

    3、简单案例一

    参考博客:python之sklearn学习笔记
    本案例说明了,KMeans分析的一些类如何调取与什么意义。

    import numpy as np
    from sklearn.cluster import KMeans
    data = np.random.rand(100, 3) #生成一个随机数据,样本大小为100, 特征数为3
    
    #假如我要构造一个聚类数为3的聚类器
    estimator = KMeans(n_clusters=3)#构造聚类器
    estimator.fit(data)#聚类
    label_pred = estimator.labels_ #获取聚类标签
    centroids = estimator.cluster_centers_ #获取聚类中心
    inertia = estimator.inertia_ # 获取聚类准则的总和
    

    estimator初始化Kmeans聚类;estimator.fit聚类内容拟合;
    estimator.label_聚类标签,这是一种方式,还有一种是predict;estimator.cluster_centers_聚类中心均值向量矩阵
    estimator.inertia_代表聚类中心均值向量的总和

    4、案例二

    案例来源于:使用scikit-learn进行KMeans文本聚类

    from sklearn.cluster import KMeans
     
    num_clusters = 3
    km_cluster = KMeans(n_clusters=num_clusters, max_iter=300, n_init=40, \
                        init='k-means++',n_jobs=-1)
    
    #返回各自文本的所被分配到的类索引
    result = km_cluster.fit_predict(tfidf_matrix)
     
    print "Predicting result: ", result
    

    km_cluster是KMeans初始化,其中用init的初始值选择算法用’k-means++’;
    km_cluster.fit_predict相当于两个动作的合并:km_cluster.fit(data)+km_cluster.predict(data),可以一次性得到聚类预测之后的标签,免去了中间过程。

    • n_clusters: 指定K的值
    • max_iter: 对于单次初始值计算的最大迭代次数
    • n_init: 重新选择初始值的次数
    • init: 制定初始值选择的算法
    • n_jobs: 进程个数,为-1的时候是指默认跑满CPU
    • 注意,这个对于单个初始值的计算始终只会使用单进程计算,
    • 并行计算只是针对与不同初始值的计算。比如n_init=10,n_jobs=40,
    • 服务器上面有20个CPU可以开40个进程,最终只会开10个进程

    其中:

    km_cluster.labels_
    km_cluster.predict(data)
    

    这是两种聚类结果标签输出的方式,结果貌似都一样。都需要先km_cluster.fit(data),然后再调用。

    5、案例四——Kmeans的后续分析

    Kmeans算法之后的一些分析,参考来源:用Python实现文档聚类

    from sklearn.cluster import KMeans
     
    num_clusters = 5
     
    km = KMeans(n_clusters=num_clusters)
     
    %time km.fit(tfidf_matrix)
     
     
    clusters = km.labels_.tolist()
    

    分为五类,同时用%time来测定运行时间,把分类标签labels格式变为list。

    • (1)模型保存与载入
    from sklearn.externals import joblib
     
    # 注释语句用来存储你的模型
    joblib.dump(km,  'doc_cluster.pkl')
    km = joblib.load('doc_cluster.pkl')
    clusters = km.labels_.tolist()
    
    • (2)聚类类别统计
    frame = pd.DataFrame(films, index = [clusters] , columns = ['rank', 'title', 'cluster', 'genre'])
    frame['cluster'].value_counts()
    
    • (3)质心均值向量计算组内平方和

    选择更靠近质心的点,其中 km.cluster_centers_代表着一个 (聚类个数*维度数),也就是不同聚类、不同维度的均值。
    该指标可以知道:
    一个类别之中的,那些点更靠近质心;
    整个类别组内平方和。

    类别内的组内平方和要参考以下公式:
    这里写图片描述
    这里写图片描述
    通过公式可以看出:
    质心均值向量每一行数值-每一行均值(相当于均值的均值)
    注意是平方。其中,n代表样本量,k是聚类数量(譬如聚类5)
    其中,整篇的组内平方和可以通过来获得总量:

    km.inertia_
    

    .


    **公众号“素质云笔记”定期更新博客内容:**
    ![这里写图片描述](https://img-blog.csdn.net/20180226155348545?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc2luYXRfMjY5MTczODM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)

    二、大数据量下的Mini-Batch-KMeans算法

    部分内容参考来源:scikit-learn学习之K-means聚类算法与 Mini Batch K-Means算法
    当数据量很大的时候,Kmeans 显然还是很弱的,会比较耗费内存速度也会收到很大影响。scikit-learn 提供了MiniBatchKMeans算法,大致思想就是对数据进行抽样,每次不使用所有的数据来计算,这就会导致准确率的损失。

    MiniBatchKmeans 继承自Kmeans 因为MiniBathcKmeans 本质上还利用了Kmeans 的思想.从构造方法和文档大致能看到这些参数的含义,了解了这些参数会对使用的时候有很大的帮助。batch_size 是每次选取的用于计算的数据的样本量,默认为100.

    Mini Batch K-Means算法是K-Means算法的变种,采用小批量的数据子集减小计算时间,同时仍试图优化目标函数,这里所谓的小批量是指每次训练算法时所随机抽取的数据子集,采用这些随机产生的子集进行训练算法,大大减小了计算时间,与其他算法相比,减少了k-均值的收敛时间,小批量k-均值产生的结果,一般只略差于标准算法。

    该算法的迭代步骤有两步:
    1:从数据集中随机抽取一些数据形成小批量,把他们分配给最近的质心
    2:更新质心
    与K均值算法相比,数据的更新是在每一个小的样本集上。对于每一个小批量,通过计算平均值得到更新质心,并把小批量里的数据分配给该质心,随着迭代次数的增加,这些质心的变化是逐渐减小的,直到质心稳定或者达到指定的迭代次数,停止计算
    Mini Batch K-Means比K-Means有更快的 收敛速度,但同时也降低了聚类的效果,但是在实际项目中却表现得不明显
    一张k-means和mini batch k-means的实际效果对比图
    这里写图片描述

    来看一下 MiniBatchKMeans的python实现:
    官网链接案例一则链接

    主函数 :

    MiniBatchKMeans(n_clusters=8, init=’k-means++’, max_iter=100, batch_size=100, verbose=0, compute_labels=True, random_state=None, 
    tol=0.0, max_no_improvement=10, init_size=None, n_init=3, reassignment_ratio=0.01)
    

    相关参数解释(来自博客:用scikit-learn学习K-Means聚类):

    • random_state: 随机生成簇中心的状态条件,譬如设置random_state = 9

    • tol: 容忍度,即kmeans运行准则收敛的条件

    • max_no_improvement:即连续多少个Mini Batch没有改善聚类效果的话,就停止算法,
      和reassignment_ratio, max_iter一样是为了控制算法运行时间的。默认是10.一般用默认值就足够了。

    • batch_size:即用来跑Mini Batch
      KMeans算法的采样集的大小,默认是100.如果发现数据集的类别较多或者噪音点较多,需要增加这个值以达到较好的聚类效果。

    • reassignment_ratio:
      某个类别质心被重新赋值的最大次数比例,这个和max_iter一样是为了控制算法运行时间的。这个比例是占样本总数的比例,
      乘以样本总数就得到了每个类别质心可以重新赋值的次数。如果取值较高的话算法收敛时间可能会增加,尤其是那些暂时拥有样本数较少的质心。
      默认是0.01。如果数据量不是超大的话,比如1w以下,建议使用默认值。 如果数据量超过1w,类别又比较多,可能需要适当减少这个比例值。
      具体要根据训练集来决定。

    import time
    
    import numpy as np
    import matplotlib.pyplot as plt
    
    from sklearn.cluster import MiniBatchKMeans, KMeans
    from sklearn.metrics.pairwise import pairwise_distances_argmin
    from sklearn.datasets.samples_generator import make_blobs
    
    # 获取数据
    np.random.seed(0)
    
    batch_size = 45
    centers = [[1, 1], [-1, -1], [1, -1]]
    n_clusters = len(centers)
    X, labels_true = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7)
    
    # kmeans
    # Compute clustering with Means
    
    k_means = KMeans(init='k-means++', n_clusters=3, n_init=10)
    t0 = time.time()
    k_means.fit(X)
    t_batch = time.time() - t0
    
    # MiniBatchKMeans
    
    mbk = MiniBatchKMeans(init='k-means++', n_clusters=3, batch_size=batch_size,
                          n_init=10, max_no_improvement=10, verbose=0)
    t0 = time.time()
    mbk.fit(X)
    t_mini_batch = time.time() - t0
    
    

    内容跟kmeans很像,只是一般多加一个参数,batch_size。

    .


    三、sklearn中的cluster进行kmeans聚类

    参考博客:python之sklearn学习笔记

    import numpy as np
    from sklearn import cluster
    data = np.random.rand(100, 3) #生成一个随机数据,样本大小为100, 特征数为3
    k = 3 # 假如我要聚类为3个clusters
    [centroid, label, inertia] = cluster.k_means(data, k)
    

    四、分类变量聚类方法的K-modes与K-prototype

    K-prototype与K-modes

    K-modes是K-means用在非数值集合上的一种方法,将原本K-means使用的欧式距离替换成字符间的汉明距离。
    用去分类变量

    K-prototype是K-means与K-modes的一种集合形式,适用于数值类型与字符类型集合的数据。

    1. 度量具有混合属性的方法是,数值属性采用K-means方法得到P1,分类属性采用K-modes方法P2,那么D=P1+a*P2,a是权重。如果觉得分类属性重要,则增加a,否则减少a,a=0时即只有数值属性
    2. 更新一个簇的中心的方法,方法是结合K-means与K-modes的更新。

    code实现可参考:nicodv/kmodes


    **公众号“素质云笔记”定期更新博客内容:**
    ![这里写图片描述](https://img-blog.csdn.net/20180226155348545?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc2luYXRfMjY5MTczODM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)

    .


    延伸一:数据如何做标准化

    data_zs = 1.0*(data - data.mean())/data.std() #数据标准化
    

    .

    延伸二:Kmeans可视化案例

    来源于博客:使用python-sklearn-机器学习框架针对140W个点进行kmeans基于密度聚类划分

    from sklearn.cluster import KMeans
    from sklearn.externals import joblib
    import numpy
    import time
    import matplotlib.pyplot as plt
     
    if __name__ == '__main__':
        ## step 1: 加载数据
        print "step 1: load data..."
        dataSet = []
        fileIn = open('./data.txt')
        for line in fileIn.readlines():
            lineArr = line.strip().split(' ')
            dataSet.append([float(lineArr[0]), float(lineArr[1])])
     
        #设定不同k值以运算
        for k in range(2,10):
            clf = KMeans(n_clusters=k) #设定k  !!!!!!!!!!这里就是调用KMeans算法
            s = clf.fit(dataSet) #加载数据集合
            numSamples = len(dataSet) 
            centroids = clf.labels_
            print centroids,type(centroids) #显示中心点
            print clf.inertia_  #显示聚类效果
            mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
            #画出所有样例点 属于同一分类的绘制同样的颜色
            for i in xrange(numSamples):
                #markIndex = int(clusterAssment[i, 0])
                plt.plot(dataSet[i][0], dataSet[i][1], mark[clf.labels_[i]]) #mark[markIndex])
            mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
            # 画出质点,用特殊图型
            centroids =  clf.cluster_centers_
            for i in range(k):
                plt.plot(centroids[i][0], centroids[i][1], mark[i], markersize = 12)
                #print centroids[i, 0], centroids[i, 1]
            plt.show()
    

    这里写图片描述

    延伸三:模型保存

    from sklearn.externals import joblib
    joblib.dump(km_cluster, "/..../train_model.m")
    km_cluster = joblib.load(".../train_model.m")
    kmeans_SSE.labels_
    

    延伸四:HDBSCAN与Kmeans的聚类的一些纪要

    如果输入数据的变量类型不同,部分是数值型(numerical),部分是分类变量(categorical),需要做特别处理。

    方法1是将分类变量转化为数值型,但缺点在于如果使用独热编码(one hot encoding)可能会导致数据维度大幅度上升,如果使用标签编码(label encoding)无法很好的处理数据中的顺序(order)。方法2是对于数值型变量和分类变量分开处理,并将结果结合起来,具体可以参考Python的实现[1],如K-mode和K-prototype。

    输出结果非固定,多次运行结果可能不同。

    首先要意识到K-means中是有随机性的,从初始化到收敛结果往往不同。一种看法是强行固定随机性,比如设定sklearn中的random state为固定值。另一种看法是,如果你的K均值结果总在大幅度变化,比如不同簇中的数据量在多次运行中变化很大,那么K均值不适合你的数据,不要试图稳定结果 [2]

    运行效率与性能之间的取舍。

    但数据量上升到一定程度时,如>10万条数据,那么很多算法都不能使用。最近读到的一篇对比不同算法性能随数据量的变化很有意思 [Benchmarking Performance and Scaling of Python Clustering Algorithms]。在作者的数据集上,当数据量超过一定程度时仅K均值和HDBSCAN可用。

    在这里插入图片描述
    在这里插入图片描述

    因此不难看出,K均值算法最大的优点就是运行速度快,能够处理的数据量大,且易于理解。但缺点也很明显,就是算法性能有限,在高维上可能不是最佳选项。

    一个比较粗浅的结论是,在数据量不大时,可以优先尝试其他算法。当数据量过大时,可以试试HDBSCAN。仅当数据量巨大,且无法降维或者降低数量时,再尝试使用K均值。

    一个显著的问题信号是,如果多次运行K均值的结果都有很大差异,那么有很高的概率K均值不适合当前数据,要对结果谨慎的分析。

    此外无监督聚类的评估往往不易,基本都是基于使用者的主观设计,如sklearn中提供的Silhouette Coefficient和 Calinski-Harabaz Index [5]。更多关于无监督学习如何评估可以参考 [微调:一个无监督学习算法,如何判断其好坏呢?]。
    参考:如何正确使用「K均值聚类」?

    展开全文
  • 一、k-means 1、简述 K-Means是一种无监督学习算法。算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本集划分为K个簇。让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大。 2、K-means算法...
  • 原始的kmeans算法随机的选取数据中的k个点作为聚类中心,因此每次聚类的效果可能会有很大的区别,而且初始点选的不好,会很大程度上影响聚类的结果,为了解决此问题引入了K-means++,它的核心思想是:  a, 在数据...
  • K-Means 系列:K-Means,二分K-MeansK-Means++,K-Meansll,canopy算法,MiniBatchK-Means算法。 K-Means系列聚类算法原理:https://www.cnblogs.com/pinard/p/6164214.html 用scikit-learn学习K-Means聚类:...
  • K-Means 二维数据 聚类分析 数据样本及聚类要求 二维数据曼哈顿距离计算 K-Means 算法 步骤 第一次迭代 : 步骤 ( 1 ) 中心点初始化 第一次迭代 : 步骤 ( 2 ) 计算距离 第一次迭代 : 步骤 ( 3 ) 聚类分组 第二次迭代 ...
  • ====================================================================== 本系列博客主要参考 Scikit-Learn 官方网站上的每一个算法进行,并进行部分翻译,如有错误,请大家指正 转载请注明出处 ...
  • 通过绘制K-means代价函数与聚类数目K的关系图,选取直线拐点处的K值作为最佳的聚类中心数目。 但最好还是从实际问题出发,人工指定比较合理的K值,通过多次随机初始化聚类中心选取比较满意的结果。 k-means++算法 ...
  • K-Means

    2019-05-16 20:39:47
    K-Means K-Means的工作原理: 随机选取K个点作为初始的类中心点 将每个点分配到最近的类中心点,然后重新计算每个类的中心点 重复第二步,直到类不发生变化,或...KMeans(n_clusters=8, init='k-means++', n_init...
  • kmeans:是用Go编写的k-means聚类算法实现
  • 聚类问题是机器学习中无监督学习的典型代表,在数据分析、模式识别的很多实际问题中得到了应用。我们知道,分类问题是机器学习中最常见的一类问题,它的目标是确定一个物体所属的类别。分类问题和聚类问题一个最重要...
  • R----kmeans

    2017-08-28 17:06:45
    K-means 算法是很经典的基于距离的无监督硬聚类算法。算法认为对象距离近的, 其相似度越大。算法最终会得到一个,簇内距离尽量小,不同簇间距离尽量大的一个分类结果。 1.对样本进行初始聚类(离哪个近就归到那...
  • 遗传k-means 遗传算法 演化算法 聚类算法 k-means 遗传k-means 遗传算法 演化算法 聚类算法 k-means 遗传k-means 遗传算法 演化算法 聚类算法 k-means
  • 03 聚类算法 - K-means聚类04 聚类算法 - 代码案例一 - K-means聚类 三、K-Means算法衍生 1、二分K-Means算法 解决K-Means算法对__初始簇心__比较敏感的问题,二分K-Means算法是一种弱化初始质心的一种算法,__具体...
  • 上一篇文章中,我在最后有说到,K-means算法由于初始“聚类中心”点是随机选取的,因此最终求得的簇的划分与随机选取的“聚类中心”有关,也就是说,可能会造成多种 k 个簇的划分情况。这是因为K-means算法收敛到了...
  • K-Means(聚类)

    万次阅读 多人点赞 2019-02-28 11:26:02
    说到聚类,应先理解聚类和分类的区别,很多业务人员在日常分析时候不是很严谨,混为一谈,其实二者有本质的区别。 分类:分类其实是从特定的数据中挖掘模式,作出判断的过程。比如Gmail邮箱里有垃圾邮件分类器,...
  • 首先需要明确的是上述四种算法都属于"硬聚类”算法,即数据集中每一个样本都是被100%确定得分到某一个类别中。与之相对的"软聚类”可以理解为每个样本是以一定的概率被分到... K-meansK-means++:原始K...
  • 聚类算法之——k-means,k-means++,Minibatch kmeans 原始K-means算法最开始随机选取数据集中K个点作为聚类中心, 而K-means++按照如下的思想选取K个聚类中心: 假设已经选取了n个初始聚类中心(0<n<K),则...
  • k-means 优缺点:**  1.算法快速、简单;  2.对大数据集有较高的效率并且是可伸缩性的;  3.时间复杂度近于线性,而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(n×k×t) ,其中n代表数据集中对象的...
  • k-means提取图像主色(手写)。 二、opencv-kmeans主色提取 //输入彩色图像 k-means获取主色(颜色中心及比例) void DCD(Mat& src) { if(!src.data) { return; } //分割通道 vector bgr; split(src,...
  • 一文搞懂K-means聚类算法

    千次阅读 2019-12-01 16:09:30
    阅读目录目录聚类K-means(k均值)聚类算法案例描述从文件加载数据集计算两个向量的欧氏距离构建一个包含 K 个随机质心的集合K-Means 聚类算法分析数据:聚类可视化结果讨论与分析算法描述二分 K-Means 聚类算法伪...
  • 数据挖掘---Kmeans算法

    2016-03-19 10:14:01
    聚类算法library(amap) ###Kmeans聚类 ...setwd("E://RProgramming//k-means") getwd() rm(list = ls())## a 2-dimensional example x <- rbind(matrix(rnorm(100, sd = 0.3), ncol = 2), matrix(rnorm(100
  • 关于R与tableau的集成----kmeans聚类

    千次阅读 2016-06-02 10:48:20
    R与tableau集成(聚类) 1.利用R内置数据集iris; 2.通过Rserve 包连接tableau,服务器:localhost,默认...//使用k-means方法对数据进行聚类 SCRIPT_REAL("fit <- kmeans(data.frame(.arg1,.arg2,.arg3,.arg4),cen
  • Spark Kmeans 三种算法分析
  • 创建K个点作为起始质点。每次迭代如下: 将各个数据点分配到离它距离最近的质点的簇。 全部分配后,用各个簇中的数据点的位置均值来更新质点的位置。 直到达到迭代次数,或者所有的数据点所在的簇不再改变。 可参阅...

空空如也

1 2 3 4 5 ... 20
收藏数 19,542
精华内容 7,816
关键字:

k-means