KNN

分类算法
思想：

  1. 计算待预测点X到所有样本点xi的距离
  2. 认为距离最近的k个样本点中占比最大的类别为预测类别

优化：

  1. kd树（类似二叉搜索树）
    • 构建
      1. 设当前特征值x，y，z，将其按照方差由大到小排序（设z>y>x）
      2. 选择方差最大的特征z为当前kd树根节点，对数据项按照z的大小进行排序并按中位数进行划分为左右子kd树
      3. 递归进行划分，kd树的当前层特征选择不与上一层相同。
      4. 重复直到不可再进行划分
    • 查找
      1. 得到一条查找路径，途径节点入栈
      2. 回溯节点：令r=预测点X到叶节点的距离，以预测点X为圆心，r为半径作圆，回溯途中根据圆是否涉及其他区域点来决定是否跳到其他子树上查找
      3. 返回叶节点
  2. ball tree算法

Linear Regression

回归算法
思想：

  • 正规方程法
    1. 对于方程y=w^T x，w为权重矩阵
    2. 设置损失函数
    3. 求令损失函数最小的w，即对损失函数求导等于零的w，推导如下
      • 其中X右乘X^T使之成为方阵，可逆性由特征工程保证(不可逆说明有多余特征)
    • 特征值多的样本计算量过大
  • 梯度下降法
    • 全梯度下降法(FG)：使用所有样本数据计算梯度下降的距离
    • 随机梯度下降法(SG)：每次只代入一个样本进行计算并更新下降距离，再取下一个样本重复该过程，直到损失函数停止下降或低于阈值
    • 小批量梯度下降法(mini-batch)：每次取一个小样本集
    • 随机平均梯度下降法(SAG)：为每个样本维护一个旧的梯度，综合当前梯度和旧梯度下降

优化：
正则化对抗过拟合原理参考：浅议过拟合现象(overfitting)以及正则化技术原理
岭回归、lasso回归都是在损失函数中添加正则项限制训练参数的大小（过大的参数抗干扰性不强） ，其中岭回归倾向于让参数接近0（实际只是限制，具体依旧由样本数据决定，由α调整限制力度）,而lasso倾向于将参数变为0.

Logistic Regression

二分类算法
思想：

  1. 逻辑回归的输入是线性回归的输出
  2. 对于输入用sigmoid函数或其他激活函数得到0~1间的值
  3. 损失函数推导

补充：ROC、AUC

类别不平衡问题;

决策树

知识点：

  1. 信息熵的计算
  2. 信息增益(ID3)=整体熵-按照特征a划分的熵的加权和
  3. 信息增益率(C4.5)
    • 信息增益对属性中可取数目多的某一特征具有偏好性
    • C4.5采用后剪枝
    • C4.5对连续特征离散化，对缺失值进行处理
  4. 基尼系数
    • 可作回归
  5. 剪枝，用验证集计算决策树每个节点的划分前准确率和划分后准确率，再决定是否划分
    1. 后剪枝通常保留更多分支，欠拟合风险小，泛化性能好。
    2. 后剪枝开销大。

集成学习

原理：生成多个模型，各自独立学习和做出预测，这些预测最后加权平均组合成新的预测，其优于任何一个单分类做出的预测。
解决过拟合和欠拟合的方法
随机森林:一个包含多个决策树的分类器

  • 为何随机抽样：如果不进行随机抽样，则每颗决策树都是相同的，结果也是相同的，失去了Bagging的意义
  • 为何放回抽样：若采用不放回抽样，那么每棵树的训练样本都是不同的，每棵树都是“有偏的"，每棵树的相似性太小，投票结果比较差。
    包外估计：数据集足够大的情况下，总有36.8%的样本不会出现在训练样本中，称为包外数据。若基学习器为决策树，包外数据可辅助剪枝；若基学习器为神经网络，包外数据可辅助停止训练以防止过拟合。

聚类算法 - KMeans

原理：

  1. 随机生成K个点作为初始的聚类中心
  2. 对于每个点计算其到这K个中心的距离，并标记每个点最近的类别K_i
  3. 对于标记出的K个集群，重新计算其新的中心点
  4. 如果所有中心点不变则结束，否则回到第2步

KMeans

聚类评估：SSE、“肘”方法、轮廓系数法

优缺点：

  • 原理简单，实现容易；聚类效果中上（依赖k的选择）；
  • 对离群点敏感；难发现大小相差较大的簇；无法增量计算；

优化：

  1. 对初始中心点的选择进行改进
  2. 降维：去除冗余或无关特征