Page 231 - 《软件学报》2020年第11期

3546 Journal of Software 软件学报 Vol.31, No.11, November 2020

2.3 分 析
(1) 有效性
给定高维空间 A,将对象数据收集过程中目标信息的增长曲线与坐标轴所构成区域的“面积”,即收集过程
中目标信息的积分,作为算法 1 的有效性,用 S A 描述.
A ∑∑
S = ||A 1 i j= 1 D (Ψ j c ) (6)
i=
c
其中,|A|是 A 中的对象总数,Ψ 表示第 j 个收集到的对象数据.越重要的对象越早被收集,S A 越大.
j
(2) 复杂度
算法 1 的时间复杂度取决于 K 叉树的高度⎣log K |O|⎦和采样比 R samp .K 叉树中,下一层采样是对当前这一层
子空间分割并评估的过程,每生成一层,都会对|O|个对象按照 R samp 重新采样,并评估子空间的目标信息密度.因
此,算法 1 的时间复杂度可表示为 O(|O|⋅R samp ⋅⎣log K |O|⎦)=O(|O|⋅log|O|).
(3) 标准误差
标准误差是对子空间目标信息密度的估计误差.算法１的标准误差在不同采样点 n 下不同.
σ 1 n ⎛ 1 n ⎞ 2
标准误差的估计为 | A s | n ,其中,σ n ∑ 1⎜ D ( Ψ = ) − ∑ D ( Ψ i o ⎟ ) .
n n − 1 i= ⎝ i o n i= 1 ⎠
σ
算法 1 的 | A s | n 随着采样点数的上升以非线性趋势下降.
n
(4) 迭代次数
迭代次数是算法执行过程中对子空间分割并评估其重要性的次数,记为 N iter .算法 1 的迭代次数取决于子
空间的分割数 K 和对象总数|O|,迭代次数由定理 1 给出.
定理 1. 给定一个有|O|个对象和 K 个子空间的 OBG(|O|>0,K>1),可以得到 N iter 为
⎧ 1, 0 | O <
<
⎪ | K
⎪ | O − ⎨ | K m− 1 + ∑ m− 0 1 K j , K ≤ m | O |≤ 2K m (7)
j=
⎪
⎪ ∑ m K j , 2K < m | O < | K m+ 1
⎩ j= 0
+
其中,m=⎣log K |O|⎦,m∈Z .
证明:根据对象数的不同可分为 3 种情形,下面依次进行说明.
情形 1:对象数在 0 到 K 之间,即 0<|O|<K.由于每个子空间至少会有一个对象被收集,所以这种情况下所有
的对象将在一次迭代内收集完成,因此 N iter =1.
m
m
m
m
情形 2:对象数在 K 到 2K 之间,即 K ≤|O|≤2K .首先用叶子节点代表对象,所有非叶子节点代表一次迭
代,称为迭代节点.若 K =|O|,则为一棵完全 K 叉树有 ∑ m− 1 K 个叶子节点.当一个对象被加入时,就会有新的迭
m
j
j= 0
代节点形成,该位置上原来的叶子节点和新加入的叶子节点将作为该迭代节点的孩子节点.因此,一共有
|O|−K m−1 个新加入的节点,叶子节点按照同样的方法加入到这个 K 叉树中,如图 4(a)所示.最终, N iter = | O − |
K m− 1 + ∑ m− 1 K j .
j= 0
m
m
情形 3:对象数在 2K 到 K m+1 之间,即 2K <|O|<K m+1 .当先前的叶子节点都变成迭代节点时,新加入的节点将
不再产生新的迭代节点,直接加入现有的迭代节点中,直到形成完全 K 叉树.这种情况下,迭代次数将一直保持为
=
j
N iter ∑ m j= 0 K ,且所有的叶节点都在 K 叉树的同一层,如图 4(b)所示.
证毕. □