分类算法

读书笔记

基本概念

分类是使用特定的信息（输入）从一个预定义的潜在回应列表中做出单一选择（输出）的过程。分类是一种简单的决策形式，对单个问题提供一个离散的答案。基于机器的分类是上述决策的自动化过程，它从正确决策样本中进行学习并自动对决策进行仿真，这也是预测分析的核心概念。预测分析的目标就是建立一个自动化系统，以取代人类做出决策的功能。
分类算法的典型应用有垃圾邮件检测以及信用卡欺诈检测。
分类算法与聚类算法的区别在于聚类是无监督学习，算法自己能决定哪些区别是重要的，而分类则需要模仿做出正确决策的样本来学习，即有监督学习。分类算法与推荐算法的区别在于分类算法试图从很有限的输出集合中做出单一决策，而推荐算法会选择许多可能的答案，并对其进行排序。

基本原理

构建分类系统主要有两个阶段：通过学习算法建立一个模型，然后使用该模型对新数据进行分类。如下图：

在分类中，有几个关键术语，如下表所示

预测变量值的4种常见类型

选择训练分类器的算法

SGD&SVM

这两个算法都是串行执行，而非并行。
SGD（随机梯度下降）算法应用广泛，是那种靠每个训练样本对模型进行微调，然后逐步接近该样本正确答案的学习算法。这一递增模式在多个训练样本上重复执行。
SVM（支持向量机）是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。SVM算法详解可参考http://www.cnblogs.com/LeftNotEasy/archive/2011/05/02/basic-of-svm.html

朴素贝叶斯

具体参考：http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html
Mahout实现的朴素贝叶斯，仅限于基于单一文本型变量进行分类。如果需要连续变量，并且不能将其量化为单词型对象从而和其他文本数据一块处理，可能就没办法使用贝朴素叶斯一系的算法。

随机森林

具体参考：http://www.cnblogs.com/wentingtu/archive/2011/12/13/2286212.html
Mahout中提供了随机森林算法的串行和并行两种实现。这一算法首先训练大量的简单分类器，然后通过投票机制得出最终的唯一结果。

分类器评估&调优

评估

为了评估分类器，Mahout提供了一系列的性能指标，主要包括正确百分比或称正确率（percent correct）、混淆矩阵（confusion matrix）、AUC、对数似然（log likelihood）等。需要注意的是，诸如正确率之类的简单精度指标并不是对分类器进行评估和调优最好的指标。同时，要认识到不同的错误代价，举例来说，如果垃圾邮件被判定为正常，用户最多是抱怨，但如果正常邮件被判定为垃圾邮件，则用户可能会大为光火。
下面简单介绍下各类性能指标的含义。当所要评估的模型的目标变量为二值且该模型的输出得分为连续值时，采用AUC指标十分有用。而对于输出非分值结果的分类器来说，可能最直接的指标就是混淆矩阵。混淆矩阵是模型输出结果和已知正确目标值的交叉表。矩阵的每一行对应真是目标值而每一列对应模型的输出值。矩阵第i行j列的元素值为类别i的测试样本被模型分到类别j中的数目。一个好模型对应的混淆矩阵的大元素都集中于对角线。与混淆矩阵一样，熵矩阵中的每列对应的是实际的目标值，每列对应模型的输出值。区别在于，熵矩阵的元素计算是每个真实或估计类别组合的概率的平均对数值。对数似然是基于对输出结果的确信或非确信程度来对模型进行评分的方法，它有一个很有用的特地，即即使模型并没有精确地得到正确结果，但是在可能结果的范围有所限制时仍然得到部分的信用值。

调优

与通常的软件工程不同，模型的失败通常并不像废弃的空指针或内存溢出异常那么明显。与此相反，一个失败的模型可能会输出异常精确的结果。这样的模型同时也会输出错误里很高的结果，看上去模型不太对头。如果发现，特别在模型构建初期，分类器的结果极端精确或者糟糕，那么这一结果多少值得怀疑，这一点相当重要。在分类器模型构建过程中两个最普遍的问题称为目标泄露（target leak）和特征提取泄露（broken feature extraction）。
目标泄露是由于目标变量的信息包含在用于训练分类器的预测变量中而带来的漏洞。目标泄露的一个最主要的征兆是结果的性能好得难以置信。如果模型表现得异常好，或者如果在新数据的表现显著茶语交叉校验的预测结果，那么就值得观察一个ModelDissector的输出结果。
特征提取泄露指特征提取部分在某种程度上发生奔溃。如果奔溃的字段对模型有帮助，那么这种部分的奔溃情况会导致性能的降低。发现上述问题最好的方法是计算系统中值的汇总统计信息，如果值连续，则可以用OnlineSummarizer来检查均值、最小值、最大值和四分位数。
除了修改上述两种错误外，还有很多方法可以提高分类器的性能。

• 剔除无价值的变量：这时可以使得学习算法集中在更少的变量上
• 增加新的变量、交互和导出值：如通过聚类增加一个簇的类别型特征
• 调整学习算法：修改算法、调整参数等