數據分析與數據挖掘 - 09鄰近算法

數據分析與數據挖掘 – 09鄰近算法

2020 年 10 月 2 日
筆記
數據分析

一鄰近算法的基本介紹

1 基本說明

鄰近算法又叫做K臨近算法或者KNN(K-NearestNeighbor)，是機器學習中非常重要的一個算法，but它簡單得一塌糊塗，其核心思想就是樣本的類別由距離其最近的K個鄰居投票來決定。現在假設我們已經有一個已經標記好的數據集，也就是說我們已經知道了數據集中每個樣本所屬於的類別。這個時候我們擁有一個未標記的數據樣本，我們的任務是預測出來這個數據樣本所屬於的類別。顯然鄰近算法是屬於監督學習(Supervised Learning)的一種，它的原理是計算這個待標記的數據樣本和數據集中每個樣本的距離，取其距離最近的k個樣本，那麼待標記的數據樣本所屬於的類別，就由這距離最近的k個樣本投票產生。在這個過程中，有一個動作是標記數據集，這一點在企業中一般是有專門人來負責標記數據的。

2 舉例說明

為了更加直觀的了解鄰近算法，請看下面的例子。有兩種水果長得非常像，一個是菠蘿，另一個是鳳梨，很長一段時間我都以為它們是同一種水果。

菠蘿與鳳梨的核心區別是菠蘿的葉子有刺，而鳳梨的葉子沒有刺。菠蘿的凹槽處的顏色是黃色，而鳳梨的凹槽處的顏色是綠色。首先我們把這兩種水果抽取出其中的兩個特點(凹槽處的顏色、葉子上是否有刺)後，放入一個直角坐標系中吧。如下圖：

我們按照兩種水果的特點，已經把它們放在了直角坐標系中，按照我們所說的算法原理，此時有一個未標記的樣本，我們來預測這個樣本到底是屬於哪種水果。如下圖，這個時候來了一個未標記的樣本，也就是不知道是什麼類別的水果。

在原理中，我們說過，由其最近的K個鄰居來投票決定，這個未標記的水果到底是什麼水果，那麼這個時候，我們把K的值設置為3，如下圖:

從圖片中，我們看到，在K的值為3的時候，與未標記樣本最近的3個鄰居其中2個為菠蘿，而1個為鳳梨，那麼這個時候我們預測這個未知的水果為菠蘿。

3 偽代碼說明

我們先來看一下如何用偽代碼來實現這個算法，這樣我們在後邊的學習中才能更好的寫出來這段代碼。

第一步，我們設x_test為待標記的數據樣本，x_train為已標記的數據集。
第二步，遍歷x_train中的所有樣本，計算每個樣本與x_test的距離，並把距離保存在distance數組中。
第三步，對distance數組進行排序，取距離最近的k個點，標記為x_knn。
第四步，在x_knn中統計每個類別的個數，即class0(類別0)在x_knn中有幾個樣本，class1 (類別1)在x_knn中有幾個樣本。
第五步，待標記樣本的類別，就是x_knn中樣本個數最多的那個類別。

4 優缺點分析

優點：準確性高，對異常值有較高的容忍度，原因是異常值會單獨分佈在坐標系的一個角落，取k個鄰居的時候大概率失去不到這個異常值的。
缺點：計算量大，對內存的需求也大，因為它每次對一個未標記的樣本進行分類的時候，都需要全部計算一下距離。
關鍵點：k值的選取，首先k值一定是奇數，這樣可以確保兩個類別的投票不會一樣，其次，k值越大，模型的偏差越大，對於噪聲數據（錯誤數據或異常數據）越不敏感，k值太小就會造成模型的過擬合。

二鄰近算法的代碼練習

1 準備數據

# 從sklearn庫中的數據集對象里導入樣本生成器中的make_blobs方法幫助我們生成數據
from sklearn.datasets.samples_generator import make_blobs

# 聲明三個直角坐標系中的位置
centers = [[-2, 2], [2, 2], [0, 4]]

# 生成數據,其中n_samples是生成數據的個數，centers是中心點，cluster_std是標準差，指明離散程度
x, y = make_blobs(n_samples=60, centers=centers, cluster_std=0.6)

# x是生成的數據，y是不同的數據對應所屬的的類別0，1，2
print(x, y)

2 用圖形來幫助理解

import matplotlib.pyplot as plt
import numpy as np

plt.figure(figsize=(16, 10), dpi=144)
c = np.array(centers)
# x軸，y軸，c顏色  s指定點的大小
plt.scatter(x[:, 0], x[:, 1], c=y, s=100, cmap="cool")
# 畫出中心點
plt.scatter(c[:, 0], c[:, 1], s=100, marker="^", c="orange")
plt.show()

圖形顯示如下圖所示：

圖形中顯示的三個三角形的點就是中心點，圍繞在它們周圍的圓點就是我們隨機生成的數據的點。

3 KNN算法對數據的訓練

# 從sklearn庫中導入K鄰居分類器：KNeighbosrClassifier
from sklearn.neighbors import KNeighborsClassifier

# 設定K值
k = 5

# 聲明k臨近分類器對象
clf = KNeighborsClassifier(n_neighbors=k)

# 訓練模型
clf.fit(x, y)

4 預測樣本數據

# 定義樣本數據
x_sample = [[0, 2]]
# 使用模型進預測
neighbors = clf.kneighbors(x_sample, return_distance=False)
print(neighbors)

# 輸出值:[[23 39 21 47 29]]

x_sample變量是我們要進行預測的樣本，然後使用clf.kneighbors方法就可以對這個樣本進行預測了。關於clf.kneighbors的參數return_distance，它決定了是否返回計算後的距離，默認是True，這裡我把它修改成了False，你如果想要看一下值為True是什麼樣子，可以自己手動修改為True。到這裡你可以有一點懵，這怎麼就預測完成了呢？輸出值表示的是什麼意思呢？

輸出值表示的是5個經過計算之後的位於x訓練集中的索引值，它們並不是直接的位置。

5 畫出預測的結果

為了能夠使預測的結果更加直觀，我們還需要用代碼把他們畫出來。

# 把帶預測的樣本以及和其最近的5個點標記出來
plt.figure(figsize=(8, 5), dpi=144)  # dpi是像素值
plt.scatter(x[:, 0], x[:, 1], c=y, s=100, cmap='cool')  # 樣本數據
plt.scatter(c[:, 0], c[:, 1], s=100, marker='^', c='k')  # 中心點

# 帶預測的點
plt.scatter(x_sample[0][0], x_sample[0][1], marker='x', s=100, cmap='cool')

# 把預測點與距離最近的5個樣本連成線
for i in neighbors[0]:
    plt.plot([x[i][0], x_sample[0][0]], [x[i][1], x_sample[0][1]], 'k--', linewidth=0.6)

plt.show()

顯示結果如下圖所示：

三花卉識別項目練習

1 先認識三朵花

在這一小節我們將通過一個花卉識別項目的練習來鞏固我們所講的KNN算法，訓練數據集是非常著名的鳶尾花數據集，涉及到的花的種類一共分為三種：

第一種花是山鳶尾，長下面這個樣子

第二種花是錦葵，也叫虹膜錦葵

第三種花是變色鳶尾

2 導入數據集

我們可以通過sklearn庫的自帶數據集直接引入鳶尾花的數據集，在這個數據集中，我們可以通過花萼長度，花萼寬度，花瓣長度和花瓣寬度四個屬性來預測未標記的鳶尾花屬於哪個類別。

# 1 導入鳶尾花數據集
from sklearn.datasets import load_iris

# 2 聲明一個鳶尾花的類對象
iris = load_iris()

# 3 獲取鳶尾花的數據
iris_data = iris.data

# 4 獲取數據對應的種類
iris_target = iris.target

print(iris_data)
print(iris_target)

查看數據後你會看到iris_data變量里每一個元素一共有4個值，這四個值就是分別對應花萼長度、花萼寬度、花瓣長度、花瓣寬度4個屬性，iris_target變量對應的就是每一個花所屬的類別。一共對應的是3個類別，0的意思是山鳶尾，1是虹膜錦葵，2是變色鳶尾。

3 訓練模型

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split  # 分割訓練集和測試集
from sklearn.neighbors import KNeighborsClassifier

iris = load_iris()
iris_data = iris.data
iris_target = iris.target

# 把數據分為訓練集和測試集，x表示特徵值，y表示目標值，test_size=0.25表示將25%的數據用作測試集
x_train, x_test, y_train, y_test = train_test_split(iris_data, iris_target, test_size=0.25)

# 創建KNN算法實例，n_neighbors參數默認為5，後續可以通過網格搜索獲取最優參數
knn = KNeighborsClassifier(n_neighbors=5)

# 訓練測試集數據
knn.fit(x_train, y_train)

# 獲取預測結果
y_predict = knn.predict(x_test)

# 展示預測結果
labels = ['山鳶尾', '虹膜錦葵', '變色鳶尾']
for i in range(len(y_predict)):
    print('第%d次測試：預測值：%s 真實值：%s' %((i + 1), labels[y_predict[i]], labels[y_test[i]]))
print('準確率：', knn.score(x_test, y_test))

4 獲取k值最優參數

k值選取的思路是我們先來選擇一個k值的範圍，把這個範圍中所有的誤差值都獲取到，然後我們再來選擇誤差最小的值作為k值。

from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt

# 中文顯示
plt.rcParams["font.family"] = 'Arial Unicode MS'

# 導入數據集
iris = load_iris()
x = iris.data
y = iris.target

# 限制k的取值範圍
k_range = range(1, 31)

# 記錄每當k值變換一次，它的錯誤值是多少
k_error = []


for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    
    # cv參數決定數據集劃分比例，這裡按照5:1劃分訓練集和測試集
    scores = cross_val_score(knn, x, y, cv=6)
    print(scores)
    
    k_error.append(1 / scores.mean())

# 把結果畫成圖，直觀看出k取什麼值誤差最小，x軸為k值，y軸為誤差值
plt.plot(k_range, k_error)
plt.xlabel('k值')
plt.ylabel('誤差值')
plt.show()

圖形顯示結果如下圖所示：

根據這個圖形我們就可以看得出來，k值大概是在12這個位置時，誤差是最小的。這時當我們把12重新放入到之前的代碼中，可能你會發現他的準確率並沒有提升甚至還有可能下降了，其實是因為數據量比較小的緣故，並不影響我們解決問題的方式。

四 KNeighborsClassifier參數詳解

通過前面的練習，相信你已經基本掌握了KNeighborsClassifier的使用方法了，最後，在這裡我們會對這個方法的參數進行更細緻的說明和講解。

# 查看KNeighborsClassifier源代碼
NeighborsClassifier(
    n_neighbors=5,
    weights="uniform」,
    algorithm=」auto「,
    leaf_size=30,
    p=2,
    metric="minkowski",
    metric_params=None,
    n_jobs=None,
    **kwargs,
)

weights用於指定臨近樣本的投票權重，默認是uniform，表示所有鄰近樣本投票權重都是一樣的。如果我們把weights的值設置成distance，表示投票權重與距離成反比，也就是說鄰近樣本與未知類別樣本距離越遠，則其權重越小，反之，權重越大。
algorithm用於指定鄰近樣本的搜尋方法，如果值為ball_tree，表示用球樹搜尋法尋找近鄰樣本，kd_tree就是KD樹搜尋法，brute是使用暴力搜尋法。algorithm默認參數是auto，表示KNN算法會根據數據特徵自動選擇最佳搜尋方法。關於這些搜尋法的細節，我會在未來發佈的機器學習的文章中做詳細的說明，現在只需要知道我們當前用的是默認的自動幫我們選擇的搜尋方法。
leaf_size用於指定球樹或者KD樹葉子節點所包含的最小樣本量，它用於控制樹的生長條件，會影響查詢速度，默認值是30，目前我們先不關注這個點。
metric參數是用來指定距離的度量指標，默認為閔可夫斯基距離。
p參數是依賴metric參數生效的，當metric為minkowski距離時，p=1表示計算點之間的曼哈頓距離，p=2表示計算點之間的歐式距離，默認值為2，計算歐式距離。
metric_params是一個字典，默認值為空，它為metric參數所對應的距離指標添加關鍵字參數。
n_jobs設置KNN算法並行計算時所需的CPU數量，默認值為1，表示僅使用一個CPU運行算法，也就是不開啟並行運算。

同樣的，最後我們會有一個小的練習，請點擊下方鏈接下載：
chapter9-1.zip

Tags: 數據分析