第3章 k-近鄰算法

一種常用的分類或回歸算法。

目錄算法內容K值選取距離度量快速檢索實例算法內容給定一個訓練樣本集合以及一個需要進行預測的樣本，k-近鄰算法的思想如下：對于分類問題，k-近鄰算法從所有訓練樣本集合中找到與x最近的k個樣本，然后通過投票法選擇這k個樣本中出現(xiàn)次數(shù)最多的類別作為x的預測結果對于回歸問題，k-近鄰算法同樣找到與x最近的k個樣本，然后對這k個樣本的標簽求平均，得到x的預測結果。算法內容K值選取投票法的準則是少數(shù)服從多數(shù)，所以當k值很小時，得到的結果就容易產生偏差。最近鄰算法是這種情況下的極端，也就是k=1時的k-近鄰算法。最近鄰算法中，樣本x的預測結果只由訓練集中與其距離最近的那個樣本決定。如果k值選取較大，則可能會將大量其它類別的樣本包含進來，極端情況下，將整個訓練集的所有樣本都包含進來，這樣同樣可能會造成預測錯誤。一般情況下，可通過交叉驗證、在驗證集上多次嘗試不同的k值來挑選最佳的k值。距離度量一般對于連續(xù)變量，使用歐式距離直接進行距離度量。對于離散變量，可以先將離散變量連續(xù)化，然后再使用歐式距離進行度量。詞嵌入（Wordembedding）是自然語言處理領域常用的一種對單詞進行編碼的方式。詞嵌入首先將離散變量進行熱獨（one-hot）編碼，假定共有5個單詞{A,B,C,D,E}，則對A的熱獨編碼為，B的熱獨編碼為，其它單詞類似。距離度量編碼后的單詞用矩陣表示為隨機初始化一個用于詞嵌入轉化的矩陣，其中每一個d維的向量表示一個單詞。詞嵌入后的單詞用矩陣表示為距離度量矩陣E中的每一列是相應單詞的詞嵌入表示，d是一個超參數(shù)，M可以通過深度神經網絡在其他任務上進行學習，之后就能用單詞詞嵌入后的向量表示計算內積用以表示單詞之間的相似度。對于一般的離散變量同樣可以采用類似詞嵌入的方法進行距離度量?？焖贆z索當訓練集合的規(guī)模很大時，如何快速的找到樣本x的k個近鄰成為計算機實現(xiàn)k-近鄰算法的關鍵。一個樸素的思想是1) 計算樣本x與訓練集中所有樣本的距離。2) 將這些點依據距離從小到大進行排序選擇前k個。算法的時間復雜度是計算到訓練集中所有樣本的距離的時間加上排序的時間。該算法的第2步可以用數(shù)據結構中的查找序列中前k個最小的數(shù)的算法優(yōu)化，而不必對所有距離都進行排序。快速檢索一個更為可取的方法是為訓練樣本事先建立索引，以減少計算的規(guī)模。kd樹是一種典型的存儲k維空間數(shù)據的數(shù)據結構（此處的k指x的維度大小，與k-近鄰算法中的沒有任何關系）。建立好kd樹后，給定新樣本后就可以在樹上進行檢索，這樣就能夠大大降低檢索k個近鄰的時間，特別是當訓練集的樣本數(shù)遠大于樣本的維度時。實例

基于k-近鄰實現(xiàn)鳶尾花分類本節(jié)以鳶尾花數(shù)據集的分類來直觀理解k-近鄰算法。為了在二維平面展示鳶尾花數(shù)據集，這里使用花萼寬度和花瓣寬度兩個特征進行可視化，如下圖圓形數(shù)據點表示Setosa加號數(shù)據點表示Versicolour乘號數(shù)據點表示Virginica實例

基于k-近鄰實現(xiàn)鳶尾花分類sklearn中提供的k-近鄰模型稱為KNeighborsClassifier，下面給出了模型構造和訓練代碼。實例

基于k-近鄰實現(xiàn)鳶尾花分類用以下代碼對上述模型進行測試。根據程序輸出可以看出，模型在訓練集上的準確率達到0.964，測試集上的準確率達到0.947。實例

基于k-近鄰實現(xiàn)鳶尾花分類下圖展示了模型的決策邊界。可以看出，幾乎所有樣本點都落在相應的區(qū)域之內，只有少數(shù)邊界點可以落在邊界以外。實例

基于k-近鄰實現(xiàn)鳶尾花分類k-近鄰模型默認使用k=5。當k過小時，容易