一.KNN优缺点及KD-Tree
1) KNN优缺点：
KNN的主要优点有：
理论成熟，思想简单，既可以用来做分类也可以用来做回归
天然解决多分类问题，也可用于回归问题
和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合
KNN的主要缺点有：
计算量大，效率低。即使优化算法，效率也不高。
高度数据相关，样本不平衡的时候，对稀有类别的预测准确率低
相比决策树模型，KNN模型可解释性不强
维度灾难：随着维度的增加，“看似相近”的两个点之间的距离越来越大，而knn非常依赖距离
2）KD-Tree:
KNN优化算法之一。
原理：kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，且kd树是一种二叉树，表示对k维空间的一个划分。
k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。
KD树的构建：
循环依序取数据点的各维度来作为切分维度，
取数据点在该维度的中值作为切分超平面，
将中值左侧的数据点挂在其左子树，将中值右侧的数据点挂在其右子树，
递归处理其子树，直至所有数据点挂载完毕。
对于构建过程，有两个优化点：选择切分维度：根据数据点在各维度上的分布情况，方差越大，分布越分散，从方差大的维度开始切分，有较好的切分效果和平衡性。
确定中值点：预先对原始数据点在所有维度进行一次排序，存储下来，然后在后续的中值选择中，无须每次都对其子集进行排序，提升了性能。也可以从原始数据点中随机选择固定数目的点，然后对其进行排序，每次从这些样本点中取中值，来作为分割超平面。该方式在实践中被证明可以取得很好性能及很好的平衡性。
二. 特征工程之数据预处理
A. 数值型特征无量纲化
1.数据标准化：
标准化的前提是特征值服从正态分布，标准化后，其转换成标准正态分布。
数据标准化优缺点：
优点：
Z-Score最大的优点就是简单，容易计算，Z-Score能够应用于数值型的数据，并且不受数据量级的影响，因为它本身的作用就是消除量级给分析带来的不便。
缺点：
估算Z-Score需要总体的平均值与方差，但是这一值在真实的分析与挖掘中很难得到，大多数情况下是用样本的均值与标准差替代；
Z-Score对于数据的分布有一定的要求，正态分布是最有利于Z-Score计算的；
Z-Score消除了数据具有的实际意义，A的Z-Score与B的Z-Score与他们各自的分数不再有关系，因此Z-Score的结果只能用于比较数据间的结果，数据的真实意义还需要还原原值；
在存在异常值时无法保证平衡的特征尺度。
2.归一化：
1）MinMax归一化：区间缩放法，利用于边界值信息。将属性缩放到[0,1]
缺点：
这种方法有一个缺陷就是当有新数据加入时，可能导致max和min的变化，需要重新定义；
MinMaxScaler对异常值的存在非常敏感。
2）MaxAbs 归一化：
单独地缩放和转换每个特征，使得训练集中的每个特征的最大绝对值将为1.0，将属性缩放到[-1,1]。它不会移动/居中数据，因此不会破坏任何稀疏性。
缺点：
这种方法有一个缺陷就是当有新数据加入时，可能导致max和min的变化，需要重新定义；
MaxAbsScaler与先前的缩放器不同，绝对值映射在[0,1]范围内。在仅有正数据时，该缩放器的行为MinMaxScaler与此类似，因此也存在大的异常值。
3）正态分布化：
定义：正则化的过程是将每个样本缩放到单位范数(每个样本的范数为1)，如果要使用如二次型(点积)或者其它核方法计算两个样本之间的相似性这个方法会很有用。
该方法是文本分类和聚类分析中经常使用的向量空间模型(Vector Space Model)的基础。
Normalization主要思想是对每个样本计算其p-范数，然后对该样本中每个元素除以该范数，这样处理的结果是使得每个处理后样本的p-范数(l1-norm,l2-norm)等于1。
4.标准化与归一化对比
1）标准化与归一化的异同
相同点：
它们的相同点在于都能取消由于量纲不同引起的误差；都是一种线性变换，都是对向量X按照比例压缩再进行平移。
不同点：
目的不同，归一化是为了消除纲量压缩到[0,1]区间；
标准化只是调整特征整体的分布；
归一化与最大，最小值有关；
标准化与均值，标准差有关；
归一化输出在[0,1]之间；
标准化无限制。
2）什么时候用归一化？什么时候用标准化？
如果对输出结果范围有要求，用归一化；
如果数据较为稳定，不存在极端的最大最小值，用归一化；
如果数据存在异常值和较多噪音，用标准化，可以间接通过中心化避免异常值和极端值的影响。
3）归一化与标准化的应用场景
在分类、聚类算法中，需要使用距离来度量相似性的时候（如SVM、KNN）、或者使用PCA技术进行降维的时候，标准化(Z-score standardization)表现更好；
在不涉及距离度量、协方差计算、数据不符合正太分布的时候，可以使用第一种方法或其他归一化方法。
比如图像处理中，将RGB图像转换为灰度图像后将其值限定在[0 255]的范围；
基于树的方法不需要进行特征的归一化。
例如随机森林，bagging与boosting等方法。
如果是基于参数的模型或者基于距离的模型，因为需要对参数或者距离进行计算，都需要进行归一化。
一般来说，建议优先使用标准化。对于输出有要求时再尝试别的方法，如归一化或者更加复杂的方法。很多方法都可以将输出范围调整到[0, 1]，如果我们对于数据的分布有假设的话，更加有效的方法是使用相对应的概率密度函数来转换。
B. 数值型特征特征分箱（数据离散化）
1.无监督分箱法
1）自定义分箱
2）等距分箱 - pd.cut
3）等频分箱 - pd.qcut
4）聚类分箱：基于k均值聚类的分箱：k均值聚类法将观测值聚为k类，但在聚类过程中需要保证分箱的有序性：第一个分箱中所有观测值都要小于第二个分箱中的观测值，第二个分箱中所有观测值都要小于第三个分箱中的观测值，等等。
5）二值化：二值化可以将数值型（numerical）的feature进行阀值化得到boolean型数据。
2.无监督分箱法
1）卡方分箱法：自底向上的(即基于合并的)数据离散化方法。它依赖于卡方检验：具有最小卡方值的相邻区间合并在一起,直到满足确定的停止准则。
基本思想：
对于精确的离散化，相对类频率在一个区间内应当完全一致。因此,如果两个相邻的区间具有非常类似的类分布，则这两个区间可以合并；否则，它们应当保持分开。而低卡方值表明它们具有相似的类分布。
2）最小熵法分箱：需要使总熵值达到最小，也就是使分箱能够最大限度地区分因变量的各类别。
熵是信息论中数据无序程度的度量标准，提出信息熵的基本目的是找出某种符号系统的信息量和冗余度之间的关系，以便能用最小的成本和消耗来实现最高效率的数据存储、管理和传递。
数据集的熵越低，说明数据之间的差异越小，最小熵划分就是为了使每箱中的数据具有最好的相似性。给定箱的个数，如果考虑所有可能的分箱情况，最小熵方法得到的箱应该是具有最小熵的分箱。
