효율적인 kNN 알고리즘
An Efficient kNN Algorithm
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
본 논문은 문서분류 방법인 kNN의 실행속도를 개선하는 알고리즘을 제안한다. 제안된 알고리즘은 기존의 kNN이 사용하는 <용어, 가중치> 쌍의 목록 대신, <문서, 가중치> 쌍의 목록을 사용하여 유사성 계산을 빠르게 함으로써 실행속도를 개선하는 것이다. <문서, 가중치>의 목록은 문서분류의 학습단계에서 <용어, 가중치>의 목록을 행렬 전치함으로써 구한다. 본 논문에서는 제안된 알고리즘을 시간복잡도 측면에서 분석하고 기존의 kNN과 비교 하였으며, 로이터-21578 데이터를 사용하여 실험적으로 성능을 비교 하였다. 실험결과, 본 논문에서 제안한 알고리즘이 기존의 kNN보다 실행속도측면에서 약 90% 정도의 우수함을 알 수 있었다.
Abstract
This paper proposes an algorithm to enhance the execution time of kNN in the document classification. The proposed algorithm is to enhance the execution time by minimizing the computing cost of the similarity between two documents by using the list of <document, weight> pairs, while the conventional kNN uses the list of <term, weight> pairs. The list of <document, weight> pairs can be obtained by applying the matrix transposition to the list of <term, weight> pairs at the training phase of the document classification. This paper analyzed the proposed algorithm in the time complexity and compared it with the conventional kNN. And it compared the proposed algorithm with the conventional kNN by using reuters-21578 data experimentally. The experimental results show that the proposed algorithm outperforms kNN about 90% in terms of the execution time.
참고문헌 (13)
- "Expert Network" (1994)
- "Inductive learning algorithms and representations for text categorization" (1998)
- "A re-examination of text categorization methods"
- "Intelligent Document Classification", 4(5) (2000)
- "Classifying financial news with neural networks", pp.6~, In 6th Australian Document Symposium
- "Rocchio and Metrics for Information Filtering at TREC-10", pp.~10 (2001), In The 10th Text Retrieval Conference NIST
- "A Study on Thresholding Strategies for Text Categorization" (2001)
- "Machine learning in automated text categorization", 34(1), pp.1~47 (2002)
- "A Framework for Text Categorization"
- "텍스트 마이닝 기술을 적용한 대용량 온라인 문서 데이터의 계층적 조직화 기법" (2002)
- "Coping with the News" (2003), The 9th Australian World Wide Web Conference
- "휴리스틱을 이용한 kNN의 효율성 개선", 10-b(6) (2003)
- "C로 쓴 자료구조론", pp.68~88, 사이텍미디어