3.
决策树算法(Microsoft
Decision Trees Algorithm)
a.
目的：
决策树算法是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
b.
原理：
决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。
简而言之，Microsoft 的决策树算法是由 Microsoft SQL Server Analysis Services 提供的分类和回归算法，用于对离散和连续属性进行预测&##24615;建模。
对于离散属性，该算法根据数据集中输入列之间的关系进行预测。 它使用这些列的值（也称之为状态）预测指定为可预测的列的状态。具体地说，该算法标识与可预测列相关的输入列。 例如，在预测哪些客户可能购买自行车的方案中，假如在十名年轻客户中有九名购买了自行车，但在十名年龄较大的客户中只有两名购买了自行车，则该算法从中推断出年龄是自行车购买情况的最佳预测因子。 决策树根据朝向特定结果发展的趋势进行预测。
对于连续属性，该算法使用线性回归确定决策树的拆分位置。
如果将多个列设置为可预测列，或输入数据中包含设置为可预测的嵌套表，则该算法将为每个可预测列生成一个单独的决策树。
c.
方法：
Microsoft 决策树算法通过在树中创建一系列拆分来生成数据挖掘模型。 这些拆分以“节点”来表示。 每当发现输入列与可预测列密切相关时，该算法便会向该模型中添加一个节点。 该算法确定拆分的方式不同，主要取决于它预测的是连续列还是离散列。
Microsoft 决策树算法使用“功能选择”来指导如何选择最有用的属性。 所有 Analysis Services 数据挖掘算法均使用功能选择来改善分析的性能和质量。 功能选择对防止不重要的属性占用处理器时间意义重大。 如果在设计数据挖掘模型时使用过多的输入或可预测属性，则可能需要很长的时间来处理该模型，甚至导致内存不足。 用于确定是否拆分树的方法包括“平均信息量”和 Bayesian 网络的行业标准度量。
数据挖掘模型中的常见问题是该模型对定型数据中的细微差异过于敏感，这种情况称为“过度拟合”或“过度定型”。 过度拟合模型无法推广到其他数据集。 为避免模型对任何特定的数据集过度拟合，Microsoft 决策树算法使用一些技术来控制树的生长。
Microsoft 决策树算法使用不同的方法来计算最佳的树。 所使用的方法具体取决于任务，任务可为线性回归、分类或关联分析。 一个模型可包含多个针对不同可预测属性的树。 而且，每个树可包含多个分支，具体取决于数据中包含的属性和值的数量。 特定模型中生成的树的形状和深度取决于所使用的计分方法以及其他参数。 参数更改还会影响节点的拆分位置。
总之，Microsoft 决策树算法是一种混合算法，它综合了多种不同的创建树的方法，并支持多种分析任务，包括回归、分类以及关联。Microsoft 决策树算法支持对离散属性和连续属性进行建模。
下面对离散列和连续列的预测再做进一步的说明。
i. 预测离散列
通过柱状图可以演示 Microsoft 决策树算法为可预测的离散列生成树的方式。 下面的关系图显示了一个根据输入列 Age 绘出可预测列 Bike Buyers 的柱状图。 该柱状图显示了客户的年龄可帮助判断该客户是否将会购买自行车。
该关系图中显示的关联将会使 Microsoft 决策树算法在模型中创建一个新节点。
随着算法不断向模型中添加新节点，便形成了树结构。 该树的顶端节点描述了客户总体可预测列的分解。 随着模型的不断增大，该算法将考虑所有列。
ii. 预测连续列
当 Microsoft 决策树算法根据可预测的连续列生成树时，每个节点都包含一个回归公式。 拆分出现在回归公式的每个非线性点处。 例如，请看下面的关系图。
该关系图包含可通过使用一条或两条连线建模的数据。 不过，一条连线将使得模型表示数据的效果较差。 相反，如果使用两条连线，则模型可以更精确地逼近数据。 两条连线的相交点是非线性点，并且是决策树模型中的节点将拆分的点。 例如，与上图中的非线性点相对应的节点可以由以下关系图表示。 两个等式表示两条连线的回归等式。
d.
数据要求
一个决策树模型必须包含一个键列、若干输入列和至少一个可预测列：
· 单个key列 - 每个模型都必须包含一个用于唯一标识每条记录的数值列或文本列。 不允许复合键。
· 输入列 - 需要输入列，可为离散型或连续型。 增加输入属性的数目会影响处理时间。
· 可预测列 - 至少需要一个可预测列。 可以在模型中包括多个可预测属性，并且这些可预测属性的类型可以不同，可以是数值型或离散型。 不过，增加可预测属性的数目可导致处理时间增加。
e.
查看模型
若要浏览该模型，可以使用“Microsoft Tree Viewer”。 如果模型生成多个树，则可以选择其中一个树，然后该查看器即会显示对于每个可预测属性，这些事例分类方式的明细。 还可以使用依赖关系网络(Dependency Network)查看器来查看这些树的交互。
f.
预测
处理过模型之后，结果将以一组模式和统计信息的形式存储，可以使用这些结果来研究关系或作出预测。
g.
自定义参数与性能优化
i. 设置算法参数
1.
COMPLEXITY_PENALTY
控制决策树的增长。 值越小，则分叉数越多；值越大，则分叉数越少。 默认值基于特定模型的属性数，详见以下列表：
·
对于 1 到 9 个属性，默认值为 0.5。
·
对于 10 到 99 个属性，默认值为 0.9。
·
对于 100 或更多个属性，默认值为 0.99。
2.
FORCE_REGRESSOR
强制算法将指定的列用作回归量，而不考虑算法计算出的列的重要性。 此参数只用于预测连续属性的决策树。通过设置此参数，您可以强制要求算法尝试将属性用作回归量。 但是，属性实际是否会在最终模型中用作回归量取决于分析结果。 您可以通过查询模型内容来确定用作了回归量的列。仅可用于某些版本的 SQL Server
3.
MAXIMUM_INPUT_ATTRIBUTES
定义算法在调用功能选择之前可以处理的输入属性数。
默认值为 255。
如果将此值设置为 0，则表示关闭功能选择。
[仅可用于某些版本的 SQL Server]
4.
MAXIMUM_OUTPUT_ATTRIBUTES
定义算法在调用功能选择之前可以处理的输出属性数。
默认值为 255。
如果将此值设置为 0，则表示关闭功能选择。
[仅可用于某些版本的 SQL Server]
5.
MINIMUM_SUPPORT
确定在决策树中生成拆分所需的叶事例的最少数量。
默认值为 10。
如果数据集非常大，则可能需要增大此值，以避免过度定型。
6.
SCORE_METHOD
确定用于计算拆分分数的方法。 可用选项包括：
1 = Entropy
3 = Bayesian with K2 Prior
4 = Bayesian Dirichlet Equivalent (BDE)
with uniform prior
7.
SPLIT_METHOD
确定用于拆分节点的方法。 可用选项如下：
1 = Binary: 指示无论属性值的实际数量是多少，树都拆分为两个分支
2 = Complete: 指示树可以创建与属性值数目相同的分叉
3 = Both: 指定 Analysis Services 可确定应使用 binary 还是 complete，以获得最佳结果 （默认）
ii. 建模标志
Microsoft 决策树算法支持下列建模标志。 创建挖掘结构或挖掘模型时，可定义建模标志以指定分析期间如何处理每列中的值。
1.
MODEL_EXISTENCE_ONLY
表示该列将被视为具有两个可能状态：Missing 和 Existing。 Null 表示缺失值。适用于挖掘模型列
2.
NOT NULL
指示该列不能包含 Null。 如果 Analysis Services 在模型定型过程中遇到 Null 值，则会导致错误。适用于挖掘结构列。
iii. 决策树模型中的回归量
即使不使用 Microsoft 线性回归算法，所有其输入和输出均为连续数值的决策树模型都可能会包含表示连续属性的回归的节点。
您无需指定连续数值数据列表示回归量。 即使不对列设置 REGRESSOR 标志，Microsoft 决策树算法也会自动将列用作潜在回归量，并会将数据集分区成具有一定意义的模式的区域。
您可以使用 FORCE_REGRESSOR 参数来确保算法将使用某一特定回归量。 此参数只可用于 Microsoft 决策树算法和 Microsoft 线性回归算法。 设置建模标志时，算法会尝试查找具有 a*C1 + b*C2 + ... 形式的回归公式，以拟合树中节点的模式。 将对剩余的总和进行计算，如果偏差过大，则在树中执行强制拆分。
例如，如果要将 Income 用作属性来预测客户的购买行为，并对列设置 REGRESSOR 建模标志，则算法将会先通过使用标准回归公式来尝试拟合 Income 值。如果偏差过大，则会放弃回归公式，并根据其他属性对树进行拆分。 拆分完毕后，决策树算法将尝试拟合每个分支中的 Income 的回归量。
h.
应用
Adventure Works Cycles 公司的市场部希望标识以前的客户的某些特征，这些特征可能指示这些客户将来是否有可能购买其产品。AdventureWorks2012 数据库存储描述其以前客户的人口统计信息。 通过使用 Microsoft 决策树算法分析这些信息，市场部可以生成一个模型，该模型根据有关特定客户的已知列的状态（如人口统计或以前的购买模式）预测该客户是否会购买产品。
