MINING APPROXIMATE FUNCTIONAL DEPENDENCIES AS CONDENSED REPRESENTATIONS OF ASSOCIATION RULES
Aravind Kalavagattu · 2008
Approximate Functional Dependencies (AFD) mined from database relations represent potentially interesting patterns and have proven to be useful for various tasks like feature selection for classification, query optimization and query rewriting. Though the discovery of Functional Dependencies (FDs) from a relational database is a well studied problem, the discovery of AFDs still remains under explored, posing a special set of challenges. Such challenges include defining right interestingness measures for AFDs, employing effective pruning strategies and performing an efficient traversal in the search space of the attribute lattice. This thesis presents a novel perspective for AFDs as condensed representations of association rules; for example, an AFD (Model determines Make) is a condensation of various association rules like, (Model:Accord determines Make:Honda), (Model:Camry determines Make:Toyota). In this regard, this thesis describes two metrics, namely Confidence and Specificity analogous to the standard metrics confidence and support used in association rules respectively. This thesis presents an algorithm called AFDMiner for efficiently mining high quality AFDs by employing effective pruning strategies. AFDMiner performs a