Fast Pattern Classification through Nearest-Neighbor Search

[[abstract]]近年來，支援向量機 (Support Vector Machines，SVMs) 在樣式識別與數據挖掘的領域中已被廣泛用於解決各式各樣的分類問題。支援向量機的基本原則在於根據所有訓練樣本的類別標籤找出最佳的超平面，並利用此一超平面預測測試樣本的類別標籤。顯而易見地，基於此一原則所必須付出的計算成本限制了支援向量機對於大規模資料集的訓練能力。為了克服此一缺點，最為直觀的處理方式便是減少與建構最佳超平面無關之訓練樣本的數量。本文中，我們提出一種以最近鄰居搜尋為基礎的有效方法，進而識別出與建構最佳超平面相關的訓練樣本，使得這些樣本在被移除之後不致於影響支援向量機的分類準確性。例如：IRIS、Monks 與 Forest 為本文所提出的方法進行效能評估。我們利用一些公開的資料集實驗結果顯示，本文所提出之方法在訓練樣本所減少的數量、支援向量機所耗用的訓練時間以及分類準確性等方面有非常優異的表現。[[abstract]]Over recent years, support vector machines (SVMs) have been widely used for solving a variety of classification problems in the fields of pattern recognition and data mining applications. One basic principle behind SVMs is to predict the class label of a testing sample by using the optimal hyperplane determined from labeled training samples. Obviously, this principle brings SVMs a limitation that they are computationally infeasible for training a very large-scale dataset. To overcome this drawback, an intuitive approach is to reduce the number of training samples that are unrelated to the construction of the optimal hyperplane. In this thesis, an efficient approach based on nearest neighbor search is therefore proposed to identify non-relevant samples that can subsequently be removed from a large-scale training dataset without degrading the classification accuracy. The performance of the proposed approach is assessed through the use of several publicly available datasets such as IRIS, Monks, and Forest. Experimental results demonstrate that the proposed approach is a significant improvement compared with the previous attempts in terms of the reduced number of training samples, the time taken for SVM training procedures, and the classification accuracy