数据挖掘相关的数学基础

作者：张迪

面对复杂数据，数据挖掘的基本流程是：首先对原始数据进行填补遗漏、消除异常、平滑噪声等处理，提高数据挖掘的有效性和准确性。然后使用专门的算法对原始数据进行归纳抽象，去掉取之过多且不均匀的属性和概念层次树中不存在的属性，最终得到一个关系模型。当新的数据加入数据集中时，可以根据该关系模型决定新数据的分类和处理模式。同时，新数据也将带来对整体模型的变化，数据和模型处于动态对应的状态。

从以上过程中可以明显感到，所谓数据挖掘，就是一个典型的数学建模过程。当然，这里已经有较为成熟的工具、方法和理论。例如，统计机器学习所需要的主要理论和技术:泛函分析、逼近论与测度论、统计理论、VC维理论、覆盖数、描述长度理论与算法复杂度研究、核方法、非线性规划技术、几何变换。下文简要介绍涉及的数学学科。

1. 线性代数和统计学

在这个建模过程中，基础是两大数学学科：线性代数和统计学。这代表了机器学习中最主流的两大类方法的基础。一种是以研究函数和变换为重点的代数方法，比如降维，特征值提取等，一种是以研究统计模型和样本分布为重点的统计方法，比如图模型、信息理论模型等。它们侧重虽有不同，但是常常是共同使用的，对于代数方法，往往需要统计上的解释，对于统计模型，其具体计算则需要代数的帮助。以代数和统计为出发点，继续往深处走，我们会发现需要更多的数学。传统的统计学所研究的主要是渐进理论(大样本情况下的统计性质)，而样本数目通常有限(甚至还十分有限)。人们过去一直采用样本数目无穷为假设条件推导各种算法，然后将算法用于样本较小的情况，希望能有较好的效果，然而，算法往往不令人满意。由此，人们提出了学习的推广能力（泛化能力）的重要问题。过去多数工作集中在对大样本统计学习方法的改进和修改，或利用启发式方法设计特殊算法。

2、微积分

微积分只是数学分析体系的基础。其基础性作用不言而喻。机器学习研究的大部分问题是在连续的度量空间进行的，无论代数还是统计，在研究优化问题的时候，对一个映射的微分或者梯度的分析总是不可避免。

3、泛函分析

泛函分析体现了数学模型从特殊到一般的发展过程。

函数在19世纪前期的定义还是数与数的对应关系，空间的概念也只有欧几里德空间。十九世纪以来，数学的发展进入了一个新的阶段。这就是，由于对欧几里得第五公理的研究，引出了非欧几何这门新的学科；对于代数方程求解的一般思考，最后建立并发展了群论；对数学分析的研究又建立了集合论。这些新的理论都为用统一的观点把古典分析的基本概念和方法一般化准备了条件。泛函分析作为数学分析的分支，将函数扩展到函数与函数之间的关系，乃至任意两个集合之间的关系，空间则从有限维空间拓展到无限维空间。

在这个地方，函数以及其所作用的对象之间存在的对偶关系扮演了非常重要的角色。机器学习发展至今，也在向无限维延伸——从研究有限维向量的问题到以无限维的函数为研究对象。内核学习和高斯过程是其中典型的例子。

4、测度理论

这是和实分析关系非常密切的学科。概率本身就是一种测度。测度理论对于机器学习的意义是根本的，现代统计学整个就是建立在测度理论的基础之上——虽然初级的概率论教科书一般不这样引入。在一些统计方面的文章中它们会把统计的公式改用测度来表达，这样做有两个好处：所有的推导和结论不用分别给连续分布和离散分布各自写一遍了，这两种东西都可以用同一的测度形式表达：连续分布的积分基于Lebesgue测度，离散分布的求和基于计数测度，而且还能推广到那种既不连续又不离散的分布中去。而且，即使是连续积分，如果不是在欧氏空间进行，而是在更一般的拓扑空间（比如微分流形或者变换群），那么就不能使用传统的黎曼积分了，需要使用，比如哈尔测度或者Lebesgue-Stieltjes积分。

5、拓扑学

这是学术中很基础的学科。它一般不直接提供方法，但是它的很多概念和定理是其它数学分支的基石。看很多别的数学的时候，会经常接触这样一些概念：开集，闭集，连续函数度量空间,柯西序列,邻接性,连续性。很多这些也许在大学一年级就学习过一些，当时是基于极限的概念获得的。但是看过拓扑学之后，对这些概念的认识会有根本性的拓展。值得一提的是，计算机学科的基础布尔代数与拓扑学有重要的联系。

6、图论

图，由于它在表述各种关系的强大能力以及优雅的理论，高效的算法，越来越受到数据挖掘领域的欢迎。而从目前我所接触的范围内，图论仅在数据结构这门课中提到过。经典图论，在数据挖掘领域中的一个最重要应用就是图模型了，它被成功运用于分析统计网络的结构和规划统计推断。例如，分析社交网络的用户关系，常用邻接链表和邻接矩阵综合表示。在遍历时也离不开深度优先和广度优先算法。

>> 本文固定链接: http://www.storagelab.org.cn/zhangdi/2014/01/12/%e6%95%b0%e6%8d%ae%e6%8c%96%e6%8e%98%e7%9b%b8%e5%85%b3%e7%9a%84%e6%95%b0%e5%ad%a6%e5%9f%ba%e7%a1%80/

>> 转载请注明: 张迪 2014年01月12日 于 张迪的blog 发表