快速找中位數演算法和KNN

之前找到kd-tree這個data strucutre，想說可以用它來找KNN (k nearest neighbors)，而且建立kd-tree的速度很快，空間成本又和資料量成線性關係，實在是很讚的資料結構。

實作kd-tree的關鍵在於要能快速找到中位數，而在quick sort的Theta(N*log(N))的證明裡，有經典的找中位數演算法：用Theta(N)的時間找出中位數。不過這個演算法的常數項很大，是理論上很有意思的方法（ 由它證明了quick sort的order可以寫為 Theta(N*log(N)) )，但實務上不會拿來用。

找了一下快速計算中位數的方法，找到一篇有趣的報告：“Fast Median Search: an ANSI C implementation”。這篇報告裡提供幾種找中位數的方法以及時間比較和實務考量的分析，並附有 C source code。這篇報告用的方法都是從沒排序的陣列裡找第 k 小的數字，而找中位數只是這個問題的特殊化罷了。關鍵在於從不同的角度思考中位數的定義：

The median of a list of N values has the property that in the list there are as many greater as smaller values than this element.

很漂亮的出發點，值得學習。

我從中選了差不多最快、且馬上能讀懂的Wirth，將它改成Ruby版，畢竟我其它相關的code都用Ruby寫的（按此觀看Ruby版的Wirth）。Wirth的精神和quick sort一樣，若已學過quick sort的話，看一下code就能明白Wirth的做法。

改完Ruby版的Wirth演算法後，準備要寫kd-tree時，才想到既然我要找KNN，其實找到第 k 近的鄰居後，就可以用它當pivot快速找出前 k-1 個鄰居（掃陣列一遍而已），可以不用實作kd-tree，執行效果應該還可以接受。事實上Wirth的演算法有個副作用(side effect)，它會更動原來陣列內元素的順序，但妙的是，這個副作用在KNN裡反而省下一次線性搜尋的時間，因為找完第 k 近的鄰居後，前 k 個元素就是 KNN 了 (讀一下code立即可以明白）。

有時候意外地把不同時期學的片段記憶整理一下，串成一個完整的觀念，感覺頗爽的。最棒的是，破碎學到的東西，可以更有系統地重新吸收。

ps.

• 當然，網路上可以找到不少kd-tree的實作code，像Weka裡就有Java版的kd-tree，只是功能太雜，code太長了，以我的小規模用途來說，看懂它的code還不如自己寫快一點。
• 真的建出kd-tree的話，應該會更快，因為kd-tree建一次可以找所有元素的KNN，每個元素找的時間是O(N)，但大部份元素應該不會真的要看N個元素。而Wirth的演算法在找各個元素的KNN時，相當於每個元素重算一次，每個都是Omega(N)。有時間的話真想來比較看看kd-tree能比Wirth快多少。