资源描述
提纲(tgng)数据挖掘概览数据预处理分类（Classification）聚类（Cluster）关联(gunlin)规则（Association Rule）回归（Regression）第1页/共145页第一页，共145页。数据挖掘概览(i ln)What?数据挖掘(wju)的定义Why?数据挖掘(wju)的动机How?哪些数据可以用来挖掘(wju)？数据挖掘(wju)的主要内容第2页/共145页第二页，共145页。数据挖掘定义(dngy)什么(shn me)是数据挖掘（Data Mining）？Extraction of interesting (non-trivial, implicit, previously unknown and potentially useful) patterns or knowledge from huge amount of data 其他称谓：Knowledge discovery(mining) in database(KDD), data/pattern analysis, business intelligence, decision-support system, knowledge extraction, data archeology, data dredging and information harvesting etc.第3页/共145页第三页，共145页。模式(msh)有效性度量S i m p l i c i t yE . g . , ( a s s o c i a t i o n ) r u l e l e n g t h , ( d e c i s i o n ) t r e e s i z e C e r t a i n t yE . g . , c o n f i d e n c e , P ( A | B ) = # ( A a n d B ) / # ( B ) , c l a s s i f i c a t i o n r e l i a b i l i t y o r a c c u r a c y , r u l e s t r e n g t h , e t c . U t i l i t yP o t e n t i a l u s e f u l n e s s , e . g . , s u p p o r t ( a s s o c i a t i o n ) , n o i s e t h r e s h o l d ( d e s c r i p t i o n ) N o v e l t yN o t p r e v i o u s l y k n o w n , s u r p r i s i n g ( u s e d t o r e m o v e r e d u n d a n t r u l e s ) 第4页/共145页第四页，共145页。为何(wih)需要数据挖掘？1. 数据量大2. 缺乏(quf)理论知识3. 数据挖掘可以帮助产生新的假说或者使数据变得有意义第5页/共145页第五页，共145页。为何(wih)需要数据挖掘？We are drowning in data, but starving in knowledge Data explosion: Automated data collection tools and mature database technology lead to tremendous amounts of data accumulated and/or to be analyzed in databases, data warehouses, and other information repositories. 苦恼: 淹没在数据中 ; 不能制定合适的决策! n模式模式n趋势趋势n事实事实n关系关系n模型模型n关联规则关联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府n人口统计人口统计n生命周期生命周期第6页/共145页第六页，共145页。数据挖掘的意义(yy)数据数据挖掘挖掘辅助辅助社会社会管理管理促进促进民生民生改善改善支持支持商业商业决策决策推动推动科技科技进步进步第7页/共145页第七页，共145页。数据挖掘应用(yngyng)l银行l美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9。 l分析客户使用分销渠道的情况和分销渠道的容量 ；建立利润评测模型；客户关系优化；风险控制等l电子商务l网上商品推荐；个性化网页；自适应(shyng)网站l生物制药、基因研究lDNA序列查询和匹配；识别基因序列的共发生性 l电信l欺诈甄别；客户流失l保险、零售第8页/共145页第八页，共145页。数据挖掘应用(yngyng)Debt$40KQ QQ QQ QQ QI II I1 12 23 34 45 56 6factor 1factor 2factor n神经网络 Neural Networks Neural Networks聚类分析 Clustering ClusteringOpenAccntAdd NewProductDecreaseUsage?Time序列(xli)(xli)分析 Sequence Analysis Sequence Analysis决策树 Decision Trees Decision Trees 倾向性分析(fnx) 客户保留 客户生命周期管理 目标市场 价格弹性分析 客户细分 市场细分 倾向性分析 客户保留 目标市场 欺诈检测关联分析 Association Association 市场组合分析 套装产品分析 目录设计 交叉销售第9页/共145页第九页，共145页。数据挖掘步骤(bzhu)数 据 预 处 理数 据 清 理 （ 消 除 噪 音 或 不 一 致 数 据 ， 补 缺 ）数 据 集 成 （ 多 种 数 据 源 可 以 组 合 在 一 起 ）数 据 变 换 ( b i n h u n ) （ 规 范 化 ）数 据 规 约 （ 数 据 简 化 ）数 据 挖 掘 算 法 （ 使 用 智 能 方 法 提 取 数 据 模 式 ）分 类 、 聚 类 、 关 联 分 析 、 回 归 预 测 、 文 本 挖 掘质 量 评 估 （ 识 别 提 供 知 识 的 真 正 有 趣 模 式 ）知 识 表 示 （ 可 视 化 和 知 识 表 示 技 术 ）第10页/共145页第十页，共145页。数据质量(zhling)：为何需要数据预处理？数据质量衡量(hng ling)：准确度:correct or wrong, accurate or not完整度:not recorded unavailable一致性:some modified but some not, dangling时效性:timely update?可信度:how trustable the data are correct?可解释性:how easily the data can be understood?第11页/共145页第十一页，共145页。数据挖掘预处理的主要(zhyo)任务数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件(wnjin)数据变换规范化和聚集数据归约得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要第12页/共145页第十二页，共145页。数据(shj)清洗脏 数 据 ： 例 如 设 备 错 误 ， 人 或 者 机 器 错 误 ， 传 输 错 误 等不 完 整 性 ： 属 性 值 缺 失 或 者 只 有 聚 集 数 据例 如 ： p h o n e = “ ” ;噪 音 ： 包 含 噪 声 ( z o s h n g ) 、 错 误 或 者 异 常 值例 如 ： s a l a r y = - 1 0不 一 致 性 :例 如 ： a g e = 4 2 ， b i r t h d a y = 0 3 - 0 7 - 2 0 1 0假 值 ：例 如 ： 使 用 某 一 值 填 补 缺 失 属 性第13页/共145页第十三页，共145页。缺失(qu sh)值（Incomplete/Missing Data)数 据 并 不 总 是 完 整 的例 如 ： 数 据 库 表 中 ， 很 多 条 记 录 的 对 应 字 段 没 有 相 应 值 ， 比 如 销 售 表 中 的 顾 客 收 入引 起 空 缺 值 的 原 因设 备 异 常与 其 他 已 有 数 据 不 一 致 而 被 删 除因 为 误 解 而 没 有 被 输 入 的 数 据在 输 入 时 ， 有 些 ( y u x i ) 数 据 因 为 得 不 到 重 视 而 没 有 被 输 入对 数 据 的 改 变 没 有 进 行 日 志 记 载空 缺 值 要 经 过 推 断 而 补 上第14页/共145页第十四页，共145页。如何(rh)补充缺失值忽 略 元 组 ： 当 类 标 号 缺 少 时 通 常 这 么 做 （ 假 定 挖 掘 任 务 设 计 分 类 或 描 述 ） ， 当 每 个 属 性 缺 少 值 的 百分 比 变 化 很 大 时 ， 它 的 效 果 非 常 差 。人 工 填 写 空 缺 值 ： 工 作 量 大 ， 可 行 性 低使 用 一 个 全 局 变 量 填 充 空 缺 值 ： 比 如 使 用 u n k n o w n 或 - 使 用 属 性 的 平 均 值 填 充 空 缺 值使 用 与 给 定 ( i d n ) 元 组 属 同 一 类 的 所 有 样 本 的 平 均 值使 用 最 可 能 的 值 填 充 空 缺 值 ： 使 用 像 B a y e s i a n 公 式 或 判 定 树 这 样 的 基 于 推 断 的 方 法第15页/共145页第十五页，共145页。噪声(zoshng)数据噪声：一个测量变量中的随机错误或偏差引起不正确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致(yzh)其它需要数据清理的数据问题重复记录不完整的数据不一致(yzh)的数据第16页/共145页第十六页，共145页。如何处理(chl)噪声数据分 箱 :f i r s t s o r t d a t a a n d p a r t i t i o n i n t o ( e q u i - d e p t h ) b i n st h e n o n e c a n s m o o t h b y b i n m e a n s , s m o o t h b y b i n m e d i a n , s m o o t h b y b i n b o u n d a r i e s , e t c .聚 类d e t e c t a n d r e m o v e o u t l i e r s人 机 融 合 ( r n g h )d e t e c t s u s p i c i o u s v a l u e s a n d c h e c k b y h u m a n ( e . g . , d e a l w i t h p o s s i b l e o u t l i e r s )回 归s m o o t h b y f i t t i n g t h e d a t a i n t o r e g r e s s i o n f u n c t i o n s第17页/共145页第十七页，共145页。分箱(Binning)等 宽 E q u a l - w i d t h ( d i s t a n c e ) p a r t i t i o n i n g :D i v i d e s t h e r a n g e i n t o N i n t e r v a l s o f e q u a l s i z e : u n i f o r m g r i di f A a n d B a r e t h e l o w e s t a n d h i g h e s t v a l u e s o f t h e a t t r i b u t e , t h e w i d t h o f i n t e r v a l s w i l l b e : W = ( B A) / N .T h e m o s t s t r a i g h t f o r w a r d , b u t o u t l i e r s m a y d o m i n a t e p r e s e n t a t i o nS k e w e d d a t a i s n o t h a n d l e d w e l l .等 深 E q u a l - d e p t h ( f r e q u e n c y ) p a r t i t i o n i n g :D i v i d e s t h e r a n g e i n t o N i n t e r v a l s , e a c h c o n t a i n i n g a p p r o x i m a t e l y s a m e n u m b e r o f s a m p l e sG o o d d a t a s c a l i n gM a n a g i n g c a t e g o r i c a l a t t r i b u t e s c a n b e t r i c k y .第18页/共145页第十八页，共145页。数据平滑(pnghu)的分箱方法p r i c e 的 排 序 后 数 据 （ 单 位 ( d n w i ) ： 美 元 ） ： 4 ， 8 ， 1 5 ， 2 1 ， 2 1 ， 2 4 ， 2 5 ， 2 8 ， 3 4划 分 为 （ 等 深 的 ） 箱 ：箱 1 ： 4 ， 8 ， 1 5箱 2 ： 2 1 ， 2 1 ， 2 4箱 3 ： 2 5 ， 2 8 ， 3 4用 箱 平 均 值 平 滑 ：箱 1 ： 9 ， 9 ， 9箱 2 ： 2 2 ， 2 2 ， 2 2箱 3 ： 2 9 ， 2 9 ， 2 9用 箱 边 界 平 滑 ：箱 1 ： 4 ， 4 ， 1 5箱 2 ： 2 1 ， 2 1 ， 2 4箱 3 ： 2 5 ， 2 5 ， 3 4第19页/共145页第十九页，共145页。聚类：Cluster Analysis每个簇中的数据用其中心(zhngxn)值代替忽略孤立点先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。人工再审查这些孤立点第20页/共145页第二十页，共145页。Regression通过构造函数来符合数据(shj)变化的趋势，这样可以用一个变量预测另一个变量。线性回归 多线性回归非线性回归XY2211XXY33221XXXYxyy = x + 1X1Y1Y1第21页/共145页第二十一页，共145页。数据(shj)集成实 体 识 别元 数 据 可 帮 助 避 免 错 误知 识 图 谱属 性 冗 余相 关 分 析数 据 重 复 （ 元 组 冗 余 ）数 据 值 冲 突 的 检 测 ( j i n c ) 与 处 理表 示 、 比 例 或 编 码 不 同第22页/共145页第二十二页，共145页。数据(shj)变换（规范化）平 滑 ： 去 掉 数 据 中 的 噪 声 。 技 术 包 括 分 箱 、 回 归 、 聚 类 。聚 集 ： 对 数 据 进 行 汇 总 或 聚 集 。数 据 泛 化 （ 概 化 ） ： 使 用 概 念 ( g i n i n ) 分 层 ， 用 高 层 概 念 ( g i n i n ) 替 换 低 层 或 “ 原 始 ” 数 据 。规 范 化 ： 将 属 性 数 据 按 比 例 缩 放 ， 使 之 落 入 一 个 小 的 特 定 区 间 。 最 小 - 最 大 、 Z - S c o r e 、 按 小 数 定 标 规 范 化 。第23页/共145页第二十三页，共145页。数据(shj)变换平滑，聚集(jj)数据概化，规范化属性构造(特征构造)有限区间(q jin)的归一化：无限区间(q jin)的归一化：模糊隶属度：minmaxminvvvev11第24页/共145页第二十四页，共145页。数据(shj)规约海 量 数 据 代 表 性 数 据对 海 量 数 据 进 行 复 杂 的 数 据 分 析 ( f n x ) 和 挖 掘 将 需 要 很 长 时 间 ， 使 得 这 种 分 析 ( f n x ) 不 现 实 或 不 可 行 。数 据 归 约 技 术 可 以 用 来 得 到 数 据 集 的 归 约 表 示 ， 它 小 得 多 ， 但 仍 接 近 保 持 原 数 据 的 完 整 性 。对 归 约 后 的 数 据 集 挖 掘 将 更 有 效 ， 并 产 生 相 同 （ 或 几 乎 相 同 ） 的 结 果 。第25页/共145页第二十五页，共145页。数据(shj)规约数 据 归 约 策 略 ：（ 1 ） 数 据 立 方 体 聚 集 ： 对 数 据 立 方 体 做 聚 集 操 作（ 2 ） 属 性 子 集 选 择 ： 检 测 并 删 除 不 相 关 、 弱 相 关 或 冗 余 的 属 性 和 维 。（ 3 ） 维 度 归 约 ： 删 除 不 重 要 的 属 性（ 4 ） 数 值 归 约 ：用 规 模 较 小 的 数 据 表 示 、 替 换 或 估 计 原 始 数 据（ 5 ） 离 散 化 和 概 念 分 层 产 生属 性 的 原 始 数 值 用 区 间 ( q j i n ) 值 或 较 高 层 的 概 念 替 换第26页/共145页第二十六页，共145页。数据(shj)立方体据立方体存储多维聚集信息(xnx)，提供对预计算的汇总数据进行快速访问。如：立方体内存储季度销售额，若对年销售额感兴趣，可对数据执行聚集操作，例如sum()等。第27页/共145页第二十七页，共145页。属性子集(z j)选择通 过 删 除 不 相 关 或 冗 余 的 属 性 （ 或 维 ） 减 小 数 据 集 。其 目 标 是 找 出 最 小 属 性 集 ， 使 得 数 据 类 的 概 率 分 布 尽 可 能 地 接 近 使 用 ( s h y n g ) 所 有 属 性 得 到 的原 分 布 。通 过 穷 举 搜 索 找 出 有 属 性 的 最 佳 子 集 是 不 现 实 的 。 通 常 采 用 压 缩 搜 索 空 间 的 启 发 式 算 法 。如 贪 心 算 法 ： 从 局 部 最 优 到 全 局 最 优 。逐 步 向 前 选 择逐 步 向 后 删 除向 前 选 择 和 向 后 删 除 的 结 合决 策 树 归 纳第28页/共145页第二十八页，共145页。维度规约(guyu)维 度 归 约 使 用 数 据 编 码 或 变 换 ， 以 便 得 到 原 数 据 的 归 约 或 “ 压 缩 ” 表 示 。分 为 无 损 和 有 损 两 种 。主 要 方 法 ：串 压 缩 ： 无 损 ， 但 只 允 许 有 限 的 数 据 操 作 。小 波 变 换 （ D W T ） ： 有 损 ， 适 合 ( s h h ) 高 维 数 据 。主 成 分 分 析 （ P C A ） ： 有 损 ， 能 更 好 地 处 理 稀 疏 数 据 。第29页/共145页第二十九页，共145页。数值(shz)规约通 过 选 择 替 代 的 、 “ 较 小 的 ” 数 据 表 示 形 式 ( x n g s h ) 来 减 少 数 据 量 。可 以 分 为 参 数 方 法 和 非 参 数 方 法 。参 数 方 法 ： 回 归 （ r e g r e s s i o n ） 和 对 数 线 性 模 型非 参 数 方 法 ： 直 方 图 、 聚 类 、 抽 样第30页/共145页第三十页，共145页。离散(lsn)化离 散 ( l s n ) 化 的 用 途 ：（ 1 ） 适 应 某 些 仅 接 受 离 散 ( l s n ) 值 的 算 法 ；（ 2 ） 减 小 数 据 的 尺 度 。离 散 ( l s n ) 化 的 方 法 包 括 几 下 几 种 。（ 1 ） 等 距 分 割 ；（ 2 ） 聚 类 分 割 ；（ 3 ） 直 方 图 分 割 ；（ 4 ） 基 于 熵 的 分 割 ； （ 5 ） 基 于 自 然 属 性 的 分 割 。第31页/共145页第三十一页，共145页。抽样(chu yn)用 数 据 的 小 得 多 的 随 机 样 本 （ 子 集 ） 不 是 大 型 数 据 集 。抽 样 方 法 ( f n g f )s 个 样 本 无 放 回 简 单 随 机 抽 样s 个 样 本 有 放 回 简 单 随 机 抽 样聚 类 抽 样分 层 抽 样第32页/共145页第三十二页，共145页。分类(fn li)第33页/共145页第三十三页，共145页。分类(fn li)分类是指将数据映射到预先定义好的群组或类。在分析测试数据之前，类别就已经被确定(qudng)了，所以分类统称被称作有指导的学习。分类算法要求基于数据属性来定义类别。分类算法通常通过观察已知所属类别的数据的特征来描述类别。第34页/共145页第三十四页，共145页。分类(fn li)应用分 类 具 有 广 泛 的 应 用 ， 例 如 医 疗 诊 断 、 信 用 卡 系 统 的 信 用 分 级 、 图 像 模 式 识 别 等 。为 了 识 别 乘 客 是 否 是 潜 在 的 恐 怖 分 子 或 罪 犯 ， 机 场 安 全 摄 像 站 需 要 对 乘 客 的 脸 部 进 行 扫 描 并 辨 识 脸 部 的 基 本 模 式 （ 例 如 双 眼 间 距 、 嘴的 大 小 及 形 状 、 头 的 形 状 ） ，然 后 将 得 到 的 模 式 与 数 据 库 中 的 已 知 恐 怖 分 子 或 罪 犯 的 模 式 进 行 逐 个 ( z h g ) 比 较 ， 看 看 是 否 与 其 中 的 某 一 模 式 相 匹 配 。第35页/共145页第三十五页，共145页。分类(fn li)步骤1 建 立 一 个 模 型 ， 描 述 预 定 的 数 据 类 集 或 概 念 集数 据 元 组 也 称 作 样 本 、 实 例 或 对 象 。为 建 立 模 型 而 被 分 析 的 数 据 元 组 形 成 训 练 数 据 集 。训 练 数 据 集 中 的 单 个 元 组 称 作 训 练 样 本 ， 假 定 每 个 元 组 属 于 一 个 预 定 义 的 类 ， 由 一 个 称 作 类 标 号 。通 过 分 析 训 练 数 据 集 来 构 造 分 类 模 型 ， 可 用 分 类 规 则 、 决 策 树 或 数 学 公 式 等 形 式 提 供 。2 . 使 用 模 型 进 行 分 类首 先 评 估 模 型 （ 分 类 法 ） 的 预 测 准 确 率 。将 已 知 的 类 标 号 与 该 样 本 的 学 习 模 型 类 预 测 比 较 ( b j i o )准 确 率 等 于 测 试 集 的 样 本 中 被 模 型 正 确 分 类 的 百 分 比测 试 集 应 该 与 训 练 集 的 内 容 相 互 独 立 ， 否 则 会 出 现 过 分 适 应 的 情 况如 果 认 为 模 型 的 准 确 率 可 以 接 受 ， 就 可 以 用 它 对 类 标 号 未 知 的 数 据 元 组 或 对 象 进 行 分 类 。第36页/共145页第三十六页，共145页。（1）模型(mxng)的构建TrainingDataClassificationAlgorithmsIF rank = professorOR years 6THEN tenured = yes Classifier(Model)NAMERANKYEARSTENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no第37页/共145页第三十七页，共145页。（2）利用(lyng)模型分类ClassifierTestingDataN A M ER A N KY E A R S TE N U R E DTomA ssistant P rof2noM erlisaA ssociate P rof7noG eorge P rofessor5yesJoseph A ssistant P rof7yesUnseen Data(Jeff, Professor, 4)Tenured?第38页/共145页第三十八页，共145页。分类方法(fngf)评价预 测 的 准 确 率这 涉 及 模 型 正 确 地 预 测 新 的 或 先 前 未 见 过 的 数 据 的 类 标 号 的 能 力速 度构 造 模 型 的 速 度利 用 模 型 进 行 分 类 ( f n l i ) 的 速 度强 壮 性给 定 噪 声 数 据 或 具 有 空 缺 值 的 数 据 ， 模 型 正 确 预 测 的 能 力可 伸 缩 性当 给 定 大 量 数 据 时 ， 有 效 地 构 造 模 型 的 能 力可 解 释 性 涉 及 学 习 模 型 提 供 的 理 解 和 洞 察 的 层 次第39页/共145页第三十九页，共145页。分类器性能评价(pngji)方式准确率和召回率 - 混淆矩阵等给定一个类Cj和一个数据库元组ti，ti可能被分类器判定(pndng)为属于Cj或不属于Cj，其实ti本身可能属于Cj或不属于Cj，这样就会产生如下一些情况：真正: 判定(pndng)ti在Cj中，实际上的确在其中。假正: 判定(pndng)ti在Cj中，实际上不在其中。真负: 判定(pndng)ti不在Cj中，实际上不在其中。假负: 判定(pndng)ti不在Cj中，实际上的确在其中。准确率:P=A/(A+B)召回率:R=A/(A+C)第40页/共145页第四十页，共145页。评估分类(fn li)方法的准确性保持方法给定数据随机划分为两个集合：训练集(2/3)和测试集(1/3)训练集导出分类(fn li)法，测试集对其准确性进行评估k-折交叉验证初始数据被划分为k个不相交的，大小大致相同的子集S1,S2Sk进行k次训练和测试，第i次时，以Si做测试集，其他做训练集准确率为k次迭代正确分类(fn li)数除以初始数据集样本总数第41页/共145页第四十一页，共145页。分类(fn li)方法第42页/共145页第四十二页，共145页。基于(jy)距离的分类方法与一个类中的成员(chngyun)和另一个类中的成员(chngyun)之间的相似性相比，被映射到同一个类中的成员(chngyun)彼此之间被认为是更加相似的。相似性（距离）度量可以用来识别数据库中不同成员(chngyun)之间的“相似程度”。第43页/共145页第四十三页，共145页。基于距离的分类(fn li)方法的直观解释（a）类定义(dngy)（b）待分类(fn li)样例（c）分类结果第44页/共145页第四十四页，共145页。距离(jl)计算方法闵 可 夫 斯 基 距 离 :当 p = 2 时 ， 为 欧 几 里 得 距 离当 p = 1 时 ， 为 曼 哈 顿 距 离当 p - 时 ， 为 切 比 雪 夫 距 离向 量 内 积 ：夹 角 余 弦 ( y x i n ) ：J a c c a r d ：还 有 信 息 熵 、 相 关 系 数 等 其 他 的 度 量 方 法(|xiyi|pi1n)1/pInner(x,y) x,y xiyiicosqx1x2y1y2x12y12x22y22J(A,B)|AB|AB|第45页/共145页第四十五页，共145页。基于距离的分类(fn li)方法的一般性描述算 法 基 于 距 离 的 分 类 算 法输 入 ： 每 个 类 的 中 心 C 1 ， ， C m ； 待 分 类 的 元 组 t 。 输 出 ( s h c h ) ： 输 出 ( s h c h ) 类 别 c 。 （ 1 ） d i s t = ； / / 距 离 初 始 化（ 2 ） F O R i : = 1 t o m D O （ 3 ） I F d i s ( c i ， t ) d i s t T H E N B E G I N（ 4 ）c C i ； （ 5 ）d i s t d i s t ( C i ， t ) ； （ 6 ） E N D . 算法通过对每个元组和各个类的中心来比较，从而(cng r)可以找出他的最近的类中心，得到确定的类别标记。第46页/共145页第四十六页，共145页。K近邻(jn ln)算法（KNN）K N e a r e s t n e i g h b o r ( K N N )K N e a r e s t n e i g h b o r ( K N N )通 过 计 算 每 个 训 练 数 据 到 待 分 类 元 组 的 距 离通 过 计 算 每 个 训 练 数 据 到 待 分 类 元 组 的 距 离 ( j l )( j l ) ， 取 和 待 分 类 元 组 距 离， 取 和 待 分 类 元 组 距 离 ( j l )( j l ) 最 近 的最 近 的 K K 个 训 练 数 据 ，个 训 练 数 据 ， K K 个 数 据 中个 数 据 中哪 个 类 别 的 训 练 数 据 占 多 数 ， 则 待 分 类 元 组 就 属 于 哪 个 类 别 。哪 个 类 别 的 训 练 数 据 占 多 数 ， 则 待 分 类 元 组 就 属 于 哪 个 类 别 。训 练 样 本 用训 练 样 本 用 n n 维 数 值 属 性 描 述 。 每 个 样 本 代 表维 数 值 属 性 描 述 。 每 个 样 本 代 表 n n 维 空 间 的 一 个 点 。 所 有 的 训 练 样 本 都 放 在维 空 间 的 一 个 点 。 所 有 的 训 练 样 本 都 放 在 n n 维 模 式 空 间 中 。 给 定 一维 模 式 空 间 中 。 给 定 一个 样 本 ，个 样 本 ， k -k - 最 临 近 分 类 法 搜 索 模 式 空 间 ， 找 出 最 接 近 未 知 样 本 的最 临 近 分 类 法 搜 索 模 式 空 间 ， 找 出 最 接 近 未 知 样 本 的 k k 个 训 练 样 本 。个 训 练 样 本 。第47页/共145页第四十七页，共145页。K近邻(jn ln)算法（KNN）要 求 的 信 息要 求 的 信 息训 练训 练 ( x n l i n )( x n l i n ) 集集距 离 计 算 值距 离 计 算 值要 获 取 的 最 邻 近 的 邻 居 的 数 目要 获 取 的 最 邻 近 的 邻 居 的 数 目 k k一 个 未 知 的 记 录 进 行 分 类一 个 未 知 的 记 录 进 行 分 类计 算 与 其 它 训 练计 算 与 其 它 训 练 ( x n l i n )( x n l i n ) 记 录 之 间 的 距 离记 录 之 间 的 距 离识 别 出识 别 出 k k 个 最 近 的 邻 居个 最 近 的 邻 居使 用 最 近 邻 居 的 类 标 号 来 标 识 未 知 元 组 的 类 （使 用 最 近 邻 居 的 类 标 号 来 标 识 未 知 元 组 的 类 （ b y t a k i n g m a j o r i t y v o t eb y t a k i n g m a j o r i t y v o t e ）第48页/共145页第四十八页，共145页。K近邻(jn ln)算法（KNN）算 法 K - 近 邻 分 类 ( f n l i ) 算 法输 入 ： 训 练 数 据 T ； 近 邻 数 目 K ； 待 分 类 ( f n l i ) 的 元 组 t 。 输 出 ： 输 出 类 别 c 。 （ 1 ） N = ；（ 2 ） F O R e a c h d T D O B E G I N（ 3 ） I F | N | K T H E N（ 4 ） N = N d ； （ 5 ） E L S E（ 6 ） I F u N s u c h t h a t s i m ( t ， u ) 40000高负债工作时间5年是否是否“年收入大于￥40000”并且“高负债”的用户被认为是“高风险”；“年收入小于￥40000”但“工作时间(shjin)大于5年”的申请，是“低风险”；NYYNNY第53页/共145页第五十三页，共145页。决策树buys_computer的决策树示意(shy) Age? Credit_rating? student? yes no yesyes no 40 3040yes no fairexcellent 第54页/共145页第五十四页，共145页。决策树l决 策 树 （决 策 树 （ d e c i s i o n t r e ed e c i s i o n t r e e ）l1 9 8 61 9 8 6 年年 Q u i n l a n Q u i n l a n 提 出 了 著 名 的提 出 了 著 名 的 I D 3I D 3 算 法 。算 法 。l在在 I D 3I D 3 算 法 的 基 础 上 ，算 法 的 基 础 上 ， 1 9 9 31 9 9 3 年年 Q u i n l a nQ u i n l a n 又 提 出 了又 提 出 了 C 4 . 5C 4 . 5 算 法 。算 法 。l为 了 适 应 处 理为 了 适 应 处 理 ( c h l )( c h l ) 大 规 模 数 据 集 的 需 要 ， 后 来 又 提 出 了 若 干 改 进 的 算 法 ， 其 中大 规 模 数 据 集 的 需 要 ， 后 来 又 提 出 了 若 干 改 进 的 算 法 ， 其 中 S L I Q ( s u p e r -S L I Q ( s u p e r -v i s e d l e a r n i n g i n q u e s t )v i s e d l e a r n i n g i n q u e s t ) 和和 S P R I N T ( s c a l a b l e p a r a l l e l i z a b l e i n d u c t i o n o f d e c i s i o n S P R I N T ( s c a l a b l e p a r a l l e l i z a b l e i n d u c t i o n o f d e c i s i o n t r e e s )t r e e s ) 是 比 较 有 代 表 性 的 两 个 算 法 。是 比 较 有 代 表 性 的 两 个 算 法 。第55页/共145页第五十五页，共145页。决策树的步骤(bzhu)使 用 决 策 树 进 行 分 类 分 为 两 步 ：使 用 决 策 树 进 行 分 类 分 为 两 步 ：第第 1 1 步 ： 利 用 训 练 集 建 立 并 精 化 一 棵 决 策 树 ， 建 立 决 策 树 模 型 。 这 个 过 程 实 际 上 是 一 个 从 数 据 中 获 取 知 识 ， 进 行 机 器 学 习 的 过 程 。步 ： 利 用 训 练 集 建 立 并 精 化 一 棵 决 策 树 ， 建 立 决 策 树 模 型 。 这 个 过 程 实 际 上 是 一 个 从 数 据 中 获 取 知 识 ， 进 行 机 器 学 习 的 过 程 。第第 2 2 步 ： 利 用 生 成 完 毕 的 决 策 树 对 输 入 数 据 进 行 分 类 。 对 输 入 的 记 录步 ： 利 用 生 成 完 毕 的 决 策 树 对 输 入 数 据 进 行 分 类 。 对 输 入 的 记 录 ( j l )( j l ) ， 从 根 结 点 依 次 测 试 记 录， 从 根 结 点 依 次 测 试 记 录 ( j l )( j l ) 的 属 性 值 ， 直 到 到 达 某 个的 属 性 值 ， 直 到 到 达 某 个叶 结 点 ， 从 而 找 到 该 记 录叶 结 点 ， 从 而 找 到 该 记 录 ( j l )( j l ) 所 在 的 类 。所 在 的 类 。 第56页/共145页第五十六页，共145页。决策树算 法 递 归 执 行 的 终 止 条 件 （ 停 止算 法 递 归 执 行 的 终 止 条 件 （ 停 止 ( t n g z h )( t n g z h ) 分 支 的 条 件 ）分 支 的 条 件 ）对 于 给 定 的 节 点 ， 所 有 的 例 子 都 属 于 同 一 个 类对 于 给 定 的 节 点 ， 所 有 的 例 子 都 属 于 同 一 个 类虽 然 对 于 某 一 个 节 点 当 前 的 例 子 不 属 于 同 一 个 类 ， 但 是 已 经 没 有 属 性 可 用 来 选 择 继 续 进 行 分 支 处虽 然 对 于 某 一 个 节 点 当 前 的 例 子 不 属 于 同 一 个 类 ， 但 是 已 经 没 有 属 性 可 用 来 选 择 继 续 进 行 分 支 处理理第57页/共145页第五十七页，共145页。分裂属性(shxng)选择选 择 属 性 的 方 法选 择 属 性 的 方 法选 择 具 有 最 大 信 息 增 益 的 属 性 作 为 当 前 节 点 的 测 试 属 性选 择 具 有 最 大 信 息 增 益 的 属 性 作 为 当 前 节 点 的 测 试 属 性该 属 性 使 得 对 结 果 划 分 中 的 样 本 分 类 所 需 的 信 息 量 最 小 ， 并 反 映 划 分 的 最 小 随 机 性 。该 属 性 使 得 对 结 果 划 分 中 的 样 本 分 类 所 需 的 信 息 量 最 小 ， 并 反 映 划 分 的 最 小 随 机 性 。用 信 息 增 益 这 种 信 息 论 的 理 论 方 法 ， 使 得 对 一 个 对 象 分 类 所 需 要用 信 息 增 益 这 种 信 息 论 的 理 论 方 法 ， 使 得 对 一 个 对 象 分 类 所 需 要 ( x y o ) 的 期 望 测 试 数 目 达 到 最 小 ， 并 确 保 找 到 一 棵 简 单 的 树 。的 期 望 测 试 数 目 达 到 最 小 ， 并 确 保 找 到 一 棵 简 单 的 树 。第58页/共145页第五十八页，共145页。分裂属性(shxng)选择怎 样 计 算 信 息 增 益 （怎 样 计 算 信 息 增 益 （ i n f o r m a t i o n g a i ni n f o r m a t i o n g a i n ）信 息 增 益 被 定 义 为 原 始 分 割 的 熵 与 划 分信 息 增 益 被 定 义 为 原 始 分 割 的 熵 与 划 分 ( h u f n )( h u f n ) 以 后 各 分 割 的 熵 累 加 得 到 的 总 熵 之 间 的 差 。以 后 各 分 割 的 熵 累 加 得 到 的 总 熵 之 间 的 差 。信 息 增 益 是 指 划 分信 息 增 益 是 指 划 分 ( h u f n )( h u f n ) 前 后 进 行 正 确 预 测 所 需 的 信 息 量 之 差 。前 后 进 行 正 确 预 测 所 需 的 信 息 量 之 差 。选 择 具 有 最 高 信 息 增 益 的 属 性 作 为 当 前 节 点 的 测 试 属 性 。选 择 具 有 最 高 信 息 增 益 的 属 性 作 为 当 前 节 点 的 测 试 属 性 。第59页/共145页第五十九页，共145页。信息增益(zngy)的计算 设 S 是 有 s 个 训 练 样 本 数 据 的 集 合 ， 类 标 号 属 性 具 有 m 个 不 同 值 ， 定 义 m 个 不 同 类 C i（ i = 1 , 2 , , m ） ， s i 是 类 C i 中 的 样 本 数 ， 则 对 一 个 给 定 的 训 练 样 本 分 类 所 需 要 ( x y o ) 的 期 望 信息 为 ： miiimppsssI1221log,其中pipi是任意样本属于CiCi的概率(gil)(gil)，可用si/ssi/s来估计第60页/共145页第六十页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第61页/共145页第六十一页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买决策(juc)属性“买计算机？”。该属性分两类：买/不买S1(买)=641 S2（不买）= 383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537第第1步计算决策步计算决策(juc)属性的熵属性的熵第62页/共145页第六十二页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2步计算步计算(j sun)条件属性的熵条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉(xny)。分别计算不同属性的信息增益。第63页/共145页第六十三页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-1步计算步计算(j sun)年龄的熵年龄的熵年龄共分三个组： 青年、中年(zhngnin)、老年青年买与不买比例为128/256S1(买)=128 S2（不买）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183第64页/共145页第六十四页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-2步计算步计算(j sun)年龄的熵年龄的熵年龄共分三个组： 青年(qngnin)、中年、老年中年买与不买比例为256/0S1(买)=256 S2（不买）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0第65页/共145页第六十五页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-3步计算步计算(j sun)年龄的熵年龄的熵年龄共分三个组： 青年、中年、老年(lonin)老年(lonin)买与不买比例为125/127S1(买)=125 S2（不买）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157第66页/共145页第六十六页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第2-4步计算步计算(j sun)年龄的熵年龄的熵年龄共分三个组： 青年、中年、老年(lonin)所占比例青年组 384/1025=0.375中年组 256/1024=0.25老年(lonin)组 384/1024=0.375计算年龄的平均信息期望E（年龄） 0.25*0+ =0.6877G（年龄信息增益） =0.9537-0.6877 =0.2660 （1）第67页/共145页第六十七页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第3步计算步计算(j sun)收入的熵收入的熵收入共分三个组： 高、中、低E（收入）=0.9361收入信息(xnx)增益=0.9537-0.9361 =0.0176 (2)第68页/共145页第六十八页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第4步计算步计算(j sun)学生的熵学生的熵学生共分二个组： 学生、非学生E（学生）=0.7811年龄(ninlng)信息增益=0.9537-0.7811 =0.1726 （3）第69页/共145页第六十九页，共145页。决策树算法(sun f)计数年龄收入学生信誉归类：买计算机？归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1 老中否优买第第5步计算步计算(j su
展开阅读全文