On Minimal Rule Sets for Almost All Binary Information Systems

• Autorzy: Moshkov M.Ju. , Skowron A. , Suraj Z.
• Języki publikacji: EN

Abstrakty

EN

The minimal rules for information systems are often used for inducing data models by methods in which the optimization of models is based on the minimal length principle. We show that almost all information systems from a certain large class of information systems have relatively short minimal rules. However, the number of such rules is not polynomial in the number of attributes and the number of objects. This class consists of all binary information systems with the number of objects polynomial in the number of attributes. Hence, for efficient inducing data models some filtration techniques in rule generation are necessary. In our further study we would like to extend our results for arbitrary information systems.

Słowa kluczowe

EN

information systems; minimal rules; irreducible inconsistent systems of equations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 1-3
• Strony: 247--258
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Moshkov M.Ju.

autor

Skowron A.

autor

Suraj Z.

• Institute of Mathematics, Warsaw University ul. Banacha 2 02-097 Warsaw, Poland,

Bibliografia

• [1] Barwise, J., Seligman, J.: Information Flow: The Logic of Distributed Systems, Cambridge University Press, 1997.
• [2] Moshkov, M., Skowron, A., Suraj, Z.: On testing membership to maximal consistent extensions of information systems, In: Greco, S., Hata, Y., Hirano, S., Inuiguchi, M., Miyamoto, S., Nguyen, H.S., Słowi´nski, R. (Eds.), Proceedings of the Fifth International Conference on Rough Sets and Current Trends in Computing, RSCTC 2006, Kobe, Japan, November 6-8, 2006, LNAI 4259, Springer, Berlin, 2006, 85-90.
• [3] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [4] Pawlak, Z.: Concurrent versus sequential - the rough sets perspective, Bulletin of the EATCS, 48, 1992, 178-190.
• [5] Pawlak, Z., Skowron, A.: Rudiments of rough sets, Information Sciences, 177(1), 2007, 2-27.
• [6] Pawlak, Z., Skowron, A.: Rough sets: Some extensions, Information Sciences, 177(1), 2007, 28-40.
• [7] Pawlak, Z., Skowron, A.: Rough sets and Boolean reasoning, Information Sciences, 177(1), 2007, 41-73.
• [8] Peters, J. F.: Classification of objects by means of features, In: Fogel, D., Greenwood, G., Cholewo, T. (Eds.), Proceedings of the 2007 IEEE Symposium Series on Foundations of Computational Intelligence, IEEE SSCI 2007, Honolulu, Hawaii, 2007, 1-8.
• [9] Rissanen, J.: Modeling by shortest data description, Automatica, 14, 1978, 465-471.
• [10] Rissanen, J.: Minimum-description-length principle, in: Encyclopedia of Statistical Sciences (S. Kotz, N. Johnson, Eds.), John Wiley & Sons, New York, NY, 1985, 523-527.
• [11] Rząsa,W., Suraj, Z.: A newmethod for determining of extensions and restrictions of information systems, In: Alpigini, J.J., Peters, J.F., Skowron, A., Zhong, N. (Eds.), Proceedings of the Third International Conference on Rough Sets and Current Trends in Computing, RSCTC'2002, Malvern, PA, October 14-16, 2002, LNAI 2475, Springer, Berlin, 2002, 197-204.
• [12] Skowron, A., Suraj, Z.: Rough sets and concurrency, Bulletin of the Polish Academy of Sciences, 41(3), 1993, 237-254.
• [13] Suraj, Z.: Rough set methods for the synthesis and analysis of concurrent processes, in: Rough Set Methods and Applications (L. Polkowski, S. Tsumoto, T.Y. Lin, Eds.), Studies in Fuzziness and Soft Computing 56, Physica-Verlag, 2000, 379-488.
• [14] Suraj, Z.: Some remarks on extensions and restrictions of information systems, In: Ziarko, W., Yao, Y.Y. (Eds.) Proceedings of the 2nd International Conference on Rough Sets and Current Trends in Computing, RSCTC'2000, Banff, Canada, October 16-19, 2000, LNAI 2005, Springer, Berlin, 2001, 204-211.
• [15] Suraj, Z., Pancerz, K.: A new method for computing partially consistent extensions of information systems: A rough set approach, In: Bouchon-Meunier, B., Yager, R.R. (Eds.), Proceedings of the International Conference on Information Processing and Management under Uncertainty in Knowledge-Based Systems, IPMU 2006, Paris, France, July 2-7, 2006, no. 3, Paris: Editions E.D.K., 2006, 2618-2625.