机器学习(三)线性模型

概念储备：　

　　线性关系是指自变量x与因变量y之间可以表示成y=ax+b ,(a,b为常数)，即说x与y之间成线性关系。

　　线性关系假设即X与Y在总体上具有线性关系，这是一条最基本的假设，也就是说回归分析一定要建立在变量之间存在线性关系的基础上。如果变量之间不存在线性关系时，需要使用非线性模型。

　　本-量-利分析的线性关系假设，首先是指固定成本与产量无关，变动成本与业务量(产量)成正比例关系，其次通常都假设销售单价是个常数，销售收入与销量成正比，二者存在一种线性关系，但些假设也只有在一定的相关范围内才能成立。

　　（The least square method）和（least square error）
1）狭义的最小二乘方法，是线性假设下的一种有闭式解的参数求解方法，最终结果为全局最优；
2）梯度下降法，是假设条件更为广泛（无约束）的，一种通过迭代更新来逐步进行的参数优化方法，最终结果为局部最优；
3）广义的最小二乘准则，是一种对于偏差程度的评估准则，与上两者不同。
4）数值解(numerical solution)
是在特定条件下通过近似计算得出来的一个数值，是采用某种计算方法,如有限元的方法, 数值逼近,插值的方法, 得到的解.别人只能利用数值计算的结果
解析解(analytical solution)就是给出解的具体函数形式，从解的表达式中就可以算出任何对应值，就是一些严格的公式,给出任意的自变量就可以求出其因变量,也就是问题的解, 他人可以利用这些公式计算各自的问题.所谓的解析解是一种包含分式、三角函数、指数、对数甚至无限级数等基本函数的解的形式。解析解为一封闭形式〈closed-form〉的函数，因此对任一独立变量，带入解析函数求得正确的相依变量。因此，解析解也被称为闭式解（closed-form solution）

线性模型是一种高效模型

1.基本形式：

对于给定d个属性描述的示例x=（x1，x2，……，xd）,通过属性的线性组合来进行预测。一般的写法如下：

$$f(x) = \omega^Tx + b$$
　　因此，线性模型具有很好的解释性（understandability，comprehensibility），参数w代表每个属性在回归过程中的重要程度。

2. 线性回归

对于线性回归，我们先考虑简单的问题，输入的属性数目只有一个。
对于线性回归而言，均方误差有非常好的几何意义，它对应了常用的欧几里得距离（欧式距离），
基于均方误差最小化来进行模型求解的方法称“最小二乘法”
在求解时，我们考虑XTX可能不满秩，因此将对应多个接都能使得均方误差最小化，选择哪个解作为输出，将由学习算法的偏好决定，最常见的方法是引入正则化。

广义线性回归，其中函数g（.）称为“联系函数”

3. 对数几率回归（逻辑回归）

　　利用回归来实现分类，只需要找到一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值联系起来。我们利用对数几率函数代替单位阶跃函数，如下：

$$y = \dfrac{1}{1 + e^{-x}}$$

　　对数几率函数是一种“Sigmoid函数”，在神经网络中扮演重要的作用。将输出值转化为接近0或者1的y值，
　　

$$y = \dfrac{1}{1 + e^{-(\omega^Tx+b)}}$$
　　然后将上面这式子进行变形
　　 $$ln \dfrac{y}{1-y}= \omega^Tx+b$$
　　若将y看做是样本x作为正例的可能性，则1-y是其作为反例可能性，两者之间的比值为y/1-y称为几率（odds），对几率取对数则得到“对数几率”。
　　 $$\dfrac{y}{1-y}$$
　　逻辑回归不仅能够能够实现对任务进行分类，同时可以得到近似概率预测
　　 $$p(y = 1 \mid x) = \dfrac{ e^{\omega^Tx+b}}{1+ e^{\omega^Tx+b}}$$
　　 $$p(y = 0 \mid x) = \dfrac{ e^{\omega^Tx+b}}{1+ e^{\omega^Tx+b}}$$
　　利用极大似然法（maximum likelihood method）进行估计w和b。

　　

$$l(\omega, b) =\sum_{i=1}^m ln p(y_{i}\mid x_i;\omega,b )$$
　　
　　上述的函数是关于B的高阶可导函数，根据凸优化理论，经典的数值优化算法如梯度下降法（gradient descent method）、牛顿法（Newton method）可求得最优解。
　　协方差矩阵计算的是不同维度之间的协方差，而不是不同样本之间的。

4.线性判别分析

线性判别分析 Liner Discriminant Analysis (LDA) 是一种经典的线性学习方法（二分类）
思想：给定训练样例，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；在对新样本进行分类时，将其投影到同样的一条直线上，再根据投影点的位置来确定新样本的类型

5.多分类问题

现实中常遇到多分类学习任务，有些二分类学习方法可以直接推广到多分分类，但更多情况下，我们是基于一些基本策略，利用二分类学习方法来解决多分类问题。

6.类别不平衡问题

 大部分分类任务中，各类别下的数据个数基本上不可能完全相等，但是一点点差异是不会产生任何影响与问题的。
  在现实中有很多类别不均衡问题，它是常见的，并且也是合理的，符合人们期望的。如，在欺诈交易识别中，属于欺诈交易的应该是很少部分，即绝大部分交易是正常的，只有极少部分的交易属于欺诈交易。这就是一个正常的类别不均衡问题。又如，在客户流失的数据集中，绝大部分的客户是会继续享受其服务的（非流失对象），只有极少数部分的客户不会再继续享受其服务（流失对象）。一般而已，如果类别不平衡比例超过4:1，那么其分类器会大大地因为数据不平衡性而无法满足分类要求的。因此在构建分类模型之前，需要对分类不均衡性问题进行处理。
  在前面，我们使用准确度这个指标来评价分类质量，可以看出，在类别不均衡时，准确度这个评价指标并不能work。因为分类器将所有的样本都分类到大类下面时，该指标值仍然会很高。即，该分类器偏向了大类这个类别的数据。
八大解决方法

可以扩大数据集吗？
  当遇到类别不均衡问题时，首先应该想到，是否可能再增加数据（一定要有小类样本数据），更多的数据往往战胜更好的算法。因为机器学习是使用现有的数据多整个数据的分布进行估计，因此更多的数据往往能够得到更多的分布信息，以及更好分布估计。即使再增加小类样本数据时，又增加了大类样本数据，也可以使用放弃一部分大类数据（即对大类数据进行欠采样）来解决。
尝试其它评价指标
  从前面的分析可以看出，准确度这个评价指标在类别不均衡的分类任务中并不能work，甚至进行误导（分类器不work，但是从这个指标来看，该分类器有着很好的评价指标得分）。因此在类别不均衡分类任务中，需要使用更有说服力的评价指标来对分类器进行评价。如何对不同的问题选择有效的评价指标参见这里。
  上面的超链接中的文章，讲述了如何对乳腺癌患者复发类别不均衡数据进行分类。在文中，推荐了几个比传统的准确度更有效的评价指标：

混淆矩阵(Confusion Matrix)：使用一个表格对分类器所预测的类别与其真实的类别的样本统计，分别为：TP、FN、FP与TN。
精确度(Precision)
召回率(Recall)
F1得分(F1 Score)：精确度与找召回率的加权平均。
  特别是：

Kappa (Cohen kappa)
ROC曲线(ROC Curves)：见Assessing and Comparing Classifier Performance with ROC Curves
对数据集进行重采样
  可以使用一些策略该减轻数据的不平衡程度。该策略便是采样(sampling)，主要有两种采样方法来降低数据的不平衡性。

对小类的数据样本进行采样来增加小类的数据样本个数，即过采样（over-sampling ，采样的个数大于该类样本的个数）。
对大类的数据样本进行采样来减少该类数据样本的个数，即欠采样（under-sampling，采样的次数少于该类样本的个素）。
  采样算法往往很容易实现，并且其运行速度快，并且效果也不错。更详细的内容参见这里。
  一些经验法则：

考虑对大类下的样本（超过1万、十万甚至更多）进行欠采样，即删除部分样本；
考虑对小类下的样本（不足1为甚至更少）进行过采样，即添加部分样本的副本；
考虑尝试随机采样与非随机采样两种采样方法；
考虑对各类别尝试不同的采样比例，比一定是1:1，有时候1:1反而不好，因为与现实情况相差甚远；
考虑同时使用过采样与欠采样。
尝试产生人工数据样本
  一种简单的人工样本数据产生的方法便是，对该类下的所有样本每个属性特征的取值空间中随机选取一个组成新的样本，即属性值随机采样。你可以使用基于经验对属性值进行随机采样而构造新的人工样本，或者使用类似朴素贝叶斯方法假设各属性之间互相独立进行采样，这样便可得到更多的数据，但是无法保证属性之前的线性关系（如果本身是存在的）。
  有一个系统的构造人工数据样本的方法SMOTE(Synthetic Minority Over-sampling Technique)。SMOTE是一种过采样算法，它构造新的小类样本而不是产生小类中已有的样本的副本，即该算法构造的数据是新样本，原数据集中不存在的。该基于距离度量选择小类别下两个或者更多的相似样本，然后选择其中一个样本，并随机选择一定数量的邻居样本对选择的那个样本的一个属性增加噪声，每次处理一个属性。这样就构造了更多的新生数据。具体可以参见原始论文。
  这里有SMOTE算法的多个不同语言的实现版本：
Python: UnbalancedDataset模块提供了SMOTE算法的多种不同实现版本，以及多种重采样算法。
R: DMwR package。
Weka: SMOTE supervised filter。
尝试不同的分类算法
  强烈建议不要对待每一个分类都使用自己喜欢而熟悉的分类算法。应该使用不同的算法对其进行比较，因为不同的算法使用于不同的任务与数据。具体可以参见“Why you should be Spot-Checking Algorithms on your Machine Learning Problems”。
  决策树往往在类别不均衡数据上表现不错。它使用基于类变量的划分规则去创建分类树，因此可以强制地将不同类别的样本分开。目前流行的决策树算法有：C4.5、C5.0、CART和Random Forest等。基于R编写的决策树参见这里。基于Python的Scikit-learn的CART使用参见这里。
尝试对模型进行惩罚
  你可以使用相同的分类算法，但是使用一个不同的角度，比如你的分类任务是识别那些小类，那么可以对分类器的小类样本数据增加权值，降低大类样本的权值（这种方法其实是产生了新的数据分布，即产生了新的数据集，译者注），从而使得分类器将重点集中在小类样本身上。一个具体做法就是，在训练分类器时，若分类器将小类样本分错时额外增加分类器一个小类样本分错代价，这个额外的代价可以使得分类器更加“关心”小类样本。如penalized-SVM和penalized-LDA算法。
  Weka中有一个惩罚模型的通用框架CostSensitiveClassifier，它能够对任何分类器进行封装，并且使用一个自定义的惩罚矩阵对分错的样本进行惩罚。
  如果你锁定一个具体的算法时，并且无法通过使用重采样来解决不均衡性问题而得到较差的分类结果。这样你便可以使用惩罚模型来解决不平衡性问题。但是，设置惩罚矩阵是一个复杂的事，因此你需要根据你的任务尝试不同的惩罚矩阵，并选取一个较好的惩罚矩阵。
尝试一个新的角度理解问题
  我们可以从不同于分类的角度去解决数据不均衡性问题，我们可以把那些小类的样本作为异常点(outliers)，因此该问题便转化为异常点检测(anomaly detection)与变化趋势检测问题(change detection)。
  异常点检测即是对那些罕见事件进行识别。如通过机器的部件的振动识别机器故障，又如通过系统调用序列识别恶意程序。这些事件相对于正常情况是很少见的。
  变化趋势检测类似于异常点检测，不同在于其通过检测不寻常的变化趋势来识别。如通过观察用户模式或银行交易来检测用户行为的不寻常改变。
  将小类样本作为异常点这种思维的转变，可以帮助考虑新的方法去分离或分类样本。这两种方法从不同的角度去思考，让你尝试新的方法去解决问题。
尝试创新
  仔细对你的问题进行分析与挖掘，是否可以将你的问题划分成多个更小的问题，而这些小问题更容易解决。你可以从这篇文章In classification, how do you handle an unbalanced training set?中得到灵感。例如：
将你的大类压缩成小类；
使用One Class分类器（将小类作为异常点）；
使用集成方式，训练多个分类器，然后联合这些分类器进行分类；
….
  这些想法只是冰山一角，你可以想到更多的有趣的和有创意的想法去解决问题。更多的想法参加Reddit的文章http://www.quora.com/In-classification-how-do-you-handle-an-unbalanced-training-set。

选择某一种方法并使用它

  你不必成为一个精通所有算法的算法奇才或者一个建立准确而可靠的处理数据不平衡的模型的统计学家，你只需要根据你的问题的实际情况从上述算法或方法中去选择一种或两种方法去使用。希望上述的某些方法能够解决你的问题。例如使用其它评价指标或重采样算法速度快并且有效。

总结

  记住，其实并不知道哪种方法最适合你的任务与数据，你可以使用一些启发式规则或经验去选择某一个较优算法。当然最好的方法测试每一种算法，然后选择最好的方法。最重要的是，从点滴开始做起，根据自己现有的知识，并不断学习去一步步完善。

Further Reading…

  这里有一些我认为有价值的可供参考的相关资料，让你进一步去认识与研究数据不平衡问题：

相关书籍
Imbalanced Learning: Foundations, Algorithms, and Applications
相关论文
Data Mining for Imbalanced Datasets: An Overview
Learning from Imbalanced Data
Addressing the Curse of Imbalanced Training Sets: One-Sided Selection (PDF)
A Study of the Behavior of Several Methods for Balancing Machine Learning Training Data
Sergey Feldman的回答：

设超大类中样本的个数是极小类中样本个数的L倍，那么在随机梯度下降（SGD，stochastic gradient descent）算法中，每次遇到一个极小类中样本进行训练时，训练L次。
将大类中样本划分到L个聚类中，然后训练L个分类器，每个分类器使用大类中的一个簇与所有的小类样本进行训练得到。最后对这L个分类器采取少数服从多数对未知类别数据进行分类，如果是连续值（预测），那么采用平均值。
设小类中有N个样本。将大类聚类成N个簇，然后使用每个簇的中心组成大类中的N个样本，加上小类中所有的样本进行训练。
无论你使用前面的何种方法，都对某个或某些类进行了损害。为了不进行损害，那么可以使用全部的训练集采用多种分类方法分别建立分类器而得到多个分类器，采用投票的方式对未知类别的数据进行分类，如果是连续值（预测），那么采用平均值。
在最近的ICML论文中，表明增加数据量使得已知分布的训练集的误差增加了，即破坏了原有训练集的分布，从而可以提高分类器的性能。这篇论文与类别不平衡问题不相关，因为它隐式地使用数学方式增加数据而使得数据集大小不变。但是，我认为破坏原有的分布是有益的。
More details than you need: imho, the most interesting of the corrupting distributions is the blankout distribution, where you just zero out a random subset of features. Why is it interesting? Because you are helping your classifier be sturdier/hardier by giving it variations of your data that have essentially missing features. So it has to learn to classify correctly even in adverse conditions. 一个相关的想法是，在神经网络中，随机选择部分隐藏层单元来继续训练（即，随机去掉一部分隐藏层单元，(zeroed-out)）。具体见http://web.stanford.edu/~sidaw/cgi-bin/home/lib/exe/fetch.php?media=papers:fastdropout.pdf
Kripa Chettiar的回答：

增加新数据，可以使用SMOTE或SMOTEBoost产生人造数据。
将大类压缩。压缩比例需要具体情况具体分析，取决于你所拥有的数据。例如，A类中有30个样本，B类中有4000个样本，那么你可以将B类压缩成1000（进行采样）。
可以结合1与2
对于那种极小类是异常点的分类任务，因此分类器需要学习到大类的决策分界面，即分类器是一个单个类分类器（One Class Classifier）。Weka中有相关的库。
获得更多的数据。
Roar Nybø的回答：

对小类进行过采样。并且使用集成模式会获得更好的效果。
Dan Levin的回答：

一个很好的方法去处理非平衡数据问题，并且在理论上证明了。这个方法便是由Robert E. Schapire于1990年在Machine Learning提出的”The strength of weak learnability” ，该方法是一个boosting算法，它递归地训练三个弱学习器，然后将这三个弱学习器结合起形成一个强的学习器。我们可以使用这个算法的第一步去解决数据不平衡问题。
  首先使用原始数据集训练第一个学习器L1。
  然后使用50%在L1学习正确和50%学习错误的的那些样本训练得到学习器L2，即从L1中学习错误的样本集与学习正确的样本集中，循环一边采样一个。
  接着，使用L1与L2不一致的那些样本去训练得到学习器L3。
  最后，使用投票方式作为最后输出。
  那么如何使用该算法来解决类别不平衡问题呢？
  假设是一个二分类问题，大部分的样本都是true类。让L1输出始终为true。使用50%在L1分类正确的与50%分类错误的样本训练得到L2，即从L1中学习错误的样本集与学习正确的样本集中，循环一边采样一个。因此，L2的训练样本是平衡的。L使用L1与L2分类不一致的那些样本训练得到L3，即在L2中分类为false的那些样本。最后，结合这三个分类器，采用投票的方式来决定分类结果，因此只有当L2与L3都分类为false时，最终结果才为false，否则true。
  自己已经在实践中使用过很多次，并且效果都不错。
Kaushik Kasi的回答：

对小类中的样本进行复制以增加该类中的样本数，但是可能会增加bias。
对小类中的样本通过调整特征值来人工生成样本，而使得该类中样本个数增多。如在图像中，对一幅图像进行扭曲得到另一幅图像，即改变了原图像的某些特征值。但是该方法可能会产生现实中并存在的样本。
Quora User的回答：

简单快速的方法：对大类欠采样或者对小类过采样。
更有效的方法：使用代价函数学习得到每个类的权值，大类的权值小，小类的权值大。刚开始，可以设置每个类别的权值与样本个数比例的倒数，然后可以使用过采样进行调优。
Dayvid Victor的回答：

  在类别不平衡中，以下几个点需要注意：

常规的分类评价指标可能会失效，比如将所有的样本都分类成大类，那么准确率、精确率等都会很高。这种情况下，AUC时最好的评价指标。
你能够使用原型选择技术去降低不平衡水平。选择那些重要的样本。One-Sided Selection (OSS) 是一个预处理技术（模型训练之前使用），能够处理类别不平衡问题。
从另一个角度，可以增加小类的样本个数，可以使用过采样与原型生成技术（prototype-generation techniques）。
在K-Fold 校验中，每一份数据集中原则上应该保持类别样本比例一样或者近似，如果每份数据集中小类样本数目过少，那么应该降低K的值，知道小类样本的个数足够。
  一般来说，如果事前不对不平衡问题进行处理，那么对于小类别的样本则会错误率很高，即大部分甚至全部小类样本都会分错。
Muktabh Mayank的回答：

这里有一个类似SVM的方法来处理不平衡问题。具体参见这里。
Sandeep Subramanian的回答：

使用SMOTE（Synthetic Minority Oversampling TEchnique）方法人工生成小类数据。其类似于最近邻算法。
Quora User的回答：

赋予小类样本更高的训练权值
对小类进行过采样
某些时候，高不平衡性下仍然可以得到效果较好的训练结果。我认为对于某些评价指标是有意义的，如AUC。
Sumit Soman 的回答：

如果你使用SVM分类器进行分类，那么可以使用Twin SVM（Twin Support Vector Machines for Pattern Classification），其能够应付类别不平衡问题。

以上内容均来自周教授的《机器学习》
其中多次出现矩阵，转置矩阵，向量，各种分布，拉格朗日乘子法，贝叶斯决策理论，最小二乘法等数学概念的应用。对数学基础要求比较高，鄙人数学初中水平，导致一知半解，不明其中奥妙。暂且记下，日后渐渐沉淀