概況

We study the problem of r-anonymized clustering and give a k-means type extension. The problem is partition a set of objects into k different groups by minimizing the total cost between objects and cluster centers subject to a constraint that each cluster contains at least r objects. Previous work has reported an approach when the cluster centers are constrained to be a real member of the objects. In this paper, we release the constraint and allow a center to be the mean of the objects in its group, similar to the settings of the classical k-means clustering model. To address the inherent computational difficulty, we exploit linear program relaxation to find high quality solutions in an efficient manner. We conduct a series of experiments and confirm the effectiveness of the method as expected.