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

丁世飞 等:基于不相似性度量优化的密度峰值聚类算法 3325

m(x,y|D,F)=E H (D) [R F (R(x,y|H,D))] (7)
其中,R F (⋅)是关于 F 的概率,期望需要取 H (D)中的所有模型.而在实际中,基于块的不相似性是从有限的模型 H i ∈
H (D),i=1,…,t 中估计得到的.

( , | ) =
(( , | y H D
m x y D 1 t PR x ; )), () = ∑ PR 1 ∑ ( I z ∈ D ) (8)
e i | D | zD
∈
i t = 1
注意,R(x,y|H;D)是覆盖 x 和 y 的最小区域,类似于 x 和 y 几何模型中最短的距离.
基于块的不相似性度量共定义两个参数 t 和ψ,t 表示 iTrees 的数目,ψ表示每棵 iTree 的大小,每棵树的高度
最高为 h=⎡log 2 ψ⎤.例如,存在一个大小为 8 的数据集 X={x 1 ,x 2 ,x 3 ,…,x 8 }.
• 第 1 步,构建一个由 t 个 iTrees 组成的 iForest 作为分区结构 R.
每个 iTree 都使用子集 D⊂D 独立构建,其中,|D|=ψ.假设定义 t=100 和ψ=256,即设置 iTrees 的数目为 100,
每棵 iTree 的大小为 256,但是由于 256 大于样本总数目 8,所以随机采样样本数为|D|=8 代替|D|=256.然后,在每
棵 iTree 的每个内部节点处采用轴平行分割算法将节点处的样本集分为两个非空子集,直到每个点被隔离或达
到最大树高度 h.轴平行分割 iTree 构建过程如算法 1 所示.
算法 1. 轴平行分割算法.
输入:数据集 X,最高限制 h.
输出:一棵 iTree.
步骤:
Step 1. 随机选择一个属性 q.
Step 2. 随机选择一个分裂的点 p,此点的属性 q 需要在属性 q 最小和最大值之间.
Step 3. 将在属性 q 取值小于 p 点的点归为一类,将在属性 q 取值大于等于 p 点的点归为一类.
Step 4. 如果树的高度大于最高限制 h,或者点都成了独立的节点,则停止,否则返回 Step1.
Step 5. 返回 iTree 树结构.
假设通过算法 1 分割第 1 棵 iTree,得到如图 3 所示的树结构.依次分割 100 棵 iTree 得到类似 100 个图 3
的树构成 iForest.X 中的所有实例遍历每棵树,并记录每个节点的块.
{ 1 ,, ,, , , ,x xx xx x x x 8 }
7
2
6
4
3
5
,
,
x , x } x ,, ,xx x x x }
{ 4 6 { 1 2 3 5 7 8
{ } { } { 3 ,, ,xx x 8 } { 1 , x x 2 }
x
x
x
4
6
5
7
x ,,xx } { } { } { }
1 x
7 x
2 x
{ 3 5 8
8 x
x , x } { }
{ 3 5
{ } { }
3 x
5 x
Fig.3 Structure of one iTree
图 3 iTree 的树结构
• 第 2 步,进行块的评估.
通过每个 iTree 解析测试点 x 和 y,计算包含 x 和 y 两者的最低节点的块总和,即 ∑ |( , |R xy H ) | .
i i
• 最后,m e (x,y)是这些块的均值.
(, )y = ∑
mx 1 t | ( , |Rx y H i ) | (9)
e | D |
i t = 1
假设求解点 x 3 和 x 7 的不相似性.在图 3 的 iTree 中,x 3 和 x 7 的块值为包含两者的最小的区域|{x 3 ,x 5 ,x 7 ,x 8 }|=4.