博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
机器学习入门|聚类(一)
阅读量:6814 次
发布时间:2019-06-26

本文共 1489 字,大约阅读时间需要 4 分钟。

hot3.png

聚类算法是在没有给定标签和样本值的前提下进行数据划分,是典型的无监督学习(unsupervised learning)算法。聚类试图将数据集中的样本划分成若干个不相交的子集,称为“簇”,或“类”。一个好的样本划分肯定是簇内的样本相似度高,而簇与簇之间的样本相似度低。

基于原型的聚类

簇是对象的集合,其中每个对象到定义该簇的原型的距离比其他簇的原型距离更近,例如在下面的k-means算法中,原型就是簇的质心。

1.k-means算法

k-means算法把数据集划分为k个簇,划分依据是簇的每一个样本点到质心(均值)的最小化平方误差和,即欧氏距离。欧氏距离越小,则代表这一个簇的紧密程度越大,簇内的样本相似度越高。

给定样本集D={x1,x2,...,xm}D={x1,x2,...,xm},k-means算法得到的簇划分C={C1,C2,...,Ck}C={C1,C2,...,Ck}最小化平方误差

 

E=∑i=1k∑x∈Ci||x−μi||22E=∑i=1k∑x∈Ci||x−μi||22

 

其中μi=1|Ci|∑x∈Cixμi=1|Ci|∑x∈Cix 为簇CiCi的均值向量

但直接求解欧氏距离最小值并不容易,因此采用迭代求解的方法。

1.首先随机选取k个质心,遍历每一个样本点,把样本点归入距它最近的质心所代表的簇中。 

2.重新计算质心位置,即当前簇中的样本点的均值。 
3.重复以上两步,直到算法收敛(更新不再产生划分变动),或者达到停止条件。

k值需要预先指定,而很多情况下k值难以确定,这是k-means的一个缺陷。

k-means的迭代过程本质上是坐标上升的过程。k-means是必定会收敛的,但是和梯度下降一样,只能保证收敛到局部最优,而不能保证收敛到到全局最优。因此初始质心的选择对算法的结果影响十分巨大。

坐标上升法每次通过更新函数中的一维,把其他维的参数看成常量,迭代直到当前维度收敛,再通过多次的迭代计算其他维度以达到优化函数的目的。

因为k-means算法是求均方误差,因此对于一些偏差较大的噪声点非常敏感,因此在k-means基础上可以做适当优化。

K-medoids算法就是一种优化算法,它和k-means唯一不同之处是:k-medoids算法用类中最靠近中心的一个样本点来代表该聚类,而k-means算法用质心来代表聚类。可以减少噪声点带来的影响。

二分K均值法也是一种优化算法,二分K均值法初始时将所有点看成一个簇,在簇的数量小于K的时候进行迭代,算法的核心是选择一个簇一分为二,这里一分为二的方法还是K均值法,只不过K变成了2。二分K均值依次计算每个簇一分为二后新的总平方误差,选择划分后总体平方误差最小的簇进行划分。这样就尽可能避免了k-means落入局部最优的情况。

2.学习向量量化(Learning Vector Quantization)

学习向量量化(LVQ)也是试图找到一组原型来刻画聚类结构,但与k-means不同的是,LVQ的样本带有类别标记。

给定样本集D={(x1,y1),(x2,y2),...,(xm,ym)}D={(x1,y1),(x2,y2),...,(xm,ym)},每个样本xjxj是一个n维向量,yjyj是类别标记,LVQ的目标是学得一组n维原型量{p1,p2,...,pq}{p1,p2,...,pq},每一个原型向量代表一个簇的原型。原型向量的簇标记为ti∈γti∈γ

同样,LVQ也是采用迭代求解的方法。

转载于:https://my.oschina.net/u/3611008/blog/1617417

你可能感兴趣的文章
【cocos2d-js官方文档】四、基础数据类型
查看>>
【IIS错误】IIS各种错误
查看>>
LeetCode题解 | 215. 数组中的第K个最大元素
查看>>
DL4NLP —— 序列标注:BiLSTM-CRF模型做基于字的中文命名实体识别
查看>>
Python图片裁剪实例代码(如头像裁剪)
查看>>
【虚拟机】oracle Virtual Box4.2.6虚拟机正在运行的过程中删除了其上的一个备份,之后虚拟机就无法使用了...
查看>>
数据库MySQL--条件查询/排序查询
查看>>
资源文件加载(Pack URI 方案)
查看>>
步步为营:Asp.Net使用HttpWebRequest通知,抓取,采集
查看>>
求2维数组相邻元素的和的最大值
查看>>
大数据开发实战:离线大数据处理的主要技术--Hive,概念,SQL,Hive数据库
查看>>
VsCode使用之HTML 中 CSS Class 智能提示
查看>>
JMeter基础之一 一个简单的性能测试
查看>>
【转】性能测试工具 性能测试如何做?
查看>>
fullpage.js禁止滚动
查看>>
LoadRunner中响应时间与事物时间详解
查看>>
ZigZag Conversion
查看>>
Android 通过HTTPCLINET POST请求互联网数据
查看>>
Hadoop集群的配置(一)
查看>>
Kafka 学习笔记之 Consumer API
查看>>