Apriori_Goal Algorithm for Building Association Rules in a Classified Database

Vladimir Billig · 2024

Read Apriori_Goal Algorithm for Building Association Rules in a Classified Database by Vladimir Billig (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00615.txt.

Description

A 2024 arXiv research paper by Vladimir Billig. An efficient Apriori_Goal algorithm is proposed for constructing association rules in a relational database with predefined classification. The target parameter of the database specifies a finite number of goals G ​ o ​ a ​ l k Goal_{k} , for each of which the algorithm constructs association rules of the form X ⇒ G ​ o ​ a ​ l k X\Rightarrow Goal_{k} .

Catalog record

CREATORVladimir Billig
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-00615

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Apriori_Goal Algorithm for Building Association Rules in a Classified Database Vladimir Billig Abstract . An efficient Apriori_Goal algorithm is proposed for constructing association rules in a relational database with predefined classification. The target parameter of the database specifies a finite number of goals G ​ o ​ a ​ l k Goal_{k} , for each of which the algorithm constructs association rules of the form X ⇒ G ​ o ​ a ​ l k X\Rightarrow Goal_{k} . The quality of the generated rules is characterized by five criteria: two represent rule frequency, two reflect rule reliability, and the fifth is a weighted sum of these four criteria. The algorithm initially generates rules with single premises, where the correlation criterion between the premise X X and the conclusion G ​ o ​ a ​ l k Goal_{k} exceeds a specified threshold. Then, rules with extended premises are built based on the anti-monotonicity of rule frequency criteria and the monotonicity of rule reliability criteria. Newly constructed rules tend to decrease in frequency while increasing in reliability. The article proves several statements that justify the rule construction process. The algorithm enables the construction of both high-frequency and rare rules with low occurrence frequency but high reliability. It also allows for the generation of negative rules with negative correlation between the premise and conclusion, which can be valuable in practical applications for filtering out undesired goals. The efficiency of the algorithm is based on two factors: the method of encoding the database and its partitioning into subsets linked to the target parameter. Time complexity estimates for rule construction are provided using a medical database as an example. 1. Introduction Association rules are a crucial tool in knowledge extraction from databases. Their advantage lies in the fact that extracted knowledge is represented in implication form: X\Rightarrow Y (1) where X is the rule premise, and Y is the rule conclusion. This format is intuitive for experts who utilize extracted knowledge, interpreting the rule as ”if X , then Y ” or ” X implies Y .” However, a rule is valuable only if it holds with high probability. Association rules extracted from databases gained widespread use after the introduction of the Apriori algorithm, proposed by R. Agrawal and colleagues [ 1 , 2 , 3 ] . The Apriori algorithm considers a finite set of literals: D=\{d_{1},d_{2},\dots,d_{m}\} (2) and a database: db=\{t_{1},t_{2},\dots,t_{n}\} (3) consisting of records (transactions), where each transaction t_{k} is a subset of literals. In an association rule (1), X and Y are non-empty and non-overlapping subsets of D : X\cap Y=\emptyset (4) For each rule constructed by the Apriori algorithm, two characteristics determine its value: frequency and confidence. Frequency is defined as the ratio of transactions that contain both the premise and conclusion of the rule to the total number of transactions. Confidence is the ratio of transactions that contain both the premise and conclusion to those that contain only the premise. The objective of the Apriori algorithm is to generate all association rules whose frequency and confidence exceed predefined minimum thresholds. The efficiency of the Apriori algorithm, which enables it to manage the combinatorial explosion of possible rules, is based on the property of anti-monotonicity of frequency. If a set Z is not frequent, then any of its supersets (extensions of Z ) are also not frequent. As a result, the algorithm first identifies all frequent subsets of D , starting with single frequent items and expanding them iteratively. In the second stage, these frequent subsets are used to generate rules that satisfy the required confidence level. Frequency is the primary criterion: if a set of literals is not frequent, it is excluded from rule generation, even if it has a high probability of occurrence. Subsequent variations of association rule mining algorithms have, in one way or another, built upon the fundamental idea of the Apriori algorithm. These variations have evolved in different directions. One primary focus has been improving the efficiency of the algorithm to make it applicable to large databases. The key idea behind this optimization is to construct a data structure that allows rule generation using only a subset of the original database records. Several studies have contributed to this direction. For instance, F. Bodon [ 4 ] proposed a sorting tree structure that demonstrated its effectiveness in database compression. Another efficient implementation of the Apriori algorithm was developed by Christian Borgelt [ 5 , 6 , 7 ] , in which the database is compressed into a transaction tree. A distinctive feature of these works is their optimization of Apriori into a highly efficient implementation written in C. Borgelt’s survey [ 8 ] provides an overview of various algorithms for frequent pattern mining. The database model in the classic Apriori algorithm is based on a market basket analysis framework, where each record represents a shopping basket in a supermarket. The literals in this model correspond to individual products, each assigned a unique identifier (ID). Given that the number of products can be quite large, a hierarchical structure is often introduced to group products at different levels. Several studies have focused on the construction of multi-level association rules. The first notable work in this area was by J. Han and Y. Fu [ 9 ] . Later studies, such as [ 10 ] , analyzed the efficiency of multi-level rule construction. The seminal book by J. Han, M. Kamber, and J. Pei [ 11 ] , which covers fundamental concepts and methodologies in data mining, provides an in-depth discussion of various approaches to association rule mining within a broader data mining framework. However, the itemset-based database model is a special case of a more general relational database structure. It is desirable to apply association rule mining to relational databases as well. Such cases are explored in the work of Minakshi Kaushik and co-authors [ 12 ] , where the authors address how to adapt Apriori to datasets with different attribute types, including continuous and categorical attributes. Their study examines various approaches to transforming such data into the itemset format required by the Apriori algorithm. As mentioned earlier, a fundamental characteristic of the Apriori algorithm is the preprocessing of frequent itemsets before rule generation. However, this constraint results in the loss of potentially valuable rules that exhibit low frequency but high confidence—rules that may be particularly insightful for experts. Identifying such rare but highly reliable rules is often of significant practical interest. Studies such as [ 13 , 14 , 15 ] focus on mining rare association rules in databases where item frequencies vary widely. Another area of research involves the discovery of negative association rules, where the presence of one attribute reduces the likelihood of another. Studies [ 16 , 17 ] address techniques for mining negative patterns, which can be just as valuable in practice as positive association rules. Association rule mining has also been extensively applied to solving real-world problems across various domains. In particular, several studies [ 19 , 20 , 21 ] focus on extracting rules from medical databases, where association patterns can help identify important diagnostic and predictive factors. Such databases serve as a model framework for the Apriori_Goal algorithm proposed in

Read the complete text