机器学习期中复习
0.概念
性质
-
分类：定性（离散）
- 二分类：仅正例与负例两种
- 多分类：多种结果
-
回归：定量（连续）
是否存在标记数据
- 有监督学习 - 有标记数据的训练
- 无监督学习 - 无标记数据的训练
- 半监督学习 - 使用大量的未标记数据，以及同时使用标记数据，来进行模式识别工作
学习过程：学习阶段 => 训练阶段 => 测试
1.聚类
概念
- 将数据集中的样本划分为若干个通常是不相交的子集（求划分），每个子集称为一个“簇（cluster）”
K-Means 算法
-
步骤
- step1.在样本数据中随机选取k个点
- step2.计算各样本数据向量与k个随机点的距离，选择与其距离最近的那个随机点，归为一类
- step3.已经分好的k个类各自计算类内数据的的平均值，得到新的k个点的参数
- 循环step2、step3，直到k个点的位置不再发生变化
-
距离计算
- 欧式距离
- d ( x i , x j ) = ∑ u = 1 n ( x i u − x j u ) 2 {d(x_i,x_j) = \sqrt{\sum_{u=1}^{n}{(x_{{iu}-x_{ju}})^2}}} d(xi,xj)=∑u=1n(xiu−xju)2
- 闵可夫斯基距离
- d ( x i , x j ) = ( ∑ u = 1 n ( x i u − x j u ) p ) 1 p {d(x_i,x_j) = (\sum_{u=1}^{n}{(x_{{iu}-x_{ju}})^p})^{\frac{1}{p}}} d(xi,xj)=(∑u=1n(xiu−xju)p)p1
- p = 1时：曼哈顿距离
- p = 2 时: 欧几里得距离
- 欧式距离
-
缺点：
- 必须要指定分成几类（但是不一定知道要分成几类）
-
改进：
- 基于密度的聚类算法 —— DBSCAN
DBSCAN（Density-Based Spatial Clustering Application with Noises）
-
概念：
-
密度：
- 在一定 ε 邻域中，其他点的数量多少
-
ε 邻域：
- 以其为中心，ε 为半径的范围
-
核心对象：
- 当某点的 ε 邻域内的其他样本多于一定值时，称其为一核心对象
-
密度直达：
- 对一核心对象，其 ε 邻域所有点由其密度直达（单向，不满足对称性）
-
密度可达：
- 某点对于另一点通过密度直达的传递关系能达到的联通效果（满足直递性，不满足对称性）
-
密度相邻：
- 若两点都可以由另一个点密度可达，称这两点密度相邻（无方向，满足对称性）
-
关于对称性的解释：
- 由于闵可夫斯基距离计算去奇数次方的时候可能出现负距离，所以距离两点之间的距离是有方向的( w(u,v) != w(v,u) )，所以 v 可以由 u 密度直达但反之不一定。
-
-
步骤：
- 随机选择一个高密度点作为种子，以其所有密度可达的点作为一类，若仍有可做种子（包含去重操作）的剩余点，则再次随机选取种子，重复上述操作。
层次聚类
-
类似生成树算法？
-
步骤：
-
初始化：
- 每个点各成一类
-
循环：
- 选取距离最近的两个类，若二者的距离小于阈值，则把这两者合为一类，否则，结束循环
-
-
聚类结果的评价
- 类间最大，类内最小
2. 线性模型
概念：
- 通过属性值的线性组合来进行值的预测
- 可分为线性分类和线性回归
线性回归：
-
使用线性模型达到对整体趋势的接近
- 评判：均方误差最小化
- G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V D v D E n t ( D v ) {Gain(D,a)=Ent(D)-\sum_{v=1}^{V}{\frac{D^v}{D}Ent(D^v)}} Gain(D,a)=Ent(D)−∑v=1VDDvEnt(Dv)
-
计算方式：最小二乘法
-
对w与b分别求偏导，令以下两式为0
-
得到以下闭式解
-
-
-
高维情况
- 改写为向量矩阵（b值置1）
-
-
令以下式为零即可
-
若出现多解，考虑正则化
-
- 改写为向量矩阵（b值置1）
-
线性分类
-
LDA：线性判别分析
-
作用：
- 降维、分类
-
-
基本思想：投影
-
给定一个训练样本集，设法将样本的投影点尽可能的接近，异类样本投影点的中心尽可能的远离——类内最小，类间最大
-
对样本进行分类的时，将其投影到同样的直线上去，根据投影点的位置来判定该样本的类别
- -
计算：
- 最大化目标
-
-
- 转化：
-
- 等价于
-
-
带约束的求解：拉格朗日乘数法
-
求解 f(x,y) 在 Φ(x,y)=0 下的极值
- 加入参数：拉格朗格乘子 λ- F(x,y,λ) = f(x,y) + λ * Φ(x,y)
-
使用最小二乘法对 F(x,y,λ) 进行求解
-
多分类问题
-
OVO : 一对一
- 每个类别两两配对进行二分类，最后结果由投票产生
-
OVR ： 一对其余
- 每个类别作为正例与其余所有类别进行二分类，若有多个类别作为正例，则考虑置信度。
-
-
-
-
3. 决策树
算法分类（基于选取子结点的依据）
- ID3：信息增益
- C4.5：增益率
- CART：基尼指数
信息增益
-
信息熵：度量信息的不确定性
- 设共分为Dv个类
- E n t ( D ) = − ∑ k = 1 ∣ y ∣ P k l o g 2 P k {Ent(D) = -\sum_{k=1}^{|y|}{P_klog_2{P_k}}} Ent(D)=−∑k=1∣y∣Pklog2Pk
-
信息增益：
- 某属性分解之前的信息熵与分解之后各块信息熵均值的差
- 类似加权平均，（总体为D，分为V块，为Dv）
- G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V D v D E n t ( D v ) {Gain(D,a)=Ent(D)-\sum_{v=1}^{V}{\frac{D^v}{D}Ent(D^v)}} Gain(D,a)=Ent(D)−∑v=1VDDvEnt(Dv)
- 差值越大，说明引入属性后信息不确定性下降越多，说明属性权重越重
ID3：
- 每次在当前结点还未选择的属性中选出信息增益最大的属性后，按照选中的属性分成几块，若分成的块中仍有不同类别的样本，则继续分解此块（一条路径上一个属性只能分解一次）
决策树评价指标：
-
ROC曲线
-
对于一个二分问题，可将实例（case）分成正类（positive）或负类（negative）。如果进行预测，会出现四种情况：
-
- ROC曲线即是根据一系列不同的二分类方式（分界值或决定阈），以真正例率（True Positive Rate,TPR = TP / (TP+FN）也就是灵敏度）为纵坐标，假正例率（False Positive Rate,FPR = FP / (FP + TN），1-特效性）为横坐标绘制的曲线。
- ROC曲线的面积，即AUC。
-
-
AUC
- AUC（Area Under Curve）即ROC曲线下与坐标轴围成的面积，其概率学上的意义是：随机选取一个正例和一个负例，分类器给正例的打分大于分类器给负例的打分的概率。
剪枝：
-
预剪枝
-
如果分解后的预测准确率比之间咬定一个结果的准确率还要低，就不再分解
-
例：全局：10个瓜，5个好瓜 -> 咬定好瓜，精确度：50%
-
按照纹理分类：
- 清晰：6个里面4个好瓜 -> 判为好瓜 -> 4个判对
- 稍糊：3个里面1个好瓜 -> 判为坏瓜 -> 2个判对
- 模糊：1个坏瓜 -> 坏瓜 -> 1个判对
- 精确度：（4+2+1）/ 10 = 70% > 50% 无须剪枝
-
-
-
-
后剪枝：
- 在生成决策树后，判断剪去某结点后整体精确度会不会上升
*XMind: ZEN - Trial Versio