Article Preview
Top1. Introduction
Sequential pattern mining (SPM) is a well-known data mining technique introduced in (Srikant & Agrawal, 1995) to find regularities in a database of sequences. With the increasing amount of data available on the World Wide Web (WWW), discovering and analyzing useful information from the WWW becomes an essential task (Blockeel & Kosala, 2000). The task of Web Mining consists to extract an interesting and potentially meaningful patterns based on activities related to the WWW (Kohavi, 2002). There are roughly three knowledge discovery domains that pertain to web mining (Cooley, 1997): web content mining, web structure mining and web usage mining. In Web Usage Mining (WUM), also known as web access, the mining process aims at extracting knowledge from server log files collected when users access Web servers over a period of time (Kohavi, 2002).
Mining web access patterns from Web logs can provide useful information for server performance enhancements, restructuring a web site, and direct marketing in e-commerce (Etzioni & Oren, 1996). For an e-commerce company, this may help detecting future customers likely to make a large number of purchases, or predicting which online visitors will click on what commercials or banners, based on observation of prior visitors, who have behaved both positively or negatively to the advertisement banner (Ezeife & Yi, 2005).
There are already in the literature many efficient algorithms to extract sequential patterns (e.g. GSP (Agrawal & Srikant, 1996), SPADE (Zaki, 2001), PrefixSpan (Pei, Han, Mortazavi-Asl, Pinto, Dayal, & Hsu, 2001), web sequential patterns on web log data (e.g. WAP-tree (Jian Pei J. H.-A., 2000)), PLWAP (Ezeife & Yi, 2005)), closed sequential patterns (e.g. CloSpan (Yan, Han, & Afshar, 2003), BIDE (Han & Wang, 2004)) or sequential patterns satisfying regular expressions (e.g. SPIRIT (Minos, Garofalakis, & Rastogi, 2002)). All the above methods, though efficient, they suffer from two major problems. First, they tackle particular classes of constraints (i.e. monotonic1 and anti-monotonic ones (see Section 5.3)) by using devoted techniques. However, several practical constraints required in data mining tasks, such as regular expression, gap, aggregates, do not fit into these classes. Second, they suffer from a lack of genericity to handle simultaneously different types of constraints in a simple way. Indeed, new constraints have to be hand-coded and their combinations often require the revision of the original algorithm to take into account the new constraints.