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

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 mm groups of small fixed size kk, 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)(m×k)-partitioning problem.