9장. 연관규칙분석과 협업필터링

9 장. 연관규칙분석과협업필터링 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 1 / 29

학습내용 연관규칙분석연관규칙측도절차고려사항협업필터링 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 2 / 29

연관규칙분석 I 데이터에존재하는항목 (item) 들간의 if-then 형식의연관규칙을찾는방법기업의데이터베이스에서상품의구매, 서비스등일련의거래 (transaction) 또는사건들간의연관성에대한규칙을발견손님의장바구니에들어있는품목간의관계를알아본다는의미에서장바구니분석 (market basket analysis) 이라고도함효율적인매장진열, 패키지상품의개발, 교차판매전략구사, 기획상품의결정등 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 3 / 29

연관규칙분석 II 예 서비스: 고객들이 특정 서비스를 받은 후 다음에 어떤 서비스를 원하는지 금융: 고객들의 기존 금융서비스 내역으로부터 대출과 같은 특정한 서비스를 받을 가능성이 높은 고객을 찾음 보험: 보험금 청구가 기존의 정상적인 청구와 다른 패턴을 보이는 경우 보험사기일 가능성이 있음 인터넷 쇼핑몰의 상품 추천, 텍스트마이닝에서 웹페이지간의 링크에 대한 분석 등 박창이 (서울시립대학교 통계학과) 9장. 연관규칙분석과 협업필터링 4 / 29

연관규칙 I 연관규칙의종류유용한규칙 목요일에식료품가게를찾는고객은아기기저귀와맥주를함께구입하는경향이있다 자명한규칙 한회사의전자제품 ( 가령스마트폰, 세탁기등 ) 을구매하던고객은전자제품을살때같은회사의제품을사는경향이있다 설명이불가능한규칙 새로연건축자재점에서는변기덮게가많이팔린다 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 5 / 29

연관규칙 II 편의점거래내역예제고객번호품목 1 오렌지쥬스, 사이다 2 우유, 오렌지쥬스, 식기세척제 3 오렌지쥬스, 세제 4 오렌지쥬스, 세제, 사이다 5 식기세척제, 사이다 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 6 / 29

연관규칙 III 동시구매표 오렌지쥬스 식기세척제 우유 사이다 세제 오렌지쥬스 4 1 1 2 2 식기세척제 1 2 1 1 0 우유 1 1 1 0 0 사이다 2 1 0 3 1 세제 2 0 0 1 2 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 7 / 29

연관규칙 IV 연관규칙 : If X, then Y (X Y ) 두품목 X와 Y를동시에구매한경우의수가일정수준이상품목 X를포함하는거래중품목 Y를구입하는경우의수도일정수준이상 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 8 / 29

연관규칙분석의측도 지지도 지지도 = ˆP(X Y ) = X 와 Y 가동시에포함된거래수전체거래수 신뢰도 ˆP(Y X ) = ˆP(X Y ) ˆP(X ) = 품목 X 와 Y 를동시에포함하는거래수품목 X 를포함하는거래수 편의점거래내역예제 오렌지쥬스를구매하면사이다를구매한다 : 2/5 와 2/4 우유와오렌지쥬스를사면식기세척제를산다 : 1/5 과 1/1 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 9 / 29

지지도와향상도예제 I 거래내역 항목 거래수 A 100 B 150 C 200 {A,B} 400 {A,C} 300 {B,C} 200 {A,B,C} 100 추가안함 550 전체거래수 2000 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 10 / 29

지지도와향상도예제 II 상대도수 항목 품목이포함된거래수 확률 A 900 0.450 B 850 0.425 C 800 0.400 {A,B} 500 0.250 {A,C} 400 0.200 {B,C} 300 0.150 {A,B,C} 100 0.050 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 11 / 29

지지도와향상도예제 III 하나의품목만을결과로갖는모든연관규칙 규칙 지지도 신뢰도 X Y ˆP(X Y ) ˆP(X ) ˆP(Y X ) A B 0.250 0.450 0.556 B A 0.250 0.425 0.588 B C 0.150 0.425 0.353 C B 0.150 0.400 0.375 A C 0.200 0.450 0.444 C A 0.200 0.400 0.500 {A, B} C 0.050 0.250 0.200 {B, C} A 0.050 0.150 0.333 {A, C} B 0.050 0.200 0.250 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 12 / 29

향상도 I {B, C} A: 신뢰도 0.333 으로가장높음. 품목 {B, C} 의거래가 일어날가능성은 0.15 로작음 지지도와신뢰도만으로는유용한규칙인지판단하기어렵기때문에 향상도를고려 연관규칙 X Y 의향상도 ˆP(X Y ) ˆP(X )ˆP(Y ) = ˆP(Y X ) = 신뢰도 ˆP(Y ) ˆP(Y ) = 품목 X 와 Y 를포함하는거래수 전체거래수품목 X 를포함하는거래수 품목 Y 를포함하는거래수 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 13 / 29

향상도 II 향상도 = 1: 두품목이서로독립적인관계향상도 > 1: 규칙이결과를예측하는데있어서우연적기회 (random chance) 보다우수. 양의상관관계향상도 < 1: 규칙이결과를예측하는데있어서우연적기회보다나쁨. 음의상관관계 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 14 / 29

연관규칙분석절차 품목의갯수가 k이면모든가능한품목의수는 2 k k가아주큰경우에이모든집합중에지지도가높은집합을찾는것은현실적으로불가능 최소지지도보다큰집합만을대상으로높은지지도를갖는품목집합을찾음 Apriori 알고리즘 1. 최소지지도를넘는모든빈발품목집합 (frequent itemset) 을생성 2. 빈발품목집합에서최소신뢰도를넘는모든규칙을생성 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 15 / 29

빈발품목집합의생성 1. 개별품목중에서최소지지도를넘는모든품목을찾음 2. 위에서찾은개별품목만을이용해서최소지지도를넘는 2가지품목집합을찾음 3. 위의두스텝에서찾은품목집합을결합하여최소지지도를넘는 3 가지품목집합을찾음 4. 위과정을반복하여최소지지도가넘는빈발품목집합들을찾음 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 16 / 29

빈발품목집합의생성예제 I 최소지지도 30% 데이터 거래품목 1 F, K, N 2 E, F 3 E, S 4 E, F, N 5 C, E, F, K, N 6 C, K, N 7 C, K, N 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 17 / 29

빈발품목집합의생성예제 II 빈발품목집합생성과정 C, E, F, K, N, S의빈도 : 3, 4, 4, 4, 5, 1 F 1 = {C, E, F, K, N} 2-후보품목집합 : C 2 = {{C, E}, {C, F }, {C, K}, {C, N}, {E, F }, {E, K}, {E, N}, {F, K}, {F, N}, {K, N}} 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 18 / 29

빈발품목집합의생성예제 III C 2 의각품목의빈도 : 1, 1, 3, 3, 3, 1, 2, 2, 3, 4 F 2 = {{C, K}, {C, N}, {E, F }, {F, N}, {K, N}} 3-후보품목집합 : C 3 = {{C, K, N}} {E, N} F 2 이므로 {E, F, N} 는제외 {C, K, N} 의빈도 : 3으로최소지지도를넘고 F 3 = {{N, C, K}} 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 19 / 29

연관규칙의생성 빈발품목집합에대하여연관규칙을생성하기위해, 공집합을제외한빈발품목집합의모든부분집합을대상으로신뢰도를계산하고주어진최소신뢰도를넘는연관규칙을찾음예제에서빈발품목집합 F 1, F 2, F 3 이생성되면모든가능한연관규칙을생성한후정해진최소신뢰도를넘는연관규칙을찾음 ( 질문 ) 최소신뢰도가 80% 를넘는연관규칙은? 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 20 / 29

고려사항 I 적절한 품목의 선택 분석의 목적 (예) 술 vs 소주, 맥주, 포도주, 위스키 등 디자이너 레이블이나 저지방, 무지방 제품 등과 같은 가상품목 일반적으로는 일차 단계에서 상위수준의 품목 분류를 이용하여 규칙을 찾은 후 이를 바탕으로 세분화된 품목으로 분석을 진행 연관규칙의 발견 연관규칙의 표현 음의 상관규칙 B와 C이면 A이다 의 신뢰도가 33%이고 향상도는 1보다 작은 경우 B와 C이면 A가 아니다 라는 연관규칙은 신뢰도가 67%가 되고 따라서 향상도는 1보다 커짐 박창이 (서울시립대학교 통계학과) 9장. 연관규칙분석과 협업필터링 21 / 29

고려사항 II 시차연관성분석웹로그 (web log) 로부터동일한고객의구매패턴이나웹페이지방문패턴을알수있는경우현실적문제의해결품목의수가증가하면계산량은기하급수적으로증가최소지지도가지치기 (minimum support pruning), 품목수가일정수를넘는규칙제외등 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 22 / 29

협업필터링 (Collaborative filtering) 개인의선호도와과거상품구매이력을분석하여개인에게최적인상품을추천 기호 고객중심 예 : 로맨스영화를좋아하는고객에게로맨스장르의다른영화추천 상품중심 예 : 로맨스영화를좋아하는고객에게특정자동차를추천 n 명의고객과 p 개의상품을가정 r ij : i 번째고객의 j 번째상품에대한선호도 O = {(i, j) : r ij 가관측 } 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 23 / 29

협업필터링방법 I 1. 고객중심 s(i, i ): 고객 i와 i 의선도호도에대한유사성의측도 cos(i, i ) = corr(i, i ) = j O ii r ijr i j r 2 j Oii ij j O r 2 ii i j j O (r ii ij r i )(r i j r i ) (r j Oii ij r i ), 2 (r j Oii i j r i ) 2 여기서 O ii 은고객 i 와 j 에대하여공통적으로선호도가관측된 상품들의집합 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 24 / 29

협업필터링방법 II 선호도에대한추정치 : ˆr ij = 1 N j (i) i N j (i) r i j 또는 ˆr ij = i N j (i) s(i, i )r i j i N j (i) s(i, i ) N(i): 고객 i 와유사한고객들의집합 N j (i): N(i) 에속하는고객중상품 j 에대한선호도정보가있는고객들의 집합 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 25 / 29

협업필터링방법 III 2. 품목중심 선호도에대한추정치 : ˆr ij = 1 N i (j) j N j (i) r ij 또는 ˆr ij = j N i (j) s(j, j )r ij j N i (j) s(j, j ) N(j): 상품 j 와유사한상품들의집합 N i (j): N(j) 에속하는상품중고객 i 에대한선호도정보가있는 상품들의집합 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 26 / 29

협업필터링예제 I 영화타이타닉에대한 Eric 의선호도추정 Matrix Titanic Die Hard Forrest Gump Wall-E John 5 1 2 2 Lucy 1 5 2 5 5 Eric 2 3 5 4 Diane 4 3 5 3 고객중심 Eric 과 Lucy, Eric 과 Diane 의유사성의측도 : 0.75, 0.15 ˆr = 0.75 5+0.15 3 0.75+0.15 = 4.67 상품중심 Titanic 과유사한영화 Forrest Gump 와 Wall-E 에대한유사성의측도 : 0.85, 0.75 ˆr = 0.85 5+0.75 4 0.85+0.75 = 4.53 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 27 / 29

협업필터링의특징 I 고객중심과상품중심의비교예측의정확도 : n > (<)p인경우상품 ( 고객 ) 기반이우수함계산의효율성 : n > (<)p인경우상품 ( 고객 ) 기반이효율적안정성 : 고객 ( 상품 ) 이상품 ( 고객 ) 보다빨리변하는경우상품 ( 고객 ) 기반이안정적. 가령온라인쇼핑의경우고객이상품보다빨리변함해석력 : 상품기반이고객에게설명하기쉬움. 고객기반은잘모르는유사한고객에대해서얘기해야함새로움 : 상품기반추천은상품군을뛰어넘지못하는반면고객기반추천은로맨스영화를좋아하는사람에게특정자동차를추천할수도있음 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 28 / 29

협업필터링의특징 II 소수의관측된선호도를이용하여대부분관측되지않은선호도를 추정함 소개한협업필터링방법은최근방에대한것으로관측된선호도의갯수가매우작으면예측력이매우떨어지며, 대신행렬분해에의한 matrix completion 을흔히사용함 R = AB R: n p 선호도행렬, A: n r 행렬, B: r p 행렬 r: 데이터의잠재적차원 (i,j) O (r ij r k=1 a ikb kj ) 2 을최소화하는 Â, ˆB 를구함 ˆR = Â ˆB 로추정 박창이 ( 서울시립대학교통계학과 ) 9 장. 연관규칙분석과협업필터링 29 / 29