본 게시글은
서울대학교 데이터사이언스대학원 이상원 교수님의
데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을
학습을 목적으로 재구성하였습니다
우선 저번 시간에 하다가 만 내용을
마저 진행해보자
Walking the Tree란
Oracle에서 부모-자식 관계를 걸어가는 방식,
즉, tree의 계층구조를 이용한 쿼리문이다
위 쿼리는 가장 대표적인
Walking the Tree를 구현한 쿼리인데
차근차근 살펴보자
위 쿼리에서 PRIOR은 부모 행의 ename을 참조라하는 뜻이고
SELECT ename || 'reports to' || PRIOR ename "Walk"
라고 되어있는 부분은
||과 함께 문자열을 연결해서 결과물을 출력해달라는 뜻이다
START WITH ename = 'King'이란 부분은
트리의 루트 노드가 King이라는 뜻이고
CONNECY BY PRIOR empno = mgr;은
이전 행의 empno이 현재 행의 mgr과 같은 방향으로
내려가라는 뜻이다
따라서 위 예시를 보면 루트 노드인 KING의
empno가 7839인데
자식 노드인 CLARK, JONES, BLAKE는 KING을 reports 한다고 출력될 것이고
그의 자식인 ALLEN, WARD, MARTIN은 BLAKE를
SCOTT과 FORD는 JONES를
MILLER는 CLARK를 reports한다고 출력이 될 것이다
이렇게 각자의 부모를 따라가는 형식으로 출력이 되고
총 14개의 rows가 가장 오른쪽과 같이 출력이 되게 된다
Walk라는 column을 출력하는데
가장 루트인 King부터 출력한다
하지만 King은 부모가 없으므로 PRIOR ename은 출력하지않고
KING reports to
만 출력이 된 다음에
BLAKE reports to KING
MARTIN reports to KING ... 등등
쭈욱 총 14개가 출력이 되게 되는 것이다
그렇다면 중간에 탐색하다가
출력하고싶지 않은 부분도 있을 것이다
그럴 때는 위와 같은 방식으로 수행해주면 된다
WHERE절로 조건을 다는 방식인데
SCOTT을 빼고싶다면
WHERE ename != 'SCOTT'과 같은 방식이 있다
또 CONNECT BY 뒤에 조건을 달아주는 방식도 있는데
CONNECT BY PRIOR empno = mgr AND ename != 'SCOTT'
과 같은 방법으로 해주면
ename이 SCOTT인건 뺼 수 있다
그렇다면 이런 쿼리의 목적은 무엇일까?
바로 쿼리에서 recursion을 수행하기 위함이다
예를 들면
KING의 모든 부하를 찾아라
와 같은 쿼리를 수행하고 싶었는데
이를 할 수 있는 방법이 recursion이기 때문이다
이렇게 재귀적인 쿼리를 수행하고싶은 것에서
나온 것이 바로 Datalog이다
Datalog는 if-else 기반의 논리 언어(logic-based query language)인데
트리, 그래프, 조상 찾기, 경로 탐색 등과 같은
재귀적 질의를 더욱 간단하고 직관적으로 표현할 수 있다
그렇다면 예시를 통해 datalog를
더 자세히 알아보자
Bill of Material은
어떤 완제품이 어떤 부속품들로 구성되어 있는지를
나타내는 예제이다
Trike는 세발 자전거인데
세발 자전거는 어떤 부속품들로 구성되어있을까?
위 예시에서 바로 밑에 있는
wheel과 frame까지는 찾아내기가 쉽다
한 단계까지 밑으로 내려가는 것은
self join을 통해 연산이 가능하기 때문이다
끝까지 내려가려면
self join을 여러번 해주어야 하는데
총 몇 단계 깊이까지 가야하는지 모른다면
이런 relational algebra를 이용해서 하는 방법은
힘들 수가 있다
R.A나 SQL-92로
"Trike를 구성하는 것들은 모두 어떤 것들이 있어?"
와 같은 질문을 처리하기 어려운 이유이다
self join을 이용하면 한 단계 내려갈 수 있는데
이를 계속해서 내려가려면
계속해서 self join을 해줘야한다
즉, 어디까지 내려가야하는지를 모르면
self join으로는 수행하기 힘들어지는데
이때 if-else-then과 같은 논리적 개념을 이용하면
찾는 것이 가능해진다는 것이다
따라서 이러한 작업을
Datalog가 수행해줄 수 있는 것이다
우리가 지금 찾고싶은 관계는
단계에 관계없이
어떤 부품이 어떤 부품의 sub가 되냐는 것이다
위 예시에서 예를 들면
Trike에서 Wheel은 직접 sub의 관계니까
wheel은 trike의 sub 관계가 되고
pork는
trike -wheel -pork의 관계이므로
pork도 결국 trike의 sub관계가 되는 것이다
따라서 이러한 규칙을 정해준 것이
바로 위의 Datalog 규칙이다
우리는 Comp라는 규칙을 정의해주고싶은데
Comp(A, B)는
B는 A의 component라는 관계이다
여기서 B가 A에 직접 포함되어 있으면
-> Assembly(A, B, 1)
A와 B는 Comp의 관계가 되는 것이다
그런데 Assembly(A, X, 10)이 있고
Comp(X, Y)가 있으면
X는 A의 직접 구성 요소인데
Y는 X의 구성 요소이기 때문에
A -> X -> Y가 되는 것이고
결국 A -> Y가 되는 것이다
즉, Comp(A, X)가 성립이 되는 것이다
따라서 위와 같은 방식으로
규칙을 적용해 새로운 튜플을 만들어내고
계속 반복해서 적용해서
튜플이 나오지않을 때까지 진행하는 것이다
기존에 있는 정보로 deduction을 한다는 것이다
이러한 방식을 fixpoint computation이라고도 부른다
그럼 다시 위 예시에서 살펴보자
우리는 어떤 Assembly table이 주어지든
위에서 정의한 두 개의 datalog 규칙을
반복해서 적용함으로써
Comp관계를 완전히 계산할 수 있다
실제로는 rule1은 한 번만 적용해주는거고
그 이후에는 rule2만 반복적으로 적용해주면 되는 것이다
그러다가 rule2를 세 번 적용했는데
더 이상 생성되는 튜플이 없다면
더이상 comp관계가 없다는 것이므로
재귀를 종료하면 된다
표준 SQL-99부터 재귀적 문법이 지원됐고
이걸 이용하면 Datalog의 재귀 추론을
SQL에서도 구현할 수가 있다
문법은 위 ppt에서 나와있는 방식이다
여기서 Assembly는 우리가 이전에 정의해준
Part와 SubPart가 있는 table이다
여기에서 젤 처음 Comp의 규칙인데
Assembly 테이블을 이용해서
직접 관계가 있는 것들을 뽑아
Comp에 넣는 것이다
그다음 UNION을 통해
rule2를 실행시키는데
SELECT A2.Part, C1.Subpt
FROM Assembly A2, Comp C1
WHERE A2.Subpt = C1.Part
이 Rule2의 규칙이다
이를 통해 직접 관계와 간접 관계까지 모두 추론하여
더이상 새로운 튜플이 나오지 않게 되면
recursive는 자동으로 멈추게 된다
그래서 마지막에 Comp table을 조회하면
결과들을 확인할 수 있게 된다
또다른 datalog의 예제이다
ancestor 관계를 추론하는 SQL이다
우선 직접 부모와 자식 관계인
parent를 넣은 다음
간접 관계인 ancestor에서도 추론해서
테이블에 넣어준다
다양한 DBMS에서
recursive query를 지원해주는 방법이라고한다
한 번 찬찬히 읽어보면 좋을 것 같다
이러한 recursive CTE는
machine learning을 할 때 주로많이 쓰인다고한다
하지만 뭐 그정도로..
대중적이지는...
않다고...
ㅎㅎ
참고로 recursive CTE의 경우
중간에 cycle이 생기면
error가 발생하니 쿼리를 짤때 참고하자
이제 다음 챕터인
Data Mining을 배워보자
지금까지 계속 우리가 배우고 있는 것은
SQL의 표현력이다
SQL로 어느정도까지 표현할 수 있는지를
이해하면 좋을 것 같다
지금까지 우리가 배워왔던 SQL은
사실 단순한 조회에 불과했다
join, subquery등등 단순 조회였고
analytic function은 좀 더 분석하여 조회하는 것이었다
또한 방금 배웠던 datalog 또한
deduction을 통해서 추론하여 조회하는 것이었다
DB에서 data mining이란 어떤 개념일까?
DB는 큰 데이터는 scalable하게 다루는 것에 강점이 있다
따라서 scalable하게 다룰 수 있는
기술들의 개발에 중점을 두고있다
대용량 데이터의 data mining을 위해 설계된 시스템이
data warehouse architecture이다
기업의 다양한 시스템에서 발생하는 데이터를
중앙에 모아서 저장하고
분석과 의사결정에 사용할 수 있게 해주는
일종의 분석 전용 데이터 시스템이다
위의 그림처럼 OLTP와 OLAP는 나눠서 처리되고
요즘은 이러한 것들이 cloud로 옮겨가고 있다고 한다
각각의 차이를 한 번 살펴보자
우리가 지금까지 배워온 단순 쿼리는
그냥 사실과 정보만을 제공해주는 것이다
OLAP는 이러한 사실을 바탕으로
요약을 하는 등
존재하는 데이터를 분석하는 것을 말한다
Data Mining은 단순한 분석을 넘어서
데이터의 패턴을 통해서
insight를 발견하고
이를 이용하서 어떠한 예측을 하는 것이다
Data Mining은 많은 곳에서 사용되는데
요즘 가장 많이 사용되는 곳은 recommendation이라고 한다
위의 예시들을 보면서
아 이런 곳에 사용되는구나 이해하면 좋을 것 같다
고객들의 구매 기록이라는
위 예시를 보고
Data Mining의 예시를 살펴보도록하자
Data Mining이란 어떤 대량의 데이터에서
숨겨진 패턴, 상관관계, 규칙 등을 발견해서
의사결정에 활용할 수 있도록 하는 기술이다
위와 같은 기술들이 예시로 나와있는데
한 번 살펴보자
첫 번째는 co-ocurrences의 개념이다
어떤 항목들이 자주 나타나는지를 찾는 것이다
예를 들어 모든 고객들의 60%가
x, y, z 아이템을 동시에 구매한다던가
남성 고객들 중 75%가
기저귀와 맥주를 함께 산다는 그런 것들을 말한다
두 번째는 sequential pattern이다
이는 어떤 행위의 순서가 자주 반복되는지를 예측하는 것이다
예를 들면
아마존에서 해리포터 도서를 산 고객의 60%는
3주 이내에 DVD도 사는 그런 것이다
마지막으론 classification이다
어떤 데이터를 바탕으로 다른 데이터도
분류하는 것을 말한다
예를 들면 25세 이하인데 salary가 40k가 넘는 사람은
대부분 스포츠카를 산다는 것이다
이를 통해 어떤 고객이 어떤 차를 살지
예측이 가능한 것이다
또 다른 기술들도 있다
간단하게만 살펴보고 넘어가자
clustering은 비슷한 성향의 데이터들을 묶는 것이다
고객을 N개의 segment들로 나누는 것을 예시로 들수있다
이런걸 가능하게 하는 알고리즘으로는
k-means, EM, Birch, Cure, DBSCAN등이 있다
다음으로는 유사 시계열 분석이다
시간에 따라 변화하는 데이터를 보고
보이는 시계열 패턴을 찾는 것을 말한다
다음으로는 outlier discovery인데
이는 데이터에서 이상치를 찾는 것을 말한다
그다음 text나 web mining 혹은
유사한 이미지를 찾는 그런 것들이 있다
위에서 말했던 그런 Data Mining의 기법들을
수행해주는 알고리즘들이다
우리가 오늘 배울내용은
A-priori라고 한다
Data Mining의 대표적인 예시인
장바구니 분석을 함께 살펴보자
retailer들이 이렇게 고객들의 온오프라인 장바구니를 분석하는 이유는
어떤 아이템들이 함께 구매되었는지를 확인하고
상품간 연관성들을 분석하여
매장 레이아웃이나 카탈로그 배치들을 최적화 할 수 있기 때문이다
따라서 장바구니 분석 예시에서는
다음과 같은 질문들을 주로 해결할 수 있다
1. 고객은 주로 어떤 아이템들을 함께 구매하는가?
-> frequent itemset
2. 어떤 순서로 물건을 구매하는가?
-> sequential pattern
3. 어떤 고객들이 주로 어떤 상품을 사는가?
-> classification/clustering
아까 위에서 오늘 살펴볼 알고리즘은
A-priori라고 했는데
이는 어떤 상품이 자주 함께 구매되는지를
분석하는 알고리즘이다
따라서 frequent itemset을
위의 장바구니 분석 예시에서 살펴보자
만약 고객의 거래 목록이 담긴
database table이 주어졌다고 가정하자
그러고 각 거래의 기록에는 고객이 구매한
item의 set이 기록되어있다
위 예시를 보면
transid별로
각각 어떤 상품이 함께 구매되었는지가 나온다
itemset이란 여기서
한 거래에서 구매된 아이템의 집합을 뜨한다
그렇다면 위 예시에서
각 itemset의 support(지지도)를 구해보자
support란 우리나라 말로는 지지도라고 부르는데
어떤 거래에서 어떤 상품의 set이 포함되어있는
비율을 뜻한다
따라서 {pen, ink}는 4개의 거래에서
3개에 포함되어 있으므로 75%가 되고
{milk, juice}는 1개만 포함되어 있으므로
25%가 되는 것이다
그렇다면 사용자가 설정한 최소 지지도(minsup) 이상으로
자주 등장하는 itemset인 frequent itemset을 구해보자
만약 minsup이 70%라면
{pen}, {ink}, {milk}, {pen, ink}가
frequent itemset이 된다
이런 frequent itemset을 구하는
naive한 알고리즘을 살펴보자
I가 Database(D)안에 있는 모든 item들의
집합이고
N은 D 안에 있는 모든 거래(T)의 개수이다
따라서 위 pseudo code를 잘 보면
I안에 있는 모든 subset만큼을 순회하는데
모든 itemset에 대해서 반복문을 돌리려면
2 i제곱만큼의 순회가 일어나게 된다
(2시 아님 주의)
따라서 각 itemset에 대해 돌면서
모든 거래에 순회하며
거래 T에 해당 아이템 셋이 있다면
count에 1을 더해준다
그러다가 minsup보다 count/총개수가 더 커진다면
이는 frequent itemset이 되는 것이므로
해당 리스트에 넣어준다
따라서 이는 맨 처음 반복문에서 2의 i제곱만큼 돌리고
그 내부의 모든 Transaction에 대해서 N만큼 돌면서
시간복잡도가
O(2^i * N)이 된다
이보다 더 효율적으로 수행할 수 있는 방법은 없을까?
이 frequent itemset을 더 효율적으로 찾는
알고리즘의 핵심 원리는 바로 이것이다:
"만약 S가 포함된 subset이 frequent itemset이라면
S도 frequent itemset이다"
다시 한 번 예를 들면
만약 상품 {A, B, C}가 frequent itemset이라면
{A}, {B}, {C}도 반드시 frequent itemset이라는 뜻이다
또 {Pen, Ink, Milk}가 frequent itemset이라면
{Pen, Ink}, {Ink, Milk}, {Pen, Milk}도 역시
frequent itemset이 되는 것이다
또한 만약 어떤 itemset이 frequent하지 않다면
그걸 포함하는 집합은 절대 frequent할 수가 없다
이러한 원리를 이용하면
계산량을 굉장히 줄일 수 있게 된다
simple version의 A-priori algorithm이다
위 pseudo code를 자세하게 살펴보자
모든 item에 대해서 순회하면서
각 item이 minsup을 넘기는지를 확인해서
minsup보다 큰 것들만 남긴다
이는 1번만 실행했을 때 (K=1)일 때
minsup 이상의 itemset인데
이는 L1이라고도 부른다
그 다음 minsup이 넘는 것들에 대해서
반복적으로 탐색하는데
현재 Lk단계에 있는 minsup 이상의 상품들을 대상으로
가능한 모든 조합의 k+1의 itemset 후보들에 대해서
(이걸 aprior-gen step이라고 부른다)
이 후보 아이템셋들이 minsup보다 높으면
L(k+1)에 포함시킨다
이 과정을 계속해서 반복하는 것이다
여기서 aprior-gen step이란
k단계에 있는 조합들을 활용해서
새롭게 frequent itemset이 될 수 있는
후보들을 만드는 단계이다
예를들어서 {A, B}, {B, C}, {C, A}가
k단계의 조합이라면
{A, B, C}가 다음 후보가 된다
아무튼 이렇게 계속해서 반복하는데
언제까지 반복하냐면
더이상 minsup을 넘는 새로운 조합이 없을 때까지 반복한다
gpt가 정리해준 알고리즘의 구조인데
정리하는데에 도움될 것 같아서 같이 남겨둔다
아무튼 simple version은 이렇게 수행하는데
여기서 알고리즘을 더욱 최적화 할 수 있다고한다
바로 부분집합이 frequent하지 않은 후보는
아예 생성하지 않는 방식이다
minsup이 70%일 때의 A-priori algorithm을 잘 살펴보자
Database D가 있고
가장 처음 k=1일 때 scan을 한다
그럼 가능한 후보는 c1만큼 나오고
거기서 70%이 넘는 pen, ink, milk가 L1이 된다
그다음 L1로 만들 수 있는 모든 조합을
C2로 생성해서 다시 support를 구한다
그런 다음 70%이 넘는 것만 L2에 넣는다
다음은 L2에서 또 가능한 조합을 만들어서
support를 구한다
하지만 여기서 생성된 조합은 C3는 1개 뿐인데
그 1개가 minsup을 넘지 못했다
그럼 더이상 frequent한 itemset이 없는 것이고
이에 따라 알고리즘은 종료된다
이게 simple version이었는데
아까 위에서 여기서 frequent하지 않은
부분집합이 있다면 그걸 제외하는 걸로
더욱 optimize를 시킬 수 있다고 했다
이에 따라 위 경우에서는
L2에서 C3로 넘어갈 때
{pen, ink}, {pen, milk}라서
C3가 {pen, ink, milk}가 나오게 되었는데
{ink, milk}는 frequent한 itemset이 아니다
그럼 당연히 pen, ink, milk는 frequent한 itemset이 아니게 되므로
만약 optimize한 버전에서는 3번째 scan을 수행하지 않고
알고리즘이 끝나게 된다
오른족 사진의 분이 개발하신
알고리즘이다
apriori-gen 단게에서 새로운 후보를 생성할 때
invalid candidate가 있으면
그 후보는 제거하는 방식으로
더욱 최적화를 시켜줄 수 있다
A-priori algorithm의 또 다른 예제이다
마지막으로 이것만 살펴보고 오늘 수업정리를 마무리해보려고 한다
우선 가장 처음에 k=1 단계에서
각각 Itemset별로 support를 구해주고 L1을 구한다
그 다음 L1에서 가능한 조합을 구하여 C2를 구해준다
이 단계에서는 frequent하지 않은 부분집합이 나올 수가 없기 때문에
pruning을 하지 않고 계속 진행해준다
C2에서 각각의 support를 구하고 minsup이 넘는 것만
L2로 올려준다
그 다음 L2를 이용해서 C3를 만들어주는데
여기서는 모든 부분집합이 다 frequent하므로
pruning 해줄 것이 없다
따라서 scan3도 계속 진행해주면 된다
교수님이 이와 관련된 oracle query를 보여주면서
시험에 나오니 잘 기억해두라고 하셨는데
쿼리로 보니 도저히 모르겠다
아무래도 시험기간에 gpt와의 독대를 통해
독학..이 필요할 듯 하다
아무튼 여기서 오늘 수업 정리는 마무리-!