(Association Rules Mining)

Slides:



Advertisements
Similar presentations
연천 새둥지마을 체재형 주말농장 준공식 초청장 오시는 길 주제 일시 장소 21C 경기농촌희망심기 2005년 제1기 교육수료마을
Advertisements

SPARCS Wheel Seminar Mango X Sugoi
출석수업 자료 교과서 범위: 제1장-4장.
10월 충북노회 남선교회 순회 헌신예배 묵 도 기 도 성 경 봉 독 특 송 찬 양 설 교 찬양 / 봉헌 봉 헌 기 도
글에 나타난 시대적 사회적 배경을 파악할 수 있다. 배경 지식과 의미 해석의 관련성을 이해할 수 있다.
패널자료 분석
라오디게아 교회의 교훈 본문 계 3: ○라오디게아 교회의 사자에게 편지하라 아멘이시요 충성되고 참된 증인이시요 하나님의 창조의 근본이신 이가 이르시되 15. 내가 네 행위를 아노니 네가 차지도 아니하고 뜨겁지도 아니하도다 네가 차든지 뜨겁든지 하기를 원하노라.
한알Ⅱ「더불어 살기」전국대회 일정표 날짜 시간 7월 26일(목) 7월 27일(금) 7월 28일(토) 7월 29일(일)
2013학년도 전라북도고등학교신입생 입학전형 기본계획
선거관리위원회 위원 공개모집 4차 공고 제4기 선거관리위원회를 구성하는 위원 모집의
2015학년도 1학기 버디 프로그램 오리엔테이션 (목) 16:00.
열왕기하 1장을 읽고 묵상으로 예배를 준비합시다..
오늘의 학습 주제 Ⅱ. 근대 사회의 전개 4. 개항 이후의 경제와 사회 4-1. 열강의 경제 침탈 4-2. 경제적 구국 운동의 전개 4-3. 사회 구조와 의식의 변화 4-4. 생활 모습의 변화.
전도축제 계획서 *일시 : 2013년 4월 21, 28일 주일 (연속 2주)
2009학년도 가톨릭대학교 입학안내.
한국 상속세 및 증여세 과세제도 한국 국세공무원교육원 교 수 최 성 일.
중세시대의 의복 학번 & 이름.
다문화가정의 가정폭력의 문제점 연세대학교 행정대학원 정치행정리더십 2학기 학번 이름 홍 진옥.
이공계의 현실과 미래 제조업 立國 / 이공계 대학생의 미래 준비
신앙의 기초를 세우는 중고등부 1부 대 예 배 : 11 : 00 ~ 12 : 층 본당
신앙의 기초를 세우는 중고등부 1부 대 예 배 : 11 : 00 ~ 12 : 층 본당
◆ 지난주 반별 출석 보기 ◆ 제 56 권 26호 년 6월 26일 반 선생님 친구들 재적 출석 5세 화평 김성희 선생님
第1篇 자치입법 개론.
교직원 성희롱·성폭력·성매매 예방교육 벌교중앙초등학교 박명희
제5장 새로운 거버넌스와 사회복지정책 사회복지정책이 어떤 행위자에 의해 형성되고 집행되는지, 어떤 과정에서 그러한 일들이 이루어지는지, 효과적인 정책을 위해서는 어떤 일들이 필요한지 등을 본 장에서 알아본다 개인들이 생활을 개선하는 가장 효과적인고 궁극적인 방법은 개별적.
임상시험 규정 (최근 변경 사항 중심으로) -QCRC 보수 교육 과정 전달 교육
서울특별시 특별사법경찰 수사 송치서류 유의사항 서울특별시 특별사법경찰과 북부수사팀장 안   진.
특수학교용 아동학대! 제대로 알고 대처합시다..
사회복지현장의 이해 Generalist Social Worker 사회복지입문자기초과정 반포종합사회복지관 김한욱 관장
학교보건 운영의 실제 한천초등학교 이 채 금.
제 출 문 고용노동부 귀중 본 보고서를 ’ ~ ‘ 까지 실시한 “근로감독관 직무분석 및 교육프로그램 개발에 관한 연구”의 최종보고서로 제출합니다  연구기관 : 중앙경영연구소  프로젝트 총괄책임자 : 고병인 대표.
학습센터란? 기도에 관해 배울 수 있는 다양한 학습 코너를 통하여 어린이들이 보다 더 쉽게 기도를 알게 하고, 기도할 수 있게 하며, 기도의 사람으로 변화될 수 있도록 하는 체험학습 프로그램이다. 따라서 주입식이지 않으며 어린이들이 참여할 수 있는 역동적인 프로그램으로.
Digital BibleⅢ 폰속의 성경 디지털 바이블 2008년 12월 ㈜씨엔커뮤니케이션 ㈜씨엔엠브이엔오.
후에 70인역(LXX)을 좇아 영어 성경은 본서의 중심 주제인 “엑소도스”(출애굽기)라 하였다.
성 김대건 피츠버그 한인 성당 그리스도왕 대축일 공지사항
예배에 대하여.
말씀 듣는 시간입니다..
하나님은 영이시니 예배하는 자가 신령과 진정으로 예배할지니라.
지금 나에게 주신 레마인 말씀 히브리서 13장 8절.
예수의 제자들 담당교수 : 김동욱.
Lecture Part IV: Ecclesiology
KAINOS 날마다 더하여지는 Kainos News 이번 주 찬양 20 / 300 – 20개의 셀, 300명의 영혼
예배의 외부적인 틀II - 예배 음악 조광현.
영성기도회 렉시오 디비나와 묵상기도 2.
성인 1부 성경 공부 지도목사: 신정우 목사 부 장: 오중환 집사 2010년. 5월 9일
남북 탑승객 150명을 태운 디젤기관차가 2007년 5월 17일 오전 경의선 철길을 따라 남측 최북단 역인 도라산역 인근 통문을 통과하고 있다. /문산=사진공동취재단.
성경 암송 대회 한일교회 고등부 (일).
천주교 의정부교구 주엽동본당 사목협의회 사목활동 보고서
III. 노동조합과 경영자조직 노동조합의 이데올로기, 역할 및 기능 노동조합의 조직형태 노동조합의 설립과 운영
여수시 MICE 산업 활성화 전략 ( 중간보고 )
1. 단위사업 관리, 예산관리 사업설정 (교직원협의/의견수렴) 정책 사업 학교 정책 사업 등록 사업 기본정보 목표 설정
※과정 수료자에 한하여 수강료의 80~100% 차등 환급함
평생학습중심대학 프로그램 수강지원서 접수안내 오시는 길 관악구&구로구민을 위한 서울대학교 -- 접수 일정 및 방법 안내--
서비스산업의 선진화, 무엇이 필요한가? 김 주 훈 한 국 개 발 연 구 원.
기존에 없던 창업을 하고 싶은데, 누구의 도움을 받아야 할지 모르겠어요
전시회 개요 Ⅰ. 전시명칭 개최기간 개최장소 개최규모 주 최 참 관 객 현 지 파 트 너 General Information
Homeplus 일 家 양 득 프로그램 소개 2015년 12월.
Home Network 유동관.
통신이론 제 1 장 : 신호의 표현 2015 (1학기).
I. 기업과 혁신.
Chapter 4 – 프로그래밍 언어의 구문과 구현 기법

ESOCOM – IPIX 고정IP서비스 제안서 Proposer ㈜이소컴.
화장품 CGMP 한국콜마㈜.
초화류 종자 시장 규모 100억원 이상(추정, 생산액의 10%정도 차지)
COMPUTER ARCHITECTIRE
[ 한옥 실측 ] 1. 약실측 2. 정밀실측 조선건축사사무소.
14. 컴파일러 자동화 도구 스캐너 생성기 파서 생성기 코드 생성의 자동화
A제조용수/B환경관리/C시설관리 ㈜ 에이플러스 코리아
Introduction to Network Security
Presentation transcript:

(Association Rules Mining) 연관규칙 마이닝 (Association Rules Mining) 2014년 가을학기 강원대학교 컴퓨터과학전공 문양세

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴

연관규칙 마이닝 (Association Rules Mining) 주어진 트랜잭션 집합으로부터, “어떤 아이템(들)이 나타날지를 다른 아이템(들)의 발생으로부터 예측하는 규칙”을 찾는 작업이다. (Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction) 장바구니 분석 (Market Basket Analysis) Market-Basket transactions Example of Association Rules {Diaper}  {Beer}, {Milk, Bread}  {Eggs,Coke}, {Beer, Bread}  {Milk},

연관규칙의 응용 사례 (1/4) 장바구니 분석 (Market Basket Analysis) Association Rules Mining 장바구니 분석 (Market Basket Analysis)

연관규칙의 응용 사례 (2/4) Association Rules Mining Medical Diagnosis

연관규칙의 응용 사례 (3/4) Association Rules Mining Protein Sequences

연관규칙의 응용 사례 (4/4) Association Rules Mining 장바구니 분석 (Census Data)

빈발 항목집합 (Frequent Itemset) (1/2) Association Rules Mining 항목집합 (Itemset) 한 개 이상의 항목(들)의 집합 예: {Eggs}, {Milk, Bread, Diaper} k-항목집합 (k-itemset): k개 항목을 가지는 항목집합 지지도 카운트(Support Count):  항목집합이 (트랜잭션 DB에) 나타나는 횟수 예: {Eggs} = 1, {Milk, Bread, Diaper} = 2

빈발 항목집합 (Frequent Itemset) (2/2) Association Rules Mining 지지도(Support): s 항목집합이 나타나는 트랜잭션의 비율 예: s{Eggs} = 1/5 = 0.2 s{Milk, Bread, Diaper} = 2/5 = 0.4 빈발 항목집합(Frequent Itemset) 지지도가 주어진 임계치 minsup보다 큰 항목집합 예: minsup = 0.3이라면, {Eggs}은 빈발하지 않으며, {Milk, Bread, Diaper}은 빈발하다.

연관규칙 (Association Rules) Association Rules Mining 연관규칙이란? X와 Y가 항목집합이라 할 때, X  Y 형태로 나타나는 함축 표현(implication expression) 예: {Milk, Diaper}  {Bread} 연관규칙의 평가척도 지지도(Support): s X와 Y를 함께 포함하는 트랜잭션 비율 규칙이 얼마나 중요한가? 유용한가? (낮은 지지도의 규칙은 우연성이 기인할 수 있음) 신뢰도(Confidence): c X를 포함한 트랜잭션 중에 Y가 나타나는 비율 규칙이 얼마나 믿을 만 한가? (가정과 결론이 얼마나 타이트한 관련이 있는지를 나타냄)

연관규칙 마이닝이란? 연관규칙 마이닝 (Association Rules Mining): 간단히 ARM이라 함 트랜잭션들의 집합이 주어졌을 때, 연관규칙 마이닝이란 다음 조건을 만족하는 모든 규칙을 찾는 작업이다. support  minsup (support = 항목집합의 지지도, minsup = 주어진 최소지지도) confident  minconf (confidence = 규칙의 신뢰도, minconf = 주어진 최소신뢰도) 주먹구구 방식(Brute-force approach) 가능한 모든 연관규칙을 나열한다. 각 규칙의 지지도와 신뢰도를 계산한다. 주어진 minsup, minconf를 만족하지 않는 규칙을 제거(prune)한다.  엄두도 못 낼 정도로 계산이 복잡함! (Computationally prohibitive!)

예제를 통한 관찰… Example of Rules: Observations Association Rules Mining Example of Rules: {Milk,Diaper}  {Beer} (s=0.4, c=0.67) {Milk,Beer}  {Diaper} (s=0.4, c=1.0) {Diaper,Beer}  {Milk} (s=0.4, c=0.67) {Beer}  {Milk,Diaper} (s=0.4, c=0.67) {Diaper}  {Milk,Beer} (s=0.4, c=0.5) {Milk}  {Diaper,Beer} (s=0.4, c=0.5) Observations 모든 규칙은 {Milk, Diaper, Beer}의 동일한 항목집합에서 비롯되었다. 동일한 항목집합에서 나온 규칙들은 지지도는 동일하나 신뢰도는 다를 수 있다.  지지도와 신뢰도를 분리하여 규칙을 마이닝할 필요가 있다.

ARM 과정 2-단계 접근법  빈발 항목집합의 생성이 여전히 계산 불가능하게 복잡하다. Association Rules Mining 2-단계 접근법 빈발 항목집합 생성(Frequent Itemset Generation): support  minsup을 만족하는 모든 항목집합을 생성한다. 연관규칙 생성(Rule Generation): 각 빈발 항목집합을 두 개의 항목집합으로 분리하여 confidence  minconf를 만족하는 규칙들을 찾아낸다.  빈발 항목집합의 생성이 여전히 계산 불가능하게 복잡하다.

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴

d개 항목에 대해, 2d개의 항목집합을 고려해야 한다.  부분집합의 개수 항목집합 격자 Association Rules Mining d개 항목에 대해, 2d개의 항목집합을 고려해야 한다.  부분집합의 개수

빈발 항목집합 생성 Association Rules Mining 주먹구구 접근법 격자의 모든 항목집합이 후보 빈발 항목집합(candidate frequent itemset)이 된다. 트랜잭션 데이터베이스를 스캔하면서 각 후보에 대해 지지도를 카운트한다. 카운트를 위해, 모든 후보에 대해서 각 트랜잭션을 매치한다. 복잡도  O(NMw)  Too Expensive since M = 2d !!!

계산 복잡도 분석 항목이 d개 주어졌을 때, If d=6, R = 602 rules 가능한 항목집합의 개수 = 2d Association Rules Mining 항목이 d개 주어졌을 때, 가능한 항목집합의 개수 = 2d 가능한 연관규칙의 개수 = 3d  2d+1  1 If d=6, R = 602 rules

빈발 항목집합 생성 전략 후보 개수(M)를 줄여라. 트랜잭션 개수(N)를 줄여라. 비교 횟수(MN)를 줄여라. Association Rules Mining 후보 개수(M)를 줄여라. 모두 고려하면, M = 2d M을 줄이기 위해 전지 기술(pruning techniques)를 사용하라. 트랜잭션 개수(N)를 줄여라. 항목집합이 증가할 수록 트랜잭션 개수를 줄여라. DHP와 수직 기반(vertical-based) 마이닝 알고리즘을 사용하라. 비교 횟수(MN)를 줄여라. 후보와 트랜잭션을 저장하기 위하여 효율적인 자료구조를 사용하라. 모든 후보에 대해 모든 트랜잭션을 매치(match)시켜볼 필요는 없다.

후보 개수 줄이기 Apriori 원리 Apriori 원리가 성립하는 이유는 다음의 지지도 성질 때문이다. Association Rules Mining Apriori 원리 어떤 항목집합이 빈발하다면, 그 항목집합의 모든 부분집합도 빈발하다. 예: {Milk, Bread, Diaper}가 빈발 항목집합이면, 이의 부분집합인 {Milk, Bread}, {Bread, Diaper} 등도 빈발 항목집합이다. Apriori 원리가 성립하는 이유는 다음의 지지도 성질 때문이다. 어떤 항목집합의 지지도는 그 부분집합들의 지지도를 넘을 수 없다! 이는 지지도가 anti-monotone 성질을 가지기 때문이다. (a > b  f(a) < f(b))

Apriori 원리의 도식화 (1/2) Association Rules Mining

Apriori 원리의 도식화 (2/2) Association Rules Mining

Generate frequent itemsets of length 1 Apriori 알고리즘 Association Rules Mining Let k=1 Generate frequent itemsets of length 1 Repeat until no new frequent itemsets are identified Generate length (k+1) candidate itemsets from length k frequent itemsets Prune candidate itemsets containing subsets of length k that are infrequent Count the support of each candidate by scanning the DB Eliminate candidates that are infrequent, leaving only those that are frequent

비교 횟수 줄이기 Association Rules Mining 후보에 대한 카운트 트랜잭션 데이터베이스를 스캔 하면서, 각 후보 항목집합이 트랜잭션에 포함되어 있는지를 판단해야 한다.  많은 비교 연산이 필요함! 비교 횟수를 줄이기 위해, 후보들을 해쉬 구조(hash structure)에 관리한다.

빈발 항목집합  연관규칙 생성 Association Rules Mining 빈발 항목집합 L이 주어졌을 때, L의 공집합을 제외한 각 부분집합인 f(f  L)에 대해, 주어진 최소신뢰도(minconf)를 만족하는 f  L  f의 규칙이 찾아라. 만일 {A, B, C, D}가 빈발항목 집합이라면, 후보 규칙은 다음과 같다. ABC  D, ABD  C, ACD  B, BCD  A, A  BCD, B  ACD, C ABD, D  ABC, AB  CD, AC  BD, AD  BC, BC  AD, BD  AC, CD  AB 만일 |L| = k라면, 2k  2개의 후보 규칙이 생성된다. 전체집합(L  )과 공집합(  L)을 제외한 부분집합의 개수에 해당한다.

연관규칙 생성 빈발 항목집합으로부터 연관규칙을 효율적으로 생성하는 방법은? Association Rules Mining 빈발 항목집합으로부터 연관규칙을 효율적으로 생성하는 방법은? 신뢰도는 anti-monotone 성질을 가지지 않는다.  Apriori 성질 사용이 어려움 예: c(ABC  D) can be larger or smaller than c(AB  D) 그러나, 동일한 항목집합에서 생성된 규칙에 대해서는 anti-monotone 성질이 성립한다. 예: L = {A, B, C, D} c(ABC  D)  c(AB  CD)  c(A  BCD) 참고: 𝑐 𝐴𝐵𝐶→𝐷 = 𝜎({𝐴, 𝐵,𝐶,𝐷}) 𝜎({𝐴,𝐵,𝐶}) 𝑐 𝐴𝐵→𝐶𝐷 = 𝜎({𝐴, 𝐵,𝐶,𝐷}) 𝜎({𝐴,𝐵}) 𝑐 𝐴→𝐵𝐶𝐷 = 𝜎({𝐴, 𝐵,𝐶,𝐷}) 𝜎({𝐴})

Apriori 알고리즘에서 연관규칙 생성 Association Rules Mining

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴

최대(Maximal) 빈발 항목집합 Association Rules Mining 어떤 항목집합이 최대 빈발이라 함은(즉, 최대 빈발 항목집합이라 함은) 해당 항목집합의 어떠한 직접 모집합도 빈발하지 않는 경우를 말한다. (An itemset is maximal frequent if none of its immediate supersets is frequent) 최대 빈발 항목집합은 아주 긴 빈발 항목집합을 만들 때 유용하다. 일반적으로 짧은 항목집합은 규칙으로서 큰 의미가 없는 경우가 많다. 반면에, 긴 항목집합은 대개가 surprise한 연관규칙을 생성한다.

최대 빈발 항목집합 예제 Association Rules Mining

닫힌(Closed) 빈발 항목집합 Association Rules Mining 어떤 항목집합이 닫혀있다(즉, 닫힌 항목집합이라) 함은 해당 항목집합의 어떠한 직접 모집합과도 지지도가 같지 않은 경우를 말한다. An itemset is closed if none of its immediate supersets has the same support as the itemset 닫힌 항목집합이 빈발하면, 이를 닫힌 빈발 항목집합이라 한다.

닫힌 빈발 항목집합 (1/2) Association Rules Mining

닫힌 빈발 항목집합 (2/2) Association Rules Mining

최대 vs 닫힌 항목집합 Association Rules Mining

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴

연관규칙 평가 ARM 알고리즘은 너무 많은 연관규칙을 생성한다. Association Rules Mining ARM 알고리즘은 너무 많은 연관규칙을 생성한다. 대다수의 규칙들은 유용하지 않거나(흥미롭지 않거나, uninteresting) 중복되어 있다. 예를 들어, {A, B, C}  {D}와 {A, B}  {D}가 동일한 지지도/신뢰도를 갖는다면, 이들 두 규칙은 중복되었다 할 수 있다. (아마도 전자만 의미가 있을 것이다!) 유용성 척도(interestingness measure)는 찾아낸 규칙들을 제거(prune)하거나 순위(rank)를 매기는데 사용된다. 지지도와 신뢰도도 일종의 유용성 척도라 할 수 있다.

유용성 척도의 활용 Association Rules Mining

유용성 척도의 계산 Association Rules Mining 주어진 규칙 X  Y에 대해, 다음 분할표(contingency table)를 사용하여 다양한 유용성 척도를 계산할 수 있다.

신뢰도의 단점 Association Rules Mining

통계적 독립성 (Statistical Independence) Association Rules Mining

Lift/Interest Association Rules Mining

다양한 유용성 척도들… Association Rules Mining

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴

범주형, 연속형 속성 Association Rules Mining 연관규칙은 트랜잭션 데이터베이스에 적용되나, 실제로 기존의 많은 데이터베이스는 레코드(튜플)들의 집합이다. 레코드들은 대개 범주형 혹은 연속형 속성들로 구성된다. 범주형 속성(Categorical Attributes) 속성의 값이 범주(category)로 나타나는 경우를 일컬음 예제: 성별, 전공, 특기 연속형 속성(Continuous Attributes) 속성의 값이 숫자로 나타나는 경우를 일컬음 예제: 나이, 몸무게, 연봉

범주/연속형 속성의 연관규칙 사례 Example of Association Rule: Association Rules Mining Example of Association Rule: {Number of Pages [5,10)  (Browser=Mozilla)}  {Buy = No}

범주형 속성 처리 범주형 속성을 이진(binary) 변수로 변환한다. Association Rules Mining 범주형 속성을 이진(binary) 변수로 변환한다. 이진 변수: 트랜잭션에서는 어떤 속성이 나타나는지 나타나지 않던지 하는데, 이를 이진 속성(이진 변수)이라 함 각 속성과 그 값을 (속성 = 값)과 같이 새로운 “항목”으로 변환한다. 예제: Browser Type 속성을 다음과 같이 변환한다. Browser Type = Internet Explorer Browser Type = Mozilla Browser Type = Firefox

범주형 속성 처리 예제 Association Rules Mining

범주형 속성 처리의 이슈들 만일 속성이 많은 종류의 값을 가진다면? Association Rules Mining 만일 속성이 많은 종류의 값을 가진다면? 예를 들어, “국가”의 경우 200여 개 이상의 값을 가질 수 있다. 아마도 각 속성 값은 매우 낮은 지지도(support)를 가져, 빈발로 보이지 않을 것이다.  낮은 지지도 속성 값을 집계(aggregation)하여 표현한다. (예: 한국, 일본, 중국  동아시아 국가) 만일 속성 값의 분포가 심하게 쏠려있다면(highly skewed)? 예를 들어, 방문객의 95%는 “Buy = No”이다. 대부분 항목들이 “Buy = No”와 연관되어 나타날 것이다.  매우 빈발한 항목은 고려치 않는다.

연속형 속성 처리 여러 종류의 가능한 규칙들 연속형 속성을 처리하는 여러 방법 Association Rules Mining 여러 종류의 가능한 규칙들 Age[21,35)  Salary[70k,120k)  Buy Salary[70k,120k)  Buy  Age: =28, =4 연속형 속성을 처리하는 여러 방법 이산화 기반(Discretization-based) 방법 통계 기반(Statistics-based) 방법 Min-Apriori 기법

연속형 속성 처리 예제 Association Rules Mining

이산화(Discretization) 기반 방법 Association Rules Mining 비감독(unsupervised) 방법 Equal-width binning Equal-depth binning Clustering 감독(supervised) 방법

통계적 기반 방법, Min-Apriori 기법 Association Rules Mining 통계적 기반 방법 연관규칙의 결론부가 통계적 속성(평균, 표준편차 등)을 갖는 연속형 속성으로 나타남 예제: Salary[70k,120k)  Buy  Age: =28, =4 자세한 내용은 생략  교재 참조 Min-Apriori 기법 (비이산화 방법) 연속형 속성들 중에서 연관성을 찾는 방법  단어들 사이의 연관성 등

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴

개념 계층(Concept Hierarchy) Association Rules Mining 개념 계층: 특정한 영역에서 정의된 여러 개체들 또는 개념들의 다중 계층 조직이다. 주로, “is-a” 관계를 구성하는 taxonomy 형식을 갖는다.

다단계 연관 규칙 마이닝(1/3) 기본 성질: 개념 계층에 의해 지지도/신뢰도는 어떻게 변하나? Association Rules Mining 기본 성질: 개념 계층에 의해 지지도/신뢰도는 어떻게 변하나? If X is the parent item for both X1 and X2, then (X) ≤ (X1) + (X2) If (X1  Y1) ≥ minsup, and X is parent of X1, Y is parent of Y1 then (X  Y1) ≥ minsup, (X1  Y) ≥ minsup, (X  Y) ≥ minsup If conf(X1  Y1) ≥ minconf then conf(X1  Y) ≥ minconf

다단계 연관 규칙 마이닝(2/3) 접근법 1 이슈 상위 계층의 항목들을 각 트랜잭션에 추가하고, 기존 알고리즘을 사용한다. Association Rules Mining 접근법 1 상위 계층의 항목들을 각 트랜잭션에 추가하고, 기존 알고리즘을 사용한다. 예제 Original Transaction: {skim milk, wheat bread} Augmented Transaction: {skim milk, wheat bread, milk, bread, food} 이슈 상위 계층 항목은 다른 항목들에 비해서 높은 지지도 카운트를 갖는다.  만일, 주어진 지지도가 낮다면 너무 많은 규칙들이 생성될 것이다. 개념 계층이 복잡하다면, 트랜잭션의 차원이 높아지는 문제가 있다.

다단계 연관 규칙 마이닝(3/3) 접근법 2 이슈 먼저 최상위 계층에서 빈발 항목집합을 생성한다. Association Rules Mining 접근법 2 먼저 최상위 계층에서 빈발 항목집합을 생성한다. 다음으로 그 아래 계층에서 빈발 항목집합을 생성한다. 위 과정을 “만족할 만한 정도의 의미 있는 규칙”을 찾을 때 까지 반복한다. 이슈 많은 I/O가 필요하여 마이닝 시간이 무척 많이 걸리게 된다. 교차-단계의 연관 규칙을 찾지 못할 수 있다. (예를 들어, 가정부는 상위 계층, 결론부는 하위 계층인 연관 규칙을 찾지 못할 수 있다.)

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴

시퀀스 데이터 (Sequence Data) Association Rules Mining

시퀀스 데이터 예제 Association Rules Mining

시퀀스의 정의 Association Rules Mining 시퀀스란 원소(혹은 트랜잭션)들의 순서 리스트이다. (A sequence is an ordered list of elements (transactions)) 각 원소는 사건(혹은 항목)들의 모임을 포함한다. 각 원소는 특정 시간 혹은 장소를 속성으로 가질 수 있다. 시퀀스의 길이 |s|는 시퀀스에 포함된 원소의 개수이다. (|s| = the number of elements of the sequence s) k-시퀀스(k-sequence)란 k개 사건(항목)을 포함하는 시퀀스이다. (A k-sequence is a sequence that contains k events (items))

시퀀스의 예제 Association Rules Mining 웹 시퀀스 (Web Sequence) < {Homepage} {Electronics} {Digital Cameras} {Canon Digital Camera} {Shopping Cart} {Order Confirmation} {Return to Shopping} > 3-Mile Island에서 핵 사고의 원인이 된 사건들의 순서 < {clogged resin} {outlet valve closure} {loss of feedwater} {condenser polisher outlet valve shut} {booster pumps trip} {main waterpump trips} {main turbine trips} {reactor pressure increases}> 도서관에서 대여된 책들의 순서 <{Fellowship of the Ring} {The Two Towers} {Return of the King}>

서브시퀀스 정의와 순차 패턴 시퀀스 내에 포함된 시퀀스를 서브시퀀스라 부른다. Association Rules Mining 시퀀스 내에 포함된 시퀀스를 서브시퀀스라 부른다. Definition: A sequence <a1 a2 … an> is contained in another sequence <b1 b2 … bm> (m ≥ n) if there exist integers i1 < i2 < … < in such that a1  bi1 , a2  bi1, …, an  bin 서브시퀀스 w의 지지도는 w를 포함하는 시퀀스의 비율을 나타낸다. (The support of a subsequence w is defined as the fraction of data sequences that contain w) 순차 패턴(sequential pattern)이란 빈발 서브시퀀스(지지도가 minsup 이상인 서브시퀀스)를 의미한다. (A sequential pattern is a frequent subsequence (i.e., a subsequence whose support is ≥ minsup)

순차 패턴 마이닝 정의 다음이 주어졌을 때 다음 작업을 수행하라. 시퀀스들로 구성된 데이터베이스 Association Rules Mining 다음이 주어졌을 때 시퀀스들로 구성된 데이터베이스 사용자가 제시한 최소 지지도 minsup 다음 작업을 수행하라. 지지도가 minsup 이상인 모든 서브시퀀스를 찾아라.

순차 패턴 마이닝 예제 Association Rules Mining

순차 패턴 마이닝 방법 Apriori 원리를 활용  자세한 내용은 생략 (교재 참조) Association Rules Mining Apriori 원리를 활용  자세한 내용은 생략 (교재 참조)

시간 제약 요건 Association Rules Mining 자세한 내용은 생략 (교재 참조)

강의 내용 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 Association Rules Mining 연관규칙 정의와 적용사례 빈발 항목집합과 Apriori 알고리즘 최대 항목집합과 닫힌 항목집합 유용성 척도 범주형, 연속형 속성 처리 다단계 연관규칙 순차 패턴