# 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  
From the \(2\times 2\) column table, we know that after mining pattern \(S\), we need to find all the \(S\subseteq T_{i}\), \(l_{i}=l^{1}\) support numbers \(\sigma_{1}(S)\), and this process requires traversing the whole dataset once. Since the Westfall-Young Light algorithm [5] starts from a minimum support number of 1, the number of patterns to be mined is very large, and it would be too expensive to traverse the dataset once for each pattern mined to find its \(\sigma_{1}(S)\). When performing pattern mining, an index can be added to speed up the query, which is the position of transaction \(T_{i}\), so that counting \(l_{i}=l^{1}\) takes only linear time to find. The transaction dataset \(D\) with the index added is shown in Table 4.  
The FP-Tree with indexed structure is constructed based on the above dataset, as shown in Figure 4. The conditional pattern bases are constructed on the basis of the indexed FP-Tree, and the conditional pattern bases are constructed from the smallest to the largest support counts, that is, from \(I_{5}:<I_{2},I_{1}:\{8\}><I_{2}:\{0\}>\),\(I_{4}:<I_{2},I_{1}:\{3,5\}><I_{1}:\{9,12\}>\),\(I_{1}:<I_{2}:\{2,3,5,8\}>\). Next, we construct the indexed conditional FP-Tree based on the indexed conditional pattern base and find the pattern \(SI=(\{t_{i}\},\{TID_{i}\})\) with the index structure. The conditional pattern bases are constructed based on the index FP-Tree by supporting the degree counts from small to \begin{table}
\begin{tabular}{c c c} \hline \hline
**Index TID** & **Labels** & **Transaction** \\ \hline
0 & 0 & \(I_{2},I_{5}\) \\
1 & 1 & \(I_{1},I_{3}\) \\
2 & 1 & \(I_{1},I_{2},I_{3}\) \\
3 & 0 & \(I_{2}\) \\
4 & 0 & \(I_{1},I_{2},I_{3},I_{4}\) \\
5 & 1 & \(I_{1},I_{2},I_{3},I_{4}\) \\
6 & 1 & \(I_{2}\) \\
7 & 1 & \(I_{1},I_{3}\) \\
8 & 0 & \(I_{1},I_{2},I_{3},I_{5}\) \\
9 & 0 & \(I_{1},I_{3},I_{4}\) \\
10 & 1 & \(I_{2}\) \\
11 & 1 & \(I_{2}\) \\
12 & 0 & \(I_{1},I_{3},I_{4}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Transaction dataset with index. Figure 3: Pattern mining purpose. ing from \(I_{5}\) : \(\{<I_{2},I_{1}:\{8\}>,<I_{2}:\{0\}>\}\),\(I_{4}\) : \(\{<I_{2},I_{1}:\{3,5\}><I_{1}:\{9,12\}>\}\),\(I_{1}\) : \(\{<I_{2}:\{2,3,5,8\}>\}\). Next, we construct the indexed conditional FP tree based on the indexed conditional pattern base and find the pattern with the index structure \(SI=(\{t_{i}\},\{TID_{i}\})\). The null hypothesis \(H_{0}\) proposed in this paper is that pattern \(S\) is not significantly associated with the label \(l_{i}\), and the parameter to be tested in this paper can be set as \(\theta=\{(S,l_{i})|S\subseteq T_{j},j=1,\ldots,n,i=0,1\}\). According to Table 3 and Equation (9), the key variables for false positive control for the selected dataset \(D\) and the determined null hypothesis \(h_{0}\) are \(n\), \(n_{1}\), \(\sigma(S)\), and \(\sigma_{1}(S)\) in the case of \(l_{i}=l^{1}\) obtained after label replacement. Where \(n\),\(n_{1}\) can already be determined when the sample dataset is selected, and \(n\),\(n_{1}\) is fixed. While \(\sigma(S)\) and \(\sigma_{1}(S)\) are the support counts when \(S\subseteq T_{i}\) and \(l_{i}=l^{1}\) and \(S\subseteq T_{j}\), respectively. It is easy to see from the structure of dataset \(D\) that once the set of transactions \(\{T_{i}\}\) to which the pattern \(S\) belongs is known, the set of labels \(\{l_{i}\}\) corresponding to it can be found, and the support count \(\sigma(S)\) is the size of the set \(\{T_{i}\}\), and it is also not difficult to determine \(\sigma_{1}(S)\) based on the correspondence between transactions and labels. Therefore, it is not necessary to know what the specific pattern \(S\) is when performing the PFWER false positive control calculation, but only to know what sets of transactions \(\{T_{i}\}\) are available to mine the pattern \(S\). Finding out which transaction sets exist that can be mined for patterns is more important for subsequent computation. In this way, it is clearly more advantageous to use a vertical data format for data mining.