Homogeneous bipartition based on multidimensional ranking
Michael J Marie Aupetit · 2008
Abstract. We present an algorithm which partitions a data set in two parts with equal size and experimentally nearly the same distribution measured through the likelihood of a Parzen kernel density estimator. The generation of the partition takes O ( 1 N(N − 1)) operations (N number of 2 data) and is 2 orders of magnitude faster than the state of the art. 1 Generating an equi-distributed bipartition 1.1 Problem and applications We consider the problem of generating a homogeneous partition of a data set, that is a partition such that each part has the same distribution as the whole. We focus here on bipartitions, which are partitions containing two parts with equal size (the number N of data is even) (Figure 1a). This problem has been studied under the name ”data squashing ” [2] to summarize massive data sets in a way which preserves statistical relationships among