搜索
查看: 1268|回复: 1

聚类分析简介

[复制链接]

11

主题

54

帖子

242

积分

中级会员

Rank: 3Rank: 3

积分
242
QQ
发表于 2018-4-29 13:32:49 | 显示全部楼层 |阅读模式
聚类分析简介

聚类就是主观地将数据点分到数个cluster中,相同cluster中的数据点相对应不同cluster中的数据点,互相之间更相似(距离近)。简而言之,将具有相同特征的数据分到不同的cluster中,然后在聚集到一起。
聚类算法:
K-Means: 该聚类算法是为了发现指点数目K个cluster,该cluster被其质心(prototype)所代表的。
Hierarchical: 在该聚类过程中逐步汇聚关系近的数据点,最后形成一个等级关系图。每个数据点在最开始都是单个cluster,然后一步一步将距离近的点合并到一起,直到最后汇聚到一个点。
聚类过程:
k-means:
1. 随机选择K个点作为初始质心
2. 将每个点分配到最近的质心形成K个cluster
3.重新计算分配后的每个cluster的质心位置,然后计算点到质心的距离,再将点分配到最近的质心所在的cluster
4. 重复上面计算-分配-计算的步骤直到所有的质心位置都不会发生改变(或连续两次分配后质心不发生变化)
如图,图示十字表示质心所在位置:

K-means聚类的目的是最小化每个点到它最近cluster的质心的距离。我们这里采用Euclidean distance来计算距离,the sum of the squared error(SSE)。简而言之,计算它们的差值,每个点到其最近质心的Euclidean distance,然后计算总的SSE。


dist指的是两点在Euclidean space的standard Euclidean(L2)distance。该聚类的思想是通过合适的质心,最小化SSE,那么可知,最小化的cluster的SSE的点就是该cluster的平均点。那么质心就为:

Hierarchical Clustering:
1. 首先将每个点都作为单独的cluster,计算cluster之间距离(点与点之间的距离)
2. 将距离最近的两个cluster合并到一起
3. 重复计算新的cluster和原始cluster之间距离,合并最近距离的不同cluster
4. 重复以上步骤,直所有的cluster(最开始的cluster是各个点)合并为一个cluster
这里问题的关键也是计算cluster之间的距离问题,以下图示三种距离计算方式:

MIN(Single Link):使用两个cluster中距离最近的两的点的距离
MAX(Complete Link):使用两个cluster总距离最远的两个点的距离
Group Average:使用两个cluster中所有点距离的均值
我们也可以使用质心代表每个cluster,那么cluster之间的距离就是不同cluster间的质心的距离。Ward’s方式,就是假设通过质心来代表每个cluster,但是计算合并两个cluster所增加的SSE,和K-means一样,Ward’s方法也是最小化点到其质心的距离平方和。
举例说明:
定义了p1-p6共6个点(左)及其二维坐标位置(右)

依次计算了两两之间的距离(右)

这里只介绍Group Average的计算方法:
针对cluster C1和cluster C2,分别有mi和mj个数据点,那么其距离表示为:

该例子中,我们计算cluster{m1,m2…mi}和cluster{m1,m2..mj}的距离:
dist{3,6,4},{1} = (0.22+0.37+0.23)/(3*1)= 0.28
dist{2,5},{1} = (0.2357+0.3421)/(2*1) = 0.2889
dist{3,6,4},{2,5} = (0.15+0.28+0.25+0.39+0.2+0.29)/(6*2)=0.26
因为dist{3,6,4},{2,5}之间的距离最小,所以它们合并成为第四层,如图:

我们可以根据系统树图中合并两cluster的水平线可以得到两个cluster的距离,同时对于能最好的描述整体数据的cluster的数目,可以通过横向截断最大距离的垂线的水平线所跨越的cluster数目决定,下图AB间为最大距离,跨越了4条垂线,4个cluster:

最后Hierarchical Clustering距离计算方法有很多种,这里列出三种,其他可以查wiki百科:



K-means和Hierarchical clustering差别:
Hierarchical cluster不能用于大数据样本,但是K-means可以
K-means由于会主观地指定K个cluster及其最初K的位置,那么结果会受到K的个数及位置的影响,而Hierarchical clustering的结果是可重复的
K-means适用于多维度的数据(例如2D的圆,3D的球形)
其他:
还有一种常见聚类方法是根据密度分布进行的,DBSCAN: 该聚类方法是根据数据的分布密度生成一个个群,该群数量是根据给算法自动决定的,该方法以后用到再加到评论里面喽!






上一篇:linux下启动R报错
下一篇:服务器上运行jupyter notebook
苛求远离完美
回复

使用道具 举报

11

主题

54

帖子

242

积分

中级会员

Rank: 3Rank: 3

积分
242
QQ
 楼主| 发表于 2018-4-29 13:36:11 | 显示全部楼层
下一步,主成分析
苛求远离完美
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|生信技能树    

GMT+8, 2019-6-19 23:47 , Processed in 0.033051 second(s), 26 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.