【陆勤阅读】数据分析的主要困难与算法的重要性

数据分析的主要困难

我们碰到的数据通常有这样几个特点。一是数据量大。大家只要想一想，万维网上有多少网页，这些网页上有多少数据，就可以对现在碰到的数据量之大有点感觉了。第二是维数高。前面提到的SNP数据是64万维的。第三是类型复杂，比方说这些数据可以是网页或报纸，也可以是图像，视频。第四是噪音大。

这里面最核心的困难是维数高。维数高给我们带来的是维数诅咒（curse of dimension）：模型的复杂度和计算量随着维数的增加而指数增长。例如非参数化的模型中参数的个数会随着维数的增加而指数增长。

怎样克服维数高带来的困难？通常有两类方法。一类方法就是将数学模型限制在一个极小的特殊类里面，如线性模型，如假设概率密度遵循正态分布，如假设观测到的时间序列是隐式马氏过程等。另一类方法是利用数据可能有的特殊结构，例如稀疏性，低维或低秩，光滑性等等。这些特性可以通过对模型作适当的正则化而实现。当然，降维方法也是主要方法之一。

总而言之，数据分析本质上是一个反问题。因此，处理反问题的许多想法，如正则化，在数据分析中扮演了很重要的角色。这也正是统计学与统计力学的不同之处。统计力学处理的是正问题，统计学处理的是反问题。

算法的重要性

跟模型相辅相成的是算法以及这些算法在计算机上的实现。特别是在数据量很大的情况下，算法的重要性就显得尤为突出。

从算法的角度来看，处理大数据主要有两条思路。

一是降低算法的复杂度，即计算量。通常我们要求算法的计算量是线性标度的，也就是说计算量跟数据量成线性关系。但很多关键的算法，尤其是优化方法，还达不到这个要求。对特别大的数据集，例如说万维网上的数据或社交网络数据，我们希望能有次线性标度的算法，也就是说计算量远小于数据量。这就要求我们采用抽样的方法。但怎样对这样的数据进行抽样，比方说对社交网络进行抽样，仍还是一个未解决的问题。

第二条思路是云计算，或并行计算，它的基本想法是把一个大问题分解成很多小问题，然后分而治之。著名的MapReduce软件就是一个这样的例子。

下面举几个典型的算法方面的例子。这些例子来自于2006年IEEE国际数据挖掘会议所选举出来的数据挖掘领域中的10个最重要的算法。

（1）k-平均（k-means）方法。这是对数据作聚类的最简单有效的方法。

（2）支持向量机：一种基于变分（或优化）模型的分类算法。

（3）期望最大化（EM）算法。这个算法的应用很广，典型的是基于极大似然方法（maximum likelihood）的参数估计。

（4）谷歌的网页排序算法，PageRank。它的基本想法是：网页的排序应该是由网页在整个互联网中的重要性决定。从而把排序问题转换成一个矩阵的特征值问题。

（5）贝叶斯方法。这是概率模型中最一般的迭代法框架之一。它告诉我们怎样从一个先验的概率密度模型，结合已知的数据来得到一个后验的概率密度模型。

（6）k-最近邻域方法。用邻域的信息来作分类。跟支持向量机相比，这种方法侧重局部的信息。支持向量机则更侧重整体的趋势。

（7）AdaBoost。这个方法通过变换权重，重新运用数据的办法，把一个弱分类器变成一个强分类器。

其它的方法如决策树方法和用于市场分析的Apriori算法，以及用于推荐系统的合作过滤方法，等。

就现阶段而言，对算法的研究被分散在两个基本不相往来的领域里：计算数学和计算机科学。计算数学研究的算法基本上是针对像函数这样的连续结构。其主要的应用对象是微分方程等。计算机科学处理的主要是离散结构，如网络。而数据的特点介于两者之间。数据本身当然是离散的。但往往数据的背后有一个连续的模型。所以要发展针对数据的算法，就必须把计算数学和计算机科学研究的算法有效地结合起来。