# Efficient False Positive Control Algorithms in Big Data Mining
## 3 PFWER-Based Distributed False Positive Control Algorithm
### Distributed PFWER Control Algorithm
#### 3.4.3 False Positive Control  
This section mainly uses the false positive control method proposed by [PERSON] and [PERSON] [30; 43] to control the FWER at the \(\alpha\) level, which is implemented with the main idea that a new resampled transactional dataset with no relationship between patterns and labels can be generated by just randomly arranging the class labels. This allows one to determine whether a false positive error has occurred by computing the minimum \(p\)-value after each permutation, \(p_{\text{min}}=\min p_{S}^{F}\), and checking whether \(p_{min}\leq\delta\) holds. The subsequent sections of this paper refer to this method as the WY replacement algorithm. The disadvantage of the WY replacement algorithm is that it is computationally expensive in addition to having a large number of replacement operations. [PERSON] [13] and other researchers found that in [PERSON]'s exact test, when \(2\times 2\) columns are fixed, then the value \((n,n_{1},\sigma(S))\) at the edge of the table is also fixed, and according to Equations (7) and (8) it is not difficult to find that the \(p\)-value is ultimately a function about \(\sigma_{1}(S)\). Since the objects in the \(2\times 2\) column table are discrete and can only take finitely many values, it can be determined that \(\sigma_{1}(S)\) is bounded, i.e., \(\sigma_{1}(S)\in[\sigma_{1}(S)_{min},\sigma_{1}(S)_{max}]\). Where \(\sigma_{1}(S)_{max}=\min(n_{1},\sigma(S))\), \(\sigma_{1}(S)_{min}=\max(0,\sigma(S)-(n-n_{1}))\). From the bound of \(\sigma_{1}(S)\), it can also be further deduced that there exists a minimum reachable \(p\)-value \(\varphi(\sigma_{S})\) strictly greater than 0 as follows. \[\varphi(\sigma_{S})=\min\{p_{S}^{F}(a)|\sigma_{1}(S)_{\min}\leq a\leq\sigma_{1 }(S)_{\max}\} \tag{13}\]  
According to Equation (8), the \(p\)-value calculated for [PERSON]'s exact test is the cumulative sum of the results obtained using Equation (7), and the values calculated in Equation (7) are all greater than 0. It can be inferred that when \(\sigma_{1}(S)=\sigma_{1}(S)_{min}\) or \(\sigma_{1}(S)=\sigma_{1}(S)_{max}\), the minimum reachable \(p\)-value \(\varphi(\sigma_{S})\). It is then possible to call all patterns \(S\) of \(\varphi(\sigma_{S})\leq\delta\) the set of measurable patterns so that patterns not in the set of \(\kappa(\delta)\) cannot be statistically  
Figure 8: Constructing frequent 1-item sets. significant under \(\delta\). On this basis, a monotonically decreasing lower bound \(\hat{\phi}(\sigma)\) on the minimum achievable \(p\)-value can be introduced, as shown in Equation (14). \[\hat{\phi}(\sigma){=} \begin{cases}\begin{aligned} \varphi(\sigma_{S})&0\leq \sigma_{S}\leq n_{1}\\ 1/\begin{pmatrix}n\\ n_{1}\end{pmatrix}&n_{1}\leq\sigma_{S}\leq n\end{aligned}\end{cases}  \tag{14}\]  
The monotonically decreasing lower bound \(\hat{\phi}(\sigma)\) on the minimum achievable \(p\)-value gives \(\hat{\kappa}(\delta)=\{S|\hat{\phi}(\sigma)\leq\delta\}\), which satisfies \(\kappa(\delta)\subset\hat{\kappa}(\delta)\), which, in turn, can be rewritten as \(\hat{\kappa}(\delta)=\{S|\sigma_{S}\geq\sigma_{\delta}\}\) due to monotonicity. That means only the mode \(S\) satisfying condition \(\hat{\kappa}(\delta)=\{S|\sigma_{S}\geq\sigma_{\delta}\}\) is valuable for the PFWER false positive control calculation. Based on the above, the pseudo-code of the distributed PFWER false positive control algorithm is proposed, as shown in Algorithms 3 and 4.