Published in Volume XXXIV, Issue 1, 2024, pages 67-87, doi: 10.47743/SACS.2024.1.67
Authors: D. Simovici
Abstract
We introduce an axiomatization of entropy that generates, as special cases, novel entropy types. These entropies generalize Shannon’s entropy and allow the introduction of entropy for partitions of sets of objects located in metric spaces, and for partitions of sets of vertices in undirected graphs. Corresponding metrics on the sets of partitions are introduced. Also, we hint to applications of these metrics for evaluation of clustering quality.
References
[1] Shai Ben-David, Dávid Pál, and Hans Ulrich Simon. Stability of k-means clustering. In Nader H. Bshouty and Claudio Gentile, editors, Learning Theory, 20th Annual Conference on Learning Theory, COLT 2007, volume 4539 of Lecture Notes in Computer Science, pages 20–34. Springer, 2007. doi:10.1007/978-3-540-72927-3\_4.
[2] Shai Ben-David, Ulrike von Luxburg, and Dávid Pál. A sober look at clustering stability. In Gábor Lugosi and Hans Ulrich Simon, editors, Learning Theory, 19th Annual Conference on Learning Theory, COLT 2006, volume 4005 of Lecture Notes in Computer Science, pages 5–19. Springer, 2006. doi:10.1007/11776420\_4.
[3] J. Bhasker and Tariq Samad. The clique-partitioning problem. Computers & Mathematics with Applications, 22(6):1–11, 1991. doi:10.1016/0898-1221(91)90001-K.
[4] Garrett Birkhoff. Lattice Theory, volume XXV of American Mathematical Society Colloquim Publications. Providence, RI, 3rd edition, 1973.
[5] Ramón López de Mántaras. A distance-based attribute selection measure for decision tree induction. Machine Learning, 6:81–92, 1991. doi:10.1023/A:1022694001379.
[6] Dmitry Konstantinovich Faddeev. On the notion of entropy of finite probability distributions (in russian). Uspekhi Matematicheskikh Nauk, 11:227–231, 1956.
[7] Jan Havrda and Frantis̆ek Charvàt. Quantification methods of classification processes: Concepts of structural α-entropy. Kybernetica, 3(1):30–35, 1967.
[8] Roman S. Ingarden and Kazimierz Urbanik. Information without probability. Colloquium Mathematicum, 9(1):131–150, 1962.
[9] Szymon Jaroszewicz and Dan A. Simovici. On axiomatization of conditional entropy of functions between finite sets. In 29th IEEE International Symposium on Multiple-Valued Logic, ISMVL 1999, pages 24–28. IEEE Computer Society, 1999. doi:10.1109/ISMVL.1999.779690.
[10] Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972. doi:10.1007/978-1-4684-2001-2\_9.
[11] Aleksandr Yakovlevich Khinchin. Mathematical Foundations of Information Theory. Dover, New York, 1957.
[12] Tianmou Liu, Han Yu, and Rachael Hageman Blair. Stability estimation for unsupervised clustering: A review. Wiley Interdisciplinary Reviews: Computational Statistics, 14(6):e1575, 2022. doi:10.1002/wics.1575.
[13] Ulrike Von Luxburg. Clustering stability: An overview. Foundations and Trends in Machine Learning, 2(3):235–274, 2010. doi:10.1561/2200000008.
[14] Alfréd Rényi. On the dimension and entropy of probability distributions. Acta Mathematica Academiae Scientiarum Hungarica, 10:193–215, 1959. doi:10.1007/BF02063299.
[15] Frank Ruskey and Jennifer Woodcock. The Rand and block distances of pairs of set partitions. In Costas S. Iliopoulos and William F. Smyth, editors, 22nd International Workshop on Combinatorial Algorithms, IWOCA 2011, volume 7056 of Lecture Notes in Computer Science, pages 287–299. Springer, 2011. doi:10.1007/978-3-642-25011-8\_23.
[16] Claude E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27(3):379–423, 1948. doi:10.1002/J.1538-7305.1948.TB01338.X.
[17] Claude E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27(4):623–656, 1948. doi:10.1002/J.1538-7305.1948.TB00917.X.
[18] Dan A. Simovici. Clustering – Theoretical and Practical Aspects. World-Scientific, Singapore, 2021.
[19] Dan A. Simovici and Chabane Djeraba. Mathematical Tools for Data Mining – Set Theory, Partial Orders, Combinatorics. Advanced Information and Knowledge Processing. Springer, 2nd edition, 2014. doi:10.1007/978-1-4471-6407-4.
[20] Dan A. Simovici and Szymon Jaroszewicz. An axiomatization of partition entropy. IEEE Transactions on Information Theory, 48(7):2138–2142, 2002. doi:10.1109/TIT.2002.1013159.
[21] Dan A. Simovici and Joshua Yee. Inertial entropy and external validation of clusterings. under review, June 2024.
[22] Constantino Tsallis. Possible generalization of Boltzmann-Gibbs statistics. Journal of Statistical Physics, 52:479–487, 1988. doi:10.1007/BF01016429.
[23] Kenjiro Yanagi, Shigeru Furuichi, and Ken Kuriyama. Fundamental properties of Tsallis relative entropy. Journal of Mathematical Physics, 45(12):4868–4877, 2004. doi:10.1063/1.1805729.
[24] Zoltán Daróczy. Generalized information functions. Information and Control, 16(1):36–51, 1970. doi:10.1016/S0019-9958(70)80040-7.
Bibtex
@article{sacscuza:simovici2024me,
title={Monotonic Entropies},
author={D. Simovici},
journal={Scientific Annals of Computer Science},
volume={34},
number={1},
organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
year={2024},
pages={67-87},
publisher={Alexandru Ioan Cuza University Press, Ia\c si},
doi={10.7561/SACS.2024.1.67}
}