# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 1 Introduction  
Association rule mining, a research hotspot in recent years, has been widely applied in the era of big data (e.g., cause analysis of traffic accidents [1], association analysis of weather forecasting [2], interest-based real-time news recommendation [3], recommendation of bank marketing plan [4], recommendation of e-commerce matching purchase and shopping basket analysis [5]). In particular, it has been used to realize the data-driven optimization of complex systems in various industries [6]. Association rule mining refers to finding implications such as \(A\Rightarrow B\) from the given transaction set, where \(A\) and \(B\) are itemsets. The former is called an association rule antecedent, while the latter is called an association rule consequent. If the probability for \(A\) and \(B\) to appear in the transaction set is greater than a certain threshold, it is then called a frequent itemset; otherwise, it is referred to as a non-frequent itemset. \(|A|\) or \(|B|\) represents the number of items in the itemset. If \(|A|=k\), \(A\) is called \(k\)-itemset. Hence, any item can be independently called a frequent 1-itemset or non-frequent 1-itemset. However, the feature of big data association rule mining is that the transaction number of a given transaction set is massive, and the dimension of the transaction set is very high, so it is difficult to mine association rules from it. \(I=\{I_{1},I_{2},\ldots,I_{m}\}\) is the set of all items. \(D=\{T_{1},T_{2},T_{3},\ldots,T_{n}\}\) is the big data transaction set with association rules to be mined, where \(m\) is the dimension of the transaction setand \(n\) is the number of transactions in transaction set. \(T_{i}\subseteq I\), \(T_{i}\
eq\O\), and \(i=1\), \(2\),..., \(m\). \(T_{i}=\{I_{i1}\), \(I_{i2}\), \(I_{i3}\),... \(\}\) is a transaction in the transaction set. If \(A\Rightarrow B\) is an association rule, \(A\subset I\), \(B\subset I\), and \(A\cap B=\O\). The support degree (_support_) and confidence level (_confidence_) are used in association rule mining to measure the weakness of one rule, which are defined as follows:  
\[support(A\Rightarrow B)=P(A\cup B) \tag{1}\]  
\[confidence(A\Rightarrow B)=\frac{P(A\cup B)}{P(A)} \tag{2}\]  
where \(P\) (\(X\)) is the probability (_support_) for itemset \(X\) to appear in given transaction set \(D\). Therefore, the corresponding support degree and confidence level of association rule \(A\)\(\Rightarrow B\) can be calculated only if \(P\) (\(A\cup B\)) and \(P\) (\(A\)) are obtained, and whether the two are strongly associated can be determined according to the threshold. For example, assume that \(A\) is the itemset [1, 2] and \(B\) is the itemset [2, 3, 4]. Then, _support_ (\(A\Rightarrow B\)) is equal to the probability of the [1, 2, 3, 4] appearing in transaction set \(D\). _confidence_ (\(A\Rightarrow B\)) is equal to the ratio of the probability of the [1, 2, 3, 4] to probability of the [1, 2] in transaction set \(D\). Hence, the association rule mining problem can be transformed into a mining problem of frequent itemsets. As frequent itemsets have a very important property (i.e., the non-empty subsets of all frequent itemsets are also frequent itemsets, and the supersets of all non-frequent itemsets are also non-frequent itemsets), if an itemset is a frequent itemset but any of its superset is a non-frequent itemset, it contains most frequent itemsets with the maximum capacity. In this way, the algorithm is able to find all frequent itemsets with the least optimization objectives. The itemsets of this type are called maximal frequent itemsets (MFIs). Thus, the frequent itemset mining (FIM) problem can also be transformed into the problem of maximal frequent itemsets mining (MFIM). For the purpose of association rule mining, MFIM has some advantages over FIM. Firstly, it makes the optimization problem have fewer targets to be searched. For a set of transactions with a given support threshold, the set of all MFIs is a subset of the set of all frequent itemsets.