# Efficient False Positive Control Algorithms in Big Data Mining
## 3 PFWER-Based Distributed False Positive Control Algorithm
### Index-Tree Algorithm
#### 3.3.3 Index Optimization
The transactional dataset of Table 4 is converted into a vertical data format representation, as shown in Table 5. Data mining is performed to find the patterns to be computed by intersecting the index set of each pair of items in the item set. For example, the index set of the pattern \(\{I_{1},I_{2}\}\) is \(TID(I_{1},I_{2})=TID(I_{1})\cap TID(I_{2})=\{2,3,5,8\}\). **Theorem 5**. : _If there exists \(TID(S_{1})=TID(S_{2})\), then \(p_{S_{1}}^{\rm F}(b)=p_{S_{2}}^{\rm F}(b)\)._  
Proof. : If there exists \(TID(S_{1})=TID(S_{2})\), then it means that the number of transactions containing patterns \(S_{1}\) and \(S_{2}\) are equal, i.e., \(|TID(S_{1})|=|TID(S_{2})|\), so there is \(\sigma(S_{1})=\sigma(S_{2})\). Again, since labels have a one-to-one correspondence with transactions,  
Figure 4: Pattern mining purpose. \begin{table}
\begin{tabular}{c c} \hline \hline
**Item Set** & **TID-Set** \\ \hline \(l_{1}\) & \(\{1,2,3,5,7,8,9,12\}\) \\ \(l_{2}\) & \(\{0,2,3,4,5,6,8,10,11\}\) \\ \(l_{3}\) & \(\{1,2,3,5,7,8,9,12\}\) \\ \(l_{4}\) & \(\{3,5,9,12\}\) \\ \(l_{5}\) & \(\{0,8\}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Vertical data format transaction dataset. although \(jr\)permutations are performed, pattern \(s_{1}\) belongs to the same transaction set as pattern \(s_{2}\). Therefore, for each permutation, there is \(\sigma_{1}(S_{1})=\sigma_{1}(S_{2})\). The total number of transactions \(n\) is fixed with the number of labels \(l_{i}=l^{1}\) for the same dataset \(n_{1}\), substituting \(\sigma(S)\), \(\sigma_{1}(S)\), \(n\) and \(n_{1}\) into Equations (7) and (8) to find \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\). Substituting \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\) into Equation (9) (FWER false positive control formula) shows that \(p_{S_{1}}^{F}(b)\) has the same effect as \(p_{S_{2}}^{F}(b)\) on Equation (9), so their calculated \(p\)-values have the same influence on Equation (9) for different patterns with the same index set, so it is sufficient to perform the \(p\)-value calculation only once. Based on the above problem analysis, it is clear that mining the set of transactions containing pattern \(S\) is more useful for the subsequent computation than mining all patterns in the dataset and then computing the corresponding dataset. Inspired by the vertical data format, the index tree is pruned again according to Theorem 5 to reduce the computation of invalid patterns generated in the data mining process. The conditional pattern base of \(I_{4}\) is \(<I_{2},I_{1}:\{3,5\}><I_{1}:\{9,12\}>\) according to the item header table in Figure 4, and the conditional tree constructed from this conditional pattern base is shown in Figure 5. The conditional tree using \(I_{4}\) is pattern mined using the FP-Growth algorithm by combining all nodes on this single path and then combining the combined set with that node to form the pattern output. According to the above statement, from the conditional tree of \(I_{4}\), we will receive \(S_{1}=\{I_{1},I_{4},\{3,5,9,12\}\}\), \(S_{2}=\{I_{2},I_{4},\{3,5\}\}\), \(S_{3}=\{I_{1},I_{2},I_{4},\{3,5\}\}\), but actually patterns \(S_{2}\) and \(S_{3}\) are exactly equal for the PFWER false positive control calculation, and there is no need to repeat the calculation; therefore, it is only necessary to know the index set of each node to substitute into the FWER control formula for the calculation. When the number of nodes contained in a single-path conditional tree is very large, it can reduce a lot of additional computational overhead. The purpose of Algorithm 1 is to mine the index set containing the patterns and to provide computational preparation for the subsequent PFWER false positive control. The first line of the algorithm constructs the set of frequent1 -items and calculates their support counts. The second line of the algorithm constructs the index tree. In the third line of the algorithm, it calls Algorithm 2 to perform pruning operations on the index tree.