有一句話這樣說：如果你想了解一個人，你可以從他身邊的朋友開始。
如果與他交往的好友都是一些品行高尚的人，那么可以認(rèn)為這個人的品行也差不了。
其實古人在這方面的名言警句，寓言故事有很多。例如：物以類聚，人以群分；近朱者赤，近墨者黑。
其實K-近鄰算法和古人的智慧想通，世間萬物息息相通，你中有我，我中有你。

簡述機(jī)器學(xué)習(xí)

在日常生活中，人們很難直接從原始數(shù)據(jù)本身獲得所需信息。而機(jī)器學(xué)習(xí)就是把生活中無序的數(shù)據(jù)轉(zhuǎn)換成有用的信息。例如，對于垃圾郵件的檢測，偵測一個單詞是否存在并沒有多大的作用，然而當(dāng)某幾個特定單詞同時出現(xiàn)時，再輔以考慮郵件的長度及其他因素，人們就可以更準(zhǔn)確地判定該郵件是否為垃圾郵件。

機(jī)器學(xué)習(xí)分為監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)，其中：

• （1）監(jiān)督學(xué)習(xí)：包含分類和回歸。分類，是將實例數(shù)據(jù)劃分到合適的分類中?；貧w，主要用于預(yù)測數(shù)值形數(shù)據(jù)。因為這類算法必須知道預(yù)測什么，即目標(biāo)變量的分類信息，所以稱為監(jiān)督學(xué)習(xí)。
• （2）無監(jiān)督學(xué)習(xí)：此時數(shù)據(jù)沒有類別信息，不能給定目標(biāo)值。在無監(jiān)督學(xué)習(xí)中，將數(shù)據(jù)集合分成由類似的對象組成的多個類的過程稱為聚類，將尋找描述數(shù)據(jù)統(tǒng)計值的過程稱為密度估計，此外，無監(jiān)督學(xué)習(xí)還可以減少數(shù)據(jù)特征的維度，以便我們可以使用二維或三維圖形更加直觀地展示數(shù)據(jù)信息。

以下是機(jī)器學(xué)習(xí)的主要算法：

• 監(jiān)督學(xué)習(xí)：k-近鄰算法（KNN），樸素貝葉斯算法，支持向量機(jī)（SVM），決策樹，線性回歸，局部加權(quán)線性回歸，Ridge回歸，Lasso最小回歸系數(shù)估計
• 無監(jiān)督學(xué)習(xí)：K-均值，DBSCAN，最大期望算法，Parzen窗設(shè)計

注意：K-近鄰是監(jiān)督學(xué)習(xí)，K-Means是無監(jiān)督學(xué)習(xí)

簡述K-近鄰（KNN）算法

概述

KNN算法非常簡單和有效。通過對K個最相似的實例(鄰居)對整個訓(xùn)練集進(jìn)行搜索并匯總這些K個實例的輸出變量，可以對一個新的數(shù)據(jù)點進(jìn)行預(yù)測。對于回歸問題，它可能是平均輸出變量，對于分類問題，可能是模型(或最常見)類值。
關(guān)鍵在于如何確定數(shù)據(jù)實例之間的相似性。如果您的屬性都具有相同的比例(例如，以英寸為單位)，最簡單的技術(shù)是使用歐幾里得距離，您可以根據(jù)每個輸入變量之間的差異直接計算該數(shù)字。

K近鄰（k-Nearest Neighbor,kNN）

K-近鄰算法采用測量不同特征值之間的距離方法進(jìn)行分類。
KNN（K-最近鄰）算法是相對比較簡單的機(jī)器學(xué)習(xí)算法之一，它主要用于對事物進(jìn)行分類。
工作原理：首先有一個樣本數(shù)據(jù)集合（訓(xùn)練樣本集），并且樣本數(shù)據(jù)集合中每條數(shù)據(jù)都存在標(biāo)簽（分類），即我們知道樣本數(shù)據(jù)中每一條數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系，輸入沒有標(biāo)簽的數(shù)據(jù)之后，將新數(shù)據(jù)的每個特征與樣本集的數(shù)據(jù)對應(yīng)的特征進(jìn)行比較（歐式距離運算），然后算出新數(shù)據(jù)與樣本集中特征最相似（最近鄰）的數(shù)據(jù)的分類標(biāo)簽，一般我們選擇樣本數(shù)據(jù)集中前k個最相似的數(shù)據(jù)，然后再從k個數(shù)據(jù)集中選出出現(xiàn)分類最多的分類作為新數(shù)據(jù)的分類。

優(yōu)缺點

• 優(yōu)點：精度高、對異常值不敏感、無數(shù)據(jù)輸入假定。
• 缺點：計算度復(fù)雜、空間度復(fù)雜。
• 適用范圍：數(shù)值型和標(biāo)稱型

數(shù)學(xué)公式

歐式距離：歐氏距離是最易于理解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。
(1)二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：

(2)三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：

算法實現(xiàn)

k-近鄰算法的偽代碼
對未知類型屬性的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作：
(1) 計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離；
(2) 按照距離增序排序；
(3) 選取與當(dāng)前點距離最近的k個點；
(4) 決定這k個點所屬類別的出現(xiàn)頻率；
(5) 返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類。

應(yīng)用示例

給一個新的數(shù)據(jù)時，離它最近的 k 個點中，哪個類別多，這個數(shù)據(jù)就屬于哪一類。
栗子：要區(qū)分 貓 和 狗，通過 claws 和 sound 兩個feature來判斷的話，圓形和三角形是已知分類的了，那么這個 star 代表的是哪一類呢？

k＝3時，這三條線鏈接的點就是最近的三個點，那么圓形多一些，所以這個star就是屬于貓。

KNN算法應(yīng)用—手寫數(shù)字識別

KNN算法代碼

#-*- coding: utf-8 -*-
from numpy import *
import operator
import time
from os import listdir

def classify(inputPoint,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]     #已知分類的數(shù)據(jù)集（訓(xùn)練集）的行數(shù)
    #先tile函數(shù)將輸入點拓展成與訓(xùn)練集相同維數(shù)的矩陣，再計算歐氏距離
    diffMat = tile(inputPoint,(dataSetSize,1))-dataSet  #樣本與訓(xùn)練集的差值矩陣
    sqDiffMat = diffMat ** 2                    #差值矩陣平方
    sqDistances = sqDiffMat.sum(axis=1)         #計算每一行上元素的和
    distances = sqDistances ** 0.5              #開方得到歐拉距離矩陣
    sortedDistIndicies = distances.argsort()    #按distances中元素進(jìn)行升序排序后得到的對應(yīng)下標(biāo)的列表
    #選擇距離最小的k個點
    classCount = {}
    for i in range(k):
        voteIlabel = labels[ sortedDistIndicies[i] ]
        classCount[voteIlabel] = classCount.get(voteIlabel,0)+1
    #按classCount字典的第2個元素（即類別出現(xiàn)的次數(shù)）從大到小排序
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)
    return sortedClassCount[0][0]

下面介紹如何使用knn算法對手寫識別數(shù)據(jù)進(jìn)行分類，這里構(gòu)造的分類系統(tǒng)只能識別數(shù)字0到9，數(shù)字經(jīng)圖形處理軟件處理成具有相同的色彩和大小，寬高為32x32像素，為了便于處理，已將圖像轉(zhuǎn)換為文本格式，其效果圖如下：

數(shù)據(jù)集有兩個目錄，其中目錄trainingDigits中包含了1934個例子，命名規(guī)則如 9_45.txt，表示該文件的分類是9，是數(shù)字9的第45個實例，每個數(shù)字大概有200個實例。testDigits目錄中包含946個例子。使用trainingDigits中的數(shù)據(jù)作為訓(xùn)練集，使用testDigits中的數(shù)據(jù)作為測試集測試分類的效果。兩組數(shù)據(jù)沒有重疊。

算法應(yīng)用步驟如下：

1. 數(shù)據(jù)準(zhǔn)備：數(shù)字圖像文本向量化，這里將32x32的二進(jìn)制圖像文本矩陣轉(zhuǎn)換成1x1024的向量。循環(huán)讀出文件的前32行，存儲在向量中。

#文本向量化 32x32 -> 1x1024
def img2vector(filename):
    returnVect = []
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect.append(int(lineStr[j]))
    return returnVect

2. 構(gòu)建訓(xùn)練數(shù)據(jù)集：利用目錄trainingDigits中的文本數(shù)據(jù)構(gòu)建訓(xùn)練集向量，以及對應(yīng)的分類向量

#從文件名中解析分類數(shù)字
def classnumCut(fileName):
    fileStr = fileName.split('.')[0]
    classNumStr = int(fileStr.split('_')[0])
    return classNumStr

#構(gòu)建訓(xùn)練集數(shù)據(jù)向量，及對應(yīng)分類標(biāo)簽向量
def trainingDataSet():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')           #獲取目錄內(nèi)容
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))                          #m維向量的訓(xùn)練集
    for i in range(m):
        fileNameStr = trainingFileList[i]
        hwLabels.append(classnumCut(fileNameStr))
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    return hwLabels,trainingMat

3. 測試集數(shù)據(jù)測試：通過測試testDigits目錄下的樣本，來計算算法的準(zhǔn)確率。

#測試函數(shù)
def handwritingTest():
    hwLabels,trainingMat = trainingDataSet()    #構(gòu)建訓(xùn)練集
    testFileList = listdir('testDigits')        #獲取測試集
    errorCount = 0.0                            #錯誤數(shù)
    mTest = len(testFileList)                   #測試集總樣本數(shù)
    t1 = time.time()
    for i in range(mTest):
        fileNameStr = testFileList[i]
        classNumStr = classnumCut(fileNameStr)
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        #調(diào)用knn算法進(jìn)行測試
        classifierResult = classify(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print("\nthe total number of tests is: %d" % mTest)               #輸出測試總樣本數(shù)
    print("the total number of errors is: %d" % errorCount)           #輸出測試錯誤樣本數(shù)
    print("the total error rate is: %f" % (errorCount/float(mTest)))  #輸出錯誤率
    t2 = time.time()
    print("Cost time: %.2fmin, %.4fs."%((t2-t1)//60,(t2-t1)%60))      #測試耗時

if __name__ == "__main__":
    handwritingTest()

運行結(jié)果如下：

the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9

the total number of tests is: 946
the total number of errors is: 10
the total error rate is: 0.010571
Cost time: 0.00min, 18.2610s.

利用KNN算法識別手寫數(shù)字?jǐn)?shù)據(jù)集，錯誤率為1.6%，算法的準(zhǔn)確率還算可觀。也可以通過改變變量k的值，觀察錯誤率的變化，關(guān)于k值的選擇，一般取一個比較小的數(shù)值，例如采用交叉驗證法（簡單來說，就是一部分樣本做訓(xùn)練集，一部分做測試集）來選擇最優(yōu)的K值。

通過運行以上代碼，我們會發(fā)現(xiàn)KNN算法的執(zhí)行效率并不高，因為算法需要為每個測試向量計算約2000次歐氏距離，每個距離計算包括1024個維度浮點運算，全部樣本要執(zhí)行900多次，可見算法實際耗時長，另外，KNN算法必須保存全部數(shù)據(jù)集，每次需為測試向量準(zhǔn)備2MB的存儲空間（2個1024x1024矩陣的空間）。所以如何優(yōu)化算法，減少存儲空間和計算時間的開銷，需要我們進(jìn)一步深入學(xué)習(xí)。

KNN算法應(yīng)用—電影題材分類

我們知道，電影可以按題材分類，但題材本身是如何定義的？由誰來判定某部電影屬于哪個題材？即同一題材的電影會具有哪些公共特征？這些都是在做電影分類時一定要搞清楚的問題。這里以動作片和愛情片為例做簡要說明。動作片具有哪些公共特征，使得動作片之間非常相似，卻明顯有別于愛情片？動作片中也可能有接吻鏡頭，愛情片中也可能存在打斗鏡頭，所以，不能簡單地依靠是否存在打斗或者接吻來判斷一部電影的類型。但很明顯的是，動作片中的打斗鏡頭更多、愛情片中的接吻次數(shù)更頻繁，基于此類場景在一部電影中出現(xiàn)的次數(shù)可用來進(jìn)行電影分類。

有人曾經(jīng)統(tǒng)計過很多電影的打斗鏡頭和接吻鏡頭， 下方圖1-1 給出了6部電影的打斗和接吻鏡頭。假如現(xiàn)在有一部從未看過的電影，你如何判斷它屬于動作片還是愛情片呢？

圖1-1

首先，我們弄清楚這部未知電影中存在多少打斗鏡頭、多少接吻鏡頭，圖1-1中問號位置是該未知電影出現(xiàn)的鏡頭數(shù)圖示，具體見下方表1-1。

表1-1每部電影的打斗鏡頭數(shù)、接吻鏡頭數(shù)及電影評估類型

表2-2 已知電影與未知電影之間的距離

由表2-2所示，顯然，如果樣本集中所有電影與未知電影之間的距離按照遞增排序的話，可以得到k個距離最近的電影，這里假設(shè)k=2的話，則未知電影與電影He’s Not Really into Dudes，Beautiful Woman影片類型最為相似，判定未知電影屬于愛情片。

KNN算法代碼

#-*- coding: utf-8 -*-
import numpy as np
import operator

'''
    trainData - 訓(xùn)練集
    testData - 測試集
    labels - 分類
'''


def knn(trainData, testData, labels, k):
    # 計算訓(xùn)練樣本的行數(shù)
    rowSize = trainData.shape[0]
    # 計算訓(xùn)練樣本和測試樣本的差值
    diff = np.tile(testData, (rowSize, 1)) - trainData
    # 計算差值的平方和
    sqrDiff = diff ** 2
    sqrDiffSum = sqrDiff.sum(axis=1)
    # 計算距離
    distances = sqrDiffSum ** 0.5
    # 對所得的距離從低到高進(jìn)行排序
    sortDistance = distances.argsort()

    count = {}

    for i in range(k):
        vote = labels[sortDistance[i]]
        count[vote] = count.get(vote, 0) + 1
    # 對類別出現(xiàn)的頻數(shù)從高到低進(jìn)行排序
    sortCount = sorted(count.items(), key=operator.itemgetter(1), reverse=True)

    # 返回出現(xiàn)頻數(shù)最高的類別
    return sortCount[0][0]


trainData = np.array([[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]])
labels = ['愛情片', '愛情片', '愛情片', '動作片', '動作片', '動作片']
testData = [18, 90]
X = knn(trainData, testData, labels, 3)
print(X)