2017-09-16 12:46:56 zhangce315 阅读数 413

K-means 聚类算法
k-means 算法以 k为参数,把 n个对象分成 k个簇,使内具有较高的相似度,而簇间的相似较低。
其处理过程如下:
1. 随机选择 k个点作为初始的聚类中心;
2. 对于剩下的点,根据其与聚类中心距离将归入最近簇
3. 对每个簇,计算所有点的均值作为新聚类中心
4. 重复 2、3直到聚类中心不再发生改变

image.png
K-means 的应用
数据介绍:
现有1999年全国31个省份城镇居民家庭平均每人全年消费性支出的八个主要变量数据,这八个变量分别为:食品、衣着、家庭设备用品及服务、医疗保健、交通和通讯、娱乐教育文化服务、居住以及杂项商品和服务。利用已有数据对31个省份进行聚类。
实验目的:通过聚类了解1999年各个省份的消费水平在国内的情况。


import numpy as np
from sklearn.cluster import KMeans
def loadData(filePath):
    fr = open(filePath,'r+')
    lines = fr.readlines()
    retData = []
    retCityName = []
    for line in lines:
        items = line.strip().split(",")
        retCityName.append(items[0])
        retData.append([float(items[i]) for i in range(1,len(items))])
    return retData,retCityName
if __name__ == '__main__':
    data,cityName = loadData('city.txt')
    km = KMeans(n_clusters = 4)
    label = km.fit_predict(data)
    expenses = np.sum(km.cluster_centers_,axis=1)
    CityCluster = [[],[],[],[]]
    for i in range(len(cityName)):
        CityCluster[label[i]].append(cityName[i])
    for i in range(len(CityCluster)):
        print "Expenses:%.2f" % expenses[i]
        print CityCluster[i]

调用K-Means方法所需参数:
n_clusters 用于指定聚类中心的个数
init:初始聚类中心的初始化方法
max_iter:最大的迭代次数
一般调用时只用给出n_clusters即可,init默认是k-means++,max_iter默认是300
其他参数:
data:加载的数据
label:聚类后个数据所属的标签
axis:按行求和
fit_predict()计算簇中心以及为簇分配序号

实验结果:

runfile('C:/Users/Sean Chang/.spyder/temp.py', wdir='C:/Users/Sean Chang/.spyder')
Expenses:4357.67
['Anhui', 'Hunan', 'Hubei', 'Guangxi', 'Hainan', 'Sichuan']
Expenses:5513.10
['Tianjin', 'Jiangsu', 'Zhejiang', 'Chongqing', 'Yunnan', 'Xizang']
Expenses:7754.66
['Beijing', 'Shanghai', 'Guangdong']
Expenses:3788.76
['Hebei', 'Shanxi', 'Neimong', 'Liaoning', 'Jilin', 'Heilongjiang', 'Jiangxi', 'Shandong', 'Henan', 'Guizhou', 'Shaanxi', 'Gansu', 'Qinghai', 'Ningxia', 'Xinjiang']
2011-03-24 23:28:37 iteye_7668 阅读数 124
K-均值聚类(K-means clustering)是Mac Queen提出的一种非监督实时聚类算法,在最小化误差函数的基础上将数据划分为预定的类数K。该算法原理简单并便于处理大量数据,在基因表达数据分析中得到广泛应用,如Tavazoie等应用K-means聚类酵母细胞周期表达数据。在K-means算法运行前必须先指定聚类数目K和迭代次数或收敛条件,并指定K个初始聚类中心,根据一定的相似性度量准则,将每一条基因分配到最近或“相似”的聚类中心,形成类,然后以每一类的平均矢量作为这一类的聚类中心,重新分配,反复迭代直到类收敛或达到最大的迭代次数。

K-means聚类算法对初始聚类中心依赖性比较大,随机选取初始聚类中心的缺点是如果使得初始聚类中心得到的分类严重偏离全局最优分类,这样算法可能会陷入局部最优值。而且当聚类数比较大的时候,这种缺点更为明显,往往要经过多次聚类才有可能达到较满意的结果。Yeung等提出了采用均连接层次聚类结果初始化K-means聚类中心。此方法有效地排除了随机初始化过程中引入的随机性因素,使得算法成为确定性的,可以得到稳定的聚类结果;而且,这种初始化方式也能够利用数据中的类结构信息,使得聚类质量相对于随机初始化时的平均质量有显著的提高。

K-means聚类算法的一般步骤:

初始化。输入基因表达矩阵作为对象集X,输入指定聚类类数N,并在X中随机选取N个对象作为初始聚类中心。设定迭代中止条件,比如最大循环次数或者聚类中心收敛误差容限。
进行迭代。根据相似度准则将数据对象分配到最接近的聚类中心,从而形成一类。初始化隶属度矩阵。
更新聚类中心。然后以每一类的平均向量作为新的聚类中心,重新分配数据对象。
反复执行第二步和第三步直至满足中止条件。
该算法理论严密,实现简单,已成为很多其它改进算法的基础,但它对初始码书的选择非常敏感。

以上部分为转载内容,———————————————————————————————————————————————————————————

k-means聚类的一个重要缺陷就是,初始中心点的选择,当初始中心点选择不当时,会使得算法容易陷入局部最优,所以很多的初始化的方法,下面这篇论文中,对常用的初始化的方法进行了比较,在实际使用中可以注意参考,能获得比较好的聚类效果。

论文名字是:
A systematic evaluation of different methods for
initializing the K-means clustering algorithm

附件中,是我下载的论文。
2019-08-17 11:03:39 jack_jay_du 阅读数 275

定义

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

Mini Batch KMeans使用了一个种叫做Mini Batch(分批处理)的方法对数据点之间的距离进行计算。Mini Batch的好处是计算过程中不必使用所有的数据样本,而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本量少,所以会相应的减少运行时间,但另一方面抽样也必然会带来准确度的下降。

基本思想

Mini Batch KMeans算法是一种能尽量保持聚类准确性下但能大幅度降低计算时间的聚类模型,采用小批量的数据子集减少计算时间,同时仍试图优化目标函数,这里所谓的Mini Batch是指每次训练算法时随机抽取的数据子集,采用这些随机选取的数据进行训练,大大的减少了计算的时间,减少的KMeans算法的收敛时间,但要比标准算法略差一点,建议当样本量大于一万做聚类时,就需要考虑选用Mini Batch KMeans算法。

算法描述

Mini Batch K-Means每次迭代不采用所有样本,而是每次等量的采样,然后进行中心节点的更新。与K均值算法相比,数据的更新是在每一个小的样本集上。对于每一个小批量,通过计算平均值得到更新质心,并把小批量里的数据分配给该质心,随着迭代次数的增加,这些质心的变化是逐渐减小的,直到质心稳定或者达到指定的迭代次数,停止计算

Mini Batch K-Means比K-Means有更快的 收敛速度,但同时也降低了聚类的效果,但是在实际项目中却表现得不明显

该算法的迭代步骤有两步:

1:从数据集中随机抽取一些数据形成小批量,把他们分配给最近的质心

2:更新质心

 

参数解释

 

  •  n_init :用不同的初始化质心运行算法的次数。这里和KMeans类意义稍有不同,KMeans类里的n_init是从相同训练集数据中随机初始化质心。而MiniBatchKMeans类的n_init则是每次用不一样的采样数据集来跑不同的初始化质心运行。默认为3。

  • compute_labels : 计算训练样本的类。

  • reassignment_ratio : 某个类别质心被重新赋值的最大次数比例,为了控制算法的运行复杂度。分母为样本总数。如果取值较高的话算法收敛时间可能会增加,尤其是那些暂时拥有样本数较少的质心。默认是0.01。

  •   max_no_improvement :多少次迭代中质心没有变化,算法终止。默认10。

  •  batch_size:采样数据集的大小,默认100,通常数据集较大时需要提高这个数值。

  •  init_size:用来候选质心的样本数据集大小,默认为batch_size的三倍。

与K-Means算法相比,Mini Batch K-Means中多了一个方法,partial_fit,即可以只用一个batch_size进行训练。其他与K-Means相同

应用场景

在当前大数据的背景下,工程师们往往为了追求更短的计算时间,不得不在一定程度上减少算法本身的计算精度,我说的是在一定程度上,所以肯定不能只追求速度而不顾其它。

参考文献:

https://my.oschina.net/u/3888421/blog/2209122

https://blog.csdn.net/Gamer_gyt/article/details/51244850

https://blog.csdn.net/qq_34104548/article/details/79342598

https://www.dataivy.cn/blog/%E9%80%82%E5%90%88%E5%A4%A7%E6%95%B0%E6%8D%AE%E7%9A%84%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95mini-batch-k-means/

2017-09-14 15:38:39 shiyongraow 阅读数 451

聚类(Clustering)


无监督介绍和聚类引入

正如我们前面所说,监督学习问题的数据带有标签,目的是找到一个分界面使带标签的数据分隔开。而无监督学习问题是不带标签的,如下
无监督学习
希望能通一种算法将这些数据分为俩类,这种算法我们就成为聚类算法。
聚类的应用:
聚类应用
注意:解决无监督学习问题的算法不只有聚类一种。


K-means算法

K-means算法是现在用的最多的聚类算法。
K-means算法可以看做是一个迭代过程。主要有俩步:

  • 随机选取k个聚类中心
  • 1、簇分配
  • 2、移动聚类中心
  • 迭代直到收敛

最后得到的结果是一个收敛的,即聚类中心是不变的,接下来配合图具体说明。
图1
我们目的是要从这些绿色的点中分离数据,首先是随机选择俩个聚类中心。然后计算所有数据中离这俩个中心更近的数据。离红叉更近的点我们标为红色。离蓝叉更近的点标为蓝色。这就是簇分配的过程。得到的结果如下:
图2
接着计算所有红色点的均值,并把红叉移动到均值处。蓝色点同样。即移动聚类中心。结果如下:
图3
得到俩个新的聚类中心后,再进行簇分配、移动聚类中心过程。直到达到收敛的过程,即聚类中心不再移动。结果如下:
图4


K-means规范表述

规范表述
K-means算法俩个输入,聚类数量和训练数据。这里要注意的是我们不考虑x0=1情况,所以整个训练样本是n维。

更具体的:

K-means算法
大K表示聚类中心数量,小k表示具体哪一个聚类中心。
簇分配:C(i)表示将数据分为哪一个聚类,求得【X(i)-uk)】距离的最小值即得C(i)。
移动聚类中心:求簇分配中X(i)的平均距离。将uk移向新的这个平均距离,得到新的聚类中心。
作者这里给出例子如图,C(1)、C(5)、C(6)、C(10)都等于2,就是说着四个数据都归为聚类u2。求x(1)、x(5)、x(6)、x(10)平均值,计算新的聚类中心。


注意:因为再K-means中我们是把数据分配给一个聚类中心,但是如果有一个聚类中心没有数据分配给它怎么办呢?通常情况下我们会移除那个聚类中心,这样结果得到K-1个簇。如果我们就是想要K个簇,那我们还是重新随机找一个聚类中心。幸好这个问题实际中不会经常出现。


K-means处理未分离的簇

以上我们举的例子都是分开好的簇,但是如果我们应对一些未分开的数据,K-means也能有很好的效果。
这里写图片描述
如上以T恤大小举例,以身高体重为主要特征收集一堆数据。尽管数据是连在一起的,用K-means算法也能分成三份。表示三个不同的顾客群体。


目标优化

之前学习的监督学习算法中都有个优化目标函数。即我们熟悉的损失函数。我们一般要对这个损失函数进行一个优化,往往是对其求最小值。K-means中也不例外。

K-means优化函数目的:

  • 1、 调试学习算法,确保K均值算法是在正确运行中。
  • 2、K均值优化目标函数将帮助我们找到更好的簇,并且避免局部最优解。

当K-means算法在运行时,我们需要记录俩个值,C(i)和uk。C(i)表示数据X(i)所归簇的索引。如果X(i)归为第五簇,那么C(i)=5。uk表示第k个簇的聚类中心。

K-means的优化函数

目标优化
如上图,给出了K-means的优化函数,我们可以看到优化函数主要是对X和Uc(i)的操作。优化函数要做的就是最小化图中右下角红线的距离。
我们称K-mans的优化函数为失真函数。
再来回顾一下K-means的俩个过程:
K-means俩个过程
我们可以将第一个过程看做在优化C(i)的过程。第二个过程看做优化Uk的过程。俩个过程分别对应失真函数的俩个决定因子。


随机初始化

在前面K-means的步骤中我们提到选取K个聚类中心的方法是随机选取,那么怎么随机选取呢???作者提出俩点:

随机初始化注意

  • 1、K< m 即聚类的数目要小于样本量
  • 2、随机选择K个训练样本,将这K个训练样本作为聚类中心
    随机初始化
    因为我们是随机选取样本作为聚类中心的,所以聚类的结果有不确定性。
    随机选取的聚类结果
    如果运气足够好,选择的三个聚类中心得到的局部最优恰巧就是全局最优。但是也有可能会陷入下面俩幅图的形状。如何改变这种情况呢???
    K值的随机选取进行多次,同样多次运行K-means算法,从得到的失真函数结果中挑取最小的一个。
    这里写图片描述
    作者这里推荐100次的K-means运行次数。从得到的100个失真函数中选取最小的那一个。通常,当K在2-10间时,随机初始化会有一个比较好的效果,但是如果K值很大的话,那么效果就不会有太大影响。

选择簇的数量

簇的数量选择没有一个统一的定论。大部分情况下仍然是根据可视化图或者手动选取。比如下面这堆数据可分为俩类也可分为四类,这都可以。
簇的选择
作者这里提供一些方法作为选取簇的参考:

肘部法则

肘部法则
对给定的数据,从K=1开始计算失真函数结果,如图中计算到K=8,从左图中我们可以看到从K=3开始,失真函数的下降明显变得更缓慢,(即是曲线的肘点)所以我们把K=3作为分类会是一个比较好的选择。但是但是!我们随着K值增大往往得到的失真函数图是右边的形状,这是一个平滑的曲线,也就没有左图那么好判断,这也是肘部法则的缺点。

通过后续目的来判定

仍然以卖T恤的例子说明。
后续目的
从商家盈利角度出发,当把T恤定位三个号还是五个号哪种方式盈利大一点,就采取哪种方式。
总结:大部分的簇的选取还是靠观察和手动选取,当这俩种方式行不通时,考虑肘部法则或者想一想用K-means的目的是什么。这样会有一个比较好的结果。


2019-07-09 16:01:37 weixin_41690708 阅读数 112

k-means算法是一种聚类算法,所谓聚类,即根据相似性原则,将具有较高相似度的数据对象划分至同一类簇,将具有较高相异度的数据对象划分至不同类簇。聚类与分类最大的区别在于,聚类过程为无监督过程,即待处理数据对象没有任何先验知识,而分类过程为有监督过程,即存在有先验知识的训练数据集。k-means是一种无监督学习,它会将相似的对象归到同一类中。

k-means聚类的优缺点

优点:(1)算法快速、简单; 
          (2)对大数据集有较高的效率并且是可伸缩性的; 
          (3)时间复杂度近于线性,而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(n×k×t) ,其中n代表数据集中对象的数量,t代表着算法迭代的次数,k代表着簇的数目  

缺点:(1)对异常值(噪声)敏感,可以通过一些调整(如中心值不直接取均值,而是找均值最近的样本点代替)

           (2)需要提前确定K值(提前确定多少类)

           (3)分类结果依赖于分类中心的初始化(可以通过进行多次K-means取最优来解决)

           (4)属于“硬聚类”,每个样本只能有一个类别。其他的一些聚类方法(GMM或者模糊K-means允许“软聚类”)

           (5)对于团状的数据点集区分度好,对于带状(环绕)等非凸形状不太好。(用谱聚类或做特征映射)适用于:数值型数据。

过程:

1.随机计算k个类中心作为起始点。

2. 将数据点分配到理其最近的类中心。

3.移动类中心。

4.重复2,3直至类中心不再改变或者达到限定迭代次数。


创建k个点作为起始质心(多是随机选择)
repeat
    对数据集中的每个数据点
        repeat
            对每个质心
                计算质心与数据点之间的距离
        将数据点分配到距离其最近的类(或簇)
    对每一个类(簇),计算类(簇)中所有点的均值并将其作为质心。

一般通过欧氏距离计算公式:

没有更多推荐了,返回首页