A minimum spanning tree equipartition algorithm for microaggregation

Abstract

In this paper, we propose a solution on microaggregation problem based on the hierarchical tree equi-partition (HTEP) algorithm. Microaggregation is a family of methods for statistical disclosure control of microdata, that is, for masking microdata, so that they can be released without disclose private information on the underlying individuals. Knowing that the microaggregation problem is non-deterministic polynomial-time-hard, the goal is to partition N given data into groups of at least K items, so that the sum of the within-partition squared error is minimized. The proposed method is general and it can be applied to any tree partition problem aiming at the minimization of a total score. The method is divisive, so that the tree with the highest ‘score’ is split into two trees, resulting in a hierarchical forest of trees with almost equal ‘score’ (equipartition). We propose a version of HTEP for microaggregation (HTEPM), that is applied on the minimum spanning tree (MST) of the graph defined by the data. The merit of the HTEPM algorithm is that it solves optimally some instances of the multivariate microaggregation problem on MST search space in . Experimental results and comparisons with existing methods from literature prove the high performance and robustness of HTEPM.

Keywords:

• data protection
• clustering
• microaggregation
• minimum spanning tree
• statistical disclosure control

Acknowledgments

The authors thank Prof Michael Laszlo, Prof Sumitra Mukherjee and Prof Domingo-Ferrer for providing the Tarragona, Census and EIA data sets. The work of Costas Panagiotakis has been partially supported by postdoctoral scholarship (2009–2010) from the Greek State Scholarships Foundation (I.K.Y.).

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. In the last step of HTEPM-d-T2 method, we have used the Diameter algorithm to further partition oversized groups and reduce information loss.

2. If the size of a given data set is lower than 100, then , since, if , according to the microaggregation we get the trivial solution of one group.

3. (true).