Post-Pruning in Decision Tree Induction ◾ 315
Also, let w
ACC
, w
STAB
, w
DSCPWR
, w
Leaf
, and w
Rule
be the specied nonnegative weights
associated with the accuracy, stability, discriminatory power, leaf simplicity, and
rule simplicity measures, where w
ACC
+w
STAB
+w
DSCPWR
+w
Leaf
+w
Rule
=1.
Our multiobjective, MIP formulation of the DT post-pruning problem with
multiple performance measures can be expressed as follows:
P
SubTree
: Max w
ACC
ACC + w
STAB
STAB
A
+ w
DSCPWR
DSCPWR + w
Leaf
SIMP
Leaf
+
w
Rule
SIMP
Rule
subject to
1: ∑
i∈It
x
i
= 1 ∀t ∈ I
Leaves
2a: ∑
i∈I
x
i
− ∑
ℓ ∈ [1,LLast]
λ
ℓ
a
ℓ
= 0
2b: ∑
ℓ ∈ [1, LLast]
λ
ℓ
= 1
2c: λ
1
≤ y
1
2d: λ
ℓ
≤ y
ℓ–1
+ y
ℓ
∀ ℓ = 2,. . ., (LLast – 1)
2e: λ
Last
≤ y
(LLast –1)
2f: ∑
ℓ ∈ [1,(LLast –1)]
y
ℓ
= 1
2g: y
ℓ
∈ {0,1}