Affiliations: Department of Basic Sciences, Faculty of Engineering, Kyushu Institute of Technology, Tobata, Kitakyushu, 804-8550, Japan. sakai@mns.kyutech.ac.jp | Department of Integrated System Engineering, Kyushu Institute of Technology, Tobata, Kitakyushu, 804-8550, Japan. wumogaku@yahoo.co.jp | Faculty of Management and Information Science, Josai International University, Gumyo, Togane, Chiba 283, Japan. nakatam@ieee.org
Note: [] This work is supported by the Grant-in-Aid for Scientific Research (C) (No.18500214, No.22500204), Japan Society for the Promotion of Science. Address for correspondence: Department of Basic Sciences, Faculty of Engineering, Kyushu Institute of Technology, Tobata, Kitakyushu, 804-8550, Japan.
Abstract: This paper discusses issues related to incomplete information databases and considers a logical framework for rule generation. In our approach, a rule is an implication satisfying specified constraints. The term incomplete information databases covers many types of inexact data, such as non-deterministic information, data with missing values, incomplete information or interval valued data. In the paper, we start by defining certain and possible rules based on non-deterministic information. We use their mathematical properties to solve computational problems related to rule generation. Then, we reconsider the NIS-Apriori algorithm which generates a given implication if and only if it is either a certain rule or a possible rule satisfying the constraints. In this sense, NIS-Apriori is logically sound and complete. In this paper, we pay a special attention to soundness and completeness of the considered algorithmic framework, which is not necessarily obvious when switching from exact to inexact data sets. Moreover, we analyze different types of non-deterministic information corresponding to different types of the underlying attributes, i.e., value sets for qualitative attributes and intervals for quantitative attributes, and we discuss various approaches to construction of descriptors related to particular attributes within the rules' premises. An improved implementation of NIS-Apriori and some demonstrations of an experimental application of our approach to data sets taken from the UCI machine learning repository are also presented. Last but not least, we show simplified proofs of some of our theoretical results.
Keywords: Association and decision rules, Incomplete and non-deterministic information, Set and interval valued data sets, Rough set approximations, Apriori algorithm extensions and implementation, Soundness and completeness
