第5章：数据仓库与数据挖掘的决策支持(3)

2020 4 24 信息分析与决策支持唐晶磊 决策支持系统及其开发 主讲教师 唐晶磊E mail tangjinglei Tel 87091337 O 2020 4 24 信息分析与决策支持唐晶磊 5 5知识发现与数据挖掘5 6数据挖掘的决策支持及应用 2020 4 24 信息分析与决策支持唐晶磊 DW的兴起 1 80年在美国召开了第一届国际机器学习研讨会 2 89年8月 美国底特律市召开的第一届KDD国际学术会议 3 95年 加拿大召开了第一届KDD和DM国际学术会议 4 我国于87年召开了第一届全国机器学习研讨会 5 5知识发现与数据挖掘 2020 4 24 信息分析与决策支持唐晶磊 5 5 1知识发现与数据挖掘概念 知识发现 Knowledgediscoveryindatabase 从数据中发现有用知识的整个过程 KDD KDD过程定义 从数据集中识别出有效的 新颖的 潜在有用的 以及最终可理解的模式的高级处理过程 模式 即是 知识 的雏形 需经过验证 完善 模式评价 后形成知识 KDD过程概括 数据准备 datapreparation 数据挖掘 datamining 及结果的解释和评估 interpretation evaluation 2020 4 24 信息分析与决策支持唐晶磊 5 5 1知识发现与数据挖掘概念 问题 所有企业都面临企业数据量巨大 而其中真正有价值的信息却很少 解决方法 对大量的数据进行深层分析 获得有利于商业运作 提高竞争力的信息 数据挖掘 DM KDD过程中的一个特定步骤 它用专门算法从数据中抽取模式 patterns 数据挖掘是一门交叉学科 涉及数据库技术 人工智能技术 数理统计 可视化技术 并行计算等方面 2020 4 24 信息分析与决策支持唐晶磊 5 5 1知识发现与数据挖掘概念 1 DM 技术角度 从大量的 不完全的 有噪声的 模糊的 随机的实际应用数据中 提取隐含在其中的 事先不知道的 但又是潜在有用的信息和知识的过程 即从数据源发现用户感兴趣的知识 知识要可接受 可以理解和运用 2020 4 24 信息分析与决策支持唐晶磊 5 5 1知识发现与数据挖掘概念 2 DM 商业角度 是一种新的 商业信息处理技术 对商业数据库中的大量业务数据进行抽取 转换 分析和其他模型化处理 从中提取辅助商业决策的关键性数据 数据挖掘是一种深层次的数据分析方法 2020 4 24 信息分析与决策支持唐晶磊 5 5 1知识发现与数据挖掘概念 3 DM 企业角度 按企业既定业务目标 对大量的企业数据进行探索和分析 揭示隐藏的 未知的或验证已知的规律性 并进一步将其模型化的先进有效方法 2020 4 24 信息分析与决策支持唐晶磊 KDD过程 2020 4 24 信息分析与决策支持唐晶磊 数据准备 数据选择 dataselection 数据预处理 datapreprocessing 和数据转换 datatransformation 数据选择 确定操作对象 即目标数据 targetdata 是根据用户的需要 从原始DB中选取的一组数据 数据预处理 消除噪声 处理缺值数据 消除重复记录等 数据转换 完成数据类型转换 进行属性约简 从初始属性中找出真正有用的属性 删除无用属性 以减少数据挖掘时要考虑的属性个数 数据准备 2020 4 24 信息分析与决策支持唐晶磊 数据挖掘 数据挖掘 1 首先确定挖掘的任务或目的 2 确定使用何种挖掘算法 选择挖掘算法需考虑2个因素 不同数据具有不同特点 需要用与之相关的算法来挖掘 考虑用户或实际运行系统的要求 如用户可能希望获取描述性的 容易理解的知识 或者希望获取预测准确度更可能高预测型知识 2020 4 24 信息分析与决策支持唐晶磊 结果的解释和评估 结果的解释和评估 模式评价 1 经过评估 剔除冗余或无关的模式 2 不满足用户要求的模式 需回退到KDD过程的前面阶段 3 KDD是面向用户的 一般需对发现的模式进行可视化处理 或把结果转换为用户易懂的表示形式 DM质量好坏的2个影响因素 1 所采用的DM技术的有效性 2 用于挖掘的数据的质量和数量 数据量的大小 2020 4 24 信息分析与决策支持唐晶磊 数据挖掘任务 DM任务有六项 1 关联分析若两个或多个数据项的取值重复出现 且概率很高时 它就存在某种关联 则可建立起这些数据项的关联规则 2 时序模式通过时间序列 搜索出重复发生概率较高的模式 3 聚类 通过聚类建立宏观概念 有统计分析方法 机器学习方法 神经网络方法等 2020 4 24 信息分析与决策支持唐晶磊 数据挖掘任务 4 分类 以聚类为基础 对已确定的类找出该类别的概念描述 它代表此类数据的整体信息 内涵描述 内涵描述分为特征描述和辨别性描述 判别分类方法的3个标准 预测准确度 计算复杂度 模式的简洁度 5 偏差检测 寻找观察结果与DB中参照数据之间的差别 6 预测 利用历史数据找出变化规律 建立模型 并用此模型来预测未来数据的种类 特征等 2020 4 24 信息分析与决策支持唐晶磊 属性约简 属性约简常用于分类问题原则 保持数据库中分类关系不变 一般采用粗糙集 roughset 方法 也可采用信息论方法 在DB的分类问题中 属性分为条件属性 C 和决策属性 D 条件属性分为可省略属性和不可省略属性 属性约简是在条件属性中 删除不影响对决策属性进行分类的多余的条件属性 不可省略属性 实质上是对决策属性进行分类的核心属性 2020 4 24 信息分析与决策支持唐晶磊 补充 数据挖掘与传统分析方法的区别 传统的数据分析方法 查询 报表和联机分析等 采用完全不同的工具 基于的技术差别也很大 1 查询和报表 告诉决策者数据库中都有什么 2 OLAP会进一步告诉决策者 下一步会怎么样 假设 如果我采用这样的措施 又会怎么样 OLAP通过建立一系列的假设 来证实或推翻这些假设 以得到合理的结论 因此 OLAP本质上是演绎推理过程 2020 4 24 信息分析与决策支持唐晶磊 补充 数据挖掘与联机分析处理的区别 DM在没有明确假设的前提下去挖掘信息 发现知识 DM所得到的信息是先前未知 有效的和可实用的 数据挖掘不用于验证某个假定的模式 而是在数据库中自己寻找模型 本质是一个归纳的过程 DM和OLAP具有一定的互补性 在利用DM出来的结论采取行动之前 利用OLAP验证一下 如果采取这样的行动 将会给公司带来什么样的影响 2020 4 24 信息分析与决策支持唐晶磊 5 5 2数据挖掘方法和技术 DM方法由人工智能 机器学习的方法发展而来 结合传统的统计分析方法 模糊数学方法以及计算科学可视化技术 以数据库为研究对象 形成了数据挖掘方法和技术 数据挖掘方法和技术可以分为六大类 2020 4 24 信息分析与决策支持唐晶磊 5 5 2数据挖掘方法和技术 一 归纳学习方法按采用的技术可分为信息论方法 决策树方法 和集合论方法 1 信息论方法 决策树方法 利用信息论的原理建立决策树或者决策规则树 较有特色的方法有 1 ID3等方法 决策树方法 2 IBLE 决策规则树 方法 2020 4 24 信息分析与决策支持唐晶磊 2 集合论方法 1 粗糙集 RoughSet 方法对数据库中的条件属性集与决策属性集建立上下近似关系 对下近似集合建立确定性规则 对上近似集合建立不确定性规则 含可信度 2 关联规则挖掘在交易事务数据库中 挖掘出不同商品集的关联关系 即发现哪些商品频繁地被顾客同时购买 3 覆盖正例排斥反例方法它是利用覆盖所有正例 排斥所有反例的思想来寻找规则 较典型的有AQ11方法 AQ15方法及AE5方法 2020 4 24 信息分析与决策支持唐晶磊 二 仿生物技术典型的仿生物技术方法是神经网络方法和遗传算法 1 神经网络方法 包括 前馈式网络 反馈式网络 自组织网络等多个神经网络方法 2 遗传算法 模拟生物进化过程的算法 它由三个基本算子组成 繁殖 选择 交叉 重组 变异 突变 遗传算法起到产生优良后代的作用 经过若干代的遗传 将得到满足要求的后代 问题的解 2020 4 24 信息分析与决策支持唐晶磊 三 公式发现在工程和科学数据库中对若干数据项 变量 进行一定的数学运算 求得相应的数学公式 1 物理定律发现系统BACONBACON发现系统完成了物理学中大量定律的重新发现 2 经验公式发现系统FDD寻找由数据项的初等函数或复合函数组合成的经验公式 2020 4 24 信息分析与决策支持唐晶磊 四 统计分析方法利用统计学原理对总体中的样本数据进行分析 得出描述和推断该总体信息和知识的方法 五 模糊数学方法利用模糊集合理论进行数据挖掘 如模糊聚类 模糊分类等 六 可视化技术利用可视化技术分析数据库 找到潜在的有用信息 2020 4 24 信息分析与决策支持唐晶磊 5 5 3数据挖掘的知识表示 一 DM获取知识表示形式主要有六种 规则 决策树 浓缩数据 网络权值 公式和案例 1 规则规则知识由前提条件和结论两部分组成前提条件由字段项 属性 的取值的合取 与 和析取 或 组合而成 结论为决策字段项 属性 的取值或者类别组成 2020 4 24 信息分析与决策支持唐晶磊 5 5 3数据挖掘的知识表示 一 2020 4 24 信息分析与决策支持唐晶磊 2 决策树例如 上例的人群数据库 按ID3方法得到的决策树如下 数据挖掘的知识表示 二 2020 4 24 信息分析与决策支持唐晶磊 3 知识基 浓缩数据 例如上例的人群数据库 通过计算可得出身高是不重要的字段 删除它后 再合并相同数据元组 得到浓缩数据如下表 数据挖掘的知识表示 三 2020 4 24 信息分析与决策支持唐晶磊 4 网络权值神经网络方法经过对训练样本的学习后 所得到的知识是网络连接权值和结点的阈值 数据挖掘的知识表示 四 0 5 2020 4 24 信息分析与决策支持唐晶磊 5 公式例如 太阳系行星运动数据中包含行星运动周期 旋转一周所需时间 天 以及它与太阳的距离 围绕太阳旋转的椭圆轨道的长半轴 百万公里 数据如下表 通过物理定律发现系统BACON和经验公式发现系统FDD 都可得到开普勒第三定律 d3 p2 25 数据挖掘的知识表示 五 2020 4 24 信息分析与决策支持唐晶磊 5 6数据挖掘的决策支持及应用 5 6 1决策树及其应用 1 决策树概念 用样本的属性作为结点 用属性的取值作为分支的树结构 利用信息论原理对大量样本的属性进行分析和归纳 决策树的根结点是所有样本中信息量最大的属性 中间结点是以该结点为根的子树 所包含的样本子集中信息量最大的属性 叶结点是样本的类别值 2020 4 24 信息分析与决策支持唐晶磊 5 6数据挖掘的决策支持及应用 决策树用于对新样本的分类 通过决策树对新样本属性值的测试 从树的根结点开始 按照样本属性的取值 逐渐沿着决策树向下 直到树的叶结点 该叶结点表示的类别就是新样本的类别 2020 4 24 信息分析与决策支持唐晶磊 DM的决策树方法的原理是信息论 信息论是C E Shannon为解决信息传递 通信 过程问题而建立的理论 也称为统计通信理论 传递信息的系统是由发送端 信源 和接收端 信宿 以及连接两者的通道 信道 三者组成 信息论把通信过程看做在随机干扰的环境中传递信息的过程 在这个通信模型中 信息源和干扰 噪声 都被理解为某种随机过程或随机序列 补充内容 2020 4 24 信息分析与决策支持唐晶磊 在进行实际通信之前 收信者 信宿 不可能确切了解信源究竟会发出什么样的具体信息 不可能判断信源会处于什么样的状态 此情形称为信宿对于信源状态具有不确定性 这种不确定性存在通信之前的 又叫做先验不确定性 通信之后 信宿收到了信源发来的信息 这种先验不确定性才会被消除或者被减少 如果干扰很小 信源发出的信息能够被信宿全部收到 此种情况下 信宿的先验不确定性就会被完全消除 补充内容 2020 4 24 信息分析与决策支持唐晶磊 一般情况下 干扰总会对信源发出的信息造成某种破坏 使信宿收到的信息不完全 因此 先验不确定性不能全部被消除 只能部分地消除 通信结束之后 信宿还仍然具有一定程度的不确定性 这就是后验不确定性 显然 后验不确定性总要小于先验不确定性 不可能大于先验不确定性 补充内容 2020 4 24 信息分析与决策支持唐晶磊 如果后验不确定性的大小正好等于先验不确定性的大小 表示信宿根本没有收到信息 如果后验不确定性的大小等于零 表示信宿收到了全部信息 因此 信息是用来消除 随机 不确定性的度量 信息量的大小 由所消除的不确定性的大小来计量 2020 4 24 信息分析与决策支持唐晶磊 2 ID3算法 当前国际上最有影响的示例学习方法首推ID3 ID3引进了信息论中的互信息 信息增益informationgain 作为特征 属性 判别能力的度量 且将建树的方法嵌在一个迭代的外壳之中 2020 4 24 信息分析与决策支持唐晶磊 ID3基本思想 每个实体用多个特征来描述 每个特征限于在一个离散集中取互斥的值 例如 设实体是某天早晨 分类任务是关于气候的类型 有4各特征 属性 为 天气取值为 晴 多云 雨气温取值为 冷 适中 热湿度取值为 高 正常风取值为 有风 无风 某天早晨 实体 气候描述为 天气 多云气温 冷湿度 正常风 无风 2020 4 24 信息分析与决策支持唐晶磊 判断此实体属于哪类气候类别 假定仅有两个类别 分别为P N 两个类别的归纳任务中 P类和N类的实体分别称为概念的正例和反例 将一些已知的正例和反例放在一起便得到训练集 下表给出一个训练集 由ID3算法得出一棵正确分类训练集中每个实体的决策树 2020 4 24 信息分析与决策支持唐晶磊 ID3决策树 2020 4 24 信息分析与决策支持唐晶磊 决策树叶子结点为类别名 即P或者N 其它结点由实体的特征组成 每个特征的不同取值对应一分枝 若要对一个实体分类 从树根开始进行测试 按特征的取值分枝向下进入下层结点 对该结点进行测试 过程一直进行到叶结点 实体被判为属于该叶结点所标记的类别 2020 4 24 信息分析与决策支持唐晶磊 ID3算法 一 主算法1 从训练集中随机选择一个既含正例又含反例的子集 称为 窗口 2 用 建树算法 对当前窗口形成一棵决策树 3 对训练集 窗口除外 中例子用所得决策树进行类别判定 找出错判的例子 4 若存在错判的例子 把它们插入窗口 转2 否则结束 主算法流程用下图表示 ID3主算法流程 2020 4 24 信息分析与决策支持唐晶磊 PE NE分别为正例集和反例集 共同组成训练集 PE PE 和NE NE 分别表示正例集和反例集的子集 主算法中每迭代循环一次 生成的决策树将会不相同 2020 4 24 信息分析与决策支持唐晶磊 二 建树算法1 计算当前例子集合各特征的互信息 2 选择互信息最大的特征Ak 作为树 子树 的根结点 3 把在Ak处取值相同的例子归于同一子集 分支 Ak取几个值就得几个子集 分支 4 对既含正例又含反例的子集 递归调用建树算法 5 若子集仅含正例或反例 对应分枝标上P或N 返回调用处 2020 4 24 信息分析与决策支持唐晶磊 3 ID3方法应用实例 气候分类问题具体计算有 信息熵的计算信息熵 类别ui出现的概率 类别 正例or反例 S 表示例子集S的总数 ui 表示类别ui的例子数 2020 4 24 信息分析与决策支持唐晶磊 对9个正例和5个反例有 P u1 9 14P u2 5 14H U 9 14 log2 14 9 5 14 log2 14 5 0 94b 2020 4 24 信息分析与决策支持唐晶磊 条件熵 计算条件熵 属性A1取值vj时 类别ui的条件概率 2020 4 24 信息分析与决策支持唐晶磊 A1 天气取值v1 晴 v2 多云 v3 雨在A1处取值晴的例子5个 取值多云的例子4个 取值雨的例子5个 故 P v1 5 14P v2 4 14P v3 5 14取值为晴的5个例子中有2个正例 3个反例 故 P u1 v1 2 5 P u2 v1 3 5同理有 P u1 v2 4 4 P u2 v2 0P u1 v3 2 5 P u2 v3 3 5条件熵为 H U V 5 14 2 5 log 5 2 3 5 log 5 3 4 14 4 4 log 4 4 0 5 14 2 5 log 5 2 3 5 log 5 3 0 694bit 2020 4 24 信息分析与决策支持唐晶磊 计算互信息对A1 天气处有 I 天气 信息熵 条件熵 H U H U V 0 94 0 694 0 246bit类似可得 I 气温 0 029bitI 湿度 0 151bitI 风 0 048bit 2020 4 24 信息分析与决策支持唐晶磊 建决策树的树根和分枝ID3算法将选择互信息最大的特征天气作为树根 在14个例子中 对天气的3个取值进行分枝 3个分枝对应3个子集 分别是 F1 1 2 8 9 11 F2 3 7 12 13 F3 4 5 6 10 14 其中F2中的例子全属于P类 因此对应分枝标记为P 其余两个子集既有正例又有反例 将递归调用建树算法 2020 4 24 信息分析与决策支持唐晶磊 对F1和F3子集分别利用ID3算法 在每个子集中对各特征 仍为四个特征 求互信息 1 F1中的天气全取晴值 则信息熵H U 条件熵H U V 有互信息I U V 0 在余下三个特征中求出湿度互信息最大 以它为该分枝的根结点 再向下分枝 湿度取高的例子全为N类 该分枝标记N 取值正常的例子全为P类 该分枝标记P 递归建树 2020 4 24 信息分析与决策支持唐晶磊 2 在F3中 对四个特征求互信息 得到风特征互信息最大 则以它为该分枝根结点 再向下分枝 取有风时全为N类 该分枝标记N 取无风时全为P类 该分枝标记P 这样就得到图的决策树 递归建树 2020 4 24 信息分析与决策支持唐晶磊 4 C4 5算法 ID3算法在DM中占有非常重要的地位 缺点 ID3算法不能够处理连续属性 计算信息增益时偏向于选择取值较多的属性等不足 P257 C4 5是在ID3基础上发展起来的决策树生成算法 由J R Quinl