1 KNN算法介紹

KNN算法又叫做K近鄰算法，是眾多機(jī)器學(xué)習(xí)算法里面最基礎(chǔ)入門的算法。KNN算法是最簡單的分類算法之一，同時，它也是最常用的分類算法之一。KNN算法是有監(jiān)督學(xué)習(xí)中的分類算法，它看起來和Kmeans相似（Kmeans是無監(jiān)督學(xué)習(xí)算法），但卻是有本質(zhì)區(qū)別的。

KNN算法基于實例之間的相似性進(jìn)行分類或回歸預(yù)測。在KNN算法中，要解決的問題是將新的數(shù)據(jù)點分配給已知類別中的某一類。該算法的核心思想是通過比較距離來確定最近鄰的數(shù)據(jù)點，然后利用這些鄰居的類別信息來決定待分類數(shù)據(jù)點的類別。其核心思想為：“近朱者赤近墨者黑”

1.1 KNN算法三要素

• 距離度量算法：一般使用的是歐氏距離。也可以使用其他距離：曼哈頓距離、切比雪夫距離、閔可夫斯基距離等。
• k值的確定：k值越小，模型整體變得越復(fù)雜，越容易過擬合。通常使用交叉驗證法來選取最優(yōu)k值
• 分類決策：一般使用多數(shù)表決，即在 k 個臨近的訓(xùn)練點鐘的多數(shù)類決定輸入實例的類。可以證明，多數(shù)表決規(guī)則等價于經(jīng)驗風(fēng)險最小化

1.2 KNN是一種非參的，惰性的算法模型。

• 非參：并不是說這個算法不需要參數(shù)，而是意味著這個模型不會對數(shù)據(jù)做出任何的假設(shè)，與之相對的是線性回歸總會假設(shè)線性回歸是一條直線。KNN建立的模型結(jié)構(gòu)是根據(jù)數(shù)據(jù)來決定的，這也比較符合現(xiàn)實的情況。
• 惰性：同樣是分類算法，邏輯回歸需要先對數(shù)據(jù)進(jìn)行大量訓(xùn)練，最后會得到一個算法模型。而KNN算法卻不需要，它沒有明確的訓(xùn)練數(shù)據(jù)的過程，或者說這個過程很快。

1.3 KNN算法的優(yōu)缺點

（1）KNN算法具有以下優(yōu)點：

• 簡單易懂：KNN算法的基本思想直觀簡單，易于理解和實現(xiàn)。

• 無需訓(xùn)練過程：KNN算法是一種基于實例的學(xué)習(xí)方法，不需要顯式的訓(xùn)練過程。它直接利用已有的訓(xùn)練數(shù)據(jù)進(jìn)行分類或回歸預(yù)測。

• 適用于多類別問題：KNN算法可以應(yīng)用于多類別問題，不受類別數(shù)目的限制。

• 對于不平衡數(shù)據(jù)集有效：KNN算法在處理不平衡數(shù)據(jù)集時相對較為有效，因為它不假設(shè)數(shù)據(jù)分布的先驗知識。

（2）KNN算法的一些缺點：

• 計算復(fù)雜度高：在進(jìn)行分類或回歸預(yù)測時，KNN算法需要計算待分類數(shù)據(jù)點與所有訓(xùn)練數(shù)據(jù)點之間的距離。當(dāng)訓(xùn)練數(shù)據(jù)集較大時，計算復(fù)雜度會顯著增加。

• 對特征空間維度敏感：KNN算法對于特征空間的維度敏感。當(dāng)特征空間維度較高時，由于所謂的"維度災(zāi)難"，KNN算法的性能可能會下降。在高維數(shù)據(jù)中，距離度量變得不準(zhǔn)確，所有數(shù)據(jù)點都變得離得很遠(yuǎn)，失去了近鄰的意義。

• 需要選擇合適的K值：KNN算法的性能很大程度上取決于選擇合適的最近鄰數(shù)量K。選擇過小的K值可能導(dǎo)致模型過于敏感，容易受到噪聲的影響；選擇過大的K值可能導(dǎo)致模型過于平滑，無法捕捉到細(xì)微的類別特征。

• 不適用于大規(guī)模數(shù)據(jù)集：由于KNN算法需要在預(yù)測階段計算待分類數(shù)據(jù)點與所有訓(xùn)練數(shù)據(jù)點的距離，因此對于大規(guī)模數(shù)據(jù)集來說，存儲和計算的開銷可能會非常大。

KNN算法是一種簡單但強(qiáng)大的分類和回歸方法，適用于多種問題領(lǐng)域。但在使用時需要注意計算復(fù)雜度、維度敏感性、合適的K值選擇以及適應(yīng)大規(guī)模數(shù)據(jù)集的挑戰(zhàn)。

2 KNN算法的應(yīng)用場景

KNN算法的優(yōu)點包括簡單易懂、無需訓(xùn)練過程、適用于多類別問題等。KNN算法在許多領(lǐng)域中都有廣泛的應(yīng)用，KNN算法常見的應(yīng)用場景如下：

• 分類問題：KNN算法可以用于分類問題，如文本分類、圖像分類、語音識別等。通過比較待分類數(shù)據(jù)點與已知數(shù)據(jù)點之間的相似性，KNN可以將新的數(shù)據(jù)點分配到最相似的類別中。

• 回歸問題：KNN算法也可以用于回歸問題，如房價預(yù)測、股票價格預(yù)測等。通過計算最近鄰數(shù)據(jù)點的平均值或加權(quán)平均值，KNN可以預(yù)測待分類數(shù)據(jù)點的數(shù)值屬性。

• 推薦系統(tǒng)：KNN算法可以應(yīng)用于推薦系統(tǒng)，根據(jù)用戶之間的相似性來推薦相似興趣的物品。通過比較用戶之間的行為模式或興趣偏好，KNN可以找到與當(dāng)前用戶最相似的一組用戶，并向其推薦相似的物品。

• 異常檢測：KNN算法可以用于檢測異常數(shù)據(jù)點，如信用卡欺詐、網(wǎng)絡(luò)入侵等。通過計算數(shù)據(jù)點與其最近鄰之間的距離，KNN可以識別與大多數(shù)數(shù)據(jù)點不同的異常數(shù)據(jù)點。

• 文本挖掘：KNN算法可以用于文本挖掘任務(wù)，如文本分類、情感分析等。通過比較文本之間的相似性，KNN可以將新的文本數(shù)據(jù)點歸類到相應(yīng)的類別中。

• 圖像處理：KNN算法可以應(yīng)用于圖像處理領(lǐng)域，如圖像識別、圖像檢索等。通過比較圖像之間的像素值或特征向量，KNN可以識別和檢索相似的圖像。

然而，該算法的缺點是計算復(fù)雜度高，特別是當(dāng)訓(xùn)練數(shù)據(jù)集較大時，需要計算大量的距離。此外，KNN算法對于特征空間的維度敏感，對于高維數(shù)據(jù)的處理可能會出現(xiàn)問題。

針對部分?jǐn)?shù)據(jù)（特征空間維度大，數(shù)據(jù)容量大）為了提高KNN算法的性能，可以使用特征選擇和降維技術(shù)來減少特征空間的維度，以及采用KD樹等數(shù)據(jù)結(jié)構(gòu)來加速最近鄰搜索過程。

KD Tree 是一種平衡二叉樹，目的是實現(xiàn)對 k 維空間的劃分。

KDTree形似二叉搜索樹，其實KDTree就是二叉搜索樹的變種。這里的K = 3(維度).

KD樹的組織原則

將每一個元組按0排序（第一項序號為0，第二項序號為1，第三項序號為2），在樹的第n層，第 n%3 項被用粗體顯示，而這些被粗體顯示的樹就是作為二叉搜索樹的key值，比如，根節(jié)點的左子樹中的每一個節(jié)點的第一個項均小于根節(jié)點的的第一項，右子樹的節(jié)點中第一項均大于根節(jié)點的第一項，子樹依次類推。

對于這樣的一棵樹，對其進(jìn)行搜索節(jié)點會非常容易，給定一個元組，首先和根節(jié)點比較第一項，小于往左，大于往右，第二層比較第二項，依次類推。
?

KD樹檢索

假設(shè)我們的KDTree通過樣本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}創(chuàng)建的。
我們來查找點(2.1,3.1)，在(7,2)點測試到達(dá)(5,4)，在(5,4)點測試到達(dá)(2,3)，然后search_path中的結(jié)點為<(7,2), (5,4), (2,3)>，從search_path中取出(2,3)作為當(dāng)前最佳結(jié)點nearest, dist為0.141 （歐氏距離）；
然后回溯至(5,4)，以(2.1,3.1)為圓心，以dist=0.141為半徑畫一個圓，并不和超平面y=4相交，如下圖，所以不必跳到結(jié)點(5,4)的右子空間去搜索，因為右子空間中不可能有更近樣本點了。
于是在回溯至(7,2)，同理，以(2.1,3.1)為圓心，以dist=0.141為半徑畫一個圓并不和超平面x=7相交，所以也不用跳到結(jié)點(7,2)的右子空間去搜索。
至此，search_path為空，結(jié)束整個搜索，返回nearest(2,3)作為(2.1,3.1)的最近鄰點，最近距離為0.141。

再舉一個稍微復(fù)雜的例子，我們來查找點(2,4.5)，在(7,2)處測試到達(dá)(5,4)，在(5,4)處測試到達(dá)(4,7)，然后search_path中的結(jié)點為<(7,2), (5,4), (4,7)>，從search_path中取出(4,7)作為當(dāng)前最佳結(jié)點nearest, dist為3.202；
然后回溯至(5,4)，以(2,4.5)為圓心，以dist=3.202為半徑畫一個圓與超平面y=4相交，如下圖，所以需要跳到(5,4)的左子空間去搜索。所以要將(2,3)加入到search_path中，現(xiàn)在search_path中的結(jié)點為<(7,2), (2, 3)>；另外，(5,4)與(2,4.5)的距離為3.04 < dist = 3.202，所以將(5,4)賦給nearest，并且dist=3.04。
回溯至(2,3)，(2,3)是葉子節(jié)點，直接平判斷(2,3)是否離(2,4.5)更近，計算得到距離為1.5，所以nearest更新為(2,3)，dist更新為(1.5)
回溯至(7,2)，同理，以(2,4.5)為圓心，以dist=1.5為半徑畫一個圓并不和超平面x=7相交, 所以不用跳到結(jié)點(7,2)的右子空間去搜索。
至此，search_path為空，結(jié)束整個搜索，返回nearest(2,3)作為(2,4.5)的最近鄰點，最近距離為1.5。

?3 基于pytorch在MNIST數(shù)據(jù)集上實現(xiàn)數(shù)據(jù)分類

3.1 獲取MNIST數(shù)據(jù)集

（1）代碼自動下載

train_dataset = datasets.MNIST(root='data',  # 選擇數(shù)據(jù)的根目錄
                            train=True,  # 選擇訓(xùn)練集
                            transform=None,  # 不使用任何數(shù)據(jù)預(yù)處理
                            download=True)  # 從網(wǎng)絡(luò)上下載圖片

test_dataset = datasets.MNIST(root='data',  # 選擇數(shù)據(jù)的根目錄
                           train=False,  # 選擇測試集
                           transform=None,  # 不適用任何數(shù)據(jù)預(yù)處理
                           download=True)  # 從網(wǎng)絡(luò)上下載圖片

但這個自動下載可能會出錯，錯誤如下：

urllib.error.ContentTooShortError: <urlopen error retrieval incomplete: got only 5303709 out of 9912422 bytes>

?（2）手工下載數(shù)據(jù)集

下載地址：MNIST數(shù)據(jù)

下載完成后，放到data/MNIST/raw目錄下

圖片內(nèi)容展示：

digit = train_loader.dataset.data[0] 
plt.imshow(digit, cmap=plt.cm.binary)
plt.show()
print(train_loader.dataset.targets[0])

3.2 KNN計算

以MNIST的60000張圖片作為訓(xùn)練集，通過KNN計算對測試數(shù)據(jù)集的10000張圖片全部打上標(biāo)簽。通過KNN算法比較測試圖片與訓(xùn)練集中每一張圖片，然后將它認(rèn)為最相似的那個訓(xùn)練集圖片的標(biāo)簽賦給這張測試圖片
具體應(yīng)該如何比較這兩張圖片呢？在本例中，比較圖片就是比較28×28的像素塊。最簡單的方法就是逐個像素進(jìn)行比較，最后將差異值全部加起來兩張圖片使用L1距離來進(jìn)行比較。逐個像素求差值，然后將所有差值加起來得到一個數(shù)值。如果兩張圖片一模一樣，那么L1距離為0，但是如果兩張圖片差別很大，那么，L1的值將會非常大。

def KNN_classify(k, dis_func, train_data, train_label, test_data):
    num_test = test_data.shape[0]  # 測試樣本的數(shù)量
    label_list = []
    for idx in range(num_test):
        distances = dis_func(train_data, test_data[idx])
        nearest_k = np.argsort(distances)
        top_k = nearest_k[:k]  # 選取前k個距離
        class_count = {}
        for j in top_k:
            class_count[train_label[j]] = class_count.get(train_label[j], 0) + 1
        sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
        label_list.append(sorted_class_count[0][0])

    return np.array(label_list)

3.3 完整代碼

#!/usr/bin/env python
# coding: utf-8


import operator
import matplotlib.pyplot as plt
import numpy as np
from torchvision import datasets, transforms
from torch.utils.data import DataLoader


batch_size = 100
train_dataset = datasets.MNIST(root='data',  # 選擇數(shù)據(jù)的根目錄
                            train=True,  # 選擇訓(xùn)練集
                            transform=None,  # 不使用任何數(shù)據(jù)預(yù)處理
                            download=True)  # 從網(wǎng)絡(luò)上下載圖片

test_dataset = datasets.MNIST(root='data',  # 選擇數(shù)據(jù)的根目錄
                           train=False,  # 選擇測試集
                           transform=None,  # 不適用任何數(shù)據(jù)預(yù)處理
                           download=True)  # 從網(wǎng)絡(luò)上下載圖片

train_loader = DataLoader(dataset=train_dataset, batch_size=batch_size, shuffle=True)
test_loader = DataLoader(dataset=test_dataset, batch_size=batch_size, shuffle=True)

print("train_data:", train_dataset.data.size())
print("train_labels:", train_dataset.data.size())
print("test_data:", test_dataset.data.size())
print("test_labels:", test_dataset.data.size())


# digit = train_loader.dataset.data[0]  # 取第一個圖片的數(shù)據(jù)
# plt.imshow(digit, cmap=plt.cm.binary)
# plt.show()
# print(train_loader.dataset.targets[0])

# 歐式頓距離計算
def e_distance(dataset_a, data_b):
    return np.sqrt(np.sum(((dataset_a - np.tile(data_b, (dataset_a.shape[0], 1))) ** 2), axis=1))

# 曼哈頓距離計算
def m_distance(dataset_a, data_b):
    return np.sum(np.abs(train_data - np.tile(test_data[i], (train_data.shape[0], 1))), axis=1)


def KNN_classify(k, dis_func, train_data, train_label, test_data):
    num_test = test_data.shape[0]  # 測試樣本的數(shù)量
    label_list = []
    for idx in range(num_test):
        distances = dis_func(train_data, test_data[idx])
        nearest_k = np.argsort(distances)
        top_k = nearest_k[:k]  # 選取前k個距離
        class_count = {}
        for j in top_k:
            class_count[train_label[j]] = class_count.get(train_label[j], 0) + 1
        sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
        label_list.append(sorted_class_count[0][0])

    return np.array(label_list)


def get_mean(data):
    data = np.reshape(data, (data.shape[0], -1))
    mean_image = np.mean(data, axis=0)
    return mean_image


def centralized(data, mean_image):
    data = data.reshape((data.shape[0], -1))
    data = data.astype(np.float64)
    data -= mean_image  # 減去圖像均值，實現(xiàn)領(lǐng)均值化
    return data


if __name__ == '__main__':
    # 訓(xùn)練數(shù)據(jù)
    train_data = train_loader.dataset.data.numpy()
    train_data = train_data.reshape(train_data.shape[0], 28 * 28)
    
    # 歸一化處理
    mean_image = get_mean(train_data)  # 計算所有圖像均值
    train_data = centralized(train_data, mean_image)
    
    print('train_data shape:', train_data.shape)
    train_label = train_loader.dataset.targets.numpy()
    print('train_lable shape', train_label.shape)

    # 測試數(shù)據(jù)
    test_data = test_loader.dataset.data[:1000].numpy()
    test_data = centralized(test_data, mean_image)
    test_data = test_data.reshape(test_data.shape[0], 28 * 28)
    print('test_data shape', test_data.shape)
    test_label = test_loader.dataset.targets[:1000].numpy()
    print('test_label shape', test_label.shape)

    # 訓(xùn)練
    test_label_pred = KNN_classify(5, e_distance, train_data, train_label, test_data)

    # 得到訓(xùn)練準(zhǔn)確率
    num_test = test_data.shape[0]
    num_correct = np.sum(test_label == test_label_pred)
    print(num_correct)
    accuracy = float(num_correct) / num_test
    print('Got %d / %d correct => accuracy: %f' % (num_correct, num_test, accuracy))

3.4 計算結(jié)果展示

train_data: torch.Size([60000, 28, 28])
train_labels: torch.Size([60000, 28, 28])
test_data: torch.Size([10000, 28, 28])
test_labels: torch.Size([10000, 28, 28])
train_data shape: (60000, 784)
train_lable shape (60000,)
test_data shape (1000, 784)
test_label shape (1000,)
963
Got 963 / 1000 correct => accuracy: 0.963000

使用歐氏距離計算，最終結(jié)果準(zhǔn)確率達(dá)到了96.3%

4 完整工程及數(shù)據(jù)下載

下載地址：代碼和數(shù)據(jù)文章來源地址http://www.zghlxwxcb.cn/news/detail-718443.html

到了這里，關(guān)于機(jī)器學(xué)習(xí)之KNN(K近鄰)算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！