反距離加權

反距離加權（英語：inverse distance weighting，IDW）是一種在有已知的離散數據點的情形下進行多元插值的確定性算法。賦給未知點的值是用已知點的值的加權平均數計算得出的。該算法也可在空間自相關分析（例如莫蘭指數）中用於構建空間權重矩陣。

該方法的名稱來自其加權的方式：未知點到每個已知點的距離的倒數。

問題的定義

對於給定的離散數據點，我們希望以一個函數$u$對研究區域進行插值：

$u(x):x\to \mathbb {R} ,\quad x\in \mathbf {D} \subset \mathbb {R} ^{n},$

其中$\mathbf {D}$是研究區域。

$N$個已知數據點可以視為元組列表：

$[(x_{1},u_{1}),(x_{2},u_{2}),...,(x_{N},u_{N})].$

該函數應當是「平滑的」（連續且一次可微），確定的（$u(x_{i})=u_{i}$），並滿足用戶對研究的現象的直觀預期。此外，該功能應能夠以合理成本在電腦應用上實現（如今，基本實現方法中可能會用到並行計算）。

謝潑德法（Shepard's method）

歷史參考

自1965年起，在哈佛計算機圖形和空間分析實驗室，各專業的科學家匯聚一堂，重新思考現在稱作「地理信息系統」的各種問題。

實驗室工作的推動者霍華德·費舍爾（Howard Fisher）構思了一種改良的計算機繪圖程序：SYMAP，其設計伊始，費舍爾就希望對插值進行改進。他向哈佛大學新生展示了SYMAP的進展，而後許多新生參與了實驗室活動。一位大一新生唐納德·謝潑德（Donald Shepard）決定對SYMAP中的插值法進行大改，隨後發表了他1968年的著名論文。

謝潑德的算法也受到William Warntz和實驗室其他從事空間分析工作的人的理論方法的影響。他用距離的指數進行了許多實驗，決定更接近重力模型（-2的指數）。謝潑德不僅實現了基本的反距離加權，還允許障礙（包括可滲透的和絕對的）插值。

其他研究機構此時也在研究插值，特別是堪薩斯大學及其SURFACE II計劃。但SYMAP的功能仍是最先進的，儘管是由本科生編寫的。

基本形式

來自表面上的散點在不同冪參數p下的謝潑德插值$z=\exp(-x^{2}-y^{2})$

給定一組樣本點$\{\mathbf {x} _{i},u_{i}|{\text{for }}\mathbf {x} _{i}\in \mathbb {R} ^{n},u_{i}\in \mathbb {R} \}_{i=1}^{N}$，反距離加權插值函數$u(\mathbf {x} ):\mathbb {R} ^{n}\to \mathbb {R}$定義為：

$u(\mathbf {x} )={\begin{cases}{\dfrac {\sum _{i=1}^{N}{w_{i}(\mathbf {x} )u_{i}}}{\sum _{i=1}^{N}{w_{i}(\mathbf {x} )}}},&{\text{if }}d(\mathbf {x} ,\mathbf {x} _{i})\neq 0{\text{ for all }}i,\\u_{i},&{\text{if }}d(\mathbf {x} ,\mathbf {x} _{i})=0{\text{ for some }}i,\end{cases}}$

其中

$w_{i}(\mathbf {x} )={\frac {1}{d(\mathbf {x} ,\mathbf {x} _{i})^{p}}}$

這是一個簡單的反距離加權函數，其定義由謝潑德提出，x表示一個被插值點（未知點），x_i表示一個節點（已知點），$d$是從已知點x_i到未知點x的給定距離（度規算符），N是插值中使用的已知點的總數，並且$p$是一個正實數，稱為冪參數。

其中，權重隨著與已知點的距離的增加而減小。$p$值越大，則最鄰近已知點的對插值的影響越大，當$p$足夠大時，插值結果形似馬賽克多邊形（沃羅諾伊圖），每一個多邊形內的數值幾乎為恆定值。對於二維面，冪參數$p\leq 2$時，插值由距離較遠的點主導，因為密度為$\rho$、鄰近節點距離為$r_{0}$至$R$之間的數據點集，權重的加和約為

$\sum _{j}w_{j}\approx \int _{r_{0}}^{R}{\frac {2\pi r\rho \,dr}{r^{p}}}=2\pi \rho \int _{r_{0}}^{R}r^{1-p}\,dr,$

其在$R\rightarrow \infty$且$p\leq 2$時發散。對於M維，同樣的結論適用於$p\leq M$。對於$p$值的選擇，可以考慮插值中所需的平滑程度、被插值的樣本密度和分布，以及允許單個樣本影響周圍樣本的最大距離。

謝潑德法是最小化與插值點{x, u}的元組和插值點{x_i, u_i}的i元組之間的偏差度量相關的函數的結果，定義為：

$\phi (\mathbf {x} ,u)=\left(\sum _{i=0}^{N}{\frac {(u-u_{i})^{2}}{d(\mathbf {x} ,\mathbf {x} _{i})^{p}}}\right)^{\frac {1}{p}},$

從最小化條件導出：

${\frac {\partial \phi (\mathbf {x} ,u)}{\partial u}}=0.$

該方法容易擴展到其他維數的空間，它實際上是將拉格朗日插值法推廣到多維空間。為三元插值設計的修改版算法由Robert J. Renka提出，Netlib的toms庫中的算法661提供該算法。

一維下的示例

Shepard法在一個維度下的插值，基於4個樣本數據點，p = 2

調整謝潑德法

謝潑德法的另一個修改版是僅使用半徑R範圍內的最近鄰（而不是完整樣本）來計算插值。在這種情況下，權重略有修改：

$w_{k}(\mathbf {x} )=\left({\frac {\max(0,R-d(\mathbf {x} ,\mathbf {x} _{k}))}{Rd(\mathbf {x} ,\mathbf {x} _{k})}}\right)^{2}.$

當與快速空間搜索結構（如k-d樹）結合使用時，它即為適用於大尺度問題的高效N log N插值方法。

參見

• 距離衰減
• 核密度估計