Nonparametric High-Dimensional Multi-Sample Tests based on Graph Theory
针对高维数据同质性检验，提出基于最短哈密顿路径的边计数组合统计量，通过置换检验和渐近理论分析其性质，模拟和真实数据表明方法优于现有方法。
High-dimensional data pose unique challenges for data processing in an era of ever-increasing amounts of data availability. Graph theory can provide a structure of high-dimensional data. We introduce two key properties desirable for graphs in testing homogeneity. Roughly speaking, these properties may be described as: unboundedness of edge counts under the same distribution and boundedness of edge counts under different distributions. It turns out that the minimum spanning tree violates these properties but the shortest Hamiltonian path posses them. Based on the shortest Hamiltonian path, we propose two combinations of edge counts in multiple samples to test for homogeneity. We give the permutation null distributions of proposed statistics when sample sizes go to infinity. The power is analyzed by assuming both sample sizes and dimensionality tend to infinity. Simulations show that our new tests behave very well overall in comparison with various competitors. Real data analysis of tumors and images further convince the value of our proposed tests. Software implementing the test is available in the R package GRelevance. Supplemental materials for this article are available online.