Page 110 - 《软件学报》2021年第9期

2734 Journal of Software 软件学报 Vol.32, No.9, September 2021

该算法在搜索过程中通过一个栈结构来生成从根节点到叶子节点的路径(第 1 行),若栈顶节点没有后继节
点,则倒排栈元素构成一条事务(第 2 行、第 3 行);若有后继节点,则递归处理(第 4 行~第 6 行).当前节点处理完
后弹栈(第 9 行).
2.1.2 频繁模式挖掘
频繁模式挖掘算法的类型多种多样,例如基于候选集拼接的算法、基于树的算法和基于递归后缀的算法,
分别适用于不同的挖掘场景 [26] ,应用时可能需要根据实际情况进行调整和重构.对于微服务系统的频繁调用路
径挖掘场景,挖掘算法需要考虑以下两个特点.
(1) 从数据集来看,每个服务在调用路径上的位置不能交换,即项集是有序的,属于序列模式挖掘 [26] .同时,
由于调用路径上的相邻服务之间必须存在调用关系,则一个调用路径的子路径必须是连通的,例如
“a→b→c”的子路径可以是“a→b”或者“b→c”,但不能是“a→c”.可以计算出,长度为 n 的调用路径存在
n(n+1)/2 个子路径;
(2) 从挖掘目标来看,最终输出的频繁路径应当包含尽可能多的服务.例如,“a→b”和“a→b→c”如果都是
频繁的,那么只需要输出“a→b→c”作为频繁路径.即:对于输出的频繁路径,不存在任何一条包含它路
径也是频繁的,属于最大频繁模式挖掘 [24] .
基于上述特点,提出如下定义:S={S 1 ,S 2 ,S 3 ,…,S m }为服务集合,序列 T i =〈S 1 ,S 2 ,S 3 ,…,S k 〉(0<k≤m)为一条服务调
用路径,k 为调用路径的长度,D={T 1 ,T 2 ,T 3 ,…,T n }为待挖掘服务调用路径集合,T 为所有 T i 的子路径组成的集合,
对于 t∈T,c(t)表示 t 在 D 中的出现频次,即 t 的支持度,m 为频繁阈值(最小支持度),则:
定义 1. 频繁路径集 F={t|c(t)>m,t∈D},F k 是长度为 k 频繁路径构成的集合,即 F k ={t|len(t)=k,t∈F}.
推论 1. 如果一条路径 t 不是频繁的,则包含 t 的路径也不是频繁的.
定义 2. 最大频繁路径集 P={p|Œq∈P∧q⊃p,p∈F}.
推论 2. 如果一条路径 t 是最大频繁路径,则 t 的所有子路径都不是最大频繁路径.
本文所描述的频繁路径挖掘算法是从 D 挖掘最大频繁路径集 P 的算法,参照 Apriori 算法 [26] 框架设计,伪代
码见表 3.
Table 3 Frequent calling paths mining algorithm
表 3 频繁路径挖掘算法
算法. mineFrequentPaths(D,m,P).
参数:D,事务集(输入);m,最小支持度(输入);P,最大频繁路径集(输出).
1 F←new Frequent(m)
2 F 1←F.construct_one_frequents(D)
3 k←1
4 while F k≠∅ do
5 F k+1←F.construct_candidate_frequents(D,F k,F 1)
6 for each p∈F k+1 do
7 c←D.count(p)
8 if c<m then
9 F k+1.remove(p)
10 end if
11 end for
12 k++
13 end while
14 k−−
15 while k>0 do
16 for each p∈F k do
17 if not P.subpath(p) then
18 P.add(p)
19 end if
20 end for
21 k−−
22 end while
首先,可以根据定义 1 直接计算 F 1 (第 2 行);其次,在推理 1 的基础上,通过得到 F k 和 F 1 的笛卡尔积,生成长