数据挖掘算法分类！海洋智能无人系统技术

国际权威的学术组织IEEE数据挖掘国际会议（the IEEE international conferenceon data Mining，ICDM）2006年12月评选出了数据挖掘领域的十大经典算法：C4.5、kmeans、SVM、Apriori、EM、PageRank、AdaBoost、k NN、NaiveBayes和CART。

按照有监督和无监督可以分为两大类，如图21.2所示。其中有监督学习又可以分为分类模型、预测模型两类，其中分类模型代表算法有决策树、KNN、贝叶斯判别、SVM；预测模型代表算法有：回归分析、神经网络算法等。无监督学习数据挖掘算法可以分为关联分析及聚类分析两类，其中聚类分析比较有代表性的算法有：k-means聚类算法、密度聚类算法等。下面就代表性算法分别介绍。

图21.2　数据挖掘算法的分类

1）C4.5

C4.5算法是机器学习算法中的一种分类决策树算法，其核心算法是ID3算法。C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

（1）用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。

（2）在树构造过程中进行剪枝。

（3）能够完成对连续属性的离散化处理。

（4）能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效（相对的CART算法只需要扫描两次数据集，以下仅为决策树优缺点）。

2）k-means算法

k均值聚类算法是一种迭代求解的聚类分析算法，其步骤是随机选取k个对象作为初始的聚类中心。把n个对象根据他们的属性分为k个分割，k＜n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自空间向量，并且目标是使各个群组内部的均方误差总和最小。

伪代码：

选择k个点作为初始质心。

repeat将每个点指派到最近的质心，形成k个簇重新计算每个簇的质心until质心不发生变化。

优点：

（1）原理比较简单，实现也是很容易，收敛速度快。

（2）聚类效果较优。

（3）算法的可解释度比较强。

（4）主要需要调参的参数仅仅是簇数k。

缺点：

（1）k值的选取不好把握。

（2）对于不是凸的数据集比较难收敛。

（3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。

（4）最终结果和初始点的选择有关，容易陷入局部最优。

（5）对噪声和异常点比较的敏感。

3）支持向量机

支持向量机（support vector machine，SVM）。它是一种监督学习的方法，它广泛地应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。

优点：泛化错误率低，计算开销不大，结果易解释。

缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题。

适用数据类型：数值型和标称型数据。

4）Apriori算法

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

优点：编码实现简单，容易理解。

缺点：大数据集上实现速度较慢。

适用于数值型和标称型数据。

5）最大期望（EM）算法

在统计学中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。

（1）计算期望（E），利用概率模型参数的现有估计值，计算隐藏变量的期望。

（2）最大化（M），利用E步上求得的隐藏变量的期望，对参数模型进行最大似然估计。

（3）M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

总体来说，EM的算法流程如下：

（1）初始化分布参数。

（2）重复直到收敛：

E步骤：估计未知参数的期望值，给出当前的参数估计。

M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。

优点：稳定上升的步骤能非常可靠地找到“最优的收敛值”。有时候缺失数据并非真的缺少了，而是为了简化问题而采取的策略，这时EM算法被称为数据添加技术，所添加的数据通常被称为“潜在数据”，复杂的问题通过引入恰当的潜在数据，能够有效地解决问题。

缺点：对初始值敏感：EM算法需要初始化参数θ，而参数θ的选择直接影响收敛效率，以及能否得到全局最优解。

6）PageRank(https://www.xing528.com)

PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。

PageRank根据网站的外部链接和内部链接的数量和质量衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。

PageRank算法的优点在于它对互联网上的网页给出了一个全局的重要性排序，并且算法的计算过程是可以离线完成的，这样有利于迅速响应用户的请求。其缺点在于主题无关性，没有区分页面内的导航链接、广告链接和功能链接等，容易对广告页面有过高评价；此外，PageRank算法的另一弊端是，旧页面等级会比新页面高，因为新页面，即使是非常好的页面，也不会有很多链接，除非他是一个站点的子站点。这也是PageRank需要多项算法结合的原因。

7）AdaBoost

AdaBoost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。

AdaBoost的一般流程如下所示：

（1）收集数据。

（2）准备数据：依赖于所用的基分类器的类型，这里的是单层决策树，即树桩，该类型决策树可以处理任何类型的数据。

（3）分析数据。

（4）训练算法：利用提供的数据集训练分类器。

（5）测试算法：利用提供的测试数据集计算分类的错误率。

（6）使用算法：算法的相关推广，满足实际的需要。

优点：泛化错误率低，易编码，可以应用在大部分分类器上，无参数调整。缺点：对离群点敏感。

适用数据类型：数值型和标称型数据。

8）K最近邻分类算法

K最近邻（K-Nearest Neighbor，KNN）分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。

KNN主要步骤如下：

（1）计算已知类别数据集中的点与当前点之间的距离。

（2）按照距离递增次序排序；选取与当前点距离最小的k个点。

（3）确定前k个点所在类别的出现频率。

（4）返回前k个点所出现频率最高的类别作为当前点的预测分类。

优点：

（1）简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归。

（2）可用于数值型数据和离散型数据。

（3）训练时间复杂度为O（n）；无数据输入假定。

（4）对异常值不敏感。

缺点：

（1）计算复杂性高；空间复杂性高。

（2）样本不平衡问题（即有些类别的样本数量很多，而其他样本的数量很少）。

（3）一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。

（4）无法给出数据的内在含义。

9）朴素贝叶斯模型

在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型（decision tree model，DTM）和朴素贝叶斯模型（naive bayesian model，NBC）。NBC发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

优点：

（1）朴素贝叶斯模型有稳定的分类效率。

（2）对小规模的数据表现很好，能处理多分类任务，适合增量式训练，尤其是数据量超出内存时，可以一批批地去增量训练。

（3）对缺失数据不太敏感，算法也比较简单，常用于文本分类。

缺点：

（1）理论上，朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为朴素贝叶斯模型给定输出类别的情况下，假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好。而在属性相关性较小时，朴素贝叶斯性能最为良好。对于这一点，有半朴素贝叶斯之类的算法通过考虑部分关联性适度改进。

（2）需要知道先验概率，且先验概率很多时候取决于假设，假设的模型可以有很多种，因此在某些时候会由于假设的先验模型的原因导致预测效果不佳。

（3）由于是通过先验和数据来决定后验的概率从而决定分类，所以分类决策存在一定的错误率。

（4）对输入数据的表达形式很敏感。

适用数据类型：标称型数据。

10）CART：分类与回归树

分类与回归树（classification and regression trees，CART）。在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法（二元切分法）；第二个想法是用验证数据进行剪枝（预剪枝、后剪枝）。在回归树的基础上的模型树构建难度可能增加了，但同时其分类效果也有提升。

对回归树稍作修改就可以变成模型树。模型树的生成树关键在于误差的计算。对于给定的数据集，应该先用线性的模型对它进行拟合，然后计算真实的目标值与模型预测值间的差值。最后将这些差值的平方求和就得到了所需要的误差。

树回归优点：可以对复杂和非线性的数据建模。

缺点：结果不易理解。