機器學習算法-K近鄰算法
本文中介紹的機器學習中最基礎的一個算法：k-近鄰算法座咆，將從如下方面展開：
算法概述
k近鄰法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一種基本分類與回歸方法募谎。簡單地說竭鞍，k-近鄰算法就是采用不同特征值之間的距離來進行分類抄邀，算法主要特點為：
- 優(yōu)點：精度高宣鄙，對異常值不敏感写烤，沒有數(shù)據(jù)輸入假定
- 缺點：計算復雜度高焰扳，空間復雜度高
- 適用數(shù)據(jù)范圍：數(shù)值型和標稱型（男女）
有人曾經(jīng)統(tǒng)計過很多電影的打斗鏡頭和接吻鏡頭挽荡，如下圖顯示的電影打斗鏡頭和接吻鏡頭：
假設有一部未看過的電影线得，如何確定它是愛情片還是動作片呢？我們看看下表的數(shù)據(jù)：
當我們不知道未知電影史屬于何種類型徐伐，我們可以通過計算未知電影和其他電影的距離贯钩，按照電影的遞增排序，可以找到k個距離最近的電影办素。在距離最近的電影中角雷，選擇類別最多的那部電影，即可判斷為未知電影的類型性穿。
比如k=5勺三，這5部電影中3部是愛情片，2部是動作片需曾，那么我們將未知電影歸屬為愛情片吗坚。
工作原理
- 存在一個樣本數(shù)據(jù)集和數(shù)據(jù)標簽，知道樣本和標簽的對應關系
- 輸入沒有標簽的數(shù)據(jù)呆万，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應的特征進行比較
- 提取樣本集中特征最相似數(shù)據(jù)的分類標簽商源，只選取前
k個最相似的數(shù)據(jù)，一般k是小于20
算法步驟
- 計算已知類別數(shù)據(jù)集中的點與當前點之間的距離谋减；
- 按照距離遞增次序排序牡彻；
- 選取與當前點距離最小的
k個點； - 確定前
k個點所在類別的出現(xiàn)頻率出爹； - 返回前
k個點所出現(xiàn)頻率最高的類別作為當前點的預測分類庄吼。
機器學習中向量距離度量準則
下面??列舉了機器學習中常用的向量距離度量準則：
- 歐式距離
- 曼哈頓距離
- 切比雪夫距離
- 馬氏距離
- 巴氏距離
- 漢明距離
- 皮爾遜系數(shù)
- 信息熵
圖解過程
Python3版本代碼
偽代碼
首先給出KNN算法的偽代碼（對未知類別屬性的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作）：
- 計算已知類別數(shù)據(jù)集中的點和當前點之間的距離
- 按照距離遞增次序排序
- 選取與當前距離最小的k個點
- 確定k個點所在類別的出現(xiàn)頻率
- 返回前k個點出現(xiàn)頻率最高的類別作為當前點的預測分類
Python3實現(xiàn)
下面給出實際的Python3代碼。使用內(nèi)置的collections模塊來解決：
運行上面的代碼严就，顯示的結(jié)果為：
- dist：待預測的電影和已知電影歐式距離
- k_labels：取出排序后前（k=3）3個最小距離的電影對應的類別標簽总寻，結(jié)果是
["動作片","動作片","愛情片"] - label：判斷的結(jié)果是動作片，因為動作片有2票
代碼解釋
1梢为、函數(shù)首先需要生成數(shù)據(jù)集：關于給出的前4部電影渐行，已知打斗次數(shù)和接吻次數(shù)轰坊，同時還有電影的分類情況；
2殊轴、現(xiàn)在新出現(xiàn)了一部電影：打斗次數(shù)是98衰倦，接吻次數(shù)是17，如何確定其屬于哪種類型的電影旁理？
| 打斗次數(shù) | 接吻次數(shù) | 電影分類 | |
|---|---|---|---|
| 1 | 1 | 101 | 愛情片 |
| 2 | 5 | 89 | 愛情片 |
| 3 | 108 | 5 | 動作片 |
| 4 | 115 | 8 | 動作片 |
| 待預測 | 98 | 17 | 樊零？ |
不使用collections模塊如何解決？
classfiy函數(shù)有4個輸入?yún)?shù)：
- 用于分類的輸入向量inX
- 輸入的訓練樣本集合為dataSet
- 標簽向量為labels
- 用于選擇最近鄰居的數(shù)目k
其中標簽向量的元素數(shù)目和矩陣dataSet的行數(shù)相同
看看具體的解釋：
1孽文、原始數(shù)據(jù)是什么樣子驻襟？
打印出來的效果：
2、為什么使用np.tile方法芋哭？
為了和dataSet的shape保持一致沉衣，方便后續(xù)的求距離
3、每個距離和相對的索引關系
Jupyter notebook中使用KNN算法
步驟
下面也是通過一個模擬的電影數(shù)據(jù)來講解如何在jupyter notebook中使用KNN算法减牺，大致步驟分為：
- 構(gòu)建數(shù)據(jù)集
構(gòu)建一個包含接吻鏡頭豌习、打斗鏡頭和電影類型的數(shù)據(jù)集
2、求距離
求出待預測分類的數(shù)據(jù)和原數(shù)據(jù)的歐式距離
3拔疚、距離排序
將求出的距離進行升序排列肥隆，并取出對應的電影分類
4、指定取出前k個數(shù)據(jù)
取出指定的前k個數(shù)據(jù)稚失，統(tǒng)計這些數(shù)據(jù)中電影類型的頻數(shù)栋艳，找出頻數(shù)最多的類型，即可判斷為未知待預測電影的類型
代碼
1句各、模擬數(shù)據(jù)：
2吸占、求解距離
3、對距離升序排列
4凿宾、取出前k個數(shù)并統(tǒng)計頻數(shù)
封裝成函數(shù)
將上面的整個過程封裝成函數(shù)：
import pandas as pd
"""
函數(shù)功能：KNN分類器
參數(shù)說明：
inX：待預測分類的數(shù)據(jù)
dataSet：原數(shù)據(jù)集矾屯，訓練集
k：k-近鄰算法中的超參數(shù)k
返回值：分類結(jié)果
"""
def classify0(inX, dataSet,k):
result = []
# 1、求新數(shù)據(jù)和每個原數(shù)據(jù)的距離
dist = list(((data.iloc[:6,1:3] - new_data) ** 2).sum(1) ** 0.5)
# 2菌湃、將求出的距離和電影標簽放在一起
dist_labels = pd.DataFrame({"dist":dist,"labels":data["電影類型"].tolist()})
# 3问拘、根據(jù)距離升序排列，取出前k個
dist_sorted = dist_labels.sort_values(by="dist")[:k]
# 4惧所、排序之后取出標簽，并統(tǒng)計頻數(shù)
res = dist_sorted.loc[:,"labels"].value_counts()
result.append(res.index[0])
return result
利用上面模擬的數(shù)據(jù)測試一下我們封裝的代碼绪杏，結(jié)果是相同的
參考資料
1下愈、《機器學習實戰(zhàn)》一書
2、機器學習實戰(zhàn)教程（一）：K-近鄰算法（史詩級干貨長文）
3蕾久、《統(tǒng)計學習方法》-李航老師
