機器學習中分類演算法之K近鄰分類

物以類聚，人以群分，相似的東西很可能具有相似的屬性。利用這個原理，我們可以對數據進行分類，將其劃分到最相近的類別或者最接近的鄰居。本期給大家分享機器學習中五種常見分類演算法之一：K近鄰（K-Nearest Neighbors，KNN）。

近鄰分類器就是把未標記的案例歸類為與它們最相似的帶有標記的案例所在的類，其特點可歸納為如下：

①從技術上來說，沒有抽象化的步驟；

②訓練階段進行得較快，預測的過程往往相對較慢；

③高度依賴於訓練案例，又稱為基於案例的學習（instance-based learning）或機械學習（rote learning）；

④允許學習演算法發現數據中的自然模式，但不會試圖將數據擬合為一個預先設定的形式，即不會建立模型，因而屬於非參數學習方法。

雖然近鄰分類器被認為是「懶惰」學習器，但其功能極其強大，已成功運用於計算機模式識別、基因數據模式識別、癌症的自動化篩查等領域。

簡單地說，KNN演算法就是，對於測試集中每一條記錄，確定訓練集中與該記錄相似度「最近」的k條記錄，其中k是一個預先指定的整數，未標記的測試實例被分配到k個近鄰中佔比最大的那個類中。

例如：指定k=5，對於一個新的待分類對象，其有3個近鄰在A類，1個在B類，1個在C類，則A佔比最大為3/5，該對象就被分到A類。

由上面的定義我們發現需要解決兩大問題：

其一，如何衡量相似度？

傳統上KNN演算法採用的是歐氏距離(Euclidean distance)，度量最短的直線距離。假設p和q是待比較的案例，各自有n個特徵，分別為(p1,p2,…,pn)和(q1,q2,…,qn)，則歐氏距離公式如下：

另外一些常見的距離度量有：曼哈頓距離(Manhattan distance)，最大距離(Maximum distance)，堪培拉距離(Canberra distance)，二項距離(Binary distance)，閔可夫斯基距離(Minkowski distance)。

其二，如何選擇一個合適的k？

確定鄰居數量將決定把模型推廣到未來數據時分類性能的好壞，選擇一個大的k會減少雜訊導致的模型波動，但會使得分類器產生偏差，舉一個極端的例子：k等於訓練集中案例條數，由於每一個案例都會在最終的投票表決中出現，所以最常見的訓練類總會獲得大多數的票。選擇較小的k則可以更精細地擬合訓練數據，但會使得雜訊數據或異常值過度影響案例的分類，也即方差較大，舉一個極端的例子：k=1時的單一近鄰，如果一些訓練案例被意外地貼錯了標籤，而待分類的案例恰好最接近被錯誤標記的訓練案例，那麼它就會被分到錯誤的類別中。

因而，過度擬合和低度擬合訓練數據之間的平衡問題稱為偏差-方差權衡(bias-variance tradeoff)，通常k取值在3~10之間，常見的做法是令k等於訓練集中案例數量的平方根；另一種做法是基於各種測試集來測試選取可以提供最佳分類性能的k值。有研究者稱，「更大的、更具有代表性的訓練集可以使得k值選擇並不那麼重要」，然而正如本號之前的一篇文章「樣本量達到多少才算大？」所探討的，「夠大、夠代表性」很難界定，小編認為最好還是通過測試集來選取k值。

其實還有一個潛在的問題需要解決，即數據準備。

在應用KNN演算法之前，通常將特徵轉換到一個標準的範圍內，由上述公式我們也可以看出，如果某個特徵的值相較於其他特徵很大，則距離的度量會強烈地被這個特徵的值所支配。

轉換方法常見有兩種：

(1)min-max標準化，使所有值落在0-1範圍內:

(2)z-score標準化:

對於特徵是名義變數的，則需要事先啞元化。

實例演練

1.數據準備

數據集包括569例細胞活檢案例，第一列為病人ID編號，第二列為癌症診斷結果，其他30個特徵是數值型的實驗室測量結果。癌症診斷結果用M表示惡性，B表示良性。

#設置工作目錄

setwd("D:\學海拾貝之統計\數據源")

#讀取數據

data=read.delim("wisc_bc_data.txt",sep=",",header=F)

#查看數據條目

str(data)

#重命名數據集

names(data)=c("id","diagnosis",paste0("v",seq(1:30)))

#查看良惡性案例的大致分布

table(data$diagnosis)

#將診斷結果轉化為因子並為其賦予標籤

data$diagnosis=factor(data$diagnosis,levels=c("B","M"),labels=c("Benign","Malignant"))

#將30個特徵數據標準化

install.packages("chipPCR")

library(chipPCR)

#可將「minm」換成「zscore」

standardize=function(x)data_n=as.data.frame(lapply(data[,c(3:32)],standardize))

summary(data_n)

#選取前469行案例作為訓練集，後100例作為測試集，實際操作應隨機選取

train=data_n[1:469, ]

test=data_n[470:569, ]

train_labels=data[1:469,2]

test_labels=data[470:569,2]

2.訓練模型並預測

#安裝class添加包並調用

install.packages("class")

library(class)

#使用knn( )函數來給測試集分類，這裡k選取469開平方的近似值21

test_pred=knn(train=train,test=test,cl=train_labels,k=21)

3.評估模型性能

install.packages("gmodels")

library(gmodels)

CrossTable(x=test_labels,y=test_pred,prop.chisq=F)

結果如下：

僅有2%的案例被分錯，幾行代碼即可達到98%的準確度，你難道不想拿你的數據試試么？

4.提高模型性能

①改用不同的數據標準化方法，如：z-score轉換；

②測試其他k值。

這裡不再探討細化，有待感興趣的童鞋來探索！

參考文獻：

【1】http://archive.ics.uci.edu/ml/index.php

【2】BrettLantz,蘭茲,李洪成,等.機器學習與R語言[M].機械工業出版社, 2015.

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