1、k-近鄰算法

k-近鄰算法簡稱kNN，是一種常用的監(jiān)督學(xué)習(xí)方法讥此，它的工作機(jī)制簡單來說就是：在給定的測試樣本中，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個(gè)訓(xùn)練樣本谎碍，然后基于這k個(gè)“鄰居”的信息來進(jìn)行預(yù)測。

• 在分類中可使用“投票法”洞焙，即選擇這k個(gè)樣本中出現(xiàn)最多的類別標(biāo)記作為預(yù)測的結(jié)果蟆淀；
• 在回歸中可使用“平均法”太援，即將這k個(gè)樣本的實(shí)值輸出標(biāo)記值的平均值作為預(yù)測結(jié)果。

還可基于距離的遠(yuǎn)近進(jìn)行加權(quán)平均和加權(quán)投票扳碍。

1.1提岔、度量距離

設(shè)特征空間中X是n維實(shí)數(shù)向量Rⁿ, x_i, x_j∈X, x_i=(x_i¹,x_i²,...,x_iⁿ), x_j=(x_j¹,x_j²,...,x_jⁿ).

x_i,x_j的L_p距離為=(\sum_{l=1}^{n}|x_i{l}-x_j^{l}|{p})^{\frac{1}{p}},(p≥1)$$)

當(dāng)p=2時(shí)，為歐式距離（Euclidean distance）

=(\sum_{l=1}^{n}|x_i{l}-x_j^{l}|{2})^{\frac{1}{2}}$$)

當(dāng)p=1時(shí)笋敞，為曼哈頓距離（Manhattan distance）

=\sum_{l=1}^{n}|x_i{l}-x_j^{l}|$$)

當(dāng)p=∞時(shí)碱蒙，是各個(gè)坐標(biāo)距離的最大值

=\max_{l}\sum_{l=1}^{n}|x_i{l}-x_j^{l}|$$)

1.2、k值的選取

k值的選取會(huì)對(duì)k近鄰法的結(jié)果產(chǎn)生重大影響夯巷。

如果選擇較小的k值赛惩，就相當(dāng)于用較小的鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測，“學(xué)習(xí)”的近似誤差（approximation error）會(huì)減小趁餐，只有與輸入實(shí)例相似的訓(xùn)練實(shí)例才會(huì)對(duì)預(yù)測結(jié)果產(chǎn)生作用喷兼。但缺點(diǎn)是“學(xué)習(xí)”的估計(jì)誤差（estimation error）會(huì)增大，預(yù)測結(jié)果會(huì)對(duì)近鄰的實(shí)例點(diǎn)非常敏感后雷。如果鄰近的實(shí)例點(diǎn)恰好是噪聲季惯，預(yù)測就會(huì)出錯(cuò)，亦即k值的減小就意味著整體的模型變復(fù)雜臀突，容易發(fā)生過擬合勉抓。

如果選擇較大的k值，就相當(dāng)于用較大的鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測候学，其優(yōu)點(diǎn)是可以減少學(xué)習(xí)的估計(jì)誤差藕筋，但缺點(diǎn)是學(xué)習(xí)的近似誤差會(huì)增大。這時(shí)與輸入實(shí)例不相似的訓(xùn)練實(shí)例也會(huì)對(duì)預(yù)測產(chǎn)生作用梳码，是預(yù)測發(fā)生錯(cuò)誤隐圾。k的增大就意味著整體的模型變得簡單。

2掰茶、算法實(shí)現(xiàn)

這次仍然使用學(xué)習(xí)決策樹算法時(shí)候的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)暇藏，

由于各種距離需要使用數(shù)值進(jìn)行計(jì)算，上述“色澤”符匾、“根蒂”叨咖、“敲聲”瘩例、“紋理”啊胶、“臍部”和“觸感”6個(gè)特征變量都是類別變量（factor），我們需要將其轉(zhuǎn)化為啞變量（dummy variables）垛贤。

例如在“色澤”中焰坪，令數(shù)值0代表“烏黑”，數(shù)值1代表“青綠”聘惦，數(shù)值2代表“淺白”某饰，以此進(jìn)行轉(zhuǎn)換。

其中數(shù)據(jù)集（data1.txt）中的格式如下圖所示：

下述的代碼即針對(duì)上述數(shù)據(jù)集進(jìn)行啞變量轉(zhuǎn)換的,

filename = 'data1.txt'
def factor2dummy_variable(filename):
    fr = open(filename,encoding = 'utf-8')#以u(píng)tf-8讀取文件
    dataColumns = fr.readline()#去除首行
    arrayLines = fr.readlines()#讀取所有行
    lines = np.array([line.replace('\n','').split('\t') for line in arrayLines]).T#按行指定分隔符，并進(jìn)行轉(zhuǎn)置
    lines = lines[1:,:]#實(shí)際使用的數(shù)據(jù)部分
    setFactors = [set(line) for line in lines]#set操作黔漂，只保存一種分類的集合
    k = 0
    for i in setFactors:
        dummy_num = 0
        line = lines[k]
        for j in i:
            line[line == j] = dummy_num#啞變量轉(zhuǎn)換
            dummy_num += 1
        k += 1
    lines = lines.T#轉(zhuǎn)置
    return lines

將轉(zhuǎn)換好的數(shù)據(jù)集保存到文件（data2.txt）,

lines = factor2dummy_variable(filename)
dataSet = lines
filename = 'data2.txt'
def data2txt(dataSet,filename):
    fw = open(filename,'w',encoding='utf-8')#以u(píng)tf-8編碼寫入
    for line in dataSet:
        for element in line:
            fw.write(element)
            fw.write('\t')#tab鍵分割符號(hào)
        fw.write('\n')#換行
    fw.close()

轉(zhuǎn)換好的數(shù)據(jù)集格式如下圖所示：

處理完畢上述變量后诫尽，需要將轉(zhuǎn)換好的數(shù)據(jù)文件轉(zhuǎn)化成numpy可以使用的數(shù)據(jù)集形式，

filename = 'data2.txt'
def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()#讀取所有行
    numberOfLines = len(arrayOLines)#計(jì)算記錄數(shù)量
    numberOfcloumns = len(arrayOLines[0].replace('\t\n','').split('\t')) - 1#計(jì)算變量數(shù)量
    returnMat = np.zeros((numberOfLines, numberOfcloumns))
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()#去除空格
        listFromLine = line.split('\t')#按tab鍵分割
        returnMat[index, :] = listFromLine[:-1]#得到分類變量數(shù)組
        classLabelVector.append(int(listFromLine[-1]))#類別變量數(shù)組
        index += 1
    return returnMat, classLabelVector

? 注：有時(shí)候由于各類變量之間數(shù)值差別太大炬守，同時(shí)量綱也各不相同牧嫉，這時(shí)候就需要進(jìn)行歸一 化操作，將各變量的范圍設(shè)置在0~1之間减途，以消除量綱影響酣藻，加快運(yùn)算速度。

? 其中歸一化的式子如下：
? }}{\min{(x)}-\max{(x)}}?$$)

? 下述代碼即進(jìn)行歸一化操作：

def autoNorm(dataSet):
    minValue = dataSet.min(0)#得到每列的最小值
    maxValue = dataSet.max(0)#每列最大值
    ranges = maxValue - minValue#分母
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]#行數(shù)
    normDataSet = dataSet - np.tile(minValue, (m,1))#分子
    normDataSet = normDataSet/np.tile(ranges, (m,1))
    return normDataSet, ranges, minValue

經(jīng)過上述處理鳍置，這里通過計(jì)算歐式距離進(jìn)行kNN分類辽剧，具體代碼如下：

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]#得到行數(shù)
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet#計(jì)算輸入向量inX與訓(xùn)練樣本的差
    sqDiffMat = diffMat**2#計(jì)算差值的平方
    sqDistances = sqDiffMat.sum(axis = 1)#距離平方和
    distances = sqDistances**0.5#開方得到距離
    sortedDistIndicies = distances.argsort()#距離進(jìn)行排序,得到排序的下標(biāo)
    classCount = {}
    for i in range(k):#確定前k個(gè)距離中最小元素所屬分類
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1#對(duì)出現(xiàn)的label進(jìn)行計(jì)數(shù)
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1),
                              reverse = True)#按照計(jì)數(shù)值進(jìn)行降序排序
                              #operator.itemgetter(1)確定一個(gè)函數(shù)取出classCount中的第一個(gè)域的值，即將value取出
    return sortedClassCount[0][0]#返回最大的計(jì)數(shù)值的分類

由此税产，即進(jìn)行了kNN的分類操作怕轿，下面通過以下代碼對(duì)分類效果進(jìn)行測試（測試數(shù)據(jù)集仍是訓(xùn)練數(shù)據(jù)集合）

dataLines, datalabels = file2matrix('data2.txt')
i=0
errorCount = 0.0
for line in dataLines:
    print('記錄%s的原始分類是:%d，劃分分類是:%d' %(str(line), datalabels[i], 
                                     classify0(line, dataLines ,datalabels, 1))) 
    if (datalabels[i] != classify0(line, dataLines ,datalabels, 1)):
        errorCount += 1.0
    i += 1
print('錯(cuò)誤率為: %f' %(errorCount/float(len(dataLines))))

可以看出錯(cuò)誤率為0.000000辟拷，正確率達(dá)到了100%撤卢。可以看出準(zhǔn)確度不錯(cuò)梧兼，當(dāng)然此準(zhǔn)確度也與數(shù)據(jù)量的大小有關(guān)放吩，后續(xù)可以將數(shù)據(jù)集擴(kuò)大，或者使用不同的數(shù)據(jù)集進(jìn)行訓(xùn)練測試羽杰，來驗(yàn)證分類效果渡紫。

下面代碼是通過Scikit - Learn庫進(jìn)行數(shù)據(jù)集的訓(xùn)練和測試過程。

import numpy as np
from sklearn import neighbors

data = []
labels = []
with open('data2.txt') as ifile:
    for line in ifile:
        tokens = line.replace('\t\n','').split('\t')
        data.append([float(tk) for tk in tokens[:-1]])
        labels.append(tokens[-1])
x = np.array(data)
y = np.array(labels)

clf = neighbors.KNeighborsClassifier(algorithm = 'kd_tree', n_neighbors = 1)
clf.fit(x,y)

answer = clf.predict(x)
print('準(zhǔn)確率為:%f' % float(np.mean(answer == y)))#正確率

其準(zhǔn)確率可以達(dá)到100%考赛。

值得注意的是惕澎，上述neighbors.KNeighborsClassifier()中，存在很多可以自行調(diào)節(jié)的參數(shù)颜骤，這里可以查看官方文檔（http://scikit-learn.org/stable/documentation.html） 并進(jìn)行相關(guān)操作唧喉。