Scientific Annals of Computer Science

"Alexandru Ioan Cuza" University of Iaşi



On Partition Metric Space, Index Function, and Data Compression

Published in Volume XXVIII, Issue 1, 2018, p. 141–156, doi: 10.7561/SACS.2018.1.141

Authors: D.A. Simovici, R. Sizov

ABSTRACT

We discuss a metric structure on the set of partitions of a finite set induced by the Gini index and two applications of this metric: the identification of determining sets for index functions using techniques that originate in machine learning, and a data compression algorithm.

Keywords: Gini index, Vapnik-Chervonenkis dimension, index function, determining set, compression

Full text (PDF) | BibTeX

References


[1] C. Gini. Sulla Misura della Concentrazione e della Variabilita dei Caratteri. Transactions of the Real Istituto Veneto di Scienze, Lettere ed Arti, LIII:1203, 1914. doi:10.1007/bf02858128.


[2] C. Gini. Measurement of Inequality of Incomes. The Economic Journal, 31(121):124–126, 1921. doi:10.2307/2223319.


[3] T. Sasao. Switching Theory for Logic Synthesis. Kluwer Academic Publishers, 1999. doi:10.1007/978-1-4615-5139-3.


[4] T. Sasao. On the Number of Dependent Variables for Incompletely Specified Multiple-Valued Functions. In Proceedings of the 30th International Symposium on Multiple-Valued Logic, pages 91–97, Los Alamitos, CA, 2000. Computer Society Press. doi:10.1109/ismvl.2000.848605.


[5] T. Sasao. Proceedings of the 35th International Symposium for Multiple-Valued Logic. In Radix Converters: Complexity and Implementation by LUT Cascades, pages 256–263, Los Alamitos, CA, 2005. Computer Society Press. doi:10.1109/ismvl.2005.50.


[6] T. Sasao. A Design Method of Address Generators Using Hash Memories. In International Workshop on Logic and Synthesis, pages 102–109, 2006.


[7] T. Sasao. On the Number of Variables to Represent Sparse Logic Functions. In 17th International Workshop on Logic and Synthesis (IWLS-2008), pages 233–239, Lake Tahoe, California, USA, 2008. IEEE-CS.


[8] T. Sasao. On the Number of Variables to Represent Sparse Logic Functions. In 2008 IEEE/ACM International Conference on Computer Aided Design, pages 45–51, Los Alamitos, CA, 2008. Computer Society Press. doi:10.1109/iccad.2008.4681550.


[9] T. Sasao. A Fast Updatable Implementation of Index Generation Functions Using Multiple IGUs. IEICE Transactions, 100-D(8):1574–1582, 2017. doi:10.1587/transinf.2016lop0001.


[10] T. Sasao. A Linear Decomposition of Index Generation Functions: Optimization Using Autocorrelation Functions. Multiple-Valued Logic and Soft Computing, 28(1):105–127, 2017.


[11] N. Sauer. On the Density of Families of Sets. Journal of Combinatorial Theory (A), 13:145–147, 1972. doi:10.1016/0097-3165(72)90019-2.


[12] J. S. Schlimmer. UCI Machine Learning Repository, 2013.


[13] D. A. Simovici and C. Djeraba. Mathematical Tools for Data Mining – Set Theory, Partial Orders, Combinatorics. Springer-Verlag, London, second edition, 2008.


[14] S. Shelah. A Combinatorial Problem; Stability and Order for Models and Theories in Infinitary Languages. Pacific Journal of Mathematics, 41:247–261, 1972. doi:10.2140/pjm.1972.41.247.


[15] T. Sasao and M. Matsuura. An Implementation of an Address Generator Using Hash Memories. In 10th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools, DSD-2007, pages 69–76, Los Alamitos, CA, 2007. Computer Society Press. doi:10.1109/dsd.2007.4341452.


[16] T. Sasao, T. Nakamura, and M. Matsuura. Representation of Incompletely Specified Index Generation Functions Using Minimal Number of Compound Variables. In 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools, DSD-2009, pages 765–772, Patras, Greece, 2009. Computer Society Press. doi:10.1109/DSD.2009.214.


[17] D. A. Simovici, D. Pletea, and R. Vetro. Information-Theoretical Mining of Determining Sets for Partially Defined Functions. In Proceedings of ISMVL, pages 294–299, Barcelona, 2010. IEEE Computer Society. doi:10.1109/ismvl.2010.61.


© 2006-2019 FII | Contact: annals at info.uaic.ro