lazy算法

⑵ 用沐神的方法阅读PyTorch FX论文

作者丨BBuf

来源丨GiantPandaCV

编辑丨极市平台

torch.fx 对于PyTorch来说确实是一个比较好的工作，因为它消除了一些动态图和静态图的Gap。比如在图改写方面， torch.fx 让PyTorch想做一些其它静态图框架的算子融合优化非常容易。并侍差闭且 torch.fx 让后训练量化和感知训练量化以及AMP等的实现难度大大降低，这得益于我们可以直接在Python层操作这个IR，所以我认为这是一个不错的工作。尤其是对使用PyTorch开发的算法工程师来说，现庆洞在可以基于这个特性大开脑洞了。 torch.fx 的卖点就是，它使用纯Python语言实现了一个可以捕获PyTorch程序的计算图并转化为一个IR的库，并且非常方便的在这个IR上做Pass，同时提供将变换后的IR Codegen合法的Python代码功能。我觉得算是达到了在Eager下写Pass就像做链表插入删除题目一样顺滑。

PyTorch FX论文的链接在： https://arxiv.org/pdf/2112.08429.pdf 。

下面我就以沐神的论文阅读顺序来分享一下阅读体验，帮助大家搞清楚PyTorch FX这个特性到底是什么，以及它可以在PyTorch中发挥什么作用。

摘要部分简单指明了像PyTorch这种基于动态图执行模式的深度学习框架虽然提升了用户的易用性。但是在一些真实场景中，用户可能是需要捕获和变换程序结构（也可以直接理解为神经网络的结构）来进行性能优化，可视化，分析和硬件调优等。为了解决这个痛点，PyTorch设计了 torch.fx 这个模块来做PyTorch程序的捕获和变换，这个模块是纯Python开发的。

这一节主要是讲了一下 torch.fx 的卖点，就是说动态图虽然易用性很强，但是图结构不能被提前感知和变换，但通过这篇论文的 torch.fx 模块，这件事就成啦！

早期的图模式或者叫 define-and-run 的静态图框架有Caffe，TensorFlow等，它们设计了一个表示图的IR，用户通过调用这些框架提供的API来构建IR。然后我们可以在这个IR上做程序微分，将IR切分到设备上实现并行，量化，性能优化等等。但这些事情一般都要求开发者在领域特定的语言上去做，比如以OneFlow的静态图模式为例，要做图切分，量化，性能优化等老裂都需要基于C++去开发，并且调试也会相对比较难（要借助pdb，gdb等等专业工具）。

现在的eager模式或者叫 define-by-run 的动态图框架有PyTorch，TensorFlow Eager模式等，它们可以随心所欲的让用户基于脚本语言编程并且可以解决大多数的训练（基于自动微分）和预测任务。但是有一些变换比如 “量化和算子融合” 是不能直接做的，而这一点在静态图模式下则很简单。为了消除这种Gap，动态图框架需要一种从用户的程序捕获图结构的方法来使能这些变换。

在捕获和变换程序时，eager和graph模式的深度学习框架都必须在 “捕获程序结构” 、 “程序特化” 和 “保存程序的IR的设计” 方面做出选择。这些选择的组合决定了可在框架中表示的 “程序空间” 、 “编写变换的难易程度”以及“生成的变换程序的性能” 。 “一般来说，支持程序的高性能运行需要更复杂的捕获框架和IR，从而使转换更难编写” 。每一段相关工作我就不详细过了，只描述每一段工作的核心是在说什么，相关细节大家可以查看原始论文。

这一节提到了PyTorch的 jit.trace ，MxNet Gluon，TensorFlow的 tf.function 等程序捕获方法，并指出这些方法只能处理Python的一些子集。然后，TorchScript通过在AST上分析可以处理控制流和更多的Python语法。然后还提了一下Julia和Swift For TensorFlow中将捕获程序结构的接口集成到了非Python的宿主语言中，要使用的话需要用户放弃Python生态系统。

对于 a+b 这个Python语句来说，这个表达式对 a 和 b 的类型没有限制。但当深度学习框架捕获程序时一般会对这两个变量进行特化，以便它们只对特定类型或者张量有效。在深度学习框架中处理的大多数程序都是特化类型的程序，特化程度越高，能够处理的输入就越少。例如 torch.jit.trace 在执行trace的时候只能处理某些拥有合法输入shape的输入。接下来还讨论了LazyTensor和Jax的 jit 来说明为了更好的处理特化程序中捕获的失败，它们做了哪些努力。

深度学习框架都有自己的IR设计，Caffe和TensorFlow使用Protocol Buffers格式。而PyTorch和MxNet使用C++数据结构来表示IR并额外绑定到Python。这些IR设计在runtime阶段表现都会比较好并且可以统一被序列化。但从另外一个角度来说，这些IR表示相比于纯Python语言的表示都需要更高的学习成本。接下来，这一节讨论了控制流和状态的问题，用来表明要处理这些问题需要设计较为复杂的IR以及要基于这个IR做较为复杂的分析才行。

基于上面几点，论文提出了 torch.fx 的基本设计原则：

这一节主要对一些相关工作进行了展开，以此来突出 torch.fx 的核心卖点，就是说我虽然不能像TorchScript这样的IR处理一些比较难的Case（比如动态控制流），但是我在神经网络这个领域里做得够用就可以了。最关键的是我的实现很简单，是纯Python的库，这样用户写变换就会很简单，学习成本会很小并且易用。（简单不代表不强大！

以简单为基本原则， torch.fx 通过符号跟踪来捕获程序，并通过一个简单的6个指令的IR来表示它们，并基于这个IR重新生成Python代码来运行它。为了避免JIT特化中的重捕获的复杂性， torch.fx 没有对程序本身进行特化，而是依靠变换来决定在捕获期间需要实现哪些特化。用户也可以配置符号跟踪的过程来实现自定义捕获需求。

Figure1给我们展示了使用 torch.fx.symbolic_trace 捕获程序的例子，输入可以是一个 torch.nn.Mole 或者函数，并且捕获之后的结构被存在一个Graph对象里面。该 Graph 对象和 GraphMole 中的模块参数相结合， GraphMole 是 torch.nn.Mole 的子类，其 forward 方法运行捕获的 Graph 。我们可以打印此图的 Nodes 以查看捕获的 IR。 placeholder 节点表示输入，单个 output 节点表示 Graph 的结果。 call_function 节点直接引用了它将调用的 Python 函数。 call_method 节点直接调用其第一个参数的方法。 Graph 被重组为 Python 代码（ traced.code ）以供调用。

Figure2展示了使用 torch.fx 进行变换的示例。变换是找到一个激活的所有实例并将它们替换为另一个。在这里，我们使用它来将 gelu 替换 relu 。

torch.fx 的符号跟踪机制使用一个Proxy数据结构来记录给定一个输入之后经过了哪些Op。Proxy是一个ck-typed类型的Python类记录了在它之上的的属性访问和调用方法，是程序中真实Op的上层抽象。ck-typed可以看一下这里的介绍： https://zh.wikipedia.org/wiki/%E9%B8%AD%E5%AD%90%E7%B1%BB%E5%9E%8B 。PyTorch的算子以及Python子集的某些函数都会被这个Proxy包装一次，然后在符号跟踪传入的是一个 nn.Mole 时，会对这个 nn.Mole 中的子 nn.Mole 也进行Proxy包装，当然还包含输入数据。这样程序中的输入和其它Op都是ck-typed类型的Proxy对象，我们就可以执行这个程序了，也就是符号跟踪的过程。符号跟踪的过程通过一个 Tracer 类进行配置，它的方法可以被重写以控制哪些值被作为Proxy对象保留，哪些值被unpack。（Proxy记录下来的Op可以进行unpack，unpack之后可以拿到真实的Tensor, Parameter和运算符等等）。通过Proxy和Tracer类的配合， torch.fx 就可以完成PyTorch程序的符号跟踪，需要注意的是这里的符号跟踪的意思就是运行一遍这个被代理之后的 nn.Mole 的forward。

torch.fx 的中间表示（IR）由一个Python数据结构 Graph 来做的。这个 Graph 实际上是一个包含一系列 Node 的线性表。节点有一个字符串操作码 opcode ，描述节点代表什么类型的操作（操作码的语义可以在附录 A.1 中找到）。节点有一个关联的目标，它是调用节点（ call_mole 、 call_function 和 call_method ）的调用目标。最后，节点有 args 和 kwargs ，在trace期间它们一起表示 Python 调用约定中的目标参数（每个opcode对应的 args 和 kwargs 的语义可以在附录 A.2 中找到）。节点之间的数据依赖关系表示为 args 和 kwargs 中对其他节点的引用。

torch.fx 将程序的状态存储在 GraphMole 类中。 GraphMole 是转换程序的容器，暴露转换后生成的代码，并提供 nn.Mole 类似的参数管理APIs。 GraphMole 可以在任何可以使用普通的 nn.Mole 的地方使用，以提供转换后的代码和PyTorch 生态系统的其余部分之间的互操作性。

torch.fx 变换pipline的最后阶段是代码生成。 torch.fx 并不是退出 Python 生态系统并进入定制的运行时，而是从变换后的 IR 生成有效的 Python 源代码。然后将此变换后的代码加载到 Python 中，生成一个可调用的 Python 对象，并作为 forward 方法安装在 GraphMole 实例上。使用代码生成允许将 torch.fx 变换的结果安装在模型中并用于进一步的变换。例如，在图3中，我们拿到trace原始程序的结果并将其安装为新模块中的激活函数。

到这里PyTorch FX特性就精读完了，但查看FX的论文可以发现还有一节叫作Design Decisions，分别介绍了Symbolic Tracing，Configurable Program Capture，AoT Capture without Specialization，Python-based IR and Transforms等等FX实现中依赖的一些想法和 决策，以及它们的好处等。我理解这一节就是Introction的加强版，所以就不继续讲解这一小节了，如果你担心会错过什么细节知识可以阅读论文原文。

torch.fx 的一个目标就是简化深度学习模型产生的IR，下面的Figure5以ResNet50为例展示了TorchScript IR和 torch.fx IR的差别，相比于TorchScript IR， torch.fx IR确实简单并且可读性更强。

我们知道后量化以及量化感知训练可以提示程序推理时的性能，下面的Figure6就展示了基于 torch.fx 实现的后量化（使用FBGEMM量化算子）应用在DeepRecommender模型之后，在Intel Xeon Gold 6138 CPU @2.00GHz上的性能表现。基于 torch.fx 实现的后量化模型推理速度相比float类型的模型要高3.3倍。并且基于 torch.fx 实现量化操作相比基于TorchScript IR要简单很多。

torch.fx 还可以做Op融合，Figure7展示了基于 torch.fx 做了Conv+BN融合后应用在ResNet50上，在n NVIDIA Tesla V100-SXM2 16GB with CUDA version 11.0 和 Intel Xeon Gold 6138 CPU @ 2.00GHz的性能表现，可以看到在GPU上减少了约6%的latency，在CPU上减少了约40%的latency（多线程）和约18%的latency（单线程）。

除此之外 torch.fx 还可以应用在FLOPs计算，内存带宽使用分析，工作负载的数据值大小估计等，用来分析程序运行时的内存和速度。 torch.fx 还可以用在形状推断，以及模型对应的DAG可视化作图等等。

最后， torch.fx 在runtime阶段还支持通过ASIC加速（即将 torch.fx 中的算子lowering到对应的ASIC上），下面的Figure8展示了基于 torch.fx 推理ResNet50和LearningToPaint并将算子lowering到TensorRT之后的加速情况：

torch.fx 对于PyTorch来说确实是一个比较好的工作，因为它消除了一些动态图和静态图的Gap。比如在图改写方面， torch.fx 让PyTorch想做一些其它静态图框架的算子融合优化非常容易。并且 torch.fx 让后训练量化和感知训练量化以及AMP等的实现难度大大降低，这得益于我们可以直接在Python层操作这个IR，所以我认为这是一个不错的工作。尤其是对使用PyTorch开发的算法工程师来说，现在可以基于这个特性大开脑洞了。我之前围绕FX也做了一个QAT的工作，感兴趣可以阅读：基于OneFlow实现量化感知训练： https://zhuanlan.hu.com/p/397650514

最后总结一下， torch.fx 的卖点就是，它使用纯Python语言实现了一个可以捕获PyTorch程序的计算图并转化为一个IR的库，并且非常方便的在这个IR上做Pass，同时提供将变换后的IR Codegen合法的Python代码功能。我觉得算是达到了在Eager下写Pass就像做链表插入删除题目一样顺滑。

沐神的论文阅读方法，感觉确实比较科学，文章末尾再赞一次。

⑶ 使用Node.js如何实现K最近邻分类算法

源于数据挖掘的一个作业， 这里用Node.js技术来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)。
k-nearest-neighbor-classifier
还是先严谨的介绍下。急切学习法（eager learner）是在接受待分类的新元组之前就构造了分类模型，学习后的模型已经就绪，急着对未知的元组进行分类，所以称为急切学习法，诸如决策树归纳，贝叶斯分类等都是急切学习法的例子。惰性学习法（lazy learner）正好与其相反，直到给定一个待接受分类的新元组之后，才开始根据训练元组构建分类模型，在此之前只是存储着训练元组，所以称为惰性学习法，惰性学习法在分类进行时做更多的工作。
本文的knn算法就是一种惰性学习法，它被广泛应用于模式识别。knn基于类比学习，将未知的新元组与训练元组进行对比，搜索模式空间，找出最接近未知元组的k个训练元组，这里的k即是knn中的k。这k个训练元祖就是待预测元组的k个最近邻。
balabala了这么多，是不是某些同学想大喊一声..speak Chinese! 还是来通俗的解释下，然后再来看上面的理论应该会明白很多。小时候妈妈会指着各种各样的东西教我们，这是小鸭子，这个红的是苹果等等，那我们哼哧哼哧的看着应答着，多次被教后再看到的时候我们自己就能认出来这些事物了。主要是因为我们在脑海像给这个苹果贴了很多标签一样，不只是颜色这一个标签，可能还有苹果的形状大小等等。这些标签让我们看到苹果的时候不会误认为是橘子。其实这些标签就对应于机器学习中的特征这一重要概念，而训练我们识别的过程就对应于泛化这一概念。一台iphone戴了一个壳或者屏幕上有一道划痕，我们还是能认得出来它，这对于我们人来说非常简单，但蠢计算机就不知道怎么做了，需要我们好好调教它，当然也不能过度调教2333，过度调教它要把其他手机也认成iphone那就不好了，其实这就叫过度泛化。
所以特征就是提取对象的信息，泛化就是学习到隐含在这些特征背后的规律，并对新的输入给出合理的判断。
我们可以看上图，绿色的圆代表未知样本，我们选取距离其最近的k个几何图形，这k个几何图形就是未知类型样本的邻居，如果k=3，我们可以看到有两个红色的三角形，有一个蓝色的三正方形，由于红色三角形所占比例高，所以我们可以判断未知样本类型为红色三角形。扩展到一般情况时，这里的距离就是我们根据样本的特征所计算出来的数值，再找出距离未知类型样本最近的K个样本，即可预测样本类型。那么求距离其实不同情况适合不同的方法，我们这里采用欧式距离。
综上所述knn分类的关键点就是k的选取和距离的计算。
2. 实现
我的数据是一个xls文件，那么我去npm搜了一下选了一个叫node-xlrd的包直接拿来用。
// node.js用来读取xls文件的包
var xls = require('node-xlrd');
然后直接看文档实例即可，把数据解析后插入到自己的数据结构里。
var data = [];// 将文件中的数据映射到样本的属性var map = ['a','b','c','d','e','f','g','h','i','j','k'];// 读取文件
xls.open('data.xls', function(err,bk){
if(err) {console.log(err.name, err.message); return;}
var shtCount = bk.sheet.count;
for(var sIdx = 0; sIdx < shtCount; sIdx++ ){
var sht = bk.sheets[sIdx],
rCount = sht.row.count,
cCount = sht.column.count;
for(var rIdx = 0; rIdx < rCount; rIdx++){
var item = {};
for(var cIdx = 0; cIdx < cCount; cIdx++){
item[map[cIdx]] = sht.cell(rIdx,cIdx);
}
data.push(item);
}
}
// 等文件读取完毕后 执行测试
run();
});
然后定义一个构造函数Sample表示一个样本，这里是把刚生成的数据结构里的对象传入，生成一个新的样本。
// Sample表示一个样本
var Sample = function (object) {
// 把传过来的对象上的属性克隆到新创建的样本上
for (var key in object)
{
// 检验属性是否属于对象自身
if (object.hasOwnProperty(key)) {
this[key] = object[key];
}
}
}
再定义一个样本集的构造函数
// SampleSet管理所有样本 参数k表示KNN中的kvar SampleSet = function(k) {
this.samples = [];
this.k = k;
};
// 将样本加入样本数组
SampleSet.prototype.add = function(sample) {
this.samples.push(sample);
}
然后我们会在样本的原型上定义很多方法，这样每个样本都可以用这些方法。
// 计算样本间距离 采用欧式距离
Sample.prototype.measureDistances = function(a, b, c, d, e, f, g, h, i, j, k) {
for (var i in this.neighbors)
{
var neighbor = this.neighbors[i];
var a = neighbor.a - this.a;
var b = neighbor.b - this.b;
var c = neighbor.c - this.c;
var d = neighbor.d - this.d;
var e = neighbor.e - this.e;
var f = neighbor.f - this.f;
var g = neighbor.g - this.g;
var h = neighbor.h - this.h;
var i = neighbor.i - this.i;
var j = neighbor.j - this.j;
var k = neighbor.k - this.k;
// 计算欧式距离
neighbor.distance = Math.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k);
}
};
// 将邻居样本根据与预测样本间距离排序
Sample.prototype.sortByDistance = function() {
this.neighbors.sort(function (a, b) {
return a.distance - b.distance;
});
};
// 判断被预测样本类别
Sample.prototype.guessType = function(k) {
// 有两种类别 1和-1
var types = { '1': 0, '-1': 0 };
// 根据k值截取邻居里面前k个
for (var i in this.neighbors.slice(0, k))
{
var neighbor = this.neighbors[i];
types[neighbor.trueType] += 1;
}
// 判断邻居里哪个样本类型多
if(types['1']>types['-1']){
this.type = '1';
} else {
this.type = '-1';
}
}
注意到我这里的数据有a-k共11个属性，样本有1和-1两种类型，使用truetype和type来预测样本类型和对比判断是否分类成功。
最后是样本集的原型上定义一个方法，该方法可以在整个样本集里寻找未知类型的样本，并生成他们的邻居集，调用未知样本原型上的方法来计算邻居到它的距离，把所有邻居按距离排序，最后猜测类型。
// 构建总样本数组，包含未知类型样本
SampleSet.prototype.determineUnknown = function() {

for (var i in this.samples)
{
// 如果发现没有类型的样本
if ( ! this.samples[i].type)
{
// 初始化未知样本的邻居
this.samples[i].neighbors = [];
// 生成邻居集
for (var j in this.samples)
{
// 如果碰到未知样本 跳过
if ( ! this.samples[j].type)
continue;
this.samples[i].neighbors.push( new Sample(this.samples[j]) );
}
// 计算所有邻居与预测样本的距离
this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);
// 把所有邻居按距离排序
this.samples[i].sortByDistance();
// 猜测预测样本类型
this.samples[i].guessType(this.k);
}
}
};
最后分别计算10倍交叉验证和留一法交叉验证的精度。
留一法就是每次只留下一个样本做测试集，其它样本做训练集。
K倍交叉验证将所有样本分成K份，一般均分。取一份作为测试样本，剩余K-1份作为训练样本。这个过程重复K次，最后的平均测试结果可以衡量模型的性能。
k倍验证时定义了个方法先把数组打乱随机摆放。
// helper函数 将数组里的元素随机摆放
function ruffle(array) {
array.sort(function (a, b) {
return Math.random() - 0.5;
})
}
剩余测试代码好写，这里就不贴了。
测试结果为
用余弦距离等计算方式可能精度会更高。
3. 总结
knn算法非常简单，但却能在很多关键的地方发挥作用并且效果非常好。缺点就是进行分类时要扫描所有训练样本得到距离，训练集大的话会很慢。
可以用这个最简单的分类算法来入高大上的ML的门，会有点小小的成就感。

⑷ KNN算法常见问题总结

给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。

通常，在分类任务中可使用“投票法”，即选择这k个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。

k近邻法不具有显式的学习过程，事实上，它是懒惰学习（lazy learning）的着名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

KNN一般采用欧氏距离，也可采用其他距离度量，一般的Lp距离：

KNN中的K值选取对K近邻算法的结果会产生重大影响。如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差（近似误差：可以理解为对现有训练集的训练误差）会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；

如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法来选择最优的K值。经验规则：k一般低于训练样本数的平方根

1、计算测试对象到训练集中每个对象的距离

2、按照距离的远近排序

3、选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居

4、统计这k个邻居的类别频率

5、k个邻居里频率最高的类别，即为测试对象的类别

输入X可以采用BallTree或KDTree两种数据结构，优化计算效率，可以在实例化KNeighborsClassifier的时候指定。

KDTree

基本思想是，若A点距离B点非常远，B点距离C点非常近， 可知A点与C点很遥远，不需要明确计算它们的距离。 通过这样的方式，近邻搜索的计算成本可以降低为O[DNlog(N)]或更低。 这是对于暴力搜索在大样本数N中表现的显着改善。KD 树的构造非常快，对于低维度 (D<20) 近邻搜索也非常快, 当D增长到很大时，效率变低： 这就是所谓的 “维度灾难” 的一种体现。

KD 树是一个二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。 KD 树的构造非常快：因为只需沿数据轴执行分区, 无需计算D-dimensional 距离。 一旦构建完成, 查询点的最近邻距离计算复杂度仅为O[log(N)]。 虽然 KD 树的方法对于低维度 (D<20) 近邻搜索非常快, 当D增长到很大时, 效率变低。

KD树的特性适合使用欧氏距离。

BallTree

BallTree解决了KDTree在高维上效率低下的问题，这种方法构建的树要比 KD 树消耗更多的时间，但是这种数据结构对于高结构化的数据是非常有效的， 即使在高维度上也是一样。

KD树是依次对K维坐标轴，以中值切分构造的树；ball tree 是以质心C和半径r分割样本空间，每一个节点是一个超球体。换句简单的话来说，对于目标空间(q, r)，所有被该超球体截断的子超球体内的所有子空间都将被遍历搜索。

BallTree通过使用三角不等式减少近邻搜索的候选点数:|x+y|<=|x|+|y|通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它在高维度上的性能超出 KD-tree, 尽管实际的性能高度依赖于训练数据的结构。

BallTree适用于更一般的距离。

1、优点

非常简单的分类算法没有之一，人性化，易于理解，易于实现

适合处理多分类问题，比如推荐用户

可用于数值型数据和离散型数据，既可以用来做分类也可以用来做回归

对异常值不敏感

2、缺点

属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离

样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差，可以调整样本权值改善

可解释性差，无法给出类似决策树那样的规则

向量的维度越高，欧式距离的区分能力就越弱

样本空间太大不适合，因为计算量太大，预测缓慢

文本分类

用户推荐

回归问题

1）所有的观测实例中随机抽取出k个观测点，作为聚类中心点，然后遍历其余的观测点找到距离各自最近的聚类中心点，将其加入到该聚类中。这样，我们就有了一个初始的聚类结果，这是一次迭代的过程。

2）我们每个聚类中心都至少有一个观测实例，这样，我们可以求出每个聚类的中心点（means），作为新的聚类中心，然后再遍历所有的观测点，找到距离其最近的中心点，加入到该聚类中。然后继续运行2）。

3）如此往复2），直到前后两次迭代得到的聚类中心点一模一样。

本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；

空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数。

适用范围：

K-menas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。

1）首先，算法只能找到局部最优的聚类，而不是全局最优的聚类。而且算法的结果非常依赖于初始随机选择的聚类中心的位置。我们通过多次运行算法，使用不同的随机生成的聚类中心点运行算法，然后对各自结果C通过evaluate(C)函数进行评估，选择多次结果中evaluate(C)值最小的那一个。k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远

2）关于初始k值选择的问题。首先的想法是，从一个起始值开始，到一个最大值，每一个值运行k-means算法聚类，通过一个评价函数计算出最好的一次聚类结果，这个k就是最优的k。我们首先想到了上面用到的evaluate(C)。然而，k越大，聚类中心越多，显然每个观测点距离其中心的距离的平方和会越小，这在实践中也得到了验证。第四节中的实验结果分析中将详细讨论这个问题。

3）关于性能问题。原始的算法，每一次迭代都要计算每一个观测点与所有聚类中心的距离。有没有方法能够提高效率呢？是有的，可以使用k-d tree或者ball tree这种数据结构来提高算法的效率。特定条件下，对于一定区域内的观测点，无需遍历每一个观测点，就可以把这个区域内所有的点放到距离最近的一个聚类中去。这将在第三节中详细地介绍。

相似点：都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法，一般用KD树来实现NN。

k-d tree 与 ball tree

1）k-d tree[5]

把n维特征的观测实例放到n维空间中，k-d tree每次通过某种算法选择一个特征(坐标轴)，以它的某一个值作为分界做超平面，把当前所有观测点分为两部分，然后对每一个部分使用同样的方法，直到达到某个条件为止。

上面的表述中，有几个地方下面将会详细说明：（1）选择特征（坐标轴）的方法 （2）以该特征的哪一个为界 （3）达到什么条件算法结束。

(1)选择特征的方法

计算当前观测点集合中每个特征的方差，选择方差最大的一个特征，然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。

（2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。

第一种是以各个点的方差的中值（median）为界。这样会使建好的树非常地平衡，会均匀地分开一个集合。这样做的问题是，如果点的分布非常不好地偏斜的，选择中值会造成连续相同方向的分割，形成细长的超矩形(hyperrectangles)。

替代的方法是计算这些点该坐标轴的平均值，选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡，但区域会倾向于正方地被划分，连续的分割更有可能在不同方向上发生。

（3）达到什么条件算法结束

实际中，不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值，当这个最小值达到时结束算法。

图6中，星号标注的是目标点，我们在k-d tree中找到这个点所处的区域后，依次计算此区域包含的点的距离，找出最近的一个点（黑色点），如果在其他region中还包含更近的点则一定在以这两个点为半径的圆中。假设这个圆如图中所示包含其他区域。先看这个区域兄弟结点对应区域，与圆不重叠；再看其双亲结点的兄弟结点对应区域。从它的子结点对应区域中寻找（图中确实与这个双亲结点的兄弟结点的子结点对应区域重叠了）。在其中找是否有更近的结点。

k-d tree的优势是可以递增更新。新的观测点可以不断地加入进来。找到新观测点应该在的区域，如果它是空的，就把它添加进去，否则，沿着最长的边分割这个区域来保持接近正方形的性质。这样会破坏树的平衡性，同时让区域不利于找最近邻。我们可以当树的深度到达一定值时重建这棵树。

然而，k-d tree也有问题。矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图6中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。

为了解决上面的问题，我们引入了ball tree。

2）ball tree[4]

解决上面问题的方案就是使用超球面而不是超矩形划分区域。使用球面可能会造成球面间的重叠，但却没有关系。ball tree就是一个k维超球面来覆盖这些观测点，把它们放到树里面。图7（a)显示了一个2维平面包含16个观测实例的图,图7（b）是其对应的ball tree，其中结点中的数字表示包含的观测点数。

不同层次的圆被用不同的风格画出。树中的每个结点对应一个圆，结点的数字表示该区域保含的观测点数，但不一定就是图中该区域囊括的点数，因为有重叠的情况，并且一个观测点只能属于一个区域。实际的ball tree的结点保存圆心和半径。叶子结点保存它包含的观测点。

使用ball tree时，先自上而下找到包含target的叶子结点，从此结点中找到离它最近的观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离大于这个圆的圆心加上前面的上界的值，则这个兄弟结点不可能包含所要的观测点。（如图8）否则，检查这个兄弟结点是否包含符合条件的观测点。

那么，ball tree的分割算法是什么呢？

选择一个距离当前圆心最远的观测点i1，和距离i1最远的观测点 i2，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。

与k-d tree一样，如果结点包含的观测点到达了预先设定的最小值，这个顶点就可以不再分割了。

⑸ knn算法是什么

KNN（K- Nearest Neighbor）法即K最邻近法，最初由Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。

作为一种非参数的分类算法，K-近邻（KNN）算法是非常有效和容易实现的。它已经广泛应用于分类、回归和模式识别等。

介绍

KNN算法本身简单有效，它是一种lazy-learning算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么KNN的分类时间复杂度为O(n)。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。