Page 162 - 《软件学报》2024年第4期

1740 软件学报 2024 年第 35 卷第 4 期

8: 更新距离邻接矩阵 D;
9: end while
输出: 批量的二叉树结构.
图 5 展示了使用 l 1 范数度量距离在 T=2 时使用示例数据构建批量相似二叉树的过程. 算法首先从记录动
态评估表 R 中提取最近的若干次评估结果, 以供后续计算距离使用(步骤 1); 然后, 使用 l 1 范数计算批量之间
的相似度, 并将结果记录在距离邻接矩阵中(步骤 2); 通过不断合并最近的节点并根据距离矩阵生成新节点,
直到距离邻接矩阵中只包括一个根节点时, 便完成了批量相似二叉树的初步构建(步骤 3); 最后, 算法返回批
量相似树的数据结构, 树的每个叶节点对应一个批量, 非叶节点存储其子节点之间的距离(步骤 4).

图 5 构建批量相似树的一个例子
一个值得注意的问题是: 在新节点添加到邻接矩阵时, 如何计算新节点与其他节点之间的距离. 在树的
构建过程中, 当两个节点合并形成一个新节点时, 邻接矩阵会删除这两个节点并添加合并后的新节点与其他
节点之间的距离信息, 此时, 通常可以使用合并前的节点的距离信息来评估新节点的距离信息, 比如取合并
前两节点中较大的值、较小的值或均值作为新的距离信息等. 例如: 如果节点 A 和 B 合并形成节点 X, 并且需
要计算 X 与节点 C 之间的距离, 则可以使用现有的 A, B 和 C 之间的距离信息 d(A,C)和 d(B,C)来计算 X 和 C
的距离 d(X,C). 在图 6 及本文的实验部分中, 假设新节点继承合并前节点的最小距离, 即:
d(X,C)=min{d(A,C),d(B,C)}.

图 6 批量索引选择策略的一个例子