웹 로그 파일에서 순회 패턴 탐사 알고리즘 성신여대 하미라 석사논문

Slides:



Advertisements
Similar presentations
법의 이념과 철학의 이해 법의 이념은 무엇일까 ? 정의 : 각자에게 각자의 몫을 주는 것 - 평등의 의미가 내포되어 있음 법적 안정성 : 법의 규정이 명확하고 잦은 변경 이 없어야 함 개인의 자유와 권리를 공공복지와 조화롭게 추구 – 사회질서와 안전유지 + 사회정의.
Advertisements

제주특별자치도교육청. 목 차 일상생활 속에서의 정보보안 안전한 컴퓨터 사용  보안업데이트 자동설정  가짜 백신 프로그램 주의  믿을 수 있는 웹사이트만 접속  자동 로그인 기능 사용 안함  사용 후 반드시 로그아웃 확인 
이혁재 /KASA NoSQL. 요약 NoSQL 소개 데이타베이스 관련 문서 대상 : 클라이언트 프로그래머 NoSQL 소개 데이타베이스 관련 문서 대상 : 클라이언트 프로그래머.
인 알고 보면 더 재미있는 권 여 행 국제앰네스티 인권교육 패키지. 어떻게 할까요? ① 4-6 명이 게임에 참여합니다. ② 액션키트에 있는 주사위와 자신의 말을 준비합니다. ③ 가위바위보로 게임 순서와 말을 정하세요. ④ 주사위를 굴려 나온 숫자만큼 자신의 말을 이용해.
유클리드 이후의 그리스 수학. 아르키메데스 ( 기원전 ) 죽은 뒤 묘비위에 원기둥에 내접한 구 모형을 만 들어 달라고 저서 : 평면기하에 관한 것 ① 원의 측정 - π 를 계산 하는 고전적인 방법을 처음시도 ② 포물선의 구적법 - 24 개의 명제로 구성,
열왕기 상하는 중요하다 ! 왜 ? 시가 3 권 예언서 12 원 열왕기 상하는 중요하다 ! 대라느스 단겔학슥말.
식품사업부 8 월 기도회 2006 년 8 월 9 일. 7 월 감사제목 1. 7 월에도 매장에서 안전사고와 고객클레임 없이 무사히 영업을 하게 해주셔서 감사 합니다. 2. 지난 번 폭우때 매장의 안전과 재산을 지켜주시고 직원들의 건강을 지켜주셔서 감사합니다. 3. 어려운.
국제통상 원성민 국제통상 장홍순 국제통상 이상문. 수출 거래에 수반되는 여러위험 가운데 일반적인 보험으로 구제하기 힘든 위험을 보상해 줌으로써 수출자 생산자 또는 수출 자금을 대출해준 금융기관이 입게되는 손실을 보상해주는 비영리 정책 보험. 수출자 생산자 금융기관.
Marketing Research 1  군집분석의 개념과 적용  군집분석 (cluster analysis) : 다수의 대상들 ( 소비자, 제품, 기타 ) 을 그들이 소유하는 특 성을 토대로 유사한 대상들끼리 그룹핑하는 다변량 통계기법 → 군집내의 구성원들은 가급 적.
CHAPTER 5 KARNAUGH MAPS( 카노 맵 ) This chapter in the book includes: Objectives Study Guide 5.1Minimum Forms of Switching Functions 5.2Two- and Three-Variable.
2014전망&쟁점.
지적기초측량 경일대학교/부동산지적학과.
(2) 고대 국가의 성립  1) 고대 국가의 성격    ① 중앙 집권 체제      - 국왕의 지위 강화, 부족장 세력의 통합,
1. 준비 사항 설치할 컴퓨터의 사양 확인 하드웨어와 Windows Server 2003의 호환성 확인
1. 아동 권리 및 아동 학대의 이해.
Let’s Speak English Well
2015 담당 강사 : 정세진 중국 명문 감상 2015 담당 강사 : 정세진
데이터 모델링 방법론 2003년 03월.
강소농의 성공적 추진을 위한 농업경영담당자의 역할 농촌진흥청 기술경영과 강진구.
해시 함수.
우리나라 수출농업의 현황과 문제점 김자경.
스타일리스트 양성과정 광주보건대학 피부미용과.
암 보다 더 무서운 당뇨 2010년 [아시아경제 강경훈 기자 ].
실전 데이터모델링 & 데이터베이스 설계와 구축
연습 문제 풀이 E BF F8 85 A5 E5 9B 37 A5 E5 9B FF 버전 헤더길이 서비스유형 전체길이
2007. Database Term Project Team 2 윤형석, 김희용, 최현대 우경남, 이상제
E-평가문제은행은 자료가 준비 중인 것으로 보입니다.
2013년 11월 건강보험심사평가원 의약품관리종합정보센터
Ⅷ. 도형의 닮음 1. 도형의 닮음 2. 삼각형과 평행선 3. 닮음의 응용.
인류의 분산 언어의 대 혼잡시기 창조,타락 홍수 바벨탑사건 아브라함 모세 BC 고조선 하/은/주 (창 11:7,9) 『[7] 자, 우리가.
에너지 운동량 방법: 일과 에너지법칙 1. 상자들이 초기속도 vo로 컨베이어 벨트로 운반되어 A에서 미끄러져서 B에서 떨어진다. μk= 0.40이고, 상자가 2.4m/s로 B점에서 떨어질 때 컨베이어 벨트의 속도를 구하라.
Information Retrieval (Chapter 5: 질의연산)
도덕 1학년 1학기 2. 개성신장과 인격 도야:인물학습 석가모니 인물학습 -석가모니.
제 11장 교락법과 일부실시법.
Right Now 담당 교수 : 문양세 교수님 팀 원 : 김원모(팀장) 우덕령, 김승선, 김종원, 문경민
-공인노무사 김 완 식 -외식업중앙교육원 노무관리 교수 -열린인사 노무법인 대표 노무사 (열린 세무 회계 고문)
이재상 기본 논리회로와 불의 대수 이재상
서울아산병원 의학통계학과 울산의대 예방의학교실 이무송
우리생활속의 확률 이용사례탐구 한림초등학교영재학급 6학년 김수민.
알기쉬운 시설공사(2) 경상북도교육청 이형주.
3. 게이트레벨 최소화.
평행사변형의 성질 사각형 ABCD 사각형 ABCD → 기호: □ABCD 대변: 마주 보는 변 대각: 마주 보는 각
정보처리기사 8조 신원철 양진원 유민호 이기목 김다연 윤현경 임수빈 조현진.
김포 한강베네치아 상가분양 3층~5층 오피스텔 226세대 1층~2층 상가 분양문의 : 이효철( )
물류단지 총량제 폐지 이후 물류시설 공급정책 방향 국 토 교 통 부.
Ⅶ. 원 의 성 질 1. 원 과 직 선 2. 원 주 각 3. 원 과 비 례.
ERP 솔루션 목차 회사소개 사업분야 솔루션 소개.
도구를 사용할 때의 일(2) 도구를 사용해도 마찬가지야. 지레 지레를 사용할 때의 일.
탐구하는 수학연습문제 수학 8나 대한 114쪽 Ⅲ. 도형의 닮음
쿰란 쿰란 와디 항공촬영 .
동절기 가스사고 예방 ㅇㅇㅇ 도시가스 - 가스보일러 CO중독사고 관련 (금) 동절기 CO중독 예방 및
실전 프로젝트: 홈페이지 구축 시트콤 프렌즈 팬 사이트 구축하기.
평 면 도 형 도형의 작도 삼각형의 작도와 결정조건 도형의 합동 작도와 삼각형의 합동 학습내용을 로 선택하세요
7세그먼트 표시기.
비정규직법의 이해 노 동 부.
제7장 수학과에서의 평가 7.1 평가과정의 본질 7.2 평가과정의 단계
자전거발전기 만들기 자전거 발전기 부품 조립에서 완제품까지.
진리 나무 Truth-tree  ∧ ∨ → ↔  =.
동영상 시청
(Association Rules Mining)
수학 8나 대한 64쪽 II.도형의 성질 2. 사각형의 성질 §1. 평행사변형 (17/24) 평행사변형이 되는 조건.
엔화 대환/대출 자금용도 대상 이자 차액 효과 (A,B,C) 환율 리스크 헷징 (A,B) 엔화의 평균환율 (A,B,C)
매물장 로그인 직원을 미리 생성하시면 직원 ID로 로그인 가능.
제 4장 그리디 알고리즘.
국립중앙의료원 messenger User Guide Ver 3.2.
2012년 9월 16일 바벨탑 사건과 셈의 후손들의 족보 ▣말씀:창세기 11:1-32 예 수 복 된 교 회.
논증의 타당성/부당성 검증 Verification/Falsification
매스펀 문제 2.
표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =.
Presentation transcript:

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