样本稀疏性

这里主要介绍两方面的工作：基于聚类分析的抽样和基于支持向量的稀疏方法。

通过聚类可以发现数据的紧致和分散程度，反应数据的结构信息，针对大规模数据比较可行的方法包括：（1）基于划分的方法：划分方法首先给定要聚的集群个数k，创建一个初始划分。然后，再用迭代的方式重新定位，通过最小化目标函数，把数据点从一个集群移动到另一个集群来进行划分，从而将数据点分到k个集群中。这一类的研究算法包括：k－平均算法（或k－均值算法）［53］、PAM（Partitioning Around Medoids）算法［54］、CLARA（Clustering LARge Applications）算法［54］、CLARANS（Clustering Large Applications based on RAN－domized Search）算法［55］等。在这些方法之中，k－means算法是最具代表性、最常见的一种算法。它在50多年以前被首次提出，到目前仍然是一种最广泛使用的聚类算法。该方法计算简单，存储较少，可拓展到大规模的数据聚类问题。然而k－平均算法的性能对初始点的选取依赖较强，且其聚类个数k是需要事先给定的参数，极大地限制了k－平均算法的应用。为了进一步提高k－平均算法的稳定性和适用性，目前已有很多改进的方法，如k－medoids算法［54］、模糊k－means聚类［56］、FORGY、ISODATA、CLUSTER、WISH等［57］。更详细的有关k－means方法发展的综述见参考文献［57］。（2）基于密度的方法：主要是用于发现具有任意形状的集群。它是基于这样一个事实，即在每个集群中有一个典型的点密度，这个密度是高于集群以外的。密度较低的外点被确认为噪声点。在这一类中最常用的算法之一是DBSCAN算法［58］，该算法将类定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为类，并可在噪声的空间数据库中发现任意形状的聚类。然而，其计算复杂度是O（n2），制约了其拓展到大规模数据聚类问题。2014年，Rodriguez和Laio在Science发表了新的基于密度峰的聚类算法（DP算法）［59］。DP算法不仅能自适应地识别聚类的数目，而且可以有效识别离群点。然而，DP算法需要计算和存储任意两个样本点之间的距离，导致其计算和存储复杂度都不比DBSCAN低。因此，如何降低初始聚类个数和参数选取对基于划分的聚类的影响，以及如何提高基于密度的聚类算法的计算效率是当前研究的主要方向。

SVM中所构造的支持向量可以反映数据的边缘信息，使得算法构造时可仅仅依赖于支持向量，进而可以使用支持向量来稀疏样本空间。为了让SVM能适用于更多的数据挖掘问题和更复杂的数据结构，国内外学者对SVM进行了多方面的研究，如从问题出发构造的算法：支持向量分类机，支持向量回归机SVR［12，24，60－63］、直推式SVM［64］；从标准模型出发改造得到的算法：最小二乘SVM、双子SVM和非平行SVM等。但是，由于SVM需要求解二次优化问题或线性方程组问题，计算量较大，这极大影响了其在大规模数据挖掘中的应用。高效的求解算法成了支持向量机研究的重点问题，如Chang等人使用序列极小化算法求解SVM并设计了LIBSVM［65］，Fan等人利用双坐标下降算法求解SVM并设计了LIBLINEAR［66］，以及Shalev－Shwartz等人利用随机梯度下降法求解SVM等［67］。以上这些求解算法针对标准分类和回归问题的SVM具有较好的效率，然而对新问题的SVM和新的SVM模型的求解还有待深入研究。因此，其如何通过统计学习理论和最优化方法研究大规模SVM的求解及获取尽可能少的有效支持向量，是当前急需研究的重要问题。