[Kaggle] Kobe Bryant Shot Selection - (2) k-NN Classification

星期三 (6/8) 的時候突然發現 Kaggle 的 Kobe Bryant Shot Selection 這項競賽就要到期了！
但因為即將要放端午連假沒空作 ，想說至少要在結束前放個分數上去吧 XD
於是就把第一部份的 EDA 先暫停，先放一個成果出來看看如何先。

在先前談過，這是一個 Classification 的問題，我基本上一般會使用的基本演算法有以下幾種：

1. Logistics Regression
2. k-Nearest Neighbors Classification ( k-NN, 也可用於  Regression 問題 )
3. Classification and Regression Trees ( CART ), ID3, C4.5 等 Tree Based 方法
4. Naive Bayes Classification
5. Perceptron / SVM 

這些方法分別站在不一樣的角度去進行資料的分類，當然還有更多不同的演算法，各有優缺點及好壞，根據本篇主題先不提演算法之間的比較，專注在本篇主題，使用 k-NN 對資料進行分類。

k-NN 透過計算 Test Data 與 Training Data 之間的 Euclidean Distance ( 或其他距離 Measure ) ，來找出某一筆 Test Data 對照與其最像的 k 筆 Training Data ，再看看這 k 筆 Training Data 之中，哪一個類別的次數最多，即被分到哪一類，是一種很民主的演算法。

由上述可以了解，k-NN 方法直觀、容易理解，計算簡單、並且只需要針對 k 這個參數進行優化。( 好啦，選擇 k-NN 的原因只是因為懶 XD )

當然，如果你的 Data 中是 Continuous Variable 與 Categorical Variable 混合的情況的話，那麼選擇一個適當的距離 Measure 就會是一個相當大的問題，給個例子：在第一部份有提到 action_type 這個變數，其中 Reverse Slam Dunk Shot 與 Fadeaway Jump Shot 的 Euclidean Distance 距離應該要是多少? 在無法計算現實距離又帶點抽象的情形下，是無法進行後續 k-NN 分類的，所以必須要使用某一種 Measure 來對這些 Categorical Variable 進行 Mapping ，並且要是對於這些 Categorical Variable 標準一致的 Measure ，才不會發生貓咪跟蜜蜂比較接近，跟小狗距離比較遠的奇怪現象 XDD

另外，針對 k 的選擇會對 k-NN 的結果產生重大的影響，k 的大小會與 Bias - Variance Trade-off 有直接的關係；假設你正坐在學測的會場中，會場中大家的實力都參差不齊，但是你知道坐你附近的人都與你實力差不多 ( $x$ )，如果你突然遇到一個不會的四選一選擇題 ( $y$ )，想要參考坐你附近的答案，會發生以下幾個狀況  ：

1. 你決定只參考坐你左邊的人 ( $k=1$ ) ，於是你的答案就會跟他一樣。
2. 你決定參考坐你前後左右四周的人 ( $k=8$ ) ，於是你的答案會是這 8 個人最多人寫的答案 ( 正常人應該不會選最少人寫的吧XD )
3. 你決定參考整間教室的答案，於是你的答案會是整間教室最多人寫的答案。

想想看，如果今天有 10 個人決定一起學你，他們的情況也跟你一樣，坐他們附近的實力都差不多，並且你選了多少人，他們就選了多少人 ( $k$ 值一樣 )。

1. 我們都選擇了 "左邊這個人認為這題這樣寫，風險比較低" 的作法，也就是坐在這 10 個人左邊的人，他們判斷應該是正確的答案，會造成 Training Error 低，但是 Test Error 不一定低的情況，也就是實際上這題，根據左邊這個人所判斷出的答案，他們自己覺得是正確的 ( Training Error 低 ) ，但實際上不一定會對 ( Test Error 有可能高 )，並且因為這 10 個人參考的不一定會是同一個人的答案，造成 Model 複雜程度比較高，導致 Overfitting 的情況；另外，如果今天參考到一個實力差不多，但是想法很奇怪，別人都寫 1 ，他寫 4 的答案 ( Outlier ) ，或是根本來鬧的 ( 寫 5 )，這樣的情況都會因為 k 值太小躲不開這些情形，因此若選的 k 值太小，很容易會被 Noise 所影響，導致分類效果不彰。
2. 參考四周人的想法很好，可以想見的是，這 10 個與你遇到相同情況的人，會根據附近人的投票來決定自己寫的答案，但有可能出現：
   (1)  " A 這個人，附近寫 1 的有 5 票，寫 2 的有 3 票，所以 A 寫了 1 這個答案 "
   (2)  " B 這個人，附近寫 1 的有 3 票，寫 2 的有 5 票，所以 B 寫了 2 這個答案 "
   這反映出藉由投票，提升了分類的正確率 ( Bias 降低 ) ，但也因為投票，使得分類的出象變多了 ( Variance 增加 )，像上述例子，票數距離很接近，是一個很難分類的情況，使得 Variance  增加；因此，根據你選擇要看附近多少人 ( $k$ ) 的答案，來決定影響降低 Bias 與增加 Variance 的量。相對於只選擇左邊這個人 ( $k=1$ )，選擇多個人降低了模型複雜度，減少了 Model Overfitting 的情況，但是如果增加了參考人數 $k$ ，有可能會因為參考的人越來越多了，導致參考到實力比較差的同學的答案，或是你根本不清楚哪些答案是實力好的同學寫的，哪些是實力差的同學寫的，投票之後得到的答案就會一團混亂，使得分類的正確率下降，因此找到一個適當的參考人數 ( $k$ ) 來平衡 Bias 與 Variance 是有必要的。最後一個小提醒，一般而言，會選擇 " $k$ 為單數 "，如 1,3,5,7,... ，這樣才比較好投票XD
3. 參考所有人的答案作投票，會發現這 10 個人都跟你寫了一樣的答案，也就是說，就得看這間教室正確答題的人比較多還是錯誤答題的人比較多，答題完全是一翻兩瞪眼的狀態XD這樣的模型太過於簡單，會因為忽略正確答題的人(或說是 Training Data 的有用訊息)，導致正確率過於極端，因此通常不會選擇使用這種方法進行投票。

在 k-NN  的問題中大致還有以下幾點 ：

1. 若 Training Data 中的類別不是太均勻，是很不平衡的數量差距，例如：抽樣 2000 筆 Training Data 中，有 1995 筆的類別為 "1" ，有 5 筆的類別為 "2"，顯而易見的，丟一筆 Test Data 進 Model 裡面，被分到類別 "1" 的機率要比分到類別 "2" 的機率大的多，原因是因為，即使這筆 Test Data 實際上的類別是 "2"，取 $k$ 為 15 ，在 Training Data 與他最近的 5 筆類別為 "2" 的資料都參考到了，但因為剩下 10 筆都是類別 "1"，因此多數決投票中，這筆 Test Data 只能被分到類別 "1"，這問題的原因是 (1) 抽樣 Training Data 不平均 (2) 選擇 $k$ 值的問題，但是處理 $k$ 值不是一個根本的解決之道，解決方式還是要盡量的讓 Training Data 中的每個類別盡量均勻，或是不要產生太過極端的狀況。
2. 計算量大；由於需要計算每一筆 Test Data 與 每一筆 Training Data 之間的距離，所以計算上非常耗時。目前較常見使用 kd-tree 來解決這個問題，但還是需要載入整棵 kd-tree，所以在記憶體用量與計算速度上也是一個常見的問題。
3. 使用多數決的方法真的是可靠的嗎? 距離此 Test Data 較遠的 Training Data 與距離較近的 Training Data 應該是要一票換一票嗎? 還是應該要 0.8 : 1 ? 或是直接利用他們的距離作為票數的權重 ? ( Distance-Weighted k-NN )

以上都是使用 k-NN 時必須注意的一些問題，但不失為一個好用、直覺並使用非常廣泛的分類演算法，並且常拿來與其他分類演算法進行比較；進一步進入本篇主題：使用 k-NN 進行 shot_made_flag 的分類預測。

由於尚未作變數篩選，我們先以上述探索性資料分析與常理推斷，在這裡先選擇了 lat, lon, shot_distance, period, remain_sec 作為基本分類的變數。

在這裡使用 7-fold Cross Validation ，來幫助我們選擇分類的參考數 $k$ 值，因為是一個 Binary 的分類，所以 $k$ 的選擇不太適合用偶數，$k$ 設定從 3 ~ 45 的奇數，每個 $k$ 值重複 10 次的 Cross Validation。為什麼不是用常見的 5, 10-fold, Leave-one-out? 因為 Training Data 剛好可以被 7 整除，而且實際上，我只是想看這樣的條件下， k-NN 針對這筆資料的 Performace 大概會在哪裡，所以就先不作 K-fold 的最佳化，而是先以最佳化分類參考數 $k$ 為主。

(3-1) 以 7-fold cross validation 在各 k 值 下的分類錯誤率

由圖 (3-1) 來看，隨著 $k$ 的增加，錯誤率逐漸降低，到 $k = 25$ 開始趨於平緩，並且 $k = 27$ 錯誤率有些微上升的傾向，故在此選擇 $ k = 25 $ 作為 k-NN 之參數。
平均而言，選擇 $ k = 25 $ ，分類錯誤率平均約 41.11% 左右， Logarithmic Loss 約為 14.20797 ，雖效果不是很好，但以簡單的模型而言算是可以接受的成果。

選擇好 $k$ 值後，利用模型將分類結果產出，丟上 Kaggle 跑跑看分數。

Logarithmic Loss 為 14.29226 是一個倒數的成績XD 我們可以來看看怎樣接著提升 k-NN 的效果。