当前课程知识点:机器学习概论 > 第八章 支持向量机(II)和无监督学习 > 8.7 K-means聚类和K-medoids聚类 > K-means聚类和K-medoids聚类
那么接下来我们给大家介绍另外一种聚类的方法
接下来的两种方法都不是层次聚类 是非层次聚类
也就是平的聚类的方法 第一种非常常用的叫K-means 聚类
这个K-means聚类 其实它的思路我就想要最小化欧氏距离
就是最小化距离 我们可以拿欧氏距离来举例
比较常用的时候也是拿欧氏距离举例 它是一个迭代的算法
而且是一种硬聚类 然后这个算法是怎么样的呢
我把这个算法的公式写在这里面 然后大家非常简单
其实感兴趣同学后面可以再看一下 当我跟大家说的时候
我们可以拿后面的例子来看 大家一眼就明白了
比如说这是例子第一步 我们假设 K-means意思是有一个参数K
这个K比如说取3的话 假设K等于3
我们现在有一批这样的点 随机的
random取任何3个点作为三个类的中心
就三个类的mean均值 中心 这个中心是指均值的中心
然后我们就基于所有的点跟这个中心之间的距离
把这些点 把每个点分配到了某一个类里 这就是三类
形成了这三类之后 你显然会发现原来的它就不是这个中心了
我们就重新计算它新的mean 新的中心 非常特别注意的一点 比如说
从这里体现比较明显 它的mean 就是它的均值 这个类的中心
不一定在 不是中点 就不是最中心的那个点
它这个值可以是一个虚拟的值 就是这个类平均值
大家的平均值 有了新的类中心之后 你就重新计算
比如说在这种例子下你会发现这个点 它原来离这个近
但现在离新的类中心更远了 反而离另外一个类更近了
重新分配这些点 分配下去就可以了
所以这个是给大家看到的一个例子 一个图的步骤的例子
我们假设你 random两个类是这样的 然后一开始你就到这样的分类面
分了之后你就会找到它们的中心就会发生变化了
分别在这个位置和这个的位置 当然这么一变之后
你的分类面甚至连方向都改变了 然后又变成了新的
后面一直到 最后发现好像这样已经聚完 已经稳定了
就可以停了 所以大家会发现 这个你需要让它找到稳定
第二就是你的起始点我们是random去找的 random找的起始点不同
你最后聚出来的类可能是不一样的 然后我们这里有一个(好像崩了)
很糟糕我今天的三堂课里面 ppt分别挂掉了一次
不知道是为什么 而且很有可能重启不起来 不过没关系
时间关系我们来继续讲 因为我已经积累了一些经验
而且很有可能继续重启不起来的时候
我可以换用(...)来去展示我们的slides来 我们讲到这个了
这个动图还不错 还能显示出来 这个是一个动图来看
我们是第8个、第9个、第10次、第11次
会看到现在迭代基本上比较稳定了
然后重看一遍这个是0、1 就是随机选的 然后根据它的分配
然后你根据 只要没有稳定你就可以去调整
然后等到稳定了就OK 其实你的random 初始点不一样
聚类的结果会不一样 所以在K-means聚类里面只能找到局部的最优
我们没办法说它全局最优 我们甚至不知道什么是全局最优
因为你没有标准答案 即使你有标准答案
你聚类聚出来的东西跟你的想象不一样
比如说我假设拿全班的同学这样一起的数据收集起来
我假设我想聚一下 聚出来可能比如说
假设我没有性别的信息 我希望能聚出来男生一类 女生一类
结果发现 不 我其实更常出现的是这种情况
我希望大家聚出来的是哪些同学可能听明白了
哪些同学可能没听明白 所以我就试了两类
结果聚到最后发现男生聚了一类 女生聚了一类 然后男生多嘛
常常你出现聚类的结果是有一类很大 然后有一类比较少
这个是非常容易出现的情况 对于聚类来说
因为其实你聚类的时候 并没有你的目标
希望聚到什么样来去描述 那可能反而在这种情况下
数据本身会发现男生和女生的差异是最大的
所以它就直接聚成了这样的两类 而并不是
你希望找到的哪些同学听懂了 哪些同学没听懂
所以聚类结果是不可靠的 它还可以拿来做什么用呢
比如说我们可以做图象的压缩 这个是原始图象是这样
如果K=10 你会发现是图象压缩变成这个样子了
只用10个类来描述就行了 我们原来是有非常高的象素的
R、G、B 如果K=3就是得到这样的图象 如果K=2两类
其实就是这样 事实上图象本身的结构还存在有一部分
如果你在不同的带宽的传输下
其实我觉得原来如果我的1024的像素来去描述
传不过来 好 我就把它变成十维的数据
十维的 我们就能够传输过去 原来如果1024如果不行的话
那么这个涉及到一个问题 你怎么决定这个K呢
这个K值 是个好问题 因为K值我们也不知道K应该等于多少
因为咱们没有标准答案 除非你知道这个事情
你本来就想要它是几类 假设我就想要是两类可以考虑
那事实上有一种办法是说除了你靠实际问题的本质来说
那你还可以靠data追问 就是让数据来说话 这个data数据追问的时候
你必须要有前提条件 你事实上要去看一下
你的维度不能噪声太大 而且你数据不要太稀疏
太稀疏是学不出来的 有一种什么办法呢 我们用图示来说
有一种是说 当然好用的办法还是要分出validation set 和 test set 就是training set
要有一个training set 比如说你在其中的你的training set 上面你会发现
我们现在如果是两类的时候 这个data是这样的
四类的时候我们这个类 你可以定义一个WK这个参数
这个WK这个参数你可以把它描述成你的类内相似度的一个反
就是和类类相似度取反的这样一个定义 是你自己可以定义的
比如说类的宽度等等 我们或者是类间的相似度的一个指标
总之你定义出这个指标之后你就试一试 在training data上试一试
会发现K等于不同值的时候 你可以有一个值之后
你会发现当这个K取到某一个值的时候
你给的这种指标它通常是体现类内相似度和类间相似度的
有一个很大的变化 有一个很大的sharp
那你这时候发现那我这个K值可能是比较合适了
这是一种做法 还有一种做法是这样的
你用一样的clustering算法 但是你用一批均匀分布的data
就你自己的data可能不是uniformly分布的 你用均匀分布的data
用同样的算法跑出一个结果出来
然后你再用你自己的算法跑一个结果出来
就是用同样算法 看一看你的算法和均匀分布数据上的
这个算法得到的结果之间 gap最大的那个 差异最大的那个值
就是你觉得比较合适的这个cluster值 就表示在这种cluster下
你的这个数据最能体现出它的结构
就是和这个均匀分布最不一样 所以这是最能体现出数据结构
那这也是一种办法 还有一些其他的办法 比如说贝叶斯估计
这个会是比较高阶的那种方法 大家未来可能
研究生学习也许会涉及到 或者是做cross validation
我们只有三四页slides 所以我们给大家讲到 主要的内容都讲完了
主要是分析一下这种K-means的这种聚类
它事实上有几个特点 首先就是它非常适合于处理我们的数据
不是太稀疏 而且我们能够发现数据把它学习出一些
紧凑的这些云的结构 然后它可以发现那些
非凸的形状的这样的类来 但是它有一个缺点
就是对噪声非常的敏感 尤其是outlier 那个噪声
甚至可能使得你的学习的算法在不停的震荡 那个结果
我们还有一个算法叫做K-medoids 的算法 K-medoids算法很简单
我们用图式来说 我们random去选假设K=2 选两个点作为中点
大家知道这个就是和K-means最大的差别了
K-means不一定是真的点 它只是平均值
我们在 取两个点作为终点
然后我们就把所有的数据点把它分到
自己所对应的这个cluster里面 然后我们接下来去换一换
把每一个cluster里面 我们把它这个点交换一下
比如说我觉得这个cluster不要在这了 我放到这行不行
放在另外一个位置行不行 每换一个位置之后 你去计算一下
每换一个点之后 你就会有一个重新的分配 重新分配完之后
你能够计算它有一个cost这个cost是说
比如说所有的点到我们终点之间的距离
到终点的这个距离变大了 就是距离之和变大了
你的cost就变大了 如果距离变小了
你的cost就变小了 如果说我的这个cost是变小了
那我就的确就换 否则的话 就不要换
我们刚才的这个是K-means的方法 然后K中点是这样的
我去找 找每一个点 然后找出点分配给它
然后这是我们刚才说的 我们把它重新分配了一个点之后
去计算这个类里面每个点到这个点之间的距离的和
我们把它叫做cost 这只是一种cost方法
你还可以有其他的cost 会发现这个cost
比原来的cost要大 我们就不换
那你再随机的去找其他的点 会发现换成这个点的时候
cost变小了 那么我们就要去变换它
使得最终我们事实上你的距离总得来说簇内的
类内的距离是对小的 就是cost是最小的 这样就结束了
所以它和K-means最大的差别在于它不是在那个点上
好 以上就是我们今天课程讨论的所有的内容
我们讨论了聚类 主要是学习了无指导学习
然后学习了 定义了什么是聚类的方法
以及学习了三种不同的聚类方法
-1.1 课程介绍
--课程介绍(1)
--课程介绍(2)
-1.2 机器学习的背景
--机器学习的背景
-1.3 什么是机器学习
--什么是机器学习
-1.4 机器学习系统设计
-第一章作业
-2.1 决策树的基本概念
--决策树的基本概念
-2.2 决策树的实例和发展历史
-2.3 经典决策树算法ID3
-2.4 过拟合和前剪枝
--过拟合和前剪枝
-第二章作业
-3.1 下午茶时间:勒索软件
-3.2 后剪枝
--后剪枝
-3.3 决策树的改进和归纳学习假设
-3.4 贝叶斯学习的背景
--贝叶斯学习的背景
-3.5 极大似然假设、朴素贝叶斯和最小描述长度
-第三章作业
-4.1 下午茶时间:微博的垃圾检测
-4.2 马尔可夫模型
--马尔可夫模型
-4.3 隐马尔可夫模型
--隐马尔可夫模型
-4.4 评估问题
--评估问题(1)
--评估问题(2)
-4.5 解码问题
--解码问题
-4.6 隐马尔可夫模型的应用
-第四章作业
-5.1 下午茶时间:图灵奖
-5.2 假设评估
--假设评估(1)
--假设评估(2)
--假设评估(3)
-5.3 置信度和置信区间
-5.4 有限数据下的比较
--有限数据下的比较
-第五章作业
-6.1 下午茶时间:黑洞照片
-6.2 基于实例的学习的基本概念
-6.3 最近邻算法
--最近邻算法
-6.4 K邻近算法
--K近邻算法
-6.5 KD树
--KD树
-6.6 距离加权的K近邻算法
-第六章考试
-7.1 支持向量机的背景
--支持向量机的背景
-7.2 线性支持向量机
-第七章作业
-8.1 核函数支持向量机
-8.4 支持向量机总结
--支持向量机总结
-8.5 无监督学习简介
-8.6 层次聚类
--层次聚类
-8.7 K-means聚类和K-medoids聚类
-第八章作业


