Bregman divergences in the ( m × k ) -partitioning problem

• Published in: Computational statistics & data analysis 2006-11, Vol.51 (2), p.668-678
• Main Authors: Kokolakis, G., Nanopoulos, Ph, Fouskakis, D.
• Format: Article
• Language: English
• Subjects: Bregman divergences; Confidentiality; Convex partition; Data masking; Exact sciences and technology; Fixed cardinality partitioning; Fixed size micro-aggregation; General topics; Mathematics; Multivariate analysis; Numerical analysis; Numerical analysis. Scientific computation; Numerical methods in probability and statistics; Probability and statistics; Probability theory and stochastic processes; Probability theory on algebraic and topological structures; Pythagorean property; Sciences and techniques of general use; Statistics
• ISSN: 0167-9473; 1872-7352
• DOI: 10.1016/j.csda.2006.02.017

A method of fixed cardinality partition is examined. This methodology can be applied on many problems, such as the confidentiality protection, in which the protection of confidential information has to be ensured, while preserving the information content of the data. The basic feature of the technique is to aggregate the data into m groups of small fixed size k , by minimizing Bregman divergences. It is shown that, in the case of non-uniform probability measures the groups of the optimal solution are not necessarily separated by hyperplanes, while with uniform they are. After the creation of an initial partition on a real data-set, an algorithm, based on two different Bregman divergences, is proposed and applied. This methodology provides us with a very fast and efficient tool to construct a near-optimum partition for the ( m × k ) -partitioning problem.