大数据分析与挖掘技术Mahout分类算法

目录

一、分类的基本概念

二、Mahout中常见的训练分类器算法

（一）SGD算法

（二）SVM算法

（三）朴素贝叶斯算法

（四）随机森林算法

三、应用实例：使用SGD训练分类器对新闻分类

（一）数据集预览

（二）数据训练

        本节介绍Mahout 中学习算法的最后一个部分——分类算法。本节由三小节构成，我们首先要明确分类的概念，再对常用的专用名词、分类程序运行的基本过程进行了解。随后介绍一些在Mahout中的常见的训练分类器的算法。对于使用Mahout 进行分类器训练，我们并不需要了解太多算法底层的数学原理与推导过程，因此，我们仅对不同的分类算法的特点进行描述。最后我们使用实例来展示如何将一个数据集进行处理、模型训练和分类应用。

一、分类的基本概念

        分类是使用特定信息（输入）从一个预定义的潜在回应列表中做出单一选择（输出）的过程。在上述定义中，很容易混淆的一点就是回应列表的固定性，生活中有很多例子，比如，顾客去超市购买商品，对于某件商品而言，它的属性（类别、品牌、质量和颜色等）作为输入，购买与否（是和否）作为输出，这个一个分类的例子，因为它的可能性只有两种，购买或者不买，这构成了一种分类回应列表。但是，如在评论一件商品时，对于同样的输入（类别、品牌、质量和颜色等），得到的输出却可能有很多（很不错、质量好和面料柔软，等等），此时由于输出列表的不确定性，不能构成分类。对于计算机来说，尽管不能完成人类在某些情况下的思维过程，但是可以模拟人的决策过程，高效地进行分类，分类是预测分析（Predictive Analytic）的核心，它的目标就是实现以自动化的系统取代人类做出决策的功能。
        和聚类算法不同，分类算法是一种有监督的学习，需要准备一些正确决策的样本供机器进行前期训练，而聚类算法则不需要进行训练。相对于前面所说的推荐算法，分类算法会从有限的输出集合给出确定的一个答案，而推荐算法会选择很多可能的答案，并按照可能性对它们进行排序；同时，它们的输人数据也不一样，推荐系统更倾向于使用用户的历史行为数据，对用户本身和物品本身的特征数据则不太关心，分类系统则更关心用户和物品本身的属性。
        建立一个分类系统，主要分为两个阶段，第一个阶段是通过某种学习算法对已知数据（训练集）进行训练建立一个分类模型，第二个阶段是使用该模型对新数据进行分类。其中涉及的概念和术语主要有以下几个。

1、训练样本

        训练样本是具有特征的实体，将被用作学习算法的输入。通常，将训练样本分为训练数据和测试数据，训练数据是训练样本的一个子集，带有目标变量值的标注，用作学习算法的输入以生成模型；测试数据则是存留的部分训练样本，隐藏其目标变量值，以便于评估模型。

2、特征（变量、字段和记录）

        特征是训练样本或新样本的一个已知特性，特征与特性是等同的。变量、字段和记录：在分类这一节中，变量指一个特征的值或一个关于多个特征的函数，不同于计算机编程中的变量。在分类过程中，一般涉及预测变量和目标变量。记录是用来存放样本的一个容器，由多个字段构成，每个字段存储一个变量。对于分类问题而言，目标变量必须有一个类别型的值，而预测变量的值可以是连续的/类别型文本/单词等。在实际应用中，目标变量常常是二值类别型的，例如，在垃圾邮件分类问题中，每个邮件要么是垃圾邮件要么不是，不存在中间状态或者非两者之间的状态。当目标变量具有两个以上的可能时，称之为多分类问题，这种问题在分类算法中也有相应的研究。变量值常见的四种类型（对于目标变量而言，只能存在类别型）如表所示。

值的类型 描述
连续型 通常是一个浮点值，可能是任何具有具体数值大小的量，比如价格、重量、时间、长度等，而且这个数值大小是这个值的关键属性
类别型 通常类别型数据从一个已知的集合中进行取值，无论这个集合有多大(但不能为无穷集合)，常见的集合只有两个元素，例如，布尔型数据{0,1}，也有可能是多个数据的集合
单词型 单词型值类似于类别型的值，但是它的取值集合是无穷集合，即所有单词
文本型 文本型值是多个单词型值的序列，例如，邮件地址或者一篇文章

        在实际应用中，往往会混淆连续型和类别型变量，如与数字有关的值，如邮政编码，容易识别为连续型变量，但是其中每个值都取自于预先指定的集合（所有邮政编码），在此将其识别为类别型值会更合适。如果将其错误归类，在机器学习的过程中会严重影响分类精度，常见的计量单位都是连续型；反之，若两个值相加/减/开方后就失去意义，它往往是一个类别型变量。

3、模型和训练

        模型和训练：在分类中，训练算法的输出就是一个模型。训练就是使用训练数据生成模型的学习过程，随后该模型可将预测变量作为输入来估计目标变量的值。训练过程的输出就是模型，也可以视作一个函数，该函数可以用于新样本生成输出，模仿原始样本上的决策，这些决策就是分类系纯的最终产出。
        实际上，我们常常将训练样本分为两部分，其中一部分用作训练数据，约占总样本数量的80%到90%，用于提供给训练算法进行训练产生模型；剩下的数据用作测试数据，将其隐藏目标变量后提供给模刑进行模拟决策，通过比较其决策结果和真实结果来对训练出的模型进行评估。通常，模型做出的决策不会完全正确，但是只要满足一定的性能需求，该模型便可投入生产，在使用的过程中，模型预测的准确率应该与评估过程的准确率相同。
        为了提升模型的效率和准确性，一个通常的做法是随着时间的推移，对生产环境中的样本进行采样并加入训练数据中，重新对模型进行校正，形成不断更新的模型版本。特别是当外部条件随时间逐渐改变而使得模型质量不断下降时，这种方法显得尤为重要。  

4、预测变量和目标变量

        预测变量和目标变量：在分类过程中，预测变量为模型提供线索或者经验，以便模型能够判断各个样本目标变量应该是什么样的变量。需要注意的是，分类学习不一定会用到所有特征，某些特征可能是其他特征按某种规则进行组合的结果。而目标变量是可分类的，决定其值就是分类系统的目标。正如在本节开始时举出的购买商品的分类例子，将商品的属性（价格、颜色、类别、质量和品牌等）用作模型的输入，购买与否（是和否）作为模型输出。在这个例子中，商品的各个属性就类似于分类器中的预测变量，决策目标就是一个二值的目标变量购买（是和否），每个商品对应且只对应一个选择。
        值得注意的是，在训练过程中，预测变量和目标变量都会被使用，而在模型建立以后，用作测试和实际应用时，模型仅能使用预测变量进行工作。在测试阶段，通常使用部分训练样本数据，隐藏其目标变量后作为模型的输入，让模型进行决策；然后，通过比较模型给出的输出与实际目标变量的差异来评价分类模型的效果，一个典型的分类系统的结构如图所示。

        有监督学习和无监督学习：分类算法是一种有监督学习，因为其处理的数据均带有一个特定的期望值（目标变量），而聚类算法属于无监督学习，没有一个期望的确切答案，只需要给出数据聚类的合理解释即可。同时，无监督学习中使用的训练样本也是没有目标变量的，有监督学习则需要提供目标变量进行模型构建。
        可以将这两种学习方式结合起来，得到更好的模型，通常采用聚类算法对原始数据进行处理，生成一些特征供分类算法使用；或者反之使用多个分类器进行处理，得到的输出作为特征供聚类算法使用。这种结合的方式能够大大提高数据分析的合理性与有效性。

二、Mahout中常见的训练分类器算法

（一）SGD算法

        随机梯度下降（Stochastic Gradient Descent，SGD）算法是一个非并行的算法，主要的思想是靠每个训练样本对模型进行微调，然后逐步接近样本正确答案的学习算法。这一递增模式在多个训练样本上重复执行，尽管SGD算法很难实现并行计算，但由于它是一个线性的时间复杂度算法，处理大多数应用的速度也很快，所以也没有必要采用并行计算方式。

        Mahout中关于SGD算法的实现主要有以下几个类：OnlineLogisticRegression、 CrossFoldLearner和AdaptiveLogisticRegression。

（二）SVM算法

        支持向量机（Support Vector Machine，SVM）是一种二分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

        从几何性质上看，如图给出了三种分类方式。可以看出，第三张图的分割超平面分割效果最好。能够容忍更多噪声就需要所有样本与分割超平面的距离尽可能远。为了求得这个尽可能远的分割超平面，就需要我们求得每个点到超平面的距离之和，并求得当取得这个最小距离和时的超平面。

（三）朴素贝叶斯算法

        朴素贝叶斯分类器（Naive Bayes Classifier，NBC）发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。Mahout实现的朴素贝叶斯仅限于基于单一文本型变量进行分类，对于很多问题来说，包括典型的大规模数据问题，影响不是很大。但如果需要基于连续变量，并且不能将其量化为单词型对象从而和其他文本数据一并处理时，可能就没办法使用朴素贝叶斯一系列的算法。

贝叶斯定理：P(B|A)=frac{P(A|B)P(B)}{P(A)}

        此外，如果数据中含有不止一类的单词型或文本型变量，可能需要把这些变量拼接到一起，并以一种明确的方式添加前缀以消除歧义。这样做可能会损失重要的差异信息，因为所有单词和类别的统计数据都混到一起了。但大多数文本分类问题，基本上都可以使用朴素贝叶斯或补充朴素贝叶斯算法解决。

（四）随机森林算法

        随机森林是一种多功能的机器学习算法，能够执行回归和分类的任务。之所以命名为随机森林，是烟为它是中很多的决策树构成，并且采用了随机的方式形成决策树。这些决策树在训练中被构造出来，所有的树在训练过程中都是使用同样的参数，但是训练集是不同的（Bagging）。因此，随机性主要体现在以下两个方面。
（1）构造每颗决策树时，都通过随机方式从N个全部样本中选择N个随机样本（可能会有重复）。
（2）在其中的每个节点中，也是通过随机的方式选取所有特征的子集来计算最佳分割方式，这是第二个随机性所在。
        随机森林的错误估计采用的是OOB（Out of Bag）的办法。当判别一个新的对象的类别时，通过投票的方式，每棵树均给出自己的判别，最后输出的票最多的一项；回归问题则会稍有不同，它采用的是输出平均值的方式给出预期结果。        

        下表列出了这几种训练算法的不同与适合场景。

数据集大小 Mahout算法 执行模型 特性
小到中型（数据样本数在千万级以下）

随机梯度下降（SGD）：

OnlineLogisticRegression

CrossFoldLearner

AdaptiveLogisticRegression

 串行、在线、增量式 使用全部类型的预测变量，在数据规模合适的情况下十分高效
支持向量机（SVM） 串行 在数据规模合适的情况下十分适合、高效
大到中型（训练样本数量在百万到上亿之间） 朴素贝叶斯 并行 适合于文本型数据；需要中等到很大的训练开销；处理对于SGD和SVM来说过大的数据集实用有效
补充朴素贝叶斯 并行 比朴素贝叶斯的训练成本高一些；处理对于SGD来说过大的数据集实用有效，但有和朴素贝叶斯类似的局限性
小到中型（训练样本数量在千万以内） 随机森林 并行 使用全部类型的预测变量；训练开销高；成本高，能够实现复杂的分类，比其他技术更擅于处理数据中非线性和条件关系

三、应用实例：使用SGD训练分类器对新闻分类

        20 newsgroups数据集是机器学习研究中常用的标准数据集，来自于20世纪90年代早期20个Usenet新闻组上几个月消息的副本。这个数 据集的结构比较复杂，可从以下几个方面对其进行解析和训练。

（一）数据集预览

        在进行分类之前，要对数据集进行一个预览，以便确定哪些特征可以帮助将样本分到选定目标变量的类别中，将下载好的数据集解压，查看其中的某一个文件，可以看到类似于以下内容。

From: [email protected] 
Subject: Certifying Authority question answered.
Organization: Suite Software 
Lines: 12 
Reply-To: [email protected] 
NNTP-Posting-Host: nimrod.suite.com

>>If you have access to FTP,try FTPing to rsa.com,login as anonymous. 
>>There are several documents there,including a "frequently asked questions 
>>about today's cryptography" document. It has FAQ in its name. 
>>I believe this document explains the idea behind the certifying authorities.
>>
>>Good luck 
>>
>>--John Kelsey, [email protected]

Thanks.I've ftp'ed the FAQfile and it is just what I was looking for.

[email protected]

        每一个文件都由一个文件头开始，描述了该消息的属性（由谁发送、长度、主题和组织等），然后是由一个空白行分隔，接着是消息的主要内容，每个文件的文件头不完全一样，根据文件头中出现次数最多的特征可以帮我们确定那些特征是最可能影响分类结果的字段。经过统计，该数据集最常出现的文件头字段是Subjects、From、Lines、keywords和Summary五个，分别代表该新闻的主题、源头、长度、关键词、总结。

（二）数据训练

        在SGD算法中，Mahout常用的由三个类，本次采用OnlineLogisticRegression类进行训练分类器，首先要将文本和数字转化为向量值，代码如下所示。

Map<String,Set<Integer>> traceDictionary = new TreeMap<String,Set<Integer>>();
FeatureVectorEncoder encoder = new StaticWordvalueEncoder("body");
encoder.setProbes(2);
encoder.setTraceDictionary(traceDictionary);
FeatureVectorEncoder bias = new ConstantValueEncoder("Intercept");
bias.setTraceDictionary(traceDictionary);
FeatureVectorEncoder lines = new ConstantValueEncoder("Lines");
lines.setTraceDictionary(traceDictionary);
Dictionary newsGroups = new Dictionary();
Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_31);

        接下来，采用OnlineLogisticRegressionL类配置Logistic回归学习算法，代码如下:

OnlineLogisticRegression learningAlgorithm = new OnlineLogisticRegression(
    20,FEATURES,new L1()).alpha(1).stepOffset(1000).decayExponent(0.9).
    lambda(3.0e-5).learningRate(20); 

        这个函数中的参数包括：指定的目标变量类别的个数、特征向量的大小及正则化项。此外，学算法中还有一些配置方法。其中，alpha、decayExponent和stepOffset方法可以指定学习率、衰减率以及衰减方式。 Lambda用来指定正则化的权重，learningRate用于指定初始学习率。接下来我们需要获得所有训练数据文件的清单，代码如下所示。

List<File> files = new ArrayList<File>();
for(File newsgroup: base.listFiles()){
    newsGroups.intern(newsgroup.getnName());
    files.addAll(Arrays.addList(newsgroup.listFiles()));
} 
Collections.shuffle(files);
System.out.printf("%d training files
",files.size());

        这段代码将所有新闻组的名字放入词典中，这样有助于在多次训练结果之间进行比较。
        下一个阶段是将可分类数据转换为向量。在这个数据集中，除了Lines，所有数据字段都是文本或单词型，其格式可以用标准的Lucene词条化工具轻松完成。Lines字段是数字，也能用Lucene条化订具解析。看起来这个字段对于区分某些新闻非常有价值，因为有些媒体喜欢发长新闻而有些媒体喜欢发短新闻，代码如下。

double averageLL = 0.0;
double averageCorrect = 0.0;
double averageLineCount = 0.0;
int k = 0;
double step = 0.0; 
int[] bumps = new int[]{1,2,5};
double lineCount;
for(File file:files){
    BufferedReader reader = new BufferedReader(new FileReader(file));
    //识别新闻组
    String ng = file.getParentFile().getName();
    int actual = newsGroups.intern(ng); 
    Multiset<String>words = ConcurrentHashMultiset.create();
    String line = reader.readLine();
    while(line!=null&&line.length()>0){
        //检查行数文件头
        if(line.startWith("Lines:")){ 
            String count = Iterables.get(onColon.split(Line),1);
            try{ 
                1ineCount = Integer.parseInt(Count);
                averageLineCount += (1ineCount-averageLineCount)/Math.min(k+1,1000);
            }catch(Number FormatException e){
                linecount = averageLineCount;
            }
        }
        boolean count Header = (line.startWith("From:")||
            line.startWith("Subject:")||
            line.startWith("Keywords:")||
            line.startWith("Summary:"));
        do{ 
            //计算文件头中单词数量
            StringReader in = new StringReader(line);
            if(countHeader){
                countWords(analyzer,words,in);
            }
            line = reader.readLine;
        }            
    while(line.startWith(" "));
    }
    //计算文件主体中单词的数量
    countWords(analyzer, words,reader);
    reader.close();
}

        通过上述代码可以确定文件的四个特征，即新闻组、行数、文件头中单词数和文档主体中单词数，接下来将所收集到的特征并入一个特征向量中，以供分类器的学习算法使用，代码如下。

Vector v = new RandomAccessSparseVector(FEATURES);
bias.addToVector(null,1,v);
lines.addToVector(null,lineCount/30,v);
logLines.addToVector(null,Math.log(linecount+1),v);
for(String word:Words.elementSet()){ 
    encoder.addToVector(word,Math.log(1+Words.count(word)),v); 
}

        在上述代码中，bias的值始终是1，学习算法利用该值作为阈值，这个值使得Logstic回归算法得以顺利进行，对于行数（LinCount）来说，除以30可以将该数量压缩到和其他变量一致的区间，可以加快学习进程。文档主体的编码中每个单词的权重进行了频率的对数转换而不是直接使用频率，这一点是考虑到单词在单篇文章中出现多次的频率要比单词出现的预期整体频率高，所以采用对数频率作为单词的权重。
        在训练分类器前，还需要定义一个指标，用于衡量分类器的准确度，这里采用对数似然值和正确分类的平均比例来进行衡量，进行计算的代码如下。

double mu = Math.min(k+1,200);
double ll = learningAlgorithm.logLikelihood(actual,v);
averageLL = averageLL+(ll-averageLL)/mu;
Vector p = new DenseVector(20);
learningAlgorithm.classifyFull(p,v);
int estimated = p.maxValueIndex();
int correct = (estimated == actual?1:0);
averageCorrect = averageCorrect + (correct - averageCorrect)/mu; 

        在上述代码中，计算的对数似然值的均值存放在变量averageLL中，然后利用比例最高的新闻组确定变量estimated，并与正确的值进行比较。对比较结果取均值，得出正确结果的平均百分比，存变量averageCorrect中。
        有了上述工具和向量后就可以开始训练SGD模型了，下面代码描述了使用变步长方式的训练模型，使得训练器可在逐渐变长的时间间隔上输出进度反馈。

learningAlgorithm.train(actual,v);
k++;
int bump = bumps[(int)Math.floor(step)%bumps.length];
int scale = (int)Math.pow(10,Math.floor(Step/bumps.length));
if(k%(bump*scale)==0){
    step+=0.25;
    System.out.printf("%10d %10.3f %10.3f %10.2f %s %s
",k,ll,averageLL,averagecorrect*100,ng,newsGroups.values().get(estimated));
}
learningAlgorithm.close();

        样本数量每次达到bump*scale时，都会输出一行学习算法当前状态的语句。随着学习的不断进行，状态报告的频率会逐步递减，也就是说，准确性的变化越快，状态更新越频繁。

至此，Mahout机器学习算法就介绍完成！