专栏首页WD学习记录kmeans优化算法

kmeans优化算法

k-means算法的优、缺点

1、优点:

①简单、高效、易于理解

②聚类效果好

2、缺点:

①算法可能找到局部最优的聚类,而不是全局最优的聚类。使用改进的二分k-means算法。

②算法的结果非常依赖于初始随机选择的聚类中心的位置,可以通过多次执行该算法来减少初始中心敏感的影响。方法1:选择彼此距离尽可能远的k个点作为初始簇中心。方法2:先使用canopy算法进行初始聚类,得到k个canopy中心,以此或距离每个canopy中心最近的点作为初始簇中心。

③聚类结果对k值的依赖性比较大。目前并没有一个通用的理论来确定这个k值。

④可能发生距离聚类中心最近的样本集为空的情况,因此这个聚类中心不变无法得到更新。

⑤对离群点和孤立点敏感。通过LOF(局部离群因子)检测算法对数据集进行预处理,去除离群点后再进行聚类。

⑥性能问题。原始的k-means算法,每一次迭代都要计算每一个观测点与所有聚类中心的距离,当观测点的数目很多时,算法的性能并不理想。时间复杂度为O(nkl),l为迭代次数,n为数据集容量。为了解决这一问题,我们可以使用kd树以及ball 树(数据结构)来提高k-means算法的效率。

优化方法

二分k-means算法:首先将整个数据集看成一个簇,然后进行一次k-means(k=2)算法将该簇一分为二,并计算每个簇的误差平方和,选择平方和最大的簇迭代上述过程再次一分为二,直至簇数达到用户指定的k为止,此时可以达到的全局最优。

Canopy算法:首先给定两个距离T1和T2,T1>T2。从数据集中随机有放回地选择一个点作为一个canopy中心,对于剩余数据集中的每个点计算其与每个canopy中心的距离,若距离小于T1,则将该点加入该canopy中;若距离小于T2,则将其加入该canopy的同时,从数据集中删除该点,迭代上述过程,直至数据集为空为止。

canopy算法会得到若干个canopy,可以认为每个canopy都是一个簇,只是数据集中的点可能同时属于多个不同的canopy,可以先用canopy算法进行粗聚类,得到k值和k个初始簇中心后再使用k-means算法进行细聚类。

k-means算法的k值自适应优化算法:首先给定一个较大的k值,进行一次k-means算法得到k个簇中心,然后计算每两个簇中心之间的距离,合并簇中心距离最近的两个簇,并将k值减1,迭代上述过程,直至簇类结果(整个数据集的误差平方和)不变或者变化小于某个阈值或者达到指定迭代次数为止。

参考:

k-means算法、性能及优化

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法2016-06-02

    1. 一个算法的时间复杂度是指该算法的运行时间与问题规模的对应关系。一个算法是由控制结构和原操作构成的,其执行的时间取决于二者的综合效果。为了便于比较同一问题的...

  • springboot gradle 使用过程中遇到的问题小结(5)

    1. @RequestMapping @PostMapping @GetMapping

  • K-means中K值的选取

    以下博文转自:https://blog.csdn.net/qq_15738501/article/details/79036255  感谢

  • web 图像技术:前端引入图片的各种方式及其优缺点

    前端开发人员在构建网站时需要做的一个决定是引入图片的方式。它可以是<img>标签,或者是通过CSS background 属性,还可以使用 SVG <image...

    前端小智@大迁世界
  • 我们需要“算法天使”

    算法构筑了进入互联网的很多东西,这已经被不止一次地论述过。但是,还没有一些非常确凿的证据,可以支持当初创造更加以人为中心的算法解决方案的办法。比如,我们是否需要...

    CSDN技术头条
  • 重磅|教育部发文:AI、算法等2018年进入全国高中课程!

    关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 1月16日上午,教育部召开新闻发布会...

    昱良
  • 一个图像项目的可能性处理方式

      随着深度学习的发展,图像、声音的识别几乎都是它的天下。但深度学习需要很大的空间来存储参数,而且推理的时间与所使用的硬件关系很大,于是对于成本是有很大的要求的...

    窗户
  • 在视频网站Netflix上进行个性化算法的创新 迎合你的口味排序视频

    Netflix是一家美国在线视频网站。Netflix的视频体验是由一系列排名算法(Ranking Algorithm)组成的,每一种算法都针对不同的目的进行优化...

    AiTechYun
  • 机器学习算法:选择您问题的答案

    当我开始涉足数据科学时,我经常面临为如何我的问题选择最合适的算法的问题。如果你像我一样,当你看到一些关于机器学习算法的文章时,你会看到许多详细的描述。但是,即使...

    人工智能资讯小编
  • 对皮肤美白算法的一些研究。

     皮肤美白是现在任何一款流行的美颜软件必备的功能之一,不过你如果在互联网上搜索关于美白算法,能直接拿到并使用的可能不多。一直觉得这个算法其实很简单的,并且实现...

    用户1138785

扫码关注云+社区

领取腾讯云代金券