# Multi-Objective Optimization for High-Dimensional Maximal Frequent Itemset Mining
## 3 Multi-Objective Optimization of Maximal Frequent Itemset Mining
### Fitness Function  
The algorithm deletes all 1-itemsets with _support_ smaller than the threshold in _step_1, which actually significantly decreases the dimensions of searching space. Based on Property 1, all follow-up searching tasks are performed in the \(m\)-dimensional space because all the multi-itemsets that contain non-frequent 1-itemsets cannot be frequent itemsets.  
In the selection mechanism of the survival of the fittest in multi-objective optimization, the quality of individual encodes was assessed by the fitness function. The individual encodes correspond to one itemset, and the _support_ of the itemset can reflect the quality of individuals. The number of items of the itemset is an objective of the algorithm because it searches the maximal frequent itemset or the itemset that contains items that meet the _support_ threshold as much as possible. Hence, the product of support and number of items in the itemset was used as the evaluation function of individual encodes.  
Given the reduced transaction set \(D=\{T_{1},\,T_{2},\,T_{3},\,\ldots,\,T_{n}\}\), \(T_{i}=\{t_{i1},\,t_{i2},\,\ldots,\,t_{im}\}\), \(t_{ij}\in\{0,\,1\}\), (\(i=1,\,2,\,\ldots,\,n\)), (\(j=1,\,2,\,\ldots,\,m\)). The evolutionary individual encodes \(X=(x_{1},x_{2},\ldots,x_{m})\), \(x_{i}\in\{0,\,1\}\) were provided. It hypothesized that the itemset determined by the binary individual encodes \(X\) was \(A\), and the pseudo-code Algorithm 1 of the fitness of the evolutionary algorithm of the individual \(X\) was calculated.  
```
Input: \(D=(T_{1},T_{2},\ldots,T_{n})\), \(X=(x_{1},x_{2},\ldots,x_{m})\), \(A\) Output: A new \(X\) and it's Fitness \(length=\sum_{i=1}^{m}x_{i}\); fitness \(=0\); \(f=0\); \((r_{1},r_{2},\ldots,r_{m})=(0,0,\ldots,0)\); for\(i=1\): \(n\) do  Continue with some probability;  If \(A\subseteq T_{i}\); then \(fitness=fitness+1\); \(f\); \(r_{j}=r_{j}+t_{ij}\);  end  end \(f=f+1\);  end for\(j=1\): \(m\) do \(r_{i}/f>SupportThreshold\) then \(r_{j}=1\);  else \(r_{j}=0\);  end if \(\sum_{i=1}^{m}r_{i}>length\) then  select \(x_{k}=0\) with \(r_{k}/f>SupportThreshold\); \(x_{k}=1\); fitness \(=r_{k}/f^{*}(length+1)\);  else \(fitness=fitness/f^{*}length\);  end Return fitness;
```  
**Algorithm 1** Giting fitness  
where \"Continue with some probability\" is an operation of skipping over the \"for\" loop at a certain probability, which can shorten the execution time of the fitness function. In fact, this step replaces the sampled transaction sets by the real reduced transaction set \(D\) and the sampled transaction sets distribute uniformly in \(D\). This again significantly reduces the time complexity of fitness function, and it would not influence the evolutional computation mechanism of the survival of the fittest. It was feasible in this algorithm.  
The calculation of the fitness function involves two tasks. First, it adds one item into the itemset based on no changes to the frequency (whether _support_ is still higher than the threshold), and no item is added if the itemset is a maximal frequent itemset. Second, the product between the _support_ of the new itemset and the number of items is returned. The returned value of the fitness is composed of _supports_ of two factors and the number of items. On the one hand, the _support_ of the itemset was investigated. On the other hand, the number of items in the itemset was considered. This was caused by the optimization objective of the maximal frequent itemset.