Discovering Functional Dependencies from Mixed-Type Data

Abstract. Given complex data collections, practitioners can perform non-parametric functional dependency discovery (FDD) to uncover relationships between variables that were previously unknown. However, known FDD methods are applicable to nominal data, and in practice non-nominal variables are discretized, e.g., in a pre-processing step. This is problematic because, as soon as a mix of discrete and continuous variables is involved, the interaction of discretization with the various dependency measures from the literature is poorly understood. In particular, it is unclear whether a given discretization method even leads to a consistent dependency estimate.

In this paper, we analyze these fundamental questions and derive formal criteria as to when a discretization process applied to a mixed set of random variables leads to consistent estimates of mutual information. With these insights, we derive an estimator framework applicable to any task that involves estimating mutual information from multivariate and mixed-type data. Last, we extend with this framework a previously proposed FDD approach for reliable dependencies. Experimental evaluation shows that the derived reliable estimator is both computationally and statistically efficient, and leads to effective FDD algorithms for mixed-type data.

Implementation

the Java source code (June 2020) by Panagiotis Mandros.

Related Publications

Mandros, P, Kaltenpoth, D, Boley, M & Vreeken, J Discovering Functional Dependencies from Mixed-Type Data. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'20), ACM, 2020. (16.8% acceptance rate)
Mandros, P, Boley, M & Vreeken, J Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms. In: Proceedings of the IEEE International Conference on Data Mining (ICDM'18), IEEE, 2018. (full paper, 8.9% acceptance rate; overall 19.9%)
Mandros, P, Boley, M & Vreeken, J Discovering Reliable Dependencies from Data: Hardness and Improved Algorithms. Technical Report 1809.05467, arXiv, 2018.
Mandros, P, Boley, M & Vreeken, J Discovering Reliable Approximate Functional Dependencies. In: Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp 355-363, ACM, 2017. (oral presentation, 8.6% acceptance rate; overall 17.5%)
Mandros, P, Boley, M & Vreeken, J Discovering Reliable Approximate Functional Dependencies. Technical Report 1705.09391, arXiv, 2017.