摘要：而代碼是給出現(xiàn)情況增加次數(shù)，出現(xiàn)一次排序?qū)脒\(yùn)算符模塊的方法，按照第二個(gè)元素的次序?qū)υM進(jìn)行排序，此處的排序?yàn)槟嫘颉?/p>

k近鄰是一種基本分類與回歸方法.

輸入:特征向量

輸出:實(shí)例的類別(可取多類)

核心思想:如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性.

優(yōu)點(diǎn):計(jì)算精度高、對(duì)異常值不敏感、無(wú)數(shù)據(jù)輸入假定

缺點(diǎn):計(jì)算復(fù)雜度高、空間復(fù)雜度高

適用范圍:數(shù)值型和標(biāo)稱型

收集數(shù)據(jù)
準(zhǔn)備數(shù)據(jù)：距離計(jì)算所需要的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式
分析數(shù)據(jù)：可以適用任何方法
訓(xùn)練算法：此步驟不適用于KNN
測(cè)試算法：計(jì)算錯(cuò)誤率
使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運(yùn)行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個(gè)分類，最后應(yīng)用對(duì)計(jì)算出的分類執(zhí)行后續(xù)的處理

構(gòu)造數(shù)據(jù)集

import numpy as np

def create_data_set():
    """構(gòu)造數(shù)據(jù)集"""
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    label = ["A", "A", "B", "B"]
    return group, label

生成數(shù)據(jù)集

group, label = create_data_set()

實(shí)現(xiàn)kNN算法偽代碼

對(duì)未知類別屬性的數(shù)據(jù)集種的每個(gè)點(diǎn)依次執(zhí)行以下步驟：

1. 計(jì)算已知類別屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)與當(dāng)前點(diǎn)之間的距離

2. 按照距離遞增次序排序

3. 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)

4. 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率

5. 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類
?

import operator

def classify0(inX, data_set, label, k):
    """
    KNN算法
    :param inX: 用于分類的輸入向量
    :param data_set: 訓(xùn)練樣本集
    :param label: 訓(xùn)練標(biāo)簽向量
    :param k: 選取最近鄰居的數(shù)量
    :return: k個(gè)鄰居里頻率最高的分類
    """

    """距離計(jì)算"""
    # 獲得樣本量
    data_set_size = data_set.shape[0]
    # tile：在行方向重復(fù)inX,dataSetSize次，在列方向上重復(fù)inX,1次
    diff_mat = np.tile(inX, (data_set_size, 1)) - data_set
    # 離原點(diǎn)的距離，相見后平方
    sq_diff_mat = diff_mat ** 2
    # x軸和y軸差的平方和
    sq_distances = sq_diff_mat.sum(axis=1)
    # 然后開方
    distances = sq_distances ** 0.5
    # argsort函數(shù)返回的是數(shù)組值從小到大的索引值
    sorted_distance_index = distances.argsort()
    class_count = {}
    """選擇距離最小的點(diǎn)"""
    for i in range(k):
        # 返回距離最近的第i個(gè)樣本所對(duì)應(yīng)的標(biāo)簽
        vote_label = label[sorted_distance_index[i]]
        # print(voteIlabel)
        # print(classCount.get(voteIlabel, 0))
        # 這里的0是設(shè)置默認(rèn)值為0,而代替None。而代碼是給出現(xiàn)情況增加次數(shù)，出現(xiàn)一次+1
        class_count[vote_label] = class_count.get(vote_label, 0) + 1
        # print(classCount)
    """排序"""
    # 導(dǎo)入運(yùn)算符模塊的itemgetter方法，按照第二個(gè)元素的次序?qū)υM進(jìn)行排序，此處的排序?yàn)槟嫘颉?    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    # 返回頻率最大的Label
    return sorted_class_count[0][0]

添加算法測(cè)試代碼

classify0([0, 0], group, label, k=3)

加載并解析數(shù)據(jù)

# 將文本記錄轉(zhuǎn)換為numpy的解析程序
def file2matrix(filename):
    fr = open(filename)
    # readlines把文件所有內(nèi)容讀取出來(lái)，組成一個(gè)列表，其中一行為一個(gè)元素
    array_of_lines = fr.readlines()
    number_of_lines = len(array_of_lines)
    # 返回一個(gè)用1000行每行3個(gè)0填充的數(shù)組，形成特征矩陣
    return_mat = np.zeros((number_of_lines, 3))
    class_label_vector = []
    for index, line in enumerate(array_of_lines):
        # 去除每行前后的空格
        line = line.strip()
        # 根據(jù)	把每行分隔成由四個(gè)元素組成的列表
        list_from_line = line.split("	")
        # 選取前3個(gè)元素，將它們按順序存儲(chǔ)到特征矩陣中
        return_mat[index, :] = list_from_line[0: 3]
        # 將列表的最后一個(gè)元素儲(chǔ)存到class_label_vector中去，儲(chǔ)存的元素值為整型
        class_label_vector.append(int(list_from_line[-1]))
    return return_mat, class_label_vector

獲得解析數(shù)據(jù)

dating_data_mat, dating_labels = file2matrix("datingTestSet2.txt")

使用Matplotlib創(chuàng)建散點(diǎn)圖

import matplotlib.pyplot as plt

# 創(chuàng)建Figure實(shí)例
fig = plt.figure()
# 添加一個(gè)子圖，返回Axes實(shí)例
ax = fig.add_subplot(111)  # 選取最近鄰居的數(shù)量
# 生成散點(diǎn)圖，x軸使用dating_data_mat第二列數(shù)據(jù)，y軸使用dating_data_mat的第三列數(shù)據(jù)
# ax.scatter(x=dating_data_mat[:, 1], y=dating_data_mat[:, 2])
# 個(gè)性化標(biāo)記散點(diǎn)圖，形狀(s)和顏色(c)
ax.scatter(x=dating_data_mat[:, 1], y=dating_data_mat[:, 2], s=15.0 * np.array(dating_labels), c=np.array(dating_labels))
plt.show()

歸一化特征值

def auto_num(data_set):
    """
    歸一化特征值
    :param data_set: 數(shù)據(jù)集
    :return 歸一化后的數(shù)據(jù)集， 列的差值范圍， 列的最小值
    """
    # 列的最小值
    min_val = data_set.min()
    # 列的最大值
    max_val = data_set.max()
    # 列的差值范圍
    range_s = max_val - min_val
    # 構(gòu)造返回矩陣
    norm_data_set = np.zeros(shape=np.shape(data_set))
    # m = data_set.shape[0]
    # oldValue - min
    norm_data_set = data_set - np.tile(min_val, (data_set.shape[0], 1))
    # (oldValue - min) / (max - min)
    norm_data_set = norm_data_set / np.tile(range_s, (data_set.shape[0], 1))
    return norm_data_set, range_s, min_val

歸一化測(cè)試

normalize_data_set, ranges, min_val = auto_num(dating_data_mat)
print(normalize_data_set)

測(cè)試算法

def dating_class_test():
    # 選擇測(cè)試數(shù)據(jù)量
    ho_ratio = 0.10
    # 解析數(shù)據(jù)
    dating_data_mat, dating_labels = file2matrix("datingTestSet2.txt")
    # 歸一化數(shù)據(jù)
    norm_mat, range_s, min_val = auto_num(dating_data_mat)
    # 拆分10%數(shù)據(jù)作為測(cè)試數(shù)據(jù)
    m = norm_mat.shape[0]  # 總數(shù)據(jù)量
    num_test_vec = int(m * ho_ratio)  # 測(cè)試數(shù)據(jù)量
    # 錯(cuò)誤樣本計(jì)數(shù)
    error_count = 0.0
    # 對(duì)測(cè)試數(shù)據(jù)進(jìn)行分類，并對(duì)比檢驗(yàn)結(jié)果正確率
    for i in range(num_test_vec):
        classifier_result = classify0(  # classifier_result : k個(gè)鄰居里頻率最高的分類
            norm_mat[i, :],  # 用于分類的輸入向量(測(cè)試數(shù)據(jù), : 表示一行內(nèi)所有元素)
            norm_mat[num_test_vec: m, :],  # 訓(xùn)練樣本集(從測(cè)試的數(shù)據(jù)開始到總數(shù)據(jù)量結(jié)束)
            dating_labels[num_test_vec:m],  # 訓(xùn)練標(biāo)簽向量(從測(cè)試的數(shù)據(jù)開始到總數(shù)據(jù)量結(jié)束)
            3  # 選取最近鄰居的數(shù)量
        )
        print("the classifier came back with: %d, the real answer is: %d" % (classifier_result, dating_labels[i]))
        if classifier_result != dating_labels[i]:
            error_count += 1.0
    print("the total error rate is: %f" % (error_count / float(num_test_vec)))

執(zhí)行測(cè)試

dating_class_test()

使用算法

def classify_person():
    """
    根據(jù)輸入指標(biāo)，通過分類器進(jìn)行預(yù)測(cè)喜歡程度
    :return:
    """
    result_list = ["not at all", "in small doses", "in large doses"]
    percent_tats = float(input("percentage of time spent playing vedio games?"))
    ff_miles = float(input("frequent flier miles earned per year?"))
    ice_cream = float(input("liters of ice cream consumed per year?"))
    dating_data, dating_labels = file2matrix("datingTestSet2.txt")
    normalize_matrix, ranges, min_val = auto_num(dating_data)
    # 將輸入指標(biāo)，歸一化后代入分類器進(jìn)行預(yù)測(cè)
    in_arr = np.array([ff_miles, percent_tats, ice_cream])
    print(in_arr, min_val, ranges, (in_arr-min_val)/ranges)
    print(ranges)
    classifier_result = classify0((in_arr-min_val)/ranges, normalize_matrix, dating_labels, 3)
    print("You will probably like this person: ", result_list[classifier_result - 1])

執(zhí)行函數(shù)

classify_person()

輸出

percentage of time spent playing vedio games?20
frequent flier miles earned per year?299
liters of ice cream consumed per year?1
You will probably like this person:  in large doses

sklearn中實(shí)現(xiàn)

from sklearn import neighbors

def knn_classify_person():
    """
        根據(jù)輸入指標(biāo)，通過分類器進(jìn)行預(yù)測(cè)喜歡程度
    :return:
    """
    result_list = np.array(["not at all", "in small doses", "in large doses"])
    percent_tats = float(input("percentage of time spent playing vedio games?"))
    ff_miles = float(input("frequent flier miles earned per year?"))
    ice_cream = float(input("liters of ice cream consumed per year?"))
    dating_data, dating_labels = file2matrix("datingTestSet2.txt")
    normalize_matrix, ranges, min_val = auto_num(dating_data)
    # 將輸入指標(biāo)，歸一化后代入分類器進(jìn)行預(yù)測(cè)
    in_arr = np.array([ff_miles, percent_tats, ice_cream])
    # 聲明k為3的knn算法,n_neighbors即是鄰居數(shù)量，默認(rèn)值為5
    knn = neighbors.KNeighborsClassifier(n_neighbors=3)
    # 訓(xùn)練算法
    knn.fit(normalize_matrix, dating_labels)
    # 預(yù)測(cè)
    classifier_result = knn.predict([(in_arr - min_val) / ranges])
    print("You will probably like this person: ", result_list[classifier_result - 1][0])


# 執(zhí)行函數(shù)
knn_classify_person()