Efficient Anonymizations with Enhanced Utility
Jacob H. Goldberger, Tamir Tassa · 2010
Abstract. One of the most well studied models of privacy preservation is k-anonymity. Previous studies of k-anonymization used various utility measures that aim at enhancing the correlation be-tween the original public data and the generalized public data. We, bearing in mind that a primary goal in releasing the anonymized database for data mining is to deducemethods of predicting the pri-vate data from the public data, propose a new information-theoretic measure that aims at enhancing the correlation between the generalized public data and the private data. Such a measure signifi-cantly enhances the utility of the released anonymized database for data mining. We then proceed to describe a new algorithm that is designed to achieve k-anonymity with high utility, independently of the underlying utility measure. That algorithm is based on a modified version of sequential clus-tering which is the method of choice in clustering. Experimental comparison with four well known algorithms of k-anonymity show that the sequential clustering algorithm is an efficient algorithm that achieves the best utility results. We also describe a modification of the algorithm that outputs k-anonymizations which respect the additional security measure of ℓ-diversity.