# Data Quality Measures and Efficient Evaluation Algorithms for Large-Scale High-Dimensional Data
## 3 Methods
### Methods for Efficient Computation
#### 3.3.2 Bootstrapping
\begin{table}
\begin{tabular}{c c c} \hline \hline  & _Exact_ & _Approx_ \\ \hline MNIST & 0.1550 & 0.0535 \\ CIFAR10 & 0.0331 & 0.0173 \\ notMNIST & 0.2123 & 0.0625 \\ Linnaeus & 0.0250 & 0.0118 \\ STL10 & 0.0695 & 0.0207 \\ SVHN & 0.0004 & 0.0010 \\ ImageNet-1 & 0.0062 & 0.0131 \\ ImageNet-2 & 0.0293 & 0.0145 \\ ImageNet-3 & 0.0191 & 0.0125 \\ ImageNet-4 & 0.0092 & 0.0076 \\ \hline Pearson & & 0.9847 \\ Spearman & & 0.9152 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Comparison of Exact and Approx values and their correlations. Pearson and Spearman are the Pearson and Spearman rank correlation between the Exact and Approx. \begin{table}
\begin{tabular}{c c} \hline \hline
**Measure** & \(M_{var_{1}}\)\(\times\)**1000** \\ \hline Airplane & 0.1557 \\ Automobile & 0.2069 \\ Bird & 0.1394 \\ Cat & 0.1803 \\ Deer & **0.0123** \\ Dog & 0.1830 \\ Frog & 0.1344 \\ Horse & 0.1775 \\ Ship & 0.1472 \\ Truck & 0.1997 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Our in-class variability measure for the degraded-CIFAR10 dataset. A class with a smaller value than other classes has a lower variability. Figure 4: Ten similar selected images in the deer class on degraded-CIFAR10. Images with high similarity were selected using cosine similarity. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Data** & **Quality Measure** & \(F1\) & \(N1\) & \(N3\) & \(CSG\) & _Test Accuracy (\%)_ \\ \hline Original CIFAR10 & 0.2213 & 0.7909 & 0.7065 & 0.7030 & 42.84 \\ Degraded-CIFAR10 & 0.2698 & 0.7035 & 0.6096 & 0.6049 & 41.28 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Quality measures on the degraded-CIFAR10 dataset. The existing quality measures \(F1\), \(N1\), \(N3\), and \(CSG\) only capture the class separability and fail to capture the degradation. Lower values of \(N1\), \(N3\), and \(CSG\) represent higher class separability, whereas lower values of \(F1\) represent lower class separability. The test accuracy is from MLP-2 trained with original and degraded-CIFAR10, respectively, and tested on the original CIFAR10 test data. probability of properly classifying the car will be low. This example indicates that in-class variability plays an important role in data quality evaluation. ### Quality Ranking Using \(M_{Sep}\) and \(M_{Var}\)

As we mentioned before, quality measures \(M_{sep}\) and \(M_{var}\) can be compared among different datasets. The class separability \(M_{sep}\) represents the relative difficulty of linear classification, and the overall in-class variability \(M_{var}\) represents the average variability of data points in classes. Figure 5 shows a data quality comparison plot of datasets in our experiments. The direction towards the lower-left corner indicates lower class separability and lower in-class variability, and the upper-right direction is for higher class separability and higher in-class variability. According to the plot, the MNIST and the notMNIST dataset show very high linear separability compared to other datasets, indicating that their classification might be easier than the other datasets. The SVHN dataset is at the lower-left corner, indicating low linear separability and possible redundancy issues (this could be just the reflection of the fact that many SVHN images contain changing digits but the same backgrounds). The four ImageNet datasets, Linnaeus, CIFAR10 and STL10 have similar class separability and in-class variability values. This appears to be understandable considering their similar data construction designed for object recognition. ## 5 Conclusions

In this paper, we proposed data quality measures \(M_{sep}\), \(M_{var}\) and \(M_{var_{i}}\), which can be applied efficiently on large-scale high-dimensional datasets. Our measures are estimated using random projection and bootstrapping and therefore can be applied efficiently on large-scale high-dimensional data. We showed that \(M_{sep}\) can be used as a good alternative to the existing data quality measures capturing class separability, while reducing their computational overhead significantly.