tensorflowjs knn(k近邻)实战

在机器学习和智能算法大热的时代，不甘于寂寞的前端同学们也开始涉足智能领域，各种sketch2code层出不穷，那么让我们从基础开始一步步揭开智能算法的神秘面纱。

分类

在机器学习领域，一个实际场景的问题往往会被划分成回归、分类、聚类问题，其中又属分类问题最为常见。今天我们就来了解一下什么是分类、并且怎么解决一个分类问题。

定义

first of all.我们先来学习一下什么是分类。

“帝釐下土，方設居方，別生分類，作《汩作》。” 

                                《書‧舜典》附亡《書》序

意指将无序的事物按照种类、等级、特点或性质划分成一组相似的物品过程。人们从这样的过程中不断总结归纳形成了一门一同学科，分类学。分即鉴定、描述和命名，类即归类，按一定秩序排列类群，形成系统演化。例如生物学中的界、门、纲、目、科、属、种7个分类等级便是分类学在生物中的运用。

相似性

大家可以思考一下，按照直觉逻辑，你们的分类依据是什么？没错，物与物之间相似性。相似的东西我们会归在一起，南辕北辙的东西一定不在一个类别。那么相似性应该怎么量化呢。这里就是我们的重点了。

距离

在涛涛历史长河中,人类的智慧在于总是能够将不同的经验总结抽样化归到另一个场景发光发热。物理学中，我们通过估计计算距离来对两个物体位置进行描述，数学中，我们通过距离这个计算函数来描述空间某些元素是否相互接近或者原理。那么如果我们能够将一个物品的种类、等级、特点通过空间中的一个元素来表示，元素之间的相似性是否就能够通过空间距离被量化出来了呢？

欧几里得距离

让我们回到公元前三世纪，伟大的数学家、几何学之父欧几里得通过证明毕达哥拉斯定理从而告诉了世界平面中任意两点的距离应该如何计算，史称欧几里得距离。后人成功论证了他在二维、三位空间距离的计算法适用于任何有限维度。

让我们回到刚刚的问题上来，空间中的两个元素之间的相似性能够被空间距离量化么？

这里以data-mining中的例子来说明。以亚马逊中不同用户对两本书的评价为例。其中评价等级为0-5颗星。

由于是两本书的评价，我们可以将其置于二维空间中，以Snow Crash为横轴，Girl with the Dragon Tattoo为纵轴，可以绘制出如下坐标系

计算欧几里得距离我们得到

D(Jim-Bill) = 2
D(Amy-Bill) = 3
D(Jim-Amy) = sqrt(17)

根据计算可以发现 D(Jim-Bill) < D(Amy-Bill) < D(Jim-Amy)
因此我们认为Jim和Bill的阅读口味相似度较高，可以把他们划分到一个类别中。

曼哈顿距离

在扩展到n维空间时(即本例中对n本书籍的评分)，欧几里得距离的计算会涉及海量的平方和开方运算，数量量大的时候计算速度明细下降。如果我们简化一下计算公式来近似表示距离的度量。由于勾股定理斜边长度仅与领边长度相关，那么距离的测量我们可以近似表示成

这便是十九世纪由闵可夫斯基提出的曼哈顿距离，又称街区距离，也是目前我们地图路径规划的理论基础。

皮尔逊系数

按照上面书籍评分的例子思考一下这个问题, 林子大了什么鸟都有，我们有三个风格迥然相异的用户。

Bill没有打出极端的分数，都在2至4分之间；
Jordyn似乎喜欢所有的乐队，打分都在4至5之间；
Hailey是一个有趣的人，他的分数不是1就是4。

那么这些用户间还能够直接通过我们的5分标准坐标轴计算距离来判别相似性么？Hailey打的4分对应与Jordyn的4分还是5分呢, 应该更接近5分吧。我们会发现当我们的变量量纲标准不一致的时候，仅仅用距离去计算相似性的方法效果好像就不好了。我们必须要去消除量纲的影响。

Z-score标准化

我们希望所有值能够落到一个标准的量化范围内。借助统计学中的经验，用z-score来计算标准分数

一个统计值减去均值再除以标准差，这样他的取值范围就落在了[-1, 1]之间，并且z的均值为0，标准差为1，无论量纲如何变化，都能被标准化到范围区间。

我们将标准化后的特征量纲再代入到之前的欧氏距离计算中。

设有两个向量 $X=[X_1, ...X_n]$ 和 $Y=[Y_1, ...Y_n]$ 维度相同为n.

已知X与Y均作了标准化处理，因此均值ux，uy为0，标准差αx, αy为1。有

$\sum_{i=1}^{n}{X_i^2}=\sum_{i=1}^{n}{(X_i-0)^2}=\sum_{i=1}^{n}{(X_i-\mu_X)^2}=(n-1)\sigma_X^2=n-1$

当n趋近于无穷时 $n-1\rightarrow n$ 因此可得

$\sum_{i=1}^{t}{X_i^2}=\sum_{i=1}^{t}{Y_i^2}= n$

回顾一下欧式距离的计算公式，为了简化运算，这里我们不做开方处理。

$d(X,Y)=\sum_{i=1}^{n}{(X_n-Y_n)^2}$

将上述结论带入欧式距离公式

$\begin{equation} \begin{split} d(X,Y)&=\sum_{i=1}^{n}{(X_n-Y_n)^2} \\ &=\sum_{i=1}^{n}{X_i}^2 - 2 \sum_{i=1}^{n}{X_iY_i}+\sum_{i=1}^{n}{Y_i}^2 \\ &= 2n - 2 \sum_{i=1}^{n}{X_iY_i}\\ &=2n(1-\sum_{i=1}^{n}{X_iY_i})\\ &=2n(1-\frac{\sum_{i=1}^{n}{(X_i-0)(Y_i-0)}}{1\cdot1})\\ &=2n(1-\frac{E[(X-\mu_X)(Y-\mu_Y)]}{\sigma_X\sigma_Y}\\ &= 2n(1-\rho(X,Y)) \end{split} \end{equation}$

这里的

$\rho(X,Y)=\frac{E[(X-\mu_{X})(Y-\mu_{Y})]}{\sigma_X\sigma_Y} =\frac{E[(X-\mu_{X})(Y-\mu_{Y})]}{\sqrt{\sum_{i=1}^{n}{(X_i-\mu_X)^2}}\sqrt{\sum_{i=1}^{n}{(Y_i-\mu_Y)^2}}}$

便是我们的皮尔逊系数了。可以发现皮尔逊系数其实就是标准化后的向量点积。让我们再按直觉逻辑算一下，距离越大，皮尔逊系数越小，距离越小皮尔逊系数越大。恩没问题。

余弦相似性

$c(X,Y)=\frac{X\cdot Y}{\left| X \right|\left| Y \right|} =\frac{\sum_{i=1}^{n}{X_iY_i}}{\sqrt{\sum_{i=1}^{n}{X_i^2}}\sqrt{\sum_{i=1}^{n}{Y_i^2}}}$

余弦相似给出了另一个角度的相似性解释。余弦相似并不关注数值的度量而是关注维度的度量，根据空间向量夹角来区分两个物体方向性的差异。余弦相似由于对数值不敏感，所以也
会面临之前评分标准的问题，因此我们会对余弦相似进行修正。对用户的评分标准进行减去均值的运算来平衡尺度差异。

我们将标准化后的向量代入余弦公式

$c(X,Y)=\frac{\sum_{i=1}^{n}{X_iY_i}}{\sqrt{\sum_{i=1}^{n}{X_i^2}}\sqrt{\sum_{i=1}^{n}{Y_i^2}}} =\frac{z(X)\cdot z(Y)}{\left| z(X) \right|\left| z(Y) \right|}$

惊奇的发现和欧几里得距离以及皮尔逊公式形式高度的一致，殊途同归了。

knn

knn 又称k临近算法，在相似性计算的基础上，我们会筛选出最相似的k组记录并根据记录的分类结果进行投票。选举出最终的分类，

实战

原理我们都懂了，快干起来吧。

这里我们实现了一个从后台字段到前端渲染器匹配的一个场景。在我们的可视化系统中会将每一个后台接口的字段匹配到前端的一个组件渲染器上(最通用的例子就是列表页每一列的字段会对应一个列渲染器)。

特征工程

这里的特征工程非常简单，我们先将系统存储的所有有台字段进行分词并去重得到一张特征表

根据系统中的记录的后台关键词，将关键词映射成shape为[1, 特征表长度]的一个稀疏矩阵。根据特征表，若后台字段包含特征表中的关键字，则该位置为1，否则置为0。

tensorflow接入

本次实践基于@tensorflow/tfjs-model/knn-classifier。knn-classifier分类器源码中两个关键流程如下所示

similarities

这个函数便是我们上面老生常谈的相似性计算

逻辑其实也很简单先对，输入向量进行标准化，然后和训练集(在输入训练集时已被标准化)进行矩阵乘运算。这里的矩阵乘积其实对应的便是我们上文中提到的标准化后的皮尔逊定理和余弦角公式的分子。由于标准化后分母可以看成是一个常量，因此仅计算分子便可决定相似度。函数会返回一个一维向量, 或者我们可以看成是一个一维数组，数组每项的索引与训练集中的向量索引对应, 值代表着该训练向量与输入向量的相似得分(正相关)。