Discovering of association rules without a minimum support threshold - coherent rules discovery

In the data mining field, association rules have been researched for more than fifteen years; however, the degree to which the support threshold effectively discovers interesting association rules has received little attention. This thesis proposes a new framework for data mining through which interesting association rules called coherent rules can be discovered. Coherent rules are those associations that can be mapped to logical equivalences according to propositional logic. Hence, coherent rules can be reasoned as logically true statements based solely on the truth table values of logical equivalence. Discovering coherent rules resolves the many difficulties in mining associations that require a preset minimum support threshold. Apart from solving the issues of a support threshold, the coherent rules found can also be reasoned as logical implications due to the mapping to the truth table values of logical equivalence. In contrast, classic association rules cannot be reasoned as logical implications due to their lack of this logic property. We have further devised a measure of interestingness to use with coherent rules that quantifies a coherent rule implicational strength value. The interestingness measure is sensitive to the direction of an implication. Use of coherent rules together with the measure of interestingness provides us with a better representation of associations in data mining due to their logical implications and unidirectional properties. An algorithm to discover coherent rules is also presented in this thesis. The algorithm was designed to find the shortest and strongest rule or most effectual vii coherent rules by exploiting the properties of coherent rules. Decision or actions can be implemented based on these coherent rules. In a situation whereby users are interested in weaker and/or longer rules, the algorithm enables parameters to be set. Unlike support threshold settings, these parameters do not require users to have prior knowledge of the context in which the data mining takes place. We have tested our framework on several datasets. The results confirm the strength of coherent rules in finding association rules that can be reasoned logically and in finding association rules that consider both infrequent items and negative associations. The algorithm used to discover coherent rules is also efficient. This was demonstrated by the number of prunings made to the search space during the discovery process. This study suggests that our framework for discovering coherent rules offers a technique for data mining that overcomes the limitations associated with existing methods and enables the finding of association rules among the presence and/or absence of a set of items without a preset minimum support threshold. The results justify continuing research in this area in order to increase the body of scientific knowledge of data mining - and specifically, association rules - and to provide practical support to those involved in data mining activities.