聚类

文章目录一、定义二、相似度/距离计算方法总结三、k-means算法1.基本思想2.迭代过程3.简单应用4.总结四、层次聚类五、密度聚类DBSCAN算法1相关概念2算法流程一、定义聚类就是对大量未知标注的数据集按照数据内在的相似性将数据集划分为多个类别使类别内的数据相似度较大而类别间的数据相似度较小属于无监督的学习方法。给定一个有N个对象的数据集构造数据的k个簇k≤n满足以下条件每个簇至少包含一个对象每个对象属于且仅属于一个簇将满足上述条件的k个簇称作一个合理划分二、相似度/距离计算方法总结三、k-means算法1.基本思想对于给定的类别数目k首先给出初始划分通过迭代改变样本和簇的隶属关系使得每一次改进之后的划分方案都较前一次好。2.迭代过程假定输入样本为S x 1 , x 2 , . . . . . , x n Sx_1,x_2,.....,x_nSx1​,x2​,.....,xn​则算法步骤为选择初始的k个类别中心μ 1 , μ 2 , . . . . . , μ k μ_1,μ_2,.....,μ_kμ1​,μ2​,.....,μk​可以根据先验知识对于每个样本x i x_ixi​将其标记为距离类别中心最近的类别这里的距离度量方案我们经常使用欧式距离将每个类别的中心更新为隶属该类别的所有样本的均值重复最后两步直到类别中心的变化小于某阈值3.简单应用对于这样的一些数据点初始情况下的散点图如下使用聚类算法进行聚类importnumpyasnpimportrandomimportpandasaspdimportmatplotlib.pyplotasplt times50# 迭代次数# 随机选取k个聚类质心点defselect_center(data,k,m,n):cluster_centernp.zeros((k,n))idsrandom.sample(range(m),k)foriinrange(k):cluster_center[i]data[ids[i]]returncluster_center# 计算两点的欧式距离defdistance(p1,p2):returnnp.sum((p1-p2)**2)**0.5# 求解某样本到各聚类质心点的最近点defget_cluster(point,cluster_center):disdistance(point,cluster_center[0])nearest0foriinrange(1,len(cluster_center)):new_disdistance(point,cluster_center[i])ifnew_disdis:disnew_dis nearestireturnnearestdefk_means(data,k):mlen(data)# 样本数量nlen(data[0])# 每条数据的维度# 初始化聚类质心点cluster_centernp.zeros((k,n))idsrandom.sample(range(m),k)# 随机产生k个不重复的indexforiinrange(k):cluster_center[i]data[ids[i]]clusternp.zeros(m,dtypenp.int)# 初始情况下所有点均没有聚类# 迭代times次foriinrange(times):next_cnp.zeros((k,n))# 下一轮聚类质心点c_numbernp.zeros(k)# 每个簇的样本数量forjinrange(m):cluster[j]get_cluster(data[j],cluster_center)next_c[cluster[j]]data[j]c_number[cluster[j]]1fortinrange(k):cluster_center[t]next_c[t]/c_number[t]# 更新每个聚类的质心点坐标returnclusterif__name____main__:datanp.array(pd.read_table(data.txt,headerNone,names[x,y]))x[item[0]foritemindata]y[item[1]foritemindata]clusterk_means(data,4)color[red,yellow,blue,black]forx,y,iinzip(x,y,cluster):plt.scatter(x,y,colorcolor[i])plt.show()得到这样的结果4.总结优点是解决聚类问题的一种经典算法简单、快速对处理大数据集该算法保持可伸缩性和高效率当簇近似为高斯分布时它的效果较好缺点在簇的平均值可被定义的情况下才能使用可能不适用于某些应用必须事先给出k(要生成的簇的数目)而且对初值敏感对于不同的初始值可能会导致不同结果。不适合于发现非凸形状的簇或者大小差别很大的簇将簇中所有点的均值作为新质心若簇中含有异常点将导致均值偏离严重对躁声和孤立点数据敏感四、层次聚类层次聚类方法试图在不同层次上对数据集进行划分对给定的数据集进行层次的分解直到某种条件满足为止。具体又可分为凝聚的层次聚类AGNES算法一种自底向上的策略首先将每个对象作为一个簇两个簇间的距离由这两个不同簇中距离最近的数据点对的相似度来确定聚类的合并过程反复进行直到所有的对象最终满足簇数目。分裂的层次聚类DIANA算法采用自顶向下的策略首先将所有的对象初始化到一个簇中然后根据一些原则(比如最大的欧式距离)将该簇分类。直到到达用户指定的簇数目或者两个簇之间的距离超过了某个阈值。AGNES中簇间距离的不同定义最小距离两个集合中最近的两个样本的距离容易形成链状结构最大距离两个集合中最远的两个样本的距离若存在异常值则不稳定平均距离两个集合中样本间两两距离的平均值方差使得簇内距离平方和最小簇间平方和最大五、密度聚类密度聚类方法的指导思想是只要样本点的密度大于某阈值则将该样本添加到最近的簇中。这类算法能克服基于距离的算法只能发现“类圆形”(凸)的聚类的缺点可发现任意形状的聚类且对噪声数据不敏感。但计算密度单元的计算复杂度大需要建立空间索引来降低计算量。DBSCAN算法1相关概念对象的ε-邻域给定对象在半径ε内的区域核心对象对于给定的数目m如果一个对象的ε-邻域内对象不包括自己的数量≥m则称该对象为核心对象直接密度可达给定一个对象集合D如果p在q的ε-邻域内而q是一个核心对象则我们说对象p从对象q出发是直接密度可达的。密度可达如果存在一个对象链p 1 p 2 . . . . p n , p 1 q , p n p p_1p_2....p_n,p_1q,p_npp1​p2​....pn​,p1​q,pn​p对p i ∈ D , ( 1 ≤ i ≤ n ) p_i \in D,(1≤i≤n)pi​∈D,(1≤i≤n)p i 1 p_{i1}pi1​是从p i p_ipi​关于ε和m直接密度可达的则对象p是从对象p关于ε和m密度可达的。密度相连如果对象集合D中存在一个对象o使得对象p和q是从o关于ε和m密度可达的那么对象p和q是关于ε和m密度相连的簇密度相连的点所形成的样本的集合噪声不包含在任何簇中的对象成为噪声2算法流程如果一个点p的ε-邻域包含多于m个对象则创建一个p作为核心对象的新簇寻找并合并核心对象直接密度可达的对象没有新点可以更新簇时算法结束未完待续。。。