machine_learning-knn算法具體解釋(近鄰算法)

近鄰算法是機器學習算法中的入門算法，該算法用于針對已有資料集對未知資料進行分類。

該算法核心思想是通過計算預測資料與已有資料的相似度猜測結果。

舉例：

如果有例如以下一組資料(在下面我們統一把該資料作為訓練資料):

身高	年齡	國籍
170	23	中國
180	21	美國
185	22	俄國
175	24
120		日本

我們将該組資料的前兩列作為一個特征值。最後一項作為一個待分類結果。當資料量足夠大時，能夠通過該資料便可得出較為精确的分類。

比如我們拿到測試資料。年齡23歲，身高172，須要預測其國籍。

一般預測的方法是通過特征值求測試資料與訓練資料中各項的差異(求點與點之間的距離)，當有x，y兩項特征值時，則距離為

注:xA0為測試資料第一特征值(身高)，xB0為訓練資料第一特征值(身高)，xA1為測試資料第二特征值(年齡)，xB1為訓練資料第二特征值(年齡)

同理，當特征項有3項時，則為(xA0 - xB0)的平方加上(xA1 - xB1)的平方再加上(xA2 - xB2)的平台，再開平方根。這個就是數學中求空間内兩個點的距離

距離近期的訓練資料則為特征最為相似的資料，該訓練資料的分類則是分類可能性最大的結果

由于資料過少，我們簡單能夠看出。通過春節齡和身高進行比對。最為相似的資料就是下面這一條。

在訓練資料較大時，須要程式進行比對分類，程式的一般邏輯是通過訓練資料集中的各項資料與測試資料進行距離計算，求出最為相似的資料。可是這樣對資料準确性的依賴太強，是以引入了近鄰的概念。則是通過最為相似的N個資料，求出這N個資料中出現機率最高的分類則是近鄰算法的結果，在本文中使用python和numpy庫實作近鄰算法。

# train_data為訓練資料集的特征值(在本次訓練資料集中為[[170, 23], [180, 21], [185, 22], [175, 24], [120, 23]])

# type_set為訓練資料集分類。與train_data順序相相應的(在本次訓練資料集中為[中國,美國,俄國,中國,日本])

# test_data為須要分類的測試資料([172, 23])

# k則為上面所述的N值

import numpy as np

def forecast_data_type(train_data, type_set, test_data, k):

    # 求出train_data長度，matrix類型的shape是矩陣各次元長度。比如[[1,2,3],[4,5,6]]為(2,3)

    train_data_size = train_data.shape[0]

    # 首先把test_data轉換成與train_data一樣的格式[[172,23], [172,23],[172,23], [172,23],[172,23]]

    test_data_set = np.tile(test_data, (train_data_size,1))

    # 求出train_data和test_data_set的差(結果為[[x1A0-x1A1,x1B0-x1B1], ......, [x4A0-x4A1,x4B0-x4B1]])

    data_diff = train_data - test_data_set

    # 對內插補點求平方(這個地方我用matrix來求平方不得行，是以我先轉成了array)

    data_diff_pow = np.mat(np.asarray(data_diff) ** 2)

    # 将平方值相加

    data_diff_pow_sum = data_diff_pow.sum(axis=1)

    # 求平方根，a的平方根就是a的1/2次方。得出距離(類似[[1.22], [0.31], [0.444]......])

    distances = np.mat(np.asarray(data_diff_pow_sum) ** 0.5)

    # 對結果進行排序，注意。argsort的傳回值是原資料索引清單

    # 比如old_data是[1, 3, 5, 2, 4]，sorted_data是[1, 2, 3, 4, 5]，

    # sorted_data[0]相應old_data[0]

    # sorted_data[1]相應old_data[3]

    # sorted_data[2]相應old_data[1]

    # sorted_data[3]相應old_data[4]

    # sorted_data[4]相應old_data[2]

    # 則argsort傳回 [0, 3, 1, 4, 2]，這個地方的axis=0是由于原來的資料不是[1, 2, 3, 4]而是[[1], [2], [3], [4]]，假設不加這個參數則會傳回[[0], [0], [0]]這樣的

    sorted_distance = distances.argsort(axis=0)

    # 通過給定的k值選擇最為相似的k個資料，我這邊用了collections庫的Counter

    list_result = []

    for i in range(k):

        # sorted_distance 是 [[2], [1], [4]...]

        list_result.append(type_set[sorted_distance [i][0]])

    count_result = Counter(list_result)

    count_result是一個有序dict，依照count的大小進行資料排序，比如{'a': 3, 'b': 2, 'c': 2}

    count_result的第一項就是分類的結果

注意: 

1.該算法較為依賴訓練資料集的大小。在一定範圍内，訓練資料量越大得到的結果最準确。

2.k值比較關鍵。當k值過大和過小時資料準确性都會受到影響。

3.當特征值的某一項差異太大時，比如a特征的值為1,2,3,4這樣。b特征的值為1000,2000,3000這樣。b特征對總體推斷的影響較大，這個時候就應該對全部特征值做歸一化處理，歸一化方法例如以下

歸一化值 = (資料特征值 - 最小特征值) / (最大特征值 - 最小特征值) ------這樣得出的特征值會<=1

比如c特征為 1000， 2000， 3000。 4000， 5000

最小特征值為1000，最大特征值為5000

那麼假設值為3000，那麼歸一化後的特征值為 (3000 - 1000) / (5000 - 1000) 為 0.5

參考資料:

1.<<機器學習實戰>>