《数据分析技术》PPT课件.ppt

数据分析技术 战略信息 企业目标在5年内增加15 的客户在3年内抢占15 的市场在2年内投放3种新产品提高前5 的产品质量在东北市场提高15 的销售额所需信息全面深入地了解公司运营了解关键因素及其相互作用检测这些因素如何随时间变化将公司运营状况和对手以及行业标准做比较 战略信息系统 SIS StrategicInformationSystems能够支援和改变组织战略行为 使得组织具有竞争力的信息系统 决策支持系统 正确决策 企业的竞争优势 错 错 错在错误的时间 错误的地点 同错误的对手打了一场错误的战争 噬脐何及 合九州六十四县铁 不能铸成此大错也 苍天如圆盖大地如棋局世间分楚汉荣辱争天下 博弈 博弈 博弈 博弈 纳什均衡一个博弈可能有多个纳什均衡每个参与者把其他参与人的策略当作是给定的允许了不可置信的威胁的存在 博弈 博弈 博弈 博弈 阿里巴巴 芝麻开门 哪些客户对我们最有利 如何拓展与他们的联系 哪些客户给我们提供利润 哪些客户使我们遭受损失 根据他们经常光顾的商店 最好的客户居住在哪里 哪些产品和服务能被最有效的进行交叉销售 销售对象是谁 哪些市场营销案例是最成功的 为什么 哪些销售渠道对于哪些产品是最有效的 如何才能改善我们用户的总体经历 Wearedrowningindatabutstarvedofinformation 商务智能 商务智能的需求有巨量的商业数据日常数据 订单 存货 帐单 外部数据 客户信息 对手信息 政策每2到3年商业数据变会翻番有93 的数据没有在决策过程中使用到 商务智能的目的使人能更快捷 更容易地做出更好的商业决策终极目标3w win win win 商务智能 BusinessIntelligenceisaprocessofturningdataintoknowledgeandknowledgeintoactionforbusinessgain BusinessIntelligenceistheprocessoftransformingdataintoinformation andthroughiterativediscoverytransforminginformationintoknowledge elevate 从数据到知识 垂拱而治 CEO 统计一下购买我们的产品及竞争对手产品的用户信息计算机 垂拱而治 CEO 怎样会使得用户购买我们的产品 计算机 刺激销售 如中奖销售 打折优惠 会吸引他们购物CEO 促销的成本是多少 促销的最佳时机是什么时候 它会吸引多少新用户 计算机 三拍 而治 管理活动的层次结构 管理活动各层次中信息的特征 不同层次的信息处理需求 事务处理需求不同的事务处理子系统采购子系统 订单 订单细则 供应商销售子系统 顾客 销售库存子系统 出库领料单 进料入库单 库存台帐人事子系统 员工 部门各种事务处理需求一笔订购 一笔销售 一次进料 一次出料要求强调多用户并发环境 数据的一致性 完整性 不同层次的信息处理需求 分析处理需求今年销售量下降的因素 时间 地区 商品 销售部门 某种商品今年的销售情况与以往相比 有怎样的变化 每年的第一季度商品销售在各类商品上的分布情况怎样 要求多个子系统中的数据 数据集成 历史数据汇总 综合的数据 DSS早期演化阶段 1960 1965 1970 1975 1980 主文件报表 太多主文件 数据库 所有处理的单一数据源 联机高性能事务处理 单一数据库既用于事务处理 又用于DSS DSS早期演化阶段 抽取程序搜索整个文件和数据库 使用某些标准选取合乎限制的数据 并把数据传到其他文件或数据库中优点将数据从事务处理应用中转移出来 在进行数据分析时不会与事务处理发生冲突当将数据从事务处理应用中抽取出来之后 数据的控制方式发生了转变 最终用户可以拥有抽取出来的数据 抽取程序 DSS早期演化阶段 蜘蛛网 数据缺乏可信性生产率低 从数据库到数据仓库 事务处理与分析处理的性能特性不同事务处理环境数据存取操作频率高每次操作处理的时间短占用系统资源少系统可以允许多个用户按分时方式使用资源 保持较短的响应时间分析处理环境运行时间长消耗大量系统资源事务与分析应用不宜放在同一中环境中 从数据库到数据仓库 数据集成问题事务处理目的是使业务自动化只关注与本部门业务相关的当前数据事务处理应用的分散 企业内部各事务处理应用间相互独立DSS需要集成的数据 内部各部门数据 外部数据 竞争对手数据 DSS需要对分散在各个事务处理应用中的相关数据进行集成 以向分析人员提供统一的数据视图 数据仓库的定义 数据仓库是一个面向主题的 SubjectOriented 集成的 Integrated 相对稳定的 Nonvolatile 反映历史变化的 timeVariant 数据集合 用于支持管理决策 数据粒度 粒度数据综合程度高低的一个度量粒度越小 越细节 综合程度越低 回答查询种类越多 数据量大 性能低 数据粒度 细节级一个月内客户的每个电话记录每月200个记录 40000个字节 综合级一个月内客户电话汇总 电话次数 平均通话时间 长途电话次数 每月1个记录 200个字节 能回答 不能回答 上周张三给他在上海的女朋友打电话了吗 能回答 能回答性能低 上月人们从华盛顿打出的长途电话平均次数 数据分割 分割将数据分散到各自的物理单元中去 以便能分别独立处理 灵活地访问数据 提高效率实际需要分析往往对某种相关性的数据集合进行某一时段的数据某一地区的数据某特定业务领域的数据某一时段某特定业务领域的数据日期往往是自然而均匀的分割 数据分割 健康保险人寿保险意外伤亡保险1988分片1分片2分片31989分片4分片5分片61990分片7分片8分片9 数据仓库的体系结构 信息集成 信息集成的定义informationintegration把存储在两个或多个信息源中的数据提取出来 建立一个包含所有这些信息源的信息的大数据库 该数据库可以是虚拟的 信息集成的方式联邦数据库 federaldatabase 数据仓库 datawarehouse 协调器 mediator 信息集成中的问题 汽车公司有1000位代理商 想创建一个集成数据库 各个代理商使用不同的数据库模式代理商1 Cars serialNo model color autotrans cdPlayer 代理商2 Autos serial model color Options serial option 问题数据类型不同取值不同语义不同数据丢失 联邦数据库 DB1 DB2 DB3 DB4 问题 编写n n 1 个组件来相互翻译查询 联邦数据库 代理商1询问代理商2是否有自己所需要的汽车 for eachtuple m c a inNeededCars if a true selectserialfromAutos OptionswhereAutos serial Options serialandAutos model mandAutos color celseselectserialfromAutoswhereAutos model mandAutos color cnotexists select fromOptionswhereserial Autos serialandoption autoTrans NeededCars model color autoTrans 数据仓库 查询 结果 数据仓库是个实视图 数据仓库 insertintoAutosWhse serialNo model color autotrans dealer selectserialNo model color autotrans dealer1 fromCars 导入代理商1 代理商1 Cars serialNo model color autotrans cdPlayer 代理商2 Autos serial model color Options serial option 数据仓库 AutosWhse serialNo model color autotrans dealer dealer指拥有该车的代理商 数据仓库 insertintoAutosWhse serialNo model color autotrans dealer selectserialNo model color yes dealer2 fromAutos OptionswhereAutos serial Options serialandoption autoTrans insertintoAutosWhse serialNo model color autotrans dealer selectserialNo model color no dealer2 fromAutoswherenotexists select fromOptionswhereAutos serial Options serialandoption autoTrans 导入代理商2 协调器 协调器是个虚视图 协调器 协调器 AutosMed serialNo model color autotrans dealer 询问协调器关于红色汽车的信息selectserialNo modelfromautosMedwherecolor red 代理商1的包装器selectserialNo modelfromCarswherecolor red 代理商2的包装器selectserialNo modelfromAutoswherecolor red 协调器 询问协调器是否存在Gobi型号的蓝色汽车 询问代理商1是否存在Gobi型号的蓝色汽车 询问代理商2是否存在Gobi型号的蓝色汽车 返回 是 否 包装器 包装器从协调器接受各种查询 然后将查询翻译成数据源的术语 并将结果传送给协调器如何设计包装器 将协调器可能使用的查询进行分类 成为模板模板是带有代表常数的参数的查询协调器提供常数 包装器执行给定好常数的查询用T S表示包装器将查询模板T变成对数据源的查询S 包装器生成器 类似YACC 将翻译好之后的查询模板和对应的源查询存储到表中 接受来自协调器的查询在表中查找与查询匹配的模板找到 则传递查询中参数 实例化模板没找到 拒绝协调器源查询发送到数据源将数据源的答复返回给协调器 包装器模板 协调器 AutosMed serialNo model color autotrans dealer 代理商1 Cars serialNo model color autotrans cdPlayer select fromAutosMedwherecolor c selectserialNo model color autotrans dealer1 fromCarswherecolor c 查询给定颜色的汽车 模板1 包装器模板 select fromAutosMedwherecolor c andmodel m selectserialNo model color autotrans dealer1 fromCarswherecolor c andmodel m 查询给定颜色和型号的汽车 模板2 过滤器 为避免太多的查询模板 只给包装器指定少量模板 它返回查询所需结果的超集 然后再由包装器过滤向数据源所提供的结果 询问协调器关于红色 BMW 汽车的信息selectserialNo modelfromautosMedwherecolor red andmodel BMW 执行模板1 令 c red 将结果保存在临时表TempAutos中 实际中 可以是流水方式 执行查询select fromTempAutoswheremodel Gobi 问题 如何确定一个协调器查询是某个包装器模板查询结果的子集 过滤器 查询代理商和型号 代理商有两辆同型号的红色汽车 一辆是自动的 另一辆不是 针对协调器的查询selectA1 model A1 dealerfromautosMedA1 autosMedA2whereA1 model A2 modelandA1 color red andA2 color red andA1 autoTrans no andA2 autoTrans yes 过滤器 执行模板1 令 c red 将结果保存在临时表RedAutos中接着执行 selectA1 model A1 dealerfromRedAutosA1 RedAutosA2whereA1 model A2 modelandA1 autoTrans no andA2 autoTrans yes 数据分析流程 SpreadSheet Table Extracting Visualizing 计算Vs可视化 关系系统计算数据立方体可视化系统显示数据立方体 一些分析需求 用户想使用直方图用户想在不同粒度上运用聚集函数rollup drilldown用户想使用交叉表 F G H RedBrick的扩展 N tile将所有元组按值大小分为n个连续区间 每个区间的元组个数相同 返回每个区间的平均值selectpercentile avg salary fromEMPgroupbyN tile salary 10 aspercentileRatio To Total计算每个分组的和在总和中的比例Rank返回值在所有列值中的序号 TOP select topn percent withties select list selecttop5title id price typefromtitlesselecttop5title id price typefromtitlesorderbypricedescselecttop5WITHTIEStitle id price typefromtitlesorderbypricedescselecttop30PERCENTtitle id price typefromtitlesorderbypricedesc 我要的不多只需要n个 直方图 select1 avg fromEMPwheresalary selectmax salary fromEMP 2 3union select2 avg fromEMPwheresalary selectmax salary fromEMP 3union select3 avg fromEMPwheresalary selectmax salary fromEMP 3 rank selectT1 S GRADE selectcount distinctT2 GRADE fromSCAST2whereT1 GRADE T2 GRADE asrankfromSCasT1whereGRADEisnotnullorderbyrank 中位数 declare tempINT medianINTset temp selectcount fromsc 2declaremy curscursorforselectGRADEfromSCorderbyGRADEopenmy curswhile temp 0 beginfetchmy curs temp temp 1endfetchmy cursinto median 给出成绩排在最中间的学生的成绩 落差 createviewrankgrade GRADE graderank asselectGRADE selectcount distinctGRADE fromSCasT1whereT1 GRADE T2 GRADE asrankfromSCAST2selectG1 V1 GRADE G2 V2 GRADE DIFF V2 GRADE V1 GRADE fromrankgradeasV1leftouterjoinrankgradeasV2on V2 graderank V1 graderank 1 给出所有相邻两个成绩之间的差 Skyline 问题的引入 找一个便宜并且离海滩近的旅馆系统无法决定哪些是最好的 但它会提供所有的备选 interesting 旅馆 也即它们不会在两个维上都比其他任何旅馆差 称其为Skyline Skyline 问题的引入 称点x统治 dominate 点y 如果x在所有维上都不比y差 并且至少在一个维上好过y旅馆 price 50 distance 0 8 统治 price 100 distance 1 0 Skyline 更高 更靠近河流的建筑 东食西宿 更英俊 更有钱 Skyline的性质 一个集合M 一个单调计分函数R 如果p M使得R最大 那么p一定在M的Skyline中不管你如何偏好旅馆的价格和距离 你最中意的旅馆总是在Skyline中对Skyline中的任意一点p 总存在一个单调计分函数 p使得它最大 也即Skyline不会包含不是任何人偏好的旅馆统治满足传递性 也即如果p统治q q统治r 则p统治r 带Skyline的SQL扩展 SELECT FROM WHEREGROUPBY HAVING SKYLINEOF DISTINCT d1 MIN MAX DIFF dn MIN MAX DIFF TOP ORDERBY SKYLINEOFd1MIN d2MAX d3DIFFp p1 p2 p3 统治q q1 q2 q3 如果p1 q1 p2 q2 p3 q3 带Skyline的SQL示例 用嵌套子查询实现Skyline Skyline的大小 联机分析处理 OLAP 存在着大量的分析型应用 要求对大量的数据从各个角度进行综合分析 多维分析 典型分析应用 对一些统计指标 销售金额 从不同角度 维 时间 地区 商品类型 从不同级别 层次 地区 县 地市 省 大区 今年销售量下降的因素 时间 地区 商品 销售部门 某种商品今年的销售情况与以往相比 有怎样的变化 每年的第一季度商品销售在各类商品上的分布情况怎样 多维数据模型 关系表与多维Cube 多维数据模型的基本组成 维 度量 多维数据模型 变量 指标 数据的实际意义 一般是一个数值度量指标例如 销售量 销售额 而具体数据 如 10000 是变量的一个值维观察数据的特定角度例如 时间 地区 维的层次特定角度的不同细节程度例如 时间维 日 周 月 季 年地理维 城市 地区 国家 多维分析的基本分析动作 切片 Slice 从多维数组选定一个二维子集 切出一个 平面 切块 Dice 从多维数组选定一个三维子集 切出一个 立方体 旋转改变一个报告 或页面 显示的维方向 关系的交叉表表示 关系表 关系的交叉表表示 交叉表 用SQL生成交叉表 SELECTModel Year Color SUM Sales FROMSalesWHEREModel Chevy GROUPBYModel Year ColorUNIONSELECTModel Year ALL SUM Sales FROMSalesWHEREModel Chevy GROUPBYModel YearUNIONSELECTModel ALL ALL SUM Sales FROMSalesWHEREModel Chevy GROUPBYModel cube CUBE cube selectModel Year Color sum Sales fromSalesgroupbyModel Year Colorwithcube 总行数 model个数 1 theyear个数 1 color个数 1 2 1 3 1 3 1 48 CUBE SELECTSUM units sold model theyear colorFROMmy cubeGROUPBYmodel theyear colorWITHCUBE SELECT UnitsSold SUM units sold model ALLModels GROUPING model year ALLYears GROUPING theyear color ALLColors GROUPING color FROMmy cubeGROUPBYmodel theyear colorWITHCUBE GROUPING是一个聚合函数 它产生一个附加的列 当用CUBE或ROLLUP运算符添加行时 附加的列输出值为1 当所添加的行不是由CUBE或ROLLUP产生时 附加列值为0 CUBE CREATEVIEWauto cube units model theyear color ASSELECTSUM units sold CASEWHEN GROUPING model 1 THEN ALL ELSEISNULL model END CASEWHEN GROUPING theyear 1 THEN ALL ELSEISNULL theyear END CASEWHEN GROUPING color 1 THEN ALL ELSEISNULL color ENDFROMmy cubeGROUPBYmodel theyear colorWITHCUBE ROLLUP SELECT unit sold SUM units sold model CASEWHEN GROUPING model 1 THEN ALL ELSEISNULL model END theyear CASEWHEN GROUPING theyear 1 THEN ALL ELSEISNULL theyear END color CASEWHEN GROUPING color 1 THEN ALL ELSEISNULL color ENDFROMmy cubeGROUPBYmodel theyear colorWITHROLLUP OLAPServer的分类 数据存储方式 RelationalOLAP ROLAP 利用关系数据库来存储和管理基本数据和聚合数据 并利用一些中间件来支持缺失数据的处理具有良好的可扩展性MultidimensionalOLAP MOLAP 利用多维数据库来存放和管理基本数据和聚合数据 其中需要对稀疏矩阵处理技术对预综合的数据进行快速索引HybridOLAP HOLAP 利用关系数据库来存储和管理基本数据 利用多维数据库来存储和管理聚合数据 多维数据库存储 由许多 经压缩的 类似于数组的对象构成每个对象由聚集成组的单元块组成每个单元块按类似于多维数组的结构存储通过直接偏移计算进行存取每个对象带有 压缩的 索引和指针结构分析时常需维间的组合需 旋转 数据立方体 及 切片 高效的稀疏数据处理能力 略过缺失和重复数据许多维间的组合没有值 6月份冰鞋销售量许多值重复存储 今年酱油的价格 用关系结构表示多维数据 关系数据库使用广泛 相当成熟用两类表来表示多维结构 事实表 维表事实 fact 表 用来存储变量值和各维的码值维表 用来存储维的描述信息 元数据 包括层次和类等事实表描述了主题的数据 维表是从不同的角度描述了对主题的分析尺度维表就象星星的角一样 分布在事实表的外围 描述了业务的各个维 星型模式 StarSchema 雪片模式 SnowFlakeSchema 雪片模式 一个广为流传的数据挖掘例子 美国加州某个超市连锁店通过数据挖掘从记录着每天销售和顾客基本情况的数据库中发现 在下班后前来购买婴儿尿布的顾客多数是男性 他们往往也同时购买啤酒 于是这个连锁店的经理当机立断地重新布置了货架 把啤酒类商品布置在婴儿尿布货架附近 并在二者之间放上土豆片之类的佐酒小食品 同时把男士们需要的日常生活用品也就近布置 这样一来 上述几种商品的销量几乎马上成倍增长 知识发现的定义 数据库中的知识发现是识别数据中有效的 Valid 新颖的 Novel 潜在有用的 PotentiallyUseful 和最终可被理解 UltimatelyUnderstandable 的模式 Pattern 的非平凡过程 KDD KnowledgeDiscoveryinDatabase 数据挖掘的定义 数据挖掘 DataMining 是KDD过程的一个步骤 它是在现实可接受的计算效率限制下 应用数据分析和知识发现算法 在数据的基础上 对模式 Pattern 的特定枚举 数据挖掘的任务与方法 关联分析 Associations 目的和含义目的 发现数据库中数据间的相互关联含义 给定一组数据项 例如 商品号 和一个交易集合 例如交易记录 通过分析记录集合 推导出数据项间的相关性 例如 在交易活动中商品间的相关性 基本形式给定 一组事务集每一个事务中包含若干个数据项挖掘 各个数据项之间的关联例如 98 的顾客在购买电动剃须刀的同时会购买一些电池 关联规则兴趣度的度量值 支持度 推导出的数据间的相关性称为规则 或模式 对规则兴趣度的描述采用支持度 置信度概念支持度 Support 在关联分析中表示满足规则的记录数与总记录数的比 它表明了规则的模式在数据库中出现的频度对于规则 X Y 则其支持度表示为 购买商品Y的交易 同时购买商品X和Y的交易 购买商品X的交易 关联规则兴趣度的度量值 置信度 置信度 Confidence 在关联分析中表示为满足规则的记录数与出现被分析数据项的记录数之比对于规则 X Y 则其置信度表示为 最小支持度和最小置信度用户 分析员 不关心可信程度太低的规则 因而用户需要输入两个参数 最小支持度和最小置信度 支持度和置信度举例 零售商场销售分析数据项为商品 记录集合为交易记录集合规则为 购买商品X的顾客 同时购买商品Y 即X Y 设最小支持度为0 3 最小置信度也为0 3分析结果 关联分析的基本步骤 术语设I i1 i2 im 是项的集合 itemset 包含k个项的称为k 项集设D是事务的集合 其中每个事务T是项的集合 T I设A是一个项集 事务T包含A当且仅当A T项集的出现频率 D中包含项集的事务数频繁项集 如果项集的出现频率大于或等于最小支持度min sup与D中事务总数的乘积 频繁k 项集记作Lk关联规则A B 其中A I B I 并且A B 强规则 同时满足最小支持度和最小置信度的规则 关联分析的例子 Min support50 Min confidence50 ForruleA C support support A C 50 confidence support A C support A 66 6 ForruleC A support support A C 50 confidence support A C support C 100 关联分析的基本步骤 通常 关联分析的过程分为以下两步 发现频繁项集 frequentitemset 这些项集出现的频率至少和预定义的最小支持度一样由频繁项集来产生强关联规则 这些规则必须满足最小支持度和最小置信度 Apriori算法 Apriori性质先验 Apriori 法则 一个频繁项集的任何非空子集肯定也是一个频繁项集例如 A B 为高频项集 那么其子集 A B 一定都为高频项集反单调 一个集合如果不能通过测试 则它的任何超集也不能通过测试反复寻找高频项集 从1到K阶 Apriori算法 如何由Lk 1产生Lk 连接步 对K 1阶频繁项集Lk 1做Self Join操作 形成K阶频繁项集的候选集Ck具体算法如下 insertintoCkselectp item1 p item2 p itemk 1 q itemk 1fromLk 1p Lk 1qwherep item1 q item1 p itemk 2 q itemk 2 p itemk 1 q itemk 1 Apriori算法 剪枝步 任何K 1阶非频繁项集 则其不可能为K阶频繁项集的子集具体算法如下 forallitemsetscinCkdoforall k 1 subsetssofcdoif sisnotinLk 1 thendeletecfromCk Apriori算法 示例3阶高频项目集 L3 abc abd acd ace bcd 连接步Self joining L3 L3abc abd abcdacd ace acde剪枝步acde移出 因为ade不包含在L3中4阶候选集 C4 abcd Apriori算法 数据库事务数据D 最小支持度min sup 2 Apriori算法 扫描D 对每个候选记数 比较sup 与min sup C1 L1 Apriori算法 由L1产生C2 扫描D 对每个候选记数 C2 C2 Apriori算法 比较sup 与min sup L2 由L2产生C3 C3 Apriori算法 使用Apriori性质剪枝 C3 扫描D 对每个候选记数 C3 比较sup 与min sup L3 由频繁项集来产生关联规则 步骤对于每个频繁项集l 产生l的所有非空子集对于L的每个非空子集s 如果 则输出规则 s l s 其中min conf是最小置信度阈值由于规则由频繁项集产生 每个规则自动满足最小支持度 由频繁项集来产生关联规则 示例l I1 I2 I5 l的非空子集 I1 I2 I5 I1 I2 I1 I5 I2 I5 I1 I2 I5 c 2 6 33 I2 I1 I5 c 2 7 29 I5 I1 I2 c 2 2 100 I1 I2 I5 c 2 4 50 I1 I5 I2 c 2 2 100 I2 I5 I1 c 2 2 100 若min conf 70 则输出第3 5 6条规则 分类分析 Classifiers 含义有一个记录集合和一组标记 标记用以标识记录的类别先为每个记录赋予一个标记 按标记对记录分类 对同类记录的特征进行描述显式描述 例如 一组规则定义隐式描述 例如 一个数学模型或公式分类具有极其广泛的应用分类常用于预测医疗诊断 性能预测 选择购物 信誉证实等 分类分析的两个步骤 构建模型 对预先确定的类别给出相应的描述先假设一个元组 或样本 集合中的每一个元组 或样本 属于预先定义的某一个类别 由一个类标号属性 classlabelattribute 来确定这些元组 或样本 的集合称为训练集 用于构建模型 由于提供了每个训练样本的类标号 称作有指导的学习最终的模型用决策树 分类规则或者数学公式等来表示模型应用 对未知的数据对象进行分类 分类分析第一步 构建模型 分类分析第二步 模型应用 分类分析举例 对信用卡持卡人的信誉进行分类分析记录集合 持卡人的记录集一组标记 良好 普通 较差 信誉程度 先为每个持卡人赋予一个标记 即信誉等级对同类记录 即同信誉等级的持卡人 的特征进行描述 例如 信誉良好的持卡人的特征为 收入在25000以上年龄在45 55之间居住在XYZ地区对同类记录特征的描述 规则或模型 可用来分类新记录 分类分析举例 顾客购物分类顾客属性 姓名 年龄 收入 职业 信誉度为每个顾客赋予一个标记 即是否购买计算机按该标记将顾客分类 建立分类模型新来一个顾客 按分类模型识别该顾客是否属于购买计算机类若顾客属于购买计算机的类别 则将有关新的计算机的促销材料分发给他 利用决策树进行数据分类 决策树一个类似与流程图的树结构内部接点表示一个与属性值相关的判断边表示判断的结果每个叶节点是一个类别的标识 利用决策树进行数据分类 ID3 利用决策树进行数据分类 ID3 随机判定分类器鸡蛋好坏的概率分别为6 10 4 10熵为 6 10 log 6 10 4 10 log 4 10 选择用手摇晃判定的分类器不摇晃时鸡蛋好坏的概率分别为6 8 2 8摇晃时鸡蛋好坏的概率分别为0 2 2 2熵为 6 8 log 6 8 2 8 log 2 8 8 10 0 2 log 0 2 2 2 log 2 2 2 10 选择盐水判定的分类器沉下时鸡蛋好坏的概率分别为6 6 0 6浮起时鸡蛋好坏的概率分别为0 4 4 4熵为0 利用决策树进行数据分类 ID3 算法 Generate decision tree输入 训练样本samples 候选属性集合attribute list输出 决策树步骤 创建节点N ifsamples都在同一个类Cthen返回N作为叶节点 以类C标记 ifattribute list为空then返回N作为叶节点 标记为samples中最普通的类 选择attribute list中具有最高信息增益的属性test attribute 利用决策树进行数据分类 ID3 标记节点N为test attribute foreachtest attribute中的已知值ai由节点N长出一个条件为test attribute ai的分枝 设si是samples中test attribute ai的样本的集合 ifsi为空then加上一个树叶 标记为samples中最普通的类 else加上一个由Generate decision tree si sttribute list test attribute 返回的节点 利用决策树进行数据分类 ID3 信息增益 informationgain 设S是s个样本的集合 假定类标号属性有m个不同值 定义m个不同类Ci 设si是Ci中样本数 对一个给定的样本分类所需的期望信息为 其中pi si s 利用决策树进行数据分类 ID3 设属性A有v个不同值 a1 a2 av 可以用属性A将S划分为v个子集 s1 s2 sv 其中si中样本在属性A上具有值ai 设sij是子集sj中类Ci的样本数 则根据由A划分成子集的熵或期望信息是 其中pij sij sj选择A作为分裂属性获得的信息增益为 Gain A I s1 sm E A 决策树分类举例 训练数据集 决策树分类举例 计算属性的熵 类标号属性buys computer 有两个不同值 yes no 有两个类 类yes有9个样本 类no有5个样本计算属性的熵age 40 s13 3 s23 2 I s13 s23 0 971 决策树分类举例 计算属性的熵 Gain age I s1 s2 E age 0 246Gain income 0 029Gain student 0 151Gain credit rating 0 048因此选择age作为分裂属性 决策树分类举例 分枝 age overcast 30 40 30 40 决策树分类举例 最终结果 由决策树产生规则 IFage 40 ANDcredit rating excellent THENbuys computer no IFage 40 ANDcredit rating fair THENbuys computer yes 聚类分析 Clustering 含义聚类是把一组对象按照相似性归成若干类别 即 物以类聚 它的目的是使得属于同一类别的个体之间的距离尽可能的小而不同类别上的个体间的距离尽可能的大 不同的聚类分析工具可以定义不同的规则集 从而相同的记录集合可能有不同的划分应用市场或客户分割 模式识别 基因分类 Web文档分类等 聚类算法 K Means 算法 k 平均输入 簇的数目k 包含n个对象的数据库输出 k个簇 使平方误差最小步骤 任意选择k个对象作为初始的簇中心Repeat根据簇中对象的平均值 将每个对象赋给最类似的簇更新簇的平均值 即计算每个簇中对象的平均值Until平方误差小于某个阈值或不再发生变化平方方差函数 K Means算法对噪音数据敏感 聚类算法 K Means 格言 戴手套的猫逮不着老鼠倒塌的灯塔比暗礁更危险戴手套的猫逮不着老鼠对青少年火一样的激情 岁月是最好的灭火器不掷色子 就永远别想得到六点统计数字就像超短裙 掩盖起来的部分才是关键老鼠夹上总会有免费蛋糕