一种基于混合层次聚类的RDF数据平衡分割算法

摘要

一种基于混合层次聚类的RDF数据平衡分割算法，包括如下步骤：通过对唯一属性值节点的合并和高邻域节点的移除来压缩RDF聚类数据规模；通过基于邻域节点的相似性度量和基于交互边的相似性度量计算RDF图中节点和数据块儿间的相似性；通过逐层AP聚类发现图中所有潜在的聚类中心和数据块儿，实现图的粗化；通过平衡调整算法实现RDF图分割的平衡；最后通过K-means聚类算法实现指定数目的数据分割。本发明实施例针对RDF数据有向图的本质，将AP聚类与K-means聚类相结合实现RDF数据基于图的平衡分割。本发明有效地提升网络接入服务评估准确性、动态响应性能和连接时间的预测准确度。

主权项

一种基于混合层次聚类的RDF数据平衡分割算法，包括如下步骤：步骤1：基于节点合并和移除的RDF数据预处理以RDF图节点压缩和节点移除为基础的数据预处理，节点压缩针对唯一属性值节点，节点移除针对高邻域节点，降低RDF图中参与聚类节点数目；1)节点合并给定RDF图G＝(V,E)，其中V＝V_e∪V_l表示图中节点的集合，V_e代表实体节点，V_l表示属性值节点；E＝{e(v_i,v_j)|v_i,v_j∈V}＝E_r∪E_a表示有向边的集合，其中E_r代表关系边，E_a代表属性边；在RDF有向图中，如果属性边E_a所对应的属性值节点v_j∈V_l只属于指向它的主语节点v_i∈V_e，则节点v_j在数据分割时必然要与v_i划分到同一存储节点；针对这类节点，将节点v_j与指向它的主语节点v_i合并成一个节点；2)节点移除在RDF图中，节点邻域分布并不是均匀的，有一部分节点的邻域数目非常高；节点邻域数目越高，和其关联的节点就越多，当查询时这些节点被查询的几率越高，因此产生的网络通信代价越高；为降低存储节点间通信代价，在对RDF图进行分割前，将节点度数超过一定阈值的节点从RDF图中移除，待图分割结束后加这些高度数节点分别存储到与之相关的存储节点上，用存储代价换取通信代价；步骤2：基于邻域和交互边的两种相似性度量方法：1)基于邻域相似性度量：如果一个节点的邻域节点同另一个节点相连，则认为这两个节点相似性大；同时，一个节点的邻域节点同另一个节点的远近关系也影响着相似度的大小；路径长度表示两个节点远近；设N_r(v)是节点v在半径为r的邻域集合，邻域内任意节点q与节点v的最短距离为l，节点q到节点v的权重w_qv＝1/l；节点q到v的权重和路径长度有关，路径长度越长，则权重越小，即该点与v的相似度越小；计算节点u到任意节点v的相似度如公式(1)：$similarity(u,v)=\frac{{\Sigma }_{k\in {\mathrm{inter}}_r(u,v)}{w}_{kv}}{{\Sigma }_{k\in N_r\left(u\right)}{w}_{ku}}---\left(1\right)$其中N_r(u)和N_r(v)是节点u,v的半径为r的邻域集合，inter_r(u,v)＝N_r(u)∩N_r(v)表示两个节点邻域的交集；2)基于交互边相似性度量交互边是指位于两个不同集合的节点间的连接边；RDF图分割的一个目的是使分割后的交互边最小，混合层次聚类算法中从第二层聚类开始；以交互边作为两个聚类数据块儿间的权重，衡量两个数据块儿间的相似度，如果数据块儿间交互边越多，代表两个数据块儿相似度越大，否则越小；给定两个数据块C_i和C_j，cut(C_i,C_j)表示两个数据块内节点间的交互边数目，cut_min(C_k)和cut_max(C_k)分别代表所有数据块间最小交互边和最大交互边数目，则两个数据块相似性计算如公式(2)$similarity(C_i,C_j)=\frac{cut(C_i,C_j)-{\mathrm{cut}}_{\min }\left(C_k\right)}{{\mathrm{cut}}_{\max }\left(C_k\right)-{\mathrm{cut}}_{\min }\left(C_k\right)}---\left(2\right)$步骤3：基于AP聚类算法的多层次聚类：AP聚类算法通过迭代更新吸引度矩阵R＝[r(i,k)]与归属度矩阵A＝[a(i,k)]，逐步确定高质量聚类中心，吸引度矩阵和归属度矩阵更新规则如下：用归属度矩阵与相似度矩阵S＝[s(i,k)]更新吸引度矩阵R：$r(i,k)=s(i,k)-\underset{k^{\prime }\ne k}{max}\{a(i,k^{\prime })+s(i,k^{\prime })\}---\left(4\right)$用吸引度矩阵R更新归属度矩阵A：$a(i,k)=\min \{0,r(k,k)+\underset{i^{\prime }\notin \{i,k\}}{\Sigma }max\{0,r(i^{\prime },k)\left\}\right\}$$a(k,k)=\underset{i^{\prime }\ne k}{\Sigma }max\{0,r(i^{\prime },k)\}---\left(5\right)$其中，s(i,k)为点i到点k的相似度，表明点k作为点i的聚类中心的合适程度；r(i,k)表示点k对点i的吸引度，反映点k通过与其他数据点k'竞争，作为适合数据点i的聚类中心的程度；a(i,k)表示点i对点k的归属度，反映数据点i选择数据点k作为其聚类中心的适合程度；当i＝k时，s(k,k)由输入的偏向参数p(k)设置，p(k)越大，数据点k越有可能被选为聚类中心，聚类个数越多；反之，p(k)越小，聚类个数越少；在执行过程中，吸引度矩阵和归属度矩阵需要迭代更新，每次更新的时间复杂度为O(n²)，算法迭代T次，时间复杂度为O(Tn²)；RDF图分割的目的是将紧密连接的节点分配到一个存储节点，如果两个节点间的相似性越小，则这两个节点被分配到一个存储节点的可能性就越小；在执行AP聚类前，设定相似度矩阵中小于阈值δ的节点间的相似性为‑∞，提高时间性能；AP层次聚类算法步骤：输入：RDF图G＝(V,E)，聚类数目阈值T输出：聚类数据块C＝{C₁,C₂,...,C_m}，其中m≤T步骤：1)基于邻域相似度方法构建稀疏相似度矩阵S；2)在稀疏相似度矩阵S上执行AP聚类算法，产生m个数据块；3)如果m>T，利用公式(2)计算数据块间相似度，生成新的相似度矩阵S；3)将S作为新的输入，重新执行2)，直到m≤T；步骤4、层次聚类的平衡调整将大图分割成子图分布式存储到不同存储节点时，子图的大小规模均衡性影响查询效率，如果子图大小规模不均性，并行计算和查询效率会降低；为了确保分割均衡性，在AP聚类的每一层引入平衡调整算法；给定一个图G＝(V,E)，将图分割成k个划分P＝{P₁,P₂,…,P_k}，k个分割平衡性应满足1‑e₁≤PB_i≤1+e₂，其中PB_i＝|V_i|/m并且m＝|V|/k；分割平行性越好，e₁，e₂值越小；平衡调整算法步骤：输入：聚类后的分割P＝{P₁,P₂,…,P_k}，e₁，e₂输出：平衡后分割P'＝{P₁',P′₂,…,P_t'}步骤：1)分别计算聚类后k个分割的平行性PB＝{PB₁,PB₂,...,PB_k}2)For p＝1to kif PB_i<1‑e₁merge(P_i,P_j)，其中Cut(P_i,P_j)最大，且PB_j<1+e₂else if PB_i>1+e₂利用KL算法分割P_i直到1‑e₁≤P_i'≤1+e₂；步骤5：基于K‑means的图分割算法利用AP聚类逐层缩小图的规模，当得到一定规模数据块后，采用K‑means聚类实现最终数目的聚类分割；K‑means算法步骤：输入：数据块交互边矩阵S，最终分割数目k输出：分割集合C＝{C₁,C₂,...,C_k}步骤：1)随机选择k个初始聚类中心C＝{c₁,c₂,...,c_k}2)将其它数据块分配到和其相似度最小的聚类中心3)更新聚类中心①计算聚类C_i的平均向量$S\left(\overline{v_i}\right)=\frac{1}{\left|C_i\right|}\underset{v_k\in C_i}{\Sigma }S(v_k,v_j),\forall v_j\in V$②计算新的聚类中心c_i'$c_i^{\prime }={\mathrm{argmin}}_{v_k\in C_i}||s\left(v_k\right)-s\left(\overline{v_i}\right)||$③重复步骤2)和3)，直到目标函数E收敛$E=\underset{i=1}{\overset{k}{\Sigma }}\underset{v_k\in C_i}{\Sigma }{||s\left(v_k\right)-s\left(\overline{v_i}\right)||}^2.$