Data set operations to hide decision tree rules
Dimitris Kalles1 and Vassilios S. Verykios1 and Georgios Feretzakis1 and Athanasios Papagelis2
Abstract.1This paper focuses on preserving the privacy of sensitive
patterns when inducing decision trees. We adopt a record
augmentation approach for hiding sensitive classification rules in
binary datasets. Such a hiding methodology is preferred over other
heuristic solutions like output perturbation or cryptographic
techniques - which restrict the usability of the data - since the raw
data itself is readily available for public use. We show some key
lemmas which are related to the hiding process and we also
demonstrate the methodology with an example and an indicative
experiment using a prototype hiding tool.

1

INTRODUCTION

Privacy preserving data mining [1] is a quite recent research area
trying to alleviate the problems stemming from the use of data
mining algorithms to the privacy of the data subjects recorded in the
data and the information or knowledge hidden in these piles of data.
Agrawal and Srinkant [2] were the first to consider the induction of
decision trees from anonymized data, which had been adequately
corrupted with noise to survive from privacy attacks. The generic
strand of knowledge hiding research [3] has led to specific
algorithms for hiding classification rules, like, for example, noise
addition by a data swapping process [4].
A key target area concerns individual data privacy and aims to
protect the individual integrity of database records to prevent the reidentification of individuals or characteristic groups of people from
data inference attacks. Another key area is sensitive rule hiding, the
subject of this paper, which deals with the protection of sensitive
patterns that arise from the application of data mining techniques.
Of course, all privacy preservation techniques strive to maintain data
information quality.
The main representative of statistical approaches [5] adopts a
parsimonious downgrading technique to determine whether the loss
of functionality associated with not downgrading the data, is worth
the extra confidentiality. Reconstruction techniques involve the
redesign of the public dataset [6][7] from the non-sensitive rules
produced by algorithms like C4.5 [8] and RIPPER [9]. Perturbation
based techniques involve the modification of transactions to support
only non-sensitive rules [10], the removal of tuples associated with
sensitive rules [11], the suppression of certain attribute values [12]
and the redistribution of tuples supporting sensitive patterns so as to
maintain the ordering of the rules [13].
In this paper, we propose a series of techniques to efficiently
protect the disclosure of sensitive knowledge patterns in
classification rule mining. We aim to hide sensitive rules without

1

School of Science and Technology, Hellenic Open University, Patras,
Greece,
email: kalles@eap.gr, verykios@eap.gr, georgios.feretzakis@ac.eap.gr
2Epignosis Ltd, Athens, Greece, email: papagel@efrontlearning.net

compromising the information value of the entire dataset. After an
expert selects the sensitive rules, we modify class labels at the tree
node corresponding to the tail of the sensitive pattern, to eliminate
the gain attained by the information metric that caused the splitting.
Then, we appropriately set the values of non-class attributes, adding
new instances along the path to the root where required, to allow
non-sensitive patterns to remain as unaffected as possible. This
approach is of great importance as the sanitized data set can be
subsequently published and, even, shared with competitors of the
data set owner, as can be the case with retail banking [14].
The rest of this paper is structured in 3 sections. Section 2
describes the dataset operations we employ to hide a rule while
attempting to minimally affect the decision tree that would have
been produced using the modified dataset. Section 3 contains a
detailed pseudo-code specification, and early implementation and
experimentation details. Section 4 discusses further research issues
and concludes the paper.

2

THE BASELINE PROBLEM AND A
HEURISTIC SOLUTION

Figure 1 shows a baseline problem, which assumes a binary decision
tree representation, with binary-valued, symbolic attributes (X, Y and
Z) and binary classes (C1 and C2).

X
Y

X
f

t

f

t

Z
Y

f

t
t

C1
C2

Z

t

f

C1

f

Z

t
f

C2

C1

Z
C2

t
C1

f
C2

C1

R1: 𝑋=𝑡⋀𝑌=𝑡⇒𝐶1
R2: 𝑋=𝑡⋀𝑌=𝑓⋀𝑍=𝑡⇒𝐶2
R3: 𝑋=𝑡⋀𝑌=𝑓⋀𝑍=𝑓⇒𝐶1
R4: 𝑋=𝑓⋀𝑍=𝑡⇒𝐶1
R5: 𝑋=𝑓⋀𝑍=𝑓⇒𝐶2

R1: 𝑋=𝑡⋀𝑌=𝑡⇒𝐶1
R23: 𝑿=𝒕⋀𝒀=𝒇⇒𝑪2
R4: 𝑋=𝑓⋀𝑍=𝑡⇒𝐶1
R5: 𝑋=𝑓⋀𝑍=𝑓⇒𝐶2

Figure 1. A binary decision tree before (left) and after (right) hiding and
the associated rule sets.

Hiding R3 implies that the splitting in node Z should be suppressed,
hiding R2 as well.
A first idea to hide R3 would be to remove from the training data
all the instances of the leaf corresponding to R3 and to retrain the tree
from the resulting (reduced) dataset. However this action may incur
a substantial tree restructuring, affecting other parts of the tree too.
Another approach would be to turn into a new leaf the direct
parent of the R3 leaf. However, this would not modify the actual
dataset, thus an adversary could recover the original tree.
To achieve hiding by modifying the original data set in a minimal
way, we may interpret “minimal” in terms of changes in the data set
or in terms of whether the sanitized decision tree produced via hiding
is syntactically close to the original one. Measuring minimality in
how one modifies decision trees has been studied in terms of
heuristics that guarantee or approximate the impact of changes
[[15]][[16]][[17]].
However, hiding at Z modifies the statistics along the path from
Z to the root. Since splitting along this path depends on these
statistics, the relative ranking of the attributes may change, if we run
the same induction algorithm on the modified data set. To avoid
ending up with a completely different tree, we first employ a bottomup pass (Swap-and-Add) to change the class label of instances at the
leaves and then to add some new instances on the path to the root, to
preserve the key statistics at the intermediate nodes. Then, we
employ a top-down pass (Allocate-and-Set) to complete the
specification of the newly added instances. These two passes help us
hide all sensitive rules and keep the sanitized tree close to the form
of the original decision tree.

2.1

Figure 2a.Original tree

Adding instances to preserve the class
balance

The Swap-and-Add pass aims to ensure that node statistics change
without threatening the rest of the tree. Using Figure 2a as an
example, we show the original tree with class distributions of
instances across edges (the original tree does not make use of the
parentheses’ notation).We use the information gain as the splitting
heuristic. To hide the leaf WR we change the five positive instances
to negative ones and denote this operation by (+5n,-5p). As a result
the parent node, W, becomes a one-class node with minimum (zero)
entropy. All nodes located upwards to node W until the root Z also
absorb the (+5n,-5p) operation (Figure 2b). At the resulting tree,
these primitive initial operations are shown inside parentheses and
their results are shown in bold font.
This conversion would leave X with 13n+11p instances. But, as
its initial 8n+16p distribution contributed to Y’s splitting attribute,
AY, which in turn created X (and then W), we should preserve the
information gain of AY, since the entropy of a node only depends on
the ratio p:n of its instance classes (Lemma 1).
Lemma 1 The entropy of a node only depends on the ratio of its
instance classes.

Figure 2b. Bottom-up propagation of instances (+5n,-5p)

Proof of lemma 1
Let E be the entropy of a node with p positive and n negative
instances, with p: n = a. We assume that a ≥ 1.
pi : The probability of the class i
E = − ∑ pi log 2 pi = −

n
n
p
p
log
−
log
=
p+n 2p+n p+n 2p+n

p=an

n
n
an
an
log
−
log
=
an + n 2 an + n an + n 2 an + n
1
1
a
a
=−
log 2
−
log 2
=
a+1
a+1 a+1
a+1
1
a
=
log (a + 1) −
(log 2 a − log 2 (a + 1)) =
a+1 2
a+1
a
= log 2 (a + 1) −
log a
a+1 2
=
⏞ −

Now, in the branch YX we have already added some negative
instances, while we have also eliminated some positive ones.
Ensuring that X’s entropy will not increase can be guaranteed by not
falling below the 2:1 ratio of one (any) class over the other. A greedy
option is to add 9n instances, to bring the 13:11 ratio to 22:11 (now,
22n+11p instances arrive at X). These 9n instances propagate
upwards. To preserve the 3:1 ratio of Y, we must add 47p instances
(as shown in Figure 3).

set those instance values for any other attribute other than the ones
present in the path from the root to the node where the instance
addition took place. Unspecified values must be so set to ensure that
currently selected attributes at all nodes do not get displaced by
competing attributes. This is what the Allocate-and-Set pass does.
With reference to Figure 3 and the 9n instances added due to X
via the YX branch, these instances have not had their values set for
AX and AW. Moreover, these must be so set to minimize the
possibility that AY is displaced from Y, since (at Y) any of attributes
AW, AX or AY (or any other) can be selected. Those 9n instances were
added to help guarantee the existence of X. To simplify things,
assume that Y’s parent is the root, Z. We will first show how to tackle
the top 47p instances added and, then, we will build a generic
solution.
Since AZ has been already set for these 47p instances, we examine
whether these instances will be directed to the YX branch or to the
other one (assume that an attribute value of true directs an instance
to the left branch). As it happened in the bottom-up pass, we need
the information gain of AY to be large enough to fend off competition
from AW or AX at node Y, but not too large to threaten AZ. We start
with the best possible allocation of values to attribute AY, directing
all 47p instances to false (toward the 8n+32p branch), and
progressively explore directing some of these along the YX branch,
and stop when the information gain for AY becomes lower than the
information gain for AZ. We use the term two-level hold-back to refer
to this technique, as it spans two tree levels. This approach exploits
the convexity property of the information gain difference function
(Lemma 2).
The Allocate-and-Set pass examines all four combinations of
distributing all positive and all negative instances to one branch,
select the one that maximizes the information gain difference and
then move along the slope that decreases the information gain, until
we do not exceed the information gain of the parent; then perform
the recursive specification all the way to the tree fringe.
Lemma 2 Distributing new class instances along only one branch
maximizes information gain.
Proof of lemma 2
Let 𝐺(𝑖) be the function that represents the information gain after
the addition of k new positive instances at a node and the
distribution of 𝑖 of these nodes to the left child and of 𝑘 − 𝑖 to the
right child.
𝐺(𝑖) = 𝐺(𝑝 + 𝑘, 𝑛, 𝑝1 + 𝑖, 𝑛1 , 𝑝2 + (𝑘 − 𝑖), 𝑛2 ), 𝑓𝑜𝑟 0 ≤ 𝑖 ≤ 𝑘

Figure 3. A decision tree to demonstrate hiding via instance addition in
order to maintain the node statistics, propagating these changes to the tree
root.

𝐺(𝑖) = 𝐸(𝑝 + 𝑘, 𝑛) − [𝐸(𝑝1 + 𝑖, 𝑛1 ) ∙
𝐸(𝑝2 + (𝑘 − 𝑖), 𝑛2) ∙
𝐶−𝐶𝑜𝑛𝑠𝑡𝑎𝑛𝑡

We extend this technique up until the tree root, by accumulating
at each node all instance requests from below and by adding
instances locally to maintain the node statistics, propagating these
changes to the tree root.

2.2

Fully specifying instances

Having set the values of some attributes for the newly added
instances is only a partial instance specification, since we have not

𝑝2 +𝑘−𝑖+𝑛2
𝑝+𝑘+𝑛

𝑝1 +𝑖+𝑛1
𝑝+𝑘+𝑛

+

]=

𝑝1 + 𝑖 + 𝑛1
𝑝1 + 𝑖
𝑝1 + 𝑖 𝑝1 + 𝑖 + 𝑛1
−
∙ log
)∙
𝑛1
𝑝1 + 𝑖 + 𝑛1
𝑛1
𝑝+𝑘+𝑛
𝑝2 + 𝑘 − 𝑖 + 𝑛2
𝑝2 + 𝑘 − 𝑖
+ (log
−
𝑛2
𝑝2 + 𝑘 − 𝑖 + 𝑛2
𝑝2 + 𝑘 − 𝑖 𝑝2 + 𝑘 − 𝑖 + 𝑛2
∙ log
)∙
]=
𝑛2
𝑝+𝑘+𝑛

=⏞
𝐸(𝑝 + 𝑘, 𝑛) − [(log

=𝐶−

1
𝑝1 + 𝑖 + 𝑛1
𝑝1 + 𝑖
[(𝑝 + 𝑖 + 𝑛1 ) ∙ log
− (𝑝1 + 𝑖) ∙ log
𝑝+𝑘+𝑛 1
𝑛1
𝑛1
𝑝2 + 𝑘 − 𝑖 + 𝑛2
+ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 ) ∙ log
𝑛2
𝑝2 + 𝑘 − 𝑖
− (𝑝2 + 𝑘 − 𝑖) ∙ log
]
𝑛2

′

= 𝐴(𝑖) ∙

((𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖)) ∙ ((𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 ))
((𝑝
⏟ 1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2))

2

𝐵(𝑖)>0

−

((𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖)) ∙ ((𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 ))
((𝑝
⏟ 1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 ))

2

′

=

𝐵(𝑖)>0
𝑐ℎ𝑎𝑛𝑔𝑒 𝑜𝑓 𝑏𝑎𝑠𝑒

=
⏞

1
𝐶−
𝑝+𝑘+𝑛
1
𝑝1 + 𝑖 + 𝑛1
∙
[(𝑝1 + 𝑖 + 𝑛1 ) ∙ ln
− (𝑝1 + 𝑖)
𝑙𝑛2
𝑛1
𝑝1 + 𝑖
𝑝2 + 𝑘 − 𝑖 + 𝑛2
∙ ln
+ (𝑝2 + 𝑘 − 𝑖 + 𝑛2) ∙ ln
𝑛1
𝑛2
𝑝2 + 𝑘 − 𝑖
− (𝑝2 + 𝑘 − 𝑖) ∙ ln
]
𝑛2

Taking the first derivative of 𝐺(𝑖) we have:
𝐺 ′(𝑖) = 0 −

1
𝑝+𝑘+𝑛
1
𝑝1 + 𝑖 + 𝑛1
𝑛1
[ln
+ (𝑝1 + 𝑖 + 𝑛1 ) ∙
𝑙𝑛2
𝑛1
𝑝1 + 𝑖 + 𝑛1
1
𝑝1 + 𝑖
𝑛1
1
∙ − ln
− (𝑝1 + 𝑖) ∙
∙
𝑛1
𝑛1
𝑝1 + 𝑖 𝑛1
𝑝2 + 𝑘 − 𝑖 + 𝑛2
+ (−1) ∙ ln
− (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )
𝑛2
𝑛2
1
𝑝2 + 𝑘 − 𝑖
∙
∙ − (−1) ∙ ln
𝑝2 + 𝑘 − 𝑖 + 𝑛2 𝑛2
𝑛2
𝑛2
1
− (𝑝2 + 𝑘 − 𝑖) ∙
∙ (− )] =
𝑝2 + 𝑘 − 𝑖
𝑛2
∙

𝐶(𝑖)<0

⏞𝐴(𝑖)
=(
) ∙ [(𝑝2 + 𝑘 − 𝑖 − 𝑝1 − 𝑖 − 𝑛1 ) ∙ (𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )
𝐵(𝑖)
− (𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖)
∙ (𝑝2 + 𝑘 − 𝑖 − 𝑝1 − 𝑖 + 𝑛2)] =
= 𝐶(𝑖) ∙ [((𝑝2 + 𝑘 − 𝑖) − (𝑝1 + 𝑖 + 𝑛1 )) ∙ (𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )
− (𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖)
∙ ((𝑝2 + 𝑘 − 𝑖 + 𝑛2 ) − (𝑝1 + 𝑖))] =
= 𝐶(𝑖) ∙ [(𝑝2 + 𝑘 − 𝑖) ∙ (𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 ) − (𝑝1 + 𝑖 + 𝑛1 )
∙ (𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 ) − (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )
∙ (𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖) + (𝑝1 + 𝑖)
∙ (𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖)] =
= 𝐶(𝑖) ∙ [(𝑝2 + 𝑘 − 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )(𝑝1 + 𝑖 − 𝑝1 − 𝑖 − 𝑛1 )
+ (𝑝1 + 𝑖) ∙ (𝑝1 + 𝑖 + 𝑛1 )
∙ (𝑝2 + 𝑘 − 𝑖 − 𝑝2 − 𝑘 + 𝑖 − 𝑛2 )] =
= 𝐶(𝑖) ∙ [(𝑝2 + 𝑘 − 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 ) ∙ (−𝑛1 ) + (𝑝1 + 𝑖)
∙ (𝑝1 + 𝑖 + 𝑛1 ) ∙ (−𝑛2 )] =
=−𝐶(𝑖) ∙

1
𝑝1 + 𝑖 + 𝑛1
𝑝1 + 𝑖
=−
[ln
+ 1 − ln
−1
𝑝+𝑘+𝑛
𝑛1
𝑛1
𝑝2 + 𝑘 − 𝑖 + 𝑛2
𝑝2 + 𝑘 − 𝑖
− ln
− 1 + ln
+ 1] =
𝑛2
𝑛2
=−

1
𝑝1 + 𝑖 + 𝑛1
𝑝2 + 𝑘 − 𝑖
[ln
+ ln
]=
𝑝+𝑘+𝑛
𝑝1 + 𝑖
𝑝2 + 𝑘 − 𝑖 + 𝑛2

(𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖)
1
=−
[ln
]
(𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )
𝑝+𝑘+𝑛

(𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖)
1
[ln
] =
(𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )
𝑝+𝑘+𝑛
𝐴(𝑖)<0 𝑓𝑜𝑟 𝑒𝑣𝑒𝑟𝑦 𝑖∈[0,𝑘]

=−

≥0

1
∙
𝑝+𝑘+𝑛

(𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘⏞
− 𝑖 + 𝑛2 )
≥0

(𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘⏞
− 𝑖)
∙(

=−𝐶(𝑖) ∙ 𝐷(𝑖) > 0, 𝑓𝑜𝑟 𝑒𝑣𝑒𝑟𝑦 𝑖 ∈ [0, 𝑘]

So, the function 𝐺(𝑖) is convex in the interval [0, 𝑘].

2.3
′

⏞

≥0

The proof of the Lemma 3 is completed due to a theorem that states
“A convex function on a closed bounded interval attains its
maximum at one of its endpoints”.

Next we find the second derivative function of 𝐺(𝑖)
𝐺 ′′(𝑖) = −

≥0

𝑛1 ∙ (𝑝2 + 𝑘⏞
− 𝑖) ∙ (𝑝2 + 𝑘⏞
− 𝑖 + 𝑛2 ) + 𝑛2 ∙ (𝑝1 + 𝑖) ∙ (𝑝1 + 𝑖 + 𝑛1 ) =
⏟
[
]
𝐷(𝑖)>0

(𝑝1 + 𝑖 + 𝑛1 ) ∙ (𝑝2 + 𝑘 − 𝑖) ′
) =
(𝑝1 + 𝑖) ∙ (𝑝2 + 𝑘 − 𝑖 + 𝑛2 )

Grouping of hiding requests

By serially processing hiding requests, each one incurs the full cost
of updating the instance population. By knowing all of them in
advance, we only consider once each node in the bottom-up pass and
once in the top-down pass. We express that dealing with all hiding
requests in parallel leads to the minimum number of new instances
by:
𝑆
|𝑇𝑅𝑃 | = 𝑚𝑖𝑛 |(𝑇{𝑖}
)
𝑖

𝑆

𝑅−{𝑖}

|

The formula states that for a tree T, the number of instances (|T|),
after a parallel (Tp) hiding process of all rules (leaves) in R, is the
optimal along all possible orderings of all serial (Ts) hiding requests
drawn from R. A serial hiding request is implemented by selecting a
leaf to be hidden and then, recursively, dealing with the remaining
leaves (Lemma 3). As an exception, the max:min ratio is not affected
by simultaneously requesting to hide two sibling pure-class leaves.

Lemma 3 When serially hiding two non-sibling leaves, the number
of new instances to be added to maintain the max: min ratios is
larger or equal to the number of instances that would have been
added if the hiding requests were handled in parallel.

ratio in the parent node. Therefore, 𝑝𝑋𝐼 = 𝑚𝑖𝑛{𝑝𝑋𝐼 , 𝑝𝑋𝐼𝐼 , 𝑛𝑋𝐼𝐼𝐼 , 𝑛𝑋𝐼𝑉 }
which means that 𝑝𝑋𝐼𝐼 ≥ 𝑝𝑋𝐼 (∗) . If we had selected the option
(𝐼𝐼), 𝑖. 𝑒.

𝑏

𝑎+𝑝𝑋𝐼𝐼

we would have the case (II-4) and for that it had been

proved that
𝑝1 + 𝑛2 > 𝑝𝑋𝐼𝐼 (∗∗)

Proof sketch
Let a parent node have p positive and n negative instances, with
p: n = r ≥ 1, and let two hiding requests having propagated up to
that node, each from a different branch, demanding that pL , nL (from
the left child) and pR , nR (from the right child) instances be
respectively added. Assume now, that to maintain the 𝑝: 𝑛 ratio, we
need to add at once (parallel) pX or nX instances to parent node
instead of adding first p1 or n1 (in order to control the change due to
left child) and then adding p2 or n2 (in order to control the change
due to right child). First, we construct a table (Table 1) with all (32)
possible cases and then treat each combination as a separate case.
As example we present the following proofs of eight possible
cases:
Case (I-1):
𝑄. 𝐸. 𝐷.

Case (I-2):

𝑎+𝑝𝑋𝐼𝐼

i. e.

𝑎+𝑝𝑋𝐼
𝑏

the minimum number of instances to add in order to maintain the
ratio in the parent node. Therefore, 𝑝𝑋𝐼 = 𝑚𝑖𝑛{𝑝𝑋𝐼 , 𝑝𝑋𝐼𝐼 , 𝑛𝑋𝐼𝐼𝐼 , 𝑛𝑋𝐼𝑉 }
which means that 𝑛𝑋𝐼𝑉 ≥ 𝑝𝑋𝐼 (∗). If we had selected the option
𝑏+𝑛𝑋𝐼𝑉

From (∗) , (∗∗) we have 𝑛1 + 𝑛2 > 𝑝𝑋𝐼 Q.E.D.
Case (I-7):

𝑎 + 𝑝𝑋𝐼 𝑎 + 𝑝2
=
⇔
𝑏
𝑏 + 𝑛1
⇔ 𝑎𝑏 + 𝑎𝑛1 + 𝑏𝑝𝑋𝐼 + 𝑛1 𝑝𝑋𝐼 = 𝑎𝑏 + 𝑏𝑝2 ⇔
⇔ 𝑎𝑛1 + 𝑏(𝑝𝑋𝐼 − 𝑝2 ) + 𝑛1 𝑝𝑋𝐼 = 0

we would have the case (II-2).

𝑏
𝑏
=
⇔ 𝑝𝑋𝐼𝐼 = 𝑝1 + 𝑝2 (∗∗)
𝑎 + 𝑝𝑋𝐼𝐼 𝑎 + 𝑝1 + 𝑝2


If 𝑝𝑋𝐼 ≥ 𝑝2 then this case is impossible, since the left
hand side in the above equation is positive.
If 𝑝𝑋𝐼 < 𝑝2 then we have 𝑝2 + 𝑛1 > 𝑝𝑋𝐼 Q.E.D.



Case (I-3):

𝑎 + 𝑝𝑋𝐼 𝑎 + 𝑝1
=
⇔
𝑏
𝑏 + 𝑛2
⇔ 𝑎𝑏 + 𝑎𝑛2 + 𝑏𝑝𝑋𝐼 + 𝑛2 𝑝𝑋𝐼 = 𝑎𝑏 + 𝑏𝑝1 ⇔
⇔ 𝑎𝑛2 + 𝑏(𝑝𝑋𝐼 − 𝑝1 ) + 𝑝𝑋𝐼 𝑛2 = 0



𝑎 + 𝑝𝑋𝐼 𝑏 + 𝑛1 + 𝑛2
=
𝑏
𝑎
𝑎+𝑝𝑋𝐼
The reason that we select the option(𝐼), 𝑖. 𝑒.
, is that 𝑝𝑋𝐼 is

, is that 𝑝𝑋𝐼 is

From (∗) , (∗∗) we have 𝑝1 + 𝑝2 ≥ 𝑝𝑋𝐼 Q.E.D.



Case (I-6):

we would have the case (IV-6),
𝑎
𝑏 + 𝑛𝑋𝐼𝑉
𝑏 + 𝑛1 + 𝑛2
i. e.
=
⇔ 𝑛𝑋𝐼𝑉 = 𝑛1 + 𝑛2 (∗∗)
𝑎
𝑎

the minimum number of instances to add in order to maintain the
ratio in the parent node. Therefore, 𝑝𝑋𝐼 = 𝑚𝑖𝑛{𝑝𝑋𝐼 , 𝑝𝑋𝐼𝐼 , 𝑛𝑋𝐼𝐼𝐼 , 𝑛𝑋𝐼𝑉 }
which means that 𝑝𝑋𝐼𝐼 ≥ 𝑝𝑋𝐼 (∗) . If we had selected the option
𝑏

𝑎 + 𝑝𝑋𝐼
𝑎
=
⇔
𝑏
𝑏 + 𝑛1 + 𝑛2
⇔ 𝑎𝑏 + 𝑎(𝑛1 + 𝑛2 ) + 𝑏𝑝𝑋𝐼 + 𝑝𝑋𝐼 (𝑛1 + 𝑛2 ) = 𝑎𝑏 ⇔
⇔ 𝑎(𝑛1 + 𝑛2 ) + 𝑏𝑝𝑋𝐼 + 𝑝𝑋𝐼 (𝑛1 + 𝑛2 ) = 0
This case is impossible, since all the terms in the left
hand side in the above equation are positive.

(𝐼𝑉), 𝑖. 𝑒.

𝑎 + 𝑝𝑋𝐼
𝑏
=
𝑏
𝑎 + 𝑝1 + 𝑝2

(𝐼𝐼), 𝑖. 𝑒.

Case (I-5):

𝑏

𝑎 + 𝑝𝑋𝐼 𝑎 + 𝑝1 + 𝑝2
=
⇔ 𝑝𝑋𝐼 = 𝑝1 + 𝑝2
𝑏
𝑏

The reason that we select the option(𝐼), 𝑖. 𝑒.

From (∗) , (∗∗) we have 𝑝1 + 𝑛2 > 𝑝𝑋𝐼 Q.E.D.

If 𝑝𝑋𝐼 ≥ 𝑝1 then this case is impossible, since all the
terms in the left hand side in the above equation are
positive.
If 𝑝𝑋𝐼 < 𝑝1 then we have 𝑝1 + 𝑛2 > 𝑝𝑋𝐼 Q.E.D.

Case (I-8):
𝑎 + 𝑝𝑋𝐼 𝑏 + 𝑛1
=
𝑏
𝑎 + 𝑝2
𝑎+𝑝𝑋
The reason that we select the option(𝐼), 𝑖. 𝑒. 𝑏 𝐼 , is that 𝑝𝑋𝐼 is
the minimum number of instances to add in order to maintain the
ratio in the parent node. Therefore, 𝑝𝑋𝐼 = 𝑚𝑖𝑛{𝑝𝑋𝐼 , 𝑝𝑋𝐼𝐼 , 𝑛𝑋𝐼𝐼𝐼 , 𝑛𝑋𝐼𝑉 }
which means that 𝑝𝑋𝐼𝐼 ≥ 𝑝𝑋𝐼 (∗). If we had selected the option
(𝐼𝐼), 𝑖. 𝑒.

𝑏

𝑎+𝑝𝑋𝐼𝐼

we would have the case (II-8) and for that it had been

proved that

Case (I-4):
𝑎 + 𝑝𝑋𝐼 𝑏 + 𝑛2
=
𝑏
𝑎 + 𝑝1
𝑎+𝑝𝑋𝐼
The reason that we select the option(𝐼), 𝑖. 𝑒.
, is that 𝑝𝑋𝐼 is
𝑏

the minimum number of instances to add in order to maintain the

𝑛1 + 𝑝2 > 𝑝𝑋𝐼𝐼 (∗∗)

From (∗) , (∗∗) we have 𝑛1 + 𝑝2 > 𝑝𝑋𝐼 Q.E.D.
The proofs of all other cases are similar (omitted due to space
limitations).

Table 1: All possible cases to compare serially and parallel addition of new
instances.

Parallel

a + pXI
b

b
a + pXII

a
b + nXIII

b + nXIV
a

3

Serially

(I)

a + p1 + p2
b

(1)

b
a + p1 + p2

(2)

a + p1
b + n2

(3)

(longer rules) generating relatively light changes and shallow fringe
nodes (shorter rules) generating larger ones.
A further experiment highlighted that large increases occur when
we want to hide eminent rules. For example, when we tested our
technique with a modified version of the rule set in Table 2, one that
was produced by removing all rules of length 3 and 4, it turned out
that the average increase over all leaves was about 73%, with some
leaves accounting for a nearly 400% increase and some others for a
mere 10%. When we removed all rules of length 2 and 3, the average
increase was 80%. As short, eminent, rules involve fewer attributes,
skewing the statistics for these attributes entails a substantial dataset
modification.
Large numbers of instances to be added do not mean that the tree
structure will also change a lot; we usually succeed to keep the form
of the sanitized tree as close as possible to the original one. Still, the
growth ratio can be quite large and this motivates the grouping of
hiding requests.

(II)
b + n2
(4)
a + p1
a
b + n1 + n2

4
(5)

(III)
b + n1 + n2
a
a + p2
b + n1

(6)

(7)

(IV)
b + n1
(8)
a + p2

A PROTOTYPE IMPLEMENTATION

A prototype system allows a user to experiment with our hiding
heuristic in binary-class, binary-value data sets. For a brief
experiment we used a home-grown data generator; we generated
1,000 instances for a 5-attribute problem and distributed those
instances uniformly over 11 rules (Table 2).
Table 2. Rule notation: (t,_,_,f,_) means “if (A1 = t) & (A4 = f) then …”.
(t,t,t,t,t):p
(t,t,t,t,f):n
(t,t,t,f,t):p
(t,t,t,f,f):n

(t,t,f,t,_):p
(t,t,f,f,_):n

(t,f,t, _,_):p
(t,f,f, _,_):n
(f,f,f, _,_):n
(f,f,t,_,_):n

(t,t,_, _,_):p

For the original decision tree we then observed, for each leaf
node, the number of instances we would need to add to hide just that
node. The average increase is about 67% with deep fringe nodes

CONCLUSIONS AND DIRECTIONS FOR
FURTHER WORK

We have presented the outline of a heuristic that allows one to
specify which leaves of a decision tree should be hidden and then
proceed to judiciously add instances to the original data set so that
the next time one tries to build the tree, the to-be-hidden nodes will
have disappeared because the instances corresponding to those
nodes will have been absorbed by neighboring ones.
We have presented a fully-fledged example of the proposed
approach and, along its presentation, discussed a variety of issues
that relate to how one might minimize the amount of modifications
that are required to perform the requested hiding as well as where
some side-effects of this hiding might emerge. We have also
presented the heuristic in pseudo-code, mentioned the development
of a prototype system (open to all) and demonstrated its use in
synthetic data alongside some explanations for observed results.
Of course, several aspects of our technique can be substantially
improved.
The instance adding scheme is greedy. For a simple example,
refer to Figure 3, where we added 9n instances along the YX branch
and generated a need for 47p instances at the top. Had we added 15p
instances instead to maintain the 2:1 ratio (13n:26p), we would have
ended up in a 21:58 ratio at the upper branch, which would only
require a further 5p instances to maintain its original 3:1 ratio; we
would need 20 instances instead of 56.We are now developing a full
look-ahead technique based on linear Diophantine equations.
The max:min ratio concept can guarantee the preservation of the
information gain of a splitting attribute but it would be interesting to
see whether it can be applied to other splitting criteria too. Since this
ratio is based on frequencies, it should also work with a similar
popular metric, the Gini index [[18]]. On the other hand, it is unclear
whether it can preserve trees that have been induced using more
holistic metrics, such as the minimum description length principle
[[19]].
Extensive experimentation with several data sets would allow us
to estimate the quality of the max:min ratio heuristic and also
experiment with a revised version of the heuristic, one that strives to
keep the p:n ratio of a node itself (and not its parent), or one that
attempts to remove instances instead of swapping their class labels,

or still another that further relaxes the p:n ratio concept during the
top-down phase by distributing all unspecified instances evenly
among the left and right outgoing branch from a node and
proceeding recursively to the leaves (which is the one we actually
implemented). In general, experimenting with a variety of heuristics
to trade off ease of implementation with performance is an obvious
priority for experimental research.
On performance aspects, besides speed, one also needs to look at
the issue of judging the similarity of the original tree with the one
produced after the above procedure has been applied. One might be
interested in syntactic similarity [[20]] (comparing the data
structures –or parts thereof- themselves) or semantic similarity
(comparing against reference data sets). This is an issue of
substantial importance, which will also help settle questions of
which heuristics work better and which not.
As an extreme example of the need to experiment exhaustively
with the proposed heuristic, consider a simple implementation of the
hiding primitive introduced in Figure 2a: instead of swapping the
class label of a leaf, opt to swap the value of the test attribute at node
W; this also eliminates W’s contribution to X and renders the
existence of X questionable in a re-run of the induction algorithm.
Our heuristic aims at minimizing the impact on the original data set
but since such impact will have to be weighed against other problem
parameters, the issue is open for investigation.
It is rather obvious that the variety of answers one could explore
for each of the questions above constitutes a research agenda of both
a theoretical and an applied nature. At the same time, it is via
extending the base case, by allowing multi-valued and numeric
attributes and multi-class problems that we should address the
problem of enhancing our basic technique, alongside investigating
the robustness of our heuristic to a variety of splitting criteria and to
datasets of varying size and complexity. The longer-term goal is to
have it operate as a standard data engineering service to
accommodate hiding requests, coupled with a suitable environment
where one could specify the importance of each hiding request. The
current prototype (available at http://www.splendor.gr/trees) serves
exactly to highlight this goal.

REFERENCES
[1]

[2]
[3]

[4]

[5]

[6]

[7]

V.S. Verykios, E. Bertino, I.N. Fovino, L.P. Provenza, Y. Saygin, Y.
Theodoridis: State of the Art Privacy Preserving Data Mining.
SIGMOD Record 33(1), 50-57 (2004)
R. Agrawal, R. Srikant: Privacy-Preserving Data Mining. In ACM
SIGMOD Conference ofManagement of Data, pp. 439-450 (2000)
Gkoulalas-Divanis, A., Verykios, V.S.: Privacy Preserving Data
Mining: How far can we go? In Handbook of Research on Data Mining
in Public and Private Sectors: Organizational and Government
Applications. Eds. A. Syvajarvi and J. Stenvall. IGI Global (2009)
V. Estivill-Castro and L. Brankovic: Data swapping: Balancing
privacy against precision in mining for logic rules. In: First
International Conference on Data Warehousing and Knowledge
Discovery (1999)
LiWu Chang and Ira S. Moskowitz: Parsimonious Downgrading and
Decision Trees applied to the Inference Problem. In: New Security
Paradigms Workshop, pp. 82-89 (1998)
J. Natwichai, X. Li, M. Orlowska: Hiding Classification Rules for Data
Sharing with Privacy Preservation.In: 7th International Conference on
Data Warehousing and Knowledge Discovery, pp. 468-467 (2005)
J. Natwichai, X. Li, M. Orlowska: A Reconstruction-based Algorithm
for Classification Rules Hiding. In: 17th Australasian Database
Conference, pp. 49-58 (2006)

[8]
[9]
[10]

[11]

[12]

[13]

[14]

[15]
[16]

[17]
[18]
[19]

[20]

J.R.Quinlan: C4.5: Programs for Machine Learning. Morgan
Kaufmann (1993)
W.W. Cohen: Fast effective rule induction. In: Machine Learning: the
12th International Conference (1995)
A. Katsarou, A. Gkouvalas-Divanis, V. S. Verykios: Reconstructionbased Classification Rule Hiding through Controlled Data
Modification. In: IFIP International Federation for Information
Processing 296, 449-458 (2009)
J. Natwichai, X. Sun, X. Li: Data Reduction Approach for Sensitive
Associative Classification Rule Hiding. In: 19th Australian Database
Conference (2008)
K. Wang, B.C.M. Fung, P.S. Yu: Template-Based Privacy
Preservation in Classification Problems. In: 5th IEEE International
Conference on Data Mining, pp. 466-473 (2005)
Delis, A., Verykios, V.S., Tsitsonis, A.: A Data Perturbation Approach
to Sensitive Classification Rule Hiding. In: 25th Symposium On
Applied Computing (2010)
R. Li, D. de Vries, J. Roddick: Bands of Privacy Preserving Objectives:
Classification of PPDM Strategies. In: 9th Australasian Data Mining
Conference, pp. 137-151 (2011)
D. Kalles, D.T. Morris: Efficient Incremental Induction of Decision
Trees. Machine Learning 24(3), 231-242 (1996)
D. Kalles, A.Papagelis: Stable decision trees: Using local anarchy for
efficient incremental learning. International Journal on Artificial
Intelligence Tools 9(1), 79-95 (2000)
D. Kalles, A.Papagelis: Lossless fitness inheritance in genetic
algorithms for decision trees. Soft Computing 14(9), 973-993 (2010)
Breiman, L., J. H. Friedman, R. A. Olshen and C. J. Stone:
Classification and regression trees. Belmont, CA, Wadsworth (1984)
J.R. Quinlan, R.L. Rivest: Infering Decision Trees using the Minimum
Description Length Principle. Information and Computation 80, 227248 (1989)
H. Zantema, H.L.Bodlaender: Finding Small Equivalent Decision
Trees is Hard. International Journal of Foundations of Computer
Science 11(2), 343-354 (2000)

