Differential Message Importance Measure: A New Approach to the Required Sampling Number in Big Data Structure Characterization

Shanyun Liu, Rui She, Pingyi Fan

Abstract

Data collection is a fundamental problem in the scenario of big data, where the size of sampling sets plays a very important role, especially in the characterization of data structure. This paper considers the information collection process by taking message importance into account, and gives a distribution-free criterion to determine how many samples are required in big data structure characterization. Similar to differential entropy, we define differential message importance measure (DMIM) as a measure of message importance for continuous random variable. The DMIM for many common densities is discussed, and high-precision approximate values for normal distribution are given. Moreover, it is proved that the change of DMIM can describe the gap between the distribution of a set of sample values and a theoretical distribution. In fact, the deviation of DMIM is equivalent to Kolmogorov-Smirnov statistic, but it offers a new way to characterize the distribution goodness-of-fit. Numerical results show some basic properties of DMIM and the accuracy of the proposed approximate values. Furthermore, it is also obtained that the empirical distribution approaches the real distribution with decreasing of the DMIM deviation, which contributes to the selection of suitable sampling points in actual system.

Introduction

In the era of big data, processing entire datasets is often computationally prohibitive. Consequently, researchers rely on sampling to characterize underlying data structures. This introduces a critical trade-off: excessive sampling wastes resources, while insufficient sampling fails to capture the true distribution, particularly rare but significant events. Traditional metrics like Shannon entropy or Kullback-Leibler divergence often fail to intuitively describe the information collection process in contexts like intrusion detection, where small-probability events are of paramount importance. This paper introduces the Differential Message Importance Measure (DMIM) to address these challenges.

The Differential Message Importance Measure (DMIM)

The core contribution of this work is the definition of DMIM for continuous variables. Unlike Shannon entropy, which utilizes a logarithmic weighting ($-\int f \log f$), DMIM employs an exponential weight: $$l(X) = \int_S f(x)e^{-f(x)} dx$$ This mathematical structure ensures that events with small probabilities are assigned higher importance. The authors demonstrate that DMIM can be expressed as an infinite series of Rényi Entropies and is bounded between 0 and 1.

DMIM l(X) as a function of variance for various common probability distributions.

As shown in the figure above, DMIM exhibits a consistent behavior across various standard probability distributions, including Normal, Uniform, Exponential, and Gamma distributions. As the variance increases, the "relative importance" captured by DMIM levels off, reflecting the diminishing marginal utility of additional data points in characterizing the structure.

Determining the Required Sample Size

A key finding of this research is the derivation of a distribution-free criterion for the required number of samples ($n$). By linking the deviation of DMIM to the Kolmogorov-Smirnov (K-S) statistic, the authors provide a bridge between information theory and classical statistics. They derived a concrete lower bound for the number of samples required to reach a specific accuracy threshold ($\epsilon$): $$n \geq \frac{1}{4\pi\sigma^2 \ln^2(1-\epsilon)}$$

Convergence of DMIM deviation with increasing sample size N for different variance values.

Numerical simulations validate this convergence. As the number of samples $N$ increases, the empirical DMIM deviation $|l(X) - \hat{l}(X)|$ decreases until it reaches a stable threshold. The figure illustrates how the required sampling number $n_0$ varies with the variance $\sigma$ to achieve a target error level (e.g., 0.01).

Conclusion

The DMIM offers a novel and effective framework for determining optimal sampling sizes in big data characterization. By prioritizing rare events and providing a distribution-free sampling criterion, it optimizes resource allocation while maintaining high accuracy in goodness-of-fit. Future work will extend this univariate measure to a joint DMIM for multivariate data structures and explore its performance in non-stationary data streams.

Summary updated

Abstract

Data collection is a fundamental problem in the scenario of big data, where the size of sampling sets plays a very important role, especially in the characterization of data structure. This paper considers the information collection process by taking message importance into account, and gives a distribution-free criterion to determine how many samples are required in big data structure characterization. Similar to differential entropy, we define differential message importance measure (DMIM) as a measure of message importance for continuous random variable. The DMIM for many common densities is discussed, and high-precision approximate values for normal distribution are given. Moreover, it is proved that the change of DMIM can describe the gap between the distribution of a set of sample values and a theoretical distribution. In fact, the deviation of DMIM is equivalent to Kolmogorov-Smirnov statistic, but it offers a new way to characterize the distribution goodness-of-fit. Numerical results show some basic properties of DMIM and the accuracy of the proposed approximate values. Furthermore, it is also obtained that the empirical distribution approaches the real distribution with decreasing of the DMIM deviation, which contributes to the selection of suitable sampling points in actual system.
BibTeX
@inproceedings{liu2018differential,
  author = {Shanyun Liu and Rui She and Pingyi Fan},
  title = {{Differential Message Importance Measure: A New Approach to the Required Sampling Number in Big Data Structure Characterization}},
  booktitle = {IEEE Access},
  year = {2018},
  url = {https://openreview.net/forum?id=apuFAk3T410},
}

Loading related content...

Figure