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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1109/TKDE.2005.112 | Knowledge and Data Engineering, IEEE Transactions |
Keywords | Field | DocType |
computational complexity,data handling,data mining,pattern clustering,security of data,statistical databases,tree searching,very large databases,NP-hard problem,heuristic clustering methods,large data sets,microaggregation disclosure limitation technique,microdata protection,minimum information loss microaggregation problem,minimum spanning tree partitioning algorithm,pattern clustering algorithm,Index Terms- Clustering,disclosure control.,microdata protection,minimum spanning tree,partitioning | Data mining,Data set,Computer science,Artificial intelligence,Spanning tree,Cluster analysis,Minimum spanning tree,Heuristic,Information loss,Algorithm,Group method of data handling,Machine learning,Computational complexity theory | Journal |
Volume | Issue | ISSN |
17 | 7 | 1041-4347 |
Citations | PageRank | References |
104 | 3.56 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Laszlo | 1 | 214 | 10.76 |
Sumitra Mukherjee | 2 | 311 | 31.75 |