Kernel measure of multi-sample dissimilarity (KMD) measures the dissimilarity between multiple samples, based on the observations from them. It converges to the population quantity (depending on the kernel) which is between 0 and 1. A small value indicates the multiple samples are from the same distribution, and a large value indicates the corresponding distributions are different. The population quantity is 0 if and only if all distributions are the same, and 1 if and only if all distributions are mutually singular.
This package implements the computation of the sample KMD between several distributions based on independent observations from them, using K-nearest neighbor graphs and minimum spanning trees. It also implements the tests based on KMD for H0: the M distributions are equal against H1: not all the distributions are equal. Both permutation test and asymptotic test are available. The tests are consistent against all alternatives where at least two samples have different distributions.
This package depends on R (>= 4.0.0). You can install the package
KMD by (the package devtools needs to be installed
first):
devtools::install_github("zh2395/KMD")Alternatively, download the entire folder, and execute the following command in R:
install.packages("~/Downloads/KMD-main", repos=NULL, type="source")You can uninstall the package by:
remove.packages("KMD")Here we briefly introduce the functions in this package. See the documentation (help page) of the R package for more details.
KMD implements the KMD estimator based on geometric
graphs. The inputs are: X: the data matrix (n by dx) or the
distance/similarity matrix (n by n); Y: a vector of length
n, indicating the labels (from 1 to M) of the data; M: the
number of possible labels; Knn: the number of nearest
neighbors to use, or “MST”. The recommended default value for
Knn is 1; Kernel: an M by M kernel matrix with
row i and column j being the kernel value k(i, j); or “discrete” which
indicates using the discrete kernel.
library(KMD)
n = 60
d = 2
set.seed(1)
X1 = matrix(runif(n*d/2),ncol = d)
X2 = matrix(runif(n*d/2),ncol = d)
X2[,1] = X2[,1] + 1
X = rbind(X1,X2)
Y = c(rep(1,n/2),rep(2,n/2))
print(KMD(X, Y, M = 2, Knn = 1, Kernel = "discrete"))
# 0.9344444. X1 and X2 are mutually singular, so the theoretical KMD is 1.
print(KMD(X, Y, M = 2, Knn = 1, Kernel = base::diag(c(1,1))))
# 0.9344444. This is essentially the same as specifying the discrete kernel above.
print(KMD(X, Y, M = 2, Knn = 2, Kernel = "discrete"))
print(KMD(X, Y, M = 2, Knn = "MST", Kernel = "discrete"))
# 0.9508333, 0.9399074. One can also use other geometric graphs (2-NN graph and MST here) to estimate the same theoretical quantity.KMD_test implements the tests based on KMD. Both
permutation test and asymptotic test are available. The tests are
consistent against all alternatives where at least two samples have
different distributions. A small KMD value indicates the multiple
samples are from the same distribution, and a large KMD value indicates
the corresponding distributions are different. The null hypothesis that
all samples are from the same distribution is rejected for large KMD
value. The permutation test returns the p-value given by (sum(KMD_i
>= KMD_0) + 1)/(B + 1), where KMD_i is the KMD computed after a
random permutation on the Y labels, and B is the total number of
permutations that have been performed. The asymptotic test first
normalizes the KMD by the square root of the permutation variance, and
then returns the p-value given by: P(N(0,1) > normalized KMD).
The inputs of KMD_test are: X: the data
matrix (n by dx) or the distance/similarity matrix (n by n);
Y: a vector of length n, indicating the labels (from 1 to
M) of the data; M: the number of possible labels;
Knn: the number of nearest neighbors to use, or “MST”. The
recommended default value for Knn is 0.1n;
Kernel: an M by M kernel matrix with row i and column j
being the kernel value k(i, j); or “discrete” which indicates using the
discrete kernel; Permutation: TRUE or FALSE; whether to
perform permutation test or the asymptotic test; B: the
number of permutations to perform, only used for permutation test.
d = 2
set.seed(1)
X1 = matrix(rnorm(100*d), nrow = 100, ncol = d)
X2 = matrix(rnorm(100*d,sd=sqrt(1.5)), nrow = 100, ncol = d)
X3 = matrix(rnorm(100*d,sd=sqrt(2)), nrow = 100, ncol = d)
X = rbind(X1,X2,X3)
Y = c(rep(1,100),rep(2,100),rep(3,100))
print(KMD_test(X, Y, M = 3, Knn = 1, Kernel = "discrete"))
# A small p-value since the three distributions are not the same.
print(KMD_test(X, Y, M = 3, Knn = 1, Kernel = "discrete", Permutation = FALSE))
# p-value of the asymptotic test is similar to that of the permutation test
print(KMD_test(X, Y, M = 3, Knn = 1, Kernel = diag(c(10,1,1))))
# p-value is improved by using a different kernel
print(KMD_test(X, Y, M = 3, Knn = 30, Kernel = "discrete"))
# The suggested choice Knn = 0.1n yields a very small p-value.
print(KMD_test(X, Y, M = 3, Knn = "MST", Kernel = "discrete"))
# One can also use the MST.
print(KMD_test(X, Y, M = 3, Knn = 2, Kernel = "discrete"))
# MST has similar performance as 2-NN, which is between 1-NN and 30-NN
# Check null distribution of the z values
ni = 100
n = 3*ni
d = 2
Null_KMD = function(id){
set.seed(id)
X = matrix(rnorm(n*d), nrow = n, ncol = d)
Y = c(rep(1,ni),rep(2,ni),rep(3,ni))
return(KMD_test(X, Y, M = 3, Knn = "MST", Kernel = "discrete", Permutation = FALSE)[1,1])
}
hist(sapply(1:1000, Null_KMD), breaks = c(-Inf,seq(-5,5,length=50),Inf), freq = FALSE,
xlim = c(-4,4), ylim = c(0,0.5), main = expression(paste(n[i]," = 100")),
xlab = expression(paste("normalized ",hat(eta))))
lines(seq(-5,5,length=1000),dnorm(seq(-5,5,length=1000)),col="red")
# The histogram of the normalized KMD is close to that of a standard normal distribution.