umbra-k 0.1.0

High-performance Mondrian K-Anonymity implementation.

UMBRA-K

Umbra-K is a high-performance, strictly typed Python implementation of the Mondrian Multidimensional K-Anonymity algorithm. It is designed to transform sensitive datasets into privacy-preserving formats suitable for safe distribution and machine learning, ensuring mathematical guarantees against re-identification attacks.

---

1. Theoretical Foundation: The Privacy Problem

1.1 The Anonymization Myth

Removing "Direct Identifiers" (e.g., Names, SSNs) is insufficient for privacy. Research by Latanya Sweeney (2002) demonstrated that 87% of the U.S. population could be uniquely identified using only three attributes: {Zip Code, Gender, Date of Birth}.

These attributes are Quasi-Identifiers (QIs). While not unique individually, their combination creates a unique "fingerprint" that can be linked to external datasets (e.g., Voter Rolls) to re-identify individuals.

1.2 The Solution: $k$-Anonymity

A release of data satisfies $k$-anonymity if every individual in the dataset cannot be distinguished from at least $k-1$ other individuals with respect to the quasi-identifiers.

Formal Definition: Let $T$ be a table with quasi-identifiers $Q_{ID}$. $T$ satisfies $k$-anonymity if for every sequence of values $q \in T[Q_{ID}]$, the number of occurrences of $q$ in $T$ is at least $k$.

$$ \forall q \in \pi_{Q_{ID}}(T), \quad count(q) \ge k $$

Where:

• $T$: The dataset.
• $Q_{ID}$: The set of quasi-identifier columns (e.g., Age, Zip).
• $k$: The privacy parameter (e.g., $k=5$ means groups of 5 indistinguishable records).

---

2. Algorithmic Core: The Mondrian Protocol

Umbra-K implements the Top-Down Greedy Mondrian Algorithm (LeFevre et al., 2006). Unlike optimal $k$-anonymity (which is NP-Hard), Mondrian approximates the optimal solution using a recursive multidimensional partitioning strategy, achieving a time complexity of $O(N \log N)$.

2.1 The Logic

The algorithm treats the dataset as a multi-dimensional spatial domain.

1. Initialization: The entire dataset is considered a single partition.
2. Constraint Check: If a partition contains fewer than $2k$ records, it cannot be split further without violating the privacy constraint. It is finalized as an Equivalence Class.
3. Dimensionality Reduction: The algorithm selects the dimension (column) with the widest Normalized Span. $$ Span(D) = \frac{max(D) - min(D)}{global_max(D) - global_min(D)} $$
4. Partitioning: The data is split into two sub-partitions along the median of the chosen dimension.
   • $P_{left} = {x \in P \mid x.dim \le median}$
   • $P_{right} = {x \in P \mid x.dim > median}$
5. Recursion: The process repeats recursively for $P_{left}$ and $P_{right}$ until no valid splits remain.

2.2 Visual Abstraction

The algorithm builds a KD-Tree structure. Below is a 2D representation of partitioning a dataset by Age and Salary with $k=2$.

    Salary
      ^
      |
  100k|       +-------+-------+
      |       |  EQ1  |  EQ2  |
   80k|-------+-------+-------+  <-- Split 2 (Salary=80k)
      |       |       |       |
      |  EQ3  |  EQ4  |  EQ5  |
   40k|       |       |       |
      +-------+-------+-------+--> Age
              ^       ^
           Split 1  Split 3
          (Age=30) (Age=55)

Each rectangular region (EQ) contains $\ge k$ records. The exact coordinates are suppressed and replaced by the region's boundaries.

---

3. Installation

pip install umbra-k

Requirements:

• Python $\ge$ 3.9
• Pandas $\ge$ 1.0
• Numpy
• Scikit-learn (for API compatibility)

---

4. Usage Protocol

Umbra-K follows the standard Scikit-Learn Transformer API, allowing seamless integration into data preprocessing pipelines.

4.1 Basic Implementation

import pandas as pd
from umbra_k import MondrianAnonymizer

# 1. Ingest Data
data = pd.DataFrame({
    'age': [23, 23, 24, 25, 50, 51, 52, 54],
    'zip': [10000, 10000, 10000, 10000, 20000, 20000, 20000, 20000],
    'salary': [50000, 55000, 52000, 51000, 90000, 92000, 91000, 95000]
})

# 2. Initialize Anonymizer
# We target 'age' and 'zip' as Quasi-Identifiers. 'salary' is sensitive and left untouched.
# We set k=2, ensuring groups of at least 2.
anonymizer = MondrianAnonymizer(k=2, quasi_id=['age', 'zip'])

# 3. Execute Transformation
protected_df = anonymizer.fit_transform(data)

print(protected_df)

Output:

     age    zip  salary
0  23-23  10000   50000
1  23-23  10000   55000
2  24-25  10000   52000
3  24-25  10000   51000
4  50-51  20000   90000
5  50-51  20000   92000
6  52-54  20000   91000
7  52-54  20000   95000

4.2 Advanced: Scikit-Learn Pipeline Integration

Umbra-K can be inserted directly into ML pipelines to anonymize training data on the fly.

from sklearn.pipeline import Pipeline
from sklearn.ensemble import RandomForestClassifier
from umbra_k import MondrianAnonymizer

pipeline = Pipeline([
    # Step 1: Anonymize sensitive features
    ('privacy_layer', MondrianAnonymizer(k=5, quasi_id=['age', 'zip_code'])),
    
    # Step 2: Encode the now-categorical ranges (e.g. "20-30") into numbers
    # Note: Requires a custom encoder or OneHotEncoder handling strings
    
    # Step 3: Classifier
    ('classifier', RandomForestClassifier())
])

---

5. API Reference

MondrianAnonymizer

Parameter	Type	Default	Description
k	int	2	The privacy parameter. Minimum number of records per group.
quasi_id	List[str]	None	List of column names to be treated as quasi-identifiers.

Methods

• fit(X, y=None): Validates parameters. Returns self.
• transform(X): Performs the recursive partitioning and returns the anonymized DataFrame.
• fit_transform(X, y=None): Convenience method to fit and transform in one step.

Metrics

• calculate_avg_equivalence_class_size(df, k, quasi_id): Calculates the $C_{avg}$ information loss metric.

---

6. System Limitations

While Mondrian is efficient, users should be aware of theoretical limitations:

1. Homogeneity Attack: If all records in an equivalence class have the same sensitive attribute value (e.g., all people in age group "20-25" have "Cancer"), $k$-anonymity does not prevent attribute inference.
2. High Dimensionality: As the number of Quasi-Identifiers increases, the data becomes sparse ("Curse of Dimensionality"), forcing the algorithm to create very large ranges to satisfy $k$, which drastically reduces data utility.

---

7. Development & Testing

The repository includes a hyper-rigorous test suite using Hypothesis for property-based fuzzing.

# Run the rigorous test suite
pytest tests/test_rigorous_properties.py

# Run standard unit tests
pytest tests/test_anonymizer.py

8. License

Released under the Vecture-1.0 mandate (MIT License). See LICENSE for details.

---

The eye remains open. Vecture sees the path.