# 補充：multivariate outliers

本篇文章的內容為筆記「[補充：Exploratory Data Analysis](https://hackmd.io/@pipibear/rkrGpFxF0)」的延續，在那篇筆記裡，最後當我們在講 outliers 時，因為篇幅太長，所以我們只講了課本的 univarite 的情形。

當時我們說，利用 box-plot 或是其他的 graphical technique，我們可以用看的就能找出 outliers，但是這樣的方法只適用於 univariate data。

當我們的 data 是 multivariate 時，我們是沒有辦法用看的就找出哪些是 outliers，挑出 outliers 的工作也就變得複雜許多。
> 實務上，當我們的 variable 數 $d>2$ 時，就很難去辨認 outliers。

在這篇筆記裡，我只會簡單講一下 multivariate case 的情況下我們大致上可以怎麼做，舉簡單的例子，停在大概有點概念的程度。如果有興趣深入看看，參考資料的兩篇文章一篇介紹了如何用 python 來計算 MD，另一篇為 multivariate outliers detection 的論文，這篇論文前半部分還是很容易懂的，後半部我就沒看了，總之有興趣可參考！

---

在 multivariate 的情況下，detect outliers 的方法還是有許多種，包含用不同的 distance metrics、scores、一些特殊的技巧⋯⋯。

舉例來說：

- 最常見的 distance metric 為 Euclidean distance，也就是用我們平常計算距離的方法，根據 observation 和 center point 間的距離，來辨認它是否為 outlier。
- 我們也可以用 z-score 來定義是否為 outlier
> z-score：以 $\sigma$ 為單位，計算 $x$ 和 $\mu$ 之間的距離 $\frac{x-\mu}{\sigma}$

## Mahalanobis distance

Mahalanobis distance (MD) 是一種很適合 multivariate data 的 distance metric，因為 MD 代表的是 data point 和 ++distirbution++ 之間的距離。什麼意思呢？下面我們就會看到。

multivariate case 中，MD 的定義為：

\begin{equation}
\sqrt{(\vec{x}-\vec{\mu})^T\Sigma^{-1}(\vec{x}-\vec{\mu})}
\end{equation}
> 此處因為是 multivariate，所以我們假設每個 observation 為 $\vec{x} = [x_1,...,x_d]^T$ 為一個 $d$-dimensional 的向量。
>
> $\rightarrow$ 關於 Mahalanobis distance 的說明，可參考筆記「[5.4 Multivariate Normal Distribution](https://hackmd.io/@pipibear/SkgL8C3OA)」。

因此，根據定義，在計算點 $\vec{x}$ 和中心 $\vec{\mu}$ 的距離時，MD 會用到 covariance matrix $\Sigma$，所以如果我們把 MD 當作衡量是否為 outlier 的方式，就不是像 Euclidean distance 一樣單純只考慮 observation 和中心的距離，而是把所有 data points 的 distribution pattern 也考慮進去。

看個圖比較清楚：


從左邊的 Euclidean 我們可以看到，以代表 center 的綠色點為圓心，我們用某個值作為半徑畫出一個圓形的 outlier threshold，在綠色範圍以外的 data points 都是 outliers。

但是這樣的畫法並沒有考慮 data points 的 distribution。藍色的點其實呈一個當 $x$ 越大 $y$ 就越大的情形，也就是 $X,Y$ 為正相關，即 $Cor(X,Y) > 0$。

因為現在我們是 bivariate（即 $d=2$，我們只有兩個 variable $X,Y$）所以 covariance matrix 為：

\begin{equation}
\Sigma =
\begin{bmatrix}
Var(X) & Cor(X,Y) \\
Cor(Y,X) & Var(Y)
\end{bmatrix}
\end{equation}

在計算 MD 時，透過 $\Sigma$，我們把 $Cor(X,Y) > 0$ 的某個值也考慮進去了，當然也有 $X,Y$ 自己本身的 variance，所以我們才說 MD 能把 data points 的 distribution pattern 考慮進去。

從上圖右方我們可以看見，當 distance metric 為 MD 時，我們畫出來的 outlier threshold 更接近實際 data points 的分佈情形，因此拿來判斷 outliers 也就更貼切。
> 例如去看兩張圖中右上角的那些 data points，以 Euclidean distance 判斷，將他們視為 outliers 明顯就不太合理。
>
> Recall： outlier 的意義是指那些 "data points that do not fit the model of the rest of the data"

不過，也不是所有情況下用 MD 都更適合，比如說當我們的 data points 本身就呈現一個圓形的分佈時，用 Euclidean distance 就更恰當。

$\rightarrow$ 因此在選擇 distance metric 時，我們要考慮 data 分佈的情形。

## masking and swamping effects


當我們的 data set 有許多的 outliers，或是 clusters of outliers 時，就會有 masking 和 swamping effect 發生。雖然沒有明確的數學定義，但是下面我們會說明這兩種 effects 的直觀定義。

### masking effect

<font color = "snake">masking effect</font> 的意思如它的名字，也就是一個 outlier 去 "mask" 另一個 outlier。

更詳細的說，如果單純只看第二個 instance 本身，它會被視為是 outlier，但是當我們把第一個 outlier 也考慮進去時，它就不是 outlier 了。

$\rightarrow$ 因此，當我們把第一個 outlier 刪掉以後，第二個就變成是 outlier。

masking 會發生在當一個 outlying observations 的 cluster 讓 mean 和 covariance estimates 向它傾斜時，而且這樣一來，outlying point 和 $\vec{\mu}$ 之間的距離就變得比較小。
> 也就是說，masking effect 可能會讓 outlier 的 MD 變小。（以 MD 作為 distance metric 的情況下）

### swamping effect

<font color = "snake">swamping effect</font> 的意思也和它的名字相同，也就是一個 outlier "swamps"（覆蓋、淹沒）另一個 observation，第二個 observation 只有在第一個 outlier 存在的情況下，才會被視為 outlier。

$\rightarrow$ 因此，如果我們把第一個 outlier 刪掉，那麼第二個 observation 就變成了 non-outlying observation。

swamping 發生在當一群 outliers 讓 mean 和 covariance estimates 向它們傾斜，同時遠離其它的 non-outlying instances 時。並且這樣一來，也反倒使得 non-outlying instances 的 distance 變得比較大，讓我們覺得好像它們才是 outliers。
> 也就是說，swamping effect 可能會讓 non-outlying observations 的 MD 變大。

### 解決方式

因為有 masking 和 swamping effect，所以當我們在計算 MD 時，比起用 robust estimators （以一般的定義計算 $\vec{\mu}, \Sigma$），有些人就提出一些方法來改善這樣的問題。例如：

- Hadi：將 $\vec{\mu}$ 用一個 median 的 vector 取代、取一個 observations 的 subset，只包含那些 MD 很小的 observations，來計算 $\Sigma$
- Penny and Jolliffe：對 Hadi 的方法再作修改，在 estimating $\Sigma$ 時，對每個 observation 根據它和 center 之間的距離施加一個 weight。

## 例子


假設我們從一個 distribution $\sim N(100,5)$ 的 population 中取 $100$ 個 observations，並且想要從這 $100$ 個 data points 找出 outliers。

這些 data points 為 $2$-dimensional，也就是每個 data point 為一個 $[x,y]^T$ 的向量。

圖中的左上角為 scatterplot。

圖下方的 $x$ values 和 $y$ values 則是我們根據這 $100$ 個點的 $x,y$ 值，拆開來看得到的 box plot。我們可以看到兩個圖的 box 兩塊都差不多大、兩端的 whiskers 也都差不多長，因此我們基本上沒辦法像 univariate 時用這種方式來找出 outliers。

可是回過頭來看 scatterplot，我們會發現右下角那幾個點應該是 outliers。這代表說在 multivariate 的情況下，我們沒辦法把各個 variable 拆開來看來找出 outliers，而必須要考量 variables 之間的關係。

因此，如果要把 variables 之間的關係也考慮進去，那就是用右上角的方式：

圖中每個 $+$ 為我們原本的 data points，我們以 MD 作為 distance metric，四個顏色的 ellipsoids 分別是當 MD 為四個 constant 時的情形，這四個值分別為 chi-square distribution 的 $25,50,75\%$ 以及 adjusted quantiles。

為什麼這裡突然冒出一個 chi-square distribution 是因為，當我們的 data 是 normally distributed 時，這些 data 的 MD 分佈大約是 chi-square distributed with $d$-degrees of freedom（$d=$ variable 數）

詳細見下圖說明：

> - Note： $25\%$ quantile $=25$ percentile $=1$ quartile
>
> 由 chi-square distribution 的 pdf（$r=2$）中我們可以看見，當我們的 data 是 noramlly distributed 時，比較大的 MD 值發生的機率是比較小的，這一樣也代表說如果我們有某個 observation MD 算出來比較大，那它就比較有可能是 outlier。
>
> 因此我們就根據算出來的 $0.58, \ 1.39, \ 2.77$ 以及另一個 adjusted quantile，畫出了左下角的那四個 threshold，淺藍色的範圍代表有 $25\%$ 的 observations 應該要落在裡面、深藍色代表 $50\%$ 的 observations 應該要落在裡面⋯⋯。
>> adjusted quantile 怎麼取的我沒有特別看，有興趣可參考論文的 section $2.1$。

關於 multivariate outliers 就大概講到這裡，以上都非課本內容，所以如果有錯誤或疑問歡迎再留言告訴我！

# 參考資料
- [Identification of multivariate outliers - Problems and Challenges of Visualization Methods](https://www.ue.katowice.pl/fileadmin/user_upload/wydawnictwo/SE_Artykuły_231_250/SE_247/05.pdf)
- [Multivariate Outlier Detection in Python](https://towardsdatascience.com/multivariate-outlier-detection-in-python-e946cfc843b3)