An Application of Discernibility Functions to Generating Minimal Rules in Non-Deterministic Information Systems
Hiroshi Sakai* and Michinori Nakata**
*Department of Mathematics and Computer Aided Science, Faculty of Engineering, Kyushu Institute of Technology, Tobata, Kitakyushu 804-8550, Japan
**Faculty of Management and Information Science, Josai International University, Gumyo, Togane, Chiba 283-8555, Japan
Minimal rule generation in Non-deterministic Information Systems (NISs), which follows rough sets based rule generation in Deterministic Information Systems (DISs), is presented. According to certain rules and possible rules in NISs, minimal certain rules and minimal possible rules are defined. Discernibility functions are also introduced into NISs for generating minimal certain rules. Like minimal rule generation in DISs, the condition part of a minimal certain rule is given as a solution of an introduced discernibility function. As for generating minimal possible rules, there may be lots of discernibility functions to be solved. So, an algorithm based on an order of attributes is proposed. A tool, which generates minimal certain rules and minimal possible rules, has also been implemented.
-  Z. Pawlak, “Rough Sets,” Kluwer Academic Publisher, 1991.
-  Z. Pawlak, “Some Issues on Rough Sets,” Transactions on Rough Sets, International Rough Set Society, Vol.1, pp. 1-58, 2004.
-  J. Komorowski, Z. Pawlak, L. Polkowski, and A. Skowron, “Rough Sets: a tutorial, Rough Fuzzy Hybridization,” Springer, pp. 3-98, 1999.
-  L. Polkowski and A. Skowron, (eds.), “Rough Sets in Knowledge Discovery 1,” Studies in Fuzziness and Soft Computing, Physica-Verlag, Vol.18, 1998.
-  L. Polkowski and A. Skowron, (eds.), “Rough Sets in Knowledge Discovery 2,” Studies in Fuzziness and Soft Computing, Physica-Verlag, Vol.19, 1998.
-  J. Grzymala-Busse, “A New Version of the Rule Induction System LERS,” Fundamenta Informaticae, Vol.31, pp. 27-39, 1997.
-  W. Ziarko, “Variable Precision Rough Set Model,” Journal of Computer and System Sciences, Vol.46, pp. 39-59, 1993.
-  S. Tsumoto, “Knowledge Discovery in Clinical Databases and Evaluation of Discovered Knowledge in Outpatient Clinic,” Information Sciences, Vol.124, pp. 125-137, 2000.
-  A. Nakamura, S. Tsumoto, H. Tanaka, and S. Kobayashi, “Rough Set Theory and Its Applications,” J. JSAI, Vol.11, No.2, pp. 209-215, 1996.
-  N. Zhong, J. Dong, S. Fujitsu, and S. Ohsuga, “Soft Techniques to Rule Discovery in Data,” Transactions of Information Processing Society of Japan, Vol.39, pp. 2581-2592, 1998.
-  “Rough Set Software,” Bulletin of International Rough Set Society, Vol.2, pp. 15-46, 1998.
-  E. Orłowska (ed.), “Incomplete Information: Rough Set Analysis,” Physica-Verlag, 1998.
-  E. Orłowska and Z. Pawlak, “Representation of Nondeterministic Information,” Theoretical Computer Science, Vol.29, pp. 27-39, 1984.
-  W. Lipski, “On Semantic Issues Connected with Incomplete Information Data Base,” ACM Trans. DBS, Vol.4, pp. 269-296, 1979.
-  W. Lipski, “On Databases with Incomplete Information,” Journal of the ACM, Vol.28, pp. 41-70, 1981.
-  S. Demri and E. Orłowska, “Incomplete Information: Structure, Inference, Complexity,” Monographs in Theoretical Computer Science, Springer, 2002.
-  A. Nakamura, “A Rough Logic based on Incomplete Information and Its Application,” International Journal of Approximate Reasoning, Vol.15, pp. 367-378, 1996.
-  J. Grzymala-Busse and P. Werbrouck, “On the Best Search Method in the LEM1 and LEM2 Algorithms,” Incomplete Information: Rough Set Analysis, Phisica-Verlag, pp. 75-91, 1998.
-  J. Grzymala-Busse, “Data with Missing Attribute Values: Generalization of Indiscernibility Relation and Rule Induction,” Transactions on Rough Sets, International Rough Set Society, Vol.1, pp. 78-95, 2004.
-  M. Kryszkiewicz, “Rules in Incomplete Information Systems,” Information Sciences, Vol.113, pp. 271-292, 1999.
-  M. Kryszkiewicz and H. Rybinski, “Computation of Reducts of Composed Information Systems,” Fundamenta Informaticae, Vol.27, pp. 183-195, 1996.
-  M. Kryszkiewicz, “Maintenance of Reducts in the Variable Precision Rough Sets Model,” ICS Research Report 31/94,Warsaw University of Technology, 1994.
-  E. Codd, “A Relational Model of Data for Large Shared Data Banks,” Communication of the ACM, Vol.13, pp. 377-387, 1970.
-  H. Sakai and A. Okuma, “Basic Algorithms and Tools for Rough Non-deterministic Information Analysis,” Transactions on Rough Sets, International Rough Set Society, Vol.1, pp. 209-231, 2004.
-  H. Sakai, “Effective Procedures for Handling Possible Equivalence Relations in Non-deterministic Information Systems,” Fundamenta Informaticae, Vol.48, pp. 343-362, 2001.
-  H. Sakai, “Effective Procedures for Data Dependencies in Information Systems,” Rough Set Theory and Granular Computing, Studies in Fuzziness and Soft Computing, Springer-Verlag, Vol.125, pp. 167-176, 2003.
-  H. Sakai, “A Framework of Rough Sets based Rule Generation in Non-deterministic Information Systems,” Lecture Notes in AI, Springer-Verlag, Vol.2871, pp. 143-151, 2003.
-  H. Sakai and M. Nakata, “Discernibility Functions and Minimal Rules in Non-deterministic Information Systems,” Lecture Notes in AI, Springer-Verlag, Vol.3641, pp. 254-264, 2005.
-  A. Skowron and C. Rauszer, “The Discernibility Matrices and Functions in Information Systems,” In Intelligent Decision Support – Handbook of Advances and Applications of the Rough Set Theory, Kluwer Academic Publishers, pp. 331-362, 1992.