数据挖掘现阶段最常用的算法

1、数据挖掘最常见的十种方法下面介绍十种数据挖掘（data mining）的分析方法，以便于大家对模型的初步了解，这些都是日常挖掘中经常遇到的算法，希望对大家有用！（甚至有数据挖掘公司，用其中的一种算法就能独步天下）1、基于历史的mbr分析（memory-based reasoning；mbr）基于历史的mbr分析方法最主要的概念是用已知的案例（case）来预测未来案例的一些属性（attribute），通常找寻最相似的案例来做比较。记忆基础推理法中有两个主要的要素，分别为距离函数（distance function）与结合函数（combination function）。距离函数的用意在找出最相似

2、的案例；结合函数则将相似案例的属性结合起来，以供预测之用。记忆基础推理法的优点是它容许各种型态的数 据，这些数据不需服从某些假设。另一个优点是其具备学习能力，它能藉由旧案例的学习来获取关于新案例的知识。较令人诟病的是它需要大量的历史数据，有足够 的历史数据方能做良好的预测。此外记忆基础推理法在处理上亦较为费时，不易发现最佳的距离函数与结合函数。其可应用的范围包括欺骗行为的侦测、客户反应预 测、医学诊疗、反应的归类等方面。2、购物篮分析（market basket analysis）购物篮分析最主要的目的在于找出什么样的东西应该放在一起？商业上的应用在藉由顾客的购买行为来了解是什么样的顾客以及这

3、些顾客为什么买这些产品，找出相 关的联想（association）规则，企业藉由这些规则的挖掘获得利益与建立竞争优势。举例来说，零售店可藉由此分析改变置物架上的商品排列或是设计 吸引客户的商业套餐等等。购物篮分析基本运作过程包含下列三点：（1）选择正确的品项：这里所指的正确乃是针对企业体而言，必须要在数以百计、千计品项中选择出真正有用的品项出来。（2）经由对共同发生矩阵（co-occurrence matrix）的探讨挖掘出联想规则。（3）克服实际上的限制：所选择的品项愈多，计算所耗费的资源与时间愈久（呈现指数递增），此时必须运用一些技术以降低资源与时间的损耗。购物篮分析技术可以应用在下列问题

4、上：（1）针对信用卡购物，能够预测未来顾客可能购买什么。（2）对于电信与金融服务业而言，经由购物篮分析能够设计不同的服务组合以扩大利润。（3）保险业能藉由购物篮分析侦测出可能不寻常的投保组合并作预防。（4）对病人而言，在疗程的组合上，购物篮分析能作为是否这些疗程组合会导致并发症的判断依据。3、决策树（decision trees）决策树在解决归类与预测上有着极强的能力，它以法则的方式表达，而这些法则则以一连串的问题表示出来，经由不断询问问题最终能导出所需的结果。典型的决策 树顶端是一个树根，底部有许多的树叶，它将纪录分解成不同的子集，每个子集中的字段可能都包含一个简单的法则。此外，决策树可能有

5、着不同的外型，例如二元 树、三元树或混和的决策树型态。4、遗传算法（genetic algorithm）遗传算法学习细胞演化的过程，细胞间可经由不断的选择、复制、交配、突变产生更佳的新细胞。基因算法的运作方式也很类似，它必须预先建立好一个模式，再经 由一连串类似产生新细胞过程的运作，利用适合函数（fitness function）决定所产生的后代是否与这个模式吻合，最后仅有最吻合的结果能够存活，这个程序一直运作直到此函数收敛到最佳解。基因算法在群集 （cluster）问题上有不错的表现，一般可用来辅助记忆基础推理法与类神经网络的应用。5、聚类分析（cluster detection）这个技术涵

6、盖范围相当广泛，包含基因算法、类神经网络、统计学中的群集分析都有这个功能。它的目标为找出数据中以前未知的相似群体，在许许多多的分析中，刚开始都运用到群集侦测技术，以作为研究的开端。6、连接分析（link analysis）连接分析是以数学中之图形理论（graph theory）为基础，藉由记录之间的关系发展出一个模式，它是以关系为主体，由人与人、物与物或是人与物的关系发展出相当多的应用。例如电信服务业可藉 连结分析收集到顾客使用电话的时间与频率，进而推断顾客使用偏好为何，提出有利于公司的方案。除了电信业之外，愈来愈多的营销业者亦利用连结分析做有利于 企业的研究。7、olap分析（on-line

7、 analytic processing；olap）严格说起来，olap分析并不算特别的一个数据挖掘技术，但是透过在线分析处理工具，使用者能更清楚的了解数据所隐藏的潜在意涵。如同一些视觉处理技术一般，透过图表或图形等方式显现，对一般人而言，感觉会更友善。这样的工具亦能辅助将数据转变成信息的目标。8、神经网络（neural networks）神经网络是以重复学习的方法，将一串例子交与学习，使其归纳出一足以区分的样式。若面对新的例证，神经网络即可根据其过去学习的成果归纳后，推导出新的结果，乃属于机器学习的一种。数据挖掘的相关问题也可采类神经学习的方式，其学习效果十分正确并可做预测功能。9、判别分析

8、（discriminant analysis）当所遭遇问题它的因变量为定性（categorical），而自变量（预测变量）为定量（metric）时，判别分析为一非常适当之技术，通常应用在解决 分类的问题上面。若因变量由两个群体所构成，称之为双群体 判别分析 （two-group discriminant analysis）；若由多个群体构成，则称之为多元判别分析（multiple discriminant analysis；mda）。（1） 找出预测变量的线性组合，使组间变异相对于组内变异的比值为最大，而每一个线性组合与先前已经获得的线性组合均不相关。（2） 检定各组的重心是否有差异。（3）

9、找出哪些预测变量具有最大的区别能力。（4） 根据新受试者的预测变量数值，将该受试者指派到某一群体。10、罗吉斯回归分析（logistic analysis）当判别分析中群体不符合正态分布假设时，罗吉斯回归分析是一个很好的替代方法。罗吉斯回归分析并非预测事件（event）是否发生，而是预测该事件的机 率。它将自变量与因变量的关系假定是s行的形状，当自变量很小时，机率值接近为零；当自变量值慢慢增加时，机率值沿着曲线增加，增加到一定程度时，曲线协 率开始减小，故机率值介于0与1之间。补充：常用数据挖掘算法频繁模式挖掘，关系挖掘，以及相互关系挖掘所谓频繁模式挖掘，指的是比如在商品交易数据库记录中，找出

10、一起出现的商品集合，这些商品集合出现的频率要高于一个阈值，这些经常出现的商品集合称之为频繁模式。频繁模式的思路很简单，首先统计出每个单个商品出现的次数，这就构成了一个一维表。然后再根据一维表，商品两两组合产生一个二维表。然后再由二维表产生三维表，直至到n维表。其中可以利用apriori，进行剪枝，也就是说一维表中如果出现的频率低于阈值的商品，就可以直接去掉，应为包含该商品的高维商品集合的出现频率不可能高于该阈值，可以直接剪枝去掉。频繁模式挖掘还有一种更加高效的方式，就是fp growth，该方法通过扫描一遍数据库，在内存中构造一颗fp tree，基于这棵树就可以产生所有的频繁模式。很显然fp

11、growth算法的效率要高很多，但是其缺陷也很明显，在内存中维护一颗fp tree的开销也是很大的。为了解决这个问题，一个直接的思路是将数据库水平分表到各台机器上，在各台机器上执行本地的fp growth，然后再将各台机器上的结果汇总起来，得到最终的fp growth的结果。所谓关系挖掘，值得是挖掘出各个项目之间的因果关系。关系挖掘的基础是频繁模式挖掘，通过频繁模式挖掘，很容易得出关系，举例就很容易明白，比如我们得到一个频繁集合：那么通过排列组合可以得到l的子集集合：那么很容易得到下面的推理集合，也就是挖掘出的关系：所有的关系挖掘本质上都是基于频繁模式推导出来的。在关系挖掘中，有一种非常有用的

12、关系模式挖掘:mining quantitative association rules。所谓quantitative association rules是这样一种关系模式：该关系模式的挖掘，首先是确定我们所感兴趣的属性：quan1,quan2,cat，然后根据事先确定的间隔，将quan1，quan2按照一定的间隔划分成一定的catorgory，然后进行频繁模式挖掘，得出一些关系，然后将这些关系按照grid进行聚合，生成最后的关系模式。通过关系挖掘挖出的关系中往往有很多不是非常有用，因此需要通过另外的指标排除一些这样的关系，这个指标就是correlation，如下：correlation是用来

13、衡量a，b之间的相关性，从而排除那些没有意义的规则。对于上述所提到的关系挖掘，有一种称之为constraint-based association mining，这是一种特殊的关系挖掘，它对于所挖掘出的条件加了一些限制条件，这些限制条件可能是由用户提出的，其主要目的是排除一些不感兴趣的关系。对于这种关系挖掘，最直接的办法先按照最普通的关系挖掘方法进行挖掘，然后利用条件来对结果进行。但是还有更好的方法，就是在挖掘的过程中利用这些条件，从而缩小整个挖掘过程中的search space，从而提高效率。这些限制条件分为这么几种：antimonotonic，monotonic，succinct，conv

14、ertible，inconvertible，针对每一种的限制条件，都有一些通用的方法或策略来缩小挖掘的search space，可参阅相关资料。分类和预测分类树分类树是一种很常用的分类方法，它该算法的框架表述还是比较清晰的，从根节点开始不断得分治，递归，生长，直至得到最后的结果。根节点代表整个训练样本集,通过在每个节点对某个属性的测试验证,算法递归得将数据集分成更小的数据集.某一节点对应的子树对应着原数据集中满足某一属性测试的部分数据集.这个递归过程一直进行下去。该算法是数据挖掘中常用的一类方法。贝叶斯分类器贝叶斯分类的思想很简单，就是计算属性和分类之间的条件概率，选择使得条件概率最大的分类作

15、为最终的分类结果，这是一种基于统计的分类方法，得到了广泛的引用。贝叶斯分类器分为两种，一种是朴素贝叶斯分类器，它基于贝叶斯理论：其中x代表特征向量, c代表分类.我们的目标就是找出使得这个后验概率最大的那个类.其中需要注意的是x中的各个特征分量是分布独立的.这样就有:朴素贝叶斯分类器最经典的应用场景就是垃圾邮件过滤。朴素贝叶斯分类器的升级版本就是贝叶斯网络，因为朴素贝叶斯网络假设样本的特征向量的各个特征属性是独立的，但对于现实世界，这样的建模未必合理，因此有人就提出了贝叶斯网络，贝叶斯网络假设各个属性之间是存在条件概率的。贝叶斯网络是一个各个属性组成的有向拓扑网络，每条边代表条件概率，通过贝叶

16、斯网络能够计算出各个属性相互组合的条件概率。基于规则的分类器这种分类器利用if then的规则来进行分类。对于如何产生规则，有两种方法：第一种方法，就是从决策树中生成规则。因为决策树天然的就是规则。第二种方法，是采用sequential covering algorithm，直接从训练样本中生成规则集。该方法的思路是一种general-to-specific的方法，该方法从一个空规则开始，然后向规则中依次逐渐增加属性测试条件，选择该属性测试值（也就是测试分界点，attr val）的依据就是是否能够最大限度得改进规则的分类质量。基于神经网络的分类器神经网络分类器是依据属性构造一个网络拓扑结构，该

17、拓扑结构的边具有权重值，我们的目的是不断得利用训练样本然后不断得更新神经网络的边权重值。然后利用该网络就可以得到输出的分类。该算法模拟神经的组成结构，利用了单元之间的反馈机制。但该算法的缺点也很明显，网络拓扑结构的确定没有明确统一的方法论，很多只能靠规划者的经验，因此训练结果往往因人而异，限制了神经网络的使用。支持向量机分类器支持向量机是在训练样本空间中构造超平面来对样本进行分类，它的优势是对高维度不敏感。但效率较低，实施较为复杂。关联分类器关联分类器的思路很简单，前面我们提到频繁模式挖掘，我们将样本的某一属性的（属性，值）对作为一个条目，我们找出经常在一起出现的条目集合，然后找出这些频繁项目

18、集合，这些频繁项目集合对应的样本集合中占主流的分类就作为关联规则的分类结果，该结果如下：关联分类器有三种方法：cba， cmar和cparlazy learnerlazy learner主要有两种分类器：knn分类器和cbr分类器。knn分类器思路很直接，找出和待分类样本最近的k的样本，然后将这k个样本中占主流的的类别作为分类结果分配给待分类样本。该分类器的关键在于如何确定k，一种思路是根据经验，另外一种思路是迭代，让k从1开始递增，计算每个k取值时对某一测试集的错误率，选择错误最小的那个k。另外一个关键就是如何快速得找出k个最近的邻居，这需要我们对各个样本点进行事先排序，并设计一个合适的数据

19、结构，使得找出k个最近邻居的复杂度降为log|d|.预测所谓预测，就是根据既有的数据预测新出现的数据的预测值。预测有两种方法，线性回归和非线性回归。所谓线性回归，指的是y = b + wx 公式1其中x可以是向量，比如(x1,x2)，因此线性回归则变成y=w0+w1*x1+w2*x2 公式2对于公式1，其目标就是求出w向量。那么比较常用的方法就是最小二乘法，使得求出的w对于已有的样本使其方差和最小。方差和就是目标函数，目标函数就是自变量w的一个函数，通过求导求极值，很容易得到使得目标函数最小的w的值。通过一些软件包，如sas，matlab，spss很容易做这种线性回归的w计算。并不是所有的模型

20、都是线性模型，实际的问题中很多模型是非线性的，比如多项式，如下y = w0 +w1*x+w2*x*x + w3*x*x*x解决这种问题的思路是将非线性模型转化为线性模型，然后再用线性回归的方法来解决。比如上面的多项式公式，我们令x1=x x2=x*x x3=x*x*x这样就变成了y = w0 + w1*x1 + w2*x2 + w3*x3，这就变成了线性回归的问题。聚类聚类是数据挖掘需要解决的另外一个问题，分类是我们知道确切的分类结果，知道我们需要将样本分成具体的哪几类。而聚类问题是实现不知道我们的样本具体属于哪些类别，而需要我们从样本中发掘出这些类别。下面谈几种较为通用的聚类方法谈谈。基于分

21、区的聚类法该方法的一个典型的方法就是k-means，该方法非常简单，首先确定我们需要将数据样本分成多少个类，这个需要确定，我们称之为k。然后从样本中任意选择k个样本作为k个类的中心，然后计算每个样本到这k个中心的距离，把他们分配到最相近的类。这样就得到k个聚类，然后重新计算这k个聚类的中心，然后再重复前面的过程，直至没有样本被重新分配从而达到收敛。下面是k-means的伪码基于层次的分类法基于层次的分类法有两种：凝聚和分裂。凝聚：它基于一种自底而上的策略，在最开始的时候，每个样本都代表一个聚类，然后计算两两之间的区分度，然后进行合并，这个合并一直按照这样的方式持续下去，直至所有的样本都被合并为

22、一个类。分裂：它基于一种自上而下的策略，在最开始的时候，所有的样本都是一个类，然后会依据一些区分方法，进行分裂，直至每个样本都分裂成一个聚类。基于层次的分类法，其意义在于其他的聚类方法引入这种基于层次的思路，可以被改造成一个多阶段的的聚类方法，可以大大改进聚类的质量。基于密度的分类法这种方法的一个代表就是dbscan。要理解dbscan，首先要明白这么几种概念：某一样本在e半径内的邻居称之为e-邻居。如果某一样本的e-邻居个数大于某一最小值，那该样本被称之为核心样本。如果q是核心样本，p是q的e-邻居，那么p是q的直接密度可达。对于一个样本链p1,p2,.pn，如果p1=q,pn=p，pi+1

23、是pi的直接可达，那么p就是q的密度可达。如果p,q都是o的密度可达，那么p，q就是密度连通的。有了这些概念，算法就很简单了，首先找出样本中所有的核心样本，那么基于这些核心样本，这些核心样本就代表某一个聚类。遍历这些核心样本，不断找到他们的密度可达的样本，其间某些样本就会被不断合并，直至所有的样本分类趋于稳定，不会再有新的点被加入各个聚类。基于grid的聚类法该算法的代表是sting，它比较晦涩，从表面上来看，它似乎不是一种显然的聚类法。首先我们先划分一些层次，每个层次上我们根据维度或者概念分层不同的cell，实际上这里的每个层次对应的是样本的一个分辨率。每个高层的cell在其下一层中被对应得划分成多个cell，每个cell我们都计算出它的统计信息，估计出它的分布。利用这样的结构，我们很容易进行查询，比如我们查询具有某些属性的样本