Privacy issues during data publishing is an increasing concern of involved entities. The problem is addressed in the field of statistical disclosure control with the aim of producing protected datasets that are also useful for interested end users such as government agencies and research communities. The problem of producing useful protected datasets is addressed in multiple computational privacy models such as k-anonymity in which data is clustered into groups of at least k members. Microaggregation is a mechanism to realize k-anonymity. The objective is to assign records of a dataset to clusters and replace the original values with their associated cluster centers which are the average of assigned values to minimize information loss in terms of the sum of within group squared errors (SSE). While the problem is shown to be NP-hard in general, there is an optimal polynomial-time algorithm for univariate datasets. This paper shows that the assignment of the univariate Microaggregation algorithm cannot produce optimal partitions for integer observations where the computed centroids have to be integer values. In other words, the integrality constraint on published quantities has to be addressed within the algorithm steps and the optimal partition cannot be attained using only the results of the general solution. Then, an effective method that considers the constraint is proposed and analyzed which can handle very large numerical volumes. Experimental evaluations confirm that the developed algorithm not only produces more useful datasets but also is more efficient in comparison with the general optimal univariate algorithm.

In this paper, we propose an effective Microaggregation algorithm to produce a more useful protected data for publishing. Microaggregation is mapped to a clustering problem with known minimum and maximum group size constraints. In this scheme, the goal is to cluster n records into groups of at least k and at most 2k-1 records, such that the sum of the within-group squared error (SSE) is minimized. We propose a local search algorithm which iteratively satisfies the constraints of the optimal solution of the problem. The algorithm solves the problem in O (n2) time. Experimental results on real and synthetic data sets with different distributions demonstrate the effectiveness of the method in producing useful protected data sets.

One of the main techniques used in data mining is data clustering, which has many applications in computer science, biology and social sciences. Constrained clustering is a type of clustering in which side information provided by the user is incorporated into current clustering algorithms. One of the well researched constrained clustering algorithms is called Microaggregation. In a Microaggregation technique, the algorithm divides the dataset into groups containing at least  members, where  is a user-defined parameter. The main application of Microaggregation is in Statistical Disclosure Control (SDC) for privacy preserving data publishing. A Microaggregation algorithm is qualified based on the sum of within-group squared error, . Unfortunately, it has been proven that the optimal Microaggregation problem is NP-Hard in general, but the special univariate case can be solved optimally in polynomial time. Many heuristics exist for the general case of the problem that are founded on the univariate case. These techniques order multivariate records in a sequence. This paper proposes a novel method for record ordering. Starting from a conventional clustering algorithm, the proposed method repeatedly puts multivariate records into a sequence and then clusters them again. The process is repeated until no improvement is achieved. Extensive experiments have been conducted in this research to confirm the effectiveness of the proposed method for different parameters and datasets.