A Novel Cluster Matching Algorithm Based on Support Vector Machine Indoor Localization System

為了建立一個可以在真實環境下運作的室內定位系統，我們採用了從無線接取器接收到的訊號強度及採用指紋辨識位置方法來建構我們的系統。在指紋辨識定位方法中，我們可以分成兩個步驟，離線階段以及線上階段。離線階段通常又可以被稱作訓練階段，在這個階段，我們會收集所有參考點上的無線網路訊號強度，並以此建立資料庫與訓練機器學習模型。線上階段通常又可以被稱為測試階段，在這個階段，我們會收集新的無線網路訊號強度當作測試資料，並且使用訓練完的模型去預測測試資料的位置。不過每次一收集新的測試資料，就要和所有資料庫中的資料進行比對會造成運算複雜度過高，為了解決這個問題，我們使用了非監督是學習的分群演算法，將所有參考點依照之間的相似度分成不同的集合。這樣做的好處是，當我們收集新的測試資料時，我們先做群集匹配決定此測試資料屬於哪一個群集，再使用這個群集裡的參考點來作為預測位置的依據。如此一來，便可大幅度的降低運算複雜度。另外，由於在真實的環境中，無線網路訊號強度的模式是時變且隨機的，使用傳統的監督式學習來進行群集匹配效果明顯不好。為此，我提出了一個新穎的群集匹配演算法─與質心之間餘量的群集匹配，並依此演算法建構了一個可以使用於真實環境中的室內定位系統。此演算法的精隨在於使用支持向量機求取測試資料與群集質心間的餘量，進而得到相似度，依此決定此測試資料屬於哪一個群集。實驗的結果顯示出我建構的室內定位系統可以在真實環境中達到2.6公尺的平均誤差。相較於先前直接使用核心支持向量機來做群集匹配，我們在平均定位誤差改善了80.711個百分比。To build a real-environment indoor localization system, we use the received signal strength (RSS) of Wi-Fi being the features and the fingerprinting method to construct the system. There are two stages of fingerprinting method: offline stage and online stage. The offline stage is so-called training stage which means that we construct the database from all reference points (RPs) and extract the features of RSS to train the model. The online stage is so-called testing stage which means that we collect the new data and use the trained model to predict the location. Due to the high computation complexity of the location predicting, we use the clustering algorithms to divide all the RPs into different groups. When we collect the new data and try to estimate the location, we can use cluster matching algorithm to decide which cluster it belongs to first. And then we can use the members of the cluster to do localization by the kernel-based weighting sum method. Because of the time-variant and uncertainty property of received signal strength, the traditional cluster matching algorithm using machine learning model to fit the training data and doing prediction is useless in the real environment. I propose a novel cluster matching algorithm called Margin with Centroids Cluster Matching (MCCM) to build a real-environment indoor localization system. The idea of MCCM is using the similarity which is obtained by kernel SVM margins between the cluster centroids and the test data and choosing the most similar centroid to be the cluster which the test data belongs to. Experiment results demonstrate that the proposed indoor localization system achieves 2.60 meters as mean error in the real environment. As compared to the kernel SVM, the proposed method reduces the mean localization error by 80.711%