数学建模的数据挖掘方法.ppt

第四章分类 分类 Classification 就是通过学习得到一个目标函数 称为模型函数 f 然后把新的对象x通过f映射到一个预先定义的类别号y 1 分类的定义 一 相关概念 2 数据挖掘中分类任务的一般模型 数据集 模型是否合理 2 分类性能的度量 考虑二分类问题即类标号只有2个 可设为1和0 定义 f11 实际为第一类 按模型也判别为第一类 f00 实际为第二类 按模型也判别为第二类 f10 实际为第一类 按模型也判别为第二类 f01 实际为第二类 按模型也判别为第一类 则分类性能可以用准确率或错误率来度量 准确率 f11 f00 f11 f00 f10 f01 准确率 1 准确率 3 常见的分类方法 常见的分类有 决策树 神经网络 支持向量机 遗传算法 粗糙集 贝叶斯等 三 基于决策树的分类方法 例1 下表是用于构造分类模型的数据集 包括14个样本和5个属性 Outlook Temperature Humidity Windy和Play 其中前4个属性是天气 最后一个属性是根据前4个属性的情况说明这样的天气状况是否适合比赛 各属性取值如下 Outlook sunny s overcast o rain r Temperature hot h mild m cool c Humidity high h normal n Windy false truePlay Yes y no n 训练样本集如下 决策树是类似如下的一棵树 Outlook Play no Play yes windy Play yes Play no 给定一个新的天气象 rain hot high true 则判别其类别 决策树的构造 分裂属性的选择 四 基于信息增益的特征选择策略 1 相关概念 设信息源X的取值为A a1 a2 an ai出现的概率为pi 称 I ai log 1 pi logpi 为ai的信息量 称 为X的信息熵 决策树分类方法利用信息量增加 信息增益 作为特征选择的一种指标 信息增益衡量每个属性对分裂后的数据子集的信息量的贡献 假设训练集T包含n个样本 这些样本分别属于m个类 其中第i个类在T中出现的比例为pi 称 为集合T的信息熵 如果m 1 即T的样本都属于一个类 则I T 0 达到最小值 何时 达到最大 假设属性 把集合 划分为 个子集 T1 T2 Tv 其中Ti所包含的样本数为ni 那么划分后的熵就是 分裂后的信息增益定义为 基于信息理论的特征选择方法就是逐一计算每种分裂的信息增益 选择信息增益最大的属性作为分裂属性 下面以前面给出的数据集为例 利用信息增益方法构造决策树 第一步 计算训练样本集 的信息量 分类属性Play有两个类 其样本数统计如下 因此T的信息量为 第二步 计算每个属性的信息增益 对于Outlook属性 它有3个属性值 把样本集T分成3个子集 每个子集的类别统计如下 Outlook的信息熵为 Outlook的信息增益为 同理对于Temperature属性 它也有3个属性值 把样本集T分成3个子集 每个子集的类别统计如下 Temperature的信息熵为 Temperature的信息增益为 对于Humidity属性和Windy属性 统计如下 计算其信息增益值分别为0 1653和0 0481 第三步 比较四个属性的信息增益 按大小顺序排列为 Gain Outlook Gain Humidity Gain Windy Gain Temperature 因此应该选Outlook作为首分裂结点 即决策树的形状为 Outlook 第二层结点的选择与首结点类似 具体选择过程如下 对于 Sunny 的分支 从原数据集T中统计出Outlook属性值为sunny的样本作为新的数据集T 计算T的信息量为 对于Temperature属性 简单统计如下 显然 对于Humidity属性 简单统计如下 显然 因此Sunny分支下的分裂属性可选Temperature或Humidity 若取Humidity 则其属性H和N下的记录都为相同的类 该分支算法结束 其分支结构如下 Humidity Play No Play Yes 若取Temperature 则重新确定记录集如下 Temp Play No Play No 可以看出其三个分支H C和M下的所有记录也属于相同的类 此分支算法结束 其分支结构如右 Play Yes 同理 对于Rain分支 统计数据如下 Windy Play Yes Play No 因此选Windy其分支结构如右 同理 对于Overcast分支 统计数据如下 Play Yes 该分支下所有记录均为同一类 因此该分支算法结束 其结构如下右 综合以上结果 最后得到决策树如下 Outlook Temp Play No Play No Play Yes Windy Play Yes Play No Play Yes 决策树构造好后 给出新的对象便可判别其类别 例如 新的天气对象为 1 Overcast cool high False 2 Rain Mild Normal True 其类别分别为 五 基于数据分布的特征选择策略 除了基于信息增益的特征选择策略外 还可以根据结点的数据类别的分布来选择最优分裂结点 称之为GiniIndex方法 定义 假设训练集T包含n个样本 这些样本分别属于m个类 其中第i个类在T中出现的比例为pi 则T的GiniIndex定义为 假设属性 把集合 划分为 个子集 T1 T2 Tv 其中Ti所包含的样本数为ni 那么这个划分的GiniIndex为 GiniIndex的特征选择方法就是逐一计算按每个属性分裂后的GiniIndex值 选择giniIndex值最小的属性作为分裂属性 下面以前面给出的数据集为例 利用GiniIndex选择策略构造决策树的过程 对总样本进行统计如下 样本集T的giniIndex值为 对于Outlook属性 它有3个属性值 把样本集T分成3个子集 每个子集的类别统计如下 每个子集的GiniIndex值如下 因此属性Outlook的GiniIndex值为 同理对于Temperature属性 它也有3个属性值 把样本集T分成3个子集 每个子集的类别统计如下 因此属性Temperature的GiniIndex值为 对于Humidity属性和Windy属性 统计如下 计算其GiniIndex值分别为0 3674和0 4357 第三步 比较四个属性的GiniIndex值如下 因此应该选Outlook作为首分裂结点 即决策树的形状为 Outlook 第二层结点的选择与首结点类似 具体选择过程如下 对于 Sunny 的分支 从原数据集T中统计出Outlook属性值为sunny的样本作为新的数据集T 对于Temperature属性 简单统计如下 对于Humidity属性 简单统计如下 显然 因此Sunny分支下的分裂属性可选Temperature或Humidity 若取Humidity 则其属性H和N下的记录都为相同的类 该分支算法结束 其分支结构如下 Humidity Play No Play Yes 剩下的计算类似 最后得到决策树如下 Outlook Temp Play No Play No Play Yes Windy Play Yes Play No Play Yes 六 信息增益和GiniIndex值的另一个应用 考虑如下问题 预测贷款申请者是否会按时归还贷款 历史数据如下 对于 年收入 属性 它是连续型变量 按前面决策树的构造方法 应该每个属性都是离散型属性 为此 应该把连续型属性划分成若干个区间 这样把该属性化为离散型属性 简单的 若划分为两个区间 如何划分 可以用信息增益或GiniIndex值方法 步骤如下 把连续型属性值由小到大排列 取每两个值的中间值作为候选划分点 然后计算按各个候选划分点划分的信息增益或GiniIndex值 例如 用GiniIndex值方法如下 对于候选点65 划分后类别统计如下 对于候选点72 划分后类别统计如下 对于候选点80 对于候选点87 对于候选点92 对于候选点97 对于候选点110 对于候选点122 对于候选点172 根据上面的分析 可把 年收入 属性划分成两个区间 0 97 和 97 10000 分别设为属性A1和A2 则原数据集变为 再按前面的方法构造决策树 便可对类似的顾客 否 单身 100K 进行分类判别 七 朴素贝叶斯分类法 1 朴素贝叶斯分类方法描述 设样本集T有n个属性 A1 A2 An 可能的类别有m个 C1 C2 Cm 待分类的样本为x X1 X2 Xn 分别计算条件概率 则条件概率P Ci X 最大所对应的类Ci即为X所在的类 在公式 1 中 计算等式左边的每个条件概率时 右边的分母相同 因此只需要计算分子 然后比较大小即可 各概率的计算如下 另外 用朴素贝叶斯分类时还需假设各属性之间相互独立 此时有 2 条件概率P xj Ci 的估计 条件概率P xj Ci 的估计值分两种情况 情形1 第j个属性Aj为离散型的情况 此时 条件概率P xj Ci 可按如下公式计算 例1 给定训练样本集如下 请用贝叶斯方法判别对象 rain hot high true 的类别 解 分类属性Play有两个类 Play yes C1 和其Play no C2 样本数统计如下 于是P C1 9 14 P C2 5 14 对于Outlook属性 数据汇总如下表 于是各条件概率为 同理对于Temperature属性 它也有3个属性值 把样本集T分成3个子集 每个子集的类别统计如下 于是各条件概率为 对于Humidity属性和Windy属性 统计如下 试计算其 条件概率 对于待分类样本 分别计算以下两个概率 0 333 0 22 0 33 0 3 0 643 0 0053 0 4 0 4 0 8 0 6 0 357 0 0274 因此 为第二类 即不适合比赛 情形2 第j个属性Aj为连续型的情况 属性 年收入 为连续型数据类型 此时如果再用公式 来估计条件概率已不合适 例如 若新样本的 年收入 为110K 则 类似的新样本将无法判别 有两种策略可以用了估计连续型属性的条件概率 1 把连续属性离散化 2 用概率分布来估计条件概率 1 把连续属性离散化 如前面构造决策树的GiniIndex或信息增益方法 把连续属性划分成几个区间 即连续属性离散化 按前面所述 如果把 年收入 划分成两个区间 则最佳的候选划分点为97K 对应区间为 0 97 和 97 10000 通过计算类Ci中属性 年收入 落入对应区间的比例来估计条件概率 即把训练数据集修改为下表 用Bayes方法估计每个条件概率后 对新给出的任何样本都可以判别 2 用概率分布来估计条件概率 假设连续型属性服从某种概率分布 通常假设服从正态分布 然后用训练数据估计出分布的参数 进而计算相应的条件概率 如上例中 假设 年收入 属性为随机变量 对于每个类Ci 属性值xj属于类Ci的概率为 可分别用Ci中xj的观察值的样本均值和标准差估计 如上表数据中 年收入 数据 分别属于两类 设类别C1 否 C2 是 对应的观察值如下 类别C1 否 的两个参数估计如下 类别C1 否 的两个参数估计为 同理 类别C2 是 的两个参数估计为 对于新样本 可以估计 年收入 属性相应的条件概率为 下面用上述方法来判别新样本 数据汇总如下 样本集 所属的类别 对于属性 年输入 已估计相应的条件概率为 由以上概率计算样本 相应的条件概率为 因此新样本属于第二类 即 是 拖欠贷款 问题1 则整个类的后验概率就等于0 如果样本 的类条件概率 X应该如何判别 问题2 对于连续型属性Xj 估计条件概率时把它视为连续型随机变量 估计的条件概率为 那么 这样估计是否合理 内的类条件概率为 问题2的解释 但我们知道 对于连续型随机变量 有 假设Xj落在区间 对于连续型属性Xj的每个取值xj 都使用同一个小正数 对于问题1 通常使用m值法来估计条件概率以解决这种情况 m值估计法 条件概率的估计值用下式进行估计 其中 n为训练样本中类Ci的总实例数 nc为Ci类中取值为xj的实例数 m和p是用户事先给定的参数 一般m为正整数 p是位于0与1之间的小数 例 设m 10 p 1 4 试对前面所给的数据重新估计离散型属性的各条件概率