Data(Under Construction!)

Data

繁中「資料」、簡中「数据」。

備忘

vector presentation / matrix representation
row dimension is feature / column vector is data
注意到本站的矩陣格式與統計學慣用方式不同。
資料畫成圖形 function plot
statistics table <---> data point plot
coordinate 兩種變數標記方式
statistics: histogram
distribution -> sequence                   realization
frequency distribution(pdf) <- sequence    bucket sort/histogram
empirical distribution(cdf) <- sequence    bucket sort/histogram
new chapter: point set / sampling / metric
succeeded by transformation

Measure

長度(Length)

現實世界,考慮一個東西有多少份量;化為數學,就是考慮一個東西的長度是多少。

此處的長度,是數學術語,不是物理學術語。此處的長度,是指份量多寡,不是指公分公尺。

長度函數(Norm)

長度在數學中擁有嚴謹定義:

一、長度不會是負數,p(A) ≥ 0。
二、有些東西長度為零,p(X) = 0。
三、一個東西均勻放大縮小,其長度也隨著放大縮小,p(k⋅A) = |k|⋅p(A)。
四、兩個東西拼裝起來,其長度只會累加或短少,p(A + B) ≤ p(A) + p(B)。

常見的長度函數:

L₀-Norm:非零的數量。
L₁-Norm:先轉正數、再相加。
L₂-Norm:先平方和、再平方根。
L∞-Norm:最大值。

常見的元件:

一個數值的長度:用絕對值計算長度。
一個向量的長度:有多種公式,請參考「Vector Norm」。
        最經典的是平方長度:先平方和、再平方根。
一個矩陣的長度:有多種公式,請參考「Matrix Norm」。

距離(Distance)

現實世界,考慮兩個東西有多相似;化為數學,就是考慮兩個東西的距離有多接近。

此處的距離,是數學術語,不是物理學術語。此處的距離,是指差異份量多寡,不是指公分公尺。

距離函數(Metric)

距離在數學中擁有嚴謹定義:

一、距離不會是負數,d(A,B) ≥ 0。
二、兩個一樣的東西,距離等於零,d(A,A) = 0。
三、A到B的距離等於B到A的距離,d(A,B) = d(B,A)。
四、三角不等式,ABC三個東西,兩邊和大於等於第三邊,
  d(A,B) + d(B,C) ≥ d(A,C)。
  或者說,三個東西融合成兩個東西,其距離只會累加或短少,
  d(A,C) ≤ d(A,B) + d(B,C)。

常見的距離函數:

Euclidean Distance(L₂):直線距離。
Taxicab Distance(L₁):垂直、水平移動的距離。
Hamming Distance(L₀):相對應維度,數值相異的維度個數。

常見的元件:

兩個數值的距離:用減法與絕對值計算距離。
兩個向量的距離:以「Minkowski Distance」或「Angular Distance」計算距離。
兩串字串的距離:以「Edit Distance」或者「K-mer Distance」計算距離。
兩串數列的距離:數列類似字串,同上。
兩串訊號的距離:以「Linear Predictive Coding」或者「Fourier Transform」
        重新表示訊號,再用數學公式計算距離。
兩個樣本的距離:以「Mahalanobis Distance」計算距離。
兩條曲線的距離:以「Fréchet Distance」計算距離。
兩群點的距離:以「Hausdorff Distance」或者「Matching Distance」計算距離。
兩個集合的距離:以「Jaccard Index」或者「Sørensen-Dice Index」計算距離。
兩棵樹的距離:以「Tree Edit Distance」計算距離。
兩張圖的距離:以「Graph Kernel」計算距離。

UVa 10508 11085 ICPC 5132

距離函數(Divergence)

不滿足上述定義的距離函數,嚴謹起見,大家另起一名divergence。由於該詞彙已經用於多變量函數的散度運算,簡單起見,大家經常假借舊名distance。

常見的元件:

兩個向量的距離:以「Cosine Distance」計算距離。
兩個函數點(凸函數)的距離:以「Bregman Divergence」計算距離。
兩個分布的距離:以「Kullback-Leibler Divergence」計算距離。