第四章 数据预处理PPT课件

数据仓库与数据挖掘 主讲 王名扬信息与计算机工程学院 2 引言 目前 数据挖掘的研究工作大都集中在算法的探讨而忽视对数据处理的研究 事实上 数据预处理对数据挖掘十分重要 一些成熟的算法都对其处理的数据集合有一定的要求 比如数据的完整性好 冗余性小 属性的相关性小等 高质量的决策来自高质量的数据 因此数据预处理是整个数据挖掘与知识发现过程中的一个重要步骤 数据挖掘 数据库中的知识挖掘 KDD 数据挖掘 知识挖掘的核心 数据清洗 数据集成 数据库 数据仓库 Knowledge 任务相关数据 选择 数据挖掘 模式评估 第4章 数据预处理 5 数据预处理的重要性 数据预处理是数据挖掘的重要一环 而且必不可少 要使挖掘算法挖掘出有效的知识 必须为其提供干净 准确 简洁的数据 然而 当今现实世界中的数据库极易受到噪声数据 空缺数据和不一致性数据的侵扰 多数为 脏 数据 1 杂乱性 如命名规则的不同如性别 A数据库male 1 female 2B数据库male 男 female 女 C数据库male M female F 数据预处理的重要性 2 重复性 同一客观事物在数据库中存在两个以上相同的物理描述 假设某周刊有100000个订户 邮件列表中0 1 的记录是重复的 主要是因为同一个客户的名字可能有不同的写法 如 JonDoe和JohnDoe 因此 每周需要印刷和邮寄100份额外的刊物 假设每份刊物每周的邮寄和印刷费用是两美元 公司每年将至少浪费1万美元以上 数据预处理的重要性 3 不完整性 由于实际系统设计时存在的缺陷以及使用过程中的一些人为因素 数据记录可能会出现数据值的丢失或不确定 原因可能有 1 有些属性的内容有时没有 家庭收入 参与销售事务数据中的顾客信息 2 有些数据当时被认为是不必要的 3 由于误解或检测设备失灵导致相关数据没有记录下来 4 与其它记录内容不一致而被删除 5 忽略了历史数据或对数据的修改 数据预处理的重要性 4 噪声数据 数据中存在着错误或异常 偏离期望值 如 血压和身高为0就是明显的错误噪声数据的产生原因 数据采集设备有问题 在数据录入过程发生人为或计算机错误 数据传输过程中出现错误 由于命名规则或数据代码不同而引起的不一致 数据预处理的重要性 数据清理 清洗 去掉数据中的噪声 纠正不一致数据集成 将多个数据源合并成一致的数据存储 构成一个完整的数据集 如数据仓库 数据变换 转换 将一种格式的数据转换为另一格式的数据 如规范化 数据归约 消减 通过聚集 删除冗余属性或聚类等方法来压缩数据 数据预处理的常见方法 11 注意 上述的各种数据预处理方法 并不是相互独立的 而是相互关联的 如消除数据冗余既可以看成是一种形式的数据清洗 也可以看成是一种数据归约 消减 4 1数据清洗4 2数据集成和变换4 3数据归约4 4数据离散化和概念分层 第4章 14 学习目的 掌握数据清洗的处理方法 空缺 噪声 不一致 掌握各种数据归约的方法 理解数据离散化的方法 4 1数据清洗 现实世界的数据一般是脏的 不完整的和不一致的 而数据清洗试图填充空缺的值 识别孤立点 消除噪声 并纠正数据中的不一致性 因此 从如下几个方面介绍 1 空缺值 2 噪声数据 3 不一致数据 1 空缺值的处理 17 空缺值 数据并不总是完整的数据库表中 很多条记录的对应字段可能没有相应值 比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时 有些数据因为得不到重视而没有被输入对数据的改变没有进行日志记载空缺值要经过推断而补上 如何处理空缺值 1 忽略该元组 若一条记录中有属性值被遗漏了 则将该记录排除在数据挖掘之外 尤其当类标号缺少时通常这样做 假定挖掘任务涉及分类或描述 但是 当某类属性的空缺值所占百分比很大时 直接忽略元组会使挖掘性能变得非常差 如何处理空缺值 2 人工填写空缺值 工作量大 可行性低3 使用属性的平均值填充空缺值 如所有顾客的平均收入为 1000 则使用该值替换income中的空缺值 如何处理空缺值 4 使用一个全局变量填充空缺值 如 将空缺的属性值用同一个常数 如 Unknown 替换 如果空缺值都用 Unknown 替换 当空缺值较多时 挖掘程序可能误以为它们形成了一个有趣的概念 因为它们都具有相同的值 Unknown 因此 尽管该方法简单 我们并不推荐它 如何处理空缺值 5 使用与给定元组属同一类的所有样本的平均值 适用于分类数据挖掘 如将顾客按信用度分类 则用具有相同信用度的顾客的平均收入替换income中的空缺值 6 使用最可能的值填充空缺值 最常用 可以利用回归 贝叶斯计算公式或判定树归纳确定 推断出该条记录特定属性最大可能的取值 如 利用数据集中其他顾客的属性 构造一棵判定树 预测income的空缺值 2 噪声数据的处理 噪声数据 噪声 noise 是一个测量变量中的随机错误或偏差引起噪声数据的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致 如何处理噪声数据 1 分箱 binning 分箱方法通过考察 邻居 即周围的值 来平滑存储数据的值 存储的值被分布到一些 桶 或箱中 由于分箱方法参考相邻的值 因此它进行局部平滑 如何处理噪声数据 分箱的步骤 首先排序数据 并将它们分到等深 等宽 的箱中 然后可以按箱的平均值 按箱中值或者按箱的边界等进行平滑 按箱的平均值平滑 箱中每一个值被箱中的平均值替换按箱的中值平滑 箱中的每一个值被箱中的中值替换按箱的边界平滑 箱中的最大和最小值被视为箱边界 箱中的每一个值被最近的边界值替换 如何处理噪声数据 等深分箱 binning 按记录数进行分箱 每箱具有相同的记录数 每箱的记录数称为箱的权重 也称箱子的深度 示例 已知一组价格数据 15 21 24 21 25 4 8 34 28现用等深 深度为3 分箱方法对其进行平滑 以对数据中的噪声进行处理 思考 根据bin中值进行平滑的结果 结果 Bin1 8 8 8 Bin2 21 21 21 Bin3 28 28 28 在该例中 price数据首先被划分并存人等深的箱中 深度3 对于按箱平均值平滑 箱中每一个值被箱中的平均值替换 例如 箱1中的值4 8和15的平均值是9 这样 该箱中的每一个值被替换为9 对于按箱边界平滑 箱中的最大和最小值被视为箱边界 箱中的每一个值被最近的边界值替换 类似地 可以使用按箱中值平滑 此时 箱中的每一个值被箱中的中值替换 如何处理噪声数据 等宽分箱 binning 在整个属性值的区间上平均分布 即每个箱的区间范围设定为一个常量 称为箱子的宽度 示例 已知一组价格数据 15 21 24 21 25 4 8 34 28现用等宽 宽度为10 分箱方法对其进行平滑 以对数据中的噪声进行处理 结果 先排序 4 8 15 21 21 24 25 28 341 划分为等宽度箱子Bin1 4 8 Bin2 15 21 21 24 25 Bin3 28 342 根据均值进行平滑Bin1 6 6 Bin2 21 21 21 21 21 Bin3 31 31 3 根据中值进行平滑Bin1 6 6 Bin2 21 21 21 21 21 Bin3 31 314 根据边界进行平滑 Bin1 4 8 Bin2 15 25 25 25 25 Bin3 28 34 练习 已知客户收入属性income排序后的值 人民币元 800 1000 1200 1500 1500 1800 2000 2300 2500 2800 3000 3500 4000 4500 4800 5000要求 分别用等深分箱方法 箱深为4 等宽分箱方法 宽度为1000 对其进行平滑 以对数据中的噪声进行处理 1 等深分箱结果 1 首先 划分为等深的箱 箱1 800 1000 1200 1500 箱2 1500 1800 2000 2300 箱3 2500 2800 3000 3500 箱4 4000 4500 4800 5000 2 按箱的平均值平滑 结果为 箱1 1125 1125 1125 1125 箱2 1900 1900 1900 1900 箱3 2950 2950 2950 2950 箱4 4575 4575 4575 4575 1 等深分箱结果 2 按箱的中值平滑 结果为 箱1 1100 1100 1100 1100 箱2 1900 1900 1900 1900 箱3 2900 2900 2900 2900 箱4 4650 4650 4650 4650 2 按箱的边界值平滑 结果为 箱1 800 800 1500 1500 箱2 1500 1500 2300 2300 箱3 2500 2500 3500 3500 箱4 4000 4000 5000 5000 2 等宽分箱结果 1 首先 划分为等宽的箱 箱1 800 1000 1200 1500 1500 1800 箱2 2000 2300 2500 2800 3000 箱3 3500 4000 4500 箱4 4800 5000 2 按箱的平均值平滑 结果为 箱1 1300 1300 1300 1300 1300 1300 箱2 2520 2520 2520 2520 2520 箱3 4000 4000 4000 箱4 4900 4900 2 等宽分箱结果 1 按箱的中值平滑 结果为 箱1 1350 1350 1350 1350 1350 1350 箱2 2500 2500 2500 2500 2500 箱3 4000 4000 4000 箱4 4900 4900 2 按箱的边界值平滑 结果为 箱1 800 800 800 1800 1800 1800 箱2 2000 2000 3000 3000 3000 箱3 3500 3500 4000 箱4 4800 5000 如何处理噪声数据 2 聚类 Clustering 相似或相邻近的数据聚合在一起形成各个聚类集合 而那些位于聚类集合之外的数据对象 被视为孤立点 特点 直接形成簇并对簇进行描述 不需要任何先验知识 通过聚类分析查找孤立点 消除噪声 如何处理噪声数据 3 计算机和人工检查结合计算机检测可疑数据 然后对它们进行人工判断4 回归发现两个相关的变量之间的变化模式 利用回归分析方法所获得的拟合函数 帮助平滑数据及除去噪声 许多数据平滑的方法也是涉及离散化的数据归约方法 例如 上面介绍的分箱技术减少了每个属性的不同值的数量 另外 概念分层是一种数据离散化形式 也可以用于数据平滑 例如 price的概念分层可以把price的值映射到inexpensive moderately priced和expensive 从而减少了挖掘过程所处理的值的数量 注意 3 不一致数据的处理 40 不一致数据 处理不一致数据的方式 人工更正利用知识工程工具 如 如果知道属性间的函数依赖关系 可以据此查找违反函数依赖的值 数据字典 在将不同操作性数据库中的数据进行集成时 也会带来数据的不一致 如 一个给定的属性在不同的数据库中可能具有不同的名字 如姓名在一个数据库中为Bill 在另一个数据库中可能为B 对此 可根据数据字典中提供的信息 消除不一致 4 2数据集成和变换 数据挖掘所需要的海量数据集往往涉及多个数据源 因此 在信息处理之前需要合并这些数据源存储的数据 如果原始数据的形式不适合信息处理算法的需要 就要进行数据变换 1 数据集成 将来自多个数据源的数据合并到一起 2 数据变换 对数据进行规范化操作 将其转换成适合于数据挖掘的形式 1 数据集成 43 数据集成 数据集成将多个数据源中的数据整合到一个一致的存储中 这些源可以是关系型数据库 数据立方体或一般文件 它需要统一原始数据中的所有矛盾之处 如字段的 同名异义 异名同义 单位不统一 字长不一致等 44 数据集成 集成过程中需要注意的问题模式集成问题 冗余问题 数据值冲突检测与消除 45 1 模式集成问题 模式集成 整合不同数据源中的元数据 进行实体识别 匹配来自不同数据源的现实世界的实体如 如何确信一个数据库中的customer id和另一个数据库中的cust number是同一实体 通常 数据库的数据字典和数据仓库的元数据 可帮助避免模式集成中的错误 46 2 数据冗余问题 数据冗余问题 同一属性值不同的数据库中会有不同的字段名 一个属性可以由另外一个表导出 如 一个顾客数据表中的平均月收入属性 可以根据月收入属性计算出来 47 2 数据冗余问题 数据冗余问题 有些冗余可以被相关分析检测到 如果变量A B间具有较高的相关系数 表明A或B可以作为冗余而去掉 除了检查属性是否冗余外 还要检查记录行的冗余 48 3 数据值冲突问题 数据值冲突对现实世界的同一实体 来自不同数据源的属性值可能不同 产生的原因 表示 比例或编码不同 如 重量属性在一个系统中可能以公制单位存放 而在另一系统中可能以英制单位存放 同一商品的价格属性值不同地域采用不同价格单位 不同学校的成绩单可能以百分制 五分制及其他等级制来存放等等 2 数据变换 50 数据变换 数据变换 将数据转换成适合数据挖掘的形式 涉及内容 1 平滑 去掉数据中的噪声 将连续的数据离散化 分箱聚类回归 2 聚集 对数据进行汇总和聚集Avg count sum min max 如 每天销售额 数据 可以进行聚集操作以获得每月或每年的总额 可用来构造数据立方体 51 数据变换 数据变换 将数据转换成适合数据挖掘的形式 涉及内容 3 数据概化 使用概念分层 用更抽象 更高层次 的概念来取代低层次或数据层的数据对象如 街道属性 可以泛化到更高层次的概念 如城市 国家 同样 对于数值型的属性 如年龄属性 可以映射到更高层次的概念 如年轻 中年和老年 52 数据变换 数据变换 将数据转换成适合数据挖掘的形式 涉及内容 4 规范化 将数据按比例进行缩放 使之落入一个特定的区域 以消除数值型属性因大小不一而造成的挖掘结果的偏差 如将工资收入属性值映射到 1 0 1 0 的范围内 常用的方法 最小 最大规范化 零 均值规范化 z score规范化 小数定标规范化 规格化的目的 是将一个属性取值范围影射到一个特定范围之内 以消除数值性属性因大小不一而造成挖掘结果的偏差 数据变换 规范化 在正式进行数据挖掘之前 尤其是使用基于对象距离的挖掘算法时 必须进行数据的规格化 如对于一个顾客信息数据库中年龄属性或工资属性 由于工资属性的取值比年龄属性的取值要大得多 若不进行规格化处理 基于工资属性的距离计算值将远远超过基于年龄属性的计算值 这就意味着工资属性的作用在整个数据对象的距离计算中被错误放大了 数据变换 规范化 55 数据变换 规范化 数据规范化 将数据按比例缩放至一个小的特定区间 1 最小 最大规范化 假定minA和maxA分别为属性A的最小和最大值 则通过下面公式将A的值映射到区间 new min new max 中的v 例 假定属性income的最小与最大值分别为 12000和 98000 可根据最小 最大规范化方法将其范围映射到 0 1 如 属性值 73600将变换为 73600 12000 98000 12000 1 0 0 0 716 56 数据变换 规范化 2 z score规范化 零均值规范化 将属性A的值根据其平均值和标准差进行规范化 常用于属性最大值与最小值未知 或使用最小最大规范化方法会出现异常数据的情况 其中 meanA standard devA分别为属性A取值的均值和标准差 例 假定属性income的平均值与标准差分别为 54000和 16000 使用z score规范化 则属性值 73600将变换为 73600 54000 16000 1 225 57 数据变换 规范化 3 小数定标规范化 通过移动属性A的小数点位置进行规范化 小数点的移动依赖于A的最大绝对值 例 假定A的取值范围 986 917 则A的最大绝对值为986 为使用小数定标规范化 用1000 即j 3 除每个值 这样 986被规范化为 0 986 其中 j是使Max v 1的最小整数 规范化将原来的数据改变很多 特别是上述的后两种方法 有必要保留规范化参数 如平均值和标准差 如果使用z score规范化 以便将来的数据可以用一致的方式规范化 注意 59 数据变换 数据变换 将数据转换成适合数据挖掘的形式 涉及内容 5 属性构造 利用已有属性集构造出新的属性 并加入到现有属性集中以帮助挖掘更深层次的模式知识 提高挖掘结果的准确性 如 根据宽 高属性 可以构造一个新属性 面积 4 3数据归约 对大规模数据库内容进行复杂的数据分析常需要消耗大量的时间 使得这样的分析变得不现实和不可行 数据归约 datareduction 数据消减或约简 是在不影响最终挖掘结果的前提下 缩小所挖掘数据的规模 数据归约技术可以用来得到数据集的归约表示 它小得多 但仍接近保持原数据的完整性 对归约后的数据集进行挖掘可提高挖掘的效率 并产生相同 或几乎相同 的结果 4 3数据归约 数据归约的标准 用于数据归约的时间不应当超过或 抵消 在归约后的数据集上挖掘节省的时间 归约得到的数据比原数据小得多 但可以产生相同或几乎相同的分析结果 4 3数据归约 数据归约的策略如下 数据立方体聚集 维归约 数据压缩 数值归约 离散化和概念分层生成 1 数据立方体聚集 64 数据立方体聚集 2 维归约 66 维归约 维归约 主要用于检测并删除不相关 弱相关或冗余的属性维用于数据分析的数据可能包含数以百计的属性 其中大部分可能与挖掘任务不相关 是冗余的 如 分析顾客是否会在商场购买mp3播放器 诸如顾客的电话号码等属性多半是不相关的 维归约通过删除不相关的属性 或维 而有效减少数据库的规模 最常用的方法 属性子集选择 67 维归约 属性子集选择 目标 找出最小属性集 确保新数据集的概率分布尽可能接近原数据集的概率分布 如何找出原属性的一个 好的 子集d个属性有2d个可能的子集 穷举搜索找出属性的最佳子集可能是不现实的 特别是当d的数目很大时 68 维归约 属性子集选择 启发式算法 对于属性子集选择 通常使用压缩搜索空间的启发式算法 它们的策略是做局部最优选择 期望由此导致全局最优解 69 维归约 属性子集选择 常用的启发式方法 1 逐步向前选择 该过程由空属性集开始 选择原属性集中最好的属性 并将它添加到该集合中 在其后的每一次迭代 将原属性集剩下的属性中的最好的属性添加到该集合中 如 遗传算法是一种基于生物进化论和分子遗传学的全局随机搜索算法 70 维归约 属性子集选择 常用的启发式方法 2 逐步向后删除 由整个属性集开始 每一步都删除尚在属性集中的最坏属性 直到无法选择出最坏属性或满足一定的阈值为止 如 粗糙集理论 利用定义的数据集合U上的等价关系对U进行划分 对于数据表来说 这种等价关系可以是某个属性 或者是几个属性的集合 因此 按照不同属性的组合就把数据表划分成不同的基本类 在这些基本类的基础上进一步求得最小约简集 71 维归约 属性子集选择 常用的启发式方法 3 向前选择和向后删除的结合 将向前选择和向后删除方法结合在一起 每一步选择一个最好的属性 并在剩余属性中删除一个最坏的属性 72 维归约 属性子集选择 常用的启发式方法 4 判定树归纳 在判定树的每个节点 算法选择 最好 的属性 将数据划分成类 当判定树归纳用于属性子集选择时 不出现在树中的所有属性假定是不相关的 出现在判定树中的属性形成归约后的属性子集 3 数据压缩 75 数据压缩 数据压缩就是利用数据编码或数据转换将原来的数据集合压缩为一个较小规模的数据集合 压缩算法分为两类 无损压缩 loseless 可以不丢失任何信息地还原压缩数据 如 字符串压缩有损压缩 lossy 只能重新构造原数据的近似表示 如 音频 视频压缩 76 77 数据压缩 两类 1 无损压缩 指使用压缩后的数据进行重构 或者叫做还原 解压缩 重构后的数据与原来的数据完全相同 即 数据经过压缩后 信息不受损失 还能完全恢复到压缩前的原样 压缩软件 Zip或RAR 78 数据压缩 两类 2 有损压缩 又称破坏型压缩 即将次要的信息数据压缩掉 牺牲一些质量来减少数据量 使压缩比提高 常用于压缩声音 图像以及视频 音频能够在没有察觉的质量下降情况下实现10 1的压缩比 视频能够在稍微观察质量下降的情况下实现如300 1这样非常大的压缩比 常见算法 JPEG MPEG MP3等 算法机理 小波变换或主成份分析 4 数值归约 80 数值归约 数值归约 通过选择替代的 较小的数据表示形式来减少数据量 1 有参方法 通常使用一个参数模型来评估数据 该方法只需要存储参数 而不是实际数据 能大大减少数据量 但只对数值型数据有效 如 线性回归方法 最小二乘法 Y X 81 数值归约 数值归约 通过选择替代的 较小的数据表示形式来减少数据量 2 无参方法 常见的有 直方图 聚类 取样 82 1 直方图 直方图 根据属性的数据分布将其分成若干不相交的区间 每个区间的高度与其出现的频率成正比 例 下面的数据是AllElectronics通常销售的商品的单价表 已排序 1 1 5 5 5 5 5 8 8 10 10 10 10 12 14 14 14 15 15 15 15 15 15 18 18 18 18 18 18 18 18 20 20 20 20 20 20 20 21 21 21 21 25 25 25 25 25 28 28 30 30 30 试用直方图表示 以压缩数据 83 1 直方图 频率 值对应关系图 84 2 聚类 聚类 将原数据集划分成多个群或聚类 原则 同类中的数据彼此相似 不同类中的数据彼此不相似 相似 通常用空间距离度量聚类的有效性依赖于实际数据的内在规律 85 3 取样 取样 抽样 允许用数据的较小随机样本 子集 表示大的数据集 取样方法 不放回简单随机取样 SimpleRandomSamplingWithoutReplacement SRSWOR 放回简单随机取样 SimpleRandomSamplingWithReplacement SRSWR 聚类取样 先聚类 后取样分层取样 先分层 后取样 取样 SRS SRSWOR 简单随机选样 不回放 SRSWR 简单随机选样 回放 87 取样 聚类采样 首先将大数据集D划分为M个互不相交的聚类 然后再从M个类中的数据对象分别进行随机抽取 可最终获得聚类采样的数据子集 聚类采样方法示意图 88 聚类取样 89 取样 分层取样 首先将大数据集D划分为互不相交的层 然后对每一层简单随机选样得到D的分层选样 如 根据顾客的年龄组进行分层 然后再在每个年龄组中进行随机选样 从而确保了最终获得分层采样数据子集中的年龄分布具有代表性 90 分层取样 分层采样方法示意图 4 4数据离散化和概念分层 三种类型的属性值 标称型 名称型 名义型 数值来自于无序集合 如性别 地名 人名等 序数型 数值来自于有序集合 如奖学金的等级 职称分布等 连续型 实数值 如温度 体重等 离散化技术 通过将属性 连续取值 阈值范围分为若干区间 来帮助消减一个连续 取值 属性的取值个数 如 将气温划分为 冷 正常 热 4 4数据离散化和概念分层 概念分层 概念分层定义了一组由低层概念到高层概念集的映射 允许在各种抽象级别上处理数据 从而在多个抽象层上发现知识 用较高层概念替换低层次 如年龄的数值 的概念 以此来减少取值个数 虽然一些细节数据在泛化过程中消失了 但这样所获得的泛化数据或许更易于理解 更有意义 另外 在消减后的数据集上进行信息处理显然效率更高 概念分层结构可以用树来表示 树的每个节点代表一个概念 93 概念分层 离散化方法 常用的离散化方法 1 分箱 属性的值可以通过将其分配到各分箱中而将其离散化 利用每个分箱的均值或中数替换每个分箱中的值 利用均值或中数进行平滑 循环应用这些操作处理每次操作结果 就可以获得一个概念层次树 离散化方法 常用的离散化方法 2 直方图 等宽直方图中 将数据划分成相等的部分或区间 如 0 100 100 200 200 300 等深直方图 值被划分使得每一部分包括相同个数的样本 离散化方法 常用的离散化方法 3 聚类分析 聚类算法可以将数据集划分为若干类或组 每个类构成了概念分层树的一个节点 每个类还可以进一步分解为若干子类 从而构造更低水平的层次 当然类也可以合并起来构成更高层次的概念水平 4 基于熵的离散化 熵是一种信息度量的方法5 通过自然划分分段 基于熵的离散化 思想 考虑类别信息 递归计算信息熵 产生分层的离散化 I S 初始不确定性 基于熵的离散化 思想 考虑类别信息 递归计算信息熵 产生分层的离散化 给定一个数据元组的集合S 基于熵对S离散化的方法如下 1 属性A中的每个取值可被认为是一个潜在的区间边界或阈值T 例如 A的取值v可以将样本S划分为分别满足A v和A v两个子集 这样就创建了一个二元离散化 2 对于数据集S 根据所划分子集而获得的最大熵增益来选择阈值 划分后数据集S提供的信息如下 E A 学习属性A之后的不确定性 基于熵的离散化 其中S1和S2分别对应于S中满足条件 A T与A T 的样本 对给定的集合 熵函数Ent根据集合中样本的类分布来计算 例如 给定m个不同类别 S1的熵就是 其中pi为类i在S1中出现的概率 等于S1中类i的样本除以S1中样本的总行数 同理 计算Ent S2 3 确定阈值的过程递归的用于所得到的每个划分 直到满足某个终止条件 如 Ent S I S T 信息增益不能低于 基于熵的离散化 与迄今为止提到的其他方法不同 基于熵的离散化使用了类别信息 这使得它更有可能将区间边界定义在准确位置 有助于提高分类的准确性 此处用到的信息增益和信息熵也用于决策树归纳 自然划分分段 思想 将数值区域划分为相对一致的 易于阅读的 看上去更直观或自然的区间 聚类分析产生的概念分层可能会将一个工资区间划分为 51263 98 60872 34 而通常数据分析人员希望看到划分的形式为 50000 60000 自然划分的3 4 5规则常可以将数值数据划分为相对一致和 自然 的区间 一般的 根据最重要的数字上的值区域 递归的和逐层的将给定的数据区域划分为3 4或5个等宽区间 自然划分的3 4 5规则 规则的划分步骤 如果一个区间最高有效位上跨越3 6 7或9个不同的值 就将该区间划分为3个等宽子区间 7 2 3 2 如果一个区间最高有效位上跨越2 4 或8个不同的值 就将该区间划分为4个等宽子区间 如果一个区间最高有效位上跨越1 5 或10个不同的值 就将该区间划分为5个等宽子区间 将该规则递归的应用于每个子区间 产生给定数值属性的概念分层 自然划分的3 4 5规则 规则的划分步骤 对于数据集中出现的最大值和最小值的极端分布 为了避免上述方法出现的结果扭曲 可以在顶层分段时 选用一个大部分的概率空间 e g 5 95 例如 在资产数据集中 少数人的资产可能比其他人高几个数量级 如果按照最高资产值进行分段 可能导致高度倾斜的分层 此时 可以在顶层分段时 选用一个大部分的概率空间 e g 5 95 越出顶层分段的特别高和特别低的部分采用类似的规则划分方法形成单独的区间 示例 3 4 5规则 假定AllElectronics所有分部1999年的利润覆盖了一个很宽的区间 从 351 00 到4700 要求利用3 4 5规则自动构造利润属性的一个概念层次树 示例 3 4 5规则 思路 设在上述范围取值为5 至95 的区间为 159 至1838 应用3 4 5规则的具体步骤如下 1 根据以上信息 在利润数据集中最小和最大值分别为 MIN 351 MAX 4700 而根据以上分析 对于分段的顶层或第一层 要考虑的最低 5 和最高 95 的值是 LOW 159 HIGH 1838 2 依据LOW和HIGH及其取值范围 确定最高有效位为1000 LOW按1000 美元向下取整 得到LOW 1000 HIGH按1000 向上取整 得到 HIGH 2000 示例 3 4 5规则 3 由于该区间在最高有效位上跨越了3个值 即 2000 1000 1000 3 根据3 4 5规则 该区间被划分成3个等宽区间 1000 0 0 1000 1000 2000 这代表分层结构的最顶层 示例 3 4 5规则 4 现在 考察原数据集中MIN和MAX值与最高层区间的联系 由于MIN值落在区间 1000 0 因此调整左边界 对MIN取整后的 400 所以第一个区间调整为 400 0 而由于MAX值不在最后一个区间 1000 2000 中 因此需新建一个区间 最右边区间 对MAX取整后得5000 因此新区间为 2000 5000 因此最终 概念树分层结构的最顶层包含4个区间 400 0 0 1000 1000 2000 2000 5000 示例 3 4 5规则 5 对上述每个区间递归应用3 4 5规则 形成分层结构的下一个较低层 第一个区间 400 0 划分为4个子区间 400 300 300 200 200 100 100 0 第二个区间 0 1000 划分为5个子区间 0 200 200 400 400 600 600 800 800 1000 第三个区间 1000 2000 划分为5个子区间 1000 1200 1200 1400 1400 1600 1600 1800 1800 2000 第四个区间