最近邻域算法的思想很简单，首先将训练集看作训练模型，然后基于新数据点与训练集的距离来预测新数据点。最直观的最近邻域算法是让预测值与最接近的训练数据集作为同一类。但是大部分样本数据集包含一定程序的噪声，更通用的方法是k个邻域的加权平均，该方法称为k最近邻域法(k-nearest neighbor, k-NN)。
假设样本训练集(x_1, x_2, ..., x_n), 对应的目标值(y_1, y_2, ..., y_n), 通过最近邻域法预测数据点z。预测的实际方法取决于我们是想做回归训练（连续型y_i）还是分类训练（离散型y_i)。
对于离散型分类目标，预测值由到预测数据点的加权距离的最大投票方案决定，公式如下:
f(z) = max(j, sum(i:=1->k, φ(d_i_j)*I_i_j
其中，预测函数f(z)是所有分类j上的最大加权值。预测数据点到训练数据点i的加权距离用φ(d_i_j)表示。I_i_j是指示函数，表示数据点i是否属于分类j。
对于连续回归训练目标，预测值是所有k个最近邻域数据点到预测数据点的加权平均，公式如下:
f(z) = 1/k * sum(i:=1->k, φ(d_i))
明显地，预测值严重依赖距离度量(d)方式的选择。常用的距离度量是L1范数和L2范数。公式如下:
d_L1(x_i, x_j) = |x_i-x_j|=|x_i_1-y_j_1|+|x_i_2-y_j_2| + ...
d_L2(x_i, x_j) = ||x_i - x_j|| = sqrt((x_i_1-x_j_1)**2 + (x_i_2+x_j_2)**2 + ... )
距离度量方式可选择性广，目前仅选用L1范数和L2范数，也会使用编辑距离和文本距离。
我们也需要选择如何加权距离。最直观的方式是用距离本身来加权，即加权权重为1。考虑到更近的数据点对预测数据点的预测值影响更小，因而最通用的加权方式是距离的归一化倒数。
注意，k-NN算法是一种聚合的方法。对于回归算法来说，需要计算邻域的加权平均距离，因而预测值将比实际目标值的特征更平缓。影响的程度将取决于k值，该值是算法中的邻域个数。
- TensorFlow的文本距离度----字符串间的编辑距离(Levenshtein距离)。
- Levenshtein距离是指由一个字符串转换成另一个字符串所需的最少编辑操作次数。允许的编辑操作包括插入一个字符，删除一个字符和将一个字符替换成另一个字符。使用TensorFlow的内建函数edit_distance()求解Levenshtein距离。
2. 展示如何计算两个单词'bear'和'beer'间的编辑距离。用Python的list()函数创建字符list,然后将list映射为一个三维稀疏矩阵。TensorFlow的tf.SparseTensor()函数需指定字符索引、矩阵形状和张量中的非零值。编辑距离计算时，指定normalize=False表示计算总的编辑距离: 指定normalize=True表示计算归一化编辑距离，通过编辑距离除以第二个单词的长度进行归一化
- 文本距离的度量方式
| 名称 | 描述 | 公式 |
|---|---|---|
| 汉明距离(Hamming distance) | 两个等长字符串中对应位置的不同字符的个数 | D(s1,s2) = sum(0,n,I_i),其中I是等长字符串的指示函数 |
| 余弦距离(Cosine distance) | 不同k-gram的点积除以不同k-gram的L2范数 | D(s1,s2) = 1-(k(s_1)k(s_2))/(||k(s_1)||||k(s_2)||) |
| Jaccard距离(Jaccard distance) | 两个字符串中相同字符数除以所有字符数 | D(s1,s2) = (|s_1且s_2|)/(|s_1并s_2|) |
- 当处理的数据观测点有多种特征时，我们应该意识到不同的特征应该用不同的归一化方式来缩放。
- 扩展最近邻域法进行多维度缩放。下面将展示如何扩展多变量的距离函数。特别地，我们将扩展距离函数为特征变量的函数。
- 加权距离函数的关键是使用加权权重矩阵。包含矩阵操作的距离函数的表达式如下：
D(x,y) = sqrt((x-y).T*A*(x-y))
其中，A是对角权重矩阵。