FP-Growth* Algorithm (Frequent-Pattern Growth)

시작하기전에

바로 전 연관규칙분석 (Apriori Algorithm) 을 보지 못했다면, 그리고 Apriori를 잘 모른다면 잠깐이라도 보고 넘어오길 바란다. Apriori와 마찬가지로 수학적으로, 논문처럼 작성된 문서들은 널리고 널렸기에, 좀더 쉽고 간단하게 설명하고자한다.

어디까지나 알고리즘 이해를 중심으로 설명하려하기에, 알려진 논문이나 자료들과는 조금 다를지도 모른다. 애시당초 그런 논문들 처럼 설명할거였으면 그냥 링크나 올리고 말았을 것이다. ㅎㅎ

소개

FP-Growth는 FP-Tree라는 구조를 이용하여 Apriori를 효과적으로 구현한 것이라 나는 생각한다.

앞서 Apriori의 처리속도 문제를 해결할 수 있게끔, 자료구조를 기똥차게(?) 응용하여 만들어낸 트릭(?)이랄까?ㅋ (처음에 이거 이해하고 얼마나 놀라웠던지..ㅋㅋ)

FP-Tree의 구조는, Tree, Array, Linked-List를 합쳐놓은 구조이다. 자료구조에 밝은 사람이라면 누구나 이해가 쉬울 것이다. 

(얼핏 구성만 보면, 강남에서 프랑스인이 길을 묻는 것 같은 유체이탈을 경험하게 되지만, 세부적으로 하나하나 뜯어보면 사실 무쟈게 단순하다. ^^)

먼저, 구성을 보자.

좌측의 Table은 Node-link(Pointer)를 가진 배열(frequent-item-header table)이다.
우측의 동그란원(Node)들과 실선 화살표는 트리(item-prefix sub-trees)이다. (Root-Node가 Null이라는 것을 주의하자.)
그리고 박스와 동그란원(Node)을 점선 화살표로 연결해 놨는데, 이것이 Linked-list 이다.

레시피

입력데이터 예시)
다음과 같은 상품정보가 있다고 생각해보자. (구성에서는 Item ID라며 I1~I5라는 코드로 되어있으나, 이해를 위해 실제 '인XX크 상품명'으로 예를 만들겠음)

1. 데오드란트, 니베아, 스틱, 세이퍼진
2. 니베아, 스프레이, 세이퍼진
3. 데오드란트, 니베아, 스틱, 세이퍼진
4. 데오드란트, 니베아, 스프레이, 세이퍼진
5. 데오드란트, 니베아, 스프레이, 스틱, 세이퍼진
6. 스프레이, 니베아, 스틱

각 item의 전체 노출 수를 구한 후, 빈도(support count)가 높은 순으로 정렬한다.

No.	Item ID	support count
1	니베아	6
2	세이퍼진	5
3	데오드란트	4
4	스프레이	4
5	스틱	4

이제 이 순서를 기준으로, 각각의 item을 정렬한다. (빈도가 높은 item이 앞에 놓인다.)

1. 니베아, 세이퍼진, 데오드란트, 스틱
2. 니베아, 세이퍼진, 스프레이
3. 니베아, 세이퍼진, 데오드란트, 스틱
4. 니베아, 세이퍼진, 데오드란트, 스프레이
5. 니베아, 세이퍼진, 데오드란트, 스프레이, 스틱
6. 니베아, 스프레이, 스틱

이 결과를 순서대로 Tree에 삽입한다. (괄호안의 숫자는 support count 이다.)

1. 첫 데이터 "니베아, 세이퍼진, 데오드란트, 스틱"이 차례로 입력된다. (키워드 옆의 (1)은, "1회씩 입력되었다"는 의미)
2. 두번째 데이터 "니베아, 세이퍼진, 스프레이"는 "니베아"와 "세이퍼진"이 각각 1회씩 추가되어 (2)로 변경되며, "스프레이"는 신규노드로 추가된다.
3. 세번째 데이터 "니베아, 세이퍼진, 데오드란트, 스틱"은 기존에 이미 만들어진 노드가 모두 있으므로 카운트만 달라진다.
4. 네번째 데이터 "니베아, 세이퍼진, 데오드란트, 스프레이"는 "니베아, 세이퍼진"이 이미 존재하므로 카운트만올리고 "데오드란트"의 하위에 "스프레이"가 없으므로 신규노드로 추가된다.
5. 다섯번째 데이터 "니베아, 세이퍼진, 데오드란트, 스프레이, 스틱"은 기존에 "니베아, 세이퍼진, 데오드란트"가 이미 존재하므로 카운트만 올리고 "스프레이"의 하위에 "스틱"이 없으므로 신규노드로 추가된다.
6. 여섯번째 데이터 "니베아, 스프레이, 스틱"은 "니베아" 카운트 증가 후 "스프레이, 스틱"이 없으므로 각각 차례로 신규 추가된다.

이제 아까 만들어놓은 배열(frequent-item-header table)과 지금 만들어진 Tree(item-prefix subtrees)를 아래와 같이 (같은 item끼리) Linked-list로 연결한다.

파란 점선 화살표의 진행을 유념하여 살펴보라.

각 노드의 괄호 안 숫자는 support count이며 횡으로 연결된 동일 노드들간 support count의 값을 합산하면 Header table의 support count값과 동일해진다.

자, 여기까지하면 일단 구조는 완성된 것이다.

매우 간단하고 쉽지않은가? ㅎㅎ (참고: https://fenix.tecnico.ulisboa.pt/downloadFile/3779571250096/licao_10.pdf )

그럼 이제부터, 연관키워드를 찾아내는 흐름을 설명하겠다.

빈발패턴을 찾아내기

먼저, 위 상품 데이터(니베아, 세이퍼진, 데오드란트 블라블라~)들 안에서 빈발패턴들을 찾아내보자.

위에서 만들어진 FP-Tree를 분해함으로서 아주 쉽게 얻을 수 있다. (분해는 항상 support count가 낮은 item부터 시작한다.)

그 전에 Apriori에서도 언급했다시피, 전체 데이터를 표본으로 삼는 것은 좋지않기 때문에 노이즈를 제거한다. 즉, Minimum support를 선언하지만, 패스하겠다.

제일 support count가 낮은 "스틱"을 기준으로 FP-Tree 內 해당 item을 찾는다.

1. "스틱"이 존재하지 않는 경로는 제거한다.
2. 그리고 support count를 업데이트하는데, 스틱의 support count를 고스란히 올려준다고 생각하면 된다.
3. 따라서 "스프레이"는 1이 되고, 데오드란트는 좌측 "스틱"의 2와 우측 "스틱"의 1이 합산된 3이 된다.
4. 같은 방법으로 부모노드의 support count를 업데이트 한다. 
5. 목표로 했던 item인 "스틱"을 제거하여, 최종트리를 완성한다.

솔직히 제거하던말던 별 차이는 없구만.. ㅎㅎ

support count가 낮은 "스프레이"를 배제하여보면, (니베아, 세이퍼진, 데오드란트, 스틱)(3), (니베아, 세이퍼진, 스틱)(3), (니베아, 데오드란트, 스틱)(3), (니베아, 스틱)(3)등의 부분집합이 만들어진다.

<(니베아, 세이퍼진, 데오드란트, 스틱) 에서 "스틱"에 맞닿은 "데오드란트"의 suport count의 값이 3이므로 (니베아, 세이퍼진, 데오드란트, 스틱)의 suport count 역시 3이 된다.>




같은 방법으로 "스프레이"를 기준으로 트리를 분해해보겠다.


"스프레이"을 기준하여, (니베아, 세이퍼진, 스프레이)(3), (니베아, 스프레이)(4), (세이퍼진, 스프레이)(3) 등의 부분집합이 만들어진다.

<(니베아, 세이퍼진, 스프레이) 에서 "스프레이"에 맞닿은 "세이퍼진"의 suport count의 값이 3이므로 (니베아, 세이퍼진, 스프레이)의 suport count 역시 3이 된다.>


"데오드란트", "세이퍼진", "니베아"도 차례로 분해하면, 각각 다음과 같은 모습이 된다.


이렇게 얻어진 패턴들이 빈발패턴이라 볼 수 있겠다. (support count를 기준으로 가중치를 조정할 수 있을 것이다.)

• "스틱"에서 얻을 수 있는 조합: (니베아, 세이퍼진, 데오드란트, 스틱)(3), (니베아, 세이퍼진, 스틱)(3), (니베아, 데오드란트, 스틱)(3), (니베아, 스틱)(4), (스틱)(4)
• "스프레이"에서 얻을 수 있는 조합: (니베아, 세이퍼진, 데오드란트, 스프레이)(3), (니베아, 세이퍼진, 스프레이)(3), (니베아, 스프레이)(4), (스프레이)(4)
• "데오드란트"에서 얻을 수 있는 조합: (니베아, 세이퍼진, 데오드란트)(4), (니베아, 데오드란트)(4), (세이퍼진, 데오드란트)(4), (데오드란트)(4)
• "세이퍼진"에서 얻을 수 있는 조합: (니베아, 세이퍼진)(5), (세이퍼진)(5)
• "니베아"에서 얻을 수 있는 조합: (니베아)(6)

결국 빨간색으로 표시한 것들을 중심으로 먼저 support count가 5인 Item-set (니베아, 세이퍼진)(5),

다음으로 support count가 4인 Item-set은, (니베아, 세이퍼진, 데오드란트)(4), (니베아, 데오드란트)(4), (세이퍼진, 데오드란트)(4), (니베아, 스프레이)(4), (니베아, 스틱)(4)

그 다음으로 support count가 3, 2, 1, …

등등의 순으로 빈발패턴이 만들어지게 된다.

FP-Growth vs Apriori

여기서 유념하여야 할 부분은 빈발패턴을 찾기위해 Apriori처럼 전체 트리를 탐색하지 않고,

Header table에서 해당 item을 찾아 Linked-list를 통해 차례로 접근하면 되기에 속도상 엄청난 이득을 가져올 수 있다는 점이다.

Apriori에서 말했듯, 워낙 비교횟수가 무지막지한 문제로 알고리즘의 퍼포먼스가 매우 안좋은데, FP-Tree에서는 그것을 효과적으로 개선했다.

※ Python package
https://pypi.org/project/pyfpgrowth/

마치며

경험상으로 미루어 볼때, 데이터의 수가 테라바이트급이로 올라가게 되면 (표본을 채취해서 분석에 활용한다해도 기가바이트급 이기에..), FP-Tree 역시 문제가 있더군요.

아시다시피 Linked-list의 퍼포먼스는 극악에 가깝지요. 매번 노드의 포인터를 찾아야할 때마다 부하가 엄청납니다. ( 속도가 나무늘보 움직이듯 하더라ㅜㅜ; )

이러한 FP-Growth의 단점들을 보완하여 많은 변형알고리즘이 존재하는데, FP-Growth Algorithm Variations 이곳에서 참고할 수 있습니다.


결국 같은 이유로 인해, 저 역시 다른 아이디어를 찾게 되었습니다. FP-Tree 그대로를 사용하지는 않고, 다른 형태로 변형/조작해서 사용하곤 했었습니다. ( 예를들어, Map-reduce )

FP-Growth를 이용하실 생각이라면 아마도 이러한 점을 유념하셔야 할 것입니다.

사실 라이브러리를 사용한다면, 세세하게 동작원리까지는 몰라도 될 수 있기에, 어디까지나 이해를 돕기위한 글이 되었으면 하는 바램입니다.

연관규칙분석 (Apriori Algorithm)

Apriori에 대하여

FP-Growth* Algorithm은 먼저, Apriori Algorithm을 이해해야 좋다.
그런 이유로 FP-Growth*를 설명하기 앞서 Apriori부터 설명토록 하겠다.
Apriori Algorithm은 연관규칙분석이다. 임의 데이터 집합간 빈번한 발생패턴을 찾는 알고리즘이다.

그러니까, '핸드폰'을 구매한 사람은 '핸드폰 케이스'를 함께 구매할 확률이 높다, 뭐 이런거?

암튼, 수학적인 그리고 이론적인 설명을 주구장창 해 봤자, 짜증(?)만 나고 이해가 안갈 것이기에, 예를들어 되도록 쉽게 설명토록 하겠다. ㅎㅎ

(전공자의 경우, 수학적 설명이나 기호가 빠져 이상하게 생각할 수 있을텐데, 비전공자를 위한 간단한 알고리즘 설명이라 생각바람.)

다음과 같은 구매 목록이 있다고 가정하자.

구매번호	구매물품
1	키보드, 노트북, 외장하드
2	노트북, 파우치
3	노트북, 거치대
4	키보드, 노트북, 파우치
5	키보드, 거치대
6	노트북, 거치대
7	디카
8	키보드, 노트북, 거치대, 외장하드
9	키보드, 노트북, 거치대
10	노트북, 파우치

먼저, 7번항목의 "디카"를 보면, 전체 구매목록에서 단 1회 구매되었다. 즉, 빈번히 발생하는 사건이 아니기에 다른 제품과의 연관성은 없다고 봐도 좋을 것이다.

이런식으로 특정 상품의 구매횟수(노출횟수)를 지지도(support)라 칭하고, 전체 items 중에 얼마나 노출되었는가에 대한 스코어를 채점한다.

지지도가 낮다면(위 구매목록의 예로보면 '디카'의 경우), 전체 데이터 분석 입장에서는 그저 노이즈가 될 뿐이다.


상품 기준으로 표를 다시 정리해보겠다.

구매번호	노트북	키보드	거치대	파우치	외장하드	디카
1	O	O	X	X	O	X
2	O	X	X	O	X	X
3	O	X	O	X	X	X
4	O	O	X	O	X	X
5	X	O	O	X	X	X
6	O	X	O	X	X	X
7	O	X	X	O	X	X
8	O	O	O	X	O	X
9	O	O	O	X	X	X
10	X	X	X	X	X	O
(support)	8	5	5	3	2	1

디카는 전체 10건 중 1회 노출(1/10=0.1)이라는 지지도로서 분석표본에서 배제되어야 할 노이즈로 간주하도록 한다.

(지지도는 전체 중 얼마나 사건(판매)이 발생되었는가 라는 개념이라, '디카'는 전체10회 중 1회이므로 1/10=0.1 이고, '키보드'는 전체 10회 중 5회이므로 5/10=0.5 이다.)

지지도를 0.2로 제한을 둔다면, 각각의 지지도를 기준으로 노트북(0.8), 키보드(0.5), 거치대(0.5), 파우치(0.3), 외장하드(0.2)만 분석대상이 되고 디카(0.1)은 배제된다.


"키보드"을 구매한 사람들은 각각 "노트북, 외장하드", "노트북, 파우치", "노트북, 거치대, 외장하드", "노트북, 거치대"를 구매했다.

각 상품별 동시 구매횟수를 보자. ('키보드'을 구매한 사람이 '노트북'을 구매한 건수는 4건이다')

	노트북	거치대	파우치	외장하드
키보드	상품노출: 5 동시노출: 4 지지도: 4/10=0.4 신뢰도: 4/5=0.8	상품노출: 5 동시노출: 3 지지도: 3/10=0.3 신뢰도: 3/5=0.6	상품노출: 5 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/5=0.2	상품노출: 5 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/5=0.4

여기서부터 신뢰도(Confidence)라는 개념이 등장한다.

지지도는 어떤 아이템이나 아이템들의 출현확률(즉 여기서는 상품이 판매된 수)을 의미한다. 신뢰도는 어떤 사건으로부터 다른 어떤 사건이 일어날 확률을 의미한다.

(실제 구매목록이 아니라 꾸며낸 것이기에 좀 이상하지만, 데이터상으로 볼땐 '키보드' 구매자가 '노트북'을 구매한 사건이 80%(0.8)의 신뢰도를 가졌으므로, '키보드'만을 구매한 사람에게 '노트북'을 추천하면 좋아할 가능성이 높다는 의미가 될 것이다.)

좀더 풀어서 설명하겠다. 여기서 알아낼 수 있는 확률관계는 다음과 같을 것이다.

• '키보드'와 파우치가 동시에 판매될 경우는 총 10회 중 5회(50%)이다.
• '키보드'를 구매한 사람이 '파우치'를 구매할 경우는 총 5회 중 1회(20%)이다.
• '파우치'를 구매한 사람이 '키보드'를 구매할 경우는 총 3회 중 1회(33%)이다.

이를 지지도나 신뢰도 입장에서 풀어보면, 다음과 같은 의미가 된다.

• '키보드'와 '파우치'에 대한 지지도는 50%이다.
• '키보드'에서 '파우치'로의 신뢰도는 20%이다. (키보드 → 파우치)
• '파우치'에서 '키보드'로의 신뢰도는 33%이다. (파우치 → 키보드)

"파우치"를 구매한 사람이 "키보드"를 구매하는 경우가 그 반대 상황보다 많다는 것을 알 수 있다.

이제 더 나아가 아이템 수를 단계별로 늘려 같은 방식으로 생각해 본다.

	노트북, 거치대	거치대, 파우치	파우치, 외장하드	외장하드, 노트북	노트북, 파우치	거치대, 외장하드
키보드	상품노출: 5 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/5=0.4	상품노출: 5 동시노출: 0 지지도: 0 신뢰도: 0	상품노출: 5 동시노출: 0 지지도: 0 신뢰도: 0	상품노출: 5 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/5=0.4	상품노출: 5 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/5=0.2	상품노출: 5 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/5=0.2

(기껏 썼는데 좋은 예제가 만들어지지 않는다. ㅠㅠ 쓴게아까워서 지우지는 않겠;;)

'키보드' 말고 '외장하드' 기준으로 다시. (아몰랑ㅎ)

	노트북, 키보드	키보드, 거치대	거치대, 파우치	파우치, 노트북	노트북, 거치대	키보드, 파우치
외장하드	상품노출: 2 동시노출: 2 지지도: 2/10=0.2 신뢰도: 2/2=1 ☞ 100%	상품노출: 2 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/2=0.5 ☞ 50%	상품노출: 2 동시노출: 0 지지도: 0 신뢰도: 0 ☞ 0%	상품노출: 2 동시노출: 0 지지도: 0 신뢰도: 0 ☞ 0%	상품노출: 2 동시노출: 1 지지도: 1/10=0.1 신뢰도: 1/2=0.5 ☞ 50%	상품노출: 2 동시노출: 0 지지도: 0 신뢰도: 0 ☞ 0%

여기서는 '외장하드' 구매자가 '노트북'과 '키보드'를 함께 구매한 사건이 100%의 신뢰도를 가졌으므로, '외장하드'를 구매한 사람은 대부분(?) '노트북'과 '키보드'를 구매할 것이라는 예측이 가능하다.

이런 방식으로, 아이템세트의 요소 수를 늘려가며 지지도가 정해진 수치 이상인 조건들을 취해 신뢰도가 높은 세트를 솎아내면 연관규칙 테이블이 완성되게 된다.

(보통 최소 지지도(Minimum Support)를 맘대로 정해, 그 이하는 모두 버리고 신뢰도가 어느정도 높은 결과 세트만을 취하는 방법을 사용한다. 최소 지지도는 그야말로 '내맘'이다.)

하지만 이러한 Apriori 알고리즘은 속도가 매우 느리다는 취약점을 가지기에, 이 문제를 보완한 Partitioning, DHP, ECLAT, 등의 방법을 사용한다.

마치며.

사실, 처음 Apriori를 접할때 느낌은.. '그지같은것들, 별것도 아닌데 참 어렵게도 써 놨다~' 였습니다.ㅋㅋㅋㅋㅋㅋㅋㅋ

정말 아주 간단한 내용입니다. 그저 서로 함께 등장할 수 있는 확률(?)을 구하는게 전부입니다.

그래서 다른걸 찾다가 FP-Growth를 찾게 되었는데, 이게 정말 놀라웠답니다. ^^;;

응용할 수 있는 여지도 엄청났구요.

(저에게만 그런 느낌일 수 있으니 너무 기대는 마시고요;)