数据挖掘十大算法

1.C4.5算法是机器学习算法中的一种分类决策树算法2. k-means algorithm算法是一种聚类算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的长处3. Support vector machines,支持向量机，简称SV机（论文中一般简称SVM）。它是一种監督式學習的措施,它广泛的应用于记录分类以及回归分析中4. Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法5. 最大盼望（EM，ExpectationMaximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法6. PageRank是Google算法的重要内容。PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值7. Adaboost是一种迭代算法，其核心思想是针对同一种训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一种更强的最后分类器 (强分类器)。其算法自身是通过变化数据分布来实现的8. kNN: k-nearest neighbor classificationK近来邻(k-Nearest Neighbor，KNN)分类算法，是一种理论上比较成熟的措施，也是最简朴的机器学习算法之一。该措施的思路是：如果一种样本在特性空间中的k个最相似(即特性空间中最邻近)的样本中的大多数属于某一种类别，则该样本也属于这个类别9. Naive Bayes在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）10. CART: 分类与回归树CART, Classification and Regression Trees。 在分类树下面有两个核心的思想。第一种是有关递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝一C4.5机器学习中，决策树是一种预测模型；她代表的是对象属性与对象值之间的一种映射关系。树中每个节点表达某个对象，而每个分叉途径则代表的某个也许的属性值，而每个叶结点则相应从根节点到该叶节点所经历的途径所示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以解决不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。决策树学习也是数据挖掘中一种一般的措施。在这里，每个决策树都表述了一种树型构造，她由她的分支来对该类型的对象依托属性进行分类。每个决策树可以依托对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一种单独的类可以被应用于某一分支时，递归过程就完毕了。此外，随机森林分类器将许多决策树结合起来以提高分类的对的率。决策树同步也可以依托计算条件概率来构造。决策树如果依托数学的计算措施可以获得更加抱负的效果。决策树是如何工作的决策树一般都是自上而下的来生成的。选择分割的措施有好几种，但是目的都是一致的：对目的类尝试进行最佳的分割。从根到叶子节点均有一条途径，这条途径就是一条“规则”。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量：1)通过该节点的记录数2)如果是叶子节点的话，分类的途径3)对叶子节点对的分类的比例。有些规则的效果可以比其她的某些规则要好。由于ID3算法在实际应用中存在某些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一种改善算法。相信人们对ID3算法都很.熟悉了，这里就不做简介。C4.5算法继承了ID3算法的长处，并在如下几方面对ID3算法进行了改善：1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的局限性；2) 在树构造过程中进行剪枝；3) 可以完毕对持续属性的离散化解决；4) 可以对不完整数据进行解决。C4.5算法有如下长处：产生的分类规则易于理解，精确率较高。其缺陷是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于可以驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运营。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. 分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树. 决策树的各部分是: 根: 学习的事例集. 枝: 分类的鉴定条件. 叶: 分好的各个类. 4.3.2 ID3算法 1.概念提取算法CLS 1) 初始化参数C=E,E涉及所有的例子,为根. 2) IF C中的任一元素e同属于同一种决策类则创立一种叶子 节点YES终结. ELSE 依启发式原则,选择特性Fi=V1,V2,V3,Vn并创立 鉴定节点 划分C为互不相交的N个集合C1,C2,C3,Cn； 3) 对任一种Ci递归. 2. ID3算法 1) 随机选择C的一种子集W (窗口). 2) 调用CLS生成W的分类树DT(强调的启发式原则在后). 3) 顺序扫描C收集DT的意外(即由DT无法拟定的例子). 4) 组合W与已发现的意外,形成新的W. 5) 反复2)到4),直到无例外为止. 启发式原则: 只跟自身与其子树有关,采用信息理论用熵来量度. 熵是选择事件时选择自由度的量度,其计算措施为 P = freq(Cj,S)/|S|; INFO(S)= - SUM( P*LOG(P) ) ; SUM()函数是求j从1到n和. Gain(X)=Info(X)-Infox(X); Infox(X)=SUM( (|Ti|/|T|)*Info(X); 为保证生成的决策树最小,ID3算法在生成子树时,选用使生成的子树的熵(即Gain(S)最小的的特性来生成子树. 4.3.3: ID3算法对数据的规定 1. 所有属性必须为离散量. 2. 所有的训练例的所有属性必须有一种明确的值. 3. 相似的因素必须得到相似的结论且训练例必须唯一. 4.3.4: C4.5对ID3算法的改善: 1. 熵的改善,加上了子树的信息. Split_Infox(X)= - SUM( (|T|/|Ti| ) *LOG(|Ti|/|T|) ); Gain ratio(X)= Gain(X)/Split Infox(X); 2. 在输入数据上的改善. 1) 因素属性的值可以是持续量,C4.5对其排序并提成不同的集合后按照ID3算法当作离散量进行解决,但结论属性的值必须是离散值. 2) 训练例的因素属性值可以是不拟定的,以 ? 表达,但结论必须是拟定的 3. 对已生成的决策树进行裁剪,减小生成树的规模.二 The k-means algorithmk-means algorithm算法是一种聚类算法，把n的对象根据她们的属性分为k个分割，k = 0软间隔1995年, Corinna Cortes 与Vapnik 提出了一种改善的最大间隔区措施，这种措施可以解决标记错误的样本。如果可辨别正负例的超平面不存在，则“软边界”将选择一种超平面尽量清晰地辨别样本，同步使其与分界最清晰的样本的距离最大化。这一成果使术语“支持向量机”（或“SVM”）得到推广。这种措施引入了松驰参数i以衡量对数据xi的误分类度。随后，将目的函数与一种针对非0i的惩罚函数相加，在增大间距和缩小错误惩罚两大目的之间进行权衡优化。如果惩罚函数是一种线性函数，则等式(3)变形为四APRIORI 算法Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度不小于最小支持度的项集称为频繁项集，简称频集。Apriori演算法所使用的前置记录量涉及了： 最大规则物件数：规则中物件组所涉及的最大物件数量 最小增援：规则中物件或是物件组必顸符合的最低案例数 最小信心水准：计算规则所必须符合的最低信心水准门槛 该算法的基本思想是：一方面找出所有的频集，这些项集浮现的频繁性至少和预定义的最小支持度同样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生盼望的规则，产生只涉及集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些不小于顾客给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的措施。也许产生大量的候选集,以及也许需要反复扫描数据库，是Apriori算法的两大缺陷。五 最大盼望(EM)算法在记录计算中，最大盼望（EM，ExpectationMaximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大盼望常常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大盼望算法通过两个环节交替进行计算，第一步是计算盼望（E），也就是将隐藏变量象可以观测到的同样涉及在内从而计算最大似然的盼望值；此外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的盼望值从而计算参数的最大似然估计。M 步上找到的参数然后用于此外一种 E 步计算，这个过程不断交替进行。最大盼望过程阐明我们用 表达可以观测到的不完整的变量值，用 表达无法观测到的变量值，这样 和 一起构成了完整的数据。 也许是实际测量丢失的数据，也也许是可以简化问题的隐藏变量，如果它的值可以懂得的话。例如，在混合模型（Mixture Model）中，如果“产生”样本的混合元素成分已知的话最大似然公式将变得更加便利（参见下面的例子）。估计无法观测的数据让 代表矢量 : 定义的参数的所有数据的概率分布（持续状况下）或者概率集聚函数（离散状况下），那么从这个函数就可以得到所有数据的最大似然值，此外，在给定的观测到的数据条件下未知数据的条件分布可以表达为：六PageRankPageRank是Google算法的重要内容。9月被授予美国专利，专利人是Google创始人之一拉里佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个级别措施是以佩奇来命名的。Google的 PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其她网站投票越多。这个就是所谓的“链接流行度”衡量多少人乐意将她们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度即被别人引述的次数越多，一般判断这篇论文的权威性就越高。Google有一套自动化措施来计算这些投票。Google的PageRank分值从0到 10；PageRank为10表达最佳，但非常少见，类似里氏震级（Richter scale），PageRank级别也不是线性的，而是按照一种指数刻度。这是一种奇特的数学术语，意思是PageRank4不是比PageRank3好一级而也许会好6到7倍。因此，一种PageRank5的网页和PageRank8的网页之间的差距会比你也许觉得的要大的多。PageRank较高的页面的排名往往要比PageRank较低的页面高，而这导致了人们对链接的着魔。在整个SEO社区，人们忙于争夺、互换甚至销售链接，它是过去几年来人们关注的焦点，以至于Google修改了她的系统，并开始放弃某些类型的链接。例如，被人们广泛接受的一条规定，来自缺少内容的“link farm”（链接工厂）网站的链接将不会提供页面的PageRank，从PageRank较高的页面得到链接但是内容不有关（例如说某个流行的漫画书网站链接到一种叉车规范页面），也不会提供页面的PageRank。Google选择减少了PageRank对更新频率，以便不鼓励人们不断的对其进行监测。Google PageRank一般一年更新四次，因此刚上线的新网站不也许获得PR值。你的网站很也许在相称长的时间里面看不到PR值的变化，特别是某些新的网站。PR值临时没有，这不是什么不好的事情，耐心等待就好了。在互联网上，如果一种网页被诸多其他网页所链接，阐明它受到普遍的承认和信赖，那么它的排名就高。这就是 Page Rank 的核心思想。 固然 Google 的 Page Rank 算法事实上要复杂得多。例如说，对来自不同网页的链接看待不同，自身网页排名高的链接更可靠，于是给这些链接予较大的权重。Page Rank 考虑了这个因素，可是目前问题又来了，计算搜索成果的网页排名过程中需要用到网页自身的排名，这不成了先有鸡还是先有蛋的问题了吗？Google 的两个创始人拉里佩奇 （Larry Page ）和谢尔盖布林 (Sergey Brin) 把这个问题变成了一种二维矩阵相乘的问题，并且用迭代的措施解决了这个问题。她们先假定所有网页的排名是相似的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名。她们两人从理论上证明了不管初始值如何选用，这种算法都保证了网页排名的估计值能收敛到她们的真实值。值得一提的事，这种算法是完全没有任何人工干预的。理论问题解决了，又遇到实际问题。由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多种元素。如果我们假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。拉里和谢尔盖两人运用稀疏矩阵计算的技巧，大大的简化了计算量，并实现了这个网页排名算法。今天 Google 的工程师把这个算法移植到并行的计算机中，进一步缩短了计算时间，使网页更新的周期比此前短了许多。我来 Google 后，拉里 (Larry) 在和我们几种新员工座谈时，讲起她当年和谢尔盖(Sergey) 是怎么想到网页排名算法的。她说：当时我们觉得整个互联网就像一张大的图（Graph)，每个网站就像一种节点，而每个网页的链接就像一种弧。我想，互联网可以用一种图或者矩阵描述，我也许可以用这个发现做个博士论文。 她和谢尔盖就这样发明了 Page Rank 的算法。网页排名的高明之处在于它把整个互联网当作了一种整体看待。它无意识中符合了系统论的观点。相比之下，此前的信息检索大多把每一种网页当作独立的个体看待，诸多人当时只注意了网页内容和查询语句的有关性，忽视了网页之间的关系。 1.PageRank基本思想：如果网页T存在一种指向网页A的连接，则表白T的所有者觉得A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/C(T)其中PR（T）为T的PageRank值，C(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。长处：是一种与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大减少了查询响应时间。局限性：人们的查询具有主题特性，PageRank忽视了主题有关性，导致成果的有关性和主题性减少；此外，PageRank有很严重的对新网页的歧视。2.Topic-Sensitive PageRank（主题敏感的PageRank）基本思想：针对PageRank对主题的忽视而提出。核心思想：通过离线计算出一种 PageRank向量集合，该集合中的每一种向量与某一主题有关，即计算某个页面有关不同主题的得分。重要分为两个阶段：主题有关的PageRank向量集合的计算和在线查询时主题的拟定。长处：根据顾客的查询祈求和有关上下文判断顾客查询有关的主题（顾客的爱好）返回查询成果精确性高。局限性：没有运用主题的有关性来提高链接得分的精确性。七 AdaBoostAdaboost是一种迭代算法，其核心思想是针对同一种训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一种更强的最后分类器 (强分类器)。其算法自身是通过变化数据分布来实现的，它根据每次训练集之中每个样本的分类与否对的，以及上次的总体分类的精确率，来拟定每个样本的权值。将修改正权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除某些不必要的训练数据特徵，并将核心放在核心的训练数据上面。目前，对adaboost算法的研究以及应用大多集中于分类问题，同步近年也出 现了某些在回归问题上的应用。就其应用adaboost系列重要解决了: 两类问题、 多类单标签问题、多类多标签问题、大类单标签问题，回归问题。它用所有的训练样本进行学习。该算法其实是一种简朴的弱分类算法提高过程，这个过程通过不断的训练，可以提高对数据的分类能力。整个过程如下所示：1. 先通过对N个训练样本的学习得到第一种弱分类器 ；2. 将 分错的样本和其她的新数据一起构成一种新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器 ；3. 将 和 都分错了的样本加上其她的新样本构成另一种新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器 ；4. 最后通过提高的强分类器 。即某个数据被分为哪一类要通过 ， 的多数表决。2.3 Adaboost(Adaptive Boosting)算法对于boosting算法，存在两个问题：1. 如何调节训练集，使得在训练集上训练的弱分类器得以进行；2. 如何将训练得到的各个弱分类器联合起来形成强分类器。针对以上两个问题，adaboost算法进行了调节：1. 使用加权后选用的训练数据替代随机选用的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上；2. 将弱分类器联合起来，使用加权的投票机制替代平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。Adaboost算法是Freund和Schapire根据在线分派算法提出的，她们具体分析了Adaboost算法错误率 的上界，以及为了使强分类器 达到错误率，算法所需要的最多迭代次数等有关问题。与Boosting算法不同的是，adaboost算法不需要预先懂得弱学习算法学习对的率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度， 这样可以进一步挖掘弱分类器算法的能力。Adaboost算法中不同的训练集是通过调节每个样本相应的权重来实现的。开始时，每个样本相应的权重是相似的，即 其中 n 为样本个数，在此样本分布下训练出一弱分类器 。对于分类错误的样本，加大其相应的权重；而对于分类对的的样本，减少其权重，这样分错的样本就被突出出来，从而得到一种新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器。依次类推，通过 T 次循环，得到 T 个弱分类器，把这 T 个弱分类器按一定的权重叠加（boost）起来，得到最后想要的强分类器。Adaboost算法的具体环节如下：1. 给定训练样本集 ，其中 分别相应于正例样本和负例样本； 为训练的最大循环次数；2. 初始化样本权重 ，即为训练样本的初始概率分布；3. 第一次迭代：(1) 训练样本的概率分布 下，训练弱分类器：(2) 计算弱分类器的错误率：(3) 选用 ，使得 最小(4) 更新样本权重：(5) 最后得到的强分类器：Adaboost算法是通过调节的Boosting算法，其可以对弱学习得到的弱分类器的错误进行适应性调节。上述算法中迭代了 次的主循环，每一次循环根据目前的权重分布对样本x定一种分布P，然后对这个分布下的样本使用若学习算法得到一种错误率为 的弱分类器 ，对于这个算法定义的弱学习算法，对所有的 ，均有，而这个错误率的上限并不需要事先懂得，事实上。每一次迭代，都要对权重进行更新。更新的规则是：减小弱分类器分类效果较好的数据的概率，增大弱分类器分类效果较差的数据的概率。最后的分类器是个弱分类器的加权平均。八kNN: k-nearest neighbor classification邻近算法KNN算法的决策过程k-Nearest Neighbor algorithm 右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。K近来邻(k-Nearest Neighbor，KNN)分类算法，是一种理论上比较成熟的措施，也是最简朴的机器学习算法之一。该措施的思路是：如果一种样本在特性空间中的k个最相似(即特性空间中最邻近)的样本中的大多数属于某一种类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经对的分类的对象。该措施在定类决策上只根据最邻近的一种或者几种样本的类别来决定待分样本所属的类别。 KNN措施虽然从原理上也依赖于极限定理，但在类别决策时，只与很少量的相邻样本有关。由于KNN措施重要靠周边有限的邻近的样本，而不是靠鉴别类域的措施来拟定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN措施较其她措施更为适合。KNN算法不仅可以用于分类，还可以用于回归。通过找出一种样本的k个近来邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的措施是将不同距离的邻居对该样本产生的影响予以不同的权值(weight)，如权值与距离成正比。该算法在分类时有个重要的局限性是，当样本不平衡时，如一种类的样本容量很大，而其她类样本容量很小时，有也许导致当输入一种新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的措施（和该样本距离小的邻居权值大）来改善。该措施的另一种局限性之处是计算量较大，由于对每一种待分类的文本都要计算它到全体已知样本的距离，才干求得它的K个近来邻点。目前常用的解决措施是事先对已知样本点进行剪辑，事先清除对分类作用不大的样本。该算法比较合用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 九 朴素贝叶斯分类贝叶斯分类器贝叶斯分类器的分类原理是通过某对象的先验概率，运用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。目前研究较多的贝叶斯分类器重要有四种，分别是：Naive Bayes、TAN、BAN和GBN。贝叶斯网络是一种带有概率注释的有向无环图，图中的每一种结点均表达一种随机变量,图中两结点间若存在着一条弧，则表达这两结点相相应的随机变量是概率相依的，反之则阐明这两个随机变量是条件独立的。网络中任意一种结点X 均有一种相应的条件概率表(Conditional Probability Table，CPT)，用以表达结点X 在其父结点取各也许值时的条件概率。若结点X 无父结点,则X 的CPT 为其先验概率分布。贝叶斯网络的构造及各结点的CPT 定义了网络中各变量的概率分布。贝叶斯分类器是用于分类的贝叶斯网络。该网络中应涉及类结点C，其中C 的取值来自于类集合( c1 , c2 , . , cm)，还涉及一组结点X = ( X1 , X2 , . , Xn)，表达用于分类的特性。对于贝叶斯网络分类器，若某一待分类的样本D，其分类特性值为x = ( x1 , x2 , . , x n) ，则样本D 属于类别ci 的概率P( C = ci | X1 = x1 , X2 = x 2 , . , Xn = x n) ，( i = 1 ,2 , . , m) 应满足下式：P( C = ci | X = x) = Max P( C = c1 | X = x) , P( C = c2 | X = x ) , . , P( C = cm | X = x ) 而由贝叶斯公式：P( C = ci | X = x) = P( X = x | C = ci) * P( C = ci) / P( X = x)其中，P( C = ci) 可由领域专家的经验得到,而P( X = x | C = ci) 和P( X = x) 的计算则较困难。应用贝叶斯网络分类器进行分类重要提成两阶段。第一阶段是贝叶斯网络分类器的学习，即从样本数据中构造分类器，涉及构造学习和CPT 学习；第二阶段是贝叶斯网络分类器的推理，即计算类结点的条件概率，对分类数据进行分类。这两个阶段的时间复杂性均取决于特性值间的依赖限度，甚至可以是 NP 完全问题，因而在实际应用中，往往需要对贝叶斯网络分类器进行简化。根据对特性值间不同关联限度的假设，可以得出多种贝叶斯分类器，Naive Bayes、TAN、BAN、GBN 就是其中较典型、研究较进一步的贝叶斯分类器。朴素贝叶斯分类是将一种未知样本分到几种预先已知类的过程。数据分类问题的解决是一种两步过程：第一步,建立一种模型，描述预先的数据集或概念集。通过度析由属性描述的样本（或实例，对象等）来构造模型。假定每一种样本均有一种预先定义的类，由一种被称为类标签的属性拟定。为建立模型而被分析的数据元组形成训练数据集，该步也称作有指引的学习。在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。决策树模型通过构造树来解决分类问题。一方面运用训练数据集来构造一棵决策树，一旦树建立起来，它就可为未知样本产生一种分类。在分类问题中使用决策树模型有诸多的长处，决策树便于使用，并且高效；根据决策树可以很容易地构造出规则，而规则一般易于解释和理解；决策树可较好地扩展到大型数据库中，同步它的大小独立于数据库的大小；决策树模型的此外一大长处就是可以对有许多属性的数据集构造决策树。决策树模型也有某些缺陷，例如解决缺失数据时的困难，过度拟合问题的浮现，以及忽视数据集中属性之间的有关性等。和决策树模型相比，朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基本，以及稳定的分类效率。同步，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简朴。理论上，NBC模型与其她分类措施相比具有最小的误差率。但是事实上并非总是如此，这是由于NBC模型假设属性之间互相独立，这个假设在实际应用中往往是不成立的，这给NBC模型的对的分类带来了一定影响。在属性个数比较多或者属性之间有关性较大时，NBC模型的分类效率比不上决策树模型。而在属性有关性较小时，NBC模型的性能最为良好。朴素贝叶斯模型：Vmap=arg max P( Vj | a1,a2.an)Vj属于V集合其中Vmap是给定一种example,得到的最也许的目的值.其中a1.an是这个example里面的属性.这里面,Vmap目的值,就是背面计算得出的概率最大的一种.因此用max 来表达贝叶斯公式应用到 P( Vj | a1,a2.an)中.可得到 Vmap= arg max P(a1,a2.an | Vj ) P( Vj ) / P (a1,a2.an)又由于朴素贝叶斯分类器默认a1.an她们互相独立的.因此P(a1,a2.an)对于成果没有用处. 由于所有的概率都要除同一种东西之后再比较大小,最后成果也似乎影响不大可得到Vmap= arg max P(a1,a2.an | Vj ) P( Vj )然后朴素贝叶斯分类器基于一种简朴的假定：给定目的值时属性之间互相条件独立。换言之。该假定阐明给定实力的目的值状况下。观测到联合的a1,a2.an的概率正好是对每个单独属性的概率乘积： P(a1,a2.an | Vj ) = i P( ai| Vj ) 素贝叶斯分类器：Vnb =arg max P( Vj ) i P ( ai | Vj )Vnb = arg max P ( Vj )此处Vj ( yes | no )，相应天气的例子。十 CART: 分类与回归树如果一种人必须去选择在很大范畴的情形下性能都好的、同步不需要应用开发者付出诸多的努力并且易于被终端顾客理解的分类技术的话，那么Brieman, Friedman, Olshen和Stone（1984）提出的分类树措施是一种强有力的竞争者。我们将一方面讨论这个分类的过程，然后在后续的节中我们将展示这个过程是如何被用来预测持续的因变量。Brieman等人用来实现这些过程的程序被称为分类和回归树（CART, Classification and Regression Trees）措施。分类树在分类树下面有两个核心的思想。第一种是有关递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。递归划分让我们用变量y表达因变量（分类变量），用x1, x2, x3,.,xp表达自变量。通过递归的方式把有关变量x的p维空间划分为不重叠的矩形。这个划分是以递归方式完毕的。一方面，一种自变量被选择，例如xi和xi的一种值si，比方说选择si把p维空间为两部分：一部分是p维的超矩形，其中涉及的点都满足xisi。接着，这两部分中的一种部分通过选择一种变量和该变量的划分值以相似的方式被划分。这导致了三个矩形区域（从这里往后我们把超矩形都说成矩形）。随着这个过程的持续，我们得到的矩形越来越小。这个想法是把整个x空间划分为矩形，其中的每个小矩形都尽量是同构的或“纯”的。“纯”的意思是（矩形）所涉及的点都属于同一类。我们觉得涉及的点都只属于一种类（固然，这不总是也许的，由于常常存在某些属于不同类的点，但这些点的自变量有完全相似的值）。