【正文】 問題， 能夠有效地處理大量的輸入變量；第二， 訓(xùn)練和預(yù)測速度快； 第三，隨機(jī)森林有良好的抗噪聲能力，并且不像決策樹一樣容易遇到過度擬合問題；第四，對(duì)數(shù)據(jù)集的適應(yīng)能力強(qiáng)，且無需進(jìn)行規(guī)范化處理。 第五， 能夠 檢測出特征的重要性程度以及 各個(gè)特征 之間的相互影響 。 第二章 當(dāng)前研究基礎(chǔ)綜述 11 隨機(jī)森林 用于模型構(gòu)建 如圖 22 所示， 由 n 棵決策樹構(gòu)成 一個(gè)隨機(jī)森林 ， 其中的 每棵決策樹 都 是一個(gè)分類器 （如決策樹 1 2 3 nTTT...T ） 。 隨機(jī)森林 算法描述如下 [19]： 1） 隨機(jī)森林的 輸入 ： 隨機(jī)森林 輸入的數(shù)據(jù)集 X 是由 N 個(gè)樣本構(gòu)成的，其中每個(gè)樣本包含 K 個(gè)表征樣本特性的特征屬性和一個(gè)表示該樣本的實(shí)際類別的類別屬性。 2） 訓(xùn)練樣本集合的選擇：使用 Bagging 方法進(jìn)行隨機(jī) 抽取 ， 在一次抽樣中，對(duì)原始輸入數(shù)據(jù)集 X 有放回的重復(fù)抽取 N 次，就可以得到一個(gè)由 N 個(gè)樣本組成的新 輸入 數(shù)據(jù)集 X’。 3） 分裂屬性集的選擇：仍然采用隨機(jī) 抽取 的辦法， 對(duì)于每棵決策樹， 從 K個(gè)特征屬性中隨機(jī)抽取 k 個(gè)屬性作為分裂屬性（ k 小于等于 K）并基于它們 構(gòu)建最優(yōu)的不剪枝決策樹。 4） 重復(fù) 2 至 3 步驟 n1 次 ， 得到 一片 由 n 棵決策樹構(gòu)成的 森林， 隨機(jī)森林分類的結(jié)果就是對(duì) n 棵決策樹的決策結(jié)果進(jìn)行匯總排序 并 取最靠前的結(jié)果。 T r e e T 1T r e e T 2T r e e T n. . .決 策 圖 22 隨機(jī)森林的示意圖 [19] 隨機(jī)森林用于特征選擇 隨機(jī)森林算法 不僅可以用于模型構(gòu)建，還可以用于特征選擇，它能夠分析出每一個(gè)特征變量的重要性（ VI）。這樣，根據(jù)特征變量的重要性進(jìn)行排序，從所有特征 中 選出重要性靠前的特征可以達(dá)到模型簡化的目的 。 通過 隨機(jī)森林 可以計(jì)算出 兩類 基本 的 VI 值 [20]，分別是 Gini importance 和 Permutation importance。 （ 1） Gini importance 的計(jì)算 首先，在計(jì)算 Gini importance 之前需要明確一個(gè)概念即為基尼 系數(shù) （ Gini系數(shù)），基尼系數(shù)被用于評(píng)價(jià)決策樹的節(jié)點(diǎn)分裂過程中的每一個(gè)節(jié)點(diǎn)的樣本純度。它的表達(dá)式如下： 北京郵電大學(xué)工學(xué)碩士學(xué)位論文 12 21 ( )??? ji p j （ 22） 其中， ()pj 表示 屬于類別 j 的樣本 數(shù)量與總樣本數(shù)量的百分比。因此，為了實(shí)現(xiàn)子節(jié)點(diǎn)樣本純度高于父親節(jié)點(diǎn)，我們需要對(duì)分裂屬性進(jìn)行一定的篩選 ，從而達(dá)到減小樣本不純度的目的，不純度降低量記為： (? ? )? ? ? ?pare nt le ft le ft ri ght ri ghti i p i p i （ 23） 其中 ， parenti 、 lefti 和 righti 分別代表了父親節(jié)點(diǎn)、左 子節(jié)點(diǎn) 和右子節(jié)點(diǎn) 的 基尼系數(shù)， leftp 對(duì)應(yīng)于左子節(jié)點(diǎn)的占比， rightp 對(duì)應(yīng)于右子節(jié)點(diǎn)的占比。最后是 Gini importance 的計(jì)算，對(duì)于任意的特征 變量 iX ，取出隨機(jī)森林中所有已經(jīng)選擇 iX 作為分裂屬性的節(jié)點(diǎn)， 統(tǒng)計(jì) 它們的不純度降低量總和 即可 ： ? ? ??kkIi????? ? ? ? ? ? ??（ ???） （ 2） Permutation importance 的計(jì)算 a） 對(duì)于隨機(jī)森林 F 中的每一棵決策樹 T， OOB 樣本 被用于 計(jì)算預(yù)測準(zhǔn)確率 tA ， 假設(shè)使 用 rN 表示 OOB 樣本 中 分類 正確的樣本 個(gè)數(shù) ， 則 計(jì)算公式如下： ? rT NA N ?????? ? ? ? ? ? ? ????（ ???） ?b） 隨機(jī)地對(duì) OOB 樣本 中 的 所有特征加入諸如隨機(jī)改變樣本在某特征處的值等噪聲干擾，假設(shè)使用 rN39。 表示 OOB 樣本被正確分類的個(gè)數(shù) ，此時(shí)的準(zhǔn)確率為： 39。* ? rT NA N ??? ? ? ? ? ? ? ? （ ???） ?c） 預(yù)測準(zhǔn)確率的 改變 量 值 除以決策樹的數(shù)量 n，可以 計(jì)算出 該特征變量 iX 的Permutation importance： *1 ???? TTTFd A An ??? ? ? ? ? ? （ ???） ?對(duì)上述說明進(jìn)行總結(jié)歸納即為 當(dāng)給某個(gè)特征變量加入噪聲干擾后，若預(yù)測準(zhǔn)確率大幅度降低，則說明這個(gè)特征對(duì)于樣本的分類結(jié)果影響很大，即其重要程度較高，基于此 ， 就可以使用 Permutation importance 來評(píng)價(jià)特征變量的重要性。 第二章 當(dāng)前研究基礎(chǔ)綜述 13 定位技術(shù) 的研究 首先， 由于 本文 的交通模式識(shí)別 結(jié)合用戶實(shí)時(shí)軌跡和交通站點(diǎn)位置進(jìn)行公共交通擬合度的計(jì)算；其次，本文的交通模式識(shí)別系統(tǒng)可 應(yīng)用于基于位置的服務(wù)領(lǐng)域。因此， 準(zhǔn)確 獲取用戶位置 成為 本研究的 關(guān)鍵之一 。本文的重點(diǎn)關(guān)注基于智能手機(jī)的定位技術(shù)， 目前 基于手機(jī)的定位技術(shù)主要包括四類 [21]，分別是 基站定位、WiFi 定位、 GPS 定位和 AGPS 定位，這四類技術(shù)分別適用于不同網(wǎng)絡(luò) 環(huán)境。 基站定位技術(shù) 基站定位技術(shù)利用基站的位置以及基站與手機(jī)之間的推算距離來分析手機(jī)的位置 [22]，是不精確的定位技術(shù)因?yàn)槠涠ㄎ粶?zhǔn)確率很大程度依賴于基站的分布和 覆蓋范圍的大小 ，誤差較大。 基于手機(jī)的基站定位主要有以下三種方式：根據(jù)信 號(hào)到達(dá)時(shí)間定位、根據(jù)信號(hào)強(qiáng)度（場強(qiáng)）定位、根據(jù)入射角定位。 到達(dá)時(shí)間 (Time of Arrival， TOA)方法是一種基于信號(hào)到達(dá)時(shí)間的來推算用戶位置的定位方法， 具有定位精度高、抗干擾能力強(qiáng)、速度快的特點(diǎn)，因此，本文使用該方法來進(jìn)行基站定位 。方法的示意圖如下： M S （ x , y ）B S 3 （ x , y ）B S 2 （ x , y ）B S 1 （ x , y ）R 1R 2R 3 圖 31 基站定位的 TOA方法示意圖 [22] TOA 算法需要使用到三個(gè)基站的信息，假設(shè)用戶的坐標(biāo)為 x（ ,y） ，基站的坐標(biāo)為 iix（ ,y） ，手機(jī)到基站的信息傳輸時(shí)間為 it ， i 取值為 1 到 3，利用 TOA 算法，可以得到如下方程組： 21 1 122 2 223 3 3x x + y y ( )x x + y y ( )x x + y y ( )22（ ） （ ）（ ） （ ）（ ） （ ）? ?? ??? ??ctctct （ 36） 北京郵電大學(xué)工學(xué)碩士學(xué)位論文 14 設(shè) 22K ??i i ixy，1 2 1 21 2 1 2A= ????????x x x xx x x x聯(lián)立以上方程組，可以計(jì)算出用戶的坐標(biāo)如下： 2 2 2 2 2 2 2 21 3 1 2 2 1 2 1 1 3 3 12 2 2 2 2 2 2 23 1 1 2 2 1 1 2 1 3 3 11 ( ) ( ) ( ) ( )2 | |1( ) ( ) ( ) ( )2 | |? ??? ? ? ? ? ? ? ? ? ?? ? ???? ? ? ? ? ? ? ? ? ? ?????x y y K K C t C t y y K K C t C tAy x x K K C t C t x x K K C t C tA （ 37） WiFi 定位技術(shù) WiFi 定位技術(shù) 是基于無線網(wǎng)絡(luò)的定位技術(shù) ，在可以實(shí)現(xiàn)無線接入的同時(shí)，可以實(shí)現(xiàn)定位功能。 Wifi 定位首先要知道各個(gè)無線接入點(diǎn) (AP)位置，通過測算無線信號(hào)的強(qiáng)弱變化，利用一定的定位算法對(duì)被定位的物體的位置進(jìn)行測算。 此定位方法存在一定的誤差，主要是由于信號(hào)強(qiáng)度不僅會(huì)受到距離因素的影響，還會(huì)受到很多其他因素的影響。 GPS 定位技術(shù) GPS(Global Positioning System)是美國從 20 世紀(jì) 70 年代開始研制的一個(gè) 覆蓋全球的衛(wèi)星定位系統(tǒng) ，即 全球定位系統(tǒng) [23]。 集成 GPS 定位需要 借助于 手 機(jī)內(nèi)置 的 GPS 模塊， 其主要用于捕獲并跟蹤一定的衛(wèi)星，只有接收無發(fā)射功能。 GPS模塊 中的微處理器根據(jù)獲取到的衛(wèi)星軌道 參數(shù) 來計(jì)算諸如經(jīng)緯度、速度等 GPS定位信息。 集成 GPS 定位技術(shù)具有全球性、全天候、全能性、實(shí)時(shí)性和連續(xù)性等顯著 的 特點(diǎn)， 而且良好性和保密性使得它成為了民用與軍用導(dǎo)航系統(tǒng)的主要技術(shù)。 盡管 GPS 定位擁有定位速度快與 定 位準(zhǔn)確率高的優(yōu)點(diǎn) ， 但是它也有存在成本 高 、 數(shù)據(jù)缺失和數(shù)據(jù)漂移的問題：首先，在室內(nèi)通常無法獲取到 GPS 信號(hào)，天氣或障礙物會(huì)阻礙信號(hào)的正常接收， GPS 啟動(dòng)之初需要 先下載輔助定位信息才能開始進(jìn)行定位，以上這些原因都會(huì)引起 GPS 數(shù)據(jù)的缺失；另外，城市中林立的高樓和茂密的樹木都可能會(huì)產(chǎn)生多徑效應(yīng)，從未容易引起 GPS 數(shù)據(jù)漂移的問題。 GPS 定位的誤差按照來源進(jìn)行劃分可以分類三類，三個(gè)來源分別是 GPS 衛(wèi)星、接收器和信號(hào)傳播路徑。在 GPS 定位的誤差中，由于傳播路徑中的障礙物引起的多徑效應(yīng)而生成的誤差是主要誤差之一，它會(huì)降低定位準(zhǔn)確率 [25]。因此，本文著重討論對(duì)多徑效應(yīng)引起的誤差的修正。 第二章 當(dāng)前研究基礎(chǔ)綜述 15 隨機(jī)誤差的大小和方向不確定。而多徑效應(yīng)引起的誤差就是隨機(jī)誤差，因此，難以對(duì)其進(jìn)行測量或者進(jìn) 行修正處理。但是，經(jīng)數(shù)學(xué)原理和統(tǒng)計(jì)實(shí)驗(yàn)可證明，隨機(jī)誤差符合正態(tài)分布的規(guī)律，因此，通?？梢允褂弥兄禐V波法、網(wǎng)絡(luò)神經(jīng)濾波法、防脈沖干擾平均值法、算數(shù)平均濾波法、信號(hào)合理判斷法等方法對(duì)誤差進(jìn)行修正。其中，信號(hào)合理判斷法算法簡便、能夠克服因偶然因素引起的脈沖干擾，因此本文采用此方法，另外，本文還結(jié)合使用最小二乘法與 3σ 法則，用于對(duì)多徑效應(yīng)引起的誤差進(jìn)行分析。 首先，對(duì)靜止的情況進(jìn)行分析。當(dāng)用戶靜止時(shí)，在一個(gè)時(shí)間窗口內(nèi)，采集到n 個(gè) GPS 坐標(biāo)位置，假設(shè) P 是這一系列坐標(biāo)的算數(shù)中心點(diǎn)， id 是 第 i 個(gè) GPS 坐標(biāo)位置與 P 點(diǎn)之間的距離， D 是最佳誤差范圍，即誤差范圍內(nèi)允許的坐標(biāo)與 P點(diǎn)之間距離的最大值。根據(jù)最小二乘法可知，當(dāng)采集到的 GPS 坐標(biāo)位置均位于正常的誤差范圍中時(shí)，偏離的平方和 S 達(dá)到最小值，公式如下： 21 m in（ ）????niiS d D （ 31） 根據(jù)極值法對(duì)上式進(jìn)行分析： 10? ??niinD d （ 32） 進(jìn)而可以計(jì)算出最佳誤差范圍 D： 11????niiD d dn （ 33） 因此，最佳誤差范圍 D 是一系列 GPS 坐標(biāo)位置與系列坐標(biāo)算數(shù)中心點(diǎn) P 之間的距離的算數(shù)平均值。由于采集的 GPS 位置數(shù)據(jù)中不可避免會(huì)存在無效點(diǎn)，因此，采用 3σ 法則對(duì)無效點(diǎn)進(jìn)行判斷，當(dāng)滿足下式時(shí)，即判定該點(diǎn)為無效點(diǎn)： 211| | 3 ( )??niiid d d dn （ 34） AGPS 定位技術(shù) 輔助 GPS(Assist GPS， AGPS） [24]是對(duì) GPS 定位方法的改進(jìn) ， 它與 GPS 定位方法的區(qū)別主要包括以下幾個(gè)方面。首先，在定位啟動(dòng)階段，從 AGPS 服務(wù)器獲取到用戶的大概位置，并把該位置對(duì)應(yīng)的 GPS 定位輔助數(shù)據(jù)發(fā)送給用戶，這樣可以大大提高 GPS 定位的預(yù)熱速度。其次，用戶的 GPS 模塊獲取到定位數(shù)據(jù)可以被發(fā)送到 AGPS 服務(wù)器 。 針對(duì) GPS 的問題， iPhone 手機(jī)使用了 AGPS 定位技術(shù)，該技術(shù)大大提高了 GPS 的啟動(dòng)速度，減少了部分?jǐn)?shù)據(jù)缺失，是仍然無法解決數(shù)據(jù)漂移和室內(nèi)定位的問題。 北京郵電大學(xué)工學(xué)碩士學(xué)位論文 16 本章總結(jié) 本章主要對(duì)當(dāng)前 交通模式識(shí)別 的相關(guān)技術(shù)，尤其是本文相關(guān)的技術(shù)進(jìn)行了概述。 第一部分， 對(duì)交通模式識(shí)別技術(shù)進(jìn)行了概述，闡述了模式識(shí)別技術(shù)的基礎(chǔ)，對(duì)當(dāng)前國內(nèi)外交通模式識(shí)別的研究現(xiàn) 狀和進(jìn)展進(jìn)行了介紹， 總結(jié)了相關(guān)方法、技術(shù)的不足，為后續(xù)開展交通模式識(shí)別方法的研究指明了方向。 第二部分， 對(duì)交通模式識(shí)別中常用的分類算法進(jìn)行了介紹，重點(diǎn)研究了 隨機(jī)森林 算法 ，包括其在模型構(gòu)建和特征選擇方面的應(yīng)用。第三 部分，對(duì) 基于智能手機(jī)的定位技術(shù) 進(jìn)行了 研究 ，分析 了各種定位方式的特點(diǎn) 、原理 以及適用場景 ，為本文定位方法的確定提供技術(shù)依據(jù)。 第三章 基于位置的公共交通擬合方法設(shè)計(jì)與實(shí)現(xiàn) 17 第 三 章 基于智能手機(jī)的 交通模式識(shí)別方法 設(shè)計(jì)與實(shí)現(xiàn) 為了實(shí)現(xiàn)基于智能手機(jī)的交通模式判別系統(tǒng)，首先，需要確定一種交通模式識(shí)別方法。本章提出了一種基于智能手機(jī)的交通模式識(shí)別方法，首先介紹了該方法的設(shè)計(jì)思路，然后從數(shù)據(jù)采集、特征提取、模型構(gòu)建等方面對(duì)方法進(jìn)行了詳細(xì)的介紹，然后通過實(shí)驗(yàn)驗(yàn)證了方法的有效性，最后介紹了對(duì)模型簡化的方法和結(jié)果。 設(shè)計(jì)思路 本章節(jié)所述的交通模式識(shí)別方法主要是指模式識(shí)別中的設(shè)計(jì)過程，設(shè)計(jì)過程主要分為以下五個(gè)步驟 ，如圖 41 所示 ： （ 1） 采集 數(shù)據(jù) 使用 手機(jī) 采集 用戶 的 原始 交通數(shù)據(jù) ，其中， 原始交通數(shù)據(jù)包括手機(jī)中 GPS、加速度傳感器、陀螺儀、聲