Abstract:
A system for traversal pattern mining. A storage device stores multiple web log records individually comprising multiple ordered web objects, and multiple minimum support records individually corresponding to the web object and comprising a min_sup value corresponding to the position of the web object. A traversal pattern mining program inserts the web objects with occurrence is exceeding or equaling the corresponding min_sup value into a first large reference sequence set (L 1 ), generates multiple first candidate reference sequences, inserts the first candidate reference sequences with occurrence exceeding or equaling the minimized min_sup value of the self-contained web objects into a second large reference sequence set (L 2 ), and generates a traversal pattern set by merging the L 1  and the L 2 .

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to web mining technology, and more particularly, to a method and apparatus of traversal pattern mining with reference to predefined minimum support value corresponding to web object position.  
         [0003]     2. Description of the Related Art  
         [0004]     With the rapid expansion of the World Wide Web (WWW), web data mining has recently become increasingly important. An important issue in web data mining is traversal pattern mining used to decide upcoming likely web page requests based on significant statistical correlations. Web log data is collected by web servers, containing information about user behavior on a site (e.g., sequences of URLs requested by different clients bearing different IP address.). The analysis of these large volumes of log data requires employment of data mining methods. According to the definition of association mining rules, mined patterns are those access sequences of frequent occurrence. If a sequence appears frequently enough, the sequence indicates a frequent traversal pattern. Understanding user traversal patterns not only helps improve the Web site design, such as providing efficient access between highly correlated objects, better authoring design for pages, and the like, but also lead to better marketing decisions, such as advertisement placement, more accurate customer classification and behavior analysis, and the like.  
         [0005]     Although conventional methods described are feasible for the mining of frequent traversal patterns from a log file, several problems remain. Specifically, conventional methods of traversal pattern mining are based on the model of a uniform support threshold to determine frequent traversal patterns without considering such important factors as the length of the pattern and the positions of web pages. As a result, a low support threshold leads to generation of unimportant patterns while a high support threshold may cause important patterns with lower support to be ignored.  
         [0006]     In view of these limitations, a need exists for an apparatus and method of traversal pattern mining, with reduced process time and improved usability of results.  
       SUMMARY OF THE INVENTION  
       [0007]     It is therefore an object of the present invention to provide an apparatus and method of traversal pattern mining, with reduced process time and improved usability of results. To achieve the above object, the present invention provides a system and method of traversal pattern mining that considers the length of the pattern and the positions of web pages.  
         [0008]     According to the invention, the apparatus includes a display device, a central processing unit (CPU), a memory, a storage device, and an input device. The CPU, controlled by instructions received from the memory  13  and an operator through the input device, executes traversal pattern mining functions. The storage device stores multiple web log records and minimum support records. The memory comprises a traversal pattern mining program, and the traversal pattern mining program comprises a mining algorithm, a preparation function, a “SeqGen C2 ” function and a “SeqGen Ck ” function.  
         [0009]     The mining algorithm, the kernel of the traversal pattern mining program, includes routines executing preparation, SeqGen C2  and SeqGen Ck  functions to generate frequent reference sequences representing frequent traversal patterns. If min_sup(p) denotes a minimum support value of page p, the minimum support value of a reference sequence c, denoted by MinSup(c), is the lowest min_sup value among the pages in the reference sequence c, then  
         MinSup   ⁡     (   c   )       =       min     p   ∈   c       ⁢       {     min_sup   ⁢     (   p   )       }     .           
 
 In order to produce the seeds for generating candidate 2-reference sequences C 2 , the algorithm first performs the preparation function with two arguments P and D, where P is the set of pages to be sorted in ascending order of their minimum support values, and D is the web log records. Frequent web path traversal patterns are generated by multiple scans of the web log records. The large k-reference sequences L k  found in the (k−1) th  scan are used to generate the candidate k-reference sequences C k  using the SeqGen Ck  function, except when k=2, for which the candidate generation function is SeqGen C2 . Next, the web log records are scanned and the support value of reference sequences in C k  is calculated. Finally, new large k-reference sequences L k  are obtained by removing those sequences whose support values are smaller than the corresponding values of MinSup(.). Finally, a resulting L k  represents the frequent traversal patterns.
 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]     The present invention can be more fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein:  
         [0011]      FIG. 1  is a diagram of the architecture of an apparatus of traversal pattern mining according to the invention;  
         [0012]      FIG. 2  is a diagram of the storage device and memory for the traversal pattern mining apparatus according to the invention;  
         [0013]      FIG. 3  is a diagram of an exemplary web page structure according to the present invention;  
         [0014]      FIG. 4  shows exemplary web log records containing ten records according to the present invention;  
         [0015]      FIG. 5  shows exemplary minimum support records according to the present invention;  
         [0016]      FIG. 6  shows exemplary large 1-reference sequences L 1  and large 2-reference sequences L 2  according to the present invention;  
         [0017]      FIG. 7  shows exemplary large 3-reference sequences L 3  according to the present invention;  
         [0018]      FIG. 8  is a flowchart showing the method of the traversal pattern mining according to the invention;  
         [0019]      FIG. 9  is a diagram of a storage medium storing a computer program providing the method of the traversal pattern mining according to the invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]      FIG. 1  is a diagram of the architecture of an apparatus of traversal pattern mining according to the invention. The apparatus  100  includes a display device  11 , a central processing unit (CPU)  12 , a memory  13 , a storage device  14 , and an input device  15 . The CPU  12  may be manufactured by Motorola, IBM, or Intel, the display device  11  can be a CRT, TFT-LCD, or plasma screen, and the input device  15  can be a keyboard, mouse, bar code reader, or others. The CPU  12  is connected by buses to the display device  11 , memory  13 , storage device  14  and input device  15  based on Von Neumann architecture. The CPU  12 , memory  13 , storage device  14 , display device  11  and input device  15  may be conventionally coupled to a mainframe computer, a mini-computer, a workstation computer, a personal computer, or a mobile computer. The CPU  12 , controlled by instructions received from the memory  13  and an operator through the input device  15 , executes traversal pattern mining functions.  
         [0021]      FIG. 2  is a diagram of the storage device and memory for the traversal pattern mining apparatus according to the invention. The storage device  14  can be implemented in a relational database, object database, or file system, and stores multiple web log records  141  and minimum support records  142 . The implementation of the web log records  141  or minimum support records  142  described is not limited to a single table, but also to multiple related tables. The memory  13  is preferably a random access memory (RAM), but may also comprise read-only memory (ROM) or flash ROM. The memory  13  comprises a traversal pattern mining program  133 , and the traversal pattern mining program  133  comprises a mining algorithm  1331 , a preparation function  1332 , a “SeqGen C2 ” function  1333  and a “SeqGen Ck ” function  1334 . The traversal pattern mining program  133  inputs the web log records  141  and minimum support records  142 , and accordingly generates frequent reference sequences. The present invention preferably uses a conventional operating system  131  such as Microsoft Windows, UNIX, LINUX, Sun Solaris, IBM AIX, or others. The memory  13  may also comprise various application programs  132  including but not limited to computer drawing programs, word processing programs, and spreadsheet programs.  
         [0022]      FIG. 3  is a diagram of an exemplary web page structure according to the present invention. The web page structure  3  contains pages A to H, showing the connectivity among web pages.  FIG. 4  shows exemplary web log records containing ten records, ranging from  401  to  410 , according to the present invention. The web log record  141  comprises two fields, such as log number and traversal path, the traversal path corresponding to the web page structure  3 . For example, record  408  indicates that pages C, B and F are sequentially accessed.  FIG. 5  shows exemplary minimum support records according to the present invention. The minimum support record stores a minimum support (min_sup) value of the web page, and the value is set according to the position of the web page. Pages with higher position, such as portal pages, are preferably configured with higher minimum support value.  
         [0023]     The mining algorithm  1331 , the kernel of the traversal pattern mining program  133 , includes routines executing the preparation function  1332 , SeqGen C2  function  1333  and SeqGen Ck  function  1334  to generate frequent reference sequences representing frequent traversal patterns. Referring to  FIG. 5 , min_sup(p) denotes a minimum support value of page p. The minimum support value of a reference sequence c, denoted by MinSup(c), is the lowest min_sup value among the pages in the reference sequence c, such that  
         MinSup   ⁡     (   c   )       =       min     p   ∈   c       ⁢       {     min_sup   ⁢     (   p   )       }     .           
 
         [0024]     The mining algorithm  1331  composed of pseudo-codes utilizes the following code sequence:  
                                         Algorithm mining(P, D)                                    (a1) SD=Preparation(P,D);           (a2) L1={&lt;s&gt;|s∈SD,s.count≧min_sup(s)};           (a3) for (k=2;L k−1 ≠0;k++) do begin           (a4)  if (k=2) then C 2 =SeqGen C2 (SD);           (a5)  else C k =SeqGen Ck (L k−1 );           (a6)  end           (a7)  Scan database and compute frequency of each               candidate C k ;           (a8)  L k ={c∈C k |c.count≧MinSup(c)};           (a9) end                      
 
 (a10) Answer=∪ k L k ; 
 
         [0025]     In order to produce the seeds for generating candidate 2-reference sequences C 2 , the algorithm first performs the preparation function  1332  with two arguments P and D, where P is the set of pages to be sorted in ascending order of their minimum support values, as shown in  FIG. 5 , and D the web log records as shown in  FIG. 4 . Details of the preparation function  1332  are further described as follows. Frequent web path traversal patterns are generated using multiple scans of the web log records  141 . The large k-reference sequences L k  found in the (k−1) th  scan are used to generate the candidate k-reference sequences C k  using the SeqGen Ck  function  1334 , except when k=2, for which the candidate generation function is SeqGen C2    1333 , as stated in step a 4  and step a 5  of the mining algorithm  1332 . Next, the web log records  141  are scanned and the support value of reference sequences in C k  is calculated as stated in step a 7 . Finally, new large reference sequences are obtained by removing those sequences whose support values are smaller than their corresponding values of MinSup(.), as stated in step a 8 . Details of both the SeqGen C2  function  1333  and SeqGen Ck  function  1334  are further described as follows.  
         [0026]     The preparation function  1332  is devised to produce not only L 1  but also the seed for C 2  generation. With the input of two arguments P and D, the preparation function  1332  composed of pseudo-codes utilizes the following code sequence:  
                                         Function Preparation(P, D)                                    (b1) Scan database and compute frequency of each page            p∈P;           (b2) Sort pages in P in ascending order of their minimum           support;           (b3) Following sorted order, find first page f in P that            frequency of f exceeds min_sup(f);           (b4) Insert page f into seed set SD;           (b5) for each subsequent page i in P that is ordered           after f           (b6)  if (i.count≧min_sup(f))           (b7)    insert i into set SD;           (b8) end                      
 
         [0027]     Consider the web page structure as shown in  FIG. 3 . The web log records  141  and the support threshold of each web page are provided in  FIG. 4  and  FIG. 5 , respectively.  FIG. 6  shows exemplary large 1-reference sequences L 1  and large 2-reference sequences L 2  according to the present invention. After one pass of the web log records  141 , the occurrence (i.e., count) of each seed (SD) as shown in  FIG. 6   b  is calculated as stated in step b 1 . As a result, the SD set and L 1  as shown in  FIG. 6   b  and  FIG. 6   c  respectively are obtained as stated in steps b 3  to b 8 . It is noted that page B is not in L 1  because B.count is smaller than the value of min_sup(B).  
         [0028]     In the SeqGen C2  function  1333 , argument SD as shown in  FIG. 6   b  is employed to generate C 2  and utilizes the following code sequence:  
                                         Function SeqGen C2  (SD)                                    (c1) for each p in SD in the same order do begin           (c2)  if p.count≧min_sup(p) then           (c3)    for each q is ordered after p in SD do           begin           (c4)      if q.count≧min_sup(p) then           (c5)        insert {pq} and {qp} into C 2 ;           (c6)    end           (c7) end                      
 
         [0029]     As a result, the C 2  as shown in  FIG. 6   d  is obtained as stated in steps c 1  to c 7 . {BA}, {AB}, {BC} and {CB} are not in C 2  because B.count is smaller than the min_sup(B). Hence, {BA}, {AB}, {BC} and {CB} are not frequent. It is noted that a web page p∉L 1  does not imply that its corresponding occurrence does not exceed that of the min_sup of an earlier page in the sorted order. For example, the page B is in SD but not in L 1 . If the SeqGen C2  function  1333  uses L 1  to generate C 2 , candidate reference sequence such as {BD} is missed, the reason for use of the SD set, other than L 1  in the SeqGen C2  function  1333 .  
         [0030]      FIG. 7  shows exemplary large 3-reference sequences L 3  according to the present invention. In the SeqGen Ck  function  1334 , argument L k−1  is employed to generate C k  and utilizes the following code sequence:  
                                         Function SeqGen Ck  (L k−1 )                                    (d1) insert into C k  //join L k−1  with L k−1             (d2) select p 1 ,p 2 ,...,p k−1 ,q k−1 from p,q∈L k−1  where //mid_join             p 2 =q 1 ,...,p k−1 =q k−2  and p 1 ∉MSP(p) and q k−1 ∉MSP(q)           (d3) Union           (d4) select p 1 ,p 2 ,...,p k−1 ,q k−1 from p,q∈L k−1  where //head_join             p 1 =q 1 ,...,p k−2 =q k−2  and p 1 ∈MSP(p) and q 1 ∈MSP(q)           (d5) Union           (d6) select p 1 ,q 1 ,q 2 ,..., q k−1 from p,q∈L k−1  where //tail_join             p 2 =q 2 ,...,p k−1 =q k−1  and p k−1 ∈MSP(P) and q k−1 ∈MSP(q);           (d7) for each reference sequence c∈C k  do begin           (d8)  for each k−1 subsets s of c do begin           (d9)    if |MSP(c)|≧2 or MinSup(s)=MinSup(c) then           (d10)      if (s∉L k−1 ) then           (d11)        delete c from C k ;           (d12)  end           (d13) end                        
         [0031]     The SeqGen Ck  function  1334  first inputs L k−1  and joins L k−1  with L k−1  to generate temporal candidate k-reference sequence c* k  using three joinable forms, such as “head_join”, “mid_join” and “tail_join”, as stated in steps d 1  to d 6 .  
         [0032]     The minimal support page of a reference sequence r is MSP(r)={p|p∈r,min_sup(p)=MinSup(r)}, referring to  FIG. 7   b , MSP({BEG})={E}. Let p and q are (k−1)-reference sequences which contain p 1 , . . . , p k−1  and q 1 , . . . , q k−1  respectively. If p excluding p 1  is equal to q excluding q k−1 , p 1  is not MSP(p) and q k−1  is not MSP(q), then c* k ={p 1 , p 2  . . . , p k−1 , q k−1 } is obtained using the mid_join form as stated in step d 2 . If p excluding p k−1  is equal to q excluding q k−1 , p 1  is MSP(p) and q 1  is MSP(q), then c* k ={p 1 , p 2  . . . , p k−1 , q k−1 } is obtained using the head_join form as stated in step d 4 . If p excluding p 1  is equal to q excluding q 1 , p k−1  is MSP(p) and q k−1  is MSP(q), then c* k ={p 1 , q 1 , q 2 , . . . , q k−1 } is obtained using the tail_join form as stated in step d 6 . The SeqGen Ck  function  1334  deletes all sets of reference sequences c∈C k  which are infrequent, as stated in steps d 7  to d 13 .  
         [0033]     The SeqGen Ck  function  1334  inputs L 2  as shown in  FIG. 7   a , joins L 2  with L 2  to generate temporary candidate 3-reference sequence c* 3  as shown in  FIG. 7   b  using the above joinable forms. For example, {BEG} is generated from {BE} and {EG} using mid_join form; {EBG} is generated from {BG} and {EG} using tail_join form; and {BAF} is generated from {BF} and {AF} using head_join form. Candidate 3-reference sequence C 3  excluding {EBG}, {BAF} and {ABF} as shown in  FIG. 7   c  is generated.  
         [0034]     Finally, the mining algorithm  1331  acquires frequent reference sequence sets including L 1 , L 2  and L 3  as shown in  FIGS. 6   c ,  6   e  and  7   d  respectively, as stated in step a 10 .  
         [0035]      FIG. 8  is a flowchart showing a method of the traversal pattern mining according to the invention. The process begins in steps S 811  and S 812 , respectively inputs web log records  141  as shown in  FIG. 4 , and minimum support records  142  as shown in  FIG. 5 . The web log record  141  comprises two fields, such as log number and traversal path, the traversal path corresponding to the web page structure  3 . The minimum support record stores a min_sup value of the web page, and the value is set according to the position of the web page.  
         [0036]     Then, in step S 821 , after one pass of the web log records  141 , the occurrence (i.e., count) of each seed (SD) as shown in  FIG. 6   b  is calculated, and the SD set is arranged in ascending order of their minimum support. In step S 822 , the L 1  as shown in  FIG. 6   c  is generated by removing pages whose occurrence is less than that of corresponding min_sup in SD set.  
         [0037]     In step S 831 , wherein each page q is ordered after page p in SD, it is determined whether occurrence of q is greater than or equal min_sup(p), if so, {pq} and {qp} are inserted into C 2 . The resulting C 2  is shown in  FIG. 6   d . Step S 832  calculates each sequence occurrence in C 2  by scanning web log records  141  and inserts sequences whose occurrence exceeds or equals corresponding MinSup(.) into L 2 . The resulting L 2  is shown in  FIG. 6   e.    
         [0038]     In step S 840 , k is set to 3. The process proceeds to step S 842  because L 2  is present. In step  842 , L 2  is joined with L 2  to generate c* 3  using the above joinable forms. The resulting c* 3  is shown in  FIG. 7   b . Next, C 3  as shown in  FIG. 7   c  is generated by deleting all reference sequences c∈c* 3  comprising invalid traversal paths according to the web page structure  3 . Step S 843  calculates each sequence occurrence in C 3  by scanning web log records  141  and inserts sequences whose occurrence exceeds or equals MinSup(sequence) into L 3 . The resulting L 3  is shown in  FIG. 7   d . Step S 844  adds 1 to k.  
         [0039]     Finally, the process proceeds to step S 851  to acquire frequent reference sequence sets including L 1 , L 2  and L 3  as shown in  FIGS. 6   c ,  6   e  and  7   d  respectively.  
         [0040]     The system and method of traversal pattern mining of the present invention considers the length of the pattern and the positions of web pages, with reduced process time and improved result usability.  
         [0041]     Although web pages are used in the embodiment, the present invention is also applicable to images, sounds, videos, files or others, linked by web pages.  
         [0042]     The invention additionally discloses a storage medium for storing a computer program  133  providing the disclosed method of traversal pattern mining, as shown in  FIG. 9 . The computer program product includes a storage medium  60  having computer readable program code embodied in the medium for use in a computer system, the computer readable program code comprising at least mining algorithm  1331 , preparation function  1332 , SeqGen C2  function  1333 , and SeqGen Ck  function  1334 .  
         [0043]     The methods and system of the present invention, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMS, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. The methods and apparatus of the present invention may also be embodied in the form of program code transmitted over some transmission medium, such as electrical wiring or cabling, through fiber optics, or via any other form of transmission, wherein, when the program code is received and loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code combines with the processor to provide a unique apparatus that operates analogously to specific logic circuits.  
         [0044]     Although the present invention has been described in its preferred embodiments, it is not intended to limit the invention to the precise embodiments disclosed herein. Those who are skilled in this technology can still make various alterations and modifications without departing from the scope and spirit of this invention. Therefore, the scope of the present invention shall be defined and protected by the following claims and their equivalents.