spark机器算法从入门到实战

第1章 机器学习概述

1.1 机器学习是啥？

  机器学习(Machine Learning, ML)是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。
  即通过算法使计算机能够模拟人类的判别能力。

1.2 机器学习能干啥？

1.3 机器学习有啥？

1.4 机器学习怎么用？

第2章 机器学习的相关概念

2.1 数据集

  一组数据的集合被称作数据集，用于模型训练的数据集叫训练集，用于测试的数据集叫测试集。一个数据集包含多条数据，一条数据包含多个属性。
  

2.2 泛化能力

  是指机器学习通过训练集进行模型的训练之后对未知的输入的准确判断能力。

2.3 过拟合和欠拟合

  过拟合是指在利用训练数据进行模型训练的时候，模型过多的依赖训练数据中过多的特征属性。欠拟合是指没有通过训练集达到识别的能力。
  

2.4 维度、特征

  对于西瓜数据集，色泽、根蒂、敲声就是维度，也叫特征值。
  

2.5 模型

  模型就是复杂的数学相关函数，只是该函数具有很多的未知的参数，通过训练集训练来确定模型中的参数，生成的已知参数的函数就是模型。就是一种映射。

2.6 学习

  学习就是根据业务数据构建模型的过程。
  机器学习分为有监督学习和无监督学习，有监督学习是指训练集中有明确的标记，如下数据集：各种特征的西瓜是不是好瓜，有明确的标记。分类就是典型的有监督学习。
  无监督学习是指训练集中没有明确的标记，聚类就是典型的无监督学习。

第3章 算法常用指标

3.1 精确率和召回率

  考虑一个二分问题，即将实例分成正类（positive）或负类（negative）。对一个二分问题来说，会出现四种情况。如果一个实例是正类并且也被预测成正类，即为真正类（True positive），如果实例是负类被预测成正类，称之为假正类（False positive）。相应地，如果实例是负类被预测成负类，称之为真负类（True negative），正类被预测成负类则为假负类（false negative）。
  TP：正确肯定的数目
  FN：漏报，没有正确找到的匹配的数目
  FP：误报，给出的匹配是不正确的
  TN：正确拒绝的非匹配对数
  列联表如下表所示，1 代表正类，0 代表负类：
  
  
  精确率（正确率）和召回率是广泛用于信息检索和统计学分类领域的两个度量值，用来评价结果的质量。其中精度是检索出相关文档数与检索出的文档总数的比率，衡量的是检索系统的查准率；召回率是指检索出的相关文档数和文档库中所有的相关文档数的比率，衡量的是检索系统的查全率。
  一般来说，Precision 就是检索出来的条目（比如：文档、网页等）有多少是准确的，Recall 就是所有准确的条目有多少被检索出来了，两者的定义分别如下：
  Precision = 提取出的正确信息条数 / 提取出的信息条数
  Recall = 提取出的正确信息条数 / 样本中的信息条数
  为了能够评价不同算法的优劣，在 Precision 和 Recall 的基础上提出了 F1 值的概念，来对 Precision 和 Recall 进行整体评价。F1 的定义如下：
  F1值 = 正确率 * 召回率 * 2 / (正确率 + 召回率)
  

不妨举这样一个例子：

某池塘有 1400 条鲤鱼，300 只虾，300 只鳖。现在以捕鲤鱼为目的。撒一大网，逮着了 700 条鲤鱼，200 只虾，100 只鳖。那么，这些指标分别如下：
　　正确率 = 700 / (700 + 200 + 100) = 70%
　　召回率 = 700 / 1400 = 50%
　　F1值 = 70% * 50% * 2 / (70% + 50%) = 58.3%
不妨看看如果把池子里的所有的鲤鱼、虾和鳖都一网打尽，这些指标又有何变化：
　　正确率 = 1400 / (1400 + 300 + 300) = 70%
　　召回率 = 1400 / 1400 = 100%
　　F1值 = 70% * 100% * 2 / (70% + 100%) = 82.35%

  由此可见，正确率是评估捕获的成果中目标成果所占得比例；召回率，顾名思义，就是从关注领域中，召回目标类别的比例；而 F1 值，则是综合这二者指标的评估指标，用于综合反映整体的指标。
  当然希望检索结果 Precision 越高越好，同时 Recall 也越高越好，但事实上这两者在某些情况下有矛盾的。比如极端情况下，我们只搜索出了一个结果，且是准确的，那么 Precision 就是 100%，但是 Recall 就很低；而如果我们把所有结果都返回，那么比如 Recall 是 100%，但是 Precision 就会很低。因此在不同的场合中需要自己判断希望 Precision 比较高或是 Recall 比较高。如果是做实验研究，可以绘制 Precision-Recall 曲线来帮助分析。

3.2 TPR、FPR & TNR

引入两个新名词。
其一是真正类率(true positive rate, TPR)，计算公式为：
  TPR = TP / (TP + FN)
刻画的是分类器所识别出的正实例占所有正实例的比例。
另一个是负正类率(false positive rate, FPR)，计算公式为：
  FPR = FP / (FP + TN)
计算的是分类器错认为正类的负实例占所有负实例的比例。
还有一个真负类率(True Negative Rate, TNR)，也称为 specificity，计算公式为:
  TNR = TN /(FP + TN) = 1 - FPR

3.3 综合评价指标 F-measure

  Precision 和 Recall 指标有时候会出现的矛盾的情况，这样就需要综合考虑他们，最常见的方法就是 F-Measure（又称 为F-Score）。
  F-Measure 是 Precision 和 Recall 加权调和平均：
  
  当参数 α=1 时，就是最常见的 F1。因此，F1 综合了 P 和 R 的结果，当 F1 较高时则能说明试验方法比较有效。

3.4 其他一些评估参数

3.5 ROC 曲线、AUC

3.5.1为什么引入 ROC 曲线？

  原因一：在一个二分类模型中，对于所得到的连续结果，假设已确定一个阀值，比如说 0.6，大于这个值的实例划归为正类，小于这个值则划到负类中。如果减小阀值，减到 0.5，固然能识别出更多的正类，也就是提高了识别出的正例占所有正例 的比类，即 TPR，但同时也将更多的负实例当作了正实例，即提高了 FPR。为了形象化这一变化，引入 ROC，ROC 曲线可以用于评价一个分类器。
  原因二：在类不平衡的情况下，如正样本 90 个，负样本 10 个，直接把所有样本分类为正样本，得到识别率为 90%。但这显然是没有意义的。单纯根据 Precision 和 Recall 来衡量算法的优劣已经不能表征这种病态问题。

3.5.2什么是 ROC 曲线？

  ROC（Receiver Operating Characteristic）翻译为 “接受者操作特性曲线”。曲线由两个变量 1-specificity 和 Sensitivity 绘制。1-specificity=FPR，即负正类率。Sensitivity 即是真正类率，TPR(True positive rate)，反映了正类覆盖程度。这个组合以 1-specificity 对 sensitivity，即是以代价 (costs) 对收益 (benefits)。
  此外，ROC 曲线还可以用来计算 “均值平均精度”（mean average precision），这是当你通过改变阈值来选择最好的结果时所得到的平均精度（PPV）。
  为了更好地理解 ROC 曲线，我们使用具体的实例来说明：
  如在医学诊断中，判断有病的样本。那么尽量把有病的揪出来是主要任务，也就是第一个指标 TPR，要越高越好。而把没病的样本误诊为有病的，也就是第二个指标 FPR，要越低越好。
  不难发现，这两个指标之间是相互制约的。如果某个医生对于有病的症状比较敏感，稍微的小症状都判断为有病，那么他的第一个指标应该会很高，但是第二个指标也就相应地变高。最极端的情况下，他把所有的样本都看做有病，那么第一个指标达到1，第二个指标也为1。
  我们以 FPR 为横轴，TPR 为纵轴，得到如下 ROC 空间。
  我们可以看出，左上角的点 (TPR=1,FPR=0) 为完美分类，也就是这个医生医术高明，诊断全对。点 A(TPR>FPR)，医生A的判断大体是正确的。中线上的点 B(TPR=FPR)，也就是医生B全都是蒙的，蒙对一半，蒙错一半。下半平面的点 C(TPR<FPR)，这个医生说你有病，那么你很可能没有病，医生C的话我们要反着听，为真庸医。上图中一个阈值，得到一个点。现在我们需要一个独立于阈值的评价指标来衡量这个医生的医术如何，也就是遍历所有的阈值，得到 ROC 曲线。
  还是一开始的那幅图，假设如下就是某个医生的诊断统计图，直线代表阈值。我们遍历所有的阈值，能够在 ROC 平面上得到如下的 ROC 曲线。
  
  曲线距离左上角越近，证明分类器效果越好。
  
  如上，是三条 ROC 曲线，在 0.23 处取一条直线。那么，在同样的低 FPR=0.23 的情况下，红色分类器得到更高的 PTR。也就表明，ROC 越往上，分类器效果越好。我们用一个标量值 AUC 来量化它。

3.5.3什么是 AUC？

  AUC 值为 ROC 曲线所覆盖的区域面积,显然，AUC 越大，分类器分类效果越好。
  AUC = 1，是完美分类器，采用这个预测模型时，不管设定什么阈值都能得出完美预测。绝大多数预测的场合，不存在完美分类器。
  0.5 < AUC < 1，优于随机猜测。这个分类器（模型）妥善设定阈值的话，能有预测价值。
  AUC = 0.5，跟随机猜测一样（例：丢铜板），模型没有预测价值。
  AUC < 0.5，比随机猜测还差；但只要总是反预测而行，就优于随机猜测。
  AUC 的物理意义：假设分类器的输出是样本属于正类的 socre（置信度），则 AUC 的物理意义为，任取一对（正、负）样本，正样本的 score 大于负样本的 score 的概率。

3.5.4 怎样计算 AUC？

  第一种方法：AUC 为 ROC 曲线下的面积，那我们直接计算面积可得。面积为一个个小的梯形面积之和。计算的精度与阈值的精度有关。
  第二种方法：根据 AUC 的物理意义，我们计算正样本 score 大于负样本的 score 的概率。取 N*M(N为正样本数,M为负样本数)个二元组，比较 score，最后得到 AUC。时间复杂度为 O(N*M)。
  第三种方法：与第二种方法相似，直接计算正样本 score 大于负样本的概率。我们首先把所有样本按照 score 排序，依次用 rank 表示他们，如最大 score 的样本，rank=n(n=N+M)，其次为 n-1。那么对于正样本中 rank 最大的样本 rank_max，有 M-1 个其他正样本比他 score 小，那么就有(rank_max-1)-(M-1)个负样本比他 score 小。其次为 (rank_second-1)-(M-2)。最后我们得到正样本大于负样本的概率，时间复杂度为 O(N+M)。
  MSE:Mean Squared Error
  均方误差：是指参数估计值与参数真值之差平方的期望值。
  MSE 可以评价数据的变化程度，MSE 的值越小，说明预测模型描述实验数据具有更好的精确度。
  
  RMSE
  均方误差：均方根误差是均方误差的算术平方根。
  
  MAE:Mean Absolute Error
  平均绝对误差：是绝对误差的平均值。
  平均绝对误差能更好地反映预测值误差的实际情况。
  
  fi 表示预测值，yi 表示真实值。
  SD:standard Deviation
  标准差：标准差是方差的算术平方根。标准差能反映一个数据集的离散程度。平均数相同的两组组数据，标准差未必相同。
  

3.6 Spark MLlib 是啥？

机器学习之常见应用框架

Spark MLlib

第4章 凸优化算法

不严格的说，凸优化就是在标准优化问题的范畴内，要求目标函数和约束函数是凸函数的一类优化问题。

注意：中国大陆数学界某些机构关于函数凹凸性定义和国外的定义是相反的。Convex Function 在某些中国大陆的数学书中指凹函数。Concave Function 指凸函数。但在中国大陆涉及经济学的很多书中，凹凸性的提法和其他国家的提法是一致的，也就是和数学教材是反的。举个例子，同济大学高等数学教材对函数的凹凸性定义与本条目相反，本条目的凹凸性是指其上方图是凹集或凸集，而同济大学高等数学教材则是指其下方图是凹集或凸集，两者定义正好相反。

4.1 梯度下降

4.2 牛顿法

4.3 拟牛顿法

4.4 BFGS 算法

第5章 L1、L2 正则化

5.1 从经验风险最小化到结构经验最小化

5.2 范数与正则项

5.3 贝叶斯先验

第6章 线性回归算法

6.1 数学模型

  线性回归是利用被称为线性回归方程的最小平方函数对一个或者多个自变量和因变量之间关系进行建模的一种回归分析。这种函数式一个或者多个被称为回归系数的模型参数的线性组合。
  在统计学中，线性回归(Linear Regression) 是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合。
  回归分析中，只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。

6.2 线性回归的应用

  通过大量样本的试验学习到线性函数，然后根据新的样本的特征数据，预测结果。

6.2 Spark MLlib 实现

示例代码：

package com.atguigu.mllib

import org.apache.log4j.{Level, Logger}
import org.apache.spark.mllib.regression.{LinearRegressionModel, LinearRegressionWithSGD}
import org.apache.spark.mllib.util.MLUtils
import org.apache.spark.{SparkConf, SparkContext}

object LinearRegression {

  def main(args: Array[String]): Unit = {

    // 屏蔽日志
    Logger.getLogger("org.apache.spark").setLevel(Level.ERROR)
    Logger.getLogger("org.eclipse.jetty.server").setLevel(Level.OFF)

    // 创建 SparkContext
    val conf = new SparkConf().setMaster("local[4]").setAppName("LinearRegression")
    val sc = new SparkContext(conf)

    // 加载数据样本
    val path = "D:\learn\JetBrains\workspace_idea\spark\doc\data.txt";

    // 通过提供的工具类加载样本文件
    val data = MLUtils.loadLibSVMFile(sc, path).cache()

    // 或者通过 RDD 转换加载
    /*
    val data = sc.textFile(path).map { line =>
      val parts = line.split(' ')
      LabeledPoint(parts(0).toDouble, Vectors.dense(parts.tail.map(_.split(":")(1).toDouble)))
    }.cache()
    */

    // 迭代次数
    val numIterations = 100
    // 梯度下降步长
    val stepSize = 0.00000001
    // 训练模型
    val model = LinearRegressionWithSGD.train(data, numIterations, stepSize)

    // 模型评估
    val valuesAndPreds = data.map { point =>
      // 根据模型预测 Label 值
      val prediction = model.predict(point.features)
      println(s"【真实值】：${point.label}      ;【预测值】：${prediction}")
      (point.label, prediction)
    }

    // 求均方误差
    val MSE = valuesAndPreds.map { case (v, p) => math.pow((v - p), 2) }.mean()
    println("训练模型的均方误差为 = " + MSE)

    // 保存模型
    model.save(sc, "target/tmp/scalaLinearRegressionWithSGDModel")
    // 重新加载模型
    val sameModel = LinearRegressionModel.load(sc, "target/tmp/scalaLinearRegressionWithSGDModel")

    sc.stop()
  }
}

输出结果如下：

【真实值】：-9.490009878824548      ;【预测值】：7.708618803157486E-9
【真实值】：-1.1838791995691869      ;【预测值】：1.1953486679306154E-8
【真实值】：0.2577820163584905      ;【预测值】：-2.460347544748461E-9
【真实值】：-1.5856680515554806      ;【预测值】：1.43032697303707E-8
【真实值】：-13.039928064104615      ;【预测值】：-2.909264331661566E-10
【真实值】：-4.438869807456516      ;【预测值】：-4.3817348405900043E-10
【真实值】：-17.428674570939506      ;【预测值】：7.864237801670372E-9
【真实值】：-19.782762789614537      ;【预测值】：2.749919462104237E-9
......
......
训练模型的均方误差为 = 106.31223022762704

第7章 FPGrowth 关联规则算法

7.1算法思想

  FPGrowth 算法通过构造一个 FPTree 树结构来压缩数据记录，使得挖掘频繁项集只需要扫描两次数据记录，而且该算法不需要生成候选集合，所以效率会比较高。如何从购物篮里面发现 尿布+啤酒 的最佳组合。 >   我们以以下数据集为例：
  
  注意：牛奶、面包叫做项，{ 牛奶、面包 } 叫做项集。项集出现的次数叫做支持度。T* 表示用户每次的购物清单。
  FPGrowth挖掘过程如下图所示：
  

7.2 Spark MLlib 实现

示例代码如下：

package com.atguigu.mllib

import org.apache.log4j.{Level, Logger}
import org.apache.spark.{SparkConf, SparkContext}
import org.apache.spark.mllib.fpm.FPGrowth

object FPGrowth extends App {

  // 屏蔽日志
  Logger.getLogger("org.apache.spark").setLevel(Level.ERROR)
  Logger.getLogger("org.eclipse.jetty.server").setLevel(Level.OFF)

  // 创建 SparkContext
  val conf = new SparkConf().setMaster("local[4]").setAppName("FPGrowth")
  val sc = new SparkContext(conf)

  // 加载数据样本
  val path = "D:\learn\JetBrains\workspace_idea\spark\doc\fpgrowth.txt";
  // 创建交易样本
  val transactions = sc.textFile(path).map(_.split(" ")).cache()

  println(s"交易样本的数量为： ${transactions.count()}")

  // 最小支持度 [0,1]
  val minSupport = 0.4

  // 计算的并行度
  val numPartition = 2

  // 训练模型
  val model = new FPGrowth()
    .setMinSupport(minSupport)
    .setNumPartitions(numPartition)
    .run(transactions)

  // 打印模型结果
  println(s"经常一起购买的物品集的数量为： ${model.freqItemsets.count()}")
  model.freqItemsets.collect().foreach { itemset =>
    println(itemset.items.mkString("[", ",", "]") + ", " + itemset.freq)
  }

  sc.stop()
}

输出结果如下：

交易样本的数量为： 6
经常一起购买的物品集的数量为： 18
[t], 3
[t,x], 3
[t,x,z], 3
[t,z], 3
[s], 3
[s,x], 3
[z], 5
[y], 3
[y,t], 3
[y,t,x], 3
[y,t,x,z], 3
[y,t,z], 3
[y,x], 3
[y,x,z], 3
[y,z], 3
[x], 4
[x,z], 3
[r], 3

第8章 协同过滤推荐算法

8.1 算法思想

  比如你想看一个电影，但是不知道具体看哪一部，你会怎么做？有两种办法，一种是问问周围兴趣相似的朋友，看看他们最近有什么好的电影推荐。另外一种是看看电影的相似程度，比如都喜欢看僵尸片，那就会找电影名带有僵尸、丧尸之类的电影。
  协同过滤算法就是基于上面的思想，主要包含基于用户的协同过滤推荐算法以及基于物品的协同过滤推荐算法。
  实现协同过滤，一般需要几个步骤：
  1、收集用户偏好。
  2、找到相似的用户或者物品。
  3、计算推荐。

  协同过滤算法主要用于推荐系统，推荐系统是信息过载所采用的措施，面对海量的数据信息，从中快速推荐出符合用户特点的物品。一些人的“选择恐惧症”、没有明确需求的人。
  • 解决如何从大量信息中找到自己感兴趣的信息。
  • 解决如何让自己生产的信息脱颖而出，受到大众的喜爱。
  

8.2 相似性度量

8.3 Spark MLlib 实现

推荐数据的准备

协同过滤推荐架构

示例代码如下：

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// scalastyle:off println
package com.spark.mllib

import org.apache.log4j.{Level, Logger}
import org.apache.spark.{SparkConf, SparkContext}

import org.apache.spark.mllib.recommendation.ALS
import org.apache.spark.mllib.recommendation.MatrixFactorizationModel
import org.apache.spark.mllib.recommendation.Rating

object Recommendation {
  def main(args: Array[String]): Unit = {

    // 屏蔽日志
    Logger.getLogger("org.apache.spark").setLevel(Level.ERROR)
    Logger.getLogger("org.eclipse.jetty.server").setLevel(Level.OFF)

    // 创建 SparkContext
    val conf = new SparkConf().setMaster("local[4]").setAppName("CollaborativeFiltering")
    val sc = new SparkContext(conf)

    // 加载数据
    val path = "D:\learn\JetBrains\workspace_idea\spark\doc\test.data"
    val data = sc.textFile(path)
    val ratings = data.map(_.split(',') match { case Array(user, item, rate) =>
      Rating(user.toInt, item.toInt, rate.toDouble)
    })

    // 训练模型
    val rank = 50
    val numIterations = 10
    val model = ALS.train(ratings, rank, numIterations, 0.01)

    // 准备用户数据
    val usersProducts = ratings.map { case Rating(user, product, rate) =>
      (user, product)
    }

    // 生成推荐结果
    val predictions =
      model.predict(usersProducts).map { case Rating(user, product, rate) =>
        ((user, product), rate)
      }

    // 对比结果
    val ratesAndPreds = ratings.map { case Rating(user, product, rate) =>
      ((user, product), rate)
    }.join(predictions)

    // 生成均方误差
    val MSE = ratesAndPreds.map { case ((user, product), (r1, r2)) =>
      println(s"【用户】：${user}  【物品】：${product}  【真实值】：${r1}  【预测值】：${r2}")
      val err = (r1 - r2)
      err * err
    }.mean()

    println("预测的均方误差为 = " + MSE)

    // 保存模型
    model.save(sc, "target/tmp/myCollaborativeFilter")
    // 加载模型
    val sameModel = MatrixFactorizationModel.load(sc, "target/tmp/myCollaborativeFilter")

    sc.stop()
  }
}

输出结果如下：

【用户】：4  【物品】：4  【真实值】：5.0  【预测值】：4.996434384228974
【用户】：2  【物品】：1  【真实值】：5.0  【预测值】：4.9967879248395715
【用户】：1  【物品】：1  【真实值】：5.0  【预测值】：4.9967879248395715
【用户】：4  【物品】：2  【真实值】：5.0  【预测值】：4.996434384228974
【用户】：1  【物品】：4  【真实值】：1.0  【预测值】：1.0001174801070112
【用户】：4  【物品】：1  【真实值】：1.0  【预测值】：1.0001881676270354
【用户】：2  【物品】：2  【真实值】：1.0  【预测值】：1.0001174801070112
【用户】：3  【物品】：1  【真实值】：1.0  【预测值】：1.0001881676270354
【用户】：2  【物品】：4  【真实值】：1.0  【预测值】：1.0001174801070112
【用户】：3  【物品】：4  【真实值】：5.0  【预测值】：4.996434384228974
【用户】：2  【物品】：3  【真实值】：5.0  【预测值】：4.9967879248395715
【用户】：3  【物品】：2  【真实值】：5.0  【预测值】：4.996434384228974
【用户】：1  【物品】：2  【真实值】：1.0  【预测值】：1.0001174801070112
【用户】：3  【物品】：3  【真实值】：1.0  【预测值】：1.0001881676270354
【用户】：4  【物品】：3  【真实值】：1.0  【预测值】：1.0001881676270354
【用户】：1  【物品】：3  【真实值】：5.0  【预测值】：4.9967879248395715
预测的均方误差为 = 5.7700628235600924E-6

第9章 决策树

9.1 算法思想

  决策树（Decision Tree）是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。相比朴素贝叶斯分类，决策树的优势在于构造过程不需要任何领域知识或参数设置，因此在实际应用中，对于探测式的知识发现，决策树更加适用。
  分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
  分类的时候，从根节点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；此时，每一个子结点对应着该特征的一个取值。如此递归向下移动，直至达到叶结点，最后将实例分配到叶结点的类中。
  举一个通俗的例子，各位立志于脱单的单身男女在找对象的时候就已经完完全全使用了决策树的思想。假设一位母亲在给女儿介绍对象时，有这么一段对话：
  母亲：给你介绍个对象。
  女儿：年纪多大了？
  母亲：26。
  女儿：长的帅不帅？
  母亲：挺帅的。
  女儿：收入高不？
  母亲：不算很高，中等情况。
  女儿：是公务员不？
  母亲：是，在税务局上班呢。
  女儿：那好，我去见见。
  这个女生的决策过程就是典型的分类决策树。相当于对年龄、外貌、收入和是否公务员等特征将男人分为两个类别：见或者不见。假设这个女生的决策逻辑如下：
  
  上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色结点（内部结点）表示判断条件，橙色结点（叶结点）表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。这幅图基本可以算是一棵决策树，说它 “基本可以算” 是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。

9.2 决策树模型的两种解释

  分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。

9.2.1 决策树与 if-then 规则

  可以将决策树看成一个 if-then 规则的集合。即由决策树的根结点到叶节点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
  决策树的路径或其对应的 if-then 规则集合的重要性质：互斥且完备（每一个实例都被一条路径或一条规则所覆盖，且只被一条路径或一条规则所覆盖，这里的覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件）

9.2.2 决策树与条件概率分布

  决策树还表示给定特征条件下类的条件概率分布，它定义在特征空间的一个划分。将特征空间划分为互不相交的单元，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的每一条路径对应于划分中的一个单元。
  假设 X 为表示特征的随机变量，Y 为表示类的随机变量，那么这个条件概率分布可以表示为 P(X|Y)，各叶结点上的条件概率往往偏向于某一个类，即属于某一类的概率越大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

9.3 特征选择

9.4 Spark MLlib 实现

示例代码如下：

package com.atguigu.mllib

import org.apache.log4j.{Level, Logger}
import org.apache.spark.{SparkConf, SparkContext}
import org.apache.spark.mllib.tree.DecisionTree
import org.apache.spark.mllib.tree.model.DecisionTreeModel
import org.apache.spark.mllib.util.MLUtils


object DecisionTreeApp extends App {
  // 屏蔽日志
  Logger.getLogger("org.apache.spark").setLevel(Level.ERROR)
  Logger.getLogger("org.eclipse.jetty.server").setLevel(Level.OFF)

  // 创建 SparkContext
  val conf = new SparkConf().setMaster("local[4]").setAppName("DecisionTree")
  val sc = new SparkContext(conf)

  val path = "D:\learn\JetBrains\workspace_idea\spark\sparkmllib_decision_tree\src\main\resources\data.txt"
  // 加载数据文件
  val data = MLUtils.loadLibSVMFile(sc, path)
  // 将数据集切分为 70% 的训练数据集和 30% 的测试数据集
  val splits = data.randomSplit(Array(0.7, 0.3))
  val (trainingData, testData) = (splits(0), splits(1))

  // 训练决策树模型
  // Empty categoricalFeaturesInfo indicates all features are continuous.
  val numClasses = 2
  val categoricalFeaturesInfo = Map[Int, Int]()
  val impurity = "gini"
  val maxDepth = 5
  val maxBins = 32

  val model = DecisionTree.trainClassifier(trainingData, numClasses, categoricalFeaturesInfo,
    impurity, maxDepth, maxBins)

  // 评估模型
  val labelAndPreds = testData.map { point =>
    val prediction = model.predict(point.features)
    (point.label, prediction)
  }

  val testErr = labelAndPreds.filter(r => r._1 != r._2).count().toDouble / testData.count()
  println("分类错误度 = " + testErr)
  println("训练的决策树模型:
" + model.toDebugString)

  // 保存决策树模型
  model.save(sc, "target/tmp/myDecisionTreeClassificationModel")
  // 重新读取决策树模型
  val sameModel = DecisionTreeModel.load(sc, "target/tmp/myDecisionTreeClassificationModel")

  sc.stop()
}

输出结果如下：

分类错误度 = 0.06896551724137931
训练的决策树模型:
DecisionTreeModel classifier of depth 2 with 5 nodes
  If (feature 406 <= 20.0)
   If (feature 99 <= 0.0)
    Predict: 0.0
   Else (feature 99 > 0.0)
    Predict: 1.0
  Else (feature 406 > 20.0)
   Predict: 1.0

第10章 随机森林算法