可以帮助确定聚类数目的Canopy算法及其R语言实现

编程入门行业动态更新时间:2024-10-10 21:31:00

可以帮助确定聚类数<a href=https://www.elefans.com/category/jswz/34/1770256.html style= 目的Canopy算法及其R语言实现"/>

可以帮助确定聚类数目的Canopy算法及其R语言实现

在毕业论文的撰写过程中接触到了Canopy的算法，但没有在R中找到自带的函数实现它。了解过后发现算法流程并不复杂，就自己用R实现了，下面我将介绍Canopy的算法流程，然后把实现它的R语言代码展示出来，再用一个例子展示运算结果。

一、Canopy算法

Canopy算法是McCallum等提出的一种无监督预聚类算法，一般与K-means或K-medoids聚类配合使用。其需要事先设置两个阈值参数T1和T2（T1>T2），再随机选择初始聚类中心，计算各样本点与聚类中心的距离，根据样本点与聚类中心的距离和阈值参数划分簇类。算法流程和图示如下。

步骤1 给定数据集D={x1,x2,⋯,xn}，设置阈值T1 ,T2 （T1>T2）

步骤2 从D中随机选取一个数据点P作为一个Canopy类中心

步骤3 遍历D中其他样本点计算与P的欧氏距离d ，若d<T1，则将该样本点打上弱标记，划入该Canopy类；进一步若d<T2，将该样本打上强标记并从D中删除，被打上强标记的样本点不会再被划入其他Canopy类中

步骤4 重复步骤2和步骤3，当D为空时结束循环。得到k个Canopy类

二、Canopy算法的R语言实现

Canopy=function(df,T1=NULL,T2=NULL,methods='euclidean'){n=nrow(df)			#n为样本量distances=as.matrix(dist(df,method=methods,diag=T,upper=T))	#计算各样本的距离，形成距离阵if(is.null(T1)|is.null(T2)){						#未给出T1或T2时，用给出的参数补充if(!is.null(T1)) T2=T1/1.5					    #补充的参数使T1:T2=3:2else if(!is.null(T2)) T1=1.5*T2else {T2=sum(distances)/(n*(n-1));T1=1.5*T2}    #若T1,T2都未给出，用平均样本距离为T2}if(T1<=T2) {print('参数有误');stop()}center=numeric()		#记录Canopy类的中心canopy=list()		    #记录各Canopy类temp=1:n			    #记录未被删除的样本i=0repeat{i=i+1center=append(center,sample(temp,1))	    #随机选取一个样本作为一个Canopy中心temp.canopy=numeric()				        #临时canopydelete=numeric()					        #记录应被删除的数据for(j in temp){					            #遍历未被删除的数据shall.append=distances[center[i],j]<T1	#距离是否小于T1shall.delete=distances[center[i],j]<T2	#距离是否小于T2	if(shall.append) temp.canopy=append(temp.canopy,j)	#若小于T1,添入临时canopy中if(shall.delete) delete=append(delete,j)			#若小于T2,记录为应删除样本}canopy=append(canopy,list(temp.canopy))	#将距离小于T1的样本正式添入该canopy中temp=temp[-which(temp%in%delete)]		#将距离小于T2的样本从数据集中删除if(length(temp)==0) break}parametrics=c(T1,T2);names(parametrics)=c('T1','T2')list(k=i,Centers=center,Parametrics=parametrics,canopy=canopy)
}

参考了文献：基于密度权重Canopy的改进K-medoids算法 - 中国知网，我将T2的默认值设为了平均样本距离。这个函数的参数methods代表样本相似性度量的定义，用于传入dist()函数计算距离阵，默认就是欧氏距离，也可以根据dist()函数中的method参数换成其他距离。

三、实例展示

用R语言中自带的USArrests数据集作为例子，为方便展示，选取其中第1、4列的数据进行Canopy预聚类。

df=USArrests[,c(1,4)]
c=Canopy(df);c
#结果如下
'''
$k
[1] 4$Centers
[1] 47 49 22 24$ParametricsT1      T2 
17.7711 11.8474 $canopy
$canopy[[1]][1]  1  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 20 21 22 23 24 25 26 27 29 30 31 32
[30] 33 35 36 37 38 40 41 42 43 44 45 46 47 48 49 50$canopy[[2]][1]  7 12 15 18 19 24 29 33 34 39 41 45 48 49$canopy[[3]]
[1]  2  5  6  9 10 18 22 28$canopy[[4]]
[1] 18 24
'''

数据被聚成了4类，Canopy类的中心分别为第47、49、22、24个样本，T1和T2用了默认的1.5倍样本平均距离和平均距离，后面的列表$canopy是各个Canopy类所包含的样本的下标。用一些低水平画图命令可以画出示意图：

plot(df,pch=20,xlim=c(-15,35),ylim=c(0,50))
for(i in c$Centers){points(df[i,],pch=3,col='red')
}
T1=c$Parametrics[1];T2=c$Parametrics[2]
for(i in c$Centers){x1=seq(df[i,1]-T1,df[i,1]+T1,length=200)x2=seq(df[i,1]-T2,df[i,1]+T2,length=200)y1.1=df[i,2]+sqrt(T1^2-(x1-df[i,1])^2)y1.2=df[i,2]-sqrt(T1^2-(x1-df[i,1])^2)y2.1=df[i,2]+sqrt(T2^2-(x2-df[i,1])^2)y2.2=df[i,2]-sqrt(T2^2-(x2-df[i,1])^2)lines(x1,y1.1,lty=2,col='blue');lines(x1,y1.2,lty=2,col='blue')lines(x2,y2.1,col='red');lines(x2,y2.2,col='red')
}

“+”代表Canopy类中心，红色实线是T2界限，蓝色虚线是T1界限。所有样本都会在某一T2界限内，但Canopy类的划分是按T1界限划分的，因此会有些样本会同时存在于不同的Canopy类里。