On Fractal Dimension in Information Systems. Toward Exact Sets in Infinite Information Systems

Article type: Research Article

Authors: Polkowski, Lech

Affiliations: Polish–Japanese Institute of Information Technology, Koszykowa 86, 02008 Warsaw Poland

Abstract: The notions of an exact as well as a rough set are well--grounded as basic notions in Rough Set Theory [13]. They are however defined in the setting of a finite information system i.e. an information system having finite numbers of objects as well as attributes. In theoretical studies e.g. of topological properties of rough sets [16], one has to trespass this limitation and to consider information systems with potentially unbound number of attributes. In such setting, the notions of rough and exact sets may be defined in terms of topological operators of interior and closure with respect to an appropriate topology [16] following the ideas from the finite case cf. e.g. [14], where it is noticed that in the finite case rough-set-theoretic operators of lower and upper approximation are identical with the interior, respectively, closure operators in topology induced by equivalence classes of the indiscernibility relation. Extensions of finite information systems are also desirable from application point of view in the area of Knowledge Discovery and Data Mining, when demands of e.g. mass collaboration and/or huge experimental data e.g. in genomic studies [2,17], call for need of working with large data tables so the sound theoretical generalization of these cases is an information system with the number of attributes not bound in advance by a fixed integer i.e. an information system with countably but infinitely many attributes. In large information systems, a need arises for qualitative measures of complexity of concepts involved free of parameters, cf. e.g. applications for the Vapnik–Czervonenkis dimension [1].We study here in the theoretical setting of infinite information system a proposal to apply fractal dimensions suitably modified as measures of concept complexity. In the finite case, exact sets form a field of sets E cf. e.g. [14]. Clearly, from topological point of view E is a compact metric space under the discrete metric on equivalence classes of the indiscernibility relation. The question poses itself, whether it is possible to define exact sets in the setting of an infinite information system in such a way that the space of exact sets E_∞ will be a compact metric space and a field of sets as well. We study in this note a way to define exact and rough sets which stems from the orthodox notion of an approximation. We apply to this end the notion of a fractal dimension adopted to the case of an information system i.e. rid of the geometric content and underlying metric characterization. We introduce notions of a lower and an upper fractal dimensions and we define exact sets as those sets for which the two dimensions coincide; otherwise, we declare the set as rough. It turns out that exact sets defined in this way extend the classical notion of an exact set and as in the classical finite case they form a field of sets. From topological point of view, exact sets form a compact metric space under the metric D defined originally for topological rough sets [16] and extended here over topological exact sets as well.

Keywords: the Minkowski dimension, information systems, rough sets, A-dimension

Journal: Fundamenta Informaticae, vol. 50, no. 3-4, pp. 305-314, 2002