化學資訊學入門與實作：k-NN (k-近鄰演算法) 的介紹與應用
回歸問題與分類問題
在監督式學習中，預測連續資料的方法稱為「回歸」。 例如，預測物性值（溶解度…等）的模型就是回歸問題。例如之前介紹過的線性回歸：
另一方面，將資料分為幾個類別稱為「分類」。 在我們這次要處理的問題中，我們將把化合物分為「負」和「正」，因此這是一種二元分類問題（binary classification）。
用於分類的機器學習方法有多種，但這次我們將重點放在一種稱為「k-近鄰演算法 (k-Nearest Neighbor, k-NN)」的方法。 此實作使用了 RDkit 計算分子指紋 與 scikit-learn 來建構一個 QSAR 模型。
關於 QSAR/QSPR 與分子指紋可以參考之前的文章：
k-近鄰演算法
k-近鄰演算法被認為是最簡單的學習演算法。演算法是分兩個階段完成的：
- 將資料集放置在特徵空間中（學習）
- 從附近 k 個數據點的值決定新點的值（預測）
也就是說根據數據點彼此之間的距離來進行分類，距離哪一種類別最近則該數據點就會被分到哪一類。
我們可以藉由改變 k 的值來改變結果，由下圖，我可以看出 k 值得影響：
當 k=1 時：與最近的一個點是紅點，所以被分類為「紅色」。
當 k=3 時：最接近的三個點是紅3藍1，因此透過多數決將分類為「紅色」。
當 k=5 時：最接近的五個點是紅3藍5，因此透過多數決將分類為「藍色」。
所以 k 的值是 k 近鄰法中最重要的參數。另外，有些人可能對使用什麼樣的「距離」感興趣，常見的距離計算方式如下幾種：
1.歐幾里德距離(Euclidean distance)
2.曼哈頓距離(Manhattan distance)
3.明氏距離(Minkowski distance)
當 p=1 時，為曼哈頓距離
當 p=2 時，為歐幾里德距離
但預設設定「歐幾里德距離」通常就足夠了。
準備數據
我們將使用以下論文所附的數據集進行建模。
「Benchmark Data Set for in Silico Prediction of Ames Mutagenicity」
J. Chem. Inf. Model. 2009, 49, 9, 2077–2081
(DOI: 10.1021/ci900161g)
利用 RDKit 與 scikit-learn 的k-NN模型進行建模
先導入需要用到的一些 library，把 Ames 數據集載入為 pandas.DataFrame :
from rdkit import rdBase, Chem
from rdkit.Chem import AllChem, Draw, PandasTools
from rdkit.Chem.Draw import IPythonConsole
import pandas as pd
import numpy as np
df = pd.read_csv('ames.csv',index_col=0)
df.head()其輸出為：
確認一下 Activity 的狀況，在 5,907 個分子中，其中 3,208 個分子為陽性（Activity = 1），2,699 個分子為陰性（Activity = 0）。（原本數據集有 6,512 分子，進行一些前處理把無法讀取分子去除之後，剩下 5,907 個分子）
再來是利用 PandasTools.AddMoleculeColumnToFrame 把 DataFrame 中 smiles 格式的分子轉換回 Mol 的形式。
PandasTools.AddMoleculeColumnToFrame(frame=df, smilesCol='Smiles')檢視一下輸出結果：
接著，我們利用 RDKit 來計算 Morgan fingerprint 。子構造範圍設定為 radius = 2，向量長度為 1024 位元。然後將資料分割成 training data 和 test data。
from sklearn.model_selection import train_test_split
morgan_fps = []
for mol in df.ROMol:
fp = [x for x in AllChem.GetMorganFingerprintAsBitVect(mol, 2, 1024)]
morgan_fps.append(fp)
morgan_fps = np.array(morgan_fps)
target = df['Activity']
X_train, X_test, y_train, y_test = train_test_split(morgan_fps, target, random_state=0)確認一下數據的狀態：
Training data 資料量為 4,430 筆，特徵量的數量為 1,024，Teat data 資料量為 282 筆。
- 使用 scikit-learn 中的 k-NN 模型
在 k-NN 中，「考慮 k 的鄰近點的數量」是一個變數。 在下面的範例中，我們測試 k = 1 到 k = 10，並比較 training data 和 test data 的準確性。
from sklearn.neighbors import KNeighborsClassifier
morgan_train_acc = []
morgan_test_acc = []
for i in range(1,11):
knn = KNeighborsClassifier(n_neighbors=i)
knn.fit(X_train, y_train)
train_acc = knn.score(X_train, y_train)
test_acc = knn.score(X_test, y_test)
print('test accuracy with k={}: {:.3f}'.format(i, test_acc))
morgan_train_acc.append(train_acc)
morgan_test_acc.append(test_acc)test accuracy with k=1: 0.752
test accuracy with k=2: 0.741
test accuracy with k=3: 0.771
test accuracy with k=4: 0.773
test accuracy with k=5: 0.793
test accuracy with k=6: 0.780
test accuracy with k=7: 0.785
test accuracy with k=8: 0.775
test accuracy with k=9: 0.787
test accuracy with k=10: 0.771
從 k = 1 嘗試到 k = 10的結果，最佳模型是“ k = 5 ”，它對 test data 具有最高的準確性。
我們把 training data 和 test data 的準確性畫成圖做個比較：
import matplotlib.pyplot as plt
ks = [i for i in range(1,11)]
plt.plot(ks,morgan_train_acc)
plt.plot(ks,morgan_test_acc)
plt.show()
我們會發現當 k=1 時，training data 的準確率是幾乎是完美，但對 test data 的準確率較低，這正是分類模型的過度擬合 (over-fitting) 現象。為了避免過度擬合，使用 test data 驗證模型是相當重要的步驟。
結語
在本文中，我們簡單介紹了k-NN 的基本概念。然後用 Ames 數據簡單地構築了 QSAR 分類模型。另外，我們也能發現在 training data 上準確率高的模型在 test data 上不一定有很好的準確率。
