# Efficient False Positive Control Algorithms in Big Data Mining
## 3 PFWER-Based Distributed False Positive Control Algorithm
### Index-Tree Algorithm
#### 3.3.2 Pruning Operation  
This chapter focuses on controlling the number of false positive errors in multiple hypothesis testing using the PFWER control method. According to the concept of FWER control, it is known that FWER (family-wise error rate) is the probability of at least one false positive error, and to ensure that the probability of error is as small as possible is to make \(FWER(\delta)\leq\alpha\). This means that reducing the significance level of \(p_{S}^{F}(b)\) from the original \(\alpha\) to \(\delta\) is a guarantee that \(FWER(\delta)\leq\alpha\). In this way, the problem becomes one of computing the significance threshold \(\delta\), where \(\delta=max\{\delta|FWER(\delta)\leq\alpha\}\). Since the Westfall-Young Light algorithm [5] requires \(jr=10^{3}\sim 10^{4}\) times permutation operation for label \(i\) in order to make the label unassociated with the pattern, and determines whether a false positive error has occurred by checking whether there is \(p_{min}\leq\alpha\) where \(p_{min}\leq\min p_{S}^{F}(b)\). Then the cluster error rate is calculated as shown in Equation (9). Figure 2: Pattern mining purpose. \[FWER(\delta)=\frac{1}{jr}\sum_{i=1}^{jr}1[p_{\min}^{(i)}\leq\delta] \tag{9}\]  
where \(1\Big{[}p_{min}^{(j)}\leq\delta\Big{]}\) means that if \(p_{min}^{(j)}\leq\delta\) is true, then it is 1, otherwise it is 0. The final \(\delta\) to be found is the \(\Big{\{}p_{min}^{(i)}\Big{\}}_{i=1}^{jr}\) of \(\alpha\) quantile point. Theorem 1: _If there exists \(S_{1}\subseteq S_{2}\) and \(\sigma(S_{1})=\sigma(S_{2})\), then \(\sigma_{1}(S_{1})=\sigma_{1}(S_{2})\), \(\sigma_{0}(S_{1})=\sigma_{0}(S_{2})\) and for each permuted label, \(\sigma_{1}(S_{1})=\sigma_{1}(S_{2})\), \(\sigma_{0}(S_{1})=\sigma_{0}(S_{2})\)._  
Theorem 2: _If \(S_{1}\subseteq S_{2}\) and there exists \(\sigma(S_{1})=\sigma(S_{2})\), then \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\)._  
Proof: Since \(\sigma(S_{1})=\sigma(S_{2})\), the values \((n,n_{1},\sigma(S))\) of the edges in the \(2\times 2\) column table are fixed, so for \(S_{1}\) and \(S_{2}\), the three values \(n\), \(n_{1}\), and \(\sigma(S)\) are equal. Equations (10) and (11) can be obtained from Equation (7). Obviously, Equation (12) can be derived from Equations (10) and (11). By substituting Equation (12) into the Fisher exact test formula, it can be deduced that \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\). \[p^{F}(\sigma_{1}(S_{1})=a|\sigma(S_{1}),n_{1},n)=\binom{n_{1}}{a}\binom{n-n_{ 1}}{\sigma(S_{1})-a}/\binom{n}{\sigma(S_{1})} \tag{10}\]  
\[p^{F}(\sigma_{1}(S_{2})=a|\sigma(S_{2}),n_{1},n)=\binom{n_{1}}{a}\binom{n-n_{ 1}}{\sigma(S_{2})-a}/\binom{n}{\sigma(S_{2})} \tag{11}\]  
\[p^{F}(\sigma_{1}(S_{1})=a|\sigma(S_{1}),n_{1},n)=p^{F}(\sigma_{1}(S_{2})=a| \sigma(S_{2}),n_{1},n) \tag{12}\]  
Theorem 3: _If \(S_{1}\subseteq S_{2}\) and \(\sigma(S_{1})=\sigma(S_{2})\), then only the \(p\)-value of mode \(S_{1}\) needs to be computed._  
Proof: According to Equation (9), it is known that the final estimate of \(FWER(\delta)\) is related to \(p_{min}^{(i)}\) after each permutation and \(p_{min}=\min p_{S}^{F}(b)\). By Theorem 2, we know that if \(S_{1}\subseteq S_{2}\) and there exists \(\sigma(S_{1})=\sigma(S_{2})\), then \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\). If \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\) is the minimum value of the \(p\)-value in this substitution, then \(p_{min}\) picks \(p_{S_{1}}^{F}(b)\) as the same as the result of \(p_{min}\) picking \(p_{S_{2}}^{F}(b)\). Therefore, it is sufficient to compute only the \(p\)-value \(p_{S_{2}}^{F}(b)\) of the mode \(S_{1}\), without computing the \(p\)-value of the mode \(S_{1}\). If \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\) is not the minimum value of \(p\)-value in this replacement, since \(p_{S_{1}}^{F}(b)=p_{S_{2}}^{F}(b)\), then \(p_{min}\) and \(p_{S_{1}}^{F}(b)\) are the same as the result of comparing \(p_{S_{2}}^{F}(b)\), so it is sufficient to perform the calculation only once.