機器學習之分類算法一：K-近鄰算法

一、K-近鄰算法

    K-近鄰算法是一種分類算法，分類算法是監督學習算法，監督學習算法和無監督學習算法的最大區別就是監督學習需要告訴機器一些正確的事物，也就是訓練數據集，而無監督學習算法則不需要事先準備這些，比如聚類算法。

    所謂的分類，就是要求數據都是離散型（標稱型）的，且是數值型的。一下子 說這么多概念術語很繞彎哈，數據從大的分類來說分為離散型（標稱型）和連續型。離散的就是數據只能在有限的數據集中（比如：是/否，1/2/3，a/b /c，紅/白/黑）,連續型的屬于無限集（比如:全體實數集），對于離散型的適合采用分類器方式也就是分類算法解決，而連續型適合使用線性回歸算法解決， 但這也不是絕對的。

    K-近鄰算法的優點：精度高、對異常值不敏感（個別噪音數據對結果的影響不是很大）；缺點是：計算復雜度高、空間復雜度高（當數據維度變大，矩陣求距離運算相當耗時耗資源）；適用數據范圍：數值型和標稱型（求距離需要要求數據是數值類型）。

    我們就用教材中的例子 簡單說一下該算法的工作原理，假設我有六部電影A（3,104，愛情片）、B（2,100，愛情片）、C（1,81，愛情片）、D（101,10，動作 片）、E（99,5，動作片）、F（98,2.動作片），其中第一個數字代表電影中打斗鏡頭次數、第二個數字代表親吻鏡頭次數，那么現在有一個新電影 G（18,90，？），它屬于愛情片還是動作片呢？其實我們一眼就能判斷出來屬于愛情片！理由呢？

    K-近鄰算法采用的是求距離方式。A(x1,y1,z1)、B(x2,y2,z2)，則d=√(x2-x1)2+(y2-y1)2+(z2-z1)2

    計算結 果為（20.5,18.7,19.2,115.3,117.4,118.9），按距離由小到大排序，所謂的K-近鄰就是選取最相近的K個，比如K=3，也 就是（18.7,19.2,20.5）對應的電影是B、C、A，他們中絕大多數都是愛情片（這里其實全部都是愛情片）。所以我們認為G就是愛情片。

    這就是K-近鄰算法的工作原理。

    下面再把書中給出的一個示例結合代碼給大家說一下怎么去編程。

    假 設我在坐標系中有四個點，分別是（1.0,1.1）、（1.0,1.0）、（0，0）、（0,0.1），這四個點分別是屬于A、A、B、B類別。我們需要 預測（0,0）這個點屬于什么類別，實際上（0,0）已經在已知的訓練數據集中，這沒關系，我們僅僅是做個小測試而已。

    給出的代碼與教材中代碼一致，不過初學者很難看懂每一步都是什么含義，所以我把一些注釋加了上去。具體的運行流程可以參考教材中的步驟。當最終結果返回了“B”，證明我們是對的。