(12)发明专利申请
(10)申请公布号 CN 105183796 A (43)申请公布日 2015.12.23
(21)申请号 201510523841.5(22)申请日 2015.08.24
(71)申请人同济大学
地址200092 上海市杨浦区四平路1239号(72)发明人马云龙 刘敏 袁菡 章锋 桂峰
孙源(74)专利代理机构上海科盛知识产权代理有限
公司 31225
代理人叶敏华(51)Int.Cl.
G06F 17/30(2006.01)
权利要求书2页 说明书5页 附图2页
(54)发明名称
一种基于聚类的分布式链路预测方法(57)摘要
本发明涉及一种基于聚类的分布式链路预测方法，包括：步骤S1：对数据集中各个节点的节点度进行并行处理，得到包含所有节点度的集合；步骤S2：采用聚类算法对数据集进行并行处理，得到聚类后的数据集；步骤S3：根据节点度的集合和RA指标，并行处理获取聚类后的数据集中两两节点之间的预测分数值以及预测结果。与现有技术相比，本发明结合了聚类算法，提高了链路预测的精确度，同时结合MapReduce分布式计算框架，提高算法的扩展性与时间效率。
C N 1 0 5 1 8 3 7 9 6 A CN 105183796 A
权 利 要 求 书
1/2页
1.一种基于聚类的分布式链路预测方法，其特征在于，包括：
步骤S1：对数据集中各个节点的节点度进行并行处理，得到包含所有节点度的集合；步骤S2：采用聚类算法对数据集进行并行处理，得到聚类后的数据集；步骤S3：根据节点度的集合和RA指标，并行处理获取聚类后的数据集中两两节点之间的预测分数值以及预测结果。
2.根据权利要求1所述的一种基于聚类的分布式链路预测方法，其特征在于，该分布式链路预测方法的各步骤均在MapReduce框架下进行并行处理。
3.根据权利要求1所述的一种基于聚类的分布式链路预测方法，其特征在于，所述步骤S2中聚类算法为ROCK聚类算法。
4.根据权利要求3所述的一种基于聚类的分布式链路预测方法，其特征在于，所述ROCK聚类算法具体为：
201：输入数据集及预期得到的簇数k，记初始阶段每个节点为一个簇；202：根据数据集的邻接表获取各簇的链接数link[Ci,Cj]，其中，C表示簇，下标i、j表示簇的编号，link[·]表示两个簇之间的链接数；
203：为每个簇Ci建立一个区域堆q[i]，区域堆q[i]包含每一个link[Ci,Cj]＞0的簇Cj，区域堆q[i]中的簇Cj按度量函数g(Ci,Cj)的数值降序排列，区域堆q[i]中排列第一的簇为区域堆q[i]的最佳簇max(q[i])；
204：建立全局堆Q，全局堆Q包含针对所有簇Ci的区域堆q[i]，全局堆Q中的区域堆q[i]按度量函数g(Ci,max(q[i]))的数值降序排列，全局堆Q中排列第一的簇为全局堆Q的最佳簇max(Q)；
205：每一回合合并区域堆q[i]中的最佳簇和全局堆Q的最佳簇，合并后根据合并结果更新区域堆和全局堆，当簇数等于k时，结束合并，得到聚类后的数据集。
5.根据权利要求4所述的一种基于聚类的分布式链路预测方法，其特征在于，所述度量函数g(Ci,Cj)满足以下公式：
式中，ni和nj分别为簇Ci和簇Cj中的节点个数，f(θ)为设定值；所述度量函数g(Ci,max(q[i]))满足以下公式：
式中，nk为簇max(q[i])中的节点个数。
6.根据权利要求1所述的一种基于聚类的分布式链路预测方法，其特征在于，所述步骤S3具体为：
301：输入聚类后的数据集G(V,E)的邻接表，得到节点的邻居集Γ[n]，其中，G(V,E)为一个无权无向网络，V表示节点集，E表示边集；
302：从Γ[n]中选取任意不同的两个邻居节点，按照节点ID的大小给全部邻居节点排序，得到两两点对之间的共同邻居；
2
CN 105183796 A
权 利 要 求 书
2/2页
303：根据公式
获取两两节点之间的预测分数值S'xy并输出预测结果，
而Com'xy则是指节点x与节点y的其中，Kz指节点x与节点y的共同邻居节点z的节点度，共同邻居集。
7.根据权利要求1所述的一种基于聚类的分布式链路预测方法，其特征在于，在步骤S1之间，将数据集划分为训练集和测试集，训练集经步骤S1、步骤S2和步骤S3处理后得到预测结果，利用测试集和AUC验证该预测结果的有效性。
8.根据权利要求7所述的一种基于聚类的分布式链路预测方法，其特征在于，所述利用测试集和AUC验证该预测结果的有效性具体为：
1)由两两节点之间的预测分数值取出测试集中所有边的预测分数值和边集补集中所有边的预测分数值，所述边集补集为不存在的边的集合；
2)分别从测试集和边集补集中随机选取一条边进行预测分数值比较，获取AUC的值，并根据AUC验证该预测结果的有效性。
3
CN 105183796 A
说 明 书
一种基于聚类的分布式链路预测方法
1/5页
技术领域
[0001]
本发明涉及数据挖掘技术领域，尤其是涉及一种基于聚类的分布式链路预测方
法。背景技术
数据挖掘是指从大量的数据中通过算法搜索隐藏于数据中的信息的过程。近年来，由于可供挖掘的数据量越来越庞大，数据挖掘引起了信息产业界的极大关注。链路预测是指通过已知的网络节点和网络结构等信息预测出网络中尚未产生连边的两个节点之间存在连接的可能性。预测既包含了对未知链接(网络中实际存在但尚未被我们发现的链接)的预测，又包含了对未来链接(网络中目前不存在，但未来可能存在的链接)的预测。链路预测处理的是信息科学中最基本的问题——缺失信息的还原和预测。[0003] 链路预测的方法中比较主流的是基于相似性的链路预测算法，其主要包括三类，基于节点邻居的相似性、基于极大似然估计以及基于概率模型。而在这几类中，代表性相似性指标包括基于共同邻居的相似性指标(common neighbor，CN)、基于路径相似性的Katz指标以及基于全局随机游走的平均通勤时间(average commute time，ACT)指标等等。基于共同邻居的相似性指标CN由于研究较早，且性能表现良好，常常作为研究中的基准参考算法。在第一类方法中，由于计算复杂度更低，基于局部信息的方法的效率要高于基于全局信息的方法。然而，由于信息不充分，基于局部信息的方法预测精度更低。第二类方法假定了网络结构的组织原则，有详细的规则和能够得到使已观察到的结构的可能性最大化的特定的参数。从而可以利用这些规则和参数计算出未知链接存在的可能性。第三类方式是应用机器学习技术。Hasan等人将链路预测看作一项监督式学习任务，即预测出两个潜在连接的节点是积极的还是消极的。从作者合作网络中提取出的特征由距离、集聚和拓扑特征组成。他们用不同的性能指标来比较七个经典的链路预测算法。由于计算复杂度较高，第二、三类算法只适合于小规模网络的链路预测。
[0002]
发明内容
本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种基于聚类的分
布式链路预测方法，结合了聚类算法，提高了链路预测的精确度，同时结合MapReduce分布式计算框架，提高算法的扩展性与时间效率。
[0005] 本发明的目的可以通过以下技术方案来实现：[0006] 一种基于聚类的分布式链路预测方法，包括：[0007] 步骤S1：对数据集中各个节点的节点度进行并行处理，得到包含所有节点度的集合；
[0004]
步骤S2：采用聚类算法对数据集进行并行处理，得到聚类后的数据集；
[0009] 步骤S3：根据节点度的集合和RA指标，并行处理获取聚类后的数据集中两两节点之间的预测分数值以及预测结果。
[0008]
4
CN 105183796 A[0010]
说 明 书
2/5页
该分布式链路预测方法的各步骤均在MapReduce框架下进行并行处理。[0011] 所述步骤S2中聚类算法为ROCK聚类算法。[0012] 所述ROCK聚类算法具体为：[0013] 201：输入数据集及预期得到的簇数k，记初始阶段每个节点为一个簇；[0014] 202：根据数据集的邻接表获取各簇的链接数link[Ci,Cj]，其中，C表示簇，下标i、j表示簇的编号，link[·]表示两个簇之间的链接数；[0015] 203：为每个簇Ci建立一个区域堆q[i]，区域堆q[i]包含每一个link[Ci,Cj]＞0的簇Cj，区域堆q[i]中的簇Cj按度量函数g(Ci,Cj)的数值降序排列，区域堆q[i]中排列第一的簇为区域堆q[i]的最佳簇max(q[i])；[0016] 204：建立全局堆Q，全局堆Q包含针对所有簇Ci的区域堆q[i]，全局堆Q中的区域堆q[i]按度量函数g(Ci,max(q[i]))的数值降序排列，全局堆Q中排列第一的簇为全局堆Q的最佳簇max(Q)；[0017] 205：每一回合合并区域堆q[i]中的最佳簇和全局堆Q的最佳簇，合并后根据合并结果更新区域堆和全局堆，当簇数等于k时，结束合并，得到聚类后的数据集。[0018] 所述度量函数g(Ci,Cj)满足以下公式：
[0019]
式中，ni和nj分别为簇Ci和簇Cj中的节点个数，f(θ)为设定值；
[0021] 所述度量函数g(Ci,max(q[i]))满足以下公式：
[0020] [0022]
式中，nk为簇max(q[i])中的节点个数。
[0024] 所述步骤S3具体为：[0025] 301：输入聚类后的数据集G(V,E)的邻接表，得到节点的邻居集Γ[n]，其中，G(V,E)为一个无权无向网络，V表示节点集，E表示边集；[0026] 302：从Γ[n]中选取任意不同的两个邻居节点，按照节点ID的大小给全部邻居节点排序，得到两两点对之间的共同邻居；
[0023] [0027]
303：根据公式
获取两两节点之间的预测分数值S'xy并输出预测结
果，其中，Kz指节点x与节点y的共同邻居节点z的节点度，而Com'xy则是指节点x与节点y的共同邻居集。
[0028] 在步骤S1之间，将数据集划分为训练集和测试集，训练集经步骤S1、步骤S2和步骤S3处理后得到预测结果，利用测试集和AUC验证该预测结果的有效性。[0029] 所述利用测试集和AUC验证该预测结果的有效性具体为：
[0030] 1)由两两节点之间的预测分数值取出测试集中所有边的预测分数值和边集补集中所有边的预测分数值，所述边集补集为不存在的边的集合；
[0031] 2)分别从测试集和边集补集中随机选取一条边进行预测分数值比较，获取AUC的
5
CN 105183796 A
说 明 书
3/5页
值，并根据AUC验证该预测结果的有效性。[0032] 与现有技术相比，本发明具有以下优点：[0033] 1)在进行链路之前先对数据集进行聚类，创新地利用聚类提高了链路预测的精确度，同时聚类过程中，进行堆与堆之间的合并时，同一时间内对所有堆的大小进行比较可以运用分布式进行处理，用不同的设备建立代号不同的堆，需要合并时可以按照键值对的值进行处理，能够大大缩减时间。
[0034] 2)基于MapReduce对该链路预测算法实现了并行化，利用将网络划分为以每个节点为中心的局部子图进行计算，大大提高了方法的效率。
[0035] 3)ROCK(RObust Clustering using linKs)聚类算法是一种鲁棒的用于分类属性的聚类算法，该算法属于凝聚型的层次聚类算法。之所以鲁棒是因为在确认两对象(样本点/簇)之间的关系时，考虑了他们共同的邻居(相似样本点)的数量，在算法中被叫做链接(Link)的概念。而其他聚类算法只关注对象之间的相似度，ROCK聚类算法更适合用于大规模复杂网络中大小不一的聚类。[0036] 4)划分测试集，增加对预测结果的验证，从而保证预测结果的精度和可靠性。附图说明
图1为MapReduce处理数据集的过程图；[0038] 图2为本发明并行化方案的整体流程图。
[0037]
具体实施方式
[0039] 下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。
[0040] 如图1所示，在Hadoop平台的HDFS(Hadoop Distributed File System)中，MapReduce通过划分的步骤，将海量数据分组并将其的处理分配给主节点下的各个分节点共同完成，最后整合各个分节点的计算结果得到最终结果。MapReduce将整个数据处理过程抽象为两个部分，用函数表示，分别为Map和Reduce。Map的工作是将任务分解成多个(即Split n，n为0,1,2…)，而Reduce则负责汇总多任务处理的结果(即Part n，n为0,1,2…)。MapReduce框架下的数据集必须可以分解成多个小数据集，并且可以被并行化处理。其中，MapReduce的数据是文本，按行计算的。[0041] 如图2所示，一种各步骤均在MapReduce框架下并行化处理的、基于聚类的分布式链路预测方法包括：[0042] 步骤S1：将原数据集划分为训练集和测试集，对训练集中各个节点的节点度进行并行计算，得到包含所有节点度的集合。利用训练集的信息进行链路预测，而测试集的信息是用于对链路预测的结果进行精度评价。[0043] 步骤S2：采用分布式ROCK聚类算法对训练集进行聚类，得到聚类后的训练集。具体为：
201：输入训练集及预期得到的簇数k，记初始阶段每个节点为一个簇，k为预设的
期望值；
[0044]
6
CN 105183796 A[0045]
说 明 书
4/5页
202：并行化处理时，将训练集分为M组，在每组中，分别计算分组中每个点与整个训练集中的每个点之间的相似度，得到数据的邻居矩阵和邻接表，是邻居的为1，不是邻居的为0，计算分组中每个数据点与整个训练集中每个数据点之间的共同邻居数，从而得到键值对L<(Pi,Pj),link(Pi,Pj)>，其中Pi和Pj为训练集中的任意节点，并得到邻居数矩阵；[0046] 则根据训练集的邻接表可获取各簇的链接数link[Ci,Cj]，其中，C表示簇，下标i、j表示簇的编号，link[·]表示两个簇之间的链接数；[0047] 203：为每个簇Ci建立一个区域堆q[i]，区域堆q[i]包含每一个link[Ci,Cj]＞0的簇Cj，区域堆q[i]中的簇Cj按度量函数g(Ci,Cj)的数值降序排列，区域堆q[i]中排列第一的簇为区域堆q[i]的最佳簇max(q[i])；[0048] 度量函数g(Ci,Cj)满足以下公式：
[0049]
式中，ni和nj分别为簇Ci和簇Cj中的节点个数，f(θ)为设定值；
[0051] 204：建立全局堆Q，全局堆Q包含针对所有簇Ci的区域堆q[i]，全局堆Q中的区
全局堆Q中排列第一的簇为全局域堆q[i]按度量函数g(Ci,max(q[i]))的数值降序排列，
堆Q的最佳簇max(Q)；
[0052] 度量函数g(Ci,max(q[i]))满足以下公式：
[0050] [0053]
式中，nk为簇max(q[i])中的节点个数；
[0055] 205：每一回合合并区域堆q[i]中的最佳簇和全局堆Q的最佳簇，合并后根据合并结果更新区域堆和全局堆，当簇数等于k时，结束合并，得到聚类后的训练集。[0056] 通过聚类形成了一个新的网络，在这个网络中存在的边的关系更接近于实际，所以有助于之后的链路预测。聚类算法还可以采用CURE算法、CHAMELEON算法等等。[0057] 步骤S3：对于聚类后的训练集的邻接表，根据节点度的集合和RA(resource allocation)指标，获取训练集中两两节点之间的预测分数值。具体为：[0058] 301：输入聚类后的训练集G(V,E)的邻接表，得到节点的邻居集Γ[n]，其中，G(V,E)为一个无权无向网络，V表示节点集，E表示边集；[0059] 302：从Γ[n]中选取任意不同的两个邻居节点，按照节点ID的大小给全部邻居节点排序，得到两两点对之间的共同邻居，节点ID为训练集中节点从上到下依次排序的序号；
[0054] [0060]
303：根据公式
获取两两节点之间的预测分数值S'xy并输出预测结
果，其中，Kz指节点x与节点y的共同邻居节点z的节点度，而Com'xy则是指节点x与节点
y的共同邻居集。
[0061] 根据预测分数的大小进行排序即可得到最后的预测结果，预测分数值越高的边其存在的可能性越大。
7
CN 105183796 A[0062]
说 明 书
5/5页
最后，利用测试集和AUC验证该预测结果的有效性。具体为：
[0063] 1)由两两节点之间的预测分数值提取出测试集中所有边的预测分数值和边集补集中所有边的预测分数值，边集补集为不存在的边的集合，测试集和训练集是由网络的边集划分而成的；
[0064] 2)分别从测试集和边集补集中随机选取一条边进行预测分数值比较，重复n次，获取AUC的值，并根据AUC验证该预测结果的有效性，重复次数n由数据集的大小决定。[0065] AUC即ROC曲线下的面积，英文全称是area under the receiver operating characteristic curve。它的实现过程是：在未观测到或者说是不存在的边的集合中，通过链路预测算法，在每对节点有可能存在的连边中选择一条赋予其一个分值Sxy，再随机从测试集中选择一条边赋予其一个分值
[0066] [0067] [0068]
最后对两个分值进行比较：
加1分，共计n′次加0.5分，共计n″次
即，如果测试集ETest中的边所得的分数大于边集补集的边的分数，就加1分，反之，加0.5分。独立的比较n次之后，如果有n′次的得分是1，而有n″次的得分是0.5，则AUC的定义为：
[0069]
AUC值越高，预测精确度就越高，若AUC值没有达到设定值，则重新选择簇数k的数
值，进行重新聚类和预测分数值的计算。图2中补集指不存在的边和测试集的集合，AUC值的检验就是查看该分布式链路预测方法能否把这几条本来存在但被划成不存在的边(测试集)找出来。
[0071] 对小规模网络挖掘时，传统单机算法比本发明所提供的方法可能更具有效率。而对于大规模网络挖掘，相比于传统单机算法挖掘社团，本发明所提供的方法的优越性十分明显。本发明在构建了寄递关系网络模型基础上，并利用MapReduce分布式计算框架以及聚类后寄递关系网络，提高传统链路预测方法的运行效率，最终实现准确、高效地对寄递网络进行链路预测。
[0070]
8
CN 105183796 A
说 明 书 附 图
1/2页
图1
9
CN 105183796 A
说 明 书 附 图
2/2页
图2
10
因篇幅问题不能全部显示，请点此查看更多更全内容