Network data的K-Means聚类实现

2018-03-27

长路漫漫

从去年12月份的科研训练项目开题到现在，项目一直没什么进展。最近突然意识到了时间的紧迫性，慢慢开始着手去做。面对自己之前毫不了解的领域，真是不知该从何下手。
俗话说，不会百（谷）度（歌）的程序猿不是一个好程序猿，于是动用了学院领导整天挂在嘴边的”信息检索能力”，所以除了向老师请教问题之外，大部分都是从博客上学习到的。

正文

第一周，目标是对一个网络数据先用K-Means算法进行聚类分析

第一步：获取数据

没有数据做测试，所有的算法都是扯淡，所以第一步先要获取数据。白老师给推荐了一个Network data网站里面有一些小型的GML格式的网络数据文件可做测试。我选择的测试数据集为：American College football，当然也可以选择其他的GML格式的数据集

第二步：读取数据

使用Python的NetworkX库可以很好地处理网络数据，其中networkx.read_gml()可以读取GML格式的文件，并得到一个Graph对象

G = nx.read_gml(filename)

第三步：处理数据

得到G后，可以先把其转化成一个稀疏矩阵

A = nx.adjacency_matrix(G)
print(A)

此时打印出稀疏矩阵

(0, 31) 1
(0, 57) 1
(0, 62) 1
(0, 71) 1
(0, 82) 1
(0, 84) 1
(0, 89) 1
(0, 95) 1
(0, 101) 1
(0, 109) 1
(0, 112) 1
(1, 5) 1
(1, 32) 1
(1, 36) 1
(1, 43) 1
(1, 59) 1
(1, 61) 1
(1, 91) 1
(1, 93) 1
(1, 103) 1
(1, 108) 1
(2, 17) 1
(2, 63) 1
(2, 70) 1
: :
(112, 54) 1
(112, 84) 1
(112, 89) 1
(112, 101) 1
(113, 14) 1
(113, 24) 1
(113, 29) 1
(113, 31) 1
(113, 32) 1
(113, 40) 1
(113, 44) 1
(113, 57) 1
(113, 66) 1
(113, 103) 1
(114, 2) 1
(114, 7) 1
(114, 24) 1
(114, 68) 1
(114, 72) 1
(114, 77) 1
(114, 79) 1
(114, 92) 1
(114, 98) 1
(114, 106) 1

第三步：聚类

调用Python的sklearn库，可查看其官方网址中的K-Means文档

cls = KMeans(n_clusters).fit(A)

第四步：绘图

聚类完成后，每一个节点现在已经有label了，对每一类节点分一种颜色。调用networkx.draw()函数，进行绘制图像，然后调用plt.savefig()保存图像到本地，或者调用plt.show()函数显示图像。最后清空一下plt的内容(可有可无，如果需要多次画图，最好清空一下)

代码

'''
Author : Victor He
E-mail : victor-he@qq.com
'''

import networkx as nx
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
import numpy as np

def kmeans(filename, n_clusters):
    '''
    参数说明：
	    filename：gml文件名或路径
	    n_clusters：聚类个数
    '''

    G = nx.read_gml(filename)	#读取gml格式的文件得到一个Graph对象
    A = nx.adjacency_matrix(G)     	#获得G的稀疏矩阵
    #A = A.todense()                	#获得密集矩阵
    #A = np.array(A)                 #转化为numpy数组

    cls = KMeans(n_clusters).fit(A)	#调用sklearn中的KMeans方法
    print(cls.labels_)

    #选取不同的颜色，用来标记不同类的节点
    color = ['green', 'red', 'blue', 'black', 'grey', 'yellow', 'purple']
    colors = []
    for i in cls.labels_:
        colors.append(color[i])

    nx.draw(G,with_labels=False,node_color=colors)
    #plt.savefig("temp.jpg")  #保存图片，一定要放在plt.show()前，不然保存的就时空白图片
    plt.show()
    fig = plt.figure()		  #清空plt的内容

if __name__ == '__main__':
    kmeans('football.gml', 3)

结果

聚类结果

致谢

今日有幸拜读白老师的论文：A novel community detection algorithm based on simplification of complex networks，对老师的专业水平和英语素养深感敬佩。最后，感谢白老师在学业规划和科研训练上的耐心指导，我们定会继续努力，不负师望。