当前位置:首页 » 操作系统 » 群聚算法

群聚算法

发布时间: 2024-12-08 22:40:42

Ⅰ 八:聚类算法K-means(20191223-29)

学习内容:无监督聚类算法K-Means

k-means:模型原理、收敛过程、超参数的选择

聚类分析是在数据中发现数据对象之间的关系,将数据进行分组,组内的相似性越大,组间的差别越大,则聚类效果越好。

不同的簇类型: 聚类旨在发现有用的对象簇,在现实中我们用到很多的簇的类型,使用不同的簇类型划分数据的结果是不同的。

基于原型的: 簇是对象的集合,其中每个对象到定义该簇的 原型 的距离比其他簇的原型距离更近,如(b)所示的原型即为中心点,在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的 基于中心的簇 ,最常用的K-Means就是这样的一种簇类型。 这样的簇趋向于球形。

基于密度的 :簇是对象的密度区域,(d)所示的是基于密度的簇,当簇不规则或相互盘绕,并且有早上和离群点事,常常使用基于密度的簇定义。

关于更多的簇介绍参考《数据挖掘导论》。

基本的聚类分析算法

     1. K均值: 基于原型的、划分的距离技术,它试图发现用户指定个数(K)的簇。

     2. 凝聚的层次距离: 思想是开始时,每个点都作为一个单点簇,然后,重复的合并两个最靠近的簇,直到尝试单个、包含所有点的簇。

     3. DBSCAN: 一种基于密度的划分距离的算法,簇的个数有算法自动的确定,低密度中的点被视为噪声而忽略,因此其不产生完全聚类。

不同的距离量度会对距离的结果产生影响,常见的距离量度如下所示:

优点:易于实现 

缺点:可能收敛于局部最小值,在大规模数据收敛慢

算法思想:

选择K个点作为初始质心 

repeat

    将每个点指派到最近的质心,形成K个簇 

    重新计算每个簇的质心  

until 簇不发生变化或达到最大迭代次数

这里的“重新计算每个簇的质心”,是根据目标函数来计算的,因此在开始时要考虑 距离度量和目标函数。

考虑欧几里得距离的数据,使用 误差平方和(Sum of the Squared Error,SSE) 作为聚类的目标函数,两次运行K均值产生的两个不同的簇集,使用SSE最小的那个。

k表示k个聚类中心,ci表示第几个中心,dist表示的是欧几里得距离。 

这里有一个问题就是为什么,我们更新质心是让所有的点的平均值,这里就是SSE所决定的。

k均值算法非常简单且使用广泛,但是其有主要的两个缺陷:

1. K值需要预先给定 ,属于预先知识,很多情况下K值的估计是非常困难的,对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景,可以进行迭代运算,然后找出Cost Function最小时所对应的K值,这个值往往能较好的描述有多少个簇类。

2. K-Means算法对初始选取的聚类中心点是敏感的 ,不同的随机种子点得到的聚类结果完全不同

3. K均值算法并不是很所有的数据类型。 它不能处理非球形簇、不同尺寸和不同密度的簇,银冠指定足够大的簇的个数是他通常可以发现纯子簇。

4. 对离群点的数据进行聚类时,K均值也有问题 ,这种情况下,离群点检测和删除有很大的帮助。

下面对初始质心的选择进行讨论:

当初始质心是随机的进行初始化的时候,K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕,可能只能得到局部的最优解,而无法得到全局的最优解。

多次运行,每次使用一组不同的随机初始质心,然后选择一个具有最小的SSE的簇集。该策略非常的简单,但是效果可能不是很好,这取决于数据集合寻找的簇的个数。

关于更多,参考《数据挖掘导论》

为了克服K-Means算法收敛于局部最小值的问题,提出了一种 二分K-均值(bisecting K-means)

将所有的点看成是一个簇

当簇小于数目k时

    对于每一个簇

        计算总误差

        在给定的簇上进行K-均值聚类,k值为2        计算将该簇划分成两个簇后总误差

    选择是的误差最小的那个簇进行划分

在原始的K-means算法中,每一次的划分所有的样本都要参与运算,如果数据量非常大的话,这个时间是非常高的,因此有了一种分批处理的改进算法。

使用Mini Batch(分批处理)的方法对数据点之间的距离进行计算。

Mini Batch的好处:不必使用所有的数据样本,而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少,所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集成为一个“簇”。通过这样的划分,每个簇可能对应于一些潜在的概念(也就是类别);需说明的是,这些概念对聚类算法而言事先是未知的,聚类过程仅能自动形成簇结构,簇对应的概念语义由使用者来把握和命名。

聚类是无监督的学习算法,分类是有监督的学习算法。所谓有监督就是有已知标签的训练集(也就是说提前知道训练集里的数据属于哪个类别),机器学习算法在训练集上学习到相应的参数,构建模型,然后应用到测试集上。而聚类算法是没有标签的,聚类的时候,需要实现的目标只是把相似的东西聚到一起。

聚类的目的是把相似的样本聚到一起,而将不相似的样本分开,类似于“物以类聚”,很直观的想法是同一个簇中的相似度要尽可能高,而簇与簇之间的相似度要尽可能的低。

性能度量大概可分为两类: 一是外部指标, 二是内部指标 。

外部指标:将聚类结果和某个“参考模型”进行比较。

内部指标:不利用任何参考模型,直接考察聚类结果。

对于给定的样本集,按照样本之间的距离大小,将样本集划分为K个簇。让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大

初学者会很容易就把K-Means和KNN搞混,其实两者的差别还是很大的。

K-Means是无监督学习的聚类算法,没有样本输出;而KNN是监督学习的分类算法,有对应的类别输出。KNN基本不需要训练,对测试集里面的点,只需要找到在训练集中最近的k个点,用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程,找到k个类别的最佳质心,从而决定样本的簇类别。

当然,两者也有一些相似点,两个算法都包含一个过程,即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

优点:

简单, 易于理解和实现 ;收敛快,一般仅需5-10次迭代即可,高效

缺点:

    1,对K值得选取把握不同对结果有很大的不同

    2,对于初始点的选取敏感,不同的随机初始点得到的聚类结果可能完全不同

    3,对于不是凸的数据集比较难收敛

    4,对噪点过于敏感,因为算法是根据基于均值的

    5,结果不一定是全局最优,只能保证局部最优

    6,对球形簇的分组效果较好,对非球型簇、不同尺寸、不同密度的簇分组效果不好。

K-means算法简单理解,易于实现(局部最优),却会有对初始点、噪声点敏感等问题;还容易和监督学习的分类算法KNN混淆。

参考阅读:

1.《 深入理解K-Means聚类算法 》

2.《 K-Means 》

热点内容
安卓上哪里下大型游戏 发布:2024-12-23 15:10:58 浏览:186
明日之后目前适用于什么配置 发布:2024-12-23 14:56:09 浏览:51
php全角半角 发布:2024-12-23 14:55:17 浏览:826
手机上传助手 发布:2024-12-23 14:55:14 浏览:730
什么样的主机配置吃鸡开全效 发布:2024-12-23 14:55:13 浏览:828
安卓我的世界114版本有什么 发布:2024-12-23 14:42:17 浏览:708
vbox源码 发布:2024-12-23 14:41:32 浏览:275
诗经是怎么存储 发布:2024-12-23 14:41:29 浏览:657
屏蔽视频广告脚本 发布:2024-12-23 14:41:24 浏览:417
php解析pdf 发布:2024-12-23 14:40:01 浏览:816