umbra-k 0.1.0
High-performance Mondrian K-Anonymity implementation.
Requires Python: >=3.9

# UMBRA-K

[![Vecture Laboratories](https://img.shields.io/badge/VECTURE-LABORATORIES-black?style=for-the-badge&labelColor=ff3333)](https://www.vecture.de)
[![License: MIT](https://img.shields.io/badge/License-MIT-grey?style=for-the-badge)](LICENSE)
[![Python](https://img.shields.io/badge/Python-3.9+-blue?style=for-the-badge)](https://www.python.org)

**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$.

```text
    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

```bash
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

```python
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:**
```text
     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.

```python
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.

```bash
# 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.*