Chinese, Computer Science, Technology
Machine Learning Chinese NLP :::: K-Means Algorithm
K-Means Algorithm
在聚类问题中
我们有未加标签的数据
我们希望有一个算法
能够自动的
把这些数据分成
有紧密关系的子集或是簇
K均值 (K-means) 算法
是现在最为广泛使用的
聚类方法
那么在这个视频中
我将会告诉你
什么是K均值算法以及它是怎么运作的
K均值算法最好用图来表达
如图所示
现在我有一些
没加标签的数据
而我想将这些数据分成两个簇
现在我执行K均值算法
方法是这样的
首先我随机选择两个点
这两个点叫做聚类中心 (cluster centroids)
就是图上边的两个叉
这两个就是聚类中心
为什么要两个点呢
因为我希望聚出两个类
K均值是一个迭代方法 它要做两件事情
第一个是簇分配
第二个是移动聚类中心
我来告诉你这两个是干嘛的
在K均值算法的每次循环中
第一步是要进行簇分配
这就是说
我要遍历所有的样本
就是图上所有的绿色的点
然后依据
每一个点
是更接近红色的这个中心
还是蓝色的这个中心
来将每个数据点
分配到两个不同的聚类中心中
具体来讲
我指的是
对数据集中的所有点
依据他们
更接近红色这个中心
还是蓝色这个中心
进行染色
染色之后的结果如图所示
以上就是簇分配的步骤
K均值的另一部分
是要移动聚类中心
具体的操作方法
是这样的
我们将两个聚类中心
也就是说红色的叉
和蓝色的叉
移动到
和它一样颜色的那堆点的均值处
那么我们要做的是
找出所有红色的点
计算出它们的均值
就是所有红色的点
平均下来的位置
然后我们就把红色点的聚类中心移动到这里
蓝色的点也是这样
找出所有蓝色的点
计算它们的均值
把蓝色的叉放到那里
那我们现在就这么做
我们将按照图上所示这么移动
现在两个中心都已经移动到新的均值那里了
你看
蓝色的这么移动
红色的这么移动
然后我们就会进入下一个
簇分配
我们重新检查
所有没有标签的样本
依据它离红色中心还是蓝色中心更近一些
将它染成红色或是蓝色
我要将每个点
分配给两个中心的某一个 就像这么做
你看某些点的颜色变了
然后我们又要移动聚类中心
于是我计算
蓝色点的均值
还有红色点的均值
然后就像图上所表示的
移动两个聚类中心
来我们再来一遍
下面我还是要做一次簇分配
将每个点
染成红色或是蓝色
依然根据它们离那个中心近
然后是移动中心 你看就像这样
实际上
如果你从这一步开始
一直迭代下去
聚类中心是不会变的
并且
那些点的颜色也不会变
在这时
我们就能说
K均值方法已经收敛了
在这些数据中找到两个簇
K均值表现的很好
来我们用更加规范的格式描述K均值算法
K均值算法接受两个输入
第一个是参数K
表示你想从数据中
聚类出的簇的个数
我一会儿会讲到
我们可以怎样选择K
这里呢 我们只是说
我们已经确定了
需要几个簇
然后我们要告诉这个算法
我们觉得在数据集里有多少个簇
K均值同时要
接收另外一个输入
那就是只有 x 的
没有标签 y 的训练集
因为这是非监督学习
我们用不着 y
同时在非监督学习的
K均值算法里
我们约定
x(i) 是一个n维向量
这就是
训练样本是 n 维而不是 n+1 维的原因
这就是K均值算法
第一步是
随机初始化 K 个聚类中心
记作
μ1, μ2 一直到 μk
就像之前
图中所示
聚类中心对应于
红色叉和蓝色叉
所在的位置
于是我们有两个聚类中心
按照这样的记法
红叉是 μ1
蓝叉是 μ2
通常情况下
我们可能会有比2要多的聚类中心
K均值的内部循环
是这样的
我们会重复做下面的事情
首先
对于每个训练样本
我们用变量 c(i) 表示
K个聚类中心中最接近 x(i) 的
那个中心的下标
这就是簇分配
这个步骤
我先将每个样本
依据它离那个聚类中心近
将其染成
红色或是蓝色
所以 c(i) 是一个
在1到 K 之间的数
而且它表明
这个点到底是
更接近红色叉
还是蓝色叉
另一种表达方式是
我想要计算 c(i)
那么
我要用第i个样本x(i)
然后
计算出这个样本
距离所有K个聚类中心的距离
这是 μ
以及小写的k
大写的 K 表示
所有聚类中心的个数
小写的 k 则是
不同的中心的下标
我希望的是
在所有K个中心中
找到一个k
使得xi到μk的距离
是xi到所有的聚类中心的距离中
最小的那个
也就是说
k的值使这个最小
这就是计算ci的方法
这里还有
另外的表示ci的方法
我用xi减μk的范数
来表示
这是第i个训练样本
到聚类中心μk
的距离
注意
我这里用的是小写的k
大写的K
大写的k表示
聚类中心的总数
这个小写的k
是第一个到第K个中心
中的一个
我用小写的k
表示不同聚类中心的下标
这是个小写k
这就是某个样本到聚类中心的距离
接下来
我要做的是
找出小写的k的值
让这个式子最小
那么
接下来
我就要将 c(i)
赋值为k
我这里按照惯例表示
x(i) 和聚类中心的距离
因为出于惯例
人们更喜欢用距离的平方来表示
所以我们可以认为
c(i) 是距样本 x(i) 的距离的平方
最小的那个聚类中心
当然
使距离的平方最小或是距离最小
都能让我们得到相同的 c(i)
但是我们通常还是
写成距离的平方
因为这是约定俗成的
这就是簇分配
K均值循环中的另一部分是
移动聚类中心
这是说
对于每个聚类中心
也就是说
小写k从1循环到K
将 μk 赋值为这个簇的均值
举个栗子
某一个聚类中心
比如说是 μ2
被分配了一些训练样本
像是1,5,6,10
这个表明
c(1) 等于2
c(5) 等于2
c(6) 等于2
同样的 c(10) 也是等于2 对吧?
如果我们从上一步
也就是簇分配那一步得到了这些
这个表明
样本1 5 6 10被分配给了聚类中心2
然后在移动聚类中心这一步中
我们要做的是
计算出这四个的平均值
即
计算 x(1)+x(5)+x(6)+x(10)
然后计算
它们的平均值
这里聚类中心有
4个点
那么我们要计算和的四分之一
这时μ2就是一个
n维的向量
因为
x(1) x(5) x(6) x(10) 都是
n维的向量
然后
把这些相加
再除以4
因为
有4个点分配到了这个聚类中心
这样聚类中心μ2的移动
就结束了
这个作用是说
将μ2移动到
这四个点的均值处
我要问的问题是
既然我们要让μk移动到分配给它的那些点的均值处
那么如果
存在一个
没有点分配给它的聚类中心 那怎么办?
通常在这种情况下
我们就直接移除
那个聚类中心
如果这么做了
最终将会得到K-1个簇
而不是K个簇
如果就是要K个簇
不多不少
但是有个
没有点分配给它的聚类中心
你所要做的是
重新随机找一个聚类中心
但是直接移除那个中心
是更为常见的方法
当你遇到了一个
没有分配点的
聚类中心
不过在实际过程中
这个问题不会经常出现
这就是K均值算法
在这个视频结束之前
我还想告诉你
K均值的
另外一个常见应用
应对没有很好分开的簇
比如说
到目前为止
我们的K均值算法
都是基于一些像图中所示的数据
有很好的隔离开来的
三个簇
然后我们就用这个算法找出三个簇
但是事实是
K均值经常会用于
一些这样的数据
看起来并没有
很好的分来的
几个簇
这是一个应用的例子 关于T恤的大小
假设你是T恤制造商
你找到了一些人
想把T恤卖给他们
然后
你搜集了一些
这些人的
身高和体重的数据
我猜
身高体重更重要一些
然后你可能
收集到了这样的样本
一些关于
人们身高和体重的样本
就像这个图所表示的
然后你想确定一下T恤的大小
假设我们要设计
三种不同大小的t恤
小号 中号 和大号
那么小号应该是多大的?
中号呢?
大号呢?
有一种
在这样的数据上
使用K均值算法进行聚类
的方法就像我展示的那样
而且可能
K均值可能将这些
聚成一个簇
把这些点
聚成第二个簇
然后把这些点
聚成第三个簇
所以说
尽管这些数据
原本看起来并没有
三个分开的簇
但是从某种程度上讲
K均值仍然能将数据分成几个类
然后你能做的就是
看这第一群人
然后
查看他们的
身高和体重
试着去设计
对这群人来说
比较合身的小号衣服
以及设计一个中号的衣服
设计一个大号的衣服
这就是一种
市场细分的例子
当你用K均值方法
将你的市场分为三个不同的部分
你就能够区别对待
你三类不同的顾客群体
更好的适应
他们不同的需求
就像大中小三种不同大小的衣服那样
这就是K均值算法
而且你现在应该
已经知道如果去实现
K均值算法并且利用它解决一些问题
在下面的视频中
我想把K均值算法
研究的更深入一些
然后讨论一下
如何能让K均值表现得更好一些的问题
Sorry, the comment form is closed at this time.