常用数据挖掘算法简介

十八岁夏至

1朴素贝叶斯
朴素贝叶斯分类法是统计学分类方法，在特征条件独立性假定下，基于贝叶斯定理计算预测类隶属关系的概率进行分类。朴素贝叶斯分类器有着坚实的数学基础和稳定的分类效率，同时分类模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上朴素贝叶斯分类模型与其他分类方法相比具有最小的误差率，但是实际上并非总是如此。这是因为朴素贝叶斯分类模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给模型的正确分类带来了一定影响。

2决策树
决策树是一种类似于流程图的树结构，其中，每个内部节点表示在一个属性上的测试，每个分支代表该测试的一个输出，每个叶节点表示存放一个类标号，顶层节点是根节点。在决策树构造时，使用属性选择度量来选择将元组最好地划分成不同的类的属性。决策树建立时，许多分枝可能反映训练数据中的噪声或离群点，使用树剪枝识别并剪去这种分枝，以提高泛化性。

常用的决策树模型有ID3、C4.5和CART，它们都采用贪心方法，用自顶向下递归的分治方式构造决策树；各算法间差别在于创建树时如何选择属性和剪枝机制。

3 K最近邻分类
K最近邻分类算法（KNN）的核心思想是，如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上，只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的K个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值，如权值与距离成反比。

4 神经网络
4.1 人工神经网络
人工神经网络是模仿生理神经网络的结构和功能而设计的一种信息处理系统。它从信息处理角度对人脑神经元网络进行抽象，建立某种简单模型，按不同的连接方式组成不同的网络。大量的人工神经元以一定的规则连接成神经网络，神经元之间的连接及各连接权值的分布用来表示特定的信息。神经网络分布式存储信息，具有很高的容错性。每个神经元都可以独立的运算和处理接收到的信息并输出结果，网络具有并行运算能力，实时性非常强。神经网络对信息的处理具有自组织、自学习的特点，便于联想、综合和推广。

4.2 深度学习
深度学习源于人工神经网络的研究，其动机在于建立、模拟人脑进行分析学习的神经网络，它模仿人脑的机制来解释数据。深度学习模型结构是含多隐层的多层感知器，通过组合低层特征形成更加抽象的高层表示属性类别或特征，以发现数据的分布式特征表示。

深度学习的概念由Hinton等人于2006年提出。基于深度置信网络(DBN)提出非监督贪心逐层训练算法，为解决深层结构相关的优化难题带来希望，随后提出多层自动编码器深层结构。此外Lecun等人提出的卷积神经网络是第一个真正多层结构学习算法，它利用空间相对关系减少参数数目以提高训练性能。

深度学习涉及相当广泛的机器学习技术和结构，根据这些结构和技术应用的方式，可以将其分成如下三类:

a) 生成性深度结构。该结构描述数据的高阶相关特性，或观测数据和相应类别的联合概率分布。

b) 区分性深度结构。目的是提供对模式分类的区分性能力，通常描述数据的后验分布。

c) 混合型结构。它的目标是区分性的， 但通常利用了生成型结构的输出会更易优化。

5 支持向量机
支持向量机(Support Vector Machine，SVM) 算法是经典的机器学习算法之一，无论在理论分析还是实际应用中都已取得很好的成果。SVM算法由Vapnik和Chervonenkis共同提出，其理论基础是Vapnik提出的“结构风险最小化"原理。SVM算法泛化能力很强，在解决很多复杂问题时有很好的表现。例如，为满足美国邮政服务局利用手写邮政编码进行自动分类邮件的需要，Boser和Guyon等人用SVM对手写体阿拉伯数字进行了识别。Osuna E和Freund R提出了基于SVM的面部识别方法。Joachims等应用SVM对路透社新闻故事数据集进行了文本分类等等。除了数据分类方面应用，SVM逐渐被推广到回归分析、多种背景的模式识别、数据挖掘、函数逼近拟合、医学诊断等众多领域。如今，SVM已成为机器学习的主要研究方向之一，它所代表的统计学习理论也必将带来机器学习领域一场深刻变革。

SVM的思想源于线性学习器，即Rosenblatt感知机。感知机可以将线性可分的两种不同类型的样例自动划分为两类。如果这两类样例不是线性可分的，则可以使用核函数方法，将实验对象的属性表达在高维特征空间上，并由最优化理论的学习算法进行训练，实现由统计学习理论推导得出的学习偏置，从而达到分类的效果，这就是SVM的基本思路。

6 集成学习
6.1随机森林
随机森林是利用多棵树对样本进行训练并预测的一种分类器。简单来说随机森林就是由多棵CART（Classification And Regression Tree）构成的。对于每棵树，它们使用的训练集是从总的训练集中有放回采样出来的，这意味着总的训练集中的有些样本可能多次出现在一棵树的训练集中，也可能从未出现在一棵树的训练集中。在训练每棵树的节点时，使用的特征是从所有特征中按照一定比例随机地无放回的抽取的。

6.2 GBDT(Gradient Boost Decision Tree)
GBDT是一个应用很广泛的算法，可以用来做分类、回归。在很多的数据上都有不错的效果。Gradient Boost其实是一个框架，里面可以套入很多不同的算法。Boost是"提升"的意思，一般Boosting算法都是一个迭代的过程，每一次新的训练都是为了改进上一次的结果。

原始的Boost算法是在算法开始的时候，为每一个样本赋上一个权重值，初始的时候，大家都是一样重要的。在每一步训练中得到的模型，会使得数据点的估计有对有错，就在每一步结束后，增加分错的点的权重，减少分对的点的权重，这样使得某些点如果老是被分错，那么就会被“严重关注”，也就被赋上一个很高的权重。然后等进行了N次迭代（由用户指定），将会得到N个简单的基础分类器，然后将它们组合起来（比如说可以对它们进行加权、或者让它们进行投票等），得到一个最终的模型。

而Gradient Boost与传统的Boost的区别是，每一次的计算是为了减少上一次的残差(residual)，而为了消除残差，可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说，在Gradient Boost中，每个新的模型的简历是为了使得之前模型的残差往梯度方向减少，与传统Boost对正确、错误的样本进行加权有着很大的区别。

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

目前，对 Adaboost 算法的研究以及应用大多集中于分类问题，同时近年也出现了一些在回归问题上的应用。就其应用 Adaboost 系列主要解决了: 两类问题、 多类单标签问题、多类多标签问题、大类单标签问题，回归问题。

该算法其实是一个简单的弱分类算法提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。

7 聚类
聚类分析又称数值分类，聚类分析将个体或对象分类，使得同一类中的对象之间相似性比其他类的对象相似性更强，即使得类间对象的同质性最大化和类间对象异质性最大化。

设已知N个观测值X1,X2,…,Xn,每个观测值是一个p维向量。聚类分析的思想是将每个观测值Xi看成p维空间的一个点,在p维空间中引入“距离”的概念，则可按各点间距离的远近将各点（观测值）归类。若要对 p个变量（即指标）进行分类，常定义一种“相似系数”来衡量变量之间的亲密程度，按各变量之间相似系数的大小可将变量进行分类。根据实际问题的需要和变量的类型，对距离和相似系数有不同的定义方法。

8 频繁模式、关联和相关性挖掘
l Apriori：

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

Apriori 演算法所使用的前置统计量包括了：

•最大规则物件数：规则中物件组所包含的最大物件数量

•最小支援：规则中物件或是物件组必顸符合的最低案例数

•最小置信水准：计算规则所必须符合的最低置信水准门槛

该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。

9 最大期望（EM）算法
在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。 M 步上找到的参数然后用于另外一个 E 步计算，这个过程不断交替进行。

10 PageRank
在PageRank提出之前，已经有研究者提出利用网页的入链数量来进行链接分析计算，这种入链方法假设一个网页的入链越多，则该网页越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的效果。PageRank除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。

对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：

数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。

质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。

利用以上两个假设，PageRank算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的PageRank得分，直到得分稳定为止。 PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似因素，完全采用PageRank来进行排序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回PageRank值最高的页面。

11 其他常用算法
a. 推荐算法

推荐算法大致可以分为三类：基于内容的推荐算法、协同过滤推荐算法和基于知识的推荐算法。

基于内容的推荐算法，原理是用户喜欢和自己关注过的Item在内容上类似的Item，与以前观看的在内容上面（共有很多关键词）有很大关联性，就把后者推荐给你，这种方法可以避免Item的冷启动问题（冷启动：如果一个Item从没有被关注过，其他推荐算法则很少会去推荐，但是基于内容的推荐算法可以分析Item之间的关系，实现推荐），弊端在于推荐的Item可能会重复，另外对于一些多媒体的推荐（比如音乐、电影、图片等)由于很难提内容特征，则很难进行推荐，一种解决方式则是人工给这些Item打标签。

协同过滤算法，原理是用户喜欢那些具有相似兴趣的用户喜欢过的商品，还有一种是基于Item的协同过滤算法（item-based collaborative filtering），这两种方法都是将用户的所有数据读入到内存中进行运算的，因此成为Memory-based Collaborative Filtering，另一种则是Model-based collaborative filtering，包括Aspect Model，pLSA，LDA，聚类，SVD，Matrix Factorization等，这种方法训练过程比较长，但是训练完成后，推荐过程比较快。

最后一种方法是基于知识的推荐算法，也有人将这种方法归为基于内容的推荐，这种方法比较典型的是构建领域本体，或者是建立一定的规则，进行推荐。

b. 社区发现

社区现象是复杂网络中的一种普遍现象，表达了多个个体具有的共同体特性。社区的发现技术，从最初的图分割方法、W-H算法、层次聚类法、GN算法等基本算法，逐渐发展和改进，形成了包括改进GN算法、派系过滤算法、局部社区算法和web社区发现方法在内的更具可操作性的方法。网络的社区发现可为个性化服务、信息推送等提供基本数据，尤其是在信息时代，社区的存在更加普遍，发现技术应用更加方便，其商业价值和服务价值更大。

社区发现问题目前并没有一个明确的定义，根据一般算法流程，大致可以描述为这样一个问题：将一个网络分割成若干个由紧密相连节点构成的社区，而分属不同社区的节点间的联系则相对松散。社区发现算法往往面临着两大难点，其一是网络中社区的个数、大小都是不确定的，社区发现往往是一种无监督的聚类算法，算法的终止依赖于数学上的收敛；其二无论是社交网络还是电信网络，网络规模和复杂度较高，一个用户又往往分属多个社区，构成重叠型社区（Overlapping Community），更增添了社区发现的难度。目前社区发现算法存在许多流派，每类算法又会衍生出许多改进算法，其计算复杂度和应用场景也不尽相同。