关键字
样本的特征数称为维数（dimensionality），当维数非常大时，也就是现在所说的“维数灾难”，具体表现在：在高维情形下，数据样本将变得十分稀疏，因为此时要满足训练样本为“密采样”的总体样本数目是一个触不可及的天文数字，训练样本的稀疏使得其代表总体分布的能力大大减弱，从而消减了学习器的泛化能力；同时当维数很高时，计算距离也变得十分复杂，甚至连计算内积都不再容易，这也是为什么支持向量机（SVM）使用核函数“低维计算，高维表现”的原因。
1、k近邻学习（KNN算法）
k近邻学习是一种常用的监督学习方法，无需训练训练集，是较为简单的经典机器学习算法之一，可以处理回归问题和分类问题。
其工作机制很简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法中k的出处，通常k是不大于20的整数。
通常在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这k个样本的实值输出标记的平均值作为预测结果，还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。
投票法：通常在分类任务中使用，判别方法是选择这k个样本中出现最多的雷冰标记作为预测结果。
平均法：通常在回归任务中使用，判别方法是将这k个样本的实值输出标记的平均值最为预测结果。
加权平均或加权投票：根据距离远近来决定权重，距离越近，权重越大。
2、SVM和KNN算法区别
SVM算法样本需要固定，属于急切性学习，即在存在训练阶段，在学习模型中训练好后，与验证集比较，将低维度问题上升到高纬度
KNN算法不需要固定样本数量，属于懒惰学习，没有显示的训练过程，它在训练阶段只是把数据保存下来，训练时间开销为0，等收到测试样本后进行处理
3、KNN优缺点：
优点：
（1）简单，易于理解，易于实现，无需参数估计，无需训练，用法灵活;（2） 精度高，对异常值不敏感，无数据输入假定
（3）适合对稀有事件进行分类;
（4） 适合于多分类问题(multi-modal,对象具有多个类别标签)，KNN要比SVM表现要好
（5）对于小样本预测方便
缺点：
（1）计算复杂度高、空间复杂度高，对大量测试样本计算量大，资源开销大。
（2）K值的选择：最大的缺点是当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
（3） KNN是一种消极学习方法、懒惰算法。 缺少训练阶段，无法应对多样本。
4、KNN实现步骤：
1）计算距离
欧氏距离（Euclidean distance），即
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点（一般不大于20个）；
4）确定前K个点所在类别的出现频率:
出现频率 =某个类别 / k
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。
举个例子，根据下图，测试样本m在图中央，若k=1时，样本m的近邻点为“+”，则判断样本m为“+”。当k=3时，近邻点有1个+、2个-，则判断为“-”。当k=5时，近邻点有3个+、2个-，则判断为“+”。
4.1、欧几里得距离、巴氏距离、马氏距离的区别：
欧几里得距离
欧几里得距离也叫做（欧氏距离）是欧几里得空间中两点的“普遍”（直线距离）。
缺点主要有两个：(1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。
举个例子：二维样本(身高,体重)，其中身高范围是150-190，体重范围是50-60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm不等价于体重的10kg。
代码实现
import numpy as np
np.linalg(vector1-vector2, ord=2)
巴氏距离
在统计中，Bhattacharyya距离测量两个离散或连续概率分布的相似性。它与衡量两个统计样品或种群之间的重叠量的Bhattacharyya系数密切相关。Bhattacharyya距离和Bhattacharyya系数以20世纪30年代曾在印度统计研究所工作的一个统计学家A. Bhattacharya命名。同时，Bhattacharyya系数可以被用来确定两个样本被认为相对接近的，它是用来测量中的类分类的可分离性。
巴氏距离的定义
对于离散概率分布 p和q在同一域 X，它被定义为：
其中
它是Bhattacharyya系数。
马氏距离
由印度科学家马哈拉诺比斯提出，表示数据的协方差距离。是一种有效的计算两个位置样本集相似度的方法。与欧氏距离不同的是他考虑到各种特性之间的联系并且是尺度无关的，即独立于测量尺度。如果协方差矩阵为单位矩阵，马氏距离就简化为欧式距离，如果协方差矩阵为对角阵，其也可称为正规化的马氏距离。
优点：（1）它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关。（它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的(scale-invariant)，即独立于测量尺度）；（2）马氏距离还可以排除变量之间的相关性的干扰。
缺点：（1）夸大了变化微小的变量的作用。（2）受协方差矩阵不稳定的影响，马氏距离并不总是能顺利计算出。即计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在。（3）如果样本的维数非常大，那么计算它的协方差矩阵是十分耗时的
代码实现：
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
#马氏距离要求样本数要大于维数，否则无法求协方差矩阵
#此处进行转置，表示10个样本，每个样本2维
X=np.vstack([x,y])
XT=X.T
#根据公式求解
S=np.cov(X) #两个维度之间协方差矩阵
SI = np.linalg.inv(S) #协方差矩阵的逆矩阵
#马氏距离计算两个样本之间的距离，此处共有10个样本，两两组合，共有45个距离。
n=XT.shape[0]
d1=[]
for i in range(0,n):
for j in range(i+1,n):
delta=XT[i]-XT[j]
d=np.sqrt(np.dot(np.dot(delta,SI),delta.T))
d1.append(d)
表格统计
| 欧氏距离 | 巴氏距离 | 马氏距离 | |
|---|---|---|---|
| 优点 | 易于理解、适用于大多数场景 | 可以测量两个离散或连续概率分布的相似性。 | （1）它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关。 （2）马氏距离还可以排除变量之间的相关性的干扰。 |
| 缺点 | (1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。 | 使用场景较少 | （1）夸大了变化微小的变量的作用。 （2）受协方差矩阵不稳定的影响，马氏距离并不总是能顺利计算出。 （3）如果样本的维数非常大，那么计算它的协方差矩阵是十分耗时的！ |
| 相同点 | （1）如果马氏距离的协方差矩阵为单位矩阵，马氏距离就简化为欧氏距离 | （2）欧氏和马氏都是计算两个未知样本集的相似度的方法。 | （3）欧氏和马氏距离都可以计算多维度数据 |
| 不同点 | （1）马氏距离它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关而欧氏当各个分量为不同性质的量时，“距离”的大小与指标的单位有关。它将样品的不同属性之间的差别等同看待 | （2）马氏距离的计算是不稳定的而欧氏和巴氏是稳定的 | （3）巴氏距离测量两个离散或连续概率分布的相似性 |
| 公式 |  |
 |
 |
参考博客：
https://blog.csdn.net/jideljd_2010/article/details/39938555
https://blog.csdn.net/shenbo2030/article/details/44226919
https://blog.csdn.net/mousever/article/details/45967643
5、MDS多维标度法
k近邻学习方法基于一个重要的假设：任意测试样本x附近任意小的 距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为密采样（dense sample）。不过这在现实任务中一般很难满足，假设 ，在单个属性情况下，仅需1000个样本点平均分布在归一化后的属性取值范围内[0,1]，即可使得任务测试样本在其附近0.001距离范围内总能找到一个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍；但若在多个属性情况下，如假定属性维数是20，按照密采样条件要求，至少需要 (〖10〗^3 )20=〖10〗60个样本。现实应用中属性维数众多，要满足密采样条件，所需的样本数目将是天文数字。而且还要考虑距离度量计算，高维空间对距离计算来说不是简单的开销，当维数很高时，连计算内积都不容易。
上文的分析暴露一个很严重的问题，就是高维情形下，样本数的采样以及距离计算问题。在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为维数灾难（curse of dimensionality）。
缓解维数灾难的两个途径：一是特征选择；二是本文要重点介绍的降维（dimension reduction）。思路上，这两种途径都是减少维数，不过一个是在事前，一个是在事中。降维，也称维数约简，通过某种数学变换将原始高维属性空间转变为一个低维子空间（subspace），在子空间中，样本密度可以大幅提高，距离计算也相对容易。事实上，观测或收集到的数据样本虽然是高维的，但与学习任务相关的或许只是某个低维分布，这也是特征选择可以事前根据业务来定义的。
在很多时候，人们观测或收集到的数据样本虽然是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维嵌入，如图10.2，原始高维空间中的样本点，在这个低维嵌入空间中更容易进行学习。
线性降维方法：基于线性变换来进行降维的方法。
5.1 不管是使用核函数升维还是对数据降维，我们都希望原始空间样本点之间的距离在新空间中基本保持不变，这样才不会使得原始空间样本之间的关系及总体分布发生较大的改变。“多维缩放”（MDS）正是基于这样的思想，MDS要求原始空间样本之间的距离在降维后的低维空间中得以保持，如图10.2
算法实现：
import numpy as np
import operator
def createDataset():
#四组二维特征
group = np.array([[5,115],[7,106],[56,11],[66,9]])
#四组对应标签
labels = ('动作片','动作片','爱情片','爱情片')
return group,labels
def classify(intX,dataSet,labels,k):
'''
KNN算法
'''
#numpy中shape[0]返回数组的行数，shape[1]返回列数
#MDS降维操作
dataSetSize = dataSet.shape[0]
#去逆矩阵
diffMat = np.tile(intX,(dataSetSize,1))-dataSet
#二维特征相减后乘方
sqdifMax = diffMat**2
#计算距离
seqDistances = sqdifMax.sum(axis=1)
distances = seqDistances**0.5
print ("distances:",distances)
#返回distance中元素从小到大排序后的索引
sortDistance = distances.argsort()
print ("sortDistance:",sortDistance)
classCount = {}
for i in range(k):
#取出前k个元素的类别
voteLabel = labels[sortDistance[i]]
print ("第%d个voteLabel=%s",i,voteLabel)
classCount[voteLabel] = classCount.get(voteLabel,0)+1
#dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
#计算类别次数
#key=operator.itemgetter(1)根据字典的值进行排序
#key=operator.itemgetter(0)根据字典的键进行排序
#reverse降序排序字典
sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
#结果sortedClassCount = [('动作片', 2), ('爱情片', 1)]
print ("sortedClassCount:",sortedClassCount)
return sortedClassCount[0][0]
if __name__ == '__main__':
group,labels = createDataset()
test = [20,101]
test_class = classify(test,group,labels,3)
print (test_class)
完整代码查看码云
5.2 主成分分析（PCA）
参阅：http://blog.csdn.net/hellotruth/article/details/30750823
简单说：以二维特征为例，如下图。特征之间可能不存在完全的线性关系，可能只是强的正相关。如果把x-y坐标分解成u1-u2坐标，而u1轴线上反应了特征的主要变化（intrinsic），而u2的特征变化较小，其实可以完全理解为一些噪声的扰动而不去考虑它。PCA的任务就是找到u1和u2。
PCA其实是最简单的降维方法之一了，很明显的劣势是它仅去除数据之间的线性相关性。对线性的改善往往通过kernel技术拓展到非线性的应用上。另外，PCA的这种降维不一定有助于分类，用于分类的降维方法之一就是LDA。从另一方面说，PCA是一种线性投影，保留了数据与数据之间的欧式距离，即原来欧式距离大的两点在降维后的空间中距离也应大（这样才好保证方差大）。而事实上数据有可能呈现某种流型结构，用PCA降维后数据将不能保持原有的流型结构。
原理：PCA采用一组新的基来表示样本点，其中每一个基向量都是原来基向量的线性组合，通过使用尽可能少的新基向量来表出样本，从而达到降维的目的。
假设使用d’个新基向量来表示原来样本，实质上是将样本投影到一个由d’个基向量确定的一个超平面上（即舍弃了一些维度），要用一个超平面对空间中所有高维样本进行恰当的表达，最理想的情形是：若这些样本点都能在超平面上表出且这些表出在超平面上都能够很好地分散开来。但是一般使用较原空间低一些维度的超平面来做到这两点十分不容易，因此我们退一步海阔天空，要求这个超平面应具有如下两个性质：
最近重构性：样本点到超平面的距离足够近，即尽可能在超平面附近；
最大可分性：样本点在超平面上的投影尽可能地分散开来，即投影后的坐标具有区分性。
这里十分神奇的是：最近重构性与最大可分性虽然从不同的出发点来定义优化问题中的目标函数，但最终这两种特性得到了完全相同的优化问题：
接着使用拉格朗日乘子法求解上面的优化问题，得到：
因此只需对协方差矩阵进行特征值分解即可求解出W，PCA算法的整个流程如下图所示：
总结
PCA优缺点：
优点：1）最小误差。2）提取了主要信息
缺点：1）计算协方差矩阵，计算量大
LDA方法简介
（1）LDA核心思想：往线性判别超平面的法向量上投影，使得区分度最大（高内聚，低耦合）。
（2）LDA优缺点：
优点：1）简单易于理解
缺点：2）计算较为复杂
在很多问题上，可能需要非线性映射才能找到恰当的低维嵌入。那么非线性降维常用的一种方法，就是基于核技巧对线性降维方法进行“核化”（使用一个超平面去近似表出）。例如核主成分分析（KPCA）
下面主要介绍核化主成分分析（KPCA）的思想。
若核函数的形式已知，即我们知道如何将低维的坐标变换为高维坐标，这时我们只需先将数据映射到高维特征空间，再在高维空间中运用PCA即可。但是一般情况下，我们并不知道核函数具体的映射规则，例如：Sigmoid、高斯核等，我们只知道如何计算高维空间中的样本内积，这时就引出了KPCA的一个重要创新之处：即空间中的任一向量，都可以由该空间中的所有样本线性表示。证明过程也十分简单：
这样我们便可以将高维特征空间中的投影向量wi使用所有高维样本点线性表出，接着代入PCA的求解问题，得到：
化简到最后一步，发现结果十分的美妙，只需对核矩阵K进行特征分解，便可以得出投影向量wi对应的系数向量α，因此选取特征值前d’大对应的特征向量便是d’个系数向量。这时对于需要降维的样本点，只需按照以下步骤便可以求出其降维后的坐标。可以看出：KPCA在计算降维后的坐标表示时，需要与所有样本点计算核函数值并求和，因此该算法的计算开销十分大。
流行学习是一类借鉴了拓扑流形概念的降维方法。常用的流行学习方法有等度量映射和局部线性嵌入。
1 等度量映射（Isomap）
等度量映射的基本出发点是：高维空间中的直线距离具有误导性，因为有时高维空间中的直线距离在低维空间中是不可达的。因此利用流形在局部上与欧式空间同胚的性质，可以使用近邻距离来逼近测地线距离，即对于一个样本点，它与近邻内的样本点之间是可达的，且距离使用欧式距离计算，这样整个样本空间就形成了一张近邻图，高维空间中两个样本之间的距离就转为最短路径问题。可采用著名的Dijkstra算法或Floyd算法计算最短距离，得到高维空间中任意两点之间的距离后便可以使用MDS算法来其计算低维空间中的坐标。
从MDS算法的描述中我们可以知道：MDS先求出了低维空间的内积矩阵B，接着使用特征值分解计算出了样本在低维空间中的坐标，但是并没有给出通用的投影向量w，因此对于需要降维的新样本无从下手，书中给出的权宜之计是利用已知高/低维坐标的样本作为训练集学习出一个“投影器”，便可以用高维坐标预测出低维坐标。Isomap算法流程如下图：
对于近邻图的构建，常用的有两种方法：一种是指定近邻点个数，像kNN一样选取k个最近的邻居；另一种是指定邻域半径，距离小于该阈值的被认为是它的近邻点。但两种方法均会出现下面的问题：
若邻域范围指定过大，则会造成“短路问题”，即本身距离很远却成了近邻，将距离近的那些样本扼杀在摇篮。
若邻域范围指定过小，则会造成“断路问题”，即有些样本点无法可达了，整个世界村被划分为互不可达的小部落。
2 局部线性嵌入(LLE)
不同于Isomap算法去保持邻域距离，LLE算法试图去保持邻域内的线性关系，假定样本xi的坐标可以通过它的邻域样本线性表出：
LLE算法分为两步走，首先第一步根据近邻关系计算出所有样本的邻域重构系数w：
接着根据邻域重构系数不变，去求解低维坐标：
这样利用矩阵M，优化问题可以重写为：
M特征值分解后最小的d’个特征值对应的特征向量组成Z，LLE算法的具体流程如下图所示：
首先要学习出距离度量必须先定义一个合适的距离度量形式。对两个样本xi与xj，它们之间的平方欧式距离为：
若各个属性重要程度不一样即都有一个权重，则得到加权的平方欧式距离：
此时各个属性之间都是相互独立无关的，但现实中往往会存在属性之间有关联的情形，例如：身高和体重，一般人越高，体重也会重一些，他们之间存在较大的相关性。这样计算距离就不能分属性单独计算，于是就引入经典的马氏距离(Mahalanobis distance):
标准的马氏距离中M是协方差矩阵的逆，马氏距离是一种考虑属性之间相关性且尺度无关（即无须去量纲）的距离度量。
矩阵M也称为“度量矩阵”，为保证距离度量的非负性与对称性，M必须为(半)正定对称矩阵，这样就为度量学习定义好了距离度量的形式，换句话说：度量学习便是对度量矩阵进行学习。现在来回想一下前面我们接触的机器学习不难发现：机器学习算法几乎都是在优化目标函数，从而求解目标函数中的参数。同样对于度量学习，也需要设置一个优化目标，书中简要介绍了错误率和相似性两种优化目标，此处限于篇幅不进行展开。
总结：
数据降维的目的:数据降维，直观地好处是维度降低了，便于计算和可视化，其更深层次的意义在于有效信息的提取综合及无用信息的摈弃。
数据降维的好处：降维可以方便数据可视化+数据分析+数据压缩+数据提取等。
-········
【问题】knn似乎和降维没有关系？
降维是将原高维空间嵌入到一个合适的低维子空间中，接着在低维空间中进行学习任务；度量学习则是试图去学习出一个距离度量来等效降维的效果，两者都是为了解决维数灾难带来的诸多问题。
那kNN呢，为什么一开头就说了kNN算法，但是好像和后面没有半毛钱关系？
正是因为在降维算法中，低维子空间的维数d’通常都由人为指定，因此我们需要使用一些低开销的学习器来选取合适的d’，kNN这家伙懒到家了根本无心学习，在训练阶段开销为零，测试阶段也只是遍历计算了距离，因此拿kNN来进行交叉验证就十分有优势了~同时降维后样本密度增大同时距离计算变易，更为kNN来展示它独特的十八般手艺提供了用武之地。
参考文献：
https://www.cnblogs.com/nolonely/p/6435159.html
