路徑分析

LBS不僅需要能確定目標的地理位置，還需要能實現對地理環境的有效分析。網絡分析是地理環境分析中的一個重要技術，包括最短路徑分析、網絡流分析等內容。在網絡分析中，最短路徑分析是最基本的，也是最關鍵的技術，一直是計算機科學、運籌學、交通工程學、地理信息學等學科的一個研究熱點。如今，最短路徑分析算法已經非常成熟，如以Dijkstra算法為代表的寬度搜索方法、動態規劃方法等。

一種統計程序，通過分析變量之間假設的因果效應，來測試研究人員提出的關於一套觀察或者呈現變量之間因果關係的理論。由美國遺傳學家S.賴特於1921年首創，後被引入社會學的研究中，並發展成為社會學的主要分析方法之一。

路徑分析的主要目的是檢驗一個假想的因果模型的準確和可靠程度，測量變量間因果關係的強弱，回答下述問題：①模型中兩變量xj與xi間是否存在相關關係；②若存在相關關係，則進一步研究兩者間是否有因果關係;③若xj影響xi，那麼xj是直接影響xi，還是通過中介變量間接影響或兩種情況都有；④直接影響與間接影響兩者大小如何。

路徑分析包含了兩個基本內容：一個是路徑的搜索；另一個是距離的計算。路徑搜索的算法與連通分析是一致的，通過鄰接關係的傳遞來實現路徑搜索。路徑的長度(距離)以積聚距離(accumulated distance)來計算。距離的計算方法為：將柵格路徑視做由一系列路徑段(path segments)組成，在進行路徑搜索的同時計算每個路徑段的長度並累計起來，表示從起點到當前柵格單元的距離。這裏路徑段指的是在一定的精度範圍內可以以直線段模擬和計算的柵格單元集合。

路徑分析是GIS中最基本的功能，其核心是對最佳路徑和最短路徑的求解 ^[1]  。

①最佳路徑

從網絡模型的角度看，最佳路徑求解就是在指定網絡的兩結點間，找一條阻礙強度最小的路徑。最佳路徑的產生基於網線和結點轉角(如果模型中結點具有轉角數據的話)的阻礙強度。

例如，如果要找最短的路徑，阻礙強度要預先設定為通過網線或在結點轉彎處所花費的時間；如果要找費用最小的路徑，阻礙強度就應該是費用。當網線在順逆兩個方向上的阻礙強度都是該網線的長度，而結點無轉角數據或轉角數據都是0時，最佳路徑就成為最短路徑。

在某些情況下，用户可能要求系統能一次求出所有結點間的最佳路徑，或者要了解兩結點間的第二、第三乃至第X條最佳路徑。

②最佳遍歷方案

另一種路徑分析功能是最佳遍歷方案的求解。

網線最佳遍歷方案求解是給定一個網線集合和一個結點，求解最佳路徑，使之由指定結點出發至少經過每條網線一次而回到起始結點。

結點最佳遍歷方案求解則是給定一個起始結點、一個終止結點和若干中間結點，求解最佳路徑，使之由起點出發遍歷全部中間結點而達到終點。

(1)靜態求最佳路徑：由用户確定權值關係後，給定每條弧段的屬性，當求最佳路徑時，讀出路徑的相關屬性，求最佳路徑。

(2)N條最佳路徑分析：確定起點、終點，求代價較小的幾條路徑。在實際應用中僅求出最佳路徑並不能滿足要求，可能NN某種因素不走最佳路徑，而走近似最佳路徑。

(3)最短路徑：確定起點、終點和所要經過的中間連線，求最短路徑。

(4)動態最佳路徑分析：實際網絡分析中權值是隨着權值關係式變化的，而且可能會臨時出現一些障礙點，所以往往需要動態地計算最佳路徑。

最優路徑分析是地理網絡分析中最常見的基本功能，也是LBS需要具備的功能。地理網絡中的最優路徑是指在地理網絡中滿足某些優化條件的一條路，包括距離最短或最長、通行時間最短、運輸費用最低、行使最安全、容量最大等。

1．道路預處理

進行道路數據錄入時，往往在道路的交叉接合處出現重疊或相離的情況，不宜計算機處理。因此，需要對原始數據進行預處理，使道路接合符合處理要求。進行預處理時，取每條線段的首末節點座標為圓心，以給定的閾值為半徑作圓域，判斷其他線段是否與圓域相交，如果相交，則相交的各個線對象共用一個節點號 ^[2]  。

2．道路自動斷鏈

對道路進行預處理之後即可獲得比較理想的數據，在此基礎上再進行道路的自動斷鏈。步驟如下：

（1）取出所有線段記錄數n，從第一條線段開始；

（2）找出所有與之相交的線段並求出交點數m；

（3）將m個交點和該線段節點在判斷無重合後進行排序；

（4）根據交點數量，該線段被分成m+1段；

（5）第一段在原始位置不變，後m段從記錄尾開始遞增；

（6）重複（2）～（5），循環至n。

3．節點匹配

拓撲關係需使用統一的節點。節點匹配方法是按記錄順序將所有線段的始末點加上相應節點號，座標相同的節點共用一個節點號，與前面所有線段首末點都不相同的節點按自然順序遞增1。

4．迪傑克斯特拉（Dijkstra）算法

經典的圖論與計算機算法的有效結合，使得新的最短路徑算法不斷湧現。目前提出的最短路徑算法中，使用最多、計算速度比較快，又比較適合於計算兩點之間的最短路徑問題的數學模型就是經典的Dijkstra算法。

該算法是典型的單源最短路徑算法，由Dijkstra EW於1959年提出，適用於所有弧的權均為非負的情況，主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。該算法的基本思想是：認為兩節點間最佳路徑要麼是直接相連，要麼是通過其他已找到的與起始點的最佳路徑的節點中轉點。定出起始點P₀後，定能找出一個與之直接相連且路徑長度最短的節點，設為P₁，P₀到P₁就是它們間的最佳路徑。

Dijkstra算法的基本流程如下：首先將網絡中所有節點分成兩組，一組包含了已經確定屬於最短路徑中點的集合，記為S（該集合在初始狀態只有一個源節點，以後每求得一條最短路徑，就將其加入到集合S中，直到全部頂點都加入到S中，算法就結束了）；另一組是尚未確定最短路徑的節點的集合，記為V，按照最短路徑長度遞增的次序依次把第二組的頂點加入到第一組中，在加入的過程中總保持從源點到S中各頂點的最短路徑長度不大於從源點到V中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點距離就是從源點到此頂點的最短路徑長度，V中的頂點距離是從源點到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

路徑分析的主要步驟是：①選擇變量和建立因果關係模型。這是路徑分析的前提。研究人員多用路徑圖形象地將變量的層次，變量間因果關係的路徑、類型、結構等,表述為所建立的因果模型。下圖是5個變量因果關係的路徑。　圖中帶箭頭的直線“→”連接的是具有因果關係的兩個變量,箭頭的方向與因果的方向相同;當兩變量只有相關關係而無因果關係時，用弧線雙向箭頭表示。圖中變量分為：a.外生變量。因果模型中只扮演因，從不扮演果的變量,是不受模型中其他變量影響的獨立變量,如x1與 x2。b.內生變量。模型中既可為因又可為果的變量，其變化受模型中其他變量的影響,如x3、x4與x5。c.殘差變量。來自因果模型之外的影響因變量的所有變量的總稱，如e3、e4、e5。

若變量間的關係是線性可加的，則圖中的因果模型可用3個標準化多元線性迴歸方程表示：

　pij 稱為由xj到xi的路徑係數，它表示xj與xi間因果關係的強弱,即當其他變量均保持不變時,變量xj對變量xi的直接作用力的大小。pie稱為殘差路徑係數,它表示所有自變量所不能解釋的因變量的變異部分，其大小對於因果模型的確定有重要作用。

②檢驗假設。路徑分析要以下列假定為前提：a.變量間的因果關係是單向的，不具有反饋性，又稱遞歸模型；b.變量間具有線性可加關係；c.變量具有等距以上測量尺度；d.所有誤差均為隨機的，外生變量無測量誤差；e.所有內生變量的誤差變量間及與內生變量有因果關係的所有自變量間無相關。當某些假定，如遞歸性或變量的測量尺度不滿足時，要做適當的處理才能應用路徑分析。

③估計參數。首先計算路徑係數與殘差路徑係數,然後計算兩變量間相關係數rji。此外，要計算兩變量間總因果作用力,包括變量xj對xi的直接作用力、xj經中間變量而對xi的間接作用力兩部分。例如,上圖的因果模型中，x1對x5的總作用力由直接作用力p51和間接作用力構成。這兩部分作用力的大小可由兩變量間的相關係數rij的分解得到。最後還要計算決定係數嵀,它表示所有作用於xi的自變量所能解釋xi變異量的比例。公式是： 　④評估因果模型。評估的主要指標是：a. 嵀，若嵀太小，則要考慮是否需要增加新的自變量，以保證模型精度。b，一個理想的因果模應當很小,當它很大時，則有必要重新估計此因果路徑也可由公計算。c.進行F檢驗。 式中Q為殘差平方和,U為迴歸平方和，N為樣本數,K為變量數，檢驗不顯著時要修改模型。 路徑分析是多元迴歸分析的延伸，與後者不同的是：①路徑分析間的因果關係是多層次的，因果變量之間加入了中介變量，使路徑分析模型較一般迴歸模型對於現實因果關係的描述更豐富有力。②路徑分析不是運用一個而是一組迴歸方程，在分析時更應注意保證各方程式所含意義的一致性 ^[3]  。