KNN算法的實現 -开发者知识库

KNN算法的實現 -开发者知识库,第1张

K近鄰(KNN)算法簡介

  KNN是通過測量不同特征值之間的距離進行分類。它的思路是:如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬於某一個類別,則該樣本也屬於這個類別,其中K通常是不大於20的整數。KNN算法中,所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

     下面通過一個簡單的例子說明一下:如下圖,綠色圓要被決定賦予哪個類,是紅色三角形還是藍色四方形?如果K=3,由於紅色三角形所占比例為2/3,綠色圓將被賦予紅色三角形那個類,如果K=5,由於藍色四方形比例為3/5,因此綠色圓被賦予藍色四方形類。

                      KNN算法的實現 -开发者知识库,第2张

由此也說明了KNN算法的結果很大程度取決於K的選擇。

     在KNN中,通過計算對象間距離來作為各個對象之間的非相似性指標,避免了對象之間的匹配問題,在這里距離一般使用歐氏距離或曼哈頓距離:

                      KNN算法的實現 -开发者知识库,第3张

同時,KNN通過依據k個對象中占優的類別進行決策,而不是單一的對象類別決策。這兩點就是KNN算法的優勢。

   接下來對KNN算法的思想總結一下:就是在訓練集中數據和標簽已知的情況下,輸入測試數據,將測試數據的特征與訓練集中對應的特征進行相互比較,找到訓練集中與之最為相似的前K個數據,則該測試數據對應的類別就是K個數據中出現次數最多的那個分類,其算法的描述為:

1)計算測試數據與各個訓練數據之間的距離;

2)按照距離的遞增關系進行排序;

3)選取距離最小的K個點;

4)確定前K個點所在類別的出現頻率;

5)返回前K個點中出現頻率最高的類別作為測試數據的預測分類。

Python實現

 

KNN算法的實現 -开发者知识库,第4张
import pandas as pddef maxminNormalization(data):
  """標准化
  data = (data - data.mean) / data.std
  :return data
  """
    mean_vals = data.mean(axis=0)
    std_val = data.std(axis=0)
    data = (data - mean_vals) / std_val
    return data


class KNN():
    def __init__(self,k=1):
        self.k = k

    def fit(self,x_train,y_train):
        self.x_train = x_train
        self.y_train = y_train

    def predict(self,x_test):
        dis_squar = (x_train - x_test)**2
        dis_squar_sum = dis_squar.sum(axis=1)
        distances = dis_squar_sum**0.5
        sortedIndics = distances.argsort()
        indices = sortedIndics[:self.k]
        labelCount = {}  # 存儲每個label的出現次數
        for i in indices:
            label = self.y_train[i]
            labelCount[label] = labelCount.get(label, 0)   1  # 次數加一
        # 排序方式一
        # sortedCount = list(zip(labelCount.values(),labelCount.keys()))
        # 對label出現的次數從大到小進行排序
        # sortedCount.sort()
        # return sortedCount[0][1]  # 返回出現次數最大的label
        # 排序方式二
        sortedCount = sorted(labelCount.items(), key=lambda k:k[1], reverse=True)
        return sortedCount[0][0]  # 返回出現次數最大的label


if __name__ == '__main__':
    # data = np.arange(24).reshape(4,6)
    train = pd.DataFrame({'age':[23,33,45],'income':[5000,12000,13000],'work':[1,2,3]})
    test = pd.DataFrame({'age':[22,30,40],'income':[9000,13000,14000],'work':[2,1,2]})
    x_train = maxminNormalization(train[['age','work']])
    y_train = train['income']
    x_test = maxminNormalization(test[['age','work']])
    y_test = test['income']
    knn = KNN()
    knn.fit(x_train,y_train)
    y_predict = knn.predict(x_test)
    print(y_predict)

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复