Realtime Contents Based Blog Recommend System

차례

• 개발 동기
• 문제 분석
• TF-IDF
• 수학적 유사도
• 데이터 분석 및 처리
• LSH
• Random Hyperplanes
• 빠른 유사도 연산

• Random Hyperplane Normal
• 분산 처리
• map reduce(단어 추출, TF-IDF)
• 연산의 멱등성
• Docker
• 구현 및 시연
• Future Works

블로그 글은 많은데

이 글과 비슷한 주제의 글은?

기존의 시스템

• 네이버 : 카테고리 기반, 조회수 기반
• 다음 : 카테고리 기반
• 이글루스 벨리 : 카테고리 기반
• 올블로그 : 메타 블로그 추천 수 기반

​

Recommend System

• contents based recommend
• 아이템 자체의 특성을 활용하여 추천하는 방법
• collaborative based
• 사용자의 행동 방식을 기반으로 아이템을 추천하는 방법
• item based
• 아이템과 아이템 사이의 유사도 산출을 사용한 방법
• user based
• 사용자와 사용자 사이의 유사도 산출을 사용한 방법

구글이 아닌 이상 collaborative 데이터를 얻을 수 없다.

collaborative based 는 사용자의 click, 이용 데이터 없이 추천해 줄 수 없음

Contents Based로 간다.

이렇게 된 이상

비슷한 블로그 글이란?

비슷한 구문 vs 비슷한 단어

• 비슷한 구문
• 주로 표절 체크
• 한 구문과 비슷한 구문이 다른 문서에 존재하는지 체크
• 비슷한 단어
• 주제가 비슷하면 자주 등장하는 단어가 비슷하다.
• 자주 쓰이는 단어를 추출하여 똑같은 구문이 없더라도 사용하는 단어가 같으면 추천

자주 쓰는 단어(TF-IDF)

• TF-IDF

​

​

​

​

자주 쓰는 단어(TF-IDF)

• TF(Term Frequency) : 문서에서 각 단어가 등장한 빈도를 나타낸다.
• DF(Document Frequency) : 모든 문서에서 해당 단어가 등장한 문서의 수를 나타낸다.
• TF-IDF : DF의 역수와 TF의 곱을 통해 얻는 값으로, 모든 문서에 대해서 단어가 어느 정도로 중요한 지를 나타내는 지표이다.
• 보통 IDF는 log normalization을 통해서 정규화 시킨다.

유사도

• cosine 유사도

• jaccard 유사도

비슷한 주제의 글

• 사용하는 단어가 비슷하다.
• 단어들 간의 중요도(TF-IDF)가 유사하다.

​

• 따라서 TF-IDF의 cosine 유사도가 높은 문서가 비슷한 주제의 글이 된다.

결국...

문제를 재정의 하면,

A글과 TF-IDF의 cosine 유사도가 높은 블로그 글을 찾는 것으로 정의할 수 있다.

Houston,

We Have Problem!

60,000,000

네이버, 다음, 티스토리, 구글 등에서 크롤링한 블로그 데이터

​

510,000

한국어 사전의 표제 단어수

6000만 x 51만

전체 TF-IDF 테이블의 크기

LSH(Local Sensitive Hashing)

• 유사도가 높은 데이터들을 찾아내는 hash.
• Diffuse 효과가 없는 hash.
• 특정 유사도를 유지시키는 hash.
• 차원을 reduction하는 효과 가 있다.
• MinHash, Random Hyperplane Projection, etc.

Random Hyperplane

• 특정 벡터를 Hyperplane을 기준으로 두 Half-Space로 나눈다.
• 이는 cosine 유사도를 유지 시켜준다.

​

• 특정 벡터와 Hyperplane간의 cosine 유사도가 높으면 같은 Half-Space에 있을 확률이 높다.
• 의미가 있으려면 충분히 공간의 갯수가 많아야 한다.

​

Random Hyperplane

• plane은 법선 벡터 v로 특정 지을 수 있다.

​

• 특정 벡터가 어느 Half-Space에 있는 지를 구하는 방법.
• (pseudo code) if x•v > 0 then 1 else -1

64개의 Hyperplane

• 2⁶⁴개의 원점을 지나는 hyperplane으로 나누어진 공간.
• 2⁶⁴ >> 6000만 데이터.
• 한 공간에는 하나의 blog만 있을 확률이 높다.
• 만약 같은 공간에 있다면 거의 동일한 글이다.
• blog를 대표하는 feature로 사용 가능하다.
• 51만 차원 -> 64차원

두 블로그 사이의 유사도

• 비슷한 블로그는 LSH Value가 서로 유사하다.
• LSH Value의 각 Element가 1 or -1 이므로(법선 벡터와 같은 방향인지 다른 방향인지)
• TF-IDF가 cosine 유사 -> LSH value가 jaccard 유사.
• 64bit int 에 담을 수 있다.
• 두 LSH Value는 XOR연산으로 빠르게 jaccard 유사도를 계산할 수 있다.
• cpu register에서 연산.
• 크기가 작으므로 cache나 paging 이 용이.
• CPU instraction으로 직접적인 연산 가능.

두 블로그 사이의 유사도 빠른 계산

Mapping

CPU 효율성

• 6000만 Cosine 연산 비용 > 6000만 XOR 연산 비용
• consine : 수백~수만 클럭(차원이 높을수록 증가)
• XOR : 수클럭(64차원 까지는 동일)

​

​

메모리 효율성

• Cosine Method : 6000만 x 51만 x 4byte = 113 GB

​

• XOR Method : 60M x 16byte = 0.8 GB

​

그래서 단일 머신에 올려서 시스템을 돌릴 수 있다.

​

​

​

Random Hyperplane Normal

Random Hyperplane의 어려운 점

• 510k 차원의 v벡터(법선 벡터)의 생성 및 유지.
• 자주 참조되고 분산 처리되더라도 모든 머신에서 같아야 한다.
• DB를 통해서 관리하거나 미리 등장할 모든 단어에 대해서 generate 되어 있어야 한다.
• 매 백터 계산마다 참조 되어야 한다.
• 등장할 모든 단어를 알고 미리 Vector generate 해둘 수 없다.
• 하루에도 수십개의 새로운 단어(?)가 나올수 있다.
• 하나의 단어가 추가되면 -> 차원이 1개 추가 된다.

Generate Random Hyperplane Normal Vector

sha-512

법선 벡터

Generate Random Hyperplane Normal Vector

• SHA-512 해쉬의 값을 Random Vector로 활용.
• SHA-512 해쉬는 diffuse 효과가 있다.
• Pseudo random으로 활용 가능하다.
• SHA-512의 결과는 어디에서 실행 하던 같다.
• 51만의 벡터를 생성 / 저장 / 관리할 필요가 없다.
• 연산 속도가 빠르다.

​

• SHA-512 해쉬의 2byte씩을 끊어 Vector의 Element로 활용.
• 64개의 hyperplain 이므로 8byte로 끊어도 된다.

v•x

• V나 X에서 0인 요소는 연산하지 않아도 된다.
• 문서에 존재하지 않는 단어에 대해서는 연산하지 않는다.
• 연산 횟수는 오직 문서의 길이에만 연관 있다. (<< 51만)
• 각 문서 별로 독립적으로 분산 처리 가능하다.

TF-IDF to LSH Value

기존 TF-IDF

LSH(Random Hyperplane)

단어 추출

단어 추출

• KoNLPy라는 한국어 정보처리 Python 패키지를 사용.

​

• 내부의 여러 형태소 분석 모듈 중 Mecab을 사용.

​

​

분산처리(TF-IDF 추출, LSH 연산)

연산의 독립성

• 각 연산은 문서 별로 독립 연산이 가능하다.
• TF는 각 문서 별로 독립적으로 연산이 가능.
• DF는 각 문서 별로 빈도수 추출 후 이후에 병합하여도 무방.
• TF-IDF는 DF가 이미 추출되었다는 가정 하에 문서 별로 독립 연산 가능 .
• TF-IDF에서 Random hyperplane을 이용한 LSH연산은 문서별로 독립 연산 가능.

​

• 결국, TF-IDF 추출 및 LSH과정은 map reduce로 연산이 가능함을 의미한다.

변환 과정

문서

TF/Doc

DF

(Cluster)

Map

Noun

Extraction

Reduce

DF

(Total)

TF-IDF

Map

빈도 계산

Map�Side-join

LSH

Value

Recommender�Engine

Map

Reduce

병합

One More Things

• Random Hyperplane 과 위 과정은 멱등성이 있으므로 �몇 번 반복한다고 결과가 달라지지 않는다.
• 각 단계의 연산은 독립이다.
• 결과적으로 지속적으로 문서를 추가해도 상관없다.
• 연산의 부하가 심할 때는 별도의 클러스터에서 연산 하여도 상관없다.
• 각 단계는 실시간을 여러 번 행해져도 LSH Value에는 아무런 영향이 없음.
• 문서의 실시간 append가 가능.
• 기존에는 batch가 주류여서 새로운 문서를 모았다가 반영.

Docker

Docker

• Linux Container.
• 프로그램 실행에 필요한 환경을 가상화.
• 환경의 가상화 일 뿐 CPU, 메모리, I/O는 기존 OS를 사용.
• docker 를 사용한 process는 host process와 동일.
• 가상 머신보다 성능이 월등히 우수.
• 이미지만 복사하면 즉시 Cluster에 Node 추가 가능.
• OS를 가리지 않고 동작하는 image를 만들 수 있다.

Docker Image

• tf-idf에 사용되는 platform/library
• Python, mecab, gcc, g++, gclibs …
• 복잡한 환경 설정.

​

• Docker Image로 작성하여 손쉽게 클러스터를 확보할 수 있도록 함.
• 단순한 image 복사만으로 모든 환경 설정 완료.
• 컴퓨터 대수만 확보된다면 즉각적으로 Node의 갯수를 늘릴수 있다.

Docker Cluster

실제 구현

좌측목록 클릭

http://bigdata.bluemir.me

Future Works

새로 추가되는 글에 대한 값들을 모델에 실시간으로 추가.

제목에 나타나는 키워드에 높은 가중치 부여, 이를 통한 추천 품질 향상.

유사도 검사 알고리즘을 이용한 블로그 글 검색.

추천 서비스를 기반으로, 기존에 수집할 수 없었던 Collaborative 정보 수집.

Reference

• http://www.slideshare.net/deview/261-52784785
• http://web.stanford.edu/class/cs345a/slides/05-LSH.pdf
• http://www.slideshare.net/chiwanpark/presentation-31773587
• Li, Bin, and Yuan Guoyong. "Improvement of TF-IDF Algorithm Based on Hadoop Framework." Computer Application and System Modeling International Conference Proceedings, Computer Science and Electronic Technology International Society 2012: 0391-0393.