k均值聚类算法考试例题_一文读懂K-means聚类算法
1、引言
什么是聚类？我们通常说，机器学习任务可以分为两类，一类是监督学习，一类是无监督学习。监督学习：训练集有明确标签，监督学习就是寻找问题（又称输入、特征、自变量）与标签（又称输出、目标、因变量）之间关系的学习方式。监督学习模型又可以分为两类，分类和回归。
分类模型：目标变量是离散的分类型变量；回归模型：目标变量是连续性数值型变量。无监督学习：只有数据，无标签，即训练集没有标注目标变量。常见的无监督学习算法有聚类，由计算机自己找出规律，把有相似属性的样本放在一组，每个小组也称为簇。
简单来说，聚类是指根据相似数据点的属性或特征将它们分组在一起。
例如，如果我们有一组人的收入和支出，我们可以将他们分为以下几类：
- 高收入，高消费
- 高收入，低消费
- 低收入，低消费
- 低收入，高消费
2、K-means聚类
聚类算法有很多，最流行的聚类算法之一是 k-means。让我们了解 k-means 算法是如何工作的，以及该算法可能达不到预期的情况。
K-means有一个很著名很清晰的解析，就是牧师-村民模型。
有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的居民，于是每个居民到离自己家最近的布道点去听课。听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的居民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个居民又去了离自己最近的布道点……就这样，牧师每个礼拜更新自己的位置，居民根据自己的情况选择布道点，最终稳定了下来。
根据上面这个故事，我们可以简单来概括一下K-means算法的一般步骤，K-Means聚类步骤是一个循环迭代的算法，非常简单易懂：
Step1：确定类别数量K，K值人为设定，在训练数据分布范围内，随机选择K个点作为初始中心点；Step2：按照距离最小原则，把所有数据点分到距离最近的中心点所在的类中；step3：每类中有若干个观数据点，计算K个类中所有数据点的均值，作为下一次迭代的中心点；Step4：重复step2、step3步，直到收敛（每个数据点所属类别或中心点不再改变），聚类过程结束。
下面我们通过一组图来直观了解一下K-means算法迭代过程：
随机生成了3个聚类中心点，然后分别计算每一个数据点对这些中心的距离，把距离最短的那个当成自己的类别。这样每个点都会对应一个中心点，可以看到聚类的并不准确，红色聚类中心太偏，没有数据点属于该类，在代码中，我们会再次随机更新这个聚类中心。
经过一次迭代之后，聚类中心向该类别的数据点的中心移动。
收敛状态收敛状态，聚类中心移动到每个类别数据点中心，继续迭代中心点位置也不在变化。
3、思考
（1）初始中心点怎么确定？
如果我们用欧式距离评估数据点与聚类中心的距离，那么在k-means算法步骤中，相当于我们一直在寻求一种最优的分割方式，使得总平方误差（SSE）最小，即数据点与其聚类中心的欧式距离最小。
在迭代过程中，从两个方面来降低SSE：
第一，把样本点分到最近邻的簇中，这样会降低SSE的值；
第二，用均值更新聚类中心，进一步的减小了SSE（以MSE为目标函数，求导可知最优解即为平均数，以MAE为目标函数，求导可知最优解为中位数，因此如果采用曼哈顿距离进行聚类，更新聚类中心时，我们就需要采用中位数而不是平均数更新）。
这样的重复迭代、不断优化，会找到局部最优解（局部最小的SSE），如果想要找到全局最优解需要找到合理的初始聚类中心。
那合理的初始中心怎么选？方法有很多，譬如先随便选个点作为第1个初始中心C1，接下来计算所有样本点与C1的距离，距离最大的被选为下一个中心C2，直到选完K个中心。这个算法叫做K-Means++，可以理解为 K-Means的改进版，它可以能有效地解决初始中心的选取问题，但无法解决离群点问题。
总的来说，最好解决办法还是多尝试几次，即多设置几个不同的初始点，从中选最优，也就是具有最小SSE值的那组作为最终聚类。
（2）K值怎么确定？
如果K过大，样本划分就越细，每个簇的聚合程度就越高，误差平方和SSE自然就越小。所以不能单纯像选择初始点那样，用不同的K来做尝试，选择SSE最小的聚类结果对应的K值，毫无疑问，SSE最小时必然对应K的最大值。
假设在我们的原始数据中，其客观存在的类别数量为M，当K值小于M时，随着K值的增大，SSE会快速下降，而当K值大于M时，随着K值增大，SSE下降幅度会减小。如下图所示，M取值事先未知，K=2开始尝试，发现K=3时，SSE大幅下降，K=4时，SSE下降幅度稍微小了点，K=5时，下降幅度迅速降低，再后面就越来越平缓。所以我们认为M取值应该为4，因此可以将K设定为4。
这种方法叫做“手肘法”，因为SSE和K的关系图就像是手肘的形状，而肘部对应的K值就被认为是数据的真实聚类数。
4、总结
k-means 聚类概念听起来不错，它易于理解，相对容易实现，并且可以应用于很多用例中。最重要的一点是，算法复杂度不高，仅仅为O(s*n)，s为迭代次数，而一般情况下，k-means算法收敛速度很快，迭代次数不超过10次，因此在数据集较大时，k-means应用起来非常方便。
但也有一些缺点和局限性需要我们注意。从上文的算例来看，k-means 算法似乎运行得很好，但是，如果你仔细观察，你会发现所有创建的簇都是圆形的。这是因为聚类中心是使用平均值迭代更新的。
现在，考虑下面的例子，其中点的分布不是圆形的。如果我们对这些数据使用 k-means 聚类，你认为会发生什么？它仍然试图以循环方式对数据点进行分组。那不太好！k-means 无法识别正确的分类：
因此，我们需要一种不同的方法来将数据点分配给聚类中心。因此，我们不应该再使用基于距离的模型，而是应该使用基于分布的模型。
下一篇文章，我们再来看，高斯混合模型(GMM)是如何来克服K-means算法的缺点。
欢迎大家关注微信公众号“数学建模andMATLAB”继续交流哦~
相关文章：
《C#精彩实例教程》小组阅读06 -- C#运算符与表达式
本微信图文介绍了C#的运算符与表达式。
kvm启动报错
[rootstorage ~]# virsh -c qemu:///system list error: failed to connect to the hypervisor error: Failed to connect socket to /var/run/libvirt/libvirt-sock: No such file or directory原因：libvirt未启动解决方法[rootstorage ~]# libvirtd -d [rootst…
邀请参加活动的邀请函_圣诞节活动策划邀请函在线制作
2020年就要过去了，许多人说这一年很难，难上加南。莎士比亚说凡是过去，皆为序章。无论好的还是坏的终究会成为过往，向前看吧。圣诞节快要到来，商场开始布置精致的橱窗，电商巨头也在忙着做促销，幼…
比较全的字符串验证类,有人顶的话以后继续发
啥也不说看代码哈~ Codeusing System;using System.Collections.Generic;using System.Text;using System.Text.RegularExpressions;namespace Utility { public class ISExt { private static ISExt instance null; public static ISExt GetInstance…
设计模式（2）工厂方法模式（Factory Method）
设计模式（0）简单工厂模式 设计模式（1）单例模式（Singleton） 源码地址 0 工厂方法模式简介 0.0 工厂方法模式定义 工厂方法模式是在简单工厂模式基础上，为解决更复杂的对象创建问题而衍生进化出来…
基于Matlab的遗传算法优化BP神经网络在非线性函数拟合中的应用
本微信图文详细介绍了遗传算法优化BP神经网络初始权值阈值的过程，并通过实例说明该优化能够提升BP神经网络的预测精确程度。
android 加载h5页面部分机型滑动卡顿回弹_网易爆款H5 的交互方法参考
在早些年，H5其实更像是手机上的PPT，只支持点击、滑动这些基础手势操作。以内容展示为主，交互形式为辅。但到了今天，H5的玩法已经有了质的突破。不仅交互形式超多，形式与内容也能紧密结合，产生11大于2的效果…
使用SDL打造游戏世界之入门篇 - 1
来源：天极开发 作者：维维编译 出处：巧巧读书 2007-07-17 进入讨论组 简介 Simple DirectMedia Layer, 简称SDL，是一个自由的跨平台的多媒体开 发包，主要通过OpenGL和2D视频帧缓冲(framebuffer)提供对音频、键盘、鼠标…
RBAC新解 - 基于资源的权限管理
1、什么是角色 当说到程序的权限管理时，人们往往想到角色这一概念。角色是代表一系列可执行的操作或责任的实体，用于限定你在软件系统中能做什么、不能做什么。用户帐号往往与角色相关联，因此，一个用户在软件系统中能做什么取决于…
《C#精彩实例教程》小组阅读07 -- C#字符与字符串
本微信图文详细介绍了C#中的字符与字符串。
syslog打印不带等级_printk的日志级别和控制台级别
printk根据日志级别(loglevel)对消息进行分类。日志级别用宏定义，日志级别宏展开为一个字符串，在编译时由预处理器将它和消息文本拼接成一个字符串，因此printk 函数中日志级别宏和格式字符串间不能有逗号。下面是两个printk的例子，…
《C#精彩实例教程》小组阅读08 -- C#流程控制语句
本微信图文详细介绍了C#的流程控制语句。
ASPJPEG缩略图生成函数
好久没有发文章，贴一段代码出来晒晒！一段aspjpeg组件生成缩略图的代码，有4种生成方式，建议用最后一种，生成的缩略图最清晰而且不会拉伸、变形！做图片生成最好不过！// 缩略图生成函数 Code By S…
java面试题收集
2019独角兽企业重金招聘Python工程师标准>>> 1.什么是B/S架构？什么是C/S架构 B/S(Browser/Server)，浏览器/服务器程序 C/S(Client/Server)，客户端/服务端，桌面应用程序 2.你所知道网络协议有那些？ HTTP&…
mobile还有人用吗 spring_话说，苹果手机语音备忘录功能还有人用吗？
hi，各位，苹果手机自带的语音备忘录功能还有人在用吗？前两天，有小伙伴在后台留言问：“苹果手机语音备忘录怎么恢复？”小编一时还有些恍惚“它是什么，手机上有吗？”，好在通…
MVC5 + EF6 完整入门教程三
期待已久的EF终于来了。 学完本篇文章，你将会掌握基于EF数据模型的完整开发流程。 本次将会完成EF数据模型的搭建和使用。 基于这个模型，将之前的示例添加数据库查询验证功能。 文章提纲 概述 & 要点 详细步骤 总结 概述 & 要点 下面是本文要点&…
Matlab编程与数据类型 -- 内联函数
本微信图文详细介绍了Matlab中的内联函数。
优化营商环境建议个人_优化营商环境的几点建议（三）
优化临沂的营商环境，重点是做好招商引资的后续环境优化！事关一个地区的财税收入，所以放眼全国，招商引资到哪里都是重点工作。早在2018年4月16日，临沂就召开了新旧动能转换暨开放型经济、招商引资工作动员大会ÿ…
基于Matlab的神经网络结合遗传算法在非线性函数极值寻优中的应用
本微信图文利用神经网络进行非线性函数数据的拟合并通过遗传算法对训练后的神经网络进行非线性函数极值寻优。
十分钟成为 Contributor 系列 | 为 TiDB 重构 built-in 函数
2019独角兽企业重金招聘Python工程师标准>>> 这是十分钟成为 TiDB Contributor 系列的第二篇文章，让大家可以无门槛参与大型开源项目，感谢社区为 TiDB 带来的贡献，也希望参与 TiDB Community 能为你的生活带来更多有意义的时刻。 …
研究生要这样度过！（转）
研究生要这样度过！ 首先要知道研究生期间做什么？我认为研究生期间学生应该学三件事情： 1）建立合理的知识结构：尽量广地涉猎学科基本知识，尽量深地了解所研究领域的 方方面面、过去和现在 2）掌握…
后端开发面试自我介绍_字节跳动暑期实习后端开发面试经历
字节跳动后端实习是什么，字节跳动后端实习面试流程是怎样？今天小编就来帮助大家了解一下字节跳动后端实习面试到底有什么内容。（好了不皮了，开始正文）字节的面试流程总的来说还是挺享受的，和面试官两人的思…
《C#精彩实例教程》小组阅读09 -- C#数组与集合
本微信图文详细介绍了C#的数组与集合。
Oracle执行计划突变诊断之统计信息收集问题
Oracle执行计划突变诊断之统计信息收集问题1. 情形描述DB version：11.2.0.4WITH SQL1 AS(SELECT LAC,CI,TO_NUMBER(C.LONGITUDE) LONGITUDE,TO_NUMBER(C.LATITUDE) LATITUDEFROM MB_SYS_CELL_INFO CWHERE C.CONTY_NAME 道孚县), SQL2 AS(SELECT DISTINCT IMSI, LA…
安装gym库_强化学习Gym库学习实践(一）
最近看了一篇研究方向相关的文章，介绍了一种DQN的应用，感觉还挺新鲜的。想着把这篇文章复现出来，就开始学习强化学习的相关知识，作为一名小白，这一路走的可是真的十分艰难（我太菜了啊！ÿ…
VS2005编译QT4.8.2
为什么要编译？ 因为安装安装版的QT4.8.2，vs2005编译报错。 1.下载QT4.8.2，qt-everywhere-opensource-src-4.8.2.zip，下载vs-AddIn1.1.11. 2.解压QT源码包到C盘， 这里路径为 c:\qt\4.8.2\。 3.配置系统环境变量…
Don’t Use the Win32 API PostThreadMessage() to Post Messages to UI Threads(翻译)
大龙的博客C博客 | 首页 | 发新随笔 | 发新文章 | 联系 | 聚合 | 管理 Don’t Use the Win32 API PostThreadMessage() to Post Messages to UI Threads(翻译) Don’t Use the Win32 API PostThreadMessage() to Post Messages to UI Threads不要用Win32 API PostThreadMessage…
Matlab编程与数据类型 -- 文本M文件
本微信图文详细介绍了Matlab中的文本M文件。
安卓x86_Android：虚拟机体验基于安卓10的BlissOS V12.2 Android X86版
我是科技鲁工，今天带来基于Android10的x86版本的Bliss os的安装体验。喜欢的朋友可以关注支持一下。Bliss OS是一个基于Android x86项目的开源操作系统，能让您在PC电脑或平板电脑设备上运行最新的Android 10操作系统。该系统基于AOSP(Android开放源代码项…
《C#精彩实例教程》小组阅读10 -- C#属性与方法
本微信图文详细介绍了C#的属性与方法。