2023年第十三屆MathorCup高校數(shù)學建模挑戰(zhàn)賽

資料思路分享群：714452621

K近鄰算法

我們先看一張圖：

觀察一下，黃點和藍點代表了兩種標簽，比如每個藍點都是一個合格的產品，黃點是劣質的產品。事實上在圖中可以看到，相同標記的樣本點通常是成團的形式聚在一起，因為合格的產品在屬性上一定是相同或相似的（合格的產品在屬性上不太可能會跑到不合格的一類中去）。

那么我們預測過程中，查看被預測的樣本x是屬于哪一堆來判斷它是黃豆還是藍豆是不是可行呢？

當然可以啦，K近鄰就是一種基于該原理的算法。從名字里就可以看到，K近鄰樣本的預測上，是看被預測樣本x離哪一團最近，那它就是屬于哪一類的。

圖里有兩種標記，就叫它黃豆、綠豆、紫豆好了（這里也能看到，K近鄰不像感知機只能劃分兩種類，K近鄰是一種多類劃分的模型)。當我們要預測一個樣本x時，將x的特征轉換為在圖中的坐標點，分別計算和綠豆、黃豆、紫豆的舉例，比如說距離分別為1， 1.5， 0.8。選擇其中距離最小的紫豆作為樣本x的預測類別。

那啥是樣本x和一團豆的距離？ 1.找到樣本x最近的點，該點的類就是樣本的預測類：這是一種方法，但是如果有噪音呢（同一塊區(qū)域又有黃點又有綠點）？比如說x實際上是黃豆，但是它的位置在黃豆和綠豆的邊界上（例如上圖黃點和綠點的交叉處），很可能它最近的點是一個綠點，所以….不太好

2.與每一團的中心點進行距離計算：分別計算綠色、黃色、紫色的中心點，判斷距離最小的類即為預測輸出類。這樣會不會有問題嗎？我們看一下上圖中綠色和紫色交叉的地方，很明顯在這個交叉位置離綠色很近，與紫色中心點較遠，但實際上紫色的。所以…..不太好

3.找到樣本點周圍的K個點，其中占數(shù)目最多的類即預測輸出的類：克服了前兩種方法的弊端，實際上這就是K近鄰所使用的算法

knn數(shù)學原理

K近鄰并沒有顯式的學習過程，也就是不需要對訓練集進行學習。預測過程中直接遍歷預測點與所有點的距離，并找到最近的K個點即可。找到K個最近點后，使用多數(shù)表決（即投票）的方式確定預測點的類別。式3.1I(yi=ci)中的I為指示函數(shù)，當括號內條件為真時I(true)=1，I(false)=0。argmax表示令后式數(shù)值最大時的參數(shù)，例如argmax(-X^2 + 1)的結果為0，因為x=0時-X^2 + 1結果為1，為最大值。

式3.1表示對于每一個類Cj，進行I(yi=cj)進行求和，就是計算這K個點中有多少個標記為Cj的點，例如K=25，一共有四個類分別為C1、C2、C3、C4，25個點中他們的個數(shù)分別有10、5、1、9個，那么最多數(shù)目的類別C1就是樣本點的預測類別。

距離度量

在多維空間中有很多種方式可以計算點與點之間的舉例，通常采用歐氏距離作為K近鄰的度量單位（大部分模型中歐氏距離都是一種不錯的選擇)。其實就是樣本A、B中每一個特征都互相相減，再平方、再求和。與二維中兩點之間距離計算方式相同，只是擴展到了多維。

曼哈頓與P=無窮可以不用深究，在本文中使用曼哈頓準確度極差（僅針對Mnist數(shù)據(jù)集使用K近鄰的情況），這兩種方式目前僅作了解即可。

KNN的缺點

1、在預測樣本類別時，待預測樣本需要與訓練集中所有樣本計算距離，當訓練集數(shù)量過高時（例如Mnsit訓練集有60000個樣本），每預測一個樣本都要計算60000個距離，計算代價過高，尤其當測試集數(shù)目也較大時（Mnist測試集有10000個）。

1、K近鄰在高維情況下時（高維在機器學習中并不少見），待預測樣本需要與依次與所有樣本求距離。向量維度過高時使得歐式距離的計算變得不太迅速了。本文在60000訓練集的情況下，將10000個測試集縮減為200個，整個過程仍然需要308秒（曼哈頓距離為246秒，但準確度大幅下降）。

使用歐氏距離還是曼哈頓距離，性能上的差別相對來說不是很大，說明歐式距離并不是制約計算速度的主要方式。最主要的是訓練集的大小，每次預測都需要與60000個樣本進行比對，同時選出距離最近的K項。

代碼實現(xiàn)

import numpy as np
import time
def loadData(fileName):
? ?'''
? ?加載文件
? ?:param fileName:要加載的文件路徑
? ?:return: 數(shù)據(jù)集和標簽集
? ?'''
? ?print('start read file')
? ?#存放數(shù)據(jù)及標記
? ?dataArr = []; labelArr = []
? ?#讀取文件
? ?fr = open(fileName)
? ?#遍歷文件中的每一行
? ?for line in fr.readlines():
? ? ? ?#獲取當前行，并按“，”切割成字段放入列表中
? ? ? ?#strip：去掉每行字符串首尾指定的字符（默認空格或換行符）
? ? ? ?#split：按照指定的字符將字符串切割成每個字段，返回列表形式
? ? ? ?curLine = line.strip().split(',')
? ? ? ?#將每行中除標記外的數(shù)據(jù)放入數(shù)據(jù)集中（curLine[0]為標記信息）
? ? ? ?#在放入的同時將原先字符串形式的數(shù)據(jù)轉換為整型
? ? ? ?dataArr.append([int(num) for num in curLine[1:]])
? ? ? ?#將標記信息放入標記集中
? ? ? ?#放入的同時將標記轉換為整型
? ? ? ?labelArr.append(int(curLine[0]))
? ?#返回數(shù)據(jù)集和標記
? ?return dataArr, labelArr
def calcDist(x1, x2):
? ?'''
? ?計算兩個樣本點向量之間的距離
? ?使用的是歐氏距離，即 樣本點每個元素相減的平方 ?再求和 ?再開方
? ?歐式舉例公式這里不方便寫，可以百度或谷歌歐式距離（也稱歐幾里得距離）
? ?:param x1:向量1
? ?:param x2:向量2
? ?:return:向量之間的歐式距離
? ?'''
? ?return np.sqrt(np.sum(np.square(x1 - x2)))
? ?#馬哈頓距離計算公式
? ?# return np.sum(x1 - x2)
def getClosest(trainDataMat, trainLabelMat, x, topK):
? ?'''
? ?預測樣本x的標記。
? ?獲取方式通過找到與樣本x最近的topK個點，并查看它們的標簽。
? ?查找里面占某類標簽最多的那類標簽
? ?（書中3.1 3.2節(jié)）
? ?:param trainDataMat:訓練集數(shù)據(jù)集
? ?:param trainLabelMat:訓練集標簽集
? ?:param x:要預測的樣本x
? ?:param topK:選擇參考最鄰近樣本的數(shù)目（樣本數(shù)目的選擇關系到正確率，詳看3.2.3 K值的選擇）
? ?:return:預測的標記
? ?'''
? ?#建立一個存放向量x與每個訓練集中樣本距離的列表
? ?#列表的長度為訓練集的長度，distList[i]表示x與訓練集中第
? ?## i個樣本的距離
? ?distList = [0] * len(trainLabelMat)
? ?#遍歷訓練集中所有的樣本點，計算與x的距離
? ?for i in range(len(trainDataMat)):
? ? ? ?#獲取訓練集中當前樣本的向量
? ? ? ?x1 = trainDataMat[i]
? ? ? ?#計算向量x與訓練集樣本x的距離
? ? ? ?curDist = calcDist(x1, x)
? ? ? ?#將距離放入對應的列表位置中
? ? ? ?distList[i] = curDist
? ?#對距離列表進行排序
? ?#argsort：函數(shù)將數(shù)組的值從小到大排序后，并按照其相對應的索引值輸出
? ?#例如：
? ?# ? >>> x = np.array([3, 1, 2])
? ?# ? >>> np.argsort(x)
? ?# ? array([1, 2, 0])
? ?#返回的是列表中從小到大的元素索引值，對于我們這種需要查找最小距離的情況來說很合適
? ?#array返回的是整個索引值列表，我們通過[:topK]取列表中前topL個放入list中。
? ?#----------------優(yōu)化點-------------------
? ?#由于我們只取topK小的元素索引值，所以其實不需要對整個列表進行排序，而argsort是對整個
? ?#列表進行排序的，存在時間上的浪費。字典有現(xiàn)成的方法可以只排序top大或top小，可以自行查閱
? ?#對代碼進行稍稍修改即可
? ?#這里沒有對其進行優(yōu)化主要原因是KNN的時間耗費大頭在計算向量與向量之間的距離上，由于向量高維
? ?#所以計算時間需要很長，所以如果要提升時間，在這里優(yōu)化的意義不大。（當然不是說就可以不優(yōu)化了，
? ?#主要是我太懶了）
? ?topKList = np.argsort(np.array(distList))[:topK] ? ? ? ?#升序排序
? ?#建立一個長度時的列表，用于選擇數(shù)量最多的標記
? ?#3.2.4提到了分類決策使用的是投票表決，topK個標記每人有一票，在數(shù)組中每個標記代表的位置中投入
? ?#自己對應的地方，隨后進行唱票選擇最高票的標記
? ?labelList = [0] * 10
? ?#對topK個索引進行遍歷
? ?for index in topKList:
? ? ? ?#trainLabelMat[index]：在訓練集標簽中尋找topK元素索引對應的標記
? ? ? ?#int(trainLabelMat[index])：將標記轉換為int（實際上已經是int了，但是不int的話，報錯）
? ? ? ?#labelList[int(trainLabelMat[index])]：找到標記在labelList中對應的位置
? ? ? ?#最后加1，表示投了一票
? ? ? ?labelList[int(trainLabelMat[index])] += 1
? ?#max(labelList)：找到選票箱中票數(shù)最多的票數(shù)值
? ?#labelList.index(max(labelList))：再根據(jù)最大值在列表中找到該值對應的索引，等同于預測的標記
? ?return labelList.index(max(labelList))
def test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, topK):
? ?'''
? ?測試正確率
? ?:param trainDataArr:訓練集數(shù)據(jù)集
? ?:param trainLabelArr: 訓練集標記
? ?:param testDataArr: 測試集數(shù)據(jù)集
? ?:param testLabelArr: 測試集標記
? ?:param topK: 選擇多少個鄰近點參考
? ?:return: 正確率
? ?'''
? ?print('start test')
? ?#將所有列表轉換為矩陣形式，方便運算
? ?trainDataMat = np.mat(trainDataArr); trainLabelMat = np.mat(trainLabelArr).T
? ?testDataMat = np.mat(testDataArr); testLabelMat = np.mat(testLabelArr).T
? ?#錯誤值技術
? ?errorCnt = 0
? ?#遍歷測試集，對每個測試集樣本進行測試
? ?#由于計算向量與向量之間的時間耗費太大，測試集有6000個樣本，所以這里人為改成了
? ?#測試200個樣本點，如果要全跑，將行注釋取消，再下一行for注釋即可，同時下面的print
? ?#和return也要相應的更換注釋行
? ?# for i in range(len(testDataMat)):
? ?for i in range(200):
? ? ? ?# print('test %d:%d'%(i, len(trainDataArr)))
? ? ? ?print('test %d:%d' % (i, 200))
? ? ? ?#讀取測試集當前測試樣本的向量
? ? ? ?x = testDataMat[i]
? ? ? ?#獲取預測的標記
? ? ? ?y = getClosest(trainDataMat, trainLabelMat, x, topK)
? ? ? ?#如果預測標記與實際標記不符，錯誤值計數(shù)加1
? ? ? ?if y != testLabelMat[i]: errorCnt += 1
? ?#返回正確率
? ?# return 1 - (errorCnt / len(testDataMat))
? ?return 1 - (errorCnt / 200)
if __name__ == "__main__":
? ?start = time.time()
? ?#獲取訓練集
? ?trainDataArr, trainLabelArr = loadData('../Mnist/mnist_train.csv')
? ?#獲取測試集
? ?testDataArr, testLabelArr = loadData('../Mnist/mnist_test.csv')
? ?#計算測試集正確率
? ?accur = test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, 25)
? ?#打印正確率
? ?print('accur is:%d'%(accur * 100), '%')
? ?end = time.time()
? ?#顯示花費時間
print('time span:', end - start)

2023年第十三屆MathorCup高校數(shù)學建模挑戰(zhàn)賽

資料思路分享群：714452621