시간여행자: 11월 2018

2018년 11월 16일 금요일

영웅의시련 한국서버 없나? 😑

아 증말 주변에 러시아애들밖에없고..

나혼자 재미도 없고.. ㅠㅠ

서버옮겨서 제대로 키워보고싶구만. 😓

2018년 11월 12일 월요일

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크 상품명'으로 예를 만들겠음)

데오드란트, 니베아, 스틱, 세이퍼진

니베아, 스프레이, 세이퍼진

데오드란트, 니베아, 스틱, 세이퍼진

데오드란트, 니베아, 스프레이, 세이퍼진

데오드란트, 니베아, 스프레이, 스틱, 세이퍼진

스프레이, 니베아, 스틱

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

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

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

니베아, 세이퍼진, 데오드란트, 스틱
니베아, 세이퍼진, 스프레이
니베아, 세이퍼진, 데오드란트, 스틱
니베아, 세이퍼진, 데오드란트, 스프레이
니베아, 세이퍼진, 데오드란트, 스프레이, 스틱
니베아, 스프레이, 스틱

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

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

이제 아까 만들어놓은 배열(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을 찾는다.

"스틱"이 존재하지 않는 경로는 제거한다.
그리고 support count를 업데이트하는데, 스틱의 support count를 고스란히 올려준다고 생각하면 된다.
따라서 "스프레이"는 1이 되고, 데오드란트는 좌측 "스틱"의 2와 우측 "스틱"의 1이 합산된 3이 된다.
같은 방법으로 부모노드의 support count를 업데이트 한다.
목표로 했던 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를 이용하실 생각이라면 아마도 이러한 점을 유념하셔야 할 것입니다.

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

2018년 11월 6일 화요일

연관규칙분석 (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를 찾게 되었는데, 이게 정말 놀라웠답니다. ^^;;

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

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

TF-IDF에 대하여

TF-IDF란

TF-IDF(Term Frequency - Inverse Document Frequency)는 Term의 가중치를 구하는 가장 흔한 알고리즘이다. ( Scoring, 참고: TF-IDF (Wikipedia) )

검색에 있어 거의 바이블(?)격인 알고리즘이기에, 반드시 알아둬야하는 개념이라 할 수 있다.

TFIDF는, 문서의 핵심어를 추출하거나, 검색 엔진에서 검색 결과의 순위를 결정하거나, 문서들 사이의 비슷한 정도를 구하는 등의 용도로 사용할 수 있다.

물론 ElasticSearch 5.0.0 GA 버전 이후 기본 scoring알고리즘이 TF-IDF에서 BM25로 변경되었으나, TF-IDF는 반드시 알아둬야할 개념임에는 분명하다.
그리고 "Term"이라는 것은 조각, 토큰과 유사한 의미로, 문헌분석의 경우에서는 단어 정도로 생각하면 좋을것이다.

Formula

공식이라고 하니 좀 복잡해보일 수 있다. 하지만 사실 간단한 의미이다. 위 공식을 쉽게 설명하자면,

"해당 단어(Term)이 문서에 몇번 노출되는가? 그리고 전체 데이터 중 해당 단어는 얼마나 흔한가?"

라는 의미이다.

결국 문헌상 많이 나타나는 단어가 있다면 그 단어는 매우 중요하며, 반대로 너무도 많이 나타나는 단어는 희소가치가 떨어져서 중요하지 않다는 의미이다.

Formula - Common

공식의 큰 뜻(?)을 이해했다면 이제 공식이 어떻게 동작하는지 보자.

TF라 함은 "Term Frequency" 즉, Term의 빈도이다. 위에 언급한 "문서에 몇번 노출되는가?"의 의미이다.

IDF에서 DF는 "Document Frequency" 즉, Term이 포함된 문서의 빈도이다. 이를 "Inverse" 즉, 역수를 취하는 것이다.

2은 2배를 의미하지만, ½은 반(Half)을 의미한다. 역수를 취한다는 의미는 결국 정 반대로 가중치를 책정한다는 의미이다.

예를들어보면,

I love dogs.
I hate dogs and knitting.
Knitting is my hobby and my passion.

아래는 위 내용을 각 문헌을 키워드 대비 빈도로 보기 좋게 정리한 표이다.

	I	love	dogs	hate	and	knitting	is	my	hobby	passion
D-1	1	1	1
D-2	1		1	1	1	1
D-3					1	1	1	2	1	1

※ 키워드별 빈도

D1문서에서의 "dogs"를 기준으로 계산해보자.

"dogs"는 D1에서 1회 나타났다. 따라서 TF는 1이 된다.

그에 반해 "dogs"는 전체 3개 문서 중 2개의 문서에서 나타났다. 따라서 DF는 2/3이다.

IDF는 역수이므로 3/2이 된다.

즉, 결과는 1 x (3/2) ≒ 1.5가 된다.

같은 방식으로 나머지를 모두 계산해보면,

	I	love	dogs	hate	and	knitting	is	my	hobby	passion
D-1	1.5	3	1.5
D-2	1.5		1.5	3	1.5	1.5
D-3					1.5	1.5	3	6	3	3

※ TF * (N/DF)

이런 방식으로 각 문서상 Term들의 중요도를 분석할 수 있게된다.

예외처리에 대해

D-1문서에서 hate의 가중치를 보려한다고 생각해보자.

계산식은 TF * (N/log(DF))이므로 대입해보면 0 * (1 / 0) 이기에, 결국 0으로 나누려하는 error가 발생한다.

따라서 일반적으로는 DF(혹은 아래 설명할 로그스케일 빈도에서의 TF)가 0이 나오는것을 방지하기 위해 (+1)을 해준다.

※ TF * ( N/ log(DF+1) )

Formula - IDF & Logarithm

자, 그럼 공식에서 사용된 log는 무어냐?

사실 log는 없어도 되는 놈이다. 특히 위와 같이 단순한 표본분석에서는 log는 필요치 않을 수도 있다.
하지만 데이터가 커지면? 좀더 다양한 데이터를 대상으로 한다면? 그때 상황이 달라진다.

다들 log 그래프를 기억(?)하고 있겠지만;; ㅎㅎ

log는 밑수가 1보다 큰 경우 점점 증가하지만 정해진 한계값을 넘어서지 않게 수렴되는 것을 볼 수 있다.

결국 log를 사용한 이유는 "리미터"을 주기 위해서이다.

전체 문헌상에 정말로 많이 노출되는 Term이나 혹은 거의 노출되지 않는 Term은 그 가중치가 엄청나게 높거나 낮은 수치를 가지게 될 텐데, 방대한 문서를 위와같이 계산하다보면 어떤 가중치는 천정부지 치솟게 되고 나중에는 관리는 커녕 계산조차 어려워질 것이다.

따라서 log로서 이러한 편차를 줄이는 것이다.

위 결과표를 IDF에 log를 적용해 계산해보면 다음과 같다.

	I	love	dogs	hate	and	knitting	is	my	hobby	passion
D-1	0.18	0.48	0.18
D-2	0.18		0.18	0.48	0.18	0.18
D-3					0.18	0.18	0.48	0.95	0.48	0.48

※ TF * log(N/(DF+1))

결국 특정 구간 값을 가지게 된다. 이것이 바로 cosine normalization(코사인 평준화)의 가장 간단한 예이다.
코사인평준화에 대한 내용은 "cosine similarity", 그러니까 "문헌 유사도" 중 "코사인유사도"에서 다시 언급되게 된다.
여기까지 이해했다면 TF-IDF는 사실 다 이해한 것이나 마찬가지다. ^^

Formula - TF

하지만, 한가지 문제가 더 남았다. IDF뿐만이 아니고 TF가 무턱대고 커지는 경우이다.

문서상에 매우 악의적(?)으로 반복되는 Term이 존재할 수가 있다. 이 경우 언급한 IDF의 문제처럼 TF역시 문제가 된다.

따라서 이를 해결하기 위해 일반적으로 다음의 3가지 방법이 쓰인다.

불린(Boolean)빈도

단어의 노출빈도를 카운팅 하지 않고, 그저 존재유무만을 따진다.
즉, 문헌상 Term이 있으면 1, 없으면 0을 적용하여 하나만 있든 1,000개가 있든 같은 상황으로 간주하는 방식이다.
위 표의 경우, my가 hobby나 passion과 다르지않은 값을 가지게 된다.

로그 스케일(Log Scale) 빈도

로그 스케일은 위에 설명과 동일하다. 즉 매우 커지는 TF값에 IDF처럼 리미터를 주는 것이다. (zero값을 피하기 위해 역시 +1을 해 준다.)
tf(t,d) = log (f(t,d) +1);

증가빈도

문서 길이에 따라 단어의 상대적 빈도 값을 조정해주는 방법으로 이 방법을 쓰면 0과 1사이에 값으로 제한할 수 있다.
문서 내 단어들의 단어 빈도 중 최대 빈도로 단어빈도를 나눠주는 방법이다.

참고

증가빈도에서의 0.5는 평준화를 위한 임의값이라 보면 좋다. 사실 다음과 같은 공식에서의 대표적인 K값일 뿐이다.