数据挖掘整理.ppt

四 数据对象之间的相异度和相似度 1 简单属性的相似度和相异度 假设数据对象只有一个属性 则通常其相似度和相异度可按如下定义 1 1标称属性的相异度和相似度 相异度 相似度 s 1 d 例如 如果只考虑顾客的性别属性 如果都是 男 则他们的相似度为1 相异度为0 1 简单属性的相似度和相异度 1 2序数属性的相异度和相似度 d x y n 1 相异度 相似度 s 1 d 例如 考虑学生的成绩 共分为A B C D四个等级 则n 4 相异度为2 3 其中n为属性取值的总个数 1 简单属性的相似度和相异度 1 3区间或比率属性的相异度和相似度 d x y 相异度 较常用的相似度有 s 1 1 d 例如 考虑如下的身高数据 S 1 d min d max d min d 可以计算学生身高的相异度矩阵如下 二元属性 属性的值只接受两个值 如真 假 男 女 是 否等 通常用0 1表示 则S2与S6之间的相异度为10 而相似度为1 11 有min d 2 max d 29 因此 也可以定义相似度为1 10 2 29 2 19 27 2 数据对象之间的相似度 相似性度量的例子 2 1 二元数据的相似性度量 两个仅包含二元属性的对象之间的相似性度量也称为相似系数 设x和y是两个对象 都由n个二元属性组成 定义如下四个量 f00 x取0且y取0的属性个数 f01 x取0且y取1的属性个数 f10 x取1且y取0的属性个数 f11 x取1且y取1的属性个数 2 1 1一种常用的相似系数是简单匹配系数 SimpleMatchingCoeffient SMC 定义如下 SMC f00 f11 对于类似顾客是否购买某商品这样的非对称二元数据 这个相似系数则难以体现顾客相同的购买行为 Why 2 1 2Jaccard相似系数 Jaccard JaccardCoeffient JC 相似系数定义如下 J f11 例1 设二元数据对象x和y如下 计算其SMC和J x 1000101001 y 1010110011 解 f00 3 f01 3 f10 1 f11 3 因此 SMC 6 10 J 3 7 例2 设两个顾客x和y购买的商品如下 计算它们的相似系数SMC和J 2 1 3余弦相似度 通常类似于文档 词这样的数据 度量其相似性不能依赖共享0的个数 如果统计0 0匹配 则大多数文档都非常相似 因此同样要忽略0 0匹配 这类数据最常用的相似度之一就是余弦相似度 定义如下 Cos x y xy x y 2 1 4广义Jaccard系数 广义Jaccard系数也可以用于文档数据 并在二元属性情况下归约为Jaccard系数 其定义如下 例3 两个文档向量x和y如下 分别计算其余弦相似度cos x y 和EJ x 3205000200 EJ xy x 2 y 2 xy y 1003106001 2 1 4相关性 两个具有二元变量或连续的数据之间对象之间的相关性是对象之间线性联系的度量 一般可以用Pearson相关系数 Pearson scorrelation 来描述 其定义如下 其中 例如 以毫米为单位 20个人的身高通常不会重复 但如果以分米为单位 则某些人很可能具有相同的身高 此外 如果使用一个唯一的值表示遗漏值 该值通常用众数 1 1 2百分位数 百分位数的定义 设有容量为n的样本观察值想x1 x2 x3 xn 样本的p分位数 0 p 1 是指满足如下性质的xp A 至少有np个观察值小于或等于xp B 至多有n 1 p 个观察值大于或等于xp 样本的p分位数xp可以按如下方法求得 将观察值按自小到大的顺序排列成 x 1 x 2 x n 即 xp 1 若np不是整数 则只有一个数据满足定义的两点要求 这一数据位于大于np的最小整数处 即 np 1处 2 若np是整数 则位于np和np 1位置的数据均符合要求 此时取这两个数的平均值作为xp 当np不是整数 x np x np 1 2 当np是整数 与分位数有关常用术语 一 极差 x n x 1 median x 二 中位数 p 0 5 此时xp称为中位数 记为median x 其计算如下 当n为奇数 x n 2 x n 2 1 2 当n整为偶数 三 第一四分位数Q1 p 0 25 第三四分位数Q3 p 0 75 四分位数极差IQR Q3 Q1 例1 下表是中国各省 市 国有单位的人均报酬 单位 元 年 分别计算p 0 25 0 5 0 75时的分位数及样本均值 解 n 34 n 0 75 8 5 Q3 32738 江苏 同理 median 22956 湖北或湖南 Q1 21608 贵州 Q3 Q1 11130 样本均值为27501 59 箱线图如下 18392 黑龙江 21608 贵州 32738 江苏 50311 上海 箱线图的说明 若中位数位于箱子中间 则数据分布较为对称 若Min离M的距离较Max离M的距离大 在表示数据分布向左倾斜 反之向右 二 估计 2 1点估计 2 1 1矩估计与极大似然估计 另外一种常用的估计方法为折叠刀估计 它通过从一组观测值中忽略一个值来实现对参数的估计 假设一个具有n个值的集合x x1 x2 xn 对均值的单次估计为 2 1 2折叠刀估计 i x1 xi 1 xi 1 xn n 1 对这些单次估计求平均值 1 n n作为总统的均值估计 例 设总体的分布率如下 现有样本的10个观察值 3 3 2 2 1 2 1 2 3 3 分别用矩估计发 极大似然估计法和折叠刀估计法估计 解 矩估计法 E X 3 2 又样本均值为2 2 因此 得矩估计值为0 4 极大似然估计 L 的极大似然估计值也是0 4 数据 3 3 2 2 1 2 1 2 3 3 折叠刀估计法 计算 1 3 2 2 1 2 1 2 3 3 9 2 9 10 19 9 因此对总体均值的估计为 19 9 20 9 4 21 9 2 10 19 8 9 3 3 3 2 1 2 1 2 3 3 9 4 6 8 20 9 5 3 3 2 2 2 1 2 3 3 9 7 6 21 9 又E X 3 2 令3 2 19 8 9 解得 0 4 估计的一个指导思想是奥卡姆剃刀原则 Ockham sRazor 越简单的模型能产生越好的结果 主成分分析步骤 1 对数据进行标准化 设标准后的数据仍记为X 2 求观察数据的相关系数矩阵 数据标准化后 样本的相关系数矩阵即为 3 计算样本相关阵的特征值和特征向量 并按特征值从小到大排列 4 计算累积贡献率 确定综合变量个数 训练样本集如下 决策树是类似如下的一棵树 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 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 七 朴素贝叶斯分类法 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