I have got two databases $X_{S}$ and $X_{T}$ which are having different number of samples but the same size of feature-space. I am wandering which is the most efficient way to calculate the distance of those databases. How can I calculate the distance between their distributions?
Solved – Calculate the distribution distance between two datasets
distancedistributions
Related Solutions
I guess it is not a direct answer, but you can try to simulate the scenario and check the empirical distribution to have a rough idea (R code below).
So it seems that for strings longer than ~ 100 the distribution is symmetric and quite narrow around .53 times the length of the string.
# dependencies
library(ggplot2); theme_set(theme_classic())
library(parallel)
library(RecordLinkage)
# settings
alphabet <- c("A", "C", "G", "T")
Nsim <- 1e3
read_lengths <- seq(60, 500, 20)
# function to create a random string of length "n" using letters of the alphabet "alph"
random_read <- function(n, alph=alphabet) paste(sample(alph, size=n, replace=T), collapse="")
# simulate
res <- mclapply(read_lengths,
function(N) replicate(Nsim, levenshteinDist(random_read(N), random_read(N))),
mc.cores=6)
# arrange results as data.frame
res_df <- data.frame(dist=unlist(res),
length=rep(read_lengths, sapply(res, length)))
# plot densities
ggplot(res_df,
aes(x=dist / length, col=length, group=length)) +
geom_density() +
ggtitle("Distribution of Levenshtein distance / length")
ggplot(res_df,
aes(x=length, y=dist / length, col=length)) +
geom_violin(aes(group=length)) +
geom_smooth(col="black", lwd=1) +
ggtitle("Distribution of Levenshtein distance / length")
As the problem comes down to compare two probability vectors, I guess you could use for instance the Kullback–Leibler divergence or, if you need a symmetrical measure, the Jensen–Shannon divergence.
Hope this help
Related Question
- Solved – Distance measure between two multivariate normal distributions (with differing mean and covariances)
- Solved – Maximum Mean Discrepancy (distance distribution)
- Solved – Kullback-Leibler distance for comparing two distribution from sample points
- Solved – How to compute the correlation between two distance matrices
- Solved – Unit of the mahalalanobis distance between two individuals
Best Answer
If you do know their distributions, you can use the KL-divergence to calculate the distance between their distributions. The problem is when you do not have any knowledge about their pdf s. You can perhaps have a look at this paper. Good luck