데이터마이닝 & 정보검색 연구실 신 현 일

 검색 시스템에 필요한 요소  인터넷 검색의 유형 / 태그란 ?  Blog 검색 시스템 설계  Target : Blog ? / 국내 Blog 사이트 분류  Collection : 어디서 무엇을 추출할 것인가 ?  Search Result : 무엇을 어떤 순서로 보여줄 것인가 ?  개발 환경  프로젝트 일정  Blog 검색 시스템 구현  Blog 검색 시스템 구조  웹로봇 + 인덱싱  색인어 ( 키워드 ) 추출  Ranking  사용자 질의 서버  검색결과를 가져오는 과정  성능 평가  Q&A

검색 시스템에 필요한 요소 무엇을 수집 ? - 구조해석 후 필요한 부분만 필터링 어디서 (Collection) 수집 ? Crawling 데이터를 저장하고 찾을 때의 효율성 고려 랭킹 정보의 인덱싱 자료구조, 알고리즘 Indexing 웹페이지의 보편적 가치 + 검색된 단어의 관련성 ( 복합적 평가 ) 중요한 페이지일수록 여러 곳에서 인용이 됨 : PageRank 단어 : 빈도수, 단어거리, 앵커 텍스트 Ranking Google 의 PageRank * 참고 : 구글을 지탱하는 기술 (2008, 니시다 케이스케 지음 )

인터넷 검색의 유형 홈페이지 찾기 디렉토리 검색 정보 찾기 키워드 검색 편집 검색 통합 검색 Tag 기반검색 주제어 검색 * 출처 : ‘09 Trend – 새로운 검색을 위한 시도들 ( 발표자료, 모란소프트 조영환 ) 주제어의 예 : 북한 위성 발사, 맛집 추천, 빅뱅 좋아 ( 특정 소재에 관한 이슈나 감성적 표현 )

네이버 시퀀스 : 영화, 자동차 등 특정 정보 에 관하여 세부적인 검색 옵션 ( 쇼핑 검색 과 유사 ) 을 주어 검색 할 수 있게 함 키워드 검색 + 세부 옵션 ( 제한된 주제 ) 네이트 시맨틱 VS 네이버 시퀀스 네이트 시맨틱 : 검색 결과를 검색어 와 관련된 주제어들로 다시 분류 키워드 검색 + 주제어 분류

태그 (Tag) 란 ?  메타데이터  글의 핵심어, 소재, 분류  주요 사례 : 블로그 태그, del.icio.us 북마킹  태깅 방법 : Social tagging, Auto tagging  트랜디한 정보에 대한 탐색이 쉬움  연관 태그를 통해 자유로운 이동 가능  주제어 검색의 기반이 될 수 있음 문서 전체집합에 대한 객관적 정보량 측정이 불가능 할 때, 주제어 단위의 정보량 측정은 효과적인 검색을 가능하게 함

Target : Blog ?  1 인 미디어  개인의 의견이나 경험을 최근 순서로 기록  개인적인 생각과 관심사 를 웹에 발행 하는 곳  댓글, 트랙백, 링크, 태그, RSS 등 다양한 기능  보통의 웹사이트에 비해 업데이트 주기가 빠른 편

Target : 국내 Blog 사이트 분류  포털형 블로그  네이버 블로그  이글루스 블로그  티스토리 블로그  다음 블로그  텍스트큐브  Etc..  설치형 블로그  텍스트큐브 ( 태터툴즈 )  워드프레스 (from 외국 )  Etc..

Blog VS Micro Blog ( 트위 터..)

Collection : 어디서 무엇을 추출할 것 인가 ?  웹 페이지 선정 - 블로그 페이지만 선별  1 차 판별 및 필터링 : URL 주소  2 차 판별 및 필터링 : 페이지 메타데이터  블로그 페이지 내용과 주소와의 특성 고려  첫 페이지  ( 날짜, 태그, 카테고리 별 ) 글 목록 페이지  무엇을 추출 하여 인덱싱 ?  페이지 정보  URL ( 절대적 주소 ), 글 제목, 날짜  랭킹 정보  글 내용에서 키워드 별 빈도수  글 제목, 앵커텍스트, 카테고리, 블로그 태그, 강조 구문 ( h1, h2, h3, b, strong 태그 등 )

Collection : 블로그 페이지 선별  URL 주소를 통해..  블로그 포털 사이트가 도메인인 경우      주소에서 알 수 없는 경우 – 메타데이터 이용  메타데이터 – 웹 페이지 소스   태그 안의 링크 경로 중에 /blog/ 가 존재

Collection : 추출할 데이터  검색 결과에 보여줄 페이지 정보  페이지 제목, 날짜, 내용 미리 보기  검색 결과 랭킹 계산에 사용할 정보 ( 종류별로 다르게 가중치를 주어서 계산 )  키워드 별 랭킹  필수 : 제목에 언급된 키워드  필수 : 본문에 나온 키워드 별 빈도수  옵션 : 본문에 나온 키워드 중 강조된 부분들  옵션 : 앵커텍스트, 블로그 태그, 카테고리  페이지 별 랭킹 (PageRank 의 제한적 적용 )  본문에서의 링크와 해당 글의 트랙백 링크

Collection : Blog Page Patterns  글의 본문 시작 부분  |   |  글 생성 날짜 ( 글 본문 태그 중에..)  class="updated“ | class=“date“ | class="infoDate"  글이 속한 카테고리 ( 글 본문 태그 중에..)  rel="category“ | rel=“ctg” | rel="category tag“  글의 블로그 태그  글 본문의 a 태그 중에 rel=“tag”

개발 환경 Python MySQL Apache 2.0 Python (CGI) + HTML AMD 3700+, RAM 2G, Windows 7 Beta 32bit 공개 소스 (JAVA) Programming Language Indexing & DBMS Web Server Web Site PC Environment 한글 형태소 분석

프로젝트 일정표 3/314/64/104/124/145/126/2 로봇 구현 랭킹 TEST 질의서버 DB 축적 총 TEST 데모 시연 개선 / 확장 최종 발표

Blog 검색 시스템 구조 웹로봇 블로그 페이지 판단 페이지 분석 필요한 데이터 추출 웹 탐색용 URL 수집 페이지 중복 여부 확인 인덱스 페이지 정보 저장 키워드 태깅 키워드 별 랭킹 스코어 저장 질의 서버 사용자의 검색 명령 수행 검색어로 사용된 키워드 를 분석 필요한 정보를 인덱스에 서 중요도 순으로 가져옴 결과를 보기 쉽게 편집

Start URL 데이터베이스 HTML 분석 URL 목록 input output 인덱스 되 어 있는지, 블로그 페 이지 판단 find 속성별 ( 제목, 날짜, 태그, 카테고리, 본 문 강조, 앵커 텍스 트 ) 데이터 수집 각각 형태소 분석 no 키워드, 키워드 수 HTML 분석 + URL, 제목, 날짜, 본문 일 부 저장 URL ID, 키워 드, Score 저장 yes 키워드 별 Score = Sum( 속성별 키워 드 빈도수 X 속성별 계수 ) Ranking Crawling Inverted Indexing Indexing

색인어 ( 키워드 ) 추출  검색어에 쓰일만한 키워드들을 문자열에서 추출해야 함  자동 색인어 추출 방법 = 형태소 분석기 + 색인어 조합  색인어 조합 : 형태소 단어 좌우에 조합을 더하여 형태소의 여러 쓰임에 대비한 키워드 생성 ( 예 : 확장 -> 확장, 확장성 )  방법  1. 색인어 사전 구축 :  검색어로 사용될 단어들을 미리 정해 놓는 방법  직접 만들기엔 너무 광범위  주기적으로 새로운 단어를 추가해야  2. Bi-gram : 2 글자씩 겹쳐서 키워드를 추출  예 : 정보검색이란 : 정보, 보검, 검색, 색이, 이란  구현이 쉽지만 검색 품질이 심각하게 저하됨  3. 형태소 분석기를 통해 명사만 추출하여 색인어 조합  3 번 방법으로 구현 결정 ( 블로그 태그도 주로 명사 위주이므로 ) = 락끄님의 한글 형태소 분석기 실행 결과 = Input : 나는 무엇을 먹고 사는 사람이더냐 나는 { 나 /VV/S+ 는 /EM/S/FM/DT}; { 날 /VV/S+ 는 /EM/S/FM/DT}; { 나 /NP/S+ 는 /JO/S/CL/SB}; 무엇을 { 무엇 /NN/S+ 을 /JO/S/CL/OB}; { 무엇 /NP/S+ 을 /JO/S/CL/OB}; 먹고 { 먹 /VV/S+ 고 /EM/S/CN/EQ}; { 먹 /VV/S+ 고 /EM/S/CN/SU}; 사는 { 사 /VV/S+ 는 /EM/S/FM/DT}; { 살 /VV/S+ 는 /EM/S/FM/DT}; { 사 /VV/S+ 아 /EM/S/CN/SU+ 는 /JO/S/SU}; { 사 /VV/S+ 아 /EM/S/ED/NM+ 는 /JO/S/SU}; 사람이더냐 { 사람 /NN/S+ 이 /CP/S+ 더 /EP/S/TM+ 냐 /EM/S/ED/QT};

Ranking  페이지 ( 블로그 글 ) 의 키워드 별 중요도를 미리 계산하여 인덱싱  본문 전체의 단어 별 빈도수 계산과 자동 태깅 ( 중요한 단어들만 추출 ) 병행  중요 단어들을 추출할 위치  제목, 카테고리, 본문 강조  특정 접속부사 ( 따라서 / 결국 / 끝으로 / 결론은 / 마침내 등등 )  특정 단어 및 기호 뒤에 위치한 구절  블로그 태그  다른 페이지의 앵커 텍스트  본문 전체에 나온 키워드들에 대한 빈도수 계산  최종 목적 : 주제어와 가장 관련이 높은 블로그 글을 계산 -> 하루의 Hot Page 가 아니고 주제어 마다의 Hot POST 를 랭킹에 반영

사용자 질의 서버  검색 결과에 페이지 제목, 날짜, 본문 일부 ( 미리보기 ), 연관 태그, 카테고리 출력  결과 리스트의 순서 = 키워드 별 랭킹 + 페이지 랭킹 스코어  Boolean 검색 지원  기본은 And 검색, 최대 3 단어  단어는 space 로 구분  검색어와 유사한 키워드에 대한 검색

검색결과를 가져오는 과정 wordlist Table 키워드 : 키워드 ID 검색어 입력 키워드로 변환 wordlocation order by score 키워드 ID : urlID, score …. urllist Table urlID : 제목, 날짜, 카테고리, 글일부, PageRank score + PageRank 내림차순 으로 결과 표시

성능 평가  검색 속도 측정  코드에 추가, 타 시스템과의 속도 비교  1 초대의 속도를 기대할 수 있어야 함  검색 정확도 (relevance) 측정 - 타 시스템과 비교  정확률 (precision) = 검색결과 중 적합한 결과 수 검색 결과 수  재현율 (recall) = 검색결과 중 적합한 결과 수 적합한 결과 수 검색결과에 포함된 것 중에 제대로 나온 것의 비율 모두 나와야 하는 것 중에 검색 결과에 포함된 것의 비율 정확률은 찾는 페이지가 명확할 때, 정확한 해답을 찾고자 할 때 중요 하며 재현율은 거의 모든 데이터에서 찾아봐야 하는 철저한 검색에서 중요함

참고 문헌 / 서적 / 사이트  논문 : 조사 유형 및 복합명사 인식에 의한 용어 가중치 부여 기법 ( 한국정보과학회 지 논문, 강승식 외 )  책 : 집단 지성 프로그래밍 ( 토비 세가란 저 )  책 : 열혈강의 파이썬 Ver.2 ( 이강성 저 )  책 : 구글을 지탱하는 기술 ( 니시다 케이스케 저 )  태깅 (Tagging) 의 존재 이유 (ibm.com 기고문, 김홍기 )  검색엔진과 통합검색 그리고 블로그 검색 ( 블로그 글, 모란소프트 조영환 )  ‘09 Trend – 새로운 검색을 위한 시도들 ( 발표자료, 모란소프트 조영환 )  검색엔진 개발자 그룹 :  강승식 교수님의 한글 형태소 분석기 공개 소스 (C, ASP):  락끄님의 한글 형태소 분석기 공개 소스 (JAVA):