kNN 演算法的 SQL 實現

在 2008 年尾的時候，讀到一本非常有趣的書，叫做《Data Mining With SQL Server 2008》. 在遇到《Inside Sql Server》系列前夕，此時正值讀書的空檔期。為什麼會對這本書感興趣呢，畢竟是作為農學畢業的我，八竿子也打不到 Data Mining 的領域去，主要還是對於前途的擔憂。這話題說來，估計長的可以寫篇小說了。咱們不賣焦慮，所以簡而言之：做了兩年 C/S 的開發之後，深深感到數據才是靈魂，而這靈魂的操盤手，普天之下，Data Mining 穩穩得排在江湖兵器譜第一位！

在堅持了兩個月的研究之後，（為什麼這麼久，只有英語六級水平的人，看純英文版還是很吃力，當時這本書還沒中文本），搗鼓了一點彩票數據進 SQL Server Cube ，以為靠著深奧萬能的模型，從此可以財富自由，一時間豪氣四射，信心倍增，連蛋餅都加 2 個蛋的，後來才知其實那只是黃粱一夢。

在萬惡的資本思想驅使下，一遍遍修鍊決策樹，聚類，神經網路，貝葉斯模型， 每一遍都用真金白銀去豪賭（2 塊錢一注，當時月薪 1200 吧，所以真是豪賭），收穫的卻是一遍遍的失望，那時的心，就像 911 下的五角大樓一樣，崩塌在即。直到把聚類的模型統統走完，一次都沒中！從此，Data Mining 與我是路人。

十年過來了，如今大火的數據挖掘，又加上了新玩法，美其名曰機器學習，人工智慧，深度學習等。再和朋友們談論的時候，閉口不談大數據，AI， ML, 大家都會帶著異樣的眼光看著你，「你丫也是在 IT 圈混的？」... 所以重新拾起來看看，與時俱進。其實內心的回答是，「08 年小哥我開始玩 Weka 的時候，你們連 Oracle 都不會玩吧，還談大數據，AI」

言歸正傳，今天的主題是 kNN ( top k nearest ) 最近鄰演算法。參考的書目是兩本《機器學習實戰》(Peter 著)與《機器學習》(周志華著). 這兩本書各有其優點，《實戰》這本書對於 Python 代碼實現演算法講的比較多，讓你很容易就寫出一個模型來完成一次實戰，跟玩王者一樣的，反饋很及時，而周志華教授的這本《機器學習》則是講的比較細緻了，用的是挑西瓜的例子，很有趣味。當然 Peter 這本書用的還是 Python 2.0 , 我費了很大的勁兒，才轉成 Python 3.0 的語法，以下的例子會有註解， 而周教授的這本書，則是沒有數學底子根本看不懂在講啥，碰到 kNN , 會跟你詳細解釋權重，概率，線性矩陣，有多少種求解最短距離的演算法等，很開眼界，讓我瞬間覺得我活著都是在浪費社會資源。

用一幅圖來講解 kNN, 可以讓你瞬間秒懂：

圖中的五角星，就是我們待分類的數據。與他最近的 k 個圓點所代表的類別，比重最大的就是預測數據的類別。求解方式很簡單，在 2 個屬性下，就是求解直三角形斜邊的長度，勾股定理一算就出來了。如果在多個屬性下，也就是將各自之差的平方相加，再求根，就得到最短距離

Peter 書中採用了婚戀網的匹配推薦項目來演示 kNN。採用的特徵分別是：

1 每年的飛行里程

2 每天玩視頻遊戲所佔的時間份額

3 每周吃掉的冰激凌分量

根據這三個特徵，收集了近1000個打分結果，來判斷約會雙方對彼此的影響，是不喜歡，喜歡還是極度渴望約會。

求解 kNN 的核心代碼的代碼，經過 Python 3.0 修改 之後，如下：

模型做出來了，我們就用劃分為測試用例的數據做預測，觀察其正確率：

最後得到的誤差是4%，模型可以用來預測分類。只要拿到一個對象的這三個特徵，就能得到他/她是否能得到大家的喜歡，而這個結果有 96% 的準確性。

為了更好的了解這個功能，用 MatPlotLib 做了一個圖，圖中面積最大的那些點，就是最受喜歡的那群人，他們的特徵在某些方面具有奇高的重疊

氣泡圖在 Python 的 MatPlotLib 下實現也非常容易：

那麼如何用 SQL 實現呢，kNN 的演算法是所有演算法中最簡單的一個，只要對原理掌握了，不過是把 Python 換成了 SQL。當然這兩者在如今的數據量環境下，都不是好的實現語言，必須與 Spark , Hadoop 等分散式存儲於計算環境結合起來，方能全量無死角的洞悉信息。

以下是兩張數據表，第一張 datingSampleDataSet 就是收集好的數據其中的900條，第二張 datingTestingDataSet 是從收集好的數據中取出來的 100 條，因這份數據已經有喜好的分類了，因此可以作為誤差的計算.

select *

from dbo.datingSampleDataSet

select *

from dbo.datingTestingDataSet

在 SQL 的實現過程中，我們用一個函數來求解預測值的分類，再來判斷函數的誤差。最後得到的誤差和 Python 實現的一樣，都是 4%。

（最近的 Github 被微軟收購了，好像有點抽風，因此源代碼暫時也放不出來，如果實在想看的話，點贊留言吧，我同步到 Github 上之後會通知到大家）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！