Minimum spanning tree partitioning algorithm for microaggregation
Authors:
- 23 May 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 17 (7) , 902-911
Abstract
This paper presents a clustering algorithm for partitioning a minimum spanning tree with a constraint on minimum group size. The problem is motivated by microaggregation, a disclosure limitation technique in which similar records are aggregated into groups containing a minimum of k records. Heuristic clustering methods are needed since the minimum information loss microaggregation problem is NP-hard. Our MST partitioning algorithm for microaggregation is sufficiently efficient to be practical for large data sets and yields results that are comparable to the best available heuristic methods for microaggregation. For data that contain pronounced clustering effects, our method results in significantly lower information loss. Our algorithm is general enough to accommodate different measures of information loss and can be used for other clustering applications that have a constraint on minimum group size.Keywords
This publication has 9 references indexed in Scilit:
- A polynomial algorithm for optimal univariate microaggregationIEEE Transactions on Knowledge and Data Engineering, 2003
- Practical data-oriented microaggregation for statistical disclosure controlIEEE Transactions on Knowledge and Data Engineering, 2002
- An efficient k-means clustering algorithm: analysis and implementationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- LHS-Based Hybrid Microdata vs Rank Swapping and Microaggregation for Numeric Microdata Protection2002
- On the complexity of optimal microaggregation for statistical disclosure controlStatistical Journal of the United Nations Economic Commission for Europe, 2001
- Data clusteringACM Computing Surveys, 1999
- Security-control methods for statistical databases: a comparative studyACM Computing Surveys, 1989
- Graph-Theoretical Methods for Detecting and Describing Gestalt ClustersIEEE Transactions on Computers, 1971
- Hierarchical Grouping to Optimize an Objective FunctionJournal of the American Statistical Association, 1963