  This paper analyzes k nearest neighbor classification with training data
anonymized using anatomy. Anatomy preserves all data values, but introduces
uncertainty in the mapping between identifying and sensitive values. We first
study the theoretical effect of the anatomized training data on the k nearest
neighbor error rate bounds, nearest neighbor convergence rate, and Bayesian
error. We then validate the derived bounds empirically. We show that 1)
Learning from anatomized data approaches the limits of learning through the
unprotected data (although requiring larger training data), and 2) nearest
neighbor using anatomized data outperforms nearest neighbor on
generalization-based anonymization.
