Satisfiability of Formulas from the Standpoint of Object Classification: The RST Approach

• Autorzy: Gomolińska A.
• Języki publikacji: EN

Abstrakty

EN

In this article we discuss judgment of satisfiability of formulas of a knowledge representation language as an object classification task. Our viewpoint is that of the rough set theory (RST), and the descriptor language for Pawlak's information systems of a basic kind is taken as the study case. We show how certain analogy-based methods can be employed to judge satisfiability of formulas of that language.

Słowa kluczowe

EN

satisfiability of formulas; valuation; object classification; Pawlak information system; descriptor language; analogy-based reasoning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 85, nr 1-4
• Strony: 139--153
• Opis fizyczny: bibliogr. 71 poz., tab.

Twórcy

autor

Gomolińska A.

• Department of Mathematics University of Białystok, Akademicka 2, 15-267 Białystok, Poland,

Bibliografia

• [1] Aamodt, A., Plaza, E.: Case-based reasoning: Foundational issues, methodological variations, and system approaches, Artificial Intelligence Communications, 7(1), 1994, 39-52.
• [2] Aha, D. W., Kibler, D., Albert, M. K.: Instance-based learning algorithms, Machine Learning, 6, 1991, 37-66.
• [3] Albatineh, A. N., Niewiadomska-Bugaj, M., Mihalko, D.: On similarity indices and correction for chance agreement, J. of Classification, 23, 2006, 301-313.
• [4] Bazan, J. G.: Approximate Methods of Synthesis of Decision Algorithms (in Polish), Ph. D. thesis, Warsaw University, 1998.
• [5] Bazan, J. G.: Discovery of decision rules by matching new objects against data tables, Lecture Notes in Artificial Intelligence, 1424, 1998, 521-528.
• [6] Bazan, J. G., Skowron, A., Swiniarski, R.: Rough sets and vague concept approximation: From sample approximation to adaptive learning, Transactions on Rough Sets V, a journal subline to Lecture Notes in Computer Science, 4100, 2006, 39-63.
• [7] Belnap, N. D.: A useful four-valued logic, in: Modern Uses ofMultiple-valued Logic (J.M. Dunn, G. Epstein, Eds.), Reidel, Dordrecht, 1977, 8-37.
• [8] Bolc, L., Borowik, P.: Many-valued Logics, vol. 1, Springer, Berlin, 1992.
• [9] Cover, T. M., Hart, P. E.: Nearest neighbor pattern classification, IEEE Transactions on Information Theory, 13, 1967, 21-27.
• [10] Duda, R. O., Hart, P. E.: Pattern Classification and Scene Analysis, JohnWiley, New York, 1973.
• [11] Dzeroski, S., Lavrac, N., Eds.: Relational Data Mining, Springer, Berlin, 2001.
• [12] Getoor, L., Taskar, B.: Introduction to Statistical Relational Learning, MIT Press, Cambridge, MA, 2007.
• [13] Gomolińska, A.: A graded meaning of formulas in approximation spaces, Fundamenta Informaticae, 60(1-4), 2004, 159-172.
• [14] Gomolińska, A.: Satisfiability and meaning of formulas and sets of formulas in approximation spaces, Fundamenta Informaticae, 67(1-3), 2005, 77-92.
• [15] Gomolińska, A.: Approximation spaces based on relations of similarity and dissimilarity of objects, Fundamenta Informaticae, 79(3-4), 2007, 319-333.
• [16] Gomolińska, A.: Satisfiability of formulas as object classification, in: Proc. Workshop on Concurrency, Specification, and Programming (CS&P'2007), Łagów, Poland, September 2007 (L. Czaja, Ed.), Warsaw University, 2007, 212-222.
• [17] Góra, G., Wojna, A. G.: RIONA: A new classification system combining rule induction and instance-based learning, Fundamenta Informaticae, 51(4), 2002, 369-390.
• [18] Greco, S., Matarazzo, B., Słowiński, R.: Dominance-based rough set approach to case-based reasoning, Lecture Notes in Artificial Intelligence, 3885, 2006, 7-18.
• [19] Grzymała-Busse, J. W.: LERS - a system for learning from examples based on rough sets, in: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory (R. Słowi´nski, Ed.), Kluwer, Dordrecht, 1992, 3-18.
• [20] Grzymała-Busse, J. W.: Rule induction, in: The Data Mining and Knowledge Discovery Handbook (O. Maimon, L. Rokach, Eds.), Springer, Berlin/Heidelberg, 2005, 255-267.
• [21] Guillet, F., Hamilton, H. J., Eds.: Quality Measures in Data Mining, Springer, Berlin/Heidelberg, 2007.
• [22] Ho´nko, P.: Classification of complex structured objects on the base of similarity degrees, Lecture Notes in Artificial Intelligence, 4585, 2007, 553-563.
• [23] Kleene, S. C.: Introduction to Metamathematics, D. Van Nostrand, New York, 1952, reprinted North-Holland, Amsterdam, 1971.
• [24] Łukasiewicz, J.: On three-valued logic (in Polish), Ruch Filozoficzny, 5, 1920, 170-171, English translation in [9], 87-88.
• [25] Łukasiewicz, J.: Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls, C. R. Soc. Sci. Lettr. Varsovie, 23, 1930, 51-77, English translation in [9], 153-178.
• [26] von Luxburg, U.: Statistical Learning with Similarity and Dissimilarity Functions, Ph. D. thesis, Technische Universit¨at Berlin, 2004.
• [27] Michalski, R. S.: Inferential theory of learning as a conceptual basis for multistrategy learning, Machine Learning, 11, 1993, 111-151.
• [28] Mitchell, M.: Analogy-making as Perception: A Computer Model, MIT Press, Cambridge,MA, 1993.
• [29] Mitchell, M.: Analogy-making as a complex adaptive system, in: Design Principles for the Immune System and Other Distributed Autonomous Systems (L. E. Segel, I. R. Cohen, Eds.), Oxford University Press, New York, 2001, 335-360.
• [30] Nguyen, H. S.: Discretization of Real Value Attributes, Boolean Reasoning Approach, Ph. D. thesis, Warsaw University, 1997.
• [31] Nguyen, H. S., Nguyen, S. H.: Discretization methods for data mining, in: [49], 1998, 451-482.
• [32] Nguyen, S. H., Nguyen, H. S.: Improving rough classifiers using concept ontology, Lecture Notes in Computer Science, 3518, 2005, 312-322.
• [33] Osherson, D. N., Smith, E. E., Wilkie, O., Lopez, A., Shafir, E.: Category-based induction, Psychological Review, 97(2), 1990, 185-200.
• [34] Pavelka, J.: On fuzzy logic I, Zeit. Math. Logic Grund. Math., 25, 1979, 45-52, see also parts II and III in the same volume, 119-134 and 447-464.
• [35] Pawlak, Z.: Classification of Objects byMeans of Attributes, vol. 429 of Research Report CC PAS, Computer Science Institute Polish Acad. Sci., 1981.
• [36] Pawlak, Z.: Information systems - theoretical foundations, Information Systems, 6(3), 1981, 205-218.
• [37] Pawlak, Z.: Rough sets, Int. J. Computer and Information Sciences, 11, 1982, 341-356.
• [38] Pawlak, Z.: Rough classification, Int. J. Man-Machine Studies, 20(5), 1984, 469-483.
• [39] Pawlak, Z.: Rough logic, Bull. Polish Acad. Sci. Tech., 35, 1987, 253-258.
• [40] Pawlak, Z.: Rough Sets. Theoretical Aspects of Reasoning About Data, Kluwer, Dordrecht, 1991.
• [41] Pawlak, Z.: A treatise on rough sets, Transactions on Rough Sets IV, a journal subline to Lecture Notes in Computer Science, 3700, 2005, 1-17.
• [42] Pawlak, Z., Skowron, A.: Rudiments of rough sets, Information Sciences, 177(1), 2007, 3-27.
• [43] Pawlak, Z., Słowiński, R.: Rough set approach to multi-attribute decision analysis, European Journal of Operational Research, 72, 1994, 443-459.
• [44] Peters, J. F.: Approximation spaces for hierarchical intelligent behavioral system models, in: Monitoring, Security, and Rescue Techniques in Multiagent Systems (B. Dunin-Ke¸plicz, A. Jankowski, A. Skowron, M. Szczuka, Eds.), Springer, Berlin/Heidelberg, 2005, 13-30.
• [45] Peters, J. F.: Classification of objects by means of features, in: Proc. 1st IEEE Symp. Foundations of Computational Intelligence (FOCI'2007), Honolulu, Hawaii, April 2007 (D. Fogel, J. Mendel, X. Yao, T. Omori, Eds.), 2007, 1-8.
• [46] Peters, J. F., Skowron, A., Stepaniuk, J.: Nearness of objects: Extension of approximation space model, Fundamenta Informaticae, 79(3-4), 2007, 497-512.
• [47] Pogorzelski, W. A.: Notions and Theorems of Elementary Formal Logic, Białystok Division of Warsaw University, 1994.
• [48] Rauszer, C. M.: Rough logic for multiagent systems, Lecture Notes in Artificial Intelligence, 808, 1994, 161-181.
• [49] Rescher, N.: Many-valued Logic, McGraw-Hill, New York, 1969.
• [50] Rosser, J. B., Turquette, A. R.: Many-valued Logics, North Holland, Amsterdam, 1958.
• [51] Skowron, A., Stepaniuk, J.: Generalized approximation spaces, in: Soft Computing (T. Y. Lin, A. M. Wildberger, Eds.), Simulation Councils, San Diego, CA, 1995, 18-21.
• [52] Skowron, A., Stepaniuk, J.: Tolerance approximation spaces, Fundamenta Informaticae, 27(2-3), 1996, 245-253.
• [53] Skowron, A., Stepaniuk, J., Peters, J. F., Swiniarski, R.: Calculi of approximation spaces, Fundamenta Informaticae, 72(1-3), 2006, 363-378.
• [54] Skowron, A., Swiniarski, R., Synak, P.: Approximation spaces and information granulation, Transactions on Rough Sets III, a journal subline to Lecture Notes in Computer Science, 3400, 2005, 175-189.
• [55] Słowiński, R., Greco, S., Matarazzo, B.: Dominance-based rough set approach to reasoning about ordinal data, Lecture Notes in Artificial Intelligence, 4585, 2007, 5-11.
• [56] Słowiński, R., Vanderpooten, D.: Similarity relation as a basis for rough approximations, in: Advances in Machine Intelligence and Soft Computing (P. P. Wang, Ed.), Duke University Press, 1997, 17-33.
• [57] Stefanowski, J.: On rough set based approaches to induction of decision rules, in: [49], 1998, 500-529.
• [58] Stefanowski, J.: Algorithms of Decision Rule Induction in Knowledge Discovery (in Polish), vol. 361 of Rozprawy, Poznań Technical University, 2001.
• [59] Stepaniuk, J.: Approximation spaces in multi relational knowledge discovery, Transactions on Rough Sets VI: a journal subline to Lecture Notes in Computer Science, 4374, 2007, 351-365.
• [60] Stepaniuk, J., Hońko, P.: Learning first-order rules: A rough set approach, Fundamenta Informaticae, 61(2), 2004, 139-157.
• [61] Suraj, Z., El Gayar, N., Delimata, P.: A rough set approach to multiple classifier systems, Fundamenta Informaticae, 72(1-3), 2006, 393-406.
• [62] Synak, P., Bazan, J. G., Skowron, A., Peters, J. F.: Spatio-temporal approximate reasoning over complex objects, Fundamenta Informaticae, 67(1-3), 2005, 249-269.
• [63] Wojna, A. G.: Analogy-based reasoning in classifier construction, Transactions on Rough Sets IV: a journal subline to Lecture Notes in Computer Science, 3700, 2005, 277-374.
• [64] Wolski, M.: Category-based rough induction, Lecture Notes in Artificial Intelligence, 4585, 2007, 192-201.
• [65] Wróblewski, J.: Adaptive Methods of Object Classification, Ph. D. thesis, Warsaw University, 2002.
• [66] Yao, Y. Y., Wong, S. K. M., Lin, T. Y.: A review of rough set models, in: Rough Sets and Data Mining: Analysis of Imprecise Data (T. Y. Lin, N. Cercone, Eds.), Kluwer, Boston/London/Dordrecht, 1997, 47-75.
• [67] Zadeh, L. A.: Fuzzy sets, Information and Control, 8, 1965, 338-353.
• [68] Zadeh, L. A.: Outline of a new approach to the analysis of complex system and decision processes, IEEE Trans. on Systems, Man, and Cybernetics, 3, 1973, 28-44.
• [69] Zadeh, L. A.: Fuzzy logic and approximate reasoning, Synthese, 30, 1975, 407-428.
• [70] Ziarko,W.: Variable precision rough set model, J. Computer and System Sciences, 46(1), 1993, 39-59.
• [71] Ziarko, W.: Probabilistic decision tables in the variable precision rough set model, Computational Intelligence, 17(3), 2001, 593-603.