Definability in Mining Incomplete Data

In this paper we study local and global definability of incomplete data sets from the view point of decision rule induction. We assume that data sets are incomplete since some attribute values are lost and some are considered as irrelevant and called “do not care” conditions. Local definability uses blocks of attribute-value pairs as basic granules, while global definability uses characteristic sets. Local definability is more general than global definability. Local definability is essential for data mining since a concept is locally definable if and only if it can be expressed by decision rules. We study seven modifications of the characteristic relation and conclude that for five of them the corresponding characteristic sets are not locally definable, so these modifications should not be used for data mining.