一维高斯分布： p ( x ) = 1 2 π σ e − ( x − μ ) 2 / 2 σ 2 p(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-(x-\mu)^2/2\sigma^2} p(x)=2π σ1e−(x−μ)2/2σ2 多维高斯分布： p ( X ; μ , Σ ) = 1 ( 2 π ) ( n / 2 ) ∣ Σ ∣ 1 / 2 exp { − 1 2 ( X − μ ) T Σ − 1 ( X − μ ) } p(X;\mu,\Sigma)=\frac{1}{(2\pi)^{(n/2)}|\Sigma|^{1/2}}\exp\{-\frac{1}{2}(X-\mu)^T\Sigma^{-1}(X-\mu)\} p(X;μ,Σ)=(2π)(n/2)∣Σ∣1/21exp{−21(X−μ)TΣ−1(X−μ)}
类条件概率： P ( X ∣ Y ) P(X|Y) P(X∣Y) 先验概率： P ( Y ) P(Y) P(Y)，一般会给定 Y ∼ N ( μ , Σ ) Y\sim N(\mu,\Sigma) Y∼N(μ,Σ) 后验概率： P ( Y = i ∣ X ) = P ( X ∣ Y = i ) P ( Y = i ) P ( X ) = P ( X ∣ Y = i ) P ( Y = i ) ∑ P ( X ∣ Y = i ) P ( Y = i ) = π i P i ( X ) ∑ π i P i ( X ) = q i ( X ) P(Y=i|X)=\frac{P(X|Y=i)P(Y=i)}{P(X)}=\frac{P(X|Y=i)P(Y=i)}{\sum P(X|Y=i)P(Y=i)}=\frac{\pi_iP_i(X)}{\sum\pi_iP_i(X)}=q_i(X) P(Y=i∣X)=P(X)P(X∣Y=i)P(Y=i)=∑P(X∣Y=i)P(Y=i)P(X∣Y=i)P(Y=i)=∑πiPi(X)πiPi(X)=qi(X) 贝叶斯测试： q i ( x ) ≶ q j ( x ) q_i(x)\lessgtr q_j(x) qi(x)≶qj(x) 似然率： l ( X ) = q i ( X ) q j ( X ) \mathcal{l}(X)=\frac{q_i(X)}{q_j(X)} l(X)=qj(X)qi(X) 区分方程： h ( x ) = ln q i ( X ) q j ( X ) ≶ ln π j π i h(x)=\ln\frac{q_i(X)}{q_j(X)}\lessgtr\ln\frac{\pi_j}{\pi_i} h(x)=lnqj(X)qi(X)≶lnπiπj
例：假设 Y = 1 Y=1 Y=1和 Y = 2 Y=2 Y=2两类， Y 1 ∼ N ( μ 1 , Σ ) , Y 2 ∼ N ( μ 2 , Σ ) Y_1\sim N(\mu_1,\Sigma),Y_2\sim N(\mu_2,\Sigma) Y1∼N(μ1,Σ),Y2∼N(μ2,Σ)贝叶斯分类器分出来，分界线应该是一条直线 ln p 1 π 1 p 2 π 2 = ln π 1 exp { − 1 2 ( X − μ 1 ) T Σ − 1 ( X − μ 1 ) } π 2 exp { − 1 2 ( X − μ 2 ) T Σ − 1 ( X − μ 2 ) = − 1 2 ( X − μ 1 ) T Σ − 1 ( X − μ 1 ) + 1 2 ( X − μ 2 ) T Σ − 1 ( X − μ 2 ) + ln π 1 π 2 = 1 2 ( − X T Σ − 1 X + μ 1 T Σ − 1 X + X T Σ − 1 μ 1 − μ 1 T Σ − 1 μ 1 + X T Σ − 1 X − μ 2 T Σ − 1 X − X T Σ − 1 μ 2 + μ 2 T Σ − 1 μ 2 ) + ln π 1 π 2 = ( μ 1 T Σ − 1 − μ 2 T Σ − 1 ) X + 1 2 ( μ 1 T Σ − 1 μ 1 − μ 2 T Σ − 1 μ 2 ) + ln π 1 π 2 = 0 \ln\frac{p_1\pi_1}{p_2\pi_2}=\ln\frac{\pi_1\exp\{-\frac{1}{2}(X-\mu_1)^T\Sigma^{-1}(X-\mu_1)\}}{\pi_2\exp\{-\frac{1}{2}(X-\mu_2)^T\Sigma^{-1}(X-\mu_2)}\\=-\frac{1}{2}(X-\mu_1)^T\Sigma^{-1}(X-\mu_1)+\frac{1}{2}(X-\mu_2)^T\Sigma^{-1}(X-\mu_2)+\ln\frac{\pi_1}{\pi_2}\\=\frac{1}{2}(-X^T\Sigma^{-1}X+\mu_1^T\Sigma^{-1}X+X^T\Sigma^{-1}\mu_1-\mu_1^T\Sigma^{-1}\mu_1+X^T\Sigma^{-1}X-\mu_2^T\Sigma^{-1}X-X^T\Sigma^{-1}\mu_2+\mu_2^T\Sigma^{-1}\mu_2)+\ln\frac{\pi_1}{\pi_2}\\=(\mu_1^T\Sigma^{-1}-\mu_2^T\Sigma^{-1})X+\frac{1}{2}(\mu_1^T\Sigma^{-1}\mu_1-\mu_2^T\Sigma^{-1}\mu_2)+\ln\frac{\pi_1}{\pi_2}=0 lnp2π2p1π1=lnπ2exp{−21(X−μ2)TΣ−1(X−μ2)π1exp{−21(X−μ1)TΣ−1(X−μ1)}=−21(X−μ1)TΣ−1(X−μ1)+21(X−μ2)TΣ−1(X−μ2)+lnπ2π1=21(−XTΣ−1X+μ1TΣ−1X+XTΣ−1μ1−μ1TΣ−1μ1+XTΣ−1X−μ2TΣ−1X−XTΣ−1μ2+μ2TΣ−1μ2)+lnπ2π1=(μ1TΣ−1−μ2TΣ−1)X+21(μ1TΣ−1μ1−μ2TΣ−1μ2)+lnπ2π1=0 计算完发现这就是 w T X + b = 0 w^TX+b=0 wTX+b=0的形式
r ( X ) = min [ q 1 ( x ) , … , q n ( x ) ] r(X)=\min[q_1(x),\dots,q_n(x)] r(X)=min[q1(x),…,qn(x)] 当是一个二分类问题的时候， r ( X ) = min [ q 1 ( x ) , q 2 ( x ) ] r(X)=\min[q_1(x),q_2(x)] r(X)=min[q1(x),q2(x)] ε = E [ r ( X ) ] = ∫ r ( x ) p ( x ) d x = ∫ min [ q 1 ( x ) π 1 , q 2 ( x ) π 2 ] d x = π 1 ε 1 + π 2 ε 2 \varepsilon=E[r(X)]=\int r(x)p(x)dx=\int\min[q_1(x)\pi_1,q_2(x)\pi_2]dx=\pi_1\varepsilon_1+\pi_2\varepsilon_2 ε=E[r(X)]=∫r(x)p(x)dx=∫min[q1(x)π1,q2(x)π2]dx=π1ε1+π2ε2 并且能够证明，贝叶斯估计的误差是最小的（取两个高斯分布的交点），当如果两个高斯分布没有交点时，可以通过给两个高斯分布乘以某一个系数 a , b a,b a,b，然后再计算 其中 ε 1 = S ( A ) , ε = S ( B + C ) \varepsilon_1=S(A),\varepsilon=S(B+C) ε1=S(A),ε=S(B+C)
h ( x ) = − ln q 1 ( X ) + ln q 2 ( X ) ≶ ln π 1 π 2 h(x)=-\ln q_1(X)+\ln q_2(X)\lessgtr\ln\frac{\pi_1}{\pi_2} h(x)=−lnq1(X)+lnq2(X)≶lnπ2π1中，已知 ln π 1 π 2 \ln\frac{\pi_1}{\pi_2} lnπ2π1去寻找 g ( X 1 , X 2 ) g(X_1,X_2) g(X1,X2)叫做带参数的产生式学习，不知道 ln π 1 π 2 \ln\frac{\pi_1}{\pi_2} lnπ2π1但是利用贝叶斯公式去寻找 g ( X 1 , X 2 ) g(X_1,X_2) g(X1,X2)叫做没有参数的产生式学习；判别式学习就是去直接寻找 g ( X 1 , X 2 ) g(X_1,X_2) g(X1,X2)
当一个预测一个样本时，我们把其嵌入我们的 N N N维空间中，然后统计与它最相邻的 k k k个点，并且按照一定的权重去处理这些距离，最后我们得到的距离最小的那个类就是这个样本的类别。 p ^ ( X ) = 1 N k − 1 V ( X ) \hat{p}(X)=\frac{1}{N}\frac{k-1}{V(X)} p^(X)=N1V(X)k−1 h ( x ) = − ln p 1 ( X ) p 2 ( X ) = − ln ( k 1 − 1 ) N 2 V 2 ( X ) ( k 2 − 1 ) N 1 V 1 ( X ) ≶ ln π 1 π 2 h(x)=-\ln\frac{p_1(X)}{p_2(X)}=-\ln\frac{(k_1-1)N_2V_2(X)}{(k_2-1)N_1V_1(X)}\lessgtr\ln\frac{\pi_1}{\pi_2} h(x)=−lnp2(X)p1(X)=−ln(k2−1)N1V1(X)(k1−1)N2V2(X)≶lnπ2π1，其中 K 1 + K 2 = K , V 1 = V 2 , N 1 N 2 = π 2 π 1 K_1+K_2=K,V_1=V_2,\frac{N_1}{N_2}=\frac{\pi_2}{\pi_1} K1+K2=K,V1=V2,N2N1=π1π2，那么 h ( x ) = − ln k 1 − 1 k 2 − 1 h(x)=-\ln\frac{k_1-1}{k_2-1} h(x)=−lnk2−1k1−1，就只跟数量有关了
def KNeighborsClassifier(n_neighbors = 5, weights='uniform', algorithm = '', leaf_size = '30', p = 2, metric = 'minkowski', metric_params = None, n_jobs = None ) - n_neighbors：这个值就是指 KNN 中的 “K”了。前面说到过，通过调整 K 值，算法会有不同的效果。 - weights（权重）：最普遍的 KNN 算法无论距离如何，权重都一样，但有时候我们想搞点特殊化，比如距离更近的点让它更加重要。这时候就需要 weight 这个参数了，这个参数有三个可选参数的值，决定了如何分配权重。参数选项如下： • 'uniform'：不管远近权重都一样，就是最普通的 KNN 算法的形式。 • 'distance'：权重和距离成反比，距离预测目标越近具有越高的权重。 • 自定义函数：自定义一个函数，根据输入的坐标值返回对应的权重，达到自定义权重的目的。 - algorithm：在 sklearn 中，要构建 KNN 模型有三种构建方式，1. 暴力法，就是直接计算距离存储比较的那种放松。2. 使用 kd 树构建 KNN 模型 3. 使用球树构建。 其中暴力法适合数据较小的方式，否则效率会比较低。如果数据量比较大一般会选择用 KD 树构建 KNN 模型，而当 KD 树也比较慢的时候，则可以试试球树来构建 KNN。参数选项如下： • 'brute' ：蛮力实现 • 'kd_tree'：KD 树实现 KNN • 'ball_tree'：球树实现 KNN • 'auto'： 默认参数，自动选择合适的方法构建模型 不过当数据较小或比较稀疏时，无论选择哪个最后都会使用 'brute' - leaf_size：如果是选择蛮力实现，那么这个值是可以忽略的，当使用KD树或球树，它就是是停止建子树的叶子节点数量的阈值。默认30，但如果数据量增多这个参数需要增大，否则速度过慢不说，还容易过拟合。 - p：和metric结合使用的，当metric参数是"minkowski"的时候，p=1为曼哈顿距离， p=2为欧式距离。默认为p=2。 - metric：指定距离度量方法，一般都是使用欧式距离。 • 'euclidean' ：欧式距离 • 'manhattan'：曼哈顿距离 • 'chebyshev'：切比雪夫距离 • 'minkowski'： 闵可夫斯基距离，默认参数 - n_jobs：指定多少个CPU进行运算，默认是-1，也就是全部都算。L 1 L_1 L1范数： ∣ x − x ′ ∣ = ∑ i = 1 n ∣ x i − x ′ ∣ |x-x'|=\sum\limits_{i=1}^n|x_i-x'| ∣x−x′∣=i=1∑n∣xi−x′∣ L ∞ L_\infin L∞范数： max ∣ x − x ′ ∣ \max{|x-x'|} max∣x−x′∣ 欧氏距离： D ( x , x ′ ) = ∑ σ i 2 ( x i − x i ′ ) 2 = ( x − x ′ ) T Σ − 1 ( x − x ′ ) D(x,x')=\sqrt{\sum\sigma_i^2(x_i-x_i')^2}=\sqrt{(x-x')^T\Sigma^{-1}(x-x')} D(x,x′)=∑σi2(xi−xi′)2 =(x−x′)TΣ−1(x−x′) 马氏距离：当欧氏距离的 Σ \Sigma Σ满且对称 角度： cos ( X 1 , X 2 ) = X 1 T X 2 ∣ X 1 ∣ ∣ X 2 ∣ \cos(X_1,X_2)=\frac{X_1^TX_2}{|X_1||X_2|} cos(X1,X2)=∣X1∣∣X2∣X1TX2 相关值： ( x i − X ‾ ) ( y j − Y ‾ ) ∑ ( X ‾ − x i ) 2 ∑ ( Y ‾ − y j ) 2 \frac{(x_i-\overline{X})(y_j-\overline{Y})}{\sqrt{\sum{(\overline{X}-x_i)}^2\sum{(\overline{Y}-y_j)^2}}} ∑(X−xi)2∑(Y−yj)2 (xi−X)(yj−Y)
我们想去查找跟目标点邻近的K个样本点，那么我们最朴素的方法就是爆搜，这样太慢了，我们就有下面的改进
kd树的主要思想就是我们把样本空间用一些垂直于坐标轴的超平面分成若干个超平面，然后通过这样的分割来建立一个二叉树，我们都知道二叉树的查找是非常快的，我们就能迅速的查找出我们想要的那个邻近点了。
建树伪代码： 输入：点集 S S S和空间range 输出：kd树 1.如果点集是空，那么就返回。 2.在样本的每一个维度上都计算方差，选方差大的那个维度作为切分的超平面（方差越大，样本越分散，切割效果越好）。将所有样本按照该维度的值排序，取中间点作为父节点，小于它的点作左子树，大于它的点作右子树。 3.递归建立左子树和右子树。
搜索伪代码： 输入：kd树，目标点 输入：最临近点 1.如果kd树是空的，那么就直接返回 2.我们按照二叉树的方式，并且按照划分的超平面顺序进行查找，直到找到一个叶子节点为止，我们认为这个可能就是临近点 3.但是由于我们的最临近点可能在分割超平面的另一半部分上，我们在2中找到的那个只是个局部最优，我们还需要回溯步骤。我们找到分割超平面的另一半的点，比较距离值。
其实跟kd树构建方式相似，但是这回并不是使用垂直于坐标轴的超平面进行分割，而是使用超球面进行分割。
参考：哈工大机器学习PPT https://www.cnblogs.com/eyeszjwang/articles/2429382.html https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html https://blog.csdn.net/weixin_41770169/article/details/81634307
