fengchupc的博客

习题答案 数据结构与算法分析java语言描述第二版 英文版的

数据结构与算法分析—Java语言描述 中文版

目录 第一章 引言 .......................................................................................................................................................... 8 1.1 什么激发数据挖掘？为什么它是重要的？.............................................................................................. 8 1.2 什么是数据挖掘？ ................................................................................................................................... 10 1.3 数据挖掘——在何种数据上进行？........................................................................................................ 12 1.3.1 关系数据库........................................................................................................................................ 13 1.3.2 数据仓库............................................................................................................................................ 14 1.3.3 事务数据库........................................................................................................................................ 16 1.3.4 高级数据库系统和高级数据库应用................................................................................................ 16 1.4 数据挖掘功能——可以挖掘什么类型的模式？.................................................................................... 18 1.4.1 概念/类描述：特征和区分............................................................................................................... 19 1.4.2 关联分析............................................................................................................................................ 19 1.4.3 分类和预测........................................................................................................................................ 20 1.4.4 聚类分析............................................................................................................................................ 20 1.4.5 局外者分析........................................................................................................................................ 21 1.4.6 演变分析............................................................................................................................................ 21 1.5 所有模式都是有趣的吗？........................................................................................................................ 21 1.6 数据挖掘系统的分类................................................................................................................................ 22 1.7 数据挖掘的主要问题................................................................................................................................ 23 1.8 总结 ........................................................................................................................................................... 25 习题.................................................................................................................................................................. 26 第二章数据仓库和数据挖掘的OLAP 技术................................................................................................... 29 2.1 什么是数据仓库?...................................................................................................................................... 29 2.2.1 操作数据库系统与数据仓库的区别................................................................................................ 30 2.1.2 但是，为什么需要一个分离的数据仓库........................................................................................ 31 2.2 多维数据模型........................................................................................................................................... 32 2.2.1 由表和电子数据表到数据方............................................................................................................ 32 2.2.2 星形、雪花和事实星座：多维数据库模式.................................................................................... 34 2.2.3 定义星形、雪花和事实星座的例子................................................................................................ 36 2.2.3 度量：它们的分类和计算................................................................................................................ 37 2.2.5 引入概念分层.................................................................................................................................... 38 2.2.6 多维数据模型上的OLAP 操作........................................................................................................ 40 2.2.7 查询多维数据库的星形网查询模型................................................................................................ 42 2.3 数据仓库的系统结构................................................................................................................................ 42 2.3.1 数据仓库的设计步骤和结构............................................................................................................ 42 2.3.2 三层数据仓库结构............................................................................................................................ 44 2.3.3 OLAP 服务器类型：ROLAP、MOLAP、HOLAP 的比较............................................................... 45 2.4 数据仓库实现........................................................................................................................................... 46 2.4.1 数据方的有效计算............................................................................................................................ 47 2.4.2 索引OLAP 数据................................................................................................................................ 50 2.4.3 OLAP 查询的有效处理...................................................................................................................... 52 2.4.4 元数据存储........................................................................................................................................ 53 2.5 数据方技术的进一步发展........................................................................................................................ 54 2.5.1 数据方发现驱动的探查.................................................................................................................... 54 2.5.2 多粒度上的复杂聚集: 多特征方..................................................................................................... 56 2.5.3 其它进展............................................................................................................................................ 57 2.6 由数据仓库到数据挖掘............................................................................................................................ 58 2.6.1 数据仓库的使用................................................................................................................................ 58 2.6.2 由联机分析处理到联机分析挖掘.................................................................................................... 59 2.7 总结 ........................................................................................................................................................... 60 习题.................................................................................................................................................................. 61 第三章数据预处理 ............................................................................................................................................ 64 3.1 为什么要预处理数据？ ............................................................................................................................ 64 3.2 数据清理 ................................................................................................................................................... 66 3.2.1 遗漏值................................................................................................................................................ 66 3.2.2 噪音数据............................................................................................................................................ 66 3.3 数据集成和变换...................................................................................................................................... 68 3.3.1 数据集成............................................................................................................................................ 68 3.3.2 数据变换............................................................................................................................................ 69 3.4 数据归约.................................................................................................................................................. 70 3.4.1 数据方聚集...................................................................................................................................... 71 3.4.2 维归约................................................................................................................................................ 72 3.4.3 数据压缩............................................................................................................................................ 73 3.4.4 数值归约.......................................................................................................................................... 75 3.5 离散化和概念分层产生.......................................................................................................................... 79 3.5.1 数值数据的离散化和概念分层产生................................................................................................ 80 3.5.2 分类数据的概念分层产生.............................................................................................................. 83 3.6 总结 ........................................................................................................................................................... 84 习题.................................................................................................................................................................. 85 第四章数据挖掘原语、语言和系统结构...................................................................................................... 87 4.1 数据挖掘原语：什么定义数据挖掘任务？ .......................................................................................... 87 4.1.1 任务相关的数据.............................................................................................................................. 89 4.1.2 要挖掘的知识的类型...................................................................................................................... 89 4.1.3 背景知识：概念分层...................................................................................................................... 90 4.1.4 兴趣度度量...................................................................................................................................... 92 4.1.5 发现模式的提供和可视化.............................................................................................................. 94 4.2 一种数据挖掘查询语言.......................................................................................................................... 95 4.2.1 任务相关数据说明的语法.............................................................................................................. 96 4.2.2 说明挖掘知识类型的语法.............................................................................................................. 97 4.2.3 概念分层说明的语法...................................................................................................................... 99 4.2.4 兴趣度度量说明的语法.................................................................................................................... 99 4.2.5 模式提供和可视化说明的语法.................................................................................................... 100 4.2.6 汇集 —— 一个DMQL 查询的例子........................................................................................ 100 4.2.7 其它数据挖掘语言和数据挖掘原语的标准化............................................................................ 101 4.3 基于数据挖掘查询语言设计图形用户界面........................................................................................ 102 4.4 数据挖掘系统的结构............................................................................................................................ 102 4.5 总结........................................................................................................................................................ 103 第五章概念描述：特征与比较...................................................................................................................... 107 5.1 什么是概念描述？................................................................................................................................ 107 5.2 数据泛化和基于汇总的特征................................................................................................................ 108 5.2.1 面向属性归纳................................................................................................................................ 108 5.2.2 面向属性归纳的有效实现...........................................................................................................111 5.2.3 导出泛化的表示............................................................................................................................ 112 5.3 解析特征: 属性相关性分析................................................................................................................. 115 5.3.1 为什么进行属性相关性分析? ...................................................................................................... 115 5.3.2 属性相关分析方法........................................................................................................................ 115 5.4 挖掘类比较：区分不同的类................................................................................................................ 118 5.4.1 类比较方法和实现........................................................................................................................ 118 5.4.2 类比较描述的表示.......................................................................................................................... 120 5.4.3 类描述: 提供特征和比较........................................................................................................... 121 5.5 在大型数据库中挖掘描述统计度量.................................................................................................... 123 5.5.1 度量中心趋势................................................................................................................................ 123 5.5.2 度量数据的发散............................................................................................................................ 124 5.5.3 基本统计类描述的图形显示........................................................................................................ 126 5.6 讨论........................................................................................................................................................ 128 5.6.1 概念描述：与典型的机器学习方法比较.................................................................................... 128 5.6.2 概念描述的增量和并行挖掘........................................................................................................ 129 5.7 总结........................................................................................................................................................ 129 第六章挖掘大型数据库中的关联规则.......................................................................................................... 132 6.1 关联规则挖掘........................................................................................................................................ 132 6.1.1 购物篮分析：一个引发关联规则挖掘的例子............................................................................ 132 6.1.2 基本概念........................................................................................................................................ 133 6.1.3 关联规则挖掘：一个路线图........................................................................................................ 133 6.2 由事务数据库挖掘单维布尔关联规则.................................................................................................. 134 6.2.1 Apriori 算法：使用候选项集找频繁项集................................................................................... 135 6.2.2 由频繁项集产生关联规则............................................................................................................ 138 6.2.3 提高Apriori 的有效性.................................................................................................................. 138 6.2.4 不产生候选挖掘频繁项集............................................................................................................ 140 6.2.5 冰山查询........................................................................................................................................ 142 6.3 由事务数据库挖掘多层关联规则........................................................................................................ 143 6.3.1 多层关联规则................................................................................................................................ 143 6.3.2 挖掘多层关联规则的方法............................................................................................................ 144 6.3.3 检查冗余的多层关联规则............................................................................................................ 146 6.4 由数据库和数据仓库挖掘多维关联规则............................................................................................ 147 6.4.1 多维关联规则................................................................................................................................ 147 6.4.2 使用量化属性的静态离散化挖掘多维关联规则........................................................................ 148 6.4.3 挖掘量化关联规则........................................................................................................................ 148 6.4.4 挖掘基于距离的关联规则............................................................................................................ 150 6.5 由关联挖掘到相关分析...................................................................................................................... 151 6.5.1 强关联规则不一定是有趣的：一个例子.................................................................................... 151 6.5.2 由关联分析到相关分析................................................................................................................ 151 6.6 基于限制的关联挖掘............................................................................................................................ 152 6.6.1 关联规则的元规则制导挖掘........................................................................................................ 153 6.6.2 用附加的规则限制制导的挖掘.................................................................................................... 154 6.7 总结 ......................................................................................................................................................... 156 第七章分类和预测 .......................................................................................................................................... 162 7.1 什么是分类？什么是预测？ ................................................................................................................ 162 7.2 关于分类和预测的问题........................................................................................................................ 163 7.2.1 准备分类和预测数据.................................................................................................................... 164 7.2.2 比较分类方法。............................................................................................................................ 164 7.3 用判定树归纳分类................................................................................................................................ 164 7.3.1 判定树归纳.................................................................................................................................... 165 7.3.2 树剪枝............................................................................................................................................ 168 7.3.3 由判定树提取分类规则.................................................................................................................. 169 7.3.4 基本判定树归纳的加强.................................................................................................................. 169 7.3.5 判定树归纳的可规模性.................................................................................................................. 170 7.3.6 集成数据仓库技术和判定树归纳.................................................................................................. 171 7.4 贝叶斯分类............................................................................................................................................ 172 7.4.1 贝叶斯定理.................................................................................................................................... 172 7.4.2 朴素贝叶斯分类............................................................................................................................ 173 7.4.3 贝叶斯信念网络............................................................................................................................ 174 7.4.4 训练贝叶斯信念网络.................................................................................................................... 175 7.5 后向传播分类........................................................................................................................................ 176 7.5.1 多路前馈神经网络.......................................................................................................................... 176 7.5.2 定义网络拓扑................................................................................................................................ 177 7.5.3 后向传播........................................................................................................................................ 177 7.5.4 后向传播和可解释性.................................................................................................................... 181 7.6 基于源于关联规则挖掘概念的分类.................................................................................................... 182 7.7 其它分类方法........................................................................................................................................ 183 7.7.1 k-最临近分类................................................................................................................................. 183 7.7.2 基于案例的推理............................................................................................................................ 184 7.7.3 遗传算法.......................................................................................................................................... 184 7.7.4 粗糙集方法.................................................................................................................................... 185 7.7.5 模糊集方法.................................................................................................................................... 185 7.8 预测........................................................................................................................................................ 186 7.8.1 线性和多元回归............................................................................................................................ 186 7.8.2 非线性回归.................................................................................................................................... 188 7.8.3 其它回归模型................................................................................................................................ 188 7.9 分类的准确性......................................................................................................................................... 188 7.9.1 评估分类法的准确率.................................................................................................................... 189 7.9.2 提高分类法的准确率.................................................................................................................... 189 7.9.3 准确率确定分类法够吗？ ............................................................................................................ 190 7.10 总结...................................................................................................................................................... 191 第八章聚类分析 ............................................................................................................................................ 196 8．1 什么是聚类分析？............................................................................................................................... 196 8．2 聚类分析中的数据类型....................................................................................................................... 197 8.2.2 区间标度（Interval-Scaled）变量................................................................................................. 198 8.2.3 二元变量（binary variable） ......................................................................................................... 199 8.2.4 标称型、序数型和比例标度型变量.............................................................................................. 200 8.2.5 混合类型的变量.............................................................................................................................. 201 8.3 主要聚类方法的分类.............................................................................................................................. 201 8.4 划分方法（PARTITIONING METHODS） ................................................................................................... 202 8.4.1 典型的划分方法：k-Means 和k-Medoids...................................................................................... 203 8.4.2 大规模数据库中的划分方法：从k-medoids 到CLARANS .......................................................... 205 8.5 层次方法 ................................................................................................................................................. 206 8.5.1 凝聚的和分裂的层次聚类.............................................................................................................. 206 8．5．2 BIRCH：利用层次方法的平衡迭代约减和聚类（Balanced Iterative Reducing and Clustering Using Hierarchies）............................................................................................................................................. 207 8．5．3 CURE：利用代表点聚类(clustering using representative) ....................................................... 208 8.5.4 Chameleon（变色龙）: 一个利用动态模型的层次聚类算法...................................................... 208 8.6 基于密度的方法..................................................................................................................................... 209 8.6.1 DBSCAN:一个基于密度和高密度的连结区域的聚类算法........................................................... 210 8.6.2 OPTICS：通过对象排序识别聚类结构（Ordering Points to Identify the Clustering Structure） 210 8．6．3 DENCLUE：基于密度分布函数的聚类................................................................................... 211 8.7 基于网格的方法..................................................................................................................................... 212 8.7.1 STING：统计信息网格(STatistical INformation Grid).................................................................... 212 8.7.2 WaveCluster：采用小波变换聚类................................................................................................... 213 8.7.3 CLIQUE：聚类高维空间................................................................................................................. 214 8.8 基于模型的聚类方法.............................................................................................................................. 215 8.9 孤立点(OUTLIER)分析............................................................................................................................. 217 8.9.1 基于统计的孤立点探测.................................................................................................................. 217 8.9.2 基于距离的孤立点探测................................................................................................................... 218 8.9.3 基于偏离的孤立点探测.................................................................................................................. 219 8.10 总结 ....................................................................................................................................................... 220 第九章复杂类型数据的挖掘.......................................................................................................................... 223 9.1 复杂数据对象的多维分析和描述性挖掘（DESCRIPTIVE MINING）..................................................... 223 9．1．1 结构数据概化............................................................................................................................ 223 9．1．2 空间和多媒体数据概化中的聚集和近似计算........................................................................ 224 9．1．3 对象标识和类/子类层次的概化............................................................................................... 224 9．1．4 类复合层次概化........................................................................................................................ 225 9．1．5 对象立方体的构造与挖掘........................................................................................................ 225 9．1．6 对规划数据库的概化挖掘......................................................................................................... 225 9．2 空间数据库挖掘.................................................................................................................................. 227 9．2．1 空间数据立方体构造和空间OLAP ......................................................................................... 227 9．2．2 空间关联分析............................................................................................................................ 229 9．2．3 空间聚类方法............................................................................................................................ 230 9．2．4 空间分类和空间趋势分析........................................................................................................ 230 9．2．5 光栅数据库挖掘........................................................................................................................ 230 9．3 多媒体数据挖掘.................................................................................................................................. 230 9．3．1 多媒体数据的相似搜索............................................................................................................ 231 9．3．2 多媒体数据的多维分析............................................................................................................ 231 9．3．3 多媒体数据的分类和预测分析................................................................................................ 232 9．3．4 多媒体数据中的关联规则挖掘................................................................................................ 232 9．4 时序和序列数据的挖掘....................................................................................................................... 233 9．4．1 趋势分析.................................................................................................................................... 233 9．4．2 时序分析中的相似搜索............................................................................................................ 235 9．4．3 序列模式挖掘............................................................................................................................ 236 9．4．4 周期分析.................................................................................................................................... 237 9．5 文本数据库挖掘................................................................................................................................... 238 9．5．1 文本数据分析和信息检索........................................................................................................ 238 9．5．2 文本挖掘：基于关键字的关联和文档分类............................................................................ 240 9．6WEB 挖掘............................................................................................................................................... 241 9．6．1 挖掘Web 链接结构，识别权威Web 页面............................................................................... 242 9．6．2 Web 文档的自动分类................................................................................................................. 243 9．6．3 多层次Web 信息库的构造....................................................................................................... 243 9．6．4 Web 使用记录的挖掘................................................................................................................. 244 9．7 总结 ...................................................................................................................................................... 245 习题............................................................................................................................................................ 245 文献注解.................................................................................................................................................... 246 第十章数据挖掘的应用和发展趋势.............................................................................................................. 248 10．1 数据挖掘的应用................................................................................................................................ 248 10．1．1 针对生物医学和DNA 数据分析的数据挖掘........................................................................ 248 10．1．2 针对金融数据分析的数据挖掘.............................................................................................. 249 10．1．3 零售业中的数据挖掘.............................................................................................................. 249 10．1．4 电信业中的数据挖掘.............................................................................................................. 250 10．2 数据挖掘系统产品和研究原型......................................................................................................... 251 10．2．1 怎样选择一个数据挖掘系统.................................................................................................. 251 10．2．2 商用数据挖掘系统的例子...................................................................................................... 252 10．3 数据挖掘的其他主题.................................................................................................................... 253 10．3．1 视频和音频数据挖掘............................................................................................................... 253 10.3.2 科学和统计数据挖掘.................................................................................................................... 254 10．3．3 数据挖掘的理论基础.............................................................................................................. 255 10．3．4 数据挖掘和智能查询应答....................................................................................................... 255 10．4 数据挖掘的社会影响......................................................................................................................... 256 10．4．1 数据挖掘是宣传出来的还是持久的稳定增长的商业？ ....................................................... 256 10．4．2 数据挖掘只是经理的事还是每个人的事？ ........................................................................... 257 10．4．3 数据挖掘对隐私或数据安全构成威胁么？ ........................................................................... 258 10．5 数据挖掘的发展趋势......................................................................................................................... 259 10．6 总结 .................................................................................................................................................... 260 习题............................................................................................................................................................ 260 文献注解.................................................................................................................................................... 261 附录A MICROSOFT’S OLE DB FOR DATA MINING 简介.................................................................... 263 A.1 创建DMM对象................................................................................................................................. 263 A.2 向模型中装入训练数据并对模型进行训练...................................................................................... 264 A.3 模型的使用......................................................................................................................................... 264 附录B DBMINER 简介................................................................................................................................ 266 B.1 系统结构............................................................................................................................................. 266 B.2 输入和输出........................................................................................................................................ 266 B.3 系统支持的数据挖掘任务................................................................................................................. 267 B.4 对任务和方法选择的支持................................................................................................................. 267 B.5 对KDD 处理过程的支持.................................................................................................................. 268 B.6 主要应用............................................................................................................................................ 268 B.7 现状.................................................................................................................................................... 268