图聚类的算法及其在社会关系网络中的应用

2019-08-15袁璐郑策山东工程职业技术大学

数码世界 2019年8期

袁璐郑策山东工程职业技术大学

在大数据时代下，聚类这种不用监督的学习算法占有非常重要的地位。随着科技的不断发展，聚类算法的研究也取得了非常大的进步。而本文主要对图聚类的算法进行分析和研究，并在划分的图聚类中，对点和点之间距离的计算方法重点进行比较同时也比较其对聚类结果的硬性。还有因社会关系网络图中的点是没有坐标值的，因此无法使用曼哈坦距离和欧几里得距离，但可以使用K-medoids 聚类算法。在使用此聚类算法时，可以使用随机漫步距离算法和最短距离算法，社会关系网络图通过DBLP 数据集构成各个子图，并结合相关实验数据对两种算法的优缺点进行验证，从而进一步得到最短距离算法获得的聚类效果最佳。

一、聚类、图聚类以及社会网络综述

聚类指的是把数据集分成若干类或簇的过程，从而使不同类数据对象的相似度较低的让同时使同类数据对象的相似度较高。而目前的聚类算法有：层次聚类算法、网格聚类算法、划分聚类算法、密度聚类算法以及模型聚类算法等。

在对聚类进行分析时，其变体是一项非常有挑战的研究课题，即图聚类。而其主要指的是把图中相关的边分以及相对连接紧密的结点组成一个可以用一个抽象结点来表示的子图。其子图内各结点的相似性比较高，但子图之间的结点只有较低的相似性。另外图聚类有许多不同的方式，突出的有基于密度的聚类、Markov 聚类以及谱聚类等。

社会网络分析在20 世纪30 年代被提出，并成为一种相对比较重要的社会定量研究方法。其主要指社会成员以及社会成员之间关系的集合，并用来表示成员间各种社会关系的边以及各成员的节点，从而组成图结构，进而对社会网络进行描述[2]。另外，社会关系有很多种表现形式，例如：上下级之间的关系、文章合著关系、朋友之间的关系以及科研合作关系等。还有社会网络关系的图聚类算法主要有：Kernighan-lin 算法、G-N 算法、Newman 算法、过滤算法以及谱平分算法等。

二、图聚类的算法

1、最短路径距离算法

在图论研究中比较经典的一个算法问题就是最短路径问题，而最短路径问题时在图中的两个点之间找一个最短的路。最短路径距离算法也叫作Dijkstra 算法，其思想是：设G=（V,E,W）的带权有向图。也就是说先把图中的顶点几何V 组成两组，一组是对最短路径的顶点集合（S）已求出，另一组是对其余最短路径的顶点集合（U）未求出，然后把未求出最短路径的顶点根据最短路径长度的增长顺序依次加入到已求出最短路径的顶点集合中去。

2、随机漫步距离算法

若P 是一个由多个（N）顶点组成的图GN×N 转移概率矩阵，那么此矩阵的第i 行第j 列的元素为第i 个顶点一步跳转到第j 个顶点的概率值；若是随机漫步从第i 个顶点到第j 个顶点走的最大步长，并假设随机漫步起始概率为c ∈（0,1），那么随机漫步的第i 个顶点到第j 个顶点距离的定义为：其中T 指的是第i 个顶点到第j 个顶点的一条路径，步长使lengh（T），对应的转移概率是P（T）。而随机漫步距离矩阵指的是各顶点之间的随机漫步距离组成的矩阵，其公示为：，其中，P 是图G 的转移概率，Ri是l 步内可达到的随机漫步距离矩阵。

3、K-medoids 算法

K-medoids 算法的工作过程为：先随机从n 个数据对象中挑选k 个对象当作初始聚类的中心，而剩下的其他对象就按照他们和这些聚类中心的距离依次分配到和其最相似的聚类；其次，对各个聚类的新聚类中心进行再次计算时，可选择此聚类中距离均值点最近的真实点，并不断对这个过程进行重复，从而使各个点的分配不在出现变化的同时也能得到满足。在这个算法中，初始聚以K 个对象为中心点，之后以局部最佳结束，但这个方法对孤立点非常敏感。因此，在对这个算法进行改进时，初始聚类的中心点先随机选取一个来当做对象；其次，对第二个聚类中心点进行选取时，其和初始聚类的中心点的距离要最远；然后到选取去第三个聚类中心点时，和第二个聚类中心点的挑取一样，并依次类推，直到第k 个聚类中心点为止。

三、实验

1、衡量指标

衡量指标用density 来表示，若图是无向图，那么就先要对整个大图进行统计，而图在没有进行分割之前，总共有n 条边，然后依次计算k 类的每类包含的点之间的边数，假如分别是n1,n2,...,nk,那么最后的计算就是density=（n1+n2+...+nk）/n。

当用程序将这个算法进行实现后，其运行程序收集数据，指在每个K 值的情况下，需要进行10 次分类，之后取10 次分类比率的比均值当做前k 值下的最后比率density，通过两个算法的density 值比较出优劣，其中，最短距离算法得到的比率用density1 表示，随机漫步距离算法得到的比率用density2 表示，对比如图1 所示。