1.数据挖掘十大算法概述

数据挖掘是人工智能和数据库领域研究的热点问题，所谓数据挖掘是指从数据库的大量数据中揭示出隐含的、先前未知的并有潜在价值信息的非平凡过程。数据挖掘是一种决策支持过程，它主要基于人工智能、机器学习、模式识别、统计学、数据库、可视化技术等，高度自动化地分析企业的数据，作出归纳性的推理，从中挖掘出潜在的模式，帮助决策者调整市场策略，减少风险，作出正确的决策。数据挖掘算法具体可以分为分类算法，聚类算法和关联规则三大类。IEEE协会于2006年12月在顶级数据挖掘会议ICDM评选出了数据挖掘领域的十大经典算法，即C4.5、K-Means、SVM、Apriori、EM、PageRank、AdaBoost、KNN、Naive Bayes和CART。

2.数据挖掘十大算法总结

2.1 EM

期望最大化算法（Expectation-Maximization algorithm，简称EM）是一种迭代算法，用于含有隐变量（Hidden Variable）的概率参数模型的最大似然估计或极大后验概率估计。1886年，美国数学家Simon Newcomb在使用高斯混合模型（Gaussian Mixture Model, GMM）解释观测误差的长尾效应时提出了类似EM算法的迭代求解技术。在极大似然估计（Maximum Likelihood Estimation, MLE）方法出现后，英国学者Anderson McKendrick在1926年发展了Newcomb的理论并在医学样本中进行了应用。EM 算法的核心思想非常简单，分为两步：Expection-Step 和 Maximization-Step。E-Step 主要通过观察数据和现有模型来估计参数，然后用这个估计的参数值来计算似然函数的期望值；而 M-Step 是寻找似然函数最大化时对应的参数。由于算法会保证在每次迭代之后似然函数都会增加，所以函数最终会收敛。

Applications of mathematics to medical problems^[1]. AG M'Kendrick. 1925.

2.2 KNN

KNN(K-NearestNeighbor)，即K最近邻算法，是一种常用的监督学习方法，简单来说，根据K个最近的邻居的状态来决定样本的状态，即“物以类聚，人以群分”。该算法的思想是：一个样本与数据集中的K个样本最相似， 如果这K个样本中的大多数属于某一个类别， 则该样本也属于这个类别。

Discriminatory Analysis-Nonparametric Discrimination: Consistency Properties^[2]. B W Silverman, M C Jones, Evelyn Fixt, J L Hodges Jr, Jones. Report 1951.

2.3 K-Means

K均值聚类算法（K-Means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是，先将数据分为K组，随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个初始聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

Some methods for classification and analysis of multivariate observations^[3]. J Macqueen. Proceedings of the fifth Berkeley symposium on mathematical statistics and probability 1967.

2.4 CART

CART（Classification and Regression Tree），即分类与回归树，使用树形结构来解决分类和回归问题。CART算法由Breiman等人在 1984 年提出，它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显著，因此CART模型被称为数据挖掘领域内里程碑式的算法。

CART: Classification and Regression Trees^[4]. Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J. Stone. 1984.

2.5 SVM

支持向量机（Support Vector Machine, SVM）是一类按监督学习方式对数据进行二元分类的广义线性分类器（generalized linear classifier），其决策边界是对学习样本求解的最大边距超平面（maximum-margin hyperplane）。SVM使用铰链损失函数（hinge loss）计算经验风险（empirical risk）并在求解系统中加入了正则化项以优化结构风险（structural risk），是一个具有稀疏性和稳健性的分类器。SVM可以通过核方法(kernel method）进行非线性分类，是常见的核学习（kernel learning）方法之一 。SVM是由模式识别中广义肖像算法（generalized portrait algorithm）发展而来的分类器，1992年，Bernhard E. Boser、Isabelle M. Guyon和Vapnik通过核方法得到了非线性SVM。

A training algorithm for optimal margin classifiers^[5]. Bernhard E. Boser, Isabelle M. Guyon, Vladimir N. Vapnik. COLT 1992.

2.6 C4.5

决策树以其出色的数据分析效率、直观易懂等特点备受青睐。构造决策树有多种算法，国际上最早的、具有影响力的决策树是由Quinlan于1986年提出的ID3算法，是基于信息熵的决策树分类算法。ID3算法采用信息熵作为属性选择标准，可这个标准易偏向于取值较多的候选属性。Quinlan于1993年又提出了ID3的改进版本C4.5算法，C4.5算法用信息增益率来选择决策属性，它继承了ID3算法的全部优点，在ID3的基础上还增加了对连续属性的离散化、对未知属性的处理和产生规则等功能。C4.5的目标是通过学习，找到一个从属性值到类别的映射关系，并且这个映射能用于对新的类别未知的实体进行分类。

C4.5: Programs for Machine Learning^[6]. J. Ross Quinlan. 1993.

2.7 Apriori

Apriori算法是第一个关联规则挖掘算法，也是最经典的算法，最早由Agrawal等人于1994年提出，用于解决大型销售交易数据库之中的关联规则问题。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为K项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。

Fast Algorithms for Mining Association Rules^[7]. Rakesh Agrawal, Ramakrishnan Srikant. VLDB 1994.

2.8 Adaboost

AdaBoost是Adaptive Boosting的简称，属于集成算法(Ensemble Method)中Boosting类别中的一种。AdaBoost是非常成功的机器学习算法，由Yoav Freund和RobertSchapire于1995年提出。AdaBoost是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它在某个分类器选入训练集的概率。如果某个样本点已经被准确分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确分类，它的权重就会被提高。通过这种方式。AdaBoost能聚焦于那些较难分（更富信息）的样本上。AdaBoost的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。

A decision-theoretic generalization of on-line learning and an application to boosting^[8]. Yoav Freund, Robert E Schapire. European Conference on Computational Learning Theory 1995.

2.9 PageRank

在实际应用中许多数据都以图（graph）的形式存在，比如互联网、社交网络都可以看作是一个图。图数据上的机器学习具有理论与应用上的重要意义。PageRank 算法是图的链接分析（link analysis）的代表性算法，属于图数据上的无监督学习方法。PageRank算法最初作为互联网网页重要度的计算方法，1996 年由Page和Brin提出，并用于谷歌搜索引擎的网页排序。事实上，PageRank 可以定义在任意有向图上，后来被应用到社会影响力分析、文本摘要等多个问题。PageRank算法的基本想法是在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为。在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，这时各个结点的平稳概率值就是其PageRank值，表示结点的重要度。PageRank 是递归定义的，PageRank 的计算可以通过迭代算法进行。

The anatomy of a large-scale hypertextual Web search engine^[9]. Sergey Brin, Lawrence Page. Comput Networks 1998.

2.10 Naive Bayes

Naive Bayes（朴素贝叶斯）是以贝叶斯原理为基础，使用概率统计的知识对样本数据集进行分类。贝叶斯方法是以贝叶斯原理为基础，使用概率统计的知识对样本数据集进行分类。由于其有着坚实的数学基础，贝叶斯分类算法的误判率是很低的。贝叶斯方法的特点是结合先验概率和后验概率，即避免了只使用先验概率的主观偏见，也避免了单独使用样本信息的过拟合现象。贝叶斯分类算法在数据集较大的情况下表现出较高的准确率，同时算法本身也比较简单。朴素贝叶斯方法是在贝叶斯算法的基础上进行了相应的简化，即假定给定目标值时属性之间相互条件独立。也就是说没有哪个属性变量对于决策结果来说占有着较大的比重，也没有哪个属性变量对于决策结果占有着较小的比重。虽然这个简化方式在一定程度上降低了贝叶斯分类算法的分类效果，但是在实际的应用场景中，极大地简化了贝叶斯方法的复杂性。

On the Optimality of the Simple Bayesian Classifier under Zero-One Loss^[10]. Pedro Domingos, Michael Pazzani. Machine Learning 1997.