ݺߣ

ݺߣShare a Scribd company logo

Hadoop 기반 문서 검색

•
•
치완 박
치완 박

MapReduce 기반의 TF-IDF를 구현해 봅니다.

1 of 48
Downloaded 52 times
Hadoop 기반 문서 검색 박치완 Software Maestro 3rd Mentee chiwanpark91@gmail.com September 17, 2012 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 1 / 47
Section 1 검색 시스템 소개 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 2 / 47
목표 1 방대한 양의 데이터를 수집하고, HDFS에 저장하는 작업을 통해 HDFS에 대해서 익힌다. 2 오픈소스 검색엔진 Lucene에서 사용하고 있는 TF-IDF(Term Frequency-Inverse Document Frequency) 알고리즘을 분산 환경에 맞게 설계하여, MapReduce로 구현해본다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 3 / 47
시스템 구조 전체 시스템은 크게 3가지 구성요소로 이루어져 있다. 1 수집 - 웹에서 문서를 수집해 단순한 가공만 거친 후, 분산 파일 시스템(HDFS)에 업로드한다. 2 색인 - 수집 된 문서를 Hadoop을 통해 Full-Text 색인 과정(TF-IDF)을 거친다. 3 검색 - 사용자의 질의어가 들어오면, 이를 미리 색인된 데이터와 비교하여 연관성이 높은 순서대로 보여준다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 4 / 47
Section 2 수집 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 5 / 47
수집기(Crawler) 요구사항 1 웹에서 문서를 수집해 HDFS에 업로드 할 수 있어야 한다. 2 수집한 문서를 기초적인 가공(제목과 본문 분리 등)을 할 수 있어야 한다. 3 특정 URL 규칙을 만족하는 문서만 수집할 수 있어야 한다. 4 문서 수집은 robots.txt등 수집기가 지켜야 할 사항들을 준수한다. 5 수집 대상은 기본적으로 IT 관련 블로그 포스트를 우선적으로 하나, Hadoop을 이용하는 만큼 많은 데이터를 확보할 수 있도록 추후 확장한다. 6 수집 과정 중 중단이 일어나더라도 이어서 수집할 수 있어야 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 6 / 47
수집기 구조 수집기는 크게 두 부분, Manager와 Worker로 구성된다. Manager 수집 과정을 사용자에게 보여주는 프로세스다. 수집 중단, 재개, 새로운 규칙 추가 등을 할 수 있다. Worker 실제 수집을 진행하는 프로세스다. Raw Data를 가공하여 HDFS에 올리는 역할도 수행한다. 매 수집 과정마다 Manager 프로세스에게 보고하여야 한다. 수집 중단, 재개 등 Manager의 요청을 처리 할 수 있어야 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 7 / 47
Section 3 색인 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 8 / 47
TF-IDF 소개 특정 단어와 문서 사이의 연관성을 구하는 알고리즘이다. 문서에서 등장하는 단어 빈도 TF(Term Frequency)와 전체 문서 집합에서 단어 빈도의 역수 IDF(Inverse Document Frequency)를 기본으로 계산한다. 단순한 TF-IDF 보다는 변형을 가한 TF-IDF가 정확도가 높다. 어떤 문서에 특정 단어가 자주 출현한다면, 해당 단어는 그 문서와 연관성이 높다고 말할 수 있다. 건강과 관련된 문서는 건강이라는 단어를 다수 포함할 수 밖에 없다. 하지만, 무조건적으로 출현 빈도에 의존하면 전체적인 정확도가 떨어진다. 어느 문서에나 빈번하게 등장하는 단어는 연관성 측정에서 제외해야 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 9 / 47
TF-IDF Algorithm 내용 소개에 앞서, 앞으로 사용되는 공통되는 표현을 먼저 소개한다. 표기 의미 t 임의의 단어 (일반적으로 문서 내부에서 단어를 추출) D 임의의 문서 집합 n t,d 단어 t 가 문서 d 에 나타나는 횟수 |D| 해당 문서 집합에 포함된 문서의 수 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 10 / 47
TF-IDF Algorithm Term Frequency는 문서에서 빈도가 높으면 높을 수록 큰 값을 가져야 하므로 아래와 같이 써볼 수 있다. t f t,d = n t,d Inverse Document Frequency는 문서 집합에서 단어의 빈도가 낮을 수록 커져야 하므로 아래와 같이 쓸 수 있다. id f t,d = 1 |{d : t ∈ d ∈ D}| + 1 위의 계산을 통해 TF와 IDF를 구했다면, 우리는 특정 단어 t 와 특정 문서 집합 D, 그리고 집합에 속한 문서 d 에 대해서 TF-IDF 가중치를 다음 식으로 구할 수 있다. t f id f t,d,D = t f t,d · id f t,d (t ∈ d ∈ D) 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 11 / 47
Enhanced TF-IDF 앞서 알아본 TF-IDF 알고리즘는 몇 가지 부족한 점이 있다. 1 길이가 긴 문서는 빈도 수가 클 확률이 높고, 길이가 짧은 문서는 빈도 수가 작을 확률이 높다. 자연히 위의 경우에는 길이가 짧은 문서가 TF값이 높아 위에 나올 확률이 높아진다. 2 단어 1000개로 이루어진 문서 안에서 1번 나온 단어 A에 비해 2번 나온 단어 B는 연관도가 두 배라고 할 수 있을까? 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 12 / 47
Enhanced TF-IDF 이와 같은 문제들을 해결하기 위해 TF-IDF 알고리즘에 로그 함수를 도입하였다.  t f t,d =  1 + ln(n t,d ) if n t,d > 0  0 if n t,d = 0 id f t,d = ln( 박치완 (SW Maestro) |D| |{d : t ∈ d ∈ D}| + 1 Hadoop 기반 문서 검색 ) September 17, 2012 13 / 47
Example 임의의 단어 t 를 ‘health’로 지정하고 아래 예제를 계산해 보자. id f t,d = ln( 4 ) = 0.6931 2 문서 d1 문서 내용 ni,d Health is a necessary condi- n t,d t f t,d t f id f 7 1 0.134 0.093 11 0 0 0 tion for happiness. d2 It is the business of the police to protect the community. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 14 / 47
Example 이어서 문서 문서 내용 d3 ni,d The city health business de- n t,d t f t,d t f id f 15 2 0.13 0.087 7 0 0 0 partment runs several free clinics for health professionals throughout the year. d4 That plane crash was a terrible business. 따라서, 사용자가 ‘health’를 질의어로 선택하였을 경우 TF-IDF 계산값이 높은 순서(d1 , d3 )대로 보여주게 될 것이다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 15 / 47
Section 4 검색 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 16 / 47
Vector Space Model 문서와 단어 사이의 관계를 표현하기 위해 벡터를 사용한다. 문서 또는 질의어가 Vector가 되고, Vector의 각 차원(Dimension)이 각 단어별 가중치를 갖는 값으로 표현된다. 일반식을 통해 특정 문서 d 를 VSM으로 표현하면 다음과 같다. Vd = [w1,d , w2,d , . . . , w N ,d ] T 이 때, 각 단어와 문서 사이의 연관성 가중치 w t,d 는 아래의 식으로 구할 수 있다. w t,d = t f id f t,d,D = t f t,d · id f t,d 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 17 / 47
Cosine Similarity q는 사용자가 입는 각각의 문서 벡터이다. 이 T d1 q 0       α  X $d   $ 2 $$$ $$$  θ $ $   E 벡터간의 사이각에 대한 정보를 cos과 벡터 내적의 관계에서 구할 수 있다. cosα = d1 · q |d1 ||q| 두 벡터가 유사하고 연관성이 있으면 있을수록 두 벡터의 사이각은 작아지게 되고, 우리는 연관성을 나타내는 척도로 Figure : 문서와 질의어를 Cosine Similarity를 사용할 수 있다. 벡터로 표현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 18 / 47
문서 검색 알고리즘 위의 내용들을 종합하여, 문서 검색 알고리즘을 기술하면 아래와 같다. 1 입력된 질의어를 문서 색인 과정과 동일한 과정을 거쳐 벡터로 표현한다. 2 미리 색인된 데이터베이스에서 질의어를 포함한 문서 목록을 불러온다. 3 각각의 문서에 대해 질의어 벡터와의 Cosine Similarity를 계산한다. 4 계산된 Similarity에 따라 정렬하여 상위 문서들을 출력한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 19 / 47
Section 5 구현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 20 / 47
Subsection 1 TF-IDF(색인)의 구현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 21 / 47
Flow Diagram 규칙 MapReduce Flow를 설명하기 전에, Flow Diagram에서 사용하는 기호들을 소개한다. - HDFS가 아닌 다른 데이터 소스에서의 데이터 입출력을 의미한다. - HDFS에서의 TextFile 입출력을 의미한다. - 시스템 내부에서의 데이터 입출력을 의미한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 22 / 47
TF-IDF 색인 과정 Data Flow Diagram Flow A Term Document Index Flow B Document Term Index MySQL Flow C Calculate TF Document MySQL MySQL Flow D Calculate DF MySQL 크게 두 가지 작업으로 분류할 수 있다. 가중치 계산의 속도를 높이기 위해 TD, DT 색인과정을 거치는 작업 실제 가중치 계산에 필요한 TF, DF를 계산하는 작업 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 23 / 47
Flow A. Term-Document Index MapReduce Job Mapper Reducer Document Noun Extracter ID: 13, 삼성과 애플의 잇단 소송 전쟁이 계속되 고 있다. [삼성,애플,소송,전 쟁,계속] Document Noun Extracter ID: 14, 애플이 최근 OS X 마운틴 라이언을 출시했 다. [애플,OS,X,마운 틴,라이언,출시] Term Document Indexer MySQL (TD Index) 삼성, 13 애플, 13 애플, 14 마운틴, 14 …… 삼성, [13] 애플, [13, 14] 마운틴, [14] …… 특정 단어가 포함된 문서들의 인덱스를 생성하는 작업 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 24 / 47
Flow B. Document-Term Index MapReduce Job Mapper Document Noun Extracter ID: 13, 삼성과 애플의 잇단 소송 전쟁이 계속되 고 있다. [삼성,애플,소송,전 쟁,계속] Document Noun Extracter ID: 14, 애플이 최근 OS X 마운틴 라이언을 출시했 다. Document Term Indexer MySQL (DT Index) 13, [삼성,……,계속] 14,[애플,……출시] [애플,OS,X,마운 틴,라이언,출시] 특정 문서에 포함된 단어들의 인덱스를 생성하는 작업 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 25 / 47
Flow C. Term Frequency MapReduce Job Mapper Combiner Document Noun Extracter ID: 15, 애플이 앱스토어 에 이어 맥 앱스토어를 개 시하였다. [애플, 앱스토어, 맥, 앱스토어, 개시] Document Noun Extracter ID: 27, OmmiGraffle 은 맥 앱스토어에서 99달 러에 판매되고있다. Term Frequency Counter MySQL (TF) 애플@15, 1 앱스토어@15, 2 달러@27, 1 …… [OmmiGraffle, 맥, 앱스토어, 99, 달러, 판매] 특정 문서에 포함된 특정 단어에 대해 빈도 수를 계산하는 작업 추후 다양한 활용을 위해 일단 WordCount만 수행한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 26 / 47
Flow D. Document Frequency SQL Query MySQL (TD Index) Document Frequency Counter MySQL (DF) 삼성, [13] 애플, [13, 14] 마운틴, [14] …… 삼성, 1 애플, 2 마운틴, 1 …… IDF를 계산하기 위해 선행되어야 하는 DF 계산하는 작업 추후 다양한 활용을 위해 일단 DocumentCount만 수행한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 27 / 47
Subsection 2 검색의 구현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 28 / 47
검색 과정 Data Flow Diagram Query (User Input) Flow A Vectorize Flow B List Preload Flow C Scoring MySQL (Temporary) MySQL Flow D Sorting and Paging Search Result 사용자로부터 입력된 질의어(Query)로 검색을 수행하는 과정 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 29 / 47
Flow A. Vectorize Query (User Input) Noun Extracter 애플의 신형 맥북 Term Frequency Counter [애플, 신형, 맥북] Next Flow 애플, 1, 신형, 1, 맥북, 1 사용자가 입력한 질의어를 VSM에 표현할 벡터로 변환하는 과정 여러가지 활용을 위해 오로지 Term Frequency 벡터로만 변환한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 30 / 47
Flow B. List Preload Query Vector Merge document list contain terms in query vector Load Document Vector Information MySQL 질의어 벡터에 속한 단어들을 포함하고 있는 문서 리스트를 불러와 합친다. 전체 목록을 합칠 경우, 고려해야하는 문서양이 많아지므로 해당 단어의 TF가 높은 순으로 정렬하여 300개 미만으로 가져오도록 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 31 / 47
Flow C. Scoring Loaded Document Vector Query Vector Scoring TF-IDF 애플, 1, 신형, 1, 맥북, 1 Load Document Frequency MySQL 애플, 0.34, 신형, 0.002, 맥북, 0.65 13, 0.00028, 23, 0.0029, 17, 0.0013 …. 질의어 벡터와 미리 불러온 비교 문서 목록의 연관성을 앞서 사용했던 Cosine-Similarity 방법을 통해 계산한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 32 / 47
Flow D. Sorting and Paging Presorted TF-IDF Scores Sorting 13, 0.00028, 23, 0.0029, 17, 0.0013 …. Sorted Data 23, 0.0029, 17, 0.0013, 13, 0.00028, …. 계산된 결과를 정렬하여 출력한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 33 / 47
Section 6 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 34 / 47
테스트 환경 소개 SKT T cloud biz 서버 4대 서버 1대의 사양: 1 Vcore, 2GB RAM, 40GB HDD, CentOS 5.5 64bit Sun Java 1.6.0_35 Apache Hadoop 1.0.3 서버 IP Hadoop1: 1.234.45.90 (Namenode, Secondary Namenode) Hadoop2: 1.234.45.94 (Datanode) Hadoop3: 1.234.62.102 (Datanode) Hadoop4: 1.234.62.101 (Datanode) 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 35 / 47
색인 과정 테스트 색인 과정은 Hadoop1 (1.234.45.90) 서버에 ssh로 접속해 이루어진다. 색인, 검색 과정에 사용할 데이터는 HDFS에서 /chiwanpark/memento-input에 올려져 있어야 한다. hadoop jar memento-engine-0.1-SNAPSHOT.jar com.chiwanpark.memento.mapreduce.WorkRunner 입력 파일 갯수에 따라 시간이 소요된다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 36 / 47
색인 과정 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 37 / 47
검색 과정 테스트 검색 과정 역시 Hadoop1 서버에 ssh로 접속해 테스트한다. java -classpath memento-engine-0.1-SNAPSHOT.jar:/opt/hadoop/conf com.chiwanpark.memento.searcher.cli.SearchRunner –query 스마트폰 명령을 수행하면 그 결과로 문서 id와 TF-IDF Score를 보여준다. 문서 ID를 통해 HDFS에서 해당 문서를 열람할 수 있다. hadoop fs -cat /chiwanpark/memento-input /e02f5b1df830e8fcf89df333dc2dd642a9f0569ee6aea26cc1e3ec3a22e4 b988bfadb397c1ba7bd593feb5bd99276b9ce15a84741b5fe583d1dc2cb9 110ae70c.txt 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 38 / 47
검색 과정 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 39 / 47
검색 과정 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 40 / 47
Section 7 토의 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 41 / 47
Subsection 1 성능 측정과 품질 검증 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 42 / 47
성능과 품질 검증 방법 성능 측정은 전체 MapReduce의 수행 시간을 구하고, 해당 시간 동안 처리한 파일의 수를 구해 성능 측정의 기준으로 삼는다. 품질 검증은 이번 TF-IDF 시스템 구현이 Lucene의 시스템과 유사한 부분이 많이 Lucene에 해당 도큐먼트 집합을 넣었을 때의 Score와 구현한 시스템이 계산한 TF-IDF Score를 비교하는 방법을 생각해 볼 수 있다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 43 / 47
성능 측정 결과 Test1 Job1 - 102개 문서/3분 58초 (참고 자료 열기) Job2 - 102개 문서/3분 43초 (참고 자료 열기) 초당 0.22개 문서 처리 Test2 Job1 - 99개 문서/3분 54초 (참고 자료 열기) Job2 - 99개 문서/4분 4초 (참고 자료 열기) 초당 0.21개 문서 처리 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 44 / 47
성능 측정 결과 Test3 Job1 230개 문서/8분 44초 (참고 자료 열기) Job2 230개 문서/8분 16초 (참고 자료 열기) 초당 0.22개 문서 처리 Test4 Job1 1862개 문서/1시간 3분 55초 (참고 자료 열기) Job2 1862개 문서/1시간 4분 27초 (참고 자료 열기) 초당 0.24개 문서 처리 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 45 / 47
Subsection 2 개선 사항 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 46 / 47
품질 개선 사항 이번 프로젝트에서 사용한 한나눔 형태소 분석기의 분석 품질이 좋지 않아, 오히려 공백을 기준으로 단어를 분리하고 그 결과에서 조사를 직접 제거한 후, 미리 준비한 단어 사전과 매칭하여 키워드를 추출하는 방법이 더 좋은 품질을 가져올 수 있다고 생각한다. 버즈니 형태소 분석기의 경우 분석 품질은 우수하나 많은 양의 자료를 처리할 수 없어 사용하지 않았다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 47 / 47
성능 개선 사항 데이터 저장 구조가 현재는 하나의 문서를 하나의 파일로 구현하였는데, 로그 분석 결과 Hadoop에서 File Split마다 Mapper 클래스를 초기화하기에 이 때 초기화 시간으로 많은 시간을 소요하였다. 따라서 이를 개선하여, 하나의 문서를 Single line으로 표현하고 수십개의 문서를 묶어서 Split 단위를 늘려 초기화 횟수를 감소시킴으로써 성능 향상을 꾀할 수 있다. 테스트 시스템에서는 Cloud System 4대를 사용하였는데, 이는 VM으로 이루어져 I/O 성능이 별로 좋지 않다. VM이 아닌 실제 시스템에서 돌리면 보다 나은 성능을 보여줄 것으로 기대한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 48 / 47

More Related Content

Hadoop 기반 문서 검색

  • 1. Hadoop 기반 문서 검색 박치완 Software Maestro 3rd Mentee chiwanpark91@gmail.com September 17, 2012 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 1 / 47
  • 2. Section 1 검색 시스템 소개 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 2 / 47
  • 3. 목표 1 방대한 양의 데이터를 수집하고, HDFS에 저장하는 작업을 통해 HDFS에 대해서 익힌다. 2 오픈소스 검색엔진 Lucene에서 사용하고 있는 TF-IDF(Term Frequency-Inverse Document Frequency) 알고리즘을 분산 환경에 맞게 설계하여, MapReduce로 구현해본다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 3 / 47
  • 4. 시스템 구조 전체 시스템은 크게 3가지 구성요소로 이루어져 있다. 1 수집 - 웹에서 문서를 수집해 단순한 가공만 거친 후, 분산 파일 시스템(HDFS)에 업로드한다. 2 색인 - 수집 된 문서를 Hadoop을 통해 Full-Text 색인 과정(TF-IDF)을 거친다. 3 검색 - 사용자의 질의어가 들어오면, 이를 미리 색인된 데이터와 비교하여 연관성이 높은 순서대로 보여준다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 4 / 47
  • 5. Section 2 수집 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 5 / 47
  • 6. 수집기(Crawler) 요구사항 1 웹에서 문서를 수집해 HDFS에 업로드 할 수 있어야 한다. 2 수집한 문서를 기초적인 가공(제목과 본문 분리 등)을 할 수 있어야 한다. 3 특정 URL 규칙을 만족하는 문서만 수집할 수 있어야 한다. 4 문서 수집은 robots.txt등 수집기가 지켜야 할 사항들을 준수한다. 5 수집 대상은 기본적으로 IT 관련 블로그 포스트를 우선적으로 하나, Hadoop을 이용하는 만큼 많은 데이터를 확보할 수 있도록 추후 확장한다. 6 수집 과정 중 중단이 일어나더라도 이어서 수집할 수 있어야 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 6 / 47
  • 7. 수집기 구조 수집기는 크게 두 부분, Manager와 Worker로 구성된다. Manager 수집 과정을 사용자에게 보여주는 프로세스다. 수집 중단, 재개, 새로운 규칙 추가 등을 할 수 있다. Worker 실제 수집을 진행하는 프로세스다. Raw Data를 가공하여 HDFS에 올리는 역할도 수행한다. 매 수집 과정마다 Manager 프로세스에게 보고하여야 한다. 수집 중단, 재개 등 Manager의 요청을 처리 할 수 있어야 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 7 / 47
  • 8. Section 3 색인 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 8 / 47
  • 9. TF-IDF 소개 특정 단어와 문서 사이의 연관성을 구하는 알고리즘이다. 문서에서 등장하는 단어 빈도 TF(Term Frequency)와 전체 문서 집합에서 단어 빈도의 역수 IDF(Inverse Document Frequency)를 기본으로 계산한다. 단순한 TF-IDF 보다는 변형을 가한 TF-IDF가 정확도가 높다. 어떤 문서에 특정 단어가 자주 출현한다면, 해당 단어는 그 문서와 연관성이 높다고 말할 수 있다. 건강과 관련된 문서는 건강이라는 단어를 다수 포함할 수 밖에 없다. 하지만, 무조건적으로 출현 빈도에 의존하면 전체적인 정확도가 떨어진다. 어느 문서에나 빈번하게 등장하는 단어는 연관성 측정에서 제외해야 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 9 / 47
  • 10. TF-IDF Algorithm 내용 소개에 앞서, 앞으로 사용되는 공통되는 표현을 먼저 소개한다. 표기 의미 t 임의의 단어 (일반적으로 문서 내부에서 단어를 추출) D 임의의 문서 집합 n t,d 단어 t 가 문서 d 에 나타나는 횟수 |D| 해당 문서 집합에 포함된 문서의 수 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 10 / 47
  • 11. TF-IDF Algorithm Term Frequency는 문서에서 빈도가 높으면 높을 수록 큰 값을 가져야 하므로 아래와 같이 써볼 수 있다. t f t,d = n t,d Inverse Document Frequency는 문서 집합에서 단어의 빈도가 낮을 수록 커져야 하므로 아래와 같이 쓸 수 있다. id f t,d = 1 |{d : t ∈ d ∈ D}| + 1 위의 계산을 통해 TF와 IDF를 구했다면, 우리는 특정 단어 t 와 특정 문서 집합 D, 그리고 집합에 속한 문서 d 에 대해서 TF-IDF 가중치를 다음 식으로 구할 수 있다. t f id f t,d,D = t f t,d · id f t,d (t ∈ d ∈ D) 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 11 / 47
  • 12. Enhanced TF-IDF 앞서 알아본 TF-IDF 알고리즘는 몇 가지 부족한 점이 있다. 1 길이가 긴 문서는 빈도 수가 클 확률이 높고, 길이가 짧은 문서는 빈도 수가 작을 확률이 높다. 자연히 위의 경우에는 길이가 짧은 문서가 TF값이 높아 위에 나올 확률이 높아진다. 2 단어 1000개로 이루어진 문서 안에서 1번 나온 단어 A에 비해 2번 나온 단어 B는 연관도가 두 배라고 할 수 있을까? 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 12 / 47
  • 13. Enhanced TF-IDF 이와 같은 문제들을 해결하기 위해 TF-IDF 알고리즘에 로그 함수를 도입하였다.  t f t,d =  1 + ln(n t,d ) if n t,d > 0  0 if n t,d = 0 id f t,d = ln( 박치완 (SW Maestro) |D| |{d : t ∈ d ∈ D}| + 1 Hadoop 기반 문서 검색 ) September 17, 2012 13 / 47
  • 14. Example 임의의 단어 t 를 ‘health’로 지정하고 아래 예제를 계산해 보자. id f t,d = ln( 4 ) = 0.6931 2 문서 d1 문서 내용 ni,d Health is a necessary condi- n t,d t f t,d t f id f 7 1 0.134 0.093 11 0 0 0 tion for happiness. d2 It is the business of the police to protect the community. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 14 / 47
  • 15. Example 이어서 문서 문서 내용 d3 ni,d The city health business de- n t,d t f t,d t f id f 15 2 0.13 0.087 7 0 0 0 partment runs several free clinics for health professionals throughout the year. d4 That plane crash was a terrible business. 따라서, 사용자가 ‘health’를 질의어로 선택하였을 경우 TF-IDF 계산값이 높은 순서(d1 , d3 )대로 보여주게 될 것이다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 15 / 47
  • 16. Section 4 검색 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 16 / 47
  • 17. Vector Space Model 문서와 단어 사이의 관계를 표현하기 위해 벡터를 사용한다. 문서 또는 질의어가 Vector가 되고, Vector의 각 차원(Dimension)이 각 단어별 가중치를 갖는 값으로 표현된다. 일반식을 통해 특정 문서 d 를 VSM으로 표현하면 다음과 같다. Vd = [w1,d , w2,d , . . . , w N ,d ] T 이 때, 각 단어와 문서 사이의 연관성 가중치 w t,d 는 아래의 식으로 구할 수 있다. w t,d = t f id f t,d,D = t f t,d · id f t,d 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 17 / 47
  • 18. Cosine Similarity q는 사용자가 입는 각각의 문서 벡터이다. 이 T d1 q 0       α  X $d   $ 2 $$$ $$$  θ $ $   E 벡터간의 사이각에 대한 정보를 cos과 벡터 내적의 관계에서 구할 수 있다. cosα = d1 · q |d1 ||q| 두 벡터가 유사하고 연관성이 있으면 있을수록 두 벡터의 사이각은 작아지게 되고, 우리는 연관성을 나타내는 척도로 Figure : 문서와 질의어를 Cosine Similarity를 사용할 수 있다. 벡터로 표현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 18 / 47
  • 19. 문서 검색 알고리즘 위의 내용들을 종합하여, 문서 검색 알고리즘을 기술하면 아래와 같다. 1 입력된 질의어를 문서 색인 과정과 동일한 과정을 거쳐 벡터로 표현한다. 2 미리 색인된 데이터베이스에서 질의어를 포함한 문서 목록을 불러온다. 3 각각의 문서에 대해 질의어 벡터와의 Cosine Similarity를 계산한다. 4 계산된 Similarity에 따라 정렬하여 상위 문서들을 출력한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 19 / 47
  • 20. Section 5 구현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 20 / 47
  • 21. Subsection 1 TF-IDF(색인)의 구현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 21 / 47
  • 22. Flow Diagram 규칙 MapReduce Flow를 설명하기 전에, Flow Diagram에서 사용하는 기호들을 소개한다. - HDFS가 아닌 다른 데이터 소스에서의 데이터 입출력을 의미한다. - HDFS에서의 TextFile 입출력을 의미한다. - 시스템 내부에서의 데이터 입출력을 의미한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 22 / 47
  • 23. TF-IDF 색인 과정 Data Flow Diagram Flow A Term Document Index Flow B Document Term Index MySQL Flow C Calculate TF Document MySQL MySQL Flow D Calculate DF MySQL 크게 두 가지 작업으로 분류할 수 있다. 가중치 계산의 속도를 높이기 위해 TD, DT 색인과정을 거치는 작업 실제 가중치 계산에 필요한 TF, DF를 계산하는 작업 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 23 / 47
  • 24. Flow A. Term-Document Index MapReduce Job Mapper Reducer Document Noun Extracter ID: 13, 삼성과 애플의 잇단 소송 전쟁이 계속되 고 있다. [삼성,애플,소송,전 쟁,계속] Document Noun Extracter ID: 14, 애플이 최근 OS X 마운틴 라이언을 출시했 다. [애플,OS,X,마운 틴,라이언,출시] Term Document Indexer MySQL (TD Index) 삼성, 13 애플, 13 애플, 14 마운틴, 14 …… 삼성, [13] 애플, [13, 14] 마운틴, [14] …… 특정 단어가 포함된 문서들의 인덱스를 생성하는 작업 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 24 / 47
  • 25. Flow B. Document-Term Index MapReduce Job Mapper Document Noun Extracter ID: 13, 삼성과 애플의 잇단 소송 전쟁이 계속되 고 있다. [삼성,애플,소송,전 쟁,계속] Document Noun Extracter ID: 14, 애플이 최근 OS X 마운틴 라이언을 출시했 다. Document Term Indexer MySQL (DT Index) 13, [삼성,……,계속] 14,[애플,……출시] [애플,OS,X,마운 틴,라이언,출시] 특정 문서에 포함된 단어들의 인덱스를 생성하는 작업 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 25 / 47
  • 26. Flow C. Term Frequency MapReduce Job Mapper Combiner Document Noun Extracter ID: 15, 애플이 앱스토어 에 이어 맥 앱스토어를 개 시하였다. [애플, 앱스토어, 맥, 앱스토어, 개시] Document Noun Extracter ID: 27, OmmiGraffle 은 맥 앱스토어에서 99달 러에 판매되고있다. Term Frequency Counter MySQL (TF) 애플@15, 1 앱스토어@15, 2 달러@27, 1 …… [OmmiGraffle, 맥, 앱스토어, 99, 달러, 판매] 특정 문서에 포함된 특정 단어에 대해 빈도 수를 계산하는 작업 추후 다양한 활용을 위해 일단 WordCount만 수행한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 26 / 47
  • 27. Flow D. Document Frequency SQL Query MySQL (TD Index) Document Frequency Counter MySQL (DF) 삼성, [13] 애플, [13, 14] 마운틴, [14] …… 삼성, 1 애플, 2 마운틴, 1 …… IDF를 계산하기 위해 선행되어야 하는 DF 계산하는 작업 추후 다양한 활용을 위해 일단 DocumentCount만 수행한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 27 / 47
  • 28. Subsection 2 검색의 구현 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 28 / 47
  • 29. 검색 과정 Data Flow Diagram Query (User Input) Flow A Vectorize Flow B List Preload Flow C Scoring MySQL (Temporary) MySQL Flow D Sorting and Paging Search Result 사용자로부터 입력된 질의어(Query)로 검색을 수행하는 과정 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 29 / 47
  • 30. Flow A. Vectorize Query (User Input) Noun Extracter 애플의 신형 맥북 Term Frequency Counter [애플, 신형, 맥북] Next Flow 애플, 1, 신형, 1, 맥북, 1 사용자가 입력한 질의어를 VSM에 표현할 벡터로 변환하는 과정 여러가지 활용을 위해 오로지 Term Frequency 벡터로만 변환한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 30 / 47
  • 31. Flow B. List Preload Query Vector Merge document list contain terms in query vector Load Document Vector Information MySQL 질의어 벡터에 속한 단어들을 포함하고 있는 문서 리스트를 불러와 합친다. 전체 목록을 합칠 경우, 고려해야하는 문서양이 많아지므로 해당 단어의 TF가 높은 순으로 정렬하여 300개 미만으로 가져오도록 한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 31 / 47
  • 32. Flow C. Scoring Loaded Document Vector Query Vector Scoring TF-IDF 애플, 1, 신형, 1, 맥북, 1 Load Document Frequency MySQL 애플, 0.34, 신형, 0.002, 맥북, 0.65 13, 0.00028, 23, 0.0029, 17, 0.0013 …. 질의어 벡터와 미리 불러온 비교 문서 목록의 연관성을 앞서 사용했던 Cosine-Similarity 방법을 통해 계산한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 32 / 47
  • 33. Flow D. Sorting and Paging Presorted TF-IDF Scores Sorting 13, 0.00028, 23, 0.0029, 17, 0.0013 …. Sorted Data 23, 0.0029, 17, 0.0013, 13, 0.00028, …. 계산된 결과를 정렬하여 출력한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 33 / 47
  • 34. Section 6 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 34 / 47
  • 35. 테스트 환경 소개 SKT T cloud biz 서버 4대 서버 1대의 사양: 1 Vcore, 2GB RAM, 40GB HDD, CentOS 5.5 64bit Sun Java 1.6.0_35 Apache Hadoop 1.0.3 서버 IP Hadoop1: 1.234.45.90 (Namenode, Secondary Namenode) Hadoop2: 1.234.45.94 (Datanode) Hadoop3: 1.234.62.102 (Datanode) Hadoop4: 1.234.62.101 (Datanode) 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 35 / 47
  • 36. 색인 과정 테스트 색인 과정은 Hadoop1 (1.234.45.90) 서버에 ssh로 접속해 이루어진다. 색인, 검색 과정에 사용할 데이터는 HDFS에서 /chiwanpark/memento-input에 올려져 있어야 한다. hadoop jar memento-engine-0.1-SNAPSHOT.jar com.chiwanpark.memento.mapreduce.WorkRunner 입력 파일 갯수에 따라 시간이 소요된다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 36 / 47
  • 37. 색인 과정 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 37 / 47
  • 38. 검색 과정 테스트 검색 과정 역시 Hadoop1 서버에 ssh로 접속해 테스트한다. java -classpath memento-engine-0.1-SNAPSHOT.jar:/opt/hadoop/conf com.chiwanpark.memento.searcher.cli.SearchRunner –query 스마트폰 명령을 수행하면 그 결과로 문서 id와 TF-IDF Score를 보여준다. 문서 ID를 통해 HDFS에서 해당 문서를 열람할 수 있다. hadoop fs -cat /chiwanpark/memento-input /e02f5b1df830e8fcf89df333dc2dd642a9f0569ee6aea26cc1e3ec3a22e4 b988bfadb397c1ba7bd593feb5bd99276b9ce15a84741b5fe583d1dc2cb9 110ae70c.txt 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 38 / 47
  • 39. 검색 과정 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 39 / 47
  • 40. 검색 과정 테스트 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 40 / 47
  • 41. Section 7 토의 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 41 / 47
  • 42. Subsection 1 성능 측정과 품질 검증 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 42 / 47
  • 43. 성능과 품질 검증 방법 성능 측정은 전체 MapReduce의 수행 시간을 구하고, 해당 시간 동안 처리한 파일의 수를 구해 성능 측정의 기준으로 삼는다. 품질 검증은 이번 TF-IDF 시스템 구현이 Lucene의 시스템과 유사한 부분이 많이 Lucene에 해당 도큐먼트 집합을 넣었을 때의 Score와 구현한 시스템이 계산한 TF-IDF Score를 비교하는 방법을 생각해 볼 수 있다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 43 / 47
  • 44. 성능 측정 결과 Test1 Job1 - 102개 문서/3분 58초 (참고 자료 열기) Job2 - 102개 문서/3분 43초 (참고 자료 열기) 초당 0.22개 문서 처리 Test2 Job1 - 99개 문서/3분 54초 (참고 자료 열기) Job2 - 99개 문서/4분 4초 (참고 자료 열기) 초당 0.21개 문서 처리 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 44 / 47
  • 45. 성능 측정 결과 Test3 Job1 230개 문서/8분 44초 (참고 자료 열기) Job2 230개 문서/8분 16초 (참고 자료 열기) 초당 0.22개 문서 처리 Test4 Job1 1862개 문서/1시간 3분 55초 (참고 자료 열기) Job2 1862개 문서/1시간 4분 27초 (참고 자료 열기) 초당 0.24개 문서 처리 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 45 / 47
  • 46. Subsection 2 개선 사항 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 46 / 47
  • 47. 품질 개선 사항 이번 프로젝트에서 사용한 한나눔 형태소 분석기의 분석 품질이 좋지 않아, 오히려 공백을 기준으로 단어를 분리하고 그 결과에서 조사를 직접 제거한 후, 미리 준비한 단어 사전과 매칭하여 키워드를 추출하는 방법이 더 좋은 품질을 가져올 수 있다고 생각한다. 버즈니 형태소 분석기의 경우 분석 품질은 우수하나 많은 양의 자료를 처리할 수 없어 사용하지 않았다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 47 / 47
  • 48. 성능 개선 사항 데이터 저장 구조가 현재는 하나의 문서를 하나의 파일로 구현하였는데, 로그 분석 결과 Hadoop에서 File Split마다 Mapper 클래스를 초기화하기에 이 때 초기화 시간으로 많은 시간을 소요하였다. 따라서 이를 개선하여, 하나의 문서를 Single line으로 표현하고 수십개의 문서를 묶어서 Split 단위를 늘려 초기화 횟수를 감소시킴으로써 성능 향상을 꾀할 수 있다. 테스트 시스템에서는 Cloud System 4대를 사용하였는데, 이는 VM으로 이루어져 I/O 성능이 별로 좋지 않다. VM이 아닌 실제 시스템에서 돌리면 보다 나은 성능을 보여줄 것으로 기대한다. 박치완 (SW Maestro) Hadoop 기반 문서 검색 September 17, 2012 48 / 47