17.【 STEMA】以下关于二分查找算法的描述中，不正确的是（A）
 A二分查找算法的最大查找时间与查找对象的大小成正比
 B二分查找一般从数组的中间元素开始
 C二分查找只对有序数组有效
 D二分查找可以使用递归实现

标准粒子群算法及其改进算法
 
首先在这里介绍一下，这个里主要介绍粒子群算法以及一个改进的二阶振荡粒子群算法。
 
原理
 
粒子群优化（PSO）算法是Kennedy和Eberhart受 鸟群群体运动的启发于1995年提出的一种新的群智能优化算法[1]。大概的意思就是一片森林里有一群鸟在找一块食物，它们不知道食物具体在哪，但是可以通过感官（例如嗅觉）去察觉到自己当前位置距离食物的远近。鸟可以记住自己走过的位置并且知道自己做过的最优位置。这一群鸟的运动都是随机的，这类似于一种穷举法。
 
标准粒子群算法
 
粒子群算法一般用来找一个函数的最优值。这个函数一般就是适应度函数。
 函数中未知量的个数就是这个查找的空间维度。
 
假设有N个粒子组成一个种群S
 
Xi是代表粒子i所在的位置，i=1，2，…，N
 
Vi代表粒子i在位置Xi处的速度，i=1，2，…，N
 
pi是记录粒子i到走过的最优位置，i=1,2，…，N
 
pg是所有粒子走过的最优的位置，i=1,2，…，N
 
w 为惯性权重
 
c1 、 c2 为学习因子
 
r1,r2为[ 0 , 1 ]之间均匀分布的参数
 
接下来种群中每个粒子按照公式更新速度和位置：
 
Vi( t +1 ) =w * Vi( t ) + c1 * r1 * (pi - xi( t ) ) + c2 * r2 * ( pg - xi( t ) ) （1）
 xi( t + 1 ) = xi( t ) + vi( t + 1 ) （2）
 
PS：这里的r1、r2是每一步迭代都需要更新的随机数
 c1、c2和w =则是一开始给定的一些参数，至于参数的给定取决于你自己每次测试这个程序所得到的经验–即哪些参数你跑出的结果比较好就选择哪些参数。
 在这里再插一句，在我的实践中认为没有必要去限制迭代过程中速度和位置是否超过最大值，如果在给定区间内存在最优值那么最后还是会迭代回来。只需要在给定的区间内初始化就OK了。在我最开始的测试过程中限制速度和位置是使程序变慢了的，但是我一开始的思路出了问题，到很后面才改正过来也么有再去测试这个，所以就不加评论了。
 
算法流程
 
 
标准PSO算法代码
 
function [xm,fv]=Pso(N,c1,c2,w,M,D)
 %c1:自我学习因子
 %c2:社会学习因子
 
%w:惯性权重
 %N:种群数量`
 %M:最大迭代次数
 %D:维数
 
%初始化种群、速度和位置
 tic
 for i=1:N
 for j=1:D
 x(i,j)=unifrnd(-10,10);
 v(i,j)=unifrnd(-10,10);
 end
 end
 
%根据适应度计算适应度值,初始化pi和pg
 for i=1:N
 y(i)=test(x(i,:));
 pi(i,:)=x(i,:); %y(i,:)为最优位置
 end
 k = find( y == min(y) ) ;
 pg=x(k(1), : ) ;
 %更新位置与速度
 for t=1:M
 for i=1:N
 v(i,:)=wv(i,:)+c1rand*(pi(i,:)-x(i,:))+c2rand(pg-x(i,:));
 x(i,:)=x(i,:)+v(i,:);
 if test(x(i,:))<y(i)
 y(i)=test(x(i,:));
 pi(i,:)=x(i,:);
 end
 if y(i)<test(pg)
 pg=pi(i,:);
 end
 end
 pbest(t)=test(pg);
 end
 
%输出结果
 disp(‘最优位置’);
 xm=pg
 disp(‘最优值’);
 fv=test(pg)
 plot(pbest)
 toc
 
test函数–就是适应度函数
 
function y = test( V )
 y=0;
 b=length(V);
 for i=1:b
 y=y+i*V(i)^2;
 end
 
标准粒子群算法的局限性
 
为进一步说明标准粒子群算法的局限性，做如下推理：
 设 φ1=c1*r1 ，φ2=c2r2 ，w=1，由式（1）、（2）可转化 为式（3）、（4）：
 Vi( t+1) =Vi( t) +φ1(pi -xi(t))+φ2(pg -xi(t)) （3）
 xi(t+1)=xi(t)+vi(t+1) （4）
 已知速度公式Vi+1=Vi +a×Δt ，可得： a=φ1(pi -xi(t))+φ2(pg -xi(t))=xi(t)″ （5）
 化简可得： xi(t)″+(φ1+φ2)xi(t)-(φ1pi +φ2pg)=0 （6）
 式（6）是二阶微分方程，通过二阶微分方程求解公式，求得搜索位置在 t 代的 x(t)的位置路径公式： xi(t)=C1 cos( φ1+φ2t)+C2 sin( φ1+φ2t) （7）
 由式（7）可知，xi(t) 在一个固定区间内波动，即在 该区间中寻找每个粒子第 t 次迭代后的位置，位置函数 xi(t) 没有振荡收敛，算法容易陷入局部最优。
 例如，令 C1=1,C2=1, φ1+φ2 =1 ，可得位置函数 xi(t)=cos(t)+ sin(t)的图像，如图1所示。在该图像中， 对于t∈[ -∞，+∞] ， xi(t) 始终在固定上下限 [- 2, 2] 内范围波动，没有振 荡收敛，容易陷入局部最优。因此，在算法中加入振荡 收敛，是跳出局部最优解，提高粒子群算法搜索性能和精度较有效的方法。[1]
 
 
改进标准粒子群算法的思想
 
胡建秀，曾建潮通过在标准二阶粒子群算法速度迭 代方程中引入二阶振荡环节的方法改进算法，来增加粒 子的多样性，提高算法的全局搜索能力，是改进位置函 数搜索区域较好的改进方法。使用二阶振荡环节后，算法前期具有较强的全局搜索能力，振荡收敛；而在后期强局部搜索，渐近收敛。 该粒子群算法的进化方程如下：
 Vi( t+1) =w×Vi( t ) + φ1(pi -(1+ξ1)xi(t)+ξ1xi(t-1))+ φ2(pg -(1+ξ2)xi(t)+ξ2xi(t-1)) （8） xi(t+1)=xi(t)+vi(t+1) （9） 算法振荡收敛：
 ξ1<2 φ1 -1 φ1 ，
 ξ2<2 φ2 -1 φ2 （10）
 算法渐进收敛：
 ξ1 ≥2 φ1 -1 φ1 ，
 ξ2 ≥2 φ2 -1 φ2 （11） 振荡收敛和渐进收敛示意图如图2和图3所示。[ 1 ]
 
 
改进后二阶振荡粒子群算法的迭代公式
 
Vi( t+1 ) =w×Vi( t ) + φ1(pi -(1+ξ1)xi(t)+ξ2xi(t-1))+ φ2(pg -(1+ξ3)xi(t)+ξ4xi(t-1)) （12） xi(t+1)=xi(t)+vi(t+1)
 
这个公式的实在上面的二阶振荡粒子群算法的基础上进行的改进，这里ξ虽然是随机数但是取值是有限制的：
 设最大迭代次数为Gmax ,
 0<ξ2<1+ξ1 2 ,0<ξ4 <1+ξ3 2 ,0<ξ1<1,0<ξ3<1 当 t < Gmax / 2时，
 ξ1<ξ2-1,ξ3<ξ4 -1,0<ξ2<1,0<ξ4 <1 当 t > Gmax / 2 时
 这么做的意义在于可以时算法在迭代的前半段振荡收敛；
 在迭代的后半段使其渐进收敛。
 这里的证明和上面的二阶振荡粒子群算法的类似，我这就不展开了，感兴趣的可以自己去找我参考的文献。
 PS：关于改进算法的流程图和标准算法的类似，无非就是加了一个迭代次数前一半和后一半参数的改变，这里就不加上去了。
 
改进二阶振荡粒子群算法代码
 
function [ z , best ] = PSO_1( w , Gmax ,lizishu , weidu ,a , b )
 %这个测试函数的最小值是0，取值范围是[-10 , 10]
 % z是最优点的适应值，best是记录最优位置的坐标
 
%lizishu输入需要的粒子数
 %weidu函数的自变量个数
 %a下界
 %b上界
 q=zeros(1,Gmax);
 tic
 p = inf * ones( 1 , lizishu ) ;%初始的最优解默认为inf
 % pg = 0 ;
 A = unifrnd( a , b , lizishu , weidu ) ;%A矩阵是位置矩阵，用于储存每一步计算出的位置
 B = unifrnd( a , b , lizishu , weidu ) ;%B是速度矩阵，用于储存每一布计算出的V
 C = A ;%用于记录每个粒子的最优位置
 D = unifrnd( a , b , lizishu , weidu ) ;%位置矩阵，用于记录上一次迭代的位置
 c = 2 ; %c通常取1.5 ， 这是一个经验值
 y = [] ;%给y申请空间
 for i = 1 : lizishu
 y = [ y , test( A( i ,: ) ) ] ;
 end
 
for i = 1 : lizishu
 if p( i ) > y( i )
 C( i , : ) = A( i , : ) ;
 end
 p( i ) = min( [ p( i ) , y( i ) ] ) ;%更新局部最优解
 end
 
%初始化全局最优解
 k = find( p == min( p ) ) ;
 pg = C( k( 1 ) , : ) ;
 q( i ) = test( pg ) ;
 
for i = 1 : Gmax
 i
 r1 = unifrnd( 0 , 1 ) ;
 r2 = unifrnd( 0 , 1 ) ;
 u1 = r1 * c ;
 u2 = r2 * c ;
 if i < Gmax / 2
 g1 = unifrnd( 0 , 1 ) ; % 这里g1是[ 0 , 1 ]上均匀分布的随机数
 g2 = ( 1 + g1 ) / 2 ;
 g3 = unifrnd( 0 , 1 ) ;
 g4 = ( 1 + g3 ) / 2 ;
 for j = 1 : lizishu
 B( j , : ) = w * B( j , : ) + u1 * ( C( j , : ) - ( 1 + g1 ) * A( j , : ) + g2 * D( j , : ) ) + u2 * ( pg - ( 1 + g3 ) * A( j , : ) + g4 * D( j , : ) ) ;
 D = A ;
 A( j , : ) = A( j , : ) + B( j , : ) ;
 end
 else
 g2 = unifrnd( 0 , 1 ) ; % 这里g2是[ 0 , 1 ]上均匀分布的随机数
 g1 = ( g2 - 1 ) / 4 ;
 g4 = unifrnd( 0 , 1 ) ;
 g3 = ( g4 - 1 ) / 4 ;
 for j = 1 : lizishu
 B( j , : ) = w * B( j , : ) + u1 * ( C( j , : ) - ( 1 + g1 ) * A( j , : ) + g2 * D( j , : ) ) + u2 * ( pg - ( 1 + g3 ) * A( j , : ) + g4 * D( j , : ) ) ;
 D = A ;
 A( j , : ) = A( j , : ) + B( j , : ) ;
 end
 end
 y = [] ;%下一次迭代前清空y
 for j = 1 : lizishu
 y = [ y , test( A( j ,: ) ) ] ;
 end
 
   for j = 1 : lizishu
      if p( j ) > y( j )
        C( j , : ) = A( j , : ) ;
      end
        p( j ) = min( [ p( j ) , y( j ) ] ) ;
   end

    k = find( p == min( p ) ) ;%找到最优解的位置
    pg = C( k( 1 ) , : ) ; %保存最优解坐标
    q(i) = test( pg ) ;
 
end
 z = q( Gmax ) ;
 best = pg ;
 toc
 plot(q)
 
test函数
 
function y = test( V )
 y=0;
 b=length(V);
 for i=1:b
 y=y+i*V(i)^2;
 end
 
两个算法的比较
 
PS:上面我只给了一个test函数,要测试其他的函数直接更改test函数即可。
 下面是两个维度跑出来的结果
 1、标准PSO算法：
 
 
 2、改进的二阶振荡PSO算法:
 
 

 在低维度上这两个算法没有太大差别，改进的算法速度上要稍微快一点。
 
下面把维度提升到100维：
 PS：为了便于观看我改了一下程序，最后都只输出一个最优值。
 1、这是标准PSO算法跑出的结果：
 很明显这并没有达到最优值，只是一个局部最优。
 
2、改进的PSO算法：
 
 可以看到改进的算法的结果在100维下依旧不错，而且很快。
 
下面我们尝试1000维：
 改进的PSO算法结果如下：
 
我也试过一些最小值是无穷的函数（X^3），以及一些振荡函数(sinx+cosx),都可以跑出结果，这里就不一个个的给出结果了。
 
PS：因为第一个算法不是我写的原因，是我同学写的我拿来用的，所以两个代码在风格上差别有点大。
 这个博客的证明部分基本上我都是从下面的文献里直接拿过来的。
 最后如果找出我的错误请告诉我，我会及时改正的。
 
参考文献
 
[ 1 ] 蒋丽,叶润周，梁昌勇等，改进的二阶振荡粒子群算法[J]，计算机工程与应用,2009，55（9）：130-139

 
证明过程：
 
首先，假设我们已经对所有边进行了排序，并且当前遍历到的边是连接点1和点2的边
因为这条边是最小的边，而点1和点2在最小生成树中一定会直接或间接的相连，因此任何从点1到点2的路径都不小于这条边。如图，如果不走这条边就只能走1→3→2（而如果这样走显然会使得1→2的距离过大，而我们当前只讨论1→2的最优选项）。或者，我们可以假设一种情况：点1和点2之间有两条权值为0.5的边，间接的连接了点1和点2，那么这条路径显然比当前权值为2的边的权值小。但是我们是从小到大遍历边的，所以如果出现了这种情况，那么由于比权值为2的这条边小，那么他们必定已经被遍历。
由于那条路径已经被遍历过，那么这时候点1和点2就处于一个并查集了，也就是说我们不会再选择边权为2的这条边了。
因此我们可以证明出一个结论：图中权值最小的这条边必然要被选择。
假设我们已经选择了直接连接点1和点2的这条边，那么我们就可以对点1和点2进行缩点，由于最小生成树的性质（只要有路径连接两个任意结点即可），缩点对建图没有任何影响。
重复以上操作，直到边的数量等于点的数量减一（一个图的最小生成树的边的数量必定等于这个图的点的数量减一）即可得出最小生成树。
拓展资料：
 
求有向图最小生成树需要使用朱刘算法

 
 

 
【从零开始学机器学习第 10 篇】

 
摘要：机器学习最简单算法——kNN 算法总结。
 
对于不少想学机器学习的初学者来说，可能听到「机器学习」四个字就有点发怵，觉得难学门槛高，既要会编程数学还要好，那些科班出身的研究生才干得了。
 
这话也对也不对，要说它对是因为要学的内容的确不少也不简单，远不像数据分析、爬虫看着好学。其次，学习路径一定程度地被魔化了：很多人说学机器学习要先去啃《西瓜书》、《统计学习方法》这些大篇幅的数学公式算法书，很容易让新手放弃。
 
要说它不对也有道理。一是可能你并没有真正想去学它，没发现它有用或者至少有趣的地方；二是机器学习真的没有那么难入门，前提是找到合适自己的方法。所以想清楚为什么学和从哪儿开始学很重要。
 
看了很多教程后，找到了合适自己的机器学习入门方法，也觉得适合很多人，接下来会一点点分享出来。
 
作为入门的第一课，kNN 算法是最好的选择，因为它是机器学习中最简单的算法，学会它几乎没有难度只需要会两点：高中数学和一点 Python 编程基础（远没有爬虫那么难）。
 
虽然是最简单的算法，但我们还是花了大量篇幅（9 篇文章）来介绍它，为的是打好基础，今天这一篇做个总结。
 
kNN 算法（K-Nearest Neighbor），也叫 K 近邻算法，在具体介绍它之前，记住它的两个特点。
 
它有什么用途？主要有两种。
 
一是可以解决分类问题，比如预测红酒属于哪一类，花属于哪一种，是良性肿瘤还是恶性肿瘤等。除了二分类，它还可以解决多分类问题。
 
二是可以解决回归问题，比如预测房价多少、学生成绩多高等。
 
kNN 算法是少数能同时解决分类和回归问题的算法，很实用。
 
它的算法思想和实现难么？非常简单。
 
kNN 算法思想可以用「近朱者赤近墨者黑」形容，谁离待预测值近，待预测值就属于哪一类，就这么简单。判断远近可以用中学学过的欧拉距离公式计算。
 
知道特点后，我们通过一个酒吧猜酒的例子引入了 kNN算法：桌上倒的红酒属于两类，需要根据它们的颜色深度、酒精浓度值去预测新倒的酒属于哪一类：
 
【机器学习01】Python 手写机器学习最简单的 kNN 算法（可点击）

 

  
 
 
具体如何预测呢？很简单，只需要两步：先把场景抽象为数学问题，然后将数学问题写成 Python 代码得到预测结果。
 
抽象为数学问题就是把酒映射到坐标轴中，接着根据欧拉公式计算待预测酒（黄色点）同每杯样本酒（红绿色点）之间的距离，然后排序并取前 k 杯酒（k 个点），哪一类酒占比多，则新倒的酒就归属哪一类。
 

  
 
 
理清数学思路后就可以手写代码，手写代码可以加深对算法的理解，同时也能搞懂 Sklearn 调包背后的真正含义。
 
在这第一篇文章中，我们就手写了 kNN  算法，预测出新倒的酒（黄色点）属于绿色的赤霞珠。
 
接下来为了作对比，我们又调用了 Sklearn 中的 kNN 算法包，仅 5 行代码就得到了相同的结果。
 

  
 
 
初次接触 sklearn 的话，可能并不清楚代码背后的 fit、predict 做了什么，于是我们仿写了 Sklearn 的 kNN 算法包，加深了对 Sklearn 调包的理解：
 
【机器学习02】sklearn 中的 kNN 封装算法实现
 
通过以上两篇我们就初步学会了 kNN 算法。不过在对算法做预测时，使用了全部数据作为训练集，这样一来算法的预测准确率如何并不清楚。
 
所以我们做了改进，将数据集拆成一大一小两部分，大的作为训练集，小的作为测试集。在训练集上训练好 kNN 模型后，把测试集喂给它得到预测结果，接着和测试集本身的真实标签值作比较，得到了模型的准确率。
 
这一过程用到了 sklearn 的 train_test_split 方法，最终将一份有 178 个样本的葡萄酒数据集，按照 7:3 的比例随机划分出了 124 个训练样本和 54 个测试样本。
 
【机器学习03】手写 Sklearn 的 train_test_split 函数
 
具体如何计算模型的分类准确率呢？我们又用到了 sklearn 的 accuracy_score 方法，在葡萄酒数据集上达到了 76% 的准确率 。（54 个测试样本中，预测对了 41 个）
 
【机器学习04】Sklearn 的 model.score 和 accuracy_score 函数
 
为了巩固之前 4 节内容，我们又以两个机器学习中常见的数据集为例：鸢尾花和手写数字识别，初步走了一遍 kNN 分类算法。
 
【机器学习05】kNN小结：解决鸢尾花和手写数字识别分类
 

  
 
 
最后，模型在鸢尾花数据集上的准确率达到 97.8%（45 个花样本仅预测错 1 个），在手写数字数据集上的预测准确率达到了 98.7%。这是在使用默认参数而未调参的情况下得到的结果，可见 kNN 算法虽简单但效果很好。
 
不过，我们又发现存在一个问题：kNN 模型有很多参数（叫超参数），我们使用的都是默认参数，这样建立得到的模型不一定是最好的，而我们期望找到最好的模型。
 
如何做到呢？这就需要调参，于是我们了解了 kNN 算法几个重要的超参数，手动搭配组合之后找到了更好的模型，分类准确率进一步提升：
 
【机器学习06】调参——得到更好的 kNN 模型
 

  
 
 
但手动调整超参数很不方便，为此我们想到了 Sklearn 中专门实现调参功能的网格搜索方法（GridSearchCV），只需要指定超参数范围，它就会运行所有超参数组合建立模型，最后返回其中效果最好的一组，这比我们自己手写的方法方便地多。
 
【机器学习07】使用网格搜索（GridSearchCV）快速找到 kNN 模型最佳超参数
 

  
 
 
通过网格搜索我们进一步优化了 kNN 模型，这并没有完，还有很重要的一点工作：对数据做归一化处理。因为 kNN 模型跟样本距离有密切关系，如果特征之间的数量级相差很大的话，在计算距离时就容易产生偏差影响分类效果，所以最好建模前先去除数据量纲。
 

  
  
 
 

  
  
 
 

  
  
 
 
常用的数据归一化方式有最值归一化和均值方差归一化，详细对比了两种方法的特点，最终建议使用均值方差归一化：
 
【机器学习08】数据归一化 Feature Scaling
 
归一化处理后，之前葡萄酒模型的分类准确率从最初的 0.76 飙升到了 0.96。（54 个测试样本中，正确分类的样本数从 41 个上升到 52 个），可见数据归一化对 kNN 算法的重要性。
 
以上我们主要介绍的是 kNN 算法解决分类问题，它还可以解决回归问题，方法大同小异。为了加深理解，我们以常见的回归数据集波士顿房价为例，运用 kNN 回归模型预测了房价，效果不错。
 
【机器学习09】kNN 解决回归问题：以波士顿房价为例
 

  
 
 
以上就是 kNN 算法的主要内容，最后总结一下 kNN 算法的特点：
 
优点：
 
可解决二分类和多分类问题（一些算法只能解决二分类问题）
可解决回归问题（部分算法只能解决分类问题，解决不了回归问题）
算法简单效果好
 
缺点：
 
计算耗时
 
kNN 算法在计算样本距离时，每个样本都要遍历计算一篇全部训练样本，当数据量很大时，会很耗时，虽然可以用 KD 树、球树等改进方法但效率依然不高。
 
对异常值敏感
 
kNN 算法预测结果依赖最近的 K 个点，一旦 K 个点之中有异常值，很可能会分类错误。
 
预测结果不具有可解释性
 
对于预测的结果，并不能解释预测值为什么属于这个类别。不像线性回归算法具有可解释性。
 
维数灾难
 
随着维度的增加，“看似相近”的两个点，它们之间的距离会随着特征维数的增多而越来越大。比如有 2 个特征的数据集，两个点之间的距离是1.4，一旦特征数量增大到 10000 维时，距离就变成了 100。
 

  
 
 
相信看完这十篇文章，应该就可以搞明白 kNN 算法了，也能看得懂李航《统计学习方法》第 3 章的 kNN 算法。
 
到这儿，你就迈出了机器学习的第一步。接下来一起学习第二个算法吧：线性回归。
 
最后以上所有文章代码，可以在下方公众号中回复：knn 得到。