서지주요정보
Instance-level dimensionality reduction for efficient similarity search in large document databases = 대규모 문서 데이터베이스에서 효율적인 유사 검색을 위한 인스턴스-레벨 차원 감소 기법
서명 / 저자 Instance-level dimensionality reduction for efficient similarity search in large document databases = 대규모 문서 데이터베이스에서 효율적인 유사 검색을 위한 인스턴스-레벨 차원 감소 기법 / Min Soo Kim.
저자명 Kim, Min Soo ; 김민수
발행사항 [대전 : 한국과학기술원, 2015].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8028052

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 15004

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Dimensionality reduction is essential in text mining since the dimensionality of text documents could easily reach several tens of thousands, and it leads to performance degradation of mining results. Most recent efforts on dimensionality reduction, however, are not adequate to large document databases due to lack of scalability. We hence propose a new type of simple but effective dimensionality reduction technique, called {\em horizontal (dimensionality) reduction}, for large document databases. Horizontal reduction converts each text document to a few bitmaps and provides tight lower bounds of inter-document distances using those bitmaps. Bitmap representation is very simple and extremely fast to be extracted and to use, and its instance-based nature makes it suitable for large and frequently updated document databases. Using the proposed horizontal reduction, we develop an efficient $k$-nearest neighbor\,($k$-NN) search algorithm for text mining such as classification and clustering, and we formally prove its correctness. The proposed algorithm decreases I/O and CPU overheads simultaneously since horizontal reduction (1)\,reduces the number of accesses to documents significantly by exploiting the bitmap-based lower bounds in filtering dissimilar documents at an early stage, and accordingly, (2)\,decreases the number of CPU-intensive computations for obtaining an actual distance between high-dimensional document vectors. Extensive experimental results show that horizontal reduction improves the performance of the reduction (preprocessing) process by one to two orders of magnitude compared with existing reduction techniques, and our $k$-NN search algorithm significantly outperforms the $k$-NN search algorithms using the existing reduction techniques.

수 만에 이르는 텍스트 문서의 차원 크기는 텍스트 마이닝의 성능을 저하시키는 주된 원인이며, 따라서 텍스트 문서의 차원 감소는 텍스트 마이닝에서 매우 중요하다. 그러나, 차원 감소에 대한 최근까지의 연구들은 확장성이 부족하여 대규모 문서 데이터베이스에 적용하는 것이 어려웠다. 따라서, 본 학위 논문에서는 수평 차원 감소라고 불리는 대규모 문서 데이터베이스를 위한 간단하면서도 효과적인 새로운 차원 감소 기법을 제안한다. 수평 차원 감소는 각각의 텍스트 문서를 소수의 비트맵으로 변환하고, 이 비트맵을 이용하는 텍스트 문서 간 유사도의 엄격한 하한을 제공한다. 비트맵 표현은 매우 간단하고, 비트맵의 생성과 사용에 필요한 시간이 매우 짧으며, 수평 차원 감소의 인스턴스-기반 성질은 대규모의 그리고 업데이트가 빈번한 문서 데이터베이스에 적합하다. 또한, 본 학위 논문에서는 수평 차원 감소 기법을 이용하여 분류와 클러스터링 등의 텍스트 마이닝을 위한 효율적인 $k$-nearest neighbor ($k$-NN) 검색 알고리즘을 제안하고, 알고리즘의 정확성을 정형적으로 증명한다. 제안하는 알고리즘은 입출력과 CPU 오버헤드를 동시에 감소시키는데, 이유는 다음과 같다. 1) 수평 차원 감소를 사용하면 유사하지 않은 문서를 걸러내는 알고리즘의 초기 단계에서, 비트맵 기반의 유사도를 사용하여 유사 여부를 확인해야하는 실제 문서의 수를 줄인다. 따라서, 2) 자연스럽게 고차원 텍스트 문서 간의 실제 유사도를 계산하기 위한 CPU-집중적인 계산의 회수가 줄어든다. 본 학위 논문에서 제안한 수평 차원 감소 기법과 기존 차원 감소 방법들을 비교한 실험 결과, 수평 차원 감소는 차원 감소(전차리) 과정의 성능을 수십 $\sim$ 수백배 향상시켰다. 또한, 수평 차원 감소을 사용한 $k$-NN 검색 알고리즘의 성능은 기존의 차원 감소 기법을 사용한 검색 알고리즘의 성능을 크게 능가하였다.

서지기타정보

서지기타정보
청구기호 {DCS 15004
형태사항 iv, 43 : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 김민수
지도교수의 영문표기 : Kyu Young Whang
지도교수의 한글표기 : 황규영
Including Appendix
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 References : p.
주제 dimensionality reduction
text mining
차원 감소
텍스트 마이닝
QR CODE qr code