Computing contingency tables from sparse ADtrees

doi:10.1007/s10489-014-0624-z

Return

Computing contingency tables from sparse ADtrees

2014-12-25

PRE

Fei Ding

庄

庄毅 (Yi Zhuang) *

DOI：10.1007/s10489-014-0624-z

Original

Original request for help

Save

Abstract

En 中文

In data-mining algorithms contingency tables are frequently built from ADtrees, as ADtrees have been demonstrated to be an efficient data structure for caching sufficient statistics. This paper introduces three modifications. The first two use a one-dimensional array and a hash map for representing contingency tables, and the third uses the non-recursive approach to build contingency tables from sparse ADtrees. We implement algorithms to construct contingency tables with a two-dimensional array, a tree, a one-dimensional array, and a hash map using recursion and non-recursive approaches in Python. We empirically test these algorithms in five aspects with a large number of randomly generated datasets. We also apply the modified algorithms to Bayesian networks learning and test the performance improvements using three real-life datasets. We demonstrate experimentally that all three of these modifications improve algorithm performance. The improvements are more significant with higher arities and larger arity values.

Keywords:

Data mining

Contingency tables

Sparse ADtrees

Non-recursive algorithms

Bayesian networks learning

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.