Authors: Philip Perry Pearce-Pearson, Phan Anh Le
- Python 3.9+
- Packages:
pip install pandas
pip install numpy
pip install matplotlib
pip install networkx
pip install ucimlrepoThis project implements a Differentially Private ID3 Decision Tree (DP-ID3) using the UCI Breast Cancer Recurrence dataset. The classical ID3 algorithm selects the feature that maximizes information gain, but in DP-ID3:
- All class counts
- Subset sizes
- Per-feature entropy values are computed using the Laplace mechanism, ensuring ε-Differential Privacy at each split. Because noise is added to every entropy computation, the DP decision tree becomes randomized, and repeated executions with the same dataset may produce different tree structures. We run the DP-ID3 algorithm five times to observe how privacy noise affects tree stability, accuracy, and usability.
a) Dataset Loading
We load the Breast Cancer Recurrence dataset using:
breast_cancer = fetch_ucirepo(id=14)
df = breast_cancer.data.original.copy()
df.replace("?", pd.NA, inplace=True)
df.dropna(inplace=True)This results in 277 rows × 10 columns, with 9 categorical features and 1 target label (Class).
b) Differential Privacy Components The project implements the following DP primitives:
- Laplace mechanism
laplace_noise(scale)- DP count query
dp_count(c, epsilon)- DP entropy: Entropy is computed using noisy class counts.
- DP feature split score: We approximate “entropy after split” using only DP counts. These pieces enable DP-ID3 to privately evaluate each feature without leaking exact statistics.
c) DP-ID3 Algorithm
The function:
dp_id3(data, target_column, features, epsilon, depth)recursively builds a private decision tree. A node becomes a leaf when:
- All examples in the subset share the same label
- No features remain
- Maximum depth is reached
- DP stopping condition triggers due to noisy small sample size
The algorithm:
- Allocates a per-node privacy budget
- Computes DP entropy for each feature
- Selects the feature with minimum noisy entropy
- Repeats recursively for each feature value
- Uses DP noisy majority vote when needed
To run the full DP-ID3 pipeline:
python3 ID3.pyThe script will:
- Load and clean the dataset
- Print DP entropy values
- Train the DP-ID3 model
- Print the learned tree (nested dictionary structure)
Running with alternative data
To test other datasets:
- Replace the dataset-loading block
- Set target_column to the correct label
- Features are automatically extracted as all remaining columns
Key parameters include:
- total_epsilon: Total privacy budget (default = 5.0)
- max_depth: Maximum tree depth (default = 5)
- e1: Per-node privacy budget = total_epsilon / (max_depth+1) / 2
- feature_cols: List of attribute columns used for splitting
- dp_noise: Laplace noise scale = 1/epsilon
If we change these parameters, it directly affects privacy, accuracy, and efficiency.
Because DP noise is added to every count and entropy, the learned trees differed across executions. Below are the actual roots observed across 5 runs:
- Run 1: breast-quad
- Run 2: menopause
- Run 3: tumor-size
- Run 4: breast-quad
- Run 5: tumor-size
Some trees produced deep splits (e.g., on inv-nodes, node-caps) while others collapsed into shallow predictions (e.g., a single split on tumor-size).
This variation directly reflects the injected DP noise and is expected.
[277 rows x 10 columns]
{'breast-quad': {'central': 'no-recurrence-events',
'left_low': {'tumor-size': {'0-4': 'no-recurrence-events',
'14-Oct': 'no-recurrence-events',
'15-19': 'no-recurrence-events',
'20-24': 'no-recurrence-events',
'25-29': 'no-recurrence-events',
'30-34': 'no-recurrence-events',
'35-39': 'no-recurrence-events',
'40-44': 'recurrence-events',
'45-49': 'no-recurrence-events',
'50-54': 'recurrence-events',
'9-May': 'no-recurrence-events'}},
'left_up': {'inv-nodes': {'0-2': {'node-caps': {'no': 'no-recurrence-events',
'yes': 'no-recurrence-events'}},
'11-Sep': 'recurrence-events',
'14-Dec': 'recurrence-events',
'15-17': 'no-recurrence-events',
'5-Mar': 'no-recurrence-events',
'8-Jun': 'recurrence-events'}},
'right_low': 'no-recurrence-events',
'right_up': 'no-recurrence-events'}}
None
{'menopause': {'ge40': {'tumor-size': {'0-4': 'no-recurrence-events',
'14-Oct': 'no-recurrence-events',
'15-19': 'no-recurrence-events',
'20-24': 'no-recurrence-events',
'25-29': 'no-recurrence-events',
'30-34': 'no-recurrence-events',
'35-39': 'no-recurrence-events',
'40-44': 'no-recurrence-events',
'45-49': 'recurrence-events',
'50-54': 'no-recurrence-events',
'9-May': 'no-recurrence-events'}},
'lt40': 'no-recurrence-events',
'premeno': {'tumor-size': {'0-4': 'no-recurrence-events',
'14-Oct': 'no-recurrence-events',
'15-19': 'no-recurrence-events',
'20-24': 'no-recurrence-events',
'25-29': 'no-recurrence-events',
'30-34': 'no-recurrence-events',
'35-39': 'no-recurrence-events',
'40-44': 'recurrence-events',
'45-49': 'no-recurrence-events',
'50-54': 'no-recurrence-events',
'9-May': 'no-recurrence-events'}}}}
None
{'tumor-size': {'0-4': 'no-recurrence-events',
'14-Oct': 'no-recurrence-events',
'15-19': 'no-recurrence-events',
'20-24': 'no-recurrence-events',
'25-29': 'no-recurrence-events',
'30-34': 'no-recurrence-events',
'35-39': 'no-recurrence-events',
'40-44': 'no-recurrence-events',
'45-49': 'no-recurrence-events',
'50-54': 'no-recurrence-events',
'9-May': 'no-recurrence-events'}}
None
{'breast-quad': {'central': 'no-recurrence-events',
'left_low': {'tumor-size': {'0-4': 'no-recurrence-events',
'14-Oct': 'no-recurrence-events',
'15-19': 'recurrence-events',
'20-24': 'recurrence-events',
'25-29': 'no-recurrence-events',
'30-34': 'no-recurrence-events',
'35-39': 'no-recurrence-events',
'40-44': 'recurrence-events',
'45-49': 'no-recurrence-events',
'50-54': 'no-recurrence-events',
'9-May': 'no-recurrence-events'}},
'left_up': {'breast': {'left': 'no-recurrence-events',
'right': 'no-recurrence-events'}},
'right_low': 'no-recurrence-events',
'right_up': 'no-recurrence-events'}}
None
{'tumor-size': {'0-4': 'no-recurrence-events',
'14-Oct': 'no-recurrence-events',
'15-19': 'no-recurrence-events',
'20-24': 'no-recurrence-events',
'25-29': 'no-recurrence-events',
'30-34': 'no-recurrence-events',
'35-39': 'no-recurrence-events',
'40-44': 'no-recurrence-events',
'45-49': 'no-recurrence-events',
'50-54': 'no-recurrence-events',
'9-May': 'no-recurrence-events'}}
None- Analysis
-
Privacy Implications In our implementation the main privacy parameter is the total budget epsilon = 5, which is split across tree depth and features. Because we use the Laplace mechanism for every count and entropy computation, the algorithm is randomized: even with the same dataset and hyper-parameters we do not always get the same tree. We can see this clearly from the five runs above. The root feature sometimes is breast-quad, sometimes menopause, and sometimes tumor-size. All three features are reasonably informative about recurrence, but DP noise in the split scores makes the “best” feature fluctuate from run to run. This instability is exactly the privacy effect of ε: the smaller epsilon is (more noise), the more the tree structure can change between runs, which prevents an attacker from confidently inferring any single individual’s contribution from the chosen splits.
-
Accuracy Implications The same randomness that protects privacy can hurt accuracy. In a non-private ID3, we would expect a single, stable root feature and very similar subtrees across runs. In our results, deeper parts of the tree also vary: for example, under breast-quad = left_low, the second-level split is sometimes on tumor-size, and in another run the next split for left_up is on inv-nodes in one tree but on breast in another. Some runs (where the root is just tumor-size) produce a very shallow tree that almost always predicts “no-recurrence-events”, which likely has lower recall for the minority “recurrence-events” class. This shows the typical DP trade-off: with our chosen ε, the model still uses sensible medical features, but the randomness can simplify the tree or choose slightly worse splits, which would lower classification accuracy compared to the non-private baseline.
-
Efficiency Implications From a computational point of view, adding differential privacy does not change the overall Big-O complexity of ID3, but it does add constant-factor overhead. At every node we now compute noisy counts and entropies for each feature and each label value, instead of using exact frequencies once. In practice, on this small dataset (277 rows, 9 features) the runtime remains very fast, and repeating the training five times is still interactive. However, the cost would grow linearly with the number of nodes and the number of DP queries: increasing the maximum depth or adding more features would both increase training time because more noisy statistics must be computed. So there is a three-way tuning trade-off: larger ε improves accuracy but reduces privacy; deeper trees improve accuracy but increase runtime and consume more of the privacy budget; shallower trees are cheaper and safer but may underfit.
• ID3.py: full implementation of the DP-ID3 algorithm
• README.md: project documentation
• Dataset accessed