数据缺失有多种原因，而大部分统计方法都假定处理的是完整矩阵、向量和数据框。
缺失数据的分类：
完全随机缺失 ：若某变量的缺失数据与其他任何观测或未观测变量都不相关，则数据为完全随机缺失（MCAR）。
随机缺失： 若某变量上的缺失数据与其他观测变量相关，与它自己的未观测值不相关，则数据为随机缺失（MAR）。
非随机缺失： 若缺失数据不属于MCAR或MAR，则数据为非随机缺失（NMAR） 。
处理缺失数据的方法有很多，但哪种最适合你，需要在实践中检验。
下面一副图形展示处理缺失数据的方法：
处理数据缺失的一般步骤：
1、识别缺失数据
2、检测导致数据缺失的原因
3、删除包含缺失值的实例或用合理的数值代替（插补）缺失值。
1、识别缺失数据：
R语言中， NA 代表缺失值， NaN 代表不可能值， Inf 和 -Inf 代表正无穷和负无穷。
在这里，推荐使用 is.na ， is.nan ， is.finite ， is.infinite 4个函数去处理。
x<-c(2,NA,0/0,5/0)
#判断缺失值
is.na(x)
#判断不可能值
is.nan(x)
#判断无穷值
is.infinite(x)
#判断正常值
is.finite(x)
推荐一个函数： complete.case() 可用来识别矩阵或数据框中没有缺失值的行！
展示出数据中缺失的行 （数据集sleep来自包VIM）
sleep[!complete.cases(sleep),]
判断数据集中有多少缺失
针对复杂的数据集，怎么更好的探索数据缺失情况呢？
mice包 中的 md.pattern() 函数可以生成一个以矩阵或数据框形式展示缺失值模式的表格。
备注：0表示变量的列中没有缺失，1则表示有缺失值。
第一行给出了没有缺失值的数目（共多少行）。
第一列表示各缺失值的模式。
最后一行给出了每个变量的缺失值数目。
最后一列给出了变量的数目（这些变量存在缺失值）。
在这个数据集中，总共有38个数据缺失。
图形化展示缺失数据：
aggr(sleep,prop=F,numbers=T)
matrixplot(sleep)
浅色表示值小，深色表示值大，默认缺失值为红色。
marginmatrix(sleep)
上述变量太多，我们可以选出部分变量展示：
x <- sleep[, 1:5]
x[,c(1,2,4)] <- log10(x[,c(1,2,4)])
marginmatrix(x)
为了更清晰，可以进行成对展示：
marginplot(sleep[c("Gest","Dream")])
在这里(左下角)可以看到，Dream和Gest分别缺失12和4个数据。
左边的红色箱线图展示的是在Gest值缺失的情况下Dream的分布，而蓝色箱线图展示的Gest值不缺失的情况下Dream的分布。同样的，Gest箱线图在底部。
2、缺失值数据的处理
行删除法： 数据集中含有缺失值的行都会被删除，一般假定缺失数据是完全随机产生的，并且缺失值只是很少一部分，对结果不会造成大的影响。
即：要有足够的样本量，并且删除缺失值后不会有大的偏差！
行删除的函数有 na.omit() 和 complete.case()
newdata<-na.omit(sleep)
sum(is.na(newdata))
newdata<-sleep[complete.cases(sleep),]
sum(is.na(newdata))
均值/中位数等填充： 这种方法简单粗暴，如果填充值对结果影响不怎么大，这种方法倒是可以接受，并且有可能会产生令人满意的结果。
方法1：
newdata<-sleep
mean(newdata$Dream,na.rm = T)
newdata[is.na(newdata$Dream),"Dream"]<-1.972
方法2：
Hmisc包更加简单，可以插补均值、中位数等，你也可以插补指定值。
library(Hmisc)
impute(newdata$Dream,mean)
impute(newdata$Dream,median)
impute(newdata$Dream,2)
mice包插补缺失数据： 链式方程多元插值，首先利用mice函数建模再用complete函数生成完整数据。
下图展示mice包的操作过程：
mice()：从一个含缺失值的数据框开始，返回一个包含多个完整数据集对象（默认可以模拟参数5个完整的数据集）
with()：可依次对每个完整数据集应用统计建模
pool()：将with()生成的单独结果整合到一起
library(mice)
newdata<-sleep
data<-mice(newdata,m = 5,method='pmm',maxit=100,seed=1)
在这里，m是默认值5，指插补数据集的数量
插补方法是pmm：预测均值匹配，可以用methods(mice)查看其他方法
maxit指迭代次数，seed指设定种子数（和set.seed同义）
概述插补后的数据：
summary(data)
在这上面可以看到数据集中变量的观测值缺失情况，每个变量的插补方法， VisitSequence 从左至右展示了插补的变量， 预测变量矩阵 （PredictorMatrix）展示了进行插补过程的含有缺失数据的变量，它们利用了数据集中其他变量的信息。（在矩阵中，行代表插补变量，列代表为插补提供信息的变量，1
和0分别表示使用和未使用。）
查看整体插补的数据：
data$imp
查看具体变量的插补数据：
data$imp$Dream
最后，最重要的是生成一个完整的数据集
completedata<-complete(data)
判断还有没有缺失值，如果没有，结果返回FLASE
anyNA(completedata)
针对以上插补结果，我们可以查看原始数据和插补后的数据的分布情况
library(lattice)
xyplot(data,Dream~NonD+Sleep+Span+Gest,pch=21)
图上，插补值是洋红点呈现出的形状，观测值是蓝色点。
densityplot(data)
图上，洋红线是每个插补数据集的数据密度曲线，蓝色是观测值数据的密度曲线。
stripplot(data, pch = 21)
上图中，0代表原始数据，1-5代表5次插补的数据，洋红色的点代表插补值。
下面我们分析对数据拟合一个线性模型：
完整数据：
library(mice)
newdata<-sleep
data<-mice(newdata,m = 5,method='pmm',maxit=100,seed=1)
model<-with(data,lm(Dream~Span+Gest))
pooled<-pool(model)
summary(pooled)
fim指的是各个变量缺失信息的比例，lambda指的是每个变量对缺失数据的贡献大小
缺失数据（在运行中，自动会行删除）：
lm.fit <- lm(Dream~Span+Gest, data = sleep，na.action=na.omit)
summary(lm.fit)
完整数据集和缺失数据集进行线性回归后，参数估计和P值基本一直。 缺失值是完全随机产生的 。如果缺失比重比较大的话，就不适合使用行删除法，建议使用多重插补法。
kNN插值法： knnImputation函数使用k近邻方法来填充缺失值。对于需要插值的记录，基于欧氏距离计算k个和它最近的观测。接着将这k个近邻的数据利用距离逆加权算出填充值，最后用该值替代缺失值。
library(DMwR)
newdata<-sleep
knnOutput <- knnImputation(newdata)
anyNA(knnOutput)
head(knnOutput)
给定测试实例，基于某种距离度量找出训练集中与其最靠近的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一样，如果结点包含的观测点到达了预先设定的最小值，这个顶点就可以不再分割了。
