웹 로그 파일에서 순회 패턴 탐사 알고리즘 2000. 2 성신여대 하미라 석사논문 웹 로그 파일에서 순회 패턴 탐사 알고리즘 2000. 2 성신여대 하미라 석사논문 2000년 7월 14일 DE Lab. 윤지영

목 차 순회 패턴 탐사 구현 알고리즘 웹 로그 파일에서 순회 패턴 탐사 성능 분석 결론 및 향후 과제

순회 패턴 탐사 순회 패턴 탐사 단계 최대 순방향 참조 단계(Maximal Forward References) : 사용자 접근 패턴에서 역방향참조 일어날 때 까지의 순방향 참조 시퀀스 2. 빈발 참조 시퀀스 단계(Large Reference Sequences) : 최대 순방향 참조 중에서 최소지지도를 만족하는 시퀀스 3. 최대 참조 시퀀스 단계(Maximal Reference Sequences) : 다른 빈발 참조 시퀀스 어느 하나에도 포함되지 않는 빈발 참조 시퀀스

{ABCD, ABEGH, ABEGW, AOU, AOV} 그림 1 . 순회패턴의 예 - 한 사용자의 순회 경로 {A, B, C, D, C, B, E, G, H, G, W, A, O, U, O, V} - 생성된 최대 순방향 참조 {ABCD, ABEGH, ABEGW, AOU, AOV}

최대 순방향 참조 Log database : a pair of (Source, Destination) 최대순방향 참조를 저장한 데이터베이스 : DF MF(Maximal Forward ) 알고리즘 - 로그 데이터베이스를 사용자 아이디로 정렬, 각 사용자에 대해 시간순으로 정렬된 순회경 로 {(s1,d1),(s2,d2),…,(sn,dn)} 을 얻음 - 정렬된 모든 로그 데이터에 대하여 d1 에서부 터 dj (역참조가 일어날 때가 j 번째 참조라면) 까지의 스트링을 DF 에 기록한다

빈발 참조 시퀀스 1≤j ≤ k에 대해 si+j = rj 인 i가 존재한다면 시퀀스 s1,…,sn 은 연속된 부분시퀀스로서 r1,…,rk를 포함한다고 한다. 예) BAHPM은 AHP를 포함한다. 빈발 k-참조시퀀스 - 연속된 부분 시퀀스로서 r1,…,rk를 포함하 는 최대순방향참조들을 가진 사용자의 수가 최소지지도를 넘는다면, 이러한 k-참조시 퀀스 r1,…,rk 를 빈발 k-참조시퀀스 라 한다.

구현 알고리즘 FS (Full-Scan) 알고리즘 DHP 알고리즘 응용 CHT_FS(Compound Hash Tree_FS) 알고리즘 FS에 복합 해쉬 트리 적용 TPADE (Traversal Pattern Discovery using Equivalence Classes) 알고리즘 SPADE 알고리즘 응용

FS(Full-Scan) 알고리즘 DHP(Direct Hashing and Pruning) 응용 결합(Join) 효과적인 빈발 항목 집합 생성 효과적인 트랜잭션 데이터베이스 전지(Pruning) 결합(Join) 빈발k-1 A B C D A B C A B D 그림2. 결합(연관 규칙) B C D 그림 3. 결합(순회 패턴) 후보k

FS(Full-Scan) 알고리즘 Lk : 모든 빈발 k-참조 시퀀스들의 집합 Ck : 모든 후보 k-참조 시퀀스들의 집합 1) DF를 스캔하여 L1 얻고 각 후보 2-참조 시퀀스 의 빈도수를 세기 위한 해쉬테이블(H2)을 만듬 2) DHP에서와 같이 k=2 일때 부터 시작하여 이전 단계에서 얻어진 해쉬테이블 카운트를 기반으 로 Ck 생성, 빈발 k-참조 시퀀스들의 집합 찾음 - Ck 에서 k-항목집합들의 한 항목으로 사용되진 수를 구하여 최소지지도 이하로 사용된 항목은 Purning함으로써 트랜잭션 DB 의 크기 줄임 - 후보 (k+1)-참조 시퀀스를 찾기 위한 해쉬테이 블 생성

CHT_FS 알고리즘 복합 해쉬 트리(Compound Hash Tree) Cm,Cm+1,…,Cm+n 을 동시에 생성한 후, 하나의 복합 해쉬트리를 생성, 한번의 DB 스캔으로 Lm,Lm+1, …,Lm+n 을 찾음 일반적인 해쉬 트리 : 검색되어야 할 레코드가 외부 노드에만 저장 복합 해쉬 트리 : 검색되어야 할 레코드가 내부 노드에도 저장 장점 : 반복적인 해쉬트리의 생성 및 데이터베이스 스캔, 후보 빈발 항목집합의 발생 수 계산을 줄임 트리 탐색 비용 감소 단점 : 후보항목집합 생성은 FS에 비해 비효과적

그림 4. C2 = {AB, AC, BC, BD, CD}, C3= {ABC, BCD}의 해쉬 트리 일반 해쉬 트리 AB AC BC BD CD C A B D ABC BCD 그림 4. C2 = {AB, AC, BC, BD, CD}, C3= {ABC, BCD}의 해쉬 트리

그림 5. C2={AB,AC,BC,BD,CD}, C3={ABC,BCD}의 복합 해쉬 트리

TPADE 알고리즘 SPADE (Sequential Pattern Discovery using Equivalence classes) 알고리즘 응용 동치 클래스(Equivalence Classes)를 이용하여 원문제를 주 메모리상에서 독립적으로 수행가능한 부문제로 나눔 수직 식별자 리스트(Vertical id-list) 데이터베이스 형식 간단한 id-list intersection으로 모든 빈발시퀀스 찾음 많아야 세 번의 데이터베이스 스캔 필요

빈발 참조 시퀀스를 찾는 과정 전처리 과정 빈발 1-참조 시퀀스(F1) 찾기 빈발 2-참조 시퀀스(F2) 찾기 빈발 k-참조 시퀀스(Fk) 찾기 1) 빈발 (k-1)-참조 시퀀스를 이용한 동치 클래스 분해 2) 각 동치 클래스에서 빈발 k-참조 시 퀀스 생성

전처리 과정 1단계에서 얻어진 MFR_DB 형식을 수평에서 수직으로 변환 -> 지지도를 쉽게 구할 수 있도록 수평 DB : transaction 단위로 저장 (UID, TID, # of ITEMS, ITEMS) 수직 DB : item 단위로 DB에 저장 ( ITEM, # of LIST, (UID TID LOC)LISTS) CTL _ list

그림 6. 수평(Horizontal) DB의 예 UID TID # of items ITEMS 1 3 C D A 2 5 A B C D F A B F D C 4 A C B 6 7 A B C F 8 A B 9 C B A

그림 7. 수직(Vertical) DB의 예 ITEM # of lists (UID TID LOC) lists A 9 (1 1 3) (1 2 1) (1 3 1) (1 4 1) (2 5 1) (2 6 3) (3 7 1) (3 8 1) (4 9 3) B 7 (1 2 2) (1 3 2) (1 4 3) (2 5 2) (3 7 2) (3 8 2) (4 9 2) C 8 (1 1 1) (1 2 3) (1 3 5) (1 4 2) (2 5 5) (2 6 1) (3 7 3) (4 9 1) D 5 (1 1 2) (1 2 4) (1 3 4) (2 5 4) (2 6 2) E F 4 (1 2 5) (1 3 3 ) (2 5 3) (3 7 4)

F1 과 F2 찾기 빈발 1-참조 시퀀스(F1) - 한번의 DB 스캔으로 주어진 수직 식별자 리스트 DB 로부터 모든 빈발-1 참조 시퀀스를 찾음 빈발 2-참조 시퀀스(F2) - 수직 식별자 리스트 DB형식을 다시 수평 형식으로 변환(on-the-fly방식)하여 기존의 방식으로 계산

그림 8. SPADE에서의 Equivalence Class의 예 빈발 k-참조 시퀀스(Fk) 빈발 (k-1)-참조 시퀀스의 동치클래스 이용 SPADE 알고리즘에서의 동치 클래스 [ε ∈ Fk-1] = { α ∈ Fk | Pk-1 (α)= ε } [ε].l1 = (ε -> α) [ε].l2 = (ε α) [A] l1 l2  AF AB [B] l1 l2 BA BF [D] l1 l2 DF  DB [F] l1 l2 FA FB FD 그림 8. SPADE에서의 Equivalence Class의 예

그림 9. TPADE에서의 Equivalence Class의 예 [ε∈Fk-1] = {α∈Fk |Drop1(α)=ε ∨ Dropk(α)=ε } [ε].l1 = { (α ε) } [ε].l2 = { (ε α) } [A] l1 l2 DA AB AC [B] l1 l2 AB BC CB BF [D] l1 l2  DA DC [F] l1 l2 BF FD CF 그림 9. TPADE에서의 Equivalence Class의 예

빈발 k-참조 시퀀스 생성 생성된 동치클래스들은 메모리 상에서 각각 독립적으로 수행됨 각 동치클래스에서 빈발시퀀스 찾는 과정 1) l1과 l2를 접합(Concatenation), 새로운 후보 참조 k-시퀀스의 Item list를 얻음 2) 얻어진 후보 시퀀스의 지지도 계산하여 빈발 시퀀스 얻음

빈발 k-참조 시퀀스 생성예 F2 의 CTL_list ITEM SUP CTL _ list AB 5 (121)(131)(251)(371)(381) BC 2 (122)(372) BF (132)(252) CB (142)(491) CD 3 (111)(123)(261) DA (112)(262) DC (134)(254) FD (133)(253)

F3 의 CTL_list EC ITEM SUP CTL _ list A DAB NULL B ABC 2 (121)(371) ABF NULL B ABC 2 (121)(371) ABF (131)(251) CBF C BCD 1 (122) DCB D CDA (111)(261) FDA FDC (133)(253) F BFD (132)(252)

EC별 접합결과 F4 의 CTL_list [A] [B] [C] [D] [F] [DA] [BF] [CB] [AB] [BC]  ABC ABF [BC] l1 l2  BCD [CD] l1 l2 BCD CDA [DC] l1 l2 FDC  [FD] l1 l2 BFD FDC EC ITEM SUP CTL _ list FD BFDC 2 (132)(252) CD BCDA NULL

실험 환경 및 실험 데이터 실험 환경 실험 데이터 CPU : Pentium II 366MHz 주 메모리 : 256MB 운영 체제 : Windows NT workstation 4.0 구현 언어 : Visual C++ 6.0 실험 데이터 성신여자대학교 웹 로그 파일 적용 데이터 수집 기간: 1999.10 .26~ 1999. 11.28 (1,000,000개, 2,000,000개, 3,000,000개 트랜잭션)

웹 엑세스 로그 데이터 수집기간 : 1999.10 .26~ 1999. 11.28 210.111.128.244 - - [26/Oct/1999:13:34:59 +0900] "GET/~plan/rule/r4_1.htm HTTP/1.1" 200 115920 210.111.128.244 - - [26/Oct/1999:13:35:00 +0900] "GET/~plan/img/first.gif HTTP/1.1" 200 427 210.125.93.41 - - [26/Oct/1999:13:35:01 +0900] "GET/Org HTTP/1.0" 302 - 그림 10. 성신여대의 웹 액세스 로그 데이터의 예

그림 11. User IP의 매핑 테이블과 Item의 매핑 테이블 데이터의 전처리 (Cont’d) 그림 11. User IP의 매핑 테이블과 Item의 매핑 테이블

그림 12. 전처리 후 웹 사용자 트랜잭션 데이터베이스의 부분 데이터의 전처리 UID 액세스한 항목 번호 18 2 2685 25333 25350 25378 19 2 893 897 898 900 919 2077 2698 12679 21915 25393 20 2 893 900 919 2077 2084 2104 2685 2698 12937 14220 20661 20798 21939 21952 25333 25350 25352 25378 25393 21 2 152 900 939 2685 25333 25350 25352 25369 25378 25387 22 2 2685 25333 25350 25352 25378 그림 12. 전처리 후 웹 사용자 트랜잭션 데이터베이스의 부분

순회 패턴의 예 (최소지지도 : 0.25%) 번호 후처리된 순회패턴 지지도(%) (1) <(/Apply/) (/Apply/images/eyes.gif) (/cgi-bin/bbs /Counter/Count.cgi?frgb=69;139;116&dd=D|ft=3|df=SWU_job.dat) (/images/apply.jpg)> 0.27 (2) <(/BBS/home.html)(/BBS/cgi-bin/bbs/A/listboard) (/BBS/cgi-bin/bbs/B/listnews) (/BBS/cgi-bin/bbs/B/suggesteditor)> 0.25 (3) <(/BBS/) (/BBS/menu.html) (/BBS/home.html) (/BBS/images/TBALL.GIF)> 0.40 (4) <(/BBS/home.html) (/BBS/images/TBALL.GIF) (cgi-bin/bbs/Counter/Count.cgi?ft=3&frgb=255; 215;0 &df=home.dat) (/images/bbs1.jpg)> 0.30

그림 13. FS, CHT_FS, TPADE 의 최소 지지도별 탐사 시간 비교 (1,000,000번 액세스) 성능 비교 그림 13. FS, CHT_FS, TPADE 의 최소 지지도별 탐사 시간 비교 (1,000,000번 액세스)

그림 14. FS, CHT_FS, TPADE 의 최소 지지도별 탐사 시간 비교 (2,000,000번 액세스) 성능 비교 그림 14. FS, CHT_FS, TPADE 의 최소 지지도별 탐사 시간 비교 (2,000,000번 액세스)

TPADE의 성능이 좋은 이유 ITEM_list 상에서 간단한 결합연산만을 사용 복잡한 해쉬트리 자료구조를 사용하지 않고 오직 두 리스트의 선형탐색만을 필요로 하므로, 사용자 부분 시퀀스를 생성, 탐색하는 오버헤드 없음. TPADE는 패턴 길이에 관계없이 오직 세번의 DB 스캔만을 하므로 최소지지도가 낮을수록, 더욱더 많고 패턴 길이가 더욱더 길어진 빈발참조시퀀스들이 탐사됨.

FS와 CHT_FS의 결과 비교 k 1 2 3 4 5 시간(초) FS 알고리즘 Ck Lk U_N CHT_FS 알고리즘 170 837 62 1441.40 Lk 89 119 47 8 U_N 149780 102172 93479 18531 CHT_FS 알고리즘 6434 51406 1191.35 - 78604 3,000,000번 액세스, 최소 지지도 : 1%

그림 15. FS와 CHT_FS의 최소 지지도별 탐사 시간 비교 (1,000,000번 액세스)

그림 16. FS와 CHT_FS의 최소 지지도별 탐사 시간 비교 (2,000,000번 액세스)

결론 및 향후과제 웹 로그 파일에서 순회 패턴 탐사 각 순회 패턴 탐사 알고리즘 성능 비교 구현 알고리즘 : FS, CHT_FS, TPADE 이용 가치 : 웹 페이지 디자인의 향상 상업적인 목적으로 이용 (예: 광고 배너의 위치 선정 등) 각 순회 패턴 탐사 알고리즘 성능 비교 향후과제 - 웹로그 파일의 세밀한 전처리 - 효율적인 순회 패턴 탐사 알고리즘 연구 - 실제 대용량 데이터에 적용 - 사용자 인터페이스 개발