機器學習：K近鄰演算法（KNN）

K近鄰演算法（KNN，K-NearestNeighbor）是機器學習或數據分析中最基礎、也是最簡單的演算法之一，這個演算法的思路就如同它字面上的意思“K個最近的鄰居”，想要得到某個樣本的某個特征的值（一個樣本通常有多個特征），就需要找到距離它最近的K個樣本，然後根據這些樣本的該特征的近似值作為它的特征值。 ...

K近鄰演算法（KNN，K-NearestNeighbor）是機器學習或數據分析中最基礎、也是最簡單的演算法之一，這個演算法的思路就如同它字面上的意思“K個最近的鄰居”，想要得到某個樣本的某個特征的值（一個樣本通常有多個特征），就需要找到距離它最近的K個樣本，然後根據這些樣本的該特征的近似值作為它的特征值。
樣本和特征：通常來講，可以理解為一個表格數據中一行數據為一個樣本，一列數據為這個樣本的一個特征，就像資料庫中的記錄和欄位的關係。
距離和K值：這個演算法的關鍵點在於距離的計算方法和K值的選取，距離的計算方式可以根據實際情況自定義，比如使用兩個樣本的某個特征值的差值絕對值作為這兩個樣本之間的距離，也可以使用比較通用的歐式距離計算方式，或者直接使用某些庫自帶的距離計算方式，如scipy庫中就有計算距離的方法“from scipy.spatial import distance”，這幾種距離的計算方式在本文示例中都有講解，可以參考下。關於K值的選取，通常不宜過大，K值太大時，準確率會隨之降低，通常選擇3-10就足夠了。
優點和缺點：優點就是思路簡單，易於實現，理解了這個演算法後，可以不用複雜的公式也能計算出來。缺點是需要計算每個樣本與自身之間的距離，當樣本數量較大時，計算量也隨之增大，而且當樣本之間的特征不平衡時，得出的結果的偏差也會隨之增大。
註：機器學習中會涉及許多數學中的概念，如果有不清楚的地方，可能是學過但忘了，也可能是以前就沒接觸過，可以再去複習一下，或者乾脆就重新學習一下，本文就不再詳細講解了。

本文將根據一個示例來實現和講解K近鄰演算法，示例的需求是這樣的：我手中有一套房子需要出租，但是價格不知道定為多少是最合適的，現在需要參考其他房東的出租信息來制定我的出租價格。示例將分為以下幾部分內容來講解：

KNN演算法實現
模型評估
基於多變數KNN模型

KNN演算法實現

數據準備
需要準備的數據為其他房東的出租數據，我們將會根據這些數據作為參考得出自己房子的合適出租價格，這裡準備的少量數據只是為了演示用，實際上應該多準備一些數據，得出的價格才能更加精確。

import pandas as pd

# 假設這些是我們獲取到的租房信息
rental_info = {
    'url': ['https://www.airbnb.com/rooms/975833', 'https://www.airbnb.com/rooms/295345', 'https://www.airbnb.com/rooms/295346',
            'https://www.airbnb.com/rooms/333613', 'https://www.airbnb.com/rooms/805961', 'https://www.airbnb.com/rooms/7087327',
            'https://www.airbnb.com/rooms/8249488', 'https://www.airbnb.com/rooms/8409022', 'https://www.airbnb.com/rooms/8411173',
            'https://www.airbnb.com/rooms/8634774', 'https://www.airbnb.com/rooms/8498095', 'https://www.airbnb.com/rooms/8513660',
            'https://www.airbnb.com/rooms/8298145', 'https://www.airbnb.com/rooms/1745866', 'https://www.airbnb.com/rooms/7678268',
            'https://www.airbnb.com/rooms/8457865', 'https://www.airbnb.com/rooms/6757134', 'https://www.airbnb.com/rooms/8479636',
            'https://www.airbnb.com/rooms/2310297', 'https://www.airbnb.com/rooms/6556520', 'https://www.airbnb.com/rooms/8519782',
            'https://www.airbnb.com/rooms/8606980', 'https://www.airbnb.com/rooms/8485995', 'https://www.airbnb.com/rooms/8607216',
            'https://www.airbnb.com/rooms/8568945', 'https://www.airbnb.com/rooms/1026034', 'https://www.airbnb.com/rooms/2486785',
            'https://www.airbnb.com/rooms/1822257', 'https://www.airbnb.com/rooms/5220279', 'https://www.airbnb.com/rooms/3419118'],
    'name': ['Historic DC Condo-Walk to Capitol!', 'Spacious Capitol Hill Townhouse', 'Spacious/private room for single',
             'A wonderful bedroom with library', 'Downtown Silver Spring', 'Exclusive Catamaran Houseboat', 
             'Cozy DC Condo, Close to Metro!', 'Warm and Cozy 1 Bedroom Apt', 'Private room for rent',
             'Elite Room w/private bath Eden Park', 'Takoma Comfort, DC Convenience', 'Great Penthouse View! Metro in 7min',
             'Sunny & Conveniently Located!', 'Beautiful Private High-Rise Apt', 'Renaissance Rm shared bath Eden PK',
             'Cozy private second floor', 'Cheap room near Fort Totten Metro', 'Near Washington,DC',
             'Sweet basement suite apartment', 'Etta Mae Inn B&B - The Kiera room', 'All the comfort you need.',
             'Etta Mae Inn B&B - The Phoenix room', 'Sunny Cape Cod minutes from DC', 'CHIC DC URBAN RETREAT',
             'Perfect studio in VERY central DC', 'Logan Circle Loft 1bedroom, 1.5bath', 'Updated 2BD Rowhome Steps to Metro',
             'Cozy Apt in the Heart of Hipsterdom', 'Beautiful room in amazing location!', 'Clean Studio - Next to Conv Center!'],
    'host_id': [15830506, 5338703, 1487418, 16970249, 30369828, 951119, 4628, 3671500, 5159038, 347309, 9188872, 21704152, 
                44519208, 3736766, 347309, 44659281, 11798122, 34290236, 4218349, 45276150, 44546458, 45276150, 2245859, 
                966914, 2070536, 12725500, 9540128, 22207701, 12772446, 4240274],
    'accommodates': [4, 6, 1, 2, 4, 4, 4, 2, 2, 2, 4, 1, 2, 2, 2, 2, 1, 2, 4, 2, 2, 2, 7, 1, 4, 4, 3, 4, 2, 2],
    'bedrooms': [4, 6, 1, 2, 4, 4, 4, 2, 2, 2, 4, 1, 2, 2, 2, 2, 1, 2, 4, 2, 2, 2, 7, 1, 4, 4, 3, 4, 2, 2],
    'bathrooms': [1, 3, 2, 1, 1, 1, 2, 1, 1.5, 2, 1.5, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1.5, 1, 1, 1, 1],
    'beds': [2, 3, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 3, 1, 2, 1, 2, 2, 1, 1],
    'price': ['$160.00 ', '$350.00 ', '$50.00 ', '$95.00 ', '$50.00 ', '$99.00 ', '$100.00 ', '$100.00 ', '$38.00 ', 
              '$71.00 ', '$97.00 ', '$55.00 ', '$50.00 ', '$99.00 ', '$60.00 ', '$52.00 ', '$23.00 ', '$200.00 ', 
              '$40.00 ', '$135.00 ', '$100.00 ', '$225.00 ', '$129.00 ', '$149.00 ', '$150.00 ', '$175.00 ', '$239.00 ', 
              '$65.00 ', '$71.00 ', '$80.00 '],
    'minimum_nights': [1, 2, 2, 1, 7, 1, 3, 1, 2, 2, 4, 3, 2, 7, 2, 1, 1, 1, 1, 1, 1, 1, 14, 3, 2, 1, 5, 2, 2, 1],
    'maximum_nights': [1125, 30, 1125, 1125, 1125, 1125, 1125, 1125, 180, 365, 1125, 1125, 14, 1125, 1125, 1125, 
                       1125, 1125, 1125, 1125, 1125, 1125, 1125, 31, 365, 1125, 1125, 1125, 14, 1125],
    'number_of_reviews': [0, 65, 1, 0, 0, 0, 0, 0, 1, 4, 5, 1, 0, 0, 2, 1, 1, 0, 0, 0, 0, 0, 0, 46, 84, 25, 4, 2, 83, 19],
    'cleaning_fee': ['$115.00 ', '$100.00 ', '$100.00', '$15.00 ', '$15.00 ', '$50.00 ', '$50.00 ', '$10.00 ', 
                     '$10.00 ', '$10.00 ', '$50.00 ', '$20.00 ', '$20.00 ', '$125.00 ', '$10.00 ', '$5.00', '$5.00 ', 
                     '$99.00 ', '$99.00 ', '$99.00 ', '$99.00 ', '$99.00 ', '$99.00 ', '$30.00 ', '$30.00 ', '$25.00 ', 
                     '$50.00 ', '$12.00 ', '$12.00 ', '$12.00 '],
    'zipcode': [20003, 20003, 20782, 20024, 20910, 20024, 20012, 20712, 20743, 20912, 20912, 20910, 20910, 20910, 
                20912, 20712, 20782, 20910, 20712, 20912, 20712, 20912, 20912, 20008, 20005, 20005, 20001, 20001, 20001, 20001]
}

# 如果數據是存放在類似csv格式的文本文件中，可以使用pd.read_csv('xxx.csv')來讀取數據
rental_df = pd.DataFrame(rental_info)
# 選取我們需要參考的信息：accommodates（可以容納的房客數量），bedrooms（卧室數量），bathrooms（衛生間數量），
# beds（床的數量），price（房租價格），minimum_nights（房客最少租了多少天），maximum_nights（房客最多租了多少天），
# number_of_reviews（評論數量）
key_info = ['accommodates', 'bedrooms', 'bathrooms', 'beds', 'price', 'minimum_nights', 'maximum_nights', 'number_of_reviews']
keyinfo_df = rental_df[key_info]
# 查看前五條數據
keyinfo_df.head()

距離計算
假設我們以卧室數量作為參考，我們自己的房子有4個卧室，那麼我們的房子與其他房東的房子的距離可以使用歐式距離計算方式，由於我們只有卧室數量這個單一變數，所以就可以簡單計算為兩者數量的差的絕對值。歐式距離公式如下：

註：其中q1-qn為一條數據（樣本）的n個特征信息，p1-pn為另一條數據（樣本）的特征信息，由此公式便可同時根據多個變數（多個特征）計算出兩個樣本之間的距離。

import numpy as np

my_bedrooms = 4
# 新加一列用以存放其他的房子與我們自己房子的距離
keyinfo_df['distance'] = np.abs(keyinfo_df['accommodates'] - my_bedrooms)
# 統計這些距離值併排序，以便查看
print(keyinfo_df['distance'].value_counts().sort_index())
keyinfo_df.head()

可以看出，與我們房子的卧室數量相同的有9個。

選擇K個近鄰算出價格
我們這裡指定K=5，即選擇5個與我們距離最近的房子作為參考，並算出近似值作為我們出租房子的參考價格。

# 將價格列的字元串去掉$符並轉換為float類型
keyinfo_df['price'] = keyinfo_df['price'].str.replace('$', '').astype(float)
# sample函數具有“洗牌”的功能，先打亂數據的順序，再返回指定的數據量，frac=1表示返回100%的數據，random_state為隨機數種子
keyinfo_df = keyinfo_df.sample(frac=1, random_state=0)
# 按照distance列排序
keyinfo_df = keyinfo_df.sort_values('distance')
# 這裡近似值的演算法我們採用求平均的方式，即選擇與我們距離最近的5個房子的價格計算平均值
my_price = keyinfo_df['price'].iloc[:5].mean()
my_price

輸出結果：105.8

結論：以卧室數量作為參考，我們可以將房子的出租價格定在105.8左右。

模型評估

模型即我們的這個演算法，對於上面這種實現方式，到底可不可靠？在不同的數據中計算得出的結果的誤差有多大？這就是模型評估需要做的事。
為了評估模型（演算法），我們需要將數據打亂之後分為兩組，一組作為訓練集（數據量占比較大），一組作為測試集（數據量占比較小），訓練集數據用來優化改進我們的演算法模型，測試集用來驗證我們的演算法模型。
驗證方法為通過計算我們測試集數據得出的結果與測試集中原本的實際數據之間的誤差來驗證演算法模型的可靠性，誤差越小，則越可靠，這裡我們採用的誤差計算方式為均方根（RMSE，Root Mean Squared Error），計算公式如下：

註：actual表示實際值，predicted表示預測出來的值，1-n表示不同的樣本，最終的值表示通過多個樣本計算出來總體誤差值。

keyinfo_df = keyinfo_df.sample(frac=1, random_state=0)  # 再次打亂數據
keyinfo_df.drop('distance', axis=1)  # 刪除distance列
train_df = keyinfo_df.copy().iloc[:20]  # 選取前20條數據作為訓練集
test_df = keyinfo_df.copy().iloc[20:]  # 選取後10條數據作為測試集


def predict_price(feature_value, feature_name):
    """
    根據特征值feature_value，在訓練集中根據指定特征feature_name得出預測的價格
    """
    temp_df = train_df
    temp_df['distance'] = np.abs(temp_df[feature_name] - feature_value)
    temp_df = temp_df.sort_values('distance')
    my_price = temp_df['price'].iloc[:5].mean()
    return my_price

# 以測試集中的每條數據的卧室數量作為“我們自己的房子的卧室數量”，去訓練集中計算得出參考價格
test_df['my_price'] = test_df['accommodates'].apply(predict_price, feature_name='accommodates')
# 根據公式計算均方根誤差
test_df['squared_price'] = (test_df['price'] - test_df['my_price']) ** 2
mean_value = test_df['squared_price'].mean()
rmse = mean_value ** (1/2)
rmse

輸出結果：101.82695124572865

單個誤差值看不出什麼意義，需要多個特征之間誤差值聯合起來一起看才有意義，誤差值更小的那種計算方式通常更為可靠。

# 根據多個特征分別計算這種演算法模型的均方根誤差
for feature in ['accommodates','bedrooms','bathrooms','number_of_reviews']:
    test_df['my_price'] = test_df[feature].apply(predict_price, feature_name=feature)
    test_df['squared_price'] = (test_df['price'] - test_df['my_price']) ** 2
    mean_value = test_df['squared_price'].mean()
    rmse = mean_value ** (1/2)
    print('{}: {}'.format(feature, rmse))

accommodates: 101.82695124572865
bedrooms: 101.82695124572865
bathrooms: 99.81280478976633
number_of_reviews: 87.14700224333595

基於多變數KNN模型

基於多變數的KNN模型意思是同時參考多個特征來選取距離自己最近的K個樣本，即需要同時參考多個特征來計算與自己的距離，這種情況通常不會再自己寫計算距離的演算法了，而是藉助於其他已經實現好的庫，比如scipy庫中的distance模塊“scipy.spatial.distance”或者sklearn庫中的neighbors模塊“sklearn.neighbors”。以下就來介紹一下如何使用這兩個庫來實現KNN演算法。

數據準備：標準化和歸一化

# 重新獲取數據
key_info = ['accommodates', 'bedrooms', 'bathrooms', 'beds', 'price', 'minimum_nights', 'maximum_nights', 'number_of_reviews']
keyinfo_df = rental_df[key_info]
keyinfo_df['price'] = keyinfo_df['price'].str.replace('$', '').astype(float)
keyinfo_df.head()

from sklearn.preprocessing import StandardScaler

# 去除數據中的空值，示例中雖然沒有空值，但實際操作中應該有這一步，至少要處理一下空值
keyinfo_df = keyinfo_df.dropna()
# 將數據歸一化和標準化，這裡採用的處理方式是StandardScaler中的fit_transform方法，即均值方差歸一化
# 這種歸一化方法會使得數據集的方差為1，均值為0，符合標準正態分佈，公式為：X=(x-μ)/σ
# 可以發現處理後的數據它們之間的差值變小了，這樣的話使用歐式距離計算的誤差就會更小了
keyinfo_df[key_info] = StandardScaler().fit_transform(keyinfo_df[key_info])
# 這裡只是另外起一個變數名稱，表示它已經是標準化的數據了
normalized_df = keyinfo_df
normalized_df.head()

使用scipy.spatial.distance計算距離
scipy庫中的distance模塊有多種計算距離的方法，這裡使用cdist()方法進行計算，這個方法預設也是採用歐氏距離的計算方式，當然也可以通過指定metric參數更換距離計算方式，具體支持的距離計算方式可以自行去查閱API文檔，這裡就不單獨介紹了。

from scipy.spatial import distance

normal_train_df = normalized_df.copy().iloc[:20]
normal_test_df = normalized_df.copy().iloc[20:]


def predict_price_multi(feature_values, feature_names):
    """
    根據多個特征值feature_values，在訓練集中根據指定的多個特征feature_names得出預測的價格
    """
    temp_df = normal_train_df
    # distance.cdist用於計算兩組數據之間的距離，可使用metric參數指定距離的計算方式，預設為euclidean（歐幾裡得距離，即歐式距離）
    temp_df['distance'] = distance.cdist(temp_df[features], [feature_values[feature_names]])
    temp_df = temp_df.sort_values('distance')
    my_price = temp_df['price'].iloc[:5].mean()
    return my_price

# 同時使用多個特征參與距離的計算
features = ['accommodates', 'bedrooms', 'bathrooms']
normal_test_df['my_price'] = normal_test_df[features].apply(predict_price_multi, feature_names=features, axis=1)
# 根據公式計算均方根誤差
normal_test_df['squared_price'] = (normal_test_df['price'] - normal_test_df['my_price']) ** 2
mean_value = normal_test_df['squared_price'].mean()
rmse = mean_value ** (1/2)
rmse

輸出結果：0.925497918931224
註：可以看到，通過數據的標準化和歸一化，最後計算出來的均方根誤差值完全不一樣了，小了很多，這樣也能更符合我們對於誤差的比較和判斷方式了。

使用sklearn.neighbors實現KNN
sklearn庫是Python中機器學習的庫，大多機器學習的操作和演算法在sklearn中都能找到，當然也包括KNN演算法，而且都已經封裝好了，我們只需要拿來用就行了。

from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error

features = ['accommodates', 'bedrooms', 'bathrooms']
# 創建一個KNN回歸器，預設k=5，即參數n_neighbors=5
knr = KNeighborsRegressor()
# 傳入訓練集和目標值
knr.fit(normal_train_df[features], normal_train_df['price'])
# 根據提供的測試集算出目標值
feature_predict = knr.predict(normal_test_df[features])
# 計算均方根誤差
mse = mean_squared_error(normal_test_df['price'], feature_predict)
rmse = mse ** (1/2)
rmse

輸出結果：1.139347164704861