## 3 Methodology and Algorithm Descriptions
### Apriori Algorithm  
The Apriori algorithm relies on a level-wise search strategy, which progressively generates and tests larger itemsets. It operates under the fundamental principle known as the Apriori property. This property asserts that if an itemset is frequent, then all of its subsets must also be frequent. Conversely, if an itemset is infrequent, its supersets must also be infrequent. This property significantly helps reduce the number of candidate itemsets that need to be examined, making the process more efficient [5; 6].  
The Apriori algorithm operates through multiple iterations, beginning with single-item item itemsets (1-itemsets) and progressively building up to larger itemsets (k-itemsets). It starts by setting key parameters: the support threshold (min_support), which defines the minimum frequency an itemset must have to be considered frequent; the confidence threshold (min_confidence), which determines the minimum reliability required for an association rule to be accepted; and the database (D), which consists of a list of transactions, each containing a set of purchased items.  
The algorithm begins by scanning the entire dataset to identify and count the frequency of all individual items. These are considered candidate 1-itemsets. Any itemset whose support--calculated as the proportion of transactions in which it appears--falls below the minimum threshold is discarded. For instance, if item {A} appears in 100 out of 1000 transactions, its support is 0.10. If the minimum support is 0.12, item {A} is deemed infrequent and removed. Only itemsets meeting the threshold are retained as frequent itemsets.  
Next, the algorithm generates candidate k-itemsets from the previously discovered frequent (k \(-\) 1)-itemsets. This is performed by joining pairs of frequent (k \(-\) 1)-itemsets, with the constraint that all subsets of any candidate must themselves be frequent. For example, if {A} and {B} are both frequent 1-itemsets, {A, B} becomes a candidate 2-itemset. The dataset is then scanned again to determine the support of each candidate itemset. Those falling below the minimum threshold are pruned according to the Apriori property, which states that all subsets of a frequent itemset must also be frequent.  
This iterative process continues for k \(\geq\) 2, with the algorithm generating and evaluating increasingly larger itemsets until no further frequent itemsets can be found. At this point, the algorithm shifts to generating association rules from the discovered frequent itemsets. A rule takes the form X \(\rightarrow\) Y, where X and Y are disjoint itemsets (i.e., X \(\cap\) Y = \(\emptyset\)). A rule is considered valid if its confidence, representing the likelihood of Y occurring given X, exceeds the predefined confidence threshold. Additionally, the lift metric is computed to assess the strength of the rule relative to random co-occurrence.  
Finally, the algorithm outputs all association rules that satisfy the minimum support and confidence thresholds, revealing significant item relationships within the transaction data.  
The time complexity of the Apriori algorithm is influenced by several key factors. One major factor is the number of database scans required, as each iteration involves a complete pass through the dataset to count the occurrences of itemsets. The total number of these scans is proportional to the length of the longest frequent itemset discovered. Another contributing factor is the size of the candidate itemsets, which increases exponentially as the itemset length grows. This rapid growth in candidate sets significantly raises computational demands.  
Overall, the time complexity of the Apriori algorithm can be expressed as O (N \(\times\) K \(\times\) L), where N represents the number of transactions, K is the maximum size of itemsets considered, and L is the maximum number of candidate itemsets generated in any iteration.  
This exponential growth in candidate itemsets makes Apriori less efficient on large datasets with many items.