Mining association rules in hypertext databases

The concepts of confidence and support for composite association rules, and two algorithms to mine such rules are proposed, show that, in spite of the worst-case complexity analysis which indicates exponential behaviour, in practice the algorithms' complexity is linear in the number of nodes traversed.

Abstract

Association rule techniques traditionally aim to mine information from databases consisting of a set of flat transaction records. In this work we propose a generalisation of the notion of association rule in the context of flat transactions to that of a composite association rule in the context of a structured directed graph, such as the world-wide-web. The techniques proposed aim at finding patterns in the user behaviour when traversing such a hypertext system. We redefine the concepts of confidence and support for composite association rules, which are trails of links representing a user's navigation session; the actual data may be obtained from log files. Two algorithms to mine composite association rules are exhibited: one is a modification of the directed graph Depth-First-Search algorithm, and the other uses an incremental approach to build the set of composite rules of size n+ 1 from the set of composite rules of size n. Extensive experiments with random data were conducted in o...