# KNN算法实现及其交叉验证

## KNN算法

knn

kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

### 1. 数据

```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`

```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)
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近邻，如何叫“近”，我们需要一个数学上的定义，最常见的是用欧式距离，二维三维的时候对应平面或空间距离。

```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.])`

```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算法具体实现的时候很简单，调用前面的函数，计算出排序好的距离列表，然后对其前k项对应的标签值取均值即可。可以用该knn算法与实际的价格模型对比，发现精度还不错。

```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. 加权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);```
```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`

## 交叉验证

Holdout Method(保留)

• 方法：将原始数据随机分为两组,一组做为训练集,一组做为验证集,利用训练集训练分类器,然后利用验证集验证模型,记录最后的分类准确率为此Hold-OutMethod下分类器的性能指标.。Holdout Method相对于K-fold Cross Validation 又称Double cross-validation ，或相对K-CV称 2-fold cross-validation(2-CV)
• 优点：好处的处理简单,只需随机把原始数据分为两组即可
• 缺点：严格意义来说Holdout Method并不能算是CV,因为这种方法没有达到交叉的思想,由于是随机的将原始数据分组,所以最后验证集分类准确率的高低与原始数据的分组有很大的关系,所以这种方法得到的结果其实并不具有说服性.(主要原因是 训练集样本数太少，通常不足以代表母体样本的分布，导致 test 阶段辨识率容易出现明显落差。此外，2-CV 中一分为二的分子集方法的变异度大，往往无法达到「实验过程必须可以被复制」的要求。)

K-fold Cross Validation(k折叠)

• 方法：作为Holdout Methon的演进，将原始数据分成K组(一般是均分),将每个子集数据分别做一次验证集,其余的K-1组子集数据作为训练集,这样会得到K个模型,用这K个模型最终的验证集的分类准确率的平均数作为此K-CV下分类器的性能指标.K一般大于等于2,实际操作时一般从3开始取,只有在原始数据集合数据量小的时候才会尝试取2. 而K-CV 的实验共需要建立 k 个models，并计算 k 次 test sets 的平均辨识率。在实作上，k 要够大才能使各回合中的 训练样本数够多，一般而言 k=10 (作为一个经验参数)算是相当足够了。
• 优点：K-CV可以有效的避免过学习以及欠学习状态的发生,最后得到的结果也比较具有说服性.
• 缺点：K值选取上

Leave-One-Out Cross Validation(留一)

• 方法：如果设原始数据有N个样本,那么留一就是N-CV,即每个样本单独作为验证集,其余的N-1个样本作为训练集,所以留一会得到N个模型,用这N个模型最终的验证集的分类准确率的平均数作为此下LOO-CV分类器的性能指标.
• 优点：相比于前面的K-CV,留一有两个明显的优点：
• a.每一回合中几乎所有的样本皆用于训练模型,因此最接近原始样本的分布,这样评估所得的结果比较可靠。
• b. 实验过程中没有随机因素会影响实验数据,确保实验过程是可以被复制的.
• 缺点：计算成本高,因为需要建立的模型数量与原始数据样本数量相同,当原始数据样本数量相当多时,LOO-CV在实作上便有困难几乎就是不显示,除非每次训练分类器得到模型的速度很快,或是可以用并行化计算减少计算所需的时间。

Holdout method方法的想法很简单，给一个train_size,然后算法就会在指定的比例(train_size)处把数据分为两部分，然后返回。

```# 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算法是把数据分成k份，进行k此循环，每次不同的份分别来充当测试组数据。但是注意，该算法不直接操作数据，而是产生一个迭代器，返回训练和测试数据的索引。看docstring里的例子应该很清楚。

```# k folds 产生一个迭代器
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算法交叉验证

#### 评价算法

```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`

#### 交叉验证

```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值

```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');```

0 条评论

• ### NumPy核心概念

NumPy是Python数据科学生态中重要的基础成员，其中有几个概念比较tricky，简单记录之。更佳阅读体验，可移步NumPy核心概念。

• ### 经典决策树对比

algo-decision-tree-conditional-probability

• ### Leetcode#500. Keyboard Row（键盘行）

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

• ### 排查 Node.js 服务内存泄漏，没想到竟是它？

团队最近将两个项目迁移至 degg 2.0 中，两个项目均出现比较严重的内存泄漏问题，此处以本人维护的埋点服务为例进行排查。服务上线后内存增长如下图，其中红框为...

• ### 科学计算工具Numpy

Numpy：提供了一个在Python中做科学计算的基础库，重在数值计算，主要用于多维数组（矩阵）处理的库。用来存储和处理大型矩阵，比Python自身的嵌套列表结...

• ### 一份 Numpy 小抄请查收

在numpy中维度（dimensions）叫做轴（axes），轴的个数叫做秩（rank）。如3D空间中一个点的坐标[1,2,3]是一个秩为1的数组，因为它只有一...

• ### iOS音频播放器锁屏歌词显示与性能优化 原

前边有博客探讨了有关iOS开发中音频播放的技术与进行后台音频播放并在后台与用户进行交互的方法，本篇将探讨一种在锁屏界面同步显示歌词歌词的方法，并在应用性...

• ### 数据分析-NumPy入门使用

今天我们学习python数据分析中一个很有用的模块NumPy，NumPy是使用Python进行科学计算的基础包。它包含其他内容：