KNN(K近鄰)算法實(shí)現(xiàn)紅酒聚類(lèi)

K近鄰算法，是有監(jiān)督學(xué)習(xí)中的分類(lèi)算法，可以用于分類(lèi)和回歸，本篇主要講解其在分類(lèi)上的用途。

算法原理

KNN算法雖然是機(jī)器學(xué)習(xí)算法，但是他不學(xué)習(xí)，他的原理是把所有的訓(xùn)練集都存儲(chǔ)下來(lái)，在測(cè)試的時(shí)候把測(cè)試集放到原圖里面，根據(jù)測(cè)試點(diǎn)和訓(xùn)練集的距離判定屬于的類(lèi)別。如下圖示例，假設(shè)我們現(xiàn)在有兩個(gè)類(lèi)別，分別是A和B，用三角和圓圈（不太圓見(jiàn)諒）表示，我們把這兩種類(lèi)別都畫(huà)在坐標(biāo)系中。此時(shí)載入一個(gè)未知類(lèi)別方框，我們的KNN算法就開(kāi)始了。

首先我們要指定一個(gè)K值，K值就是距離值，比如我們先指定K=2，就可以在這個(gè)位置類(lèi)別周?chē)?huà)一個(gè)圓（可以理解為半徑為2），如下圖：

此時(shí)我們這個(gè)圓框進(jìn)去了兩個(gè)A類(lèi)別，根據(jù)算法原理，此時(shí)就會(huì)把這個(gè)未知類(lèi)別判斷為A類(lèi)別。而如果我們擴(kuò)大K值呢

當(dāng)我們把K值從2擴(kuò)大到4時(shí)（小圓外面的大圓），可以看到，此時(shí)包進(jìn)來(lái)了4個(gè)B類(lèi)別值，A類(lèi)別值仍然只有2個(gè)，此時(shí)就會(huì)判斷為B類(lèi)別。這個(gè)算法有一點(diǎn)劃地盤(pán)的意思，畫(huà)個(gè)圈，這圈里誰(shuí)人多，你就跟誰(shuí)走，是這意思。歪理原理就這么結(jié)束了，下面讓我們看看正經(jīng)的解釋。

K近鄰算法（K-Nearest-Neighbor, KNN）是一種用于分類(lèi)和回歸的非參數(shù)統(tǒng)計(jì)方法，最初由 Cover和Hart于1968年提出(Cover等人,1967)，是機(jī)器學(xué)習(xí)最基礎(chǔ)的算法之一。它正是基于以上思想：要確定一個(gè)樣本的類(lèi)別，可以計(jì)算它與所有訓(xùn)練樣本的距離，然后找出和該樣本最接近的k個(gè)樣本，統(tǒng)計(jì)出這些樣本的類(lèi)別并進(jìn)行投票，票數(shù)最多的那個(gè)類(lèi)就是分類(lèi)的結(jié)果。KNN的三個(gè)基本要素：

• K值，一個(gè)樣本的分類(lèi)是由K個(gè)鄰居的“多數(shù)表決”確定的。K值越小，容易受噪聲影響，反之，會(huì)使類(lèi)別之間的界限變得模糊。
• 距離度量，反映了特征空間中兩個(gè)樣本間的相似度，距離越小，越相似。常用的有Lp距離（p=2時(shí)，即為歐式距離）、曼哈頓距離、海明距離等。
• 分類(lèi)決策規(guī)則，通常是多數(shù)表決，或者基于距離加權(quán)的多數(shù)表決（權(quán)值與距離成反比）。

預(yù)測(cè)算法（分類(lèi)）的流程如下：

（1）在訓(xùn)練樣本集中找出距離待測(cè)樣本x_test最近的k個(gè)樣本，并保存至集合N中；

（2）統(tǒng)計(jì)集合N中每一類(lèi)樣本的個(gè)數(shù)𝐶𝑖,𝑖=1,2,3,…,𝑐𝐶𝑖,𝑖=1,2,3,…,𝑐；

（3）最終的分類(lèi)結(jié)果為argmax𝐶𝑖𝐶𝑖 （最大的對(duì)應(yīng)的𝐶𝑖𝐶𝑖）那個(gè)類(lèi)。

在上述實(shí)現(xiàn)過(guò)程中，k的取值尤為重要。它可以根據(jù)問(wèn)題和數(shù)據(jù)特點(diǎn)來(lái)確定。在具體實(shí)現(xiàn)時(shí)，可以考慮樣本的權(quán)重，即每個(gè)樣本有不同的投票權(quán)重，這種方法稱(chēng)為帶權(quán)重的k近鄰算法，它是一種變種的k近鄰算法。

數(shù)據(jù)下載

我們使用Wine數(shù)據(jù)集進(jìn)行展示，Wine數(shù)據(jù)集的官網(wǎng)：Wine Data Set，這個(gè)數(shù)據(jù)集是對(duì)同一地區(qū)三個(gè)不同品種的葡萄酒進(jìn)行化學(xué)分析后記錄的結(jié)果。數(shù)據(jù)集分析了三種葡萄酒中每種所含13種成分的量。這些13種屬性是

1. Alcohol，酒精
2. Malic acid，蘋(píng)果酸
3. Ash，灰
4. Alcalinity of ash，灰的堿度
5. Magnesium，鎂
6. Total phenols，總酚
7. Flavanoids，類(lèi)黃酮
8. Nonflavanoid phenols，非黃酮酚
9. Proanthocyanins，原花青素
10. Color intensity，色彩強(qiáng)度
11. Hue，色調(diào)
12. OD280/OD315 of diluted wines，稀釋酒的OD280/OD315
13. Proline，脯氨酸

可以采用兩種下載方式：

• 方式一，從Wine數(shù)據(jù)集官網(wǎng)下載wine.data文件。
• 方式二，從華為云OBS中下載wine.data文件。

此時(shí)我們默認(rèn)已經(jīng)安裝了Mindspore環(huán)境，采用從華為云OBS中下載數(shù)據(jù)集

from download import download# 下載紅酒數(shù)據(jù)集
url = "https://ascend-professional-construction-dataset.obs.cn-north-4.myhuaweicloud.com:443/MachineLearning/wine.zip"  
path = download(url, "./", kind="zip", replace=True)

數(shù)據(jù)讀取與處理

數(shù)據(jù)下載下來(lái)了，我們就進(jìn)行讀取和預(yù)處理唄。

%matplotlib inline
import os
import csv
import numpy as np
import matplotlib.pyplot as pltimport mindspore as ms
from mindspore import nn, opsms.set_context(device_target="CPU")

with open('wine.data') as csv_file:data = list(csv.reader(csv_file, delimiter=','))
print(data[56:62]+data[130:133])

執(zhí)行完這幾行代碼后我們會(huì)打印出來(lái)部分?jǐn)?shù)據(jù)進(jìn)行查看，比如我這里打印出這樣的數(shù)據(jù)

此時(shí)最開(kāi)始的每個(gè)list最開(kāi)始的第一個(gè)數(shù)都是1或2或3，這就是葡萄酒的三種類(lèi)別，后面緊跟著的13個(gè)參數(shù)就是他的13種化學(xué)成分。

取三類(lèi)樣本（共178條），將數(shù)據(jù)集的13個(gè)屬性作為自變量X，將數(shù)據(jù)集的3個(gè)類(lèi)別作為因變量Y。此時(shí)X和Y的值可以自行打印查看

X = np.array([[float(x) for x in s[1:]] for s in data[:178]], np.float32)
Y = np.array([s[0] for s in data[:178]], np.int32)

取樣本的某兩個(gè)屬性進(jìn)行2維可視化，可以看到在某兩個(gè)屬性上樣本的分布情況以及可分性。

attrs = ['Alcohol', 'Malic acid', 'Ash', 'Alcalinity of ash', 'Magnesium', 'Total phenols','Flavanoids', 'Nonflavanoid phenols', 'Proanthocyanins', 'Color intensity', 'Hue','OD280/OD315 of diluted wines', 'Proline']
plt.figure(figsize=(10, 8))
for i in range(0, 4):plt.subplot(2, 2, i+1)# 選擇的化學(xué)成分由循環(huán)輪數(shù)i決定a1, a2 = 2 * i, 2 * i + 1# 選擇前59個(gè)類(lèi)別為1的數(shù)據(jù)，化學(xué)成分選a1和a2類(lèi)plt.scatter(X[:59, a1], X[:59, a2], label='1')plt.scatter(X[59:130, a1], X[59:130, a2], label='2')plt.scatter(X[130:, a1], X[130:, a2], label='3')plt.xlabel(attrs[a1])plt.ylabel(attrs[a2])plt.legend()
plt.show()

這里執(zhí)行完了就可以看到四張打印出來(lái)的圖，就體現(xiàn)了每一類(lèi)葡萄酒其中兩種化學(xué)成分的關(guān)系

將數(shù)據(jù)集按128:50劃分為訓(xùn)練集（已知類(lèi)別樣本）和驗(yàn)證集（待驗(yàn)證樣本）：

train_idx = np.random.choice(178, 128, replace=False)
test_idx = np.array(list(set(range(178)) - set(train_idx)))
X_train, Y_train = X[train_idx], Y[train_idx]
X_test, Y_test = X[test_idx], Y[test_idx]

模型構(gòu)建–計(jì)算距離

利用MindSpore提供的tile, square, ReduceSum, sqrt, TopK等算子，通過(guò)矩陣運(yùn)算的方式同時(shí)計(jì)算輸入樣本x和已明確分類(lèi)的其他樣本X_train的距離，并計(jì)算出top k近鄰

class KnnNet(nn.Cell):def __init__(self, k):super(KnnNet, self).__init__()self.k = kdef construct(self, x, X_train):#平鋪輸入x以匹配X_train中的樣本數(shù)x_tile = ops.tile(x, (128, 1))square_diff = ops.square(x_tile - X_train)square_dist = ops.sum(square_diff, 1)dist = ops.sqrt(square_dist)#-dist表示值越大，樣本就越接近values, indices = ops.topk(-dist, self.k)return indicesdef knn(knn_net, x, X_train, Y_train):x, X_train = ms.Tensor(x), ms.Tensor(X_train)indices = knn_net(x, X_train)topk_cls = [0]*len(indices.asnumpy())for idx in indices.asnumpy():topk_cls[Y_train[idx]] += 1cls = np.argmax(topk_cls)return cls

模型預(yù)測(cè)

在驗(yàn)證集上驗(yàn)證KNN算法的有效性，取𝑘=5𝑘=5，驗(yàn)證精度接近80%，說(shuō)明KNN算法在該3分類(lèi)任務(wù)上有效，能根據(jù)酒的13種屬性判斷出酒的品種。

acc = 0
knn_net = KnnNet(5)
for x, y in zip(X_test, Y_test):pred = knn(knn_net, x, X_train, Y_train)acc += (pred == y)print('label: %d, prediction: %s' % (y, pred))
print('Validation accuracy is %f' % (acc/len(Y_test)))

打卡圖片：