机器学习：从公理到算法

　　这是一本基于公理研究学习算法的书。共 17章，由两部分组成。*部分是机器学习公理以及部分理论演绎，包括第 1、2、6、8 章，论述学习公理以及相应的聚类、分类理论。第二部分关注如何从公理推出经典学习算法，包括单类、多类和多源问题。第 3～5 章为单类问题，分别论述密度估计、回归和单类数据降维。第 7、9～16 章为多类问题，包括聚类、神经网络、 K近邻、支持向量机、Logistic回归、贝叶斯分类、决策树、多类降维与升维等经典算法。*后第 17章研究了多源数据学习问题。本书可以作为高等院校计算机、自动化、数学、统计学、人工智能及相关专业的研究生教材，也可以供机器学习的爱好者参考。

　　于剑，北京交通大学计算机学院教授，博士生导师，交通数据分析与挖掘北京市重点实验室主任，先后获得北京大学数学专业本科、硕士、博士，中国人工智能学会机器学习专委会副主任，中国计算机学会人工智能与模式识别专委会秘书长，承担多项国家自然科学基金项目，发表多篇学术论文，包括TPAMI、CVPR 等。

第 1章引言 .............................................................................................1 1.1机器学习的目的：从数据到知识 .....................................................1 1.2机器学习的基本框架 .....................................................................2 1.2.1数据集合与对象特性表示 .....................................................3 1.2.2学习判据 ............................................................................4 1.2.3学习算法 ............................................................................5 1.3机器学习思想简论 .........................................................................5延伸阅读 ..............................................................................................7习题 ....................................................................................................8参考文献 ..............................................................................................9 第 2章归类理论..................................................................................... 11 2.1类表示公理 ................................................................................. 13 2.2归类公理 .................................................................................... 17 2.3归类结果分类 ............................................................................. 20 2.4归类方法设计准则 ....................................................................... 22 2.4.1类一致性准则 ................................................................... 23 2.4.2类紧致性准则 ................................................................... 23 2.4.3类分离性准则 ................................................................... 25 2.4.4奥卡姆剃刀准则 ................................................................ 25讨论 .................................................................................................. 27延伸阅读 ............................................................................................ 29习题 .................................................................................................. 30参考文献 ............................................................................................ 31 第 3章密度估计..................................................................................... 33 3.1密度估计的参数方法 ................................................................... 33 3.1.1最大似然估计 ................................................................... 33 3.1.2贝叶斯估计 ....................................................................... 35 3.2密度估计的非参数方法 ................................................................ 39 3.2.1直方图 ............................................................................. 39 3.2.2核密度估计 ....................................................................... 39 3.2.3 K近邻密度估计法 ............................................................ 40延伸阅读 ............................................................................................ 40习题 .................................................................................................. 41参考文献 ............................................................................................ 41 第 4章回归 ........................................................................................... 43 4.1线性回归 .................................................................................... 43 4.2岭回归 ....................................................................................... 47 4.3 Lasso回归 .................................................................................. 48讨论 .................................................................................................. 51习题 .................................................................................................. 52参考文献 ............................................................................................ 52 第 5章单类数据降维 .............................................................................. 53 5.1主成分分析 ................................................................................. 54 5.2非负矩阵分解 ............................................................................. 56 5.3字典学习与稀疏表示 ................................................................... 57 5.4局部线性嵌入 ............................................................................. 59 5.5典型关联分析 ............................................................................. 62 5.6多维度尺度分析与等距映射 ......................................................... 63讨论 .................................................................................................. 65习题 .................................................................................................. 66参考文献 ............................................................................................ 66 第 6章聚类理论..................................................................................... 69 6.1聚类问题表示及相关定义 ............................................................. 69 6.2聚类算法设计准则 ....................................................................... 70 6.2.1类紧致性准则和聚类不等式 ............................................... 70 6.2.2类分离性准则和重合类非稳定假设 ..................................... 72 6.2.3类一致性准则和迭代型聚类算法 ......................................... 73 6.3聚类有效性 ................................................................................. 73 6.3.1外部方法 .......................................................................... 73 6.3.2内蕴方法 .......................................................................... 75延伸阅读 ............................................................................................ 76习题 .................................................................................................. 77参考文献 ............................................................................................ 77 第 7章聚类算法..................................................................................... 81 7.1样例理论：层次聚类算法 ............................................................. 81 7.2原型理论：点原型聚类算法 .......................................................... 83 7.2.1 C均值算法 ...................................................................... 84 7.2.2模糊 C均值 ...................................................................... 86 7.3基于密度估计的聚类算法 ............................................................. 88 7.3.1基于参数密度估计的聚类算法 ............................................ 88 7.3.2基于无参数密度估计的聚类算法 ......................................... 97延伸阅读 .......................................................................................... 106习题 ................................................................................................ 107参考文献 .......................................................................................... 108 第 8章分类理论................................................................................... 111 8.1分类及相关定义 ........................................................................ 111 8.2从归类理论到经典分类理论 ....................................................... 112 8.2.1 PAC理论 ....................................................................... 113 8.2.2统计机器学习理论 ........................................................... 115 8.3分类测试公理 ........................................................................... 118讨论 ................................................................................................ 119习题 ................................................................................................ 119参考文献 .......................................................................................... 120 第 9章基于单类的分类算法：神经网络 .................................................. 121 9.1分类问题的回归表示 ................................................................. 121 9.2人工神经网络 ........................................................................... 122 9.2.1人工神经网络相关介绍 .................................................... 122 9.2.2前馈神经网络 ................................................................. 124 9.3从参数密度估计到受限玻耳兹曼机 ............................................. 129 9.4深度学习 .................................................................................. 131 9.4.1自编码器 ........................................................................ 132 9.4.2卷积神经网络 ................................................................. 132讨论 ................................................................................................ 133习题 ................................................................................................ 134参考文献 .......................................................................................... 134 第 10章 K近邻分类模型 ...................................................................... 137 10.1 K近邻算法 ............................................................................. 138 10.1.1 K近邻算法问题表示 .................................................... 138 10.1.2 K近邻分类算法 .......................................................... 139 10.1.3 K近邻分类算法的理论错误率 ...................................... 140 10.2距离加权最近邻算法 ................................................................ 141 10.3 K近邻算法加速策略 ............................................................... 142 10.4 kd树 ...................................................................................... 143 10.5 K近邻算法中的参数问题 ......................................................... 144延伸阅读 .......................................................................................... 145习题 ................................................................................................ 145参考文献 .......................................................................................... 145 第 11章线性分类模型 .......................................................................... 147 11.1判别函数和判别模型 ................................................................ 147 11.2线性判别函数 .......................................................................... 148 11.3线性感知机算法 ...................................................................... 151 11.3.1感知机数据表示 ........................................................... 151 11.3.2感知机算法的归类判据 ................................................. 152 11.3.3感知机分类算法 ........................................................... 153 11.4支持向量机 ............................................................................. 156 11.4.1线性可分支持向量机 .................................................... 156 11.4.2近似线性可分支持向量机 ............................................. 159 11.4.3多类分类问题 .............................................................. 162讨论 ................................................................................................ 164习题 ................................................................................................ 165参考文献 .......................................................................................... 166 第 12章对数线性分类模型 ................................................................... 167 12.1 Softmax回归 .......................................................................... 167 12.2 Logistic回归 ........................................................................... 170讨论 ................................................................................................ 172习题 ................................................................................................ 173参考文献 .......................................................................................... 173 第 13章贝叶斯决策 ............................................................................. 175 13.1贝叶斯分类器 .......................................................................... 175 13.2朴素贝叶斯分类 ...................................................................... 176 13.2.1最大似然估计 .............................................................. 178 13.2.2贝叶斯估计 ................................................................. 181 13.3最小化风险分类 ...................................................................... 183 13.4效用最大化分类 ...................................................................... 185讨论 ................................................................................................ 185习题 ................................................................................................ 186参考文献 .......................................................................................... 186 第 14章决策树 .................................................................................... 187 14.1决策树的类表示 ...................................................................... 187 14.2信息增益与 ID3算法 ............................................................... 192 14.3增益比率与 C4.5算法 .............................................................. 194 14.4 Gini指数与 CART算法 ........................................................... 195 14.5决策树的剪枝 .......................................................................... 196讨论 ................................................................................................ 197习题 ................................................................................................ 197参考文献 .......................................................................................... 198 第 15章多类数据降维 .......................................................................... 199 15.1有监督特征选择模型 ................................................................ 199 15.1.1过滤式特征选择 ........................................................... 200 15.1.2包裹式特征选择 ........................................................... 201 15.1.3嵌入式特征选择 ........................................................... 201 15.2有监督特征提取模型 ................................................................ 202 15.2.1线性判别分析 .............................................................. 202 15.2.2二分类线性判别分析问题 ............................................. 202 15.2.3二分类线性判别分析 .................................................... 203 15.2.4二分类线性判别分析优化算法 ....................................... 205 15.2.5多分类线性判别分析 .................................................... 205延伸阅读 .......................................................................................... 207习题 ................................................................................................ 207参考文献 .......................................................................................... 207 第 16章多类数据升维：核方法 ............................................................. 209 16.1核方法 .................................................................................... 209 16.2非线性支持向量机 ................................................................... 210 16.2.1特征空间 ..................................................................... 210 16.2.2核函数 ........................................................................ 210 16.2.3常用核函数 ................................................................. 212 16.2.4非线性支持向量机 ....................................................... 212 16.3多核方法 ................................................................................ 213讨论 ................................................................................................ 215习题 ................................................................................................ 215参考文献 .......................................................................................... 216 第 17章多源数据学习 .......................................................................... 217 17.1多源数据学习的分类 ................................................................ 217 17.2单类多源数据学习 ................................................................... 217 17.2.1完整视角下的单类多源数据学习 ................................... 218 17.2.2不完整视角下的单类多源数据学习 ................................ 220 17.3多类多源数据学习 ................................................................... 221 17.4多源数据学习中的基本假设 ...................................................... 222讨论 ................................................................................................ 222习题 ................................................................................................ 223参考文献 .......................................................................................... 223 后记 ........................................................................................................ 225 索引 ........................................................................................................ 229