9. 降维与度量学习

文章链接

https://gitee.com/fakerlove/machine-learning

9.1 KNN

参考资料

https://blog.csdn.net/sinat_30353259/article/details/80901746

9.1.1 概念

KNN（K Near Neighbor）：k个最近的邻居，即每个样本都可以用它最接近的k个邻居来代表。

最近邻 (k-Nearest Neighbors， KNN) 算法是一种分类算法， 1968年由 Cover和 Hart 提出， 应用场景有字符识别、 文本分类、 图像识别等领域。 该算法的思想是： 一个样本与数据集中的k个样本最相似， 如果这k个样本中的大多数属于某一个类别， 则该样本也属于这个类别。

KNN可以说是最简单的分类算法之一，同时，它也是最常用的分类算法之一，注意KNN算法是有监督学习中的分类算法，它看起来和另一个机器学习算法Kmeans有点像（Kmeans是无监督学习算法），但却是有本质区别的。那么什么是KNN算法呢，接下来我们就来介绍介绍吧。

KNN(k-NearestNeighbor),就是k最近邻算法，这是一种常用的监督学习方法，简单来说，根据k个最近的邻居的状态来决定样本的状态，即‘物以类聚，人以群分’。

9.1.2 数学准备

参考资料

https://www.cnblogs.com/listenfwind/p/10311496.html

从这个名字我们就能看出一些KNN算法的蛛丝马迹了。K个最近邻居，毫无疑问，K的取值肯定是至关重要的。那么最近的邻居又是怎么回事呢？其实啊，KNN的原理就是当预测一个新的值x的时候，根据它距离最近的K个点是什么类别来判断x属于哪个类别。听起来有点绕，还是看看图吧。

图中绿色的点就是我们要预测的那个点，假设K=3。那么KNN算法就会找到与它距离最近的三个点（这里用圆圈把它圈起来了），看看哪种类别多一些，比如这个例子中是蓝色三角形多一些，新来的绿色点就归类到蓝三角了。

但是，当K=5的时候，判定就变成不一样了。这次变成红圆多一些，所以新来的绿点被归类成红圆。从这个例子中，我们就能看得出K的取值是很重要的。

明白了大概原理后，我们就来说一说细节的东西吧，主要有两个，K值的选取和点距离的计算。

1) 距离计算

要度量空间中点距离的话，有好几种度量方式，比如常见的曼哈顿距离计算，欧式距离计算等等。不过通常KNN算法中使用的是欧式距离，这里只是简单说一下，拿二维平面为例，二维空间两个点的欧式距离计算公式如下：

$\rho=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

这个高中应该就有接触到的了，其实就是计算$(x_1,y_1)$和$(x_2,y_2)$的距离。拓展到多维空间，则公式变成这样：

$d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\dots+(x_n-y_n)^2}=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}$

这样我们就明白了如何计算距离，KNN算法最简单粗暴的就是将预测点与所有点距离进行计算，然后保存并排序，选出前面K个值看看哪些类别比较多。但其实也可以通过一些数据结构来辅助，比如最大堆，这里就不多做介绍，有兴趣可以百度最大堆相关数据结构的知识。

9.1.2 算法介绍

1）计算待分类点与已知类别的点之间的距离

2）按照距离递增次序排序

3）选取与待分类点距离最小的K个点

4）确定前K个点所在类别的出现次数

5）返回前K个点出现次数最高的类别作为待分类点的预测分类

9.1.3 例子

参考资料

https://zhuanlan.zhihu.com/p/110066200

代码

import math

movie_data = {"宝贝当家": [45, 2, 9, "喜剧片"],
              "美人鱼": [21, 17, 5, "喜剧片"],
              "澳门风云3": [54, 9, 11, "喜剧片"],
              "功夫熊猫3": [39, 0, 31, "喜剧片"],
              "谍影重重": [5, 2, 57, "动作片"],
              "叶问3": [3, 2, 65, "动作片"],
              "伦敦陷落": [2, 3, 55, "动作片"],
              "我的特工爷爷": [6, 4, 21, "动作片"],
              "奔爱": [7, 46, 4, "爱情片"],
              "夜孔雀": [9, 39, 8, "爱情片"],
              "代理情人": [9, 38, 2, "爱情片"],
              "新步步惊心": [8, 34, 17, "爱情片"]}

# 测试样本  唐人街探案": [23, 3, 17, "？片"]
#下面为求与数据集中所有数据的距离代码：
x = [23, 3, 17]
KNN = []
for key, v in movie_data.items():
    d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2)
    KNN.append([key, round(d, 2)])

# 输出所用电影到 唐人街探案的距离
print(KNN)

#按照距离大小进行递增排序
KNN.sort(key=lambda dis: dis[1])

#选取距离最小的k个样本，这里取k=5；
KNN=KNN[:5]
print(KNN)

#确定前k个样本所在类别出现的频率，并输出出现频率最高的类别
labels = {"喜剧片":0,"动作片":0,"爱情片":0}
for s in KNN:
    label = movie_data[s[0]]
    labels[label[3]] += 1
labels =sorted(labels.items(),key=lambda l: l[1],reverse=True)
print(labels,labels[0][0],sep='\n')

例二

#coding:utf-8

from numpy import *
import operator

##给出训练数据以及对应的类别
def createDataSet():
    group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
    labels = ['A','A','B','B']
    return group,labels

###通过KNN进行分类
def classify(input,dataSe t,label,k):
    dataSize = dataSet.shape[0]
    ####计算欧式距离
    diff = tile(input,(dataSize,1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff,axis = 1)###行向量分别相加，从而得到新的一个行向量
    dist = squareDist ** 0.5
    
    ##对距离进行排序
    sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标

    classCount={}
    for i in range(k):
        voteLabel = label[sortedDistIndex[i]]
        ###对选取的K个样本所属的类别个数进行统计
        classCount[voteLabel] = classCount.get(voteLabel,0) + 1
    ###选取出现的类别次数最多的类别
    maxCount = 0
    for key,value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key

    return classes

接下来，在命令行窗口输入如下代码：

#-*-coding:utf-8 -*-
import sys
sys.path.append("...文件路径...")
import KNN
from numpy import *
dataSet,labels = KNN.createDataSet()
input = array([1.1,0.3])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("测试数据为:",input,"分类结果为：",output)

9.2 主成分分析PCA

参考资料

https://www.jianshu.com/p/7f664785d5f6

参考资料2

https://www.cnblogs.com/pinard/p/6239403.html

参考资料3

https://blog.csdn.net/lanyuelvyun/article/details/82384179

参考资料4

https://www.zhihu.com/question/41120789/answer/474222214

参考资料5

https://blog.csdn.net/zhongkelee/article/details/44064401

参考资料6

https://www.cnblogs.com/pinard/p/6239403.html

9.2.1 介绍

**主成分分析法：**英文全名 Principal Component Analysis 简称 PCA ，由名字就可以看出来，这是一个挑重点分析的方法。

就是找出数据里最主要的方面，用数据里最主要的方面来代替原始数据。

主成分分析法是通过恰当的数学变换 ，使新变量—— 成分成为原变量的线性组合 ，并选取少数几个在变差总信息量中比例较大的主成分来分析事物的一种方法 。主成分在变差信息量中的比例越大，它在综合评价中的作用就越大。

**思想：**整体思想就是化繁为简，抓住问题关键，也就是降维思想。当然，既然是抓住关键，那么自然就是以牺牲精度为代价。

**解决问题：**因为每个变量都在不同程度上反映了所研究问题的某些信息，并且指标之间彼此有一定的相关性，因而所得的统计数据反映的信息在一定程度上有重叠

在用统计方法研究多变量问题时，变量太多会增加计算量和分析问题的复杂性。

人们希望在进行定量分析过程中，涉及的变量较少，得到的信息量较多。为了尽可能的减少冗余和噪音，一般情况可以从相关变量中选择一个，或者把几个相关变量综合为一个变量作为代表，用少数变量来代表所有变量。

事实上，PCA寻找最佳的可能特性，那些可能总结红酒列表的特性中最好的那些（在所有可能的线性组合中）。因此它才这么有用。

9.2.2 原理介绍

1) 原理

求解步骤

• 去除平均值
• 计算协方差矩阵
• 计算协方差矩阵的特征值和特征向量
• 将特征值排序
• 保留前N个最大的特征值对应的特征向量
• 将原始特征转换到上面得到的N个特征向量构建的新空间中（最后两步，实现了特征压缩）

假设有$M$个样本$\{X^1,X^2,\cdots ,X^M \}$,每个样本有$N$维特征$X^i=(x_1^i,x^i_2,\cdots ,x^i_n)$,每一个特征$x_j$都有各自的特征值。以下面的数据为例

1. 对所有特征进行中心化：去均值

求每一个特征的平均值，然后对于所有的样本，每一个特征都减去自身的均值。

特征$x_1$的平均值:$\overline{x_1}=\frac{1}{M}\sum_{i=1}^Mx_1^i=\frac{1+2+2.5+0.3+6+\cdot +0.5}{10}=2.31$

特征$x_2$​​的平均值:$\overline{x_1}=\frac{1}{M}\sum_{i=1}^Mx_2^i=\frac{32+45+7+\cdots +10}{10}=2.31$

经过去均值处理之后，原始特征的值就变成了新的值，在这个新的norm_data的基础上，进行下面的操作。

2. 求协方差矩阵C

$$C=\begin{bmatrix}cov(x_1,x_2)&cov(x_1,x_2) \\ cov(x_2,x_1)&cov(x_2,x_2) \end{bmatrix}$$

上述矩阵中，对角线上分别是特征$x_1$和$x_2$的方差，非对角线上是协方差。协方差大于0表示$x_1$和$x_2$若有一个增，另一个也增；小于0表示一个增，一个减；协方差为0时，两者独立。协方差绝对值越大，两者对彼此的影响越大，反之越小。其中$cov(x_1,x_1)$的求解公式如下，其他类似

$$cov(x_1,x_1)=\frac{\sum_{i=1}^M(x_1^i-\overline{x_1})(x_1^i-\overline{x_1})}{M-1}$$

根据上面的协方差计算公式我们就得到了这$M$个样本在这$N$​维特征下的协方差矩阵C。

3. 求协方差矩阵C的特征值和相对应的特征向量

利用矩阵的知识，求协方差矩阵$C$的特征值$\lambda$和相对应的特征向量$u$(每一个特征值对应一个特征向量)

$$Cu=\lambda u$$

特征值$\lambda$会有N个，每一个$\lambda_i$对应一个特征向量$u_i$,将特征值$\lambda$按照从大到小的顺序牌照续，选择最大的前k个，并将其相对应的k个特征向量拿出来，我们会得到一组$\{(\lambda_1,u_1),(\lambda_2,u_2),\cdots,(\lambda_k,u_k)\}$。本例中原始特征只有2维，我在选取$\lambda$的时候，令$k=1$,选择最大的$\lambda_1$和其对应的$u_1$。

4. 将原始特征投影到选取的特征向量上，得到降维后的新K维特征

这个选取最大的前k个特征值和相对应的特征向量，并进行投影的过程，就是降维的过程。

对于每一个样本$X^i$,原来的特征是$(x^i_1,x^i_2,x^i_3,\cdots,x^i_n)$,投影之后的新特征是$(y^i_1,y^i_2,\cdots,y^i_k)$​,新特征的计算公式如下：

$$\begin{bmatrix}y_1^i\\ y_2^i\\ \vdots \\ y_k^i\end{bmatrix}=\begin{bmatrix}u_1^T(x_1^i,x_2^i,\cdots,x_n^i)^T\\ u_2^T(x_1^i,x_2^i,\cdots,x_n^i)^T\\ \vdots \\ u_k^T(x_1^i,x_2^i,\cdots,x_n^i)^T\end{bmatrix}$$

对于我们的例子来说，每一个样本$X^i$,由原来的$X^i=(x_1^i,x_2^i)^T$变成了现在$X^i=y_1^i$,达到了降维的目的。

2) 注意点

为什么样本在"协方差矩阵C的最大K个特征值所对应的特征向量"上的投影就是k维理想特征？

最大方差理论:方差越大，信息量就越大。协方差矩阵的每一个特征向量就是一个投影面，每一个特征向量所对应的特征值就是原始特征投影到这个投影面之后的方差。

由于投影过去之后，我们要尽可能保证信息不丢失，所以要选择具有较大方差的投影面对原始特征进行投影，也就是选择具有较大特征值的特征向量。

然后将原始特征投影在这些特征向量上，投影后的值就是新的特征值。每一个投影面生成一个新的特征，k个投影面就生成k个新特征。

PCA降维的目的，就是为了在尽量保证“信息量不丢失”的情况下，对原始特征进行降维，也就是尽可能将原始特征往具有最大信息量的维度上进行投影。

将原特征投影到这些维度上，使降维后信息量损失最小。

那为什么协方差矩阵的特征向量可以看做是投影面，相对应的特征值是原始特征投影到这个投影面之后的方差？？

现在，假设有以下几个样本，特征只有2个维度。做完预处理（减去了均值，这步很重要，之后会解释）之后，分布如下：

现在将这些样本往低维空间进行投影，二维特征降维的话就是往一维降，投影直线有很多，比如下面的$u_1$和$u_2$,选哪一条比较好呢？

根据方差最大理论，选择投影过去之后，样本方差最大的那条投影直线作为投影维度，对原始特征进行降维。经过计算，$u_1$比较好，因为投影后的样本点之间方差最大。

那么，投影过去之后样本之间的方差怎么计算？

以一个样本$X^i$为例，蓝色点表示该样本，原始特征有2维，绿色点表示样本在u上的投影，u是该投影直线的单位向量。那么该样本的原二维特征$X_i=(x_1,x_2)^T$投影到这个投影直线上就变成了一维特征（从二维坐标系变到了一维坐标系u上),这个一维特征的值 = 投影点到原点的距离：$x^{i^T}u$.（根据向量的计算公式得到）。

同理，其他的样本投影到该投影直线上，生成的新的一维特征也这么计算。那么，投影之后的所有样本之间的方差就等于（根据方差的定义）：

$$方差=\frac{1}{M}\sum_{i=1}^M(x^{i^T}u-所有x^{i^T}u的均值)^2=\frac{1}{M}\sum_{i=1}^M(x^{i^T}u)^2$$

由于这些样本原特征的每一维特征在最一开始都进行了去均值操作，所以$X^i$每一维特征的均值都为0，因此投影到u上的特征的均值仍然是0(所有${x^i}^Tu$​的均值=0) ,对上式进行变换

$$方差=\frac{1}{M}\sum_{i=1}^M(x^{i^T}u)^2=\frac{1}{M}\sum_{i=1}^Mu^Tx^i{x^i}^Tu=u^T(\frac{1}{M}\sum_{i=1}^Mx^i{x^i}^T)u$$

那么怎么求这个方差的最大值呢？我们发现$\frac{1}{M}\sum_{i=1}^Mx^i{x^i}^T$是一个方形矩阵，我们可以从矩阵的角度求解，令方差$\frac{1}{M}\sum_{i=1}^M({x^i}^Tu)^2=\lambda,C=\frac{1}{M}\sum_{i=1}^Mx^i{x^i}^T$,上式就变成了

$$\lambda=u^TCu$$

由于$u$是单位向量，$uu^T=1$,上式两边左乘$u$得，

$$Cu=\lambda u$$

方差$\lambda$就是方阵$C$的特征值，u是特征向量。一个矩阵的特征值$\lambda$根据矩阵运算很容易求得。所以求解$\lambda$的关键就是构造出矩阵C，我们把矩阵$C=\frac{1}{M}\sum_{i=1}^Mx^i{x^i}^T$展开，把$x^i=(x_1^i,x_2^i)^T$带进去，

$$C=\frac{1}{M}\sum_{i=1}^Mx^i{x^i}^T=\frac{1}{M}\sum_{i=1}^M\begin{pmatrix}x_1^i\\ x_2^i\end{pmatrix}\begin{pmatrix}x_1^i&x_2^i\end{pmatrix} \\ =\frac{1}{M}\sum_{i=1}^M\begin{pmatrix}x_1^ix_1^i&x_1^ix_2^i\\ x_2^ix_1^i&x_2^ix_2^i\end{pmatrix} \\ =\begin{pmatrix}\frac{\sum_{i=1}^M(x_1^i-0)(x_1^i-0)}{M}& \frac{\sum_{i=1}^M(x_1^i-0)(x_2^i-0)}{M}\\ \frac{\sum_{i=1}^M(x_2^i-0)(x_1^i-0)}{M}& \frac{\sum_{i=1}^M(x_2^i-0)(x_2^i-0)}{M}\end{pmatrix}$$

由于$x_1$和$x_2$在最一开始，做了去均值处理，所以$\overline{x_1}=0,\overline{x_2}=0$。所以上述矩阵就是一个协方差矩阵！！

这样，我们就求出了多个$\lambda$(方差)以及与之相对应的投影直线$u$！！！最佳的投影直线是最大的$\lambda_1$对应的特征向量$u_1$拥有最大投影方差），其次是第二大的$\lambda_2$对应的特征向量$u_2$（拥有次大投影方差），依次类推。通过选取拥有最大前$k$个$\lambda$个$u$。 对原始特征进行投影，使得原始特征被降维，并且尽可能保证最大的信息量。

3) 例子

amoeba设想了一个大家庭聚餐的场景，大家突然对PCA是怎么回事很感兴趣，于是你逐一向家庭成员解释，首先是曾祖母，接着是祖母，接着是母亲，然后是配偶，最后是女儿，每个人都比上一个人内行一点。

曾祖母：我听说你正研究P……C……A。我想知道它是什么……

**你：**呃，这只是一种总结某些数据的方法。看，桌子那边有一些红酒瓶。我们可以通过色泽、酒精度、年份等描述每瓶红酒。这样可以根据酒窖中每瓶红酒的不同特性编制一张完整的列表。但是其中很多属性是相关的，因此会出现一些冗余。因此我们可以通过更少的特性总结每瓶酒！这正是PCA做的。

祖母：很有趣！所以这PCA检查哪些特性是冗余的，然后丢弃它们？

你：问得好，奶奶！不，PCA并没有选择一些特性然后丢弃其余。相反，它创建一些新特性，结果这些新特性能够很好地总结我们的红酒列表。当然，这些新特性是由旧特性构建的；例如，一个新特性可能通过计算年份减去酸度或其它类似的组合得出（我们称之为线性组合）。

母亲：嗯，听起来不错，但我不确定我理解它了。你说的“总结”红酒列表的新PCA特性具体指什么？

**你：**对于这个问题，我猜我可以给出两个不同的答案。第一个答案是你寻找一些在所有红酒中很不相同的属性（特性）。事实上，想象你得到了一个对于大多数红酒而言都一样的特性。那不会很有用的，对不对？红酒和红酒很不一样，而你的新属性让它们看起来都差不多了！这肯定是一个错误的总结。相反，PCA寻找能尽可能体现红酒差异的属性。

第二个答案是你寻找一些属性，这些属性允许你预测，或者说“重建”原本的红酒特性。同样，想象你得出了一个和原本的特性没什么关系的属性；如果你仅仅使用这一新属性，你不可能重建原本的特性！这又将是一个不好的总结。所以PCA寻找能够尽可能好地重建原本特性的属性。

令人惊讶的是，结果这两个目标是等效的，所以PCA可以一箭双雕。

配偶：但是，亲爱的，这两个PCA的“目标”听起来可不一样，为什么它们会是等效的？

**你：**嗯。也许我应该画一点东西（你拿了一张纸巾，然后开始涂鸦）。让我们挑选两个红酒特性，也许是颜色浓淡和酒精含量——我不知道它们是否相关，但是让我们想象它们是相关的。不同红酒的散点图可能是这样的：

这一片“红酒云”中的每个点代表一种特定的红酒。你可以看到，两种属性（x轴和y轴）是相关的。在这片红酒云的中央画一条直线，将所有点投影到这条直线上，我们可以构建一个新属性。这一新属性将由w1x+w2y的线性组合定义，每条线对应w1和w2的特定值。

现在，看好了——下面是不同的直线上的投影会是怎么样的（红点是蓝点的投影）：

正如我之前所说的，PCA会根据两种不同的“最佳”的标准找到“最佳”的直线。首先，这条线上的差异应该最大化。注意观察当直线旋转的时候，红点是如何“散布”（我们称之为“方差”）的；你能看到它们何时最大化了吗？其次，如果我们基于新特性（红点的位置）重建原本的两个特性（蓝点的位置），连接红线的长度将给出重建误差。注意观察当直线旋转的时候，红线的长度是如何改变的；你能看到它们的总长度何时最小化了吗？

如果你凝视上面的动画有一会儿的话，你会注意到“最大方差”和“最小误差”将同时达到，也就是当直线指向我在红酒云两侧标出的品红色短线时。这一直线对应于PCA将构建的新红酒属性。

顺便说下，PCA代表“主成分分析”（principal component analysis），而这个新属性称为“第一主成分”。同时，我们通常不说“属性”（property）或“特性”（characteristic），而说“特征”（feature）或“变量”（variable）。

女儿：挺不错的，爸爸！我想我知道为什么这两个目标产生一样的结果：本质上这是因为勾股定理，不是吗？不管怎么说，我听说PCA多少和本征向量、本征值有点关系；图中它们在哪里呢？

你：有才！从数学上说，我们通过每个红点到红酒云中心的均方根距离来衡量红点的散布；正如你所知的，这叫做方差。另一方面，整体的重建误差通过相应的红线的均方根距离来衡量。然而由于红线和黑线间的角度永远是90度，两个量之和等于红酒云中心与每个蓝点的均方根距离；这正是勾股定理。当然，这些均方跟距离不依赖于黑线的朝向，因此方差越高，误差就越低（因为两者之和是常数）。

顺便，你可以把黑线想象成硬质杆，然后把红线想象成弹簧。弹簧的势能和它的长度平方成正比（物理学上这称为胡克定律），所以杆将调整自己的朝向以最小化这些平方距离的总和。我做了一个关于它大概是什么样的模拟，加上了一点摩擦力。

关于本征向量和本征值。你知道协方差矩阵吧；在我的例子中它是一个2x2的矩阵

$\begin{pmatrix}1.07&0.63\\ 0.63&0.64\end{pmatrix}$

这意味着x变量的方差是1.07，而y变量的方差是0.64，它们之间的协方差是0.63。由于这是一个对称正方矩阵，给定它的本征向量，选用一个新的直角坐标系可以使其对角化（凑巧的是，这称为谱定理）。对角上的值就是对应的本征值。在这个新坐标系中，协方差矩阵是对角化的，看起来大概是这样：

$\begin{pmatrix}1.53&0\\ 0&0.19\end{pmatrix}$​​​

这意味着，现在点之间的相关性为零。很明显，投影的方差将由特征值的加权平均决定（我这里只描写了直觉）。

因此，选择第一组坐标轴上的投影将达到最大可能方差（1.52）。由此得出，第一主成分的方向由协方差矩阵的第一个本征向量指定。

你也可以在旋转的图像上观察到这一点，图像上有一条与黑色直线正交的灰色直线；它们一起组成了一个旋转坐标系。试着留意在这一旋转坐标系中，何时蓝点变得不相关。答案仍然是黑色直线指向品红色的短线的时候。现在我可以告诉你我如何找到这两根短线的：它们标记了协方差矩阵的第一个本征向量的方向，在这个例子中是(0.81, 0.58)。

9.2.3 优缺点

优点：

• 以方差衡量信息的无监督学习，不受样本标签限制。
• 由于协方差矩阵对称，因此k个特征向量之间两两正交，也就是各主成分之间正交，正交就肯定线性不相关，可消除原始数据成分间的相互影响
• 可减少指标选择的工作量
• 用少数指标代替多数指标，利用PCA降维是最常用的算法
• 计算方法简单，易于在计算机上实现。

缺点：

• 主成分解释其含义往往具有一定的模糊性，不如原始样本完整
• 贡献率小的主成分往往可能含有对样本差异的重要信息，也就是可能对于区分样本的类别（标签）更有用
• 特征值矩阵的正交向量空间是否唯一有待讨论
• 无监督学习