KNN算法
用NumPy庫實現(xiàn)K-nearest neighbors回歸或分類搓幌。
鄰近算法俱饿，或者說K最近鄰(kNN杆煞，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一谋逻。所謂K最近鄰塔插，就是k個最近的鄰居的意思冠摄，說的是每個樣本都可以用它最接近的k個鄰居來代表糯崎。
kNN算法的核心思想是如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別河泳，并具有這個類別上樣本的特性沃呢。該方法在確定分類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 kNN方法在類別決策時拆挥，只與極少量的相鄰樣本有關(guān)薄霜。由于kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的纸兔，因此對于類域的交叉或重疊較多的待分樣本集來說惰瓜，kNN方法較其他方法更為適合。
簡單的理解汉矿，我有一組數(shù)據(jù)崎坊，比如每個數(shù)據(jù)都是n維向量，那么我們可以在n維空間表示這個數(shù)據(jù)洲拇，這些數(shù)據(jù)都有對應(yīng)的標(biāo)簽值奈揍，也就是我們感興趣的預(yù)測變量曲尸。那么當(dāng)我們接到一個新的數(shù)據(jù)的時候，我們可以計算這個新數(shù)據(jù)和我們已知的訓(xùn)練數(shù)據(jù)之間的距離男翰，找出其中最近的k個數(shù)據(jù)另患，對這k個數(shù)據(jù)對應(yīng)的標(biāo)簽值取平均值就是我們得出的預(yù)測值。簡單粗暴蛾绎，誰離我近昆箕，就認(rèn)為誰能代表我，我就用你們的屬性作為我的屬性租冠。具體的簡單代碼實現(xiàn)如下为严。
1. 數(shù)據(jù)
這里例子來自《集體智慧編程》給的葡萄酒的價格模型。葡萄酒的價格假設(shè)由酒的等級與儲藏年代共同決定肺稀，給定rating與age之后，就能給出酒的價格应民。
def wineprice(rating,age):
"""
Input rating & age of wine and Output it's price.
Example:
------
input = [80.,20.] ===> output = 140.0
"""
peak_age = rating - 50 # year before peak year will be more expensive
price = rating/2.
if age > peak_age:
price = price*(5 -(age-peak_age))
else:
price = price*(5*((age+1)/peak_age))
if price < 0: price=0
return price
a = wineprice(80.,20.)
a
140.0
根據(jù)上述的價格模型话原，我們產(chǎn)生n=500瓶酒及價格，同時為價格隨機加減了20%來體現(xiàn)隨機性诲锹，同時增加預(yù)測的難度繁仁。注意基本數(shù)據(jù)都是numpy里的ndarray,為了便于向量化計算，同時又有強大的broadcast功能归园，計算首選黄虱。
def wineset(n=500):
"""
Input wineset size n and return feature array and target array.
Example:
------
n = 3
X = np.array([[80,20],[95,30],[100,15]])
y = np.array([140.0,163.6,80.0])
"""
X,y = [], []
for i in range(n):
rating = np.random.random()*50 + 50
age = np.random.random()*50
# get reference price
price = wineprice(rating,age)
# add some noise
price = price*(np.random.random()*0.4 + 0.8) #[0.8,1.2]
X.append([rating,age])
y.append(price)
return np.array(X), np.array(y)
X,y = wineset(500)
X[:3]
array([[ 88.89511317, 11.63751282],
[ 91.57171713, 39.76279923],
[ 98.38870877, 14.07015414]])
2. 相似度：歐氏距離
knn的名字叫K近鄰，如何叫“近”庸诱，我們需要一個數(shù)學(xué)上的定義捻浦，最常見的是用歐式距離，二維三維的時候?qū)?yīng)平面或空間距離桥爽。
算法實現(xiàn)里需要的是給定一個新的數(shù)據(jù)朱灿，需要計算其與訓(xùn)練數(shù)據(jù)組之間所有點之間的距離，注意是不同的維度钠四，給定的新數(shù)據(jù)只是一個sample盗扒，而訓(xùn)練數(shù)據(jù)是n組，n個sample缀去，計算的時候需要注意侣灶，不過numpy可以自動broadcat，可以很好地take care of it缕碎。
def euclidean(arr1,arr2):
"""
Input two array and output theie distance list.
Example:
------
arr1 = np.array([[3,20],[2,30],[2,15]])
arr2 = np.array([[2,20],[2,20],[2,20]]) # broadcasted, np.array([2,20]) and [2,20] also work.
d = np.array([1,20,5])
"""
ds = np.sum((arr1 - arr2)**2,axis=1)
return np.sqrt(ds)
arr1 = np.array([[3,20],[2,30],[2,15]])
arr2 = np.array([[2,20],[2,20],[2,20]])
euclidean(arr1,arr2)
array([ 1., 10., 5.])
提供一個簡潔的接口褥影，給定訓(xùn)練數(shù)據(jù)X和新sample v，然后返回排序好的距離阎曹，以及對應(yīng)的index(我們要以此索引近鄰們對應(yīng)的標(biāo)簽值)伪阶。
def getdistance(X,v):
"""
Input train data set X and a sample, output the distance between each other with index.
Example:
------
X = np.array([[3,20],[2,30],[2,15]])
v = np.array([2,20]) # to be broadcasted
Output dlist = np.array([1,5,10]), index = np.array([0,2,1])
"""
dlist = euclidean(X,np.array(v))
index = np.argsort(dlist)
dlist.sort()
# dlist_with_index = np.stack((dlist,index),axis=1)
return dlist, index
dlist, index = getdistance(X,[80.,20.])
3. KNN算法
knn算法具體實現(xiàn)的時候很簡單煞檩，調(diào)用前面的函數(shù)，計算出排序好的距離列表栅贴，然后對其前k項對應(yīng)的標(biāo)簽值取均值即可斟湃。可以用該knn算法與實際的價格模型對比檐薯，發(fā)現(xiàn)精度還不錯凝赛。
def knn(X,y,v,kn=3):
"""
Input train data and train target, output the average price of new sample.
X = X_train; y = y_train
k: number of neighbors
"""
dlist, index = getdistance(X,v)
avg = 0.0
for i in range(kn):
avg = avg + y[index[i]]
avg = avg / kn
return avg
knn(X,y,[95.0,5.0],kn=3)
32.043042600537092
wineprice(95.0,5.0)
31.666666666666664
4. 加權(quán)KNN
以上是KNN的基本算法，有一個問題就是該算法給所有的近鄰分配相等的權(quán)重坛缕，這個還可以這樣改進墓猎，就是給更近的鄰居分配更大的權(quán)重(你離我更近，那我就認(rèn)為你跟我更相似赚楚，就給你分配更大的權(quán)重)毙沾，而較遠(yuǎn)的鄰居的權(quán)重相應(yīng)地減少，取其加權(quán)平均宠页。需要一個能把距離轉(zhuǎn)換為權(quán)重的函數(shù)左胞，gaussian函數(shù)是一個比較普遍的選擇，下圖可以看到gaussian函數(shù)的衰減趨勢举户。從下面的單例可以看出其效果要比knn算法的效果要好烤宙，不過只是單個例子，不具有說服力俭嘁，后面給出更可信的評價躺枕。
def gaussian(dist,sigma=10.0):
"""Input a distance and return it's weight"""
weight = np.exp(-dist**2/(2*sigma**2))
return weight
x1 = np.arange(0,30,0.1)
y1 = gaussian(x1)
plt.title('gaussian function')
plt.plot(x1,y1);
[圖片上傳失敗...(image-eee30f-1569669311449)]
def knn_weight(X,y,v,kn=3):
dlist, index = getdistance(X,v)
avg = 0.0
total_weight = 0
for i in range(kn):
weight = gaussian(dlist[i])
avg = avg + weight*y[index[i]]
total_weight = total_weight + weight
avg = avg/total_weight
return avg
knn_weight(X,y,[95.0,5.0],kn=3)
32.063929602836012
交叉驗證
寫一個函數(shù)，實現(xiàn)交叉驗證功能供填，不能用sklearn庫拐云。
交叉驗證(Cross-Validation): 有時亦稱循環(huán)估計， 是一種統(tǒng)計學(xué)上將數(shù)據(jù)樣本切割成較小子集的實用方法捕虽。于是可以先在一個子集上做分析慨丐， 而其它子集則用來做后續(xù)對此分析的確認(rèn)及驗證。 一開始的子集被稱為訓(xùn)練集泄私。而其它的子集則被稱為驗證集或測試集房揭。常見交叉驗證方法如下：
Holdout Method(保留)
- 方法：將原始數(shù)據(jù)隨機分為兩組,一組做為訓(xùn)練集,一組做為驗證集,利用訓(xùn)練集訓(xùn)練分類器,然后利用驗證集驗證模型,記錄最后的分類準(zhǔn)確率為此Hold-OutMethod下分類器的性能指標(biāo).。Holdout Method相對于K-fold Cross Validation 又稱Double cross-validation 晌端，或相對K-CV稱 2-fold cross-validation(2-CV)
- 優(yōu)點：好處的處理簡單,只需隨機把原始數(shù)據(jù)分為兩組即可
- 缺點：嚴(yán)格意義來說Holdout Method并不能算是CV,因為這種方法沒有達到交叉的思想,由于是隨機的將原始數(shù)據(jù)分組,所以最后驗證集分類準(zhǔn)確率的高低與原始數(shù)據(jù)的分組有很大的關(guān)系,所以這種方法得到的結(jié)果其實并不具有說服性.(主要原因是 訓(xùn)練集樣本數(shù)太少捅暴，通常不足以代表母體樣本的分布，導(dǎo)致 test 階段辨識率容易出現(xiàn)明顯落差咧纠。此外蓬痒，2-CV 中一分為二的分子集方法的變異度大，往往無法達到「實驗過程必須可以被復(fù)制」的要求漆羔。)
K-fold Cross Validation(k折疊)
- 方法：作為Holdout Methon的演進梧奢，將原始數(shù)據(jù)分成K組(一般是均分),將每個子集數(shù)據(jù)分別做一次驗證集,其余的K-1組子集數(shù)據(jù)作為訓(xùn)練集,這樣會得到K個模型,用這K個模型最終的驗證集的分類準(zhǔn)確率的平均數(shù)作為此K-CV下分類器的性能指標(biāo).K一般大于等于2,實際操作時一般從3開始取,只有在原始數(shù)據(jù)集合數(shù)據(jù)量小的時候才會嘗試取2. 而K-CV 的實驗共需要建立 k 個models狱掂，并計算 k 次 test sets 的平均辨識率。在實作上亲轨，k 要夠大才能使各回合中的 訓(xùn)練樣本數(shù)夠多趋惨，一般而言 k=10 (作為一個經(jīng)驗參數(shù))算是相當(dāng)足夠了。
- 優(yōu)點：K-CV可以有效的避免過學(xué)習(xí)以及欠學(xué)習(xí)狀態(tài)的發(fā)生,最后得到的結(jié)果也比較具有說服性.
- 缺點：K值選取上
Leave-One-Out Cross Validation(留一)
- 方法：如果設(shè)原始數(shù)據(jù)有N個樣本,那么留一就是N-CV,即每個樣本單獨作為驗證集,其余的N-1個樣本作為訓(xùn)練集,所以留一會得到N個模型,用這N個模型最終的驗證集的分類準(zhǔn)確率的平均數(shù)作為此下LOO-CV分類器的性能指標(biāo).
- 優(yōu)點：相比于前面的K-CV,留一有兩個明顯的優(yōu)點：
- a.每一回合中幾乎所有的樣本皆用于訓(xùn)練模型,因此最接近原始樣本的分布,這樣評估所得的結(jié)果比較可靠惦蚊。
- b. 實驗過程中沒有隨機因素會影響實驗數(shù)據(jù),確保實驗過程是可以被復(fù)制的.
- 缺點：計算成本高,因為需要建立的模型數(shù)量與原始數(shù)據(jù)樣本數(shù)量相同,當(dāng)原始數(shù)據(jù)樣本數(shù)量相當(dāng)多時,LOO-CV在實作上便有困難幾乎就是不顯示,除非每次訓(xùn)練分類器得到模型的速度很快,或是可以用并行化計算減少計算所需的時間器虾。
Holdout method方法的想法很簡單，給一個train_size,然后算法就會在指定的比例(train_size)處把數(shù)據(jù)分為兩部分蹦锋，然后返回兆沙。
# Holdout method
def my_train_test_split(X,y,train_size=0.95,shuffle=True):
"""
Input X,y, split them and out put X_train, X_test; y_train, y_test.
Example:
------
X = np.array([[0, 1],[2, 3],[4, 5],[6, 7],[8, 9]])
y = np.array([0, 1, 2, 3, 4])
Then
X_train = np.array([[4, 5],[0, 1],[6, 7]])
X_test = np.array([[2, 3],[8, 9]])
y_train = np.array([2, 0, 3])
y_test = np.array([1, 4])
"""
order = np.arange(len(y))
if shuffle:
order = np.random.permutation(order)
border = int(train_size*len(y))
X_train, X_test = X[:border], X[border:]
y_train, y_test = y[:border], y[border:]
return X_train, X_test, y_train, y_test
K folds算法是把數(shù)據(jù)分成k份，進行k此循環(huán)莉掂，每次不同的份分別來充當(dāng)測試組數(shù)據(jù)葛圃。但是注意，該算法不直接操作數(shù)據(jù)憎妙，而是產(chǎn)生一個迭代器装悲，返回訓(xùn)練和測試數(shù)據(jù)的索引∩蟹眨看docstring里的例子應(yīng)該很清楚。
# k folds 產(chǎn)生一個迭代器
def my_KFold(n,n_folds=5,shuffe=False):
"""
K-Folds cross validation iterator.
Provides train/test indices to split data in train test sets. Split dataset
into k consecutive folds (without shuffling by default).
Each fold is then used a validation set once while the k - 1 remaining fold form the training set.
Example:
------
X = np.array([[1, 2], [3, 4], [1, 2], [3, 4]])
y = np.array([1, 2, 3, 4])
kf = KFold(4, n_folds=2)
for train_index, test_index in kf:
X_train, X_test = X[train_index], X[test_index]
y_train, y_test = y[train_index], y[test_index]
print("TRAIN:", train_index, "TEST:", test_index)
TRAIN: [2 3] TEST: [0 1]
TRAIN: [0 1] TEST: [2 3]
"""
idx = np.arange(n)
if shuffe:
idx = np.random.permutation(idx)
fold_sizes = (n // n_folds) * np.ones(n_folds, dtype=np.int) # folds have size n // n_folds
fold_sizes[:n % n_folds] += 1 # The first n % n_folds folds have size n // n_folds + 1
current = 0
for fold_size in fold_sizes:
start, stop = current, current + fold_size
train_index = list(np.concatenate((idx[:start], idx[stop:])))
test_index = list(idx[start:stop])
yield train_index, test_index
current = stop # move one step forward
X1 = np.array([[1, 2], [3, 4], [1, 2], [3, 4]])
y1 = np.array([1, 2, 3, 4])
kf = my_KFold(4, n_folds=2)
for train_index, test_index in kf:
X_train, X_test = X1[train_index], X1[test_index]
y_train, y_test = y1[train_index], y1[test_index]
print("TRAIN:", train_index, "TEST:", test_index)
('TRAIN:', [2, 3], 'TEST:', [0, 1])
('TRAIN:', [0, 1], 'TEST:', [2, 3])
KNN算法交叉驗證
萬事俱備只欠東風(fēng)洞渤，已經(jīng)實現(xiàn)了KNN算法以及交叉驗證功能阅嘶，我們就可以利用交叉驗證的思想為我們的算法選擇合適的參數(shù)，這也是交叉驗證主要目標(biāo)之一载迄。
評價算法
首先我們用一個函數(shù)評價算法讯柔，給定訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)，計算平均的計算誤差护昧，這是評價算法好壞的重要指標(biāo)魂迄。
def test_algo(alg,X_train,X_test,y_train,y_test,kn=3):
error = 0.0
for i in range(len(y_test)):
guess = alg(X_train,y_train,X_test[i],kn=kn)
error += (y_test[i] - guess)**2
return error/len(y_test)
X_train,X_test,y_train,y_test = my_train_test_split(X,y,train_size=0.8)
test_algo(knn,X_train,X_test,y_train,y_test,kn=3)
783.80937472673656
交叉驗證
得到平均誤差，注意這里KFold 生成器的使用惋耙。
def my_cross_validate(alg,X,y,n_folds=100,kn=3):
error = 0.0
kf = my_KFold(len(y), n_folds=n_folds)
for train_index, test_index in kf:
X_train, X_test = X[train_index], X[test_index]
y_train, y_test = y[train_index], y[test_index]
error += test_algo(alg,X_train,X_test,y_train,y_test,kn=kn)
return error/n_folds
選最好的k值
從下圖可以看出捣炬，模型表現(xiàn)隨k值的變化呈現(xiàn)一個折現(xiàn)型，當(dāng)為1時绽榛，表現(xiàn)較差湿酸；當(dāng)取2,3的時候，模型表現(xiàn)還不錯灭美；但當(dāng)k繼續(xù)增加的時候推溃，模型表現(xiàn)急劇下降。同時knn_weight算法要略優(yōu)于knn算法届腐，有一點點改進铁坎。
errors1, errors2 = [], []
for i in range(20):
error1 = my_cross_validate(knn,X,y,kn=i+1)
error2 = my_cross_validate(knn_weight,X,y,kn=i+1)
errors1.append(error1)
errors2.append(error2)
xs = np.arange(len(errors1)) + 1
plt.plot(xs,errors1,color='c')
plt.plot(xs,errors2,color='r')
plt.xlabel('K')
plt.ylabel('Error')
plt.title('Error vs K');
[圖片上傳失敗...(image-cf9604-1569669311449)]
