Incremental method of generating decision implication canonical basis

Decision implication is an elementary representation of decision knowledge in formal concept analysis. Decision implication canonical basis (DICB), a set of decision implications with completeness and non-redundancy, is the most compact representation of decision implications. The method based on true premises (MBTP) for DICB generation is the most efficient one at present. In practical applications, however, data are always changing dynamically, and MBTP, lacking an update mechanism of DICB, still needs to re-generate inefficiently the whole DICB. This paper proposes an incremental algorithm for DICB generation, which obtains a new DICB just by modifying and updating the existing one. Experimental results verify that when samples in data are much more than condition attributes, which is actually a general case in practical applications, the incremental algorithm is significantly superior to MBTP. Furthermore, we conclude that even for the data in which samples are less than condition attributes, when new samples are continually added into data, the incremental algorithm must be also more efficient than MBTP, because the incremental algorithm just needs to modify the existing DICB, which is only a part of work of MBTP.

Automated summary

Decision implication is a fundamental representation of decision knowledge in formal concept analysis, with Decision implication canonical basis (DICB) being the most compact and complete representation. The method based on true premises (MBTP) for DICB generation is currently the most efficient one, but lacks an update mechanism for dynamically changing data. An incremental algorithm for DICB generation is proposed in this paper, which is significantly superior to MBTP especially when samples in data are much more than condition attributes. The experimental results also suggest that the incremental algorithm is more efficient than MBTP even when new samples are continually added into data, due to its ability to modify existing DICB.