# Data Quality Measures and Efficient Evaluation Algorithms for Large-Scale High-Dimensional Data
## 3 Methods
### Methods for Efficient Computation
#### 3.3.2 Bootstrapping

Table 2: The absolute Pearson and Spearman rank correlation between the quality measures and the accuracy of three classifiers on the ten image datasets (MNIST, CIFAR10, notMNIST, Linnaeus, STL10, SVHN, ImageNet-1, ImageNet-2, ImageNet-3, and ImageNet-4). The computation time of our method \(M_{sep}\) is the fastest. #### 4.2.3 Computation Time

As mentioned above, our quality measure \(M_{sep}\) represents the class separability well, but much faster in computation than \(F1\), \(N1\), \(N3\), and \(CSG\). Here, we show how the computation time changes according to data dimension and sample sizes, in order to show that our suggested data quality measure can be used for many big-data situations. The computation time according to the data dimension is shown in Figure 2 and Table 4. In all dimensions, our measure \(M_{sep}\) was on average 3.8 times faster than \(F1\), 13.1 times faster than \(N1\), 25.9 times faster than \(N3\), and 17.7 times faster than \(CSG\). Since the \(N1\), \(N3\), and \(CSG\) have to calculate the MST and to train a 1 NN classifier and embedding networks, respectively, it is inevitable that they would take a large amount of computation time (see more details in Sections 2.1 and 2.2). On the other hand, since \(M_{sep}\) utilizes random projection and bootstrapping to avoid eigenvalue decomposition problem and to deal with the big-data situations, the computation time of \(M_{sep}\) is shortest in all cases. Figure 3 and Table 5 show how computation time changes for various sample sizes. Our measure \(M_{sep}\) was on average 2.8 times faster than \(F1\), 47.0 times faster than \(N1\), 94.5 times faster than \(N3\), and 41.6 times faster than \(CSG\). \(N1\) and \(N3\) show extremely increasing computation time with respect to the sample size, which is not suitable for large-scale high-dimensional datasets. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Image Size** & **Dimension** & \(F1\) & \(N1\) & \(N3\) & \(CSG\) & \(M_{sep}\) (Ours) & **Speedup** \\ \hline \(16\times 16\times 3\) & 768 & 49 & 246 & 445 & 1963 & 17 & \(\times 2.9\sim 115.5\) \\ \(32\times 32\times 3\) & 3072 & 203 & 947 & 1850 & 2513 & 57 & \(\times 3.6\sim 44.1\) \\ \(48\times 48\times 3\) & 6912 & 492 & 2144 & 4182 & 3132 & 122 & \(\times 4.0\sim 34.3\) \\ \(64\times 64\times 3\) & 12,288 & 1011 & 3810 & 7466 & 5427 & 303 & \(\times 3.3\sim 24.6\) \\ \(80\times 80\times 3\) & 19,200 & 1783 & 5973 & 11,674 & 6838 & 461 & \(\times 3.9\sim 25.3\) \\ \(96\times 96\times 3\) & 27,648 & 2850 & 8652 & 17,346 & 9550 & 700 & \(\times 4.1\sim 24.8\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Data dimension vs. computation time (CIFAR10) in detail (the values in the table represent seconds). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \(M_{sep}\) (Ours) & \(F1\) & \(N1\) & \(N3\) & \(CSG\) \\ \hline \(M_{sep}\) (ours) & 1.0000 & 0.9673 & 0.9322 & 0.9245 & 0.9199 \\ \(F1\) & 0.9673 & 1.000 & 0.8909 & 0.8879 & 0.8806 \\ \(N1\) & 0.9322 & 0.8909 & 1.0000 & 0.9988 & 0.940



All the above results show that our measure \(M_{sep}\) is suitable for the big-data situations and compatible with other well-accepted data quality measures. #### 4.2.4 Comparison to Exact Computation

In Section 3.2, we proposed to use random projections and bootstrapping for fast approximation of the solution of (4), which can be computed exactly as an eigenvalue. Here, we compare the values of \(M_{sep}\) using the proposed approximate computation (denoted by \"Approx\") and the exact computation (denoted by \"Exact\") due to an eigensolver in the Python scipy package. One thing is that, since we use only Gaussian random vectors for projection, it is likely that they may not match the true eigenvectors; therefore, the approximated quantity would differ from the exact value. However, we found that the approximate quantities match well the exact values in their correlation, as indicated in Table 6, and, therefore, can be used for fast comparison of data quality of high-dimensional large-scale datasets.