Random sets
| Hung T. Nguyen (2008), Scholarpedia, 3(7):3383. | doi:10.4249/scholarpedia.3383 | revision #137654 [link to/cite this article] |
Random sets are random elements taking values as subsets of some space, serve as general mathematical models for set-valued observations and irregular geometrical patterns, and generate the traditional concept of ordinary random points/vectors. Random sets appeared in statistical sampling designs (e.g. Hajek 1981) and in stochastic geometry (Kendall 1974), as well as in statistics (e.g. Robbins 1944). The first systematic treatment of random (closed) sets as bona fide random elements on Hausdorff, locally compact and second countable topological spaces (HLCS) is Matheron 1975. The theory is investigated much further by Molchanov 2006. An unified approach covering the discrete case as well as extensions to random fuzzy sets, using canonical Lawson topology on continuous lattices, is in Nguyen and Tran, 2007.
Contents |
Historical background
Sets obtained at random appeared in a variety of contexts, such as sampling designs in applied statistics, stochastic geometry. Confident regions in statistical inference are random sets and some research are focusing on obtaining smallest volumes of such random sets. These are random variables associated with random sets. The work of Robbins (1944) focused only on these associated random variables rather than on the concept of random set itself. Motivated by problems in morphology, Matheron (1975) defined rigorously the concept of random closed sets, in a HLCS space, using the so-called hit-or-miss topology. Matheron's fundamental work open the door for applications and extensions.
Why random sets?
Besides sampling designs, confident regions, stochastic geometry and morphological problems, random sets appear in general as set-valued observed processes. These include (i) nonparametric estimation of probability density functions (Polonik 1995) (ii) image analysis (Goutsias 1997) (iii) modeling of cancer tumor growth (Cressie and Laslett 1987) (iv) statistics with coarse data (Heitjan and Rubin 1991) (v) uncertainty modeling (Nguyen 1978).
Essentially, the theory of random sets complements to the existing theories of random vectors (multivariate statistical analysis) and of random functions e.g. for Brownian motion and jump processes. It serves mainly as a rigorous machinery for modeling observed phenomena which are sets rather than precise points. Specifically, it is a theory of set-valued stochastic processes. As coarse data represent a case of imprecise observation, the concept of random sets can be extended to random fuzzy sets to model perception-based information in social systems, as coarsening schemes. This is useful for artificial intelligence problems such as intelligent control and decisions.
Associated uncertainty measures
It was pointed out (Nguyen 1978) that the mathematical theory of evidence (also called belief functions, Shafer 1976) can be put rigorously in terms of random sets. Also, Zadeh's theory of possibility, based upon fuzzy sets theory (Zadeh 1978) is closely related to random sets (see Nguyen 2006). Random sets serve as a bridge between several useful measures of uncertainty in decision analysis.
The most significant feature in Matheron's theory of random closed sets is the counterpart of Lebesgue-Stieltjes theorem, namely the establishment of a bijection between probability measures of random closed sets and Choquet capacity functionals (called the Choquet theorem) which generate the concept of distribution functions of ordinary random points/vectors into the Euclidean space or more general into a metric space. Not only this makes applications possible, but the concept of Choquet capacities surfaces as a useful measure of uncertainty which is not necessarily additive.
Mathematical modeling
Matheron considered a plausible topology on the space of closed subsets of a HLCS space X, namely the hit-or-miss topology, in order to use its associated Borel σ-field to define random sets as random elements. In image analysis, random set modeling offers an alternative to random field modeling. This is the case of discrete random sets. In the foundational work of Goutsias (1997), an ad-hoc σ-field is considered to define discrete random sets. On the other hand, motivated by linguistic information processing in artificial intelligence, researchers try to extend Matheron's theory to the case of random fuzzy sets (e.g. Li et al. 2002) in which they use the technique of α-cuts, leading only to a restrictive setting.
Recall that, for random variables or more generally for random elements, we do have a unified approach with regard to the selection of a canonical σ-field on the range spaces (from finite to infinitely countable to continuous ranges). The situation of random sets is not that nice! Perhaps the nature of "sets" versus "points" makes some difference?
Fortunately, we do have a happy ending, thanks to the theory of continuous lattices! While the σ-field for finite random sets is trivial as the power set of the underlying space, the range spaces for infinitely countable random sets (i.e. random elements taking values subsets of an infinitely countable space, such as Z²) are uncountable, and it is not clear what could be a canonical topology on it. Now, if we view set inclusion as a partial order on it, it can be checked that, with its associated "way below" relation, it is a continuous lattice (see Gierz et al. 1980 for background on continuous lattices). The same is true for random closed sets on HLCS spaces with the reverse set inclusion. Moreover, for random fuzzy sets where the base space is a HLCS space, and membership functions are upper semicontinuous(usc), to generalize closed sets, they form a continuous lattice with reverse pointwise partial order between functions. In such a setting, there exists a canonical topology, namely the Lawson topology which is compact, Hausdorff and second countable (and hence metrizable) whose associated Borel σ-field serves as a canonical σ-field for random sets in general. Note that Matheron's hit-or-miss topology coincides with the Lawson's topology on HLCS spaces. See Nguyen and Tran (2007).
References
- N. Cressie and G.M. Laslett (1987) Random set theory and problems of modeling. SIAM Review (29) : 557-574. doi:10.1137/1029111.
- G. Gierz, K.M. Hofman, K. Keimel, J.D. Lawson, M. Mislove and D.S. Scott (1980) A Compendium of Continuous Lattices. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-67678-9.
- J.Goutsias (1997) Morphological analysis of random sets: An introduction. In Random Sets : Theory and Applications (J. Goutsias, R. Mahler and H.T. Nguyen, editors) : 3-26. Springer-Verlag, New York. doi:10.1007/978-1-4612-1942-2_1.
- K.Hajek (1981) Sampling from a Finite Population. Marcel Dekker, New York.
- D.F. Heitjan and D.B. Rubin (1991) Ignorability and coarse data. Annals of Statistics (19): 2244-2253. doi:10.1214/aos/1176348396.
- D.G. Kendall (1974) Foundations of a theory of random sets. In Stochastic Geometry ( E.F. Harding and D.G. Kendall, editors) : 322-376. J. Wiley, New York.
- S Li, Y. Ogura and V. Kreinovich (2002) Limit Theorems and Applications of Set-Valued and Fuzzy Set-Valued Random Variables. Kluwer Academic, Boston. doi:10.1007/978-94-015-9932-0.
- G. Matheron (1975). Random Sets and Integral Geometry. J.Wiley, New York.
- H.T. Nguyen (1978). On random sets and belief functions. Journal of Mathematical Analysis and Applications (65) : 531-542. doi:10.1016/0022-247X(78)90161-0.
- H.T. Nguyen (2006). An Introduction to Random Sets. Chapman and Hall/CRC Press, Boca Raton, Florida.
- H.T. Nguyen and H. Tran (2007) On a continuous lattice approach to modeling of coarse data in systems analysis. Journal of Uncertain Systems 1 (1) : 62-73.
- W. Polonik (1995) Density estimation under qualitative assumptions in higher dimensions. Journal of Multivariate Analysis (55) : 61-81. doi:10.1006/jmva.1995.1067.
- G. Shafer (1976). A Mathematical Theory of Evidence. Princeton University Press, Princeton.
- L.A. Zadeh (1978) Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems (1) : 3-28. doi:10.1016/0165-0114(78)90029-5.
Internal references
- Lotfi A. Zadeh (2008) Fuzzy logic. Scholarpedia, 3(3):1766. doi:10.4249/scholarpedia.1766.
- Milan Mares (2006) Fuzzy sets. Scholarpedia, 1(10):2031. doi:10.4249/scholarpedia.2031.
- Didier Dubois and Henri Prade (2007) Possibility theory. Scholarpedia, 2(10):2074. doi:10.4249/scholarpedia.2074.
