在很多网络中,如果节点v1连接于节点v2,节点v2连接于节点v3,那么节点v3很可能与v1相连接。这种现象体现了部分节点间存在的密集连接性质。可以用聚类系数(CC)来表示,在无向网络中,聚类系数定义为: C = 2*n/(k*(k-1))其中,n表示在节点v的所有k个邻居间的边数。
[cpp] view plain copy
#include <bits/stdc++.h>
#define N 5
#define M 8
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define m(a, x) memset(a, x, sizeof(a))
#define fs(u,v) fscanf(fp1,"%d %d",&(u),&(v))
using namespace std
FILE *fp1=fr("shuju.dat") , *fq1=fw("jiju.dat")
double s[N] , cc[N]
int du[N],a[N][N],b[N][N]
void read_data()//读入数据
{
m(a,0) , m(b,0)
for (int i=0i<Mi++)
{
int u , v
fs(u,v)//读入数据
a[u][v]=a[v][u] = 1 //无向图
}
for (int i=0i<Ni++)for (int j=0j<Nj++) b[i][j]=a[i][j]*2//计算邻接矩阵
fprintf(fq1,"该图每个点的度数为:\n")
for(int i=0i<Ni++)
{
int l=0
for (int j=0j<Nj++)if(b[i][j]) l++
du[i]=l
fprintf(fq1,"%d %d\n",i,du[i])
}
fprintf(fq1,"\n")
return
}
void get_cluser()//求集聚系数
{
int s1,l1,s2
double sum, ave
fprintf(fq1,"每个点的集聚系数为:\n")
for (int i=0i<Ni++)
{
l1=0
memset(s,0,sizeof(s))
if(du[i]>=2)
{
for (int j=0j<Nj++) if(b[i][j]) s[j]=1
for (int k=0k<Nk++)
{
if(s[k]==1)
{
s1=k
for (int x=s1x<Nx++)
{
if(s[x]==1)
{
s2=x
if(b[s1][s2]) l1++
}
}
}
}
cc[i]=(2.0*l1)/((du[i]*(du[i]-1)))
}
if(du[i]!=0) fprintf(fq1,"%d %f\n",i,cc[i])
}
fprintf(fq1,"\n")
sum=0.0
for(int i=0i<Ni++) sum+=cc[i]*1.0
ave=sum/N
fprintf(fq1,"平均集聚系数为:%f\n",ave)
return
}
int main()
{
read_data()
get_cluser()
fclose(fp1)
fclose(fq1)
return 0
}
聚类分析有两种主要计算方法,分别是凝聚层次聚类(Agglomerative hierarchical method)和K均值聚类(K-Means)。层次聚类又称为系统聚类,首先要定义样本之间的距离关系,距离较近的归为一类,较远的则属于不同的类。可用于定义“距离”的统计量包括了欧氏距离 (euclidean)、马氏距离(manhattan)、 两项距离(binary)、明氏距离(minkowski)。还包括相关系数和夹角余弦。 层次聚类首先将每个样本单独作为一类,然后将不同类之间距离最近的进行合并,合并后重新计算类间距离。这个过程一直持续到将所有样本归为一类为止。在计算类间距离时则有六种不同的方法,分别是最短距离法、最长距离法、类平均法、重心法、中间距离法、离差平方和法。 下面我们用iris数据集来进行聚类分析,在R语言中所用到的函数为hclust。
首先提取iris数据中的4个数值变量,然后计算其欧氏距离矩阵。然后将矩阵绘制热图,从图中可以看到颜色越深表示样本间距离越近,大致上可以区分出三到四个区块,其样本之间比较接近。 data=iris[,-5] dist.e=dist(data,method='euclidean') heatmap(as.matrix(dist.e),labRow = F, labCol = F) X 然后使用hclust函数建立聚类模型,结果存在model1变量中,其中ward参数是将类间距离计算方法设置为离差平方和法。
使用plot(model1)可以绘制出聚类树图。如果我们希望将类别设为3类,可以使用cutree函数提取每个样本所属的类别。 model1=hclust(dist.e,method='ward') result=cutree(model1,k=3) 为了显示聚类的效果,我们可以结合多维标度和聚类的结果。先将数据用MDS进行降维,然后以不同的的形状表示原本的分类,用不同的颜色来表示聚类的结果。可以看到setose品种聚类很成功,但有一些virginica品种的花被错误和virginica品种聚类到一起。