SVM
线性SVM
- loss: hinge loss 凸函数 $l(f(x^n), y^n) = max(0, 1-y^nf(x^n))$, 更为常见的写法是用 $y^nf(x) \geq 1-e^n$, 这里的 $e^n$ 就是松弛变量
- 边界最宽的 Large-Margin
- 离边界最近的点就是支撑向量
- 二次规划(凸优化)
遗传算法
- 种群->幸运轮->存活者->配对重组变异->种群->…
- 遗传算子:配对 重组 变异 三个算子
- 算法实现
- 初始种群产生
- 个体存活规则:适应函数计算个体的适用度,然后根据概率选出存活的个体
- 配对(选择)算子
- 个体任意配对,未考虑适应度高的个体更具有吸引力
- 按适应度排序,然后相邻的两两配对
- 概率选择,保留了高质量个体与低质量个体配对的可能,增加了个体的多样性,但是最终优秀个体可能会消失,解决办法是一部分最优秀的个体直接复制到下一代,不经过重组变异
- 重组(交叉)
- 单点交叉
- 两点交叉
- 均匀交叉
- 实际80%重组,20%直接复制到下一代
- 变异:随机选择一位求反,只有配对和交叉,就不存在新个体,会陷入局部最优解的
- KNN选择
- 生成种群:对d维特征进行二进制编码,包含该特征即设为1
- 适应函数: $f=1/(C_1E_R + C_2N_A)$ 其中$E_R$是分类错误的样本数. $N_A$ 是保留属性的数目. $C_1C_2$ 是可调的参数
- 选择算子:个体存活的概率为: $P = f(x_i) / \sum f(x_i) $
- 重组算子:两点交叉
- 变异:随机一位取反
- 确定最优属性:每次保留$y_i$个个体,n次运行后暴露的个体数为$\sum y_i$,统计每个属性在其中出现的频数,降序排列,即可得到最优属性
聚类
- 定义:将大量无标注的数据集,按数据的内在相似性将数据集划分成多个类别,使得类别内相似性较大,类别间相似性较小
- 对m个样本,构造k个簇,每个簇至少包含一个对象,每个对象仅属于一个簇
- 最短距离法:
- 定义距离计算方法
- 计算初始样本两两之间的距离,构造距离矩阵
- 根据距离矩阵,合并最小值对应得到两个样本,形成新样本
- 更新距离矩阵,重复上面的步骤
- 重心聚类法:计算每个簇的重心,重心可取样本的平均值,得到一个距离矩阵,后续同上
- 动态聚类法:先划分成若干个簇,计算所有样本到簇重心的距离,取最小距离作为该样本所属的簇,再更新簇的重心,直到所有的样本所属簇不再变化
- k-means算法
- 对m个样本选取k个点作为中心,分别计算每个样本到这k个点的距离,并把该样本加入到最近距离的簇,所有样本加入到k个簇后,更新k个中心点,再重复,直至不再变化
- k-means++算法
- 在k-means算法的基础之上,在初始生成k个初始点之前,对所有样本进行一次计算,使得初始中心点的距离尽可能远,这样可以减少迭代次数
- 先随机选择一个点作为第一个中心点,计算所有样本到该点的距离,选择距离最远的作为第二个样本点,依次选出k个
- 如何选择k值
- k值越大,损失越小,k代表了模型的复杂度,模型越复杂,对训练集拟合的越好,但是引起过拟合
- 轮廓分析:$$s = \frac{b-a}{max(a,b)}$$其中a表示一个类别内所有数据到聚类中心的距离平方和,b表示数据到其他最近聚类中心的距离平方和,s=1时表示达到了最佳状态,s=-1表示最差状态,s越大越好
- k-means总结
- 优点:当簇接近于高斯分布时效果较好;简单快捷;
- 缺点:必须先给出k值,对初始值敏感;不适合大小差别很大的簇;对噪声和孤立点敏感;
- LVQ(学习向量量化)
- 与k-means不同的是,假设样本带有标签
- 关键点在于中心点的更新,如果$x_i$与中心点的类别相同,则中心点向$x_i$靠拢,反之远离
- 密度聚类
- 初始化核心对象集合
- 计算每个样本的$\epsilon$-领域,将是核心对象的样本加入到集合中
- 以任何一个核心对象出发,找出由其密度可达的簇$C_i$
- 直到集合内所有核心对象都被访问过
集成学习
- Bagging
- 从D中创建T个训练子集 $D_1,D_2,D_3,…$
- 为每一个$D_i$ 引入一个基学习器 $h_i$
- 对回归问题使用简单平均;对分类问题使用简单投票
- 时间复杂度:$T(O(m)+O(n)$,$O(m)$是采样和投票的时间复杂度,$O(n)$是基学习器的计算复杂度
- 优点:泛化能力强;缺点:训练误差大
- 随机森林
- 以决策树为基学习器
- 分类问题,最终结果等于决策树输出次数最多的类别
- 回归问题,最终结果等于决策树输出结果的平均值
- 一颗决策树容易出错,但是多棵树同时犯错的概率就会很低
- 首先为每棵树创建训练子集;随机挑选部分属性构成候选属性子集,在这个子集中产生最优的属性划分;随机构成一个阈值集合
- Schapire提升
- bagging方法的严重缺陷在于各基学习器之间的关联性很弱
- 问题:用一个三元组和其他两个基分类器组成新的三元组后，集成分类器的性能就不会有多大的提升。
- 解决方法是三元组均由三个基分类器组成
- Adaboosting
- 生成训练子集:生成第一个训练子集时,每个样本被选中的几率相同,并由此训练得到第一个分类器,然后减小被错误分类样本的概率,增大错分样本选中的概率
- 集成时,加大分类误差小的分类器的权重,减小分类误差大的分类器的权重
- 加法模型: $H(x) = \sum{a_ih_i(x)} $
- 决策规则: $H(x) = sign( \sum{a_ih_i(x)})$
贝叶斯
- 先验概率可以认为就是频率,后验概率就是条件概率,后验概率比先验概率更可信
- 贝叶斯公式:$$P(C_i|x) = \frac{P(x|C_i)*P(C_i)}{P(x)}$$
- 贝叶斯假设,即属性之间是相互独立的:$$P(x|C_j) = \prod_{i=1}^dP(x_i|C_j)$$
- 由此得到贝叶斯分类器:$$h(x) = argmax(P(C_j) * \prod_{i=1}^dP(x_i|C_j )$$
- 属性之间不是相互独立的怎么办
- 忽略其影响
- 不能忽略时,可采用的方法有:去掉该属性,用其他属性替换之,或者采用别的分类方法
- 朴素贝叶斯算法
- 计算先验概率和条件概率,即各个标签的概率以及各个标签下各个特征的条件概率
- 对于给定的实例,计算$P(C_j) * \prod_{i=1}^dP(x_i|C_j )$
- 选取其中的最大值,作为该实例的类别
- 平滑处理(拉普拉斯平滑)
- 先验概率,分母加上类别数,分子加1
- 条件概率,分母加上该属性的可能取值数,分子加一
KNN
- 三要素:k值选择,距离度量,分类决策规则
- 使用的距离:欧氏距离
- k值得选择:k值减小意味着模型更复杂,容易过拟合;k值增加意味着模型变简单;实际k一般选一个较小的奇数,或者采用交叉验证的方式找到最好的k
- 分类决策规则:多数投票表决
- kd树:
- 加权最近邻:距离近的权重大,距离远的权重小
- 具体的:将k个近邻点的距离从小到大排序:$d_1, d_2, d_3,…d_k$ 则$$\begin{cases}\frac{d_k-d_i}{d_k-d_1},d_k ≠ d_1\1, d_k=d_1\end{cases}$$
- 标准化属性尺度:$x = (x - min)/(max-min)$
线性回归
- 最小二乘法:基于方差最小化进行模型求解的方法就是最小二乘法
- 梯度下降
逻辑回归
- sigmoid函数: $z = wx, f = \frac{1}{1+e^{-z}}, f’ = f*(1-f)$
决策树
- 以信息熵为度量,构造一棵熵值下降最快的树,到叶子节点处的熵值为0
- 信息量 $I(x) = -log_2p(x)$, 事件发生的概率越小,信息量越大,对于确定性事件(p=1),信息量为0
- 熵是平均信息量:$H(x) = -\sum p(x)log_2p(x)$,则对于两点分布的来说:$H(x) = -p(x)log_2p(x)-(1-p(x))log(1-p(x))$
- 条件熵:$H(Y|X) = \sum_{i=1}^np_iH(Y|X=x_i)$
- 熵和条件熵的概率值是由相对频率估算得到的话,叫做经验熵和条件经验熵
- 特征A对训练数据集D的信息增益:g(D,A) = H(D) - H(D|A)
- 经验熵$H(D)$表示对数据集D分类的不确定性,经验条件熵$H(D|A)$表示在特征A的给定条件下对数据集D分类的不确定性,他们的差值即信息增益表示特征A对数据集D的分类不确定性的减少程度,信息增益大的特征具有更强的分类能力
- 信息增益划分的缺点是太偏好取值数目较多的属性,C4.5采用信息增益率进行划分
- 信息增益率:$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$, 其中$H_A(D)$为特征A的经验熵
- 老师课件中提到:C4.5不是直接选取信息增益率最大的属性进行划分,而是从信息增益高于平均值属性中选取信息增益率最大的(统计学习方法一书中并没有这么说,就是C4.5根据信息增益率大小划分)
- 剪枝:为了降低过拟合,用叶子节点代替子树,会引起部分训练样例的错误分类,但是我们关心的是模型的泛化能力,而不是在训练集上的100%正确率
- 误差估计:错误率为$E=\frac{e+1}{n+m}$其中e是错误分类的样本数,n是达到测试节点t的样本总数,为避免n过小进行了修正
- 用测试样例比较剪枝前后的准确率,准确率提高则剪枝,反之不剪
- 预剪枝:在决策树生成的过程中,对每个节点划分前先进行估算,若划分后没有泛化能力的提升,则将该节点标记为叶子节点
- 后剪枝:先从训练集生成一棵完整的决策树,然后自底向上地对非叶子节点进行考察,若该节点换成叶子节点可以提高泛化能力,则剪枝
- CART树
- 对回归树用平方误差最小化,对分类树用基尼指数最小化
- 分类树划分属性时采用的是基尼指数:$Gini(D) = \sum_{k=1}^Kp_k(1-p_k) = 1-\sum_{k=1}^Kp_k^2$,对于二分类问题就是:$Gini(p)=2p(1-p)$
- 若样本D根据特征A的取值被划分为D1和D2两部分,则在A条件下,D的基尼指数为:$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)$
- 选择基尼指数最小的属性作为最优划分属性
人工神经网络
- 所谓的M-P模型就是按照生物神经元的结构和工作原理构造出来的一个抽象和简化了的模型，它实际上就是对单个神经元的一种建模
- BP算法的目标:最小化网络误差
- 解决过拟合:
- 采用早停策略,当训练误差降低而测试误差升高时,停止训练
- 正则化
- 跳出局部最小值:
- 随机梯度下降
- 以多种不同的参数初始化,训练后误差最小的作为最终结果
- 模拟退火,在每一步都以一定概率接受比当前解更差的结果