本书以数据挖掘为应用载体,按应用频率的高低,系统地介绍分治算法、贪心算法、搜索算法和动态规划算法。同时,介绍算法分析所用的渐近符号及常用的分析方法,包括递归分析方法、非递归分析方法。本书的特点是结合作者及其团队研究的数据挖掘问题,注重介绍算法的基本思想及算法应用的启发性。
样章试读
目录
- 目录
《信息科学技术学术著作丛书》序
前言
第1章 预备知识 1
1.1 数据挖掘概述 1
1.1.1 分类与回归 1
1.1.2 聚类分析 5
1.1.3 关联分析 7
1.1.4 时间序列分析 8
1.1.5 偏差检测 8
1.1.6 数据挖掘的过程 9
1.2 算法与算法描述 13
1.2.1 算法概念 13
1.2.2 算法描述 13
1.3 算法分析 14
1.3.1 算法分析概述及渐近符号 14
1.3.2 算法分析方法 17
习题 19
第2章 分治算法 21
2.1 归并排序 22
2.2 线性时间选择 24
2.3 基于分治策略的交叉样例选择 26
2.3.1 样例选择概述 26
2.3.2 样例选择准则 27
2.3.3 算法的基本思想 31
2.3.4 交叉样例选择算法 33
2.4 大数据K-近邻算法 38
2.4.1 大数据概述 38
2.4.2 大数据处理系统Hadoop简介 40
2.4.3 K-近邻算法 44
2.4.4 基于分治策略的大数据K-近邻算法 46
2.5 大数据样例选择 49
2.5.1 算法的基本思想 49
2.5.2 基于MapReduce和投票策略的大数据样例选择算法 49
2.6 基于随机上采样和分治策略的两类非平衡大数据分类 53
2.6.1 两类非平衡数据分类问题 53
2.6.2 算法的基本思想 53
2.6.3 基于MapReduce和上采样的两类非平衡大数据分类算法 56
习题 56
第3章 贪心算法 58
3.1 贪心算法的基本思想 58
3.2 背包问题 59
3.2.1 问题描述 59
3.2.2 求解背包问题的贪心算法 59
3.3 活动安排问题 61
3.3.1 问题描述 61
3.3.2 求解活动安排问题的贪心算法 62
3.4 旅行售货员问题 64
3.4.1 问题描述 64
3.4.2 求解旅行售货员问题的贪心算法 65
3.5 特征选择 67
3.5.1 问题描述 67
3.5.2 特征子集评价准则 67
3.5.3 不一致性准则 68
3.5.4 特征选择的贪心算法 72
3.6 决策树归纳算法 88
3.6.1 ID3算法 88
3.6.2 基于依赖度的决策树归纳算法 101
3.6.3 连续值决策树归纳算法 105
3.7 梯度下降算法 111
3.7.1 线性元模型 111
3.7.2 梯度下降算法 112
3.8 基于贪心策略的ELM网络结构选择问题 114
3.8.1 ELM网络结构选择问题 114
3.8.2 模型选择准则 114
3.8.3 基于结点敏感度的ELM网络结构选择算法 115
习题 118
第4章 搜索算法 121
4.1 遗传算法 121
4.1.1 遗传算法简介 121
4.1.2 遗传算法的五要素 122
4.1.3 基于不一致率的离散值遗传进化特征选择算法 137
4.2 粒子群算法 140
4.2.1 连续粒子群算法 140
4.2.2 离散粒子群算法 143
4.2.3 基于相对分类信息熵的二进制粒子群优化特征选择算法 147
4.2.4 混合粒子群算法 153
4.3 回溯法 155
4.3.1 0-1背包问题 155
4.3.2 n皇后问题 158
4.4 分支限界法 162
习题 163
第5章 动态规划算法 166
5.1 动态规划算法简介 166
5.2 多段图问题 167
5.2.1 问题描述 167
5.2.2 问题求解 170
5.3 矩阵连乘问题 172
5.3.1 问题描述 172
5.3.2 问题求解 173
5.4 0-1背包问题 177
5.4.1 子问题的定义 177
5.4.2 递归的定义最优值 177
5.5 所有点对之间的最短距离问题 178
5.5.1 问题描述 178
5.5.2 问题求解 178
习题 181
参考文献 183