Intro

k近鄰法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一種基本分類與回歸方法。它的工作原理是：存在一個樣本數據集合，也稱作為訓練樣本集，并且樣本集中每個數據都存在標簽，即我們知道樣本集中每一個數據與所屬分類的對應關系。輸入沒有標簽的新數據后，將新的數據的每個特征與樣本集中數據對應的特征進行比較，然后算法提取樣本最相似數據(最近鄰)的分類標簽。一般來說，我們只選擇樣本數據集中前k個最相似的數據，這就是k-近鄰算法中k的出處，通常k是不大于20的整數。最后，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。

比較Metric

使用歐氏距離度量樣本之間特征的相似度。

算法步驟

• 計算訓練數據集中的點與當前點之間的距離；
• 按照距離遞增次序排序；
• 選取與當前點距離最小的k個點；
• 確定前k個點所在類別的出現頻率；
• 返回前k個點所出現頻率最高的類別作為當前點的預測分類。

小問題

一位女士對男士的印象可以分為：不喜歡的人、魅力一般的人、極具魅力的人；主要根據三個特征來決定印象：每年獲得的飛行?？屠锍虜?、玩視頻游戲所消耗時間百分比、每周消費的冰淇淋公升數；

代碼

數據預處理，符號化

# 讀取數據，并符號化
def file2matrix(filepath):
    with open(filepath, mode="r") as fr:
        arrayOLines = fr.readlines()
        # 得到文件行數
        numberOfLines = len(arrayOLines)
        # 返回的NumPy矩陣,解析完成的數據:numberOfLines行,3列
        returnMat = np.zeros((numberOfLines, 3))
        # 返回的分類標簽向量
        classLabelVector = []
        # 行的索引值
        index = 0
        for line in arrayOLines:
            line = line.strip()
            # 使用s.split(str="",num=string,cout(str))將字符串根據'\t'分隔符進行切片。
            listFromLine = line.split("\t")
            # 將數據前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特征矩陣
            returnMat[index, :] = listFromLine[0:3]
            # 根據文本中標記的喜歡的程度進行分類,1代表不喜歡,2代表魅力一般,3代表極具魅力
            if listFromLine[-1] == "didntLike":
                classLabelVector.append(1)
            elif listFromLine[-1] == "smallDoses":
                classLabelVector.append(2)
            elif listFromLine[-1] == "largeDoses":
                classLabelVector.append(3)
            index += 1
        return returnMat, classLabelVector

數據標準化，為了提出樣本的不同特征之間值范圍的影響；

# 標準化是機器學習和深度學習中的常見操作
def auto_norm(dataSet):
    # 獲得數據的最小值
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    # 最大值和最小值的范圍
    ranges = maxVals - minVals
    # shape(dataSet)返回dataSet的矩陣行列數
    normDataSet = np.zeros(np.shape(dataSet))
    # 返回dataSet的行數
    m = dataSet.shape[0]
    # np.tile 鋪瓷磚函數
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    normDataSet = normDataSet / np.tile(ranges, (m, 1))
    return normDataSet, ranges, minVals

測試

# 返回一個測試樣本的分類結果
def classify0(test_set, train_set, labels, k):
    # numpy函數shape[0]返回dataSet的行數
    dataSetSize = train_set.shape[0]
    # 在列向量方向上重復inX共1次(橫向),行向量方向上重復inX共dataSetSize次(縱向)
    # 這里如果test_set不是一條數據，就是一種粗粒度的比較
    diffMat = np.tile(test_set, (dataSetSize, 1)) - train_set
    # 二維特征相減后平方
    sqDiffMat = diffMat**2
    # sum()所有元素相加,sum(0)列相加,sum(1)行相加
    sqDistances = sqDiffMat.sum(axis=1)
    # 開方,計算出距離
    distances = sqDistances**0.5
    # 返回distances中元素從小到大排序后的索引值
    sortedDistIndices = distances.argsort()
    # 定一個記錄類別次數的字典
    classCount = {}
    for i in range(k):
        # 取出前k個元素的類別
        voteIlabel = labels[sortedDistIndices[i]]
        # dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值。
        # 計算類別次數
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # reverse降序排序字典
    sortedClassCount = sorted(
        classCount.items(), key=lambda item: item[1], reverse=True
    )
    # 返回次數最多的類別,即所要分類的類別
    return sortedClassCount[0][0]

# 給定一個男人的三個特征，判斷其所屬類別
def classifyPerson():
    # 輸出結果
    resultList = ["討厭", "有些喜歡", "非常喜歡"]
    # 三維特征用戶輸入
    precentTats = float(input("玩視頻游戲所耗時間百分比:"))
    ffMiles = float(input("每年獲得的飛行?？屠锍虜?"))
    iceCream = float(input("每周消費的冰激淋公升數:"))
    # 打開的文件名
    filename = "../dataset/datingTestSet.txt"
    # 打開并處理數據
    datingDataMat, datingLabels = file2matrix(filename)
    # 訓練集歸一化
    normMat, ranges, minVals = auto_norm(datingDataMat)
    # 生成NumPy數組,測試集
    inArr = np.array([ffMiles, precentTats, iceCream])
    # 測試集歸一化
    norminArr = (inArr - minVals) / ranges
    # 返回分類結果
    classifierResult = classify0(norminArr, normMat, datingLabels, 3)
    # 打印結果
    print("你可能%s這個人" % (resultList[classifierResult - 1]))


if __name__ == "__main__":
    classifyPerson()

參考

參考 內涵數據集下載地址。