Abstract
The information entropy, as a measurement of the average amount of information contained in an information system, is used in the classification of objects and the analysis of information systems. The information entropy of a partition is non-increasing when the partition is refined, and is related to rough sets by Wong and Ziarko. The partitions and information entropy have some graph-theoretical properties. Given a non-empty universe U, all the partitions G on U are taken as nodes, and a relation V between partitions are defined and taken as edges. The graph obtained is denoted by (G,V), which represents the connections between partitions on U. According to the values of the information entropy of partitions, a directed graph \((G,\overrightarrow{V})\) is defined on (G,V). It will be proved that there is a set of partitions with the minimal entropy; and a set of partitions with the maximal entropy; and the entropy is non-decreasing on any directed pathes in \((G,\overrightarrow{V})\) from a partition with the minimal entropy to one of the partitions with the maximal entropy. Hence, in \((G,\overrightarrow{V})\) the information entropy of partitions is represented in a clearly structured way.
The work is supported by the National NSF of China (60373042, 60273019 and 60073017), the National 973 Project of China (G1999032701), Ministry of Science and Technology (2001CCA03000). The second author was partially supported by the Yunnan Provincial NSF grant 2000F0049M and 2001F0006Z.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beaubouef, T., Petry, F.E., Arora, G.: Information-theoretic measures of uncertainty for rough sets and rough relational databases. J. Information Sciences 109, 185–195 (1998)
Düntsch, I., Gediga, G.: Uncertainty measures of rough set prediction. Artificial Intelligence 106, 109–137 (1998)
Hu, X., Lin, T.Y., Han, J.: A new rough sets model based on database systems. Fundamenta Informaticae 59, 135–152 (2004)
Pawlak, Z.: Rough sets - theoretical aspects of reasoning about data. Kluwer Academic Publishers, Dordrecht (1991)
Shannon, C.E.: A mathematical theory of communication. The Bell system Technical Journal 27, 623–656 (1948)
Pawlak, Z.: Rough sets - theoretical aspects of reasoning about data. Kluwer Academic Publishers, Dordrecht (1991)
Sui, Y., Wang, J., Jiang, Y.: Formalization of the conditional entropy in rough set theory. J. of Software 12, 23–25 (2001)
Wong, S.K.M., Ziarko, W.: On optimal rules in decision tables. Bull. of the Polish Academy of Sciences, Math. 33, 693–696 (1985)
Yao, Y.Y.: Probabilistic approaches to rough sets. Expert Systems 20, 287–297 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cao, C., Sui, Y., Xia, Y. (2005). The Graph-Theoretical Properties of Partitions and Information Entropy. In: Ślęzak, D., Wang, G., Szczuka, M., Düntsch, I., Yao, Y. (eds) Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. RSFDGrC 2005. Lecture Notes in Computer Science(), vol 3641. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11548669_58
Download citation
DOI: https://doi.org/10.1007/11548669_58
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28653-0
Online ISBN: 978-3-540-31825-5
eBook Packages: Computer ScienceComputer Science (R0)