机器学习算法优缺点改进总结.docx

《机器学习算法优缺点改进总结.docx》由会员分享，可在线阅读，更多相关《机器学习算法优缺点改进总结.docx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Lecture 1 Introduction to Supervised Learning(1) Expectatin Maximization(EM) Algorithm (期望值最大)(2) Linear Regression Algorithm(线性回归)(3) Local Weighted Regression(局部加权回归)(4) k-Nearest Neighbor Algorithm for Regression(回归 k 近邻)(5) Linear Classifier(线性分类)(6) Perceptron Algorithm (线性分类)(7) Fisher Discrim

2、inant Analysis or Linear Discriminant Analysis(LDA)(8) k-NN Algorithm for Classifier(分类 k 近邻)(9) Bayesian Decision Method(贝叶斯决策方法)Lecture 2 Feed-forward Neural Networks and BP Algorithm(1) Multilayer Perceptron侈层感知器)(2) BP AlgorithmLecture 3 Rudiments of Support Vector Machine(1) Support Vector Mach

3、ine(支持向量机)(此算法是重点，必考题)此处有一道必考题Lecture 4 Introduction to Decision Rule Mining(2) Decision Tree Algorithm(3) ID3 Algorithm(4) C4.5 Algorithm(4)粗糙集Lecture 5Classifier Assessment and Ensemble Methods(1)Bagging(2) Booting(3) AdaboostingLecture 6 Introduction to Association Rule Mining(1) Apriori Algorith

4、ms:2) FP-tree AlgorithmsLecture 7 Introduction to Custering Analysis(1) k-means Algorithms(2) fuzzyc-meansAlgorithms(3) k-mode Algorithms(4)DBSCAN AlgorithmsLecture 8 Basics of Feature Selection1 1) Relief Algorithms2 2) ReliefF Algorithmsn . + aAw( n)dn- ( n)式中,a为动量因子,一般取0.10.8。这时权值修正量加上了有关上一时刻权值修改

5、方向的记忆，加速了网络的收敛。加动量项法的具体原理:假设相邻两次迭代点处的梯 度方向是一致的,引入动展项可使权值的调整最增大，从而加速收敛;假设相邻两次迭代点处的梯度方向相反,引入动 量项可使权值的调整量减小，防止了来回振荡,加快了收敛。3 .串连法BP算法的收敛速度主要取决于输入-输出模式间非线性映射的复杂程度。显然，这种非线性映射关系越复杂,收敛时 间越长。因此，对那些高度复杂的非线性问题,用两个串连的BP网络代替一个BP网络,能够有效地缩短训练时间。4 .利用遗传算法优化BP算法BP算法的优点是寻优具有准确性,但它易陷入局部极小、收敛速度慢，而遗传算法（GeneticAlgoiithm,

6、GA）是基于自然 选择和遗传规律的全局优化搜索算法,具有很强的宏观搜索能力和寻优全局性。因此，在BP神经网络理论中引入遗 传算法的思想，则可以很好地到达全局寻优和快速高效的目的。Lecture 3 Rudiments of Support Vector Machine（1） Support Vector Machine（支持向量机）（此算法是重点，必考题）算法思想SVM的主要思想是针对两类分类问题，寻找一个超平面作为两类训练样本点的分割，以保证最小的分类错误率。 在线性可分的情况下，存在一个或多个超平面使得训练样本完全分开，SVM的目标是找到其中的最优超平面，最优 超平面是使得每一类数据与超平

7、面距离最近的向量与超平面之间的距离最大的这样的平面，对于线性不可分的情 况，通过使用核函数（一种非线性映射算法）将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分。 优点11）小样本，并不是说样本的绝对数量少（实际上，对任何算法来说，更多的样本几乎总是能带来更好的效果）， 而是说与问题的复杂度比起来，SVM算法要求的样本数是相比照拟少的。（2）非线性，是指SVM擅长应付样本数据线性不可分的情况，主要通过松弛变量1也有人叫惩罚变量）和核函数 技术来实现，（3）高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过降维处理，出现几万维的情况很正常, 其他算法 基本就没有能力应付了

8、，SVM却可以，主要是因为SVM产生的分类器很简洁，用到的样本信息很少（仅 仅用到那些称之为“支持向量的样本，此为后话），使得即使样本维数很高，也不会给存储和计算带来大麻烦（相 对照而言，kNN算法在分类时就要用到所有样本，样本数巨大，每个样本维数再一高，这口子就没法过了）。 缺点（1） SVM算法对大规模训练样本难以实施由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶 矩阵的计算5为样本的个数），当m数目很大时该矩阵的存储和计算将消耗大量的机器内存和运算时间。（2）用SVM解决多分类问题存在困难改良：经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要

9、解决多类的分类问题。 可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、对组合模式和SVM决策树； 再就是通过构造多个分类器的组合来解决。主要原理是抑制SVU固有的缺点，结合其他算法的优势，解决多类问题的分类精度。 如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。 此处有一道必考题Lecture 4 Introduction to Decision Rule Mining(1) ID3 Algorithm算法思想：补充：ID3算法（Iterative Dichotomiser 3迭代二义树3代）是一个由Ross Quinlan创造的用于决策树的算法。这个算法便 是： 从

10、信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想就是以信息 增益度量属性选择，选择分裂后信息增益最大的属性进展分裂。该算法采用自顶向卜的贪婪搜索遍历可能的决策树 空间。所以，ID3的思想便是：自顶向下的贪婪搜索遍历可能的决策树空间构造决策树（此方法是ID3算法和C4.5算法的根基）；从“哪一个属性将在树的根节点被测试开场；使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试（若何定义 或者评判一个属性是分类能力最好的呢这便是下文将要介绍的信息增益，or信息增益率）。然后为根结点属性的每个可能值产生一个分支，并把训练样例

11、排列到适当的分支（也就是说，样例的该属性值对应 的分支）之下。重匆这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最正确属性。优点：（1）分类精度高；（2）实现对比简单，产生的规则如果用图表示出来的话，清晰易懂；优点补充：（4） ID3算法的假设空间包含了所有的决策树，不存在无解风险（5） ID3算法非常适合处理离散样本数据，利用属性结果提取分类规则，且容易理解（6）引进了信息论的中的燧，使得算法得到结点最少的决策树缺点：（1） ID3算法往往偏向于选择取值较多的属性，而在很多情况下取值较多的属性并不总是最重要的属性，即按照使 熠值最小的原则被ID3算法列为应该首先判断的属性在现实情

12、况中却并不一定非常重要。例如：在银行客户分析中， 姓名属性取值多，却不能从中得到任何信息。（简单写：由于使用信息增益，会在属性选择时偏向选择取值多的属 性）（2） ID3算法对于噪声数据敏感，ID3算法不能处理具有连续值的属性，也不能处理具有缺失数据的属性。（3）用互信息作为选择属性的标准存在一个假设，即训练子集中的正、反例的比例应与实际问题领域中正、反例 的比例一致。一般情况很难保证这两者的比例一致，这样计算训练集的互信息就会存在偏差。（4）在建造决策树时，每个结点仅含一个属性，是一种单变元的算法，致使生成的决策树结点之间的相关性不够 强。虽然在一棵树上连在一起，但联系还是松散的。（5） I

13、D3算法虽然理论清晰，但计算对比复杂，在学习和训练数据集的过程中机器内存占用率对比大，消耗资源。 （计算复杂，有很多对数计算）（6） ID3不够强健，当有一个项数据有改变时，整棵树的构造可能改变很大。改良：用R-C4.5的思想，在进展测试属性选择时，合并分类奉献小的分支，防止出现过细的分枝，提高树的强健性。 补充：（7）当训练集增加或减少的时候，决策树都会随之改变，对渐进学习不方便。改良：（1）对决策树进展剪枝。可以采用穿插验证法和参加正则化的方法。（2）使用基广决策树的combination算法，如bagging算法，randomforest算法，可以解决过拟合的问题（3）引入用户兴趣度给定

14、a（OWaWl）为用户对不确定知识的兴趣度，a的大小由决策者根据先验知识或领域知识来确定。它是一个模糊 的概念，通常指关于某一事务的先验知识，包括领域知识和专家建议，具体到决策树学习中则是指在决策树训练过 程中除了用于生成和修改决策树的实例集之外的所有影响决策树规则生成和选择的因素。（2） C4.5 Algorithm补充：既然说C4.5算法是ID3的改良算法，那么C4.5相比于ID3改良的地方有哪些呢用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熠 （entropy,烯是一种不纯度度量准则），也就是燧的变化值，而C4.5用的是信息增益

15、率。对，区别就在于一个是信息增 益，一个是信息增益率。1因此，C4.5抑制了 ID3用信息增益选择属性时偏向选择取值多的属性的缺乏。） 在树构造过程中进展剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致overfitting。 对非离散数据也能处理。能够对不完整数据进展处理算法思想：优点：（1）产生的分类规则易于理解，准确率较高。（2）对非离散数据也能处理。C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某节点上的分枝属性时，对于离散型描述属 性，C4.5的处理方法与ID3一样，按照该属性本身的取值个数进展计算；对于某个连续性描述属性Ac,假设在某个

16、 结点上的数据集的样本数量为total, C4.5将作以下处理。1）将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大进展排序，得到属性值的取值序列Ale, A2c, Atotalcjo2）在取值序列中生成total-1个分割点。第i （0itotal）个分割点的取值设置为Vi= （Aic+A （i+1） c） 2它可以将 该节点上的数据集划分为两个子集.3）从total-1个分割点中选择最正确分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益比，并 且从中选择信息增益比最大的分割点来划分数据集。（3）能够对不完整数据进展处理。在某些情况下，可供使用的数据可能缺少某

17、些属性的值。假设（x, c（x）是样本集S中的一个训练实例，但是其属 性A的值A（x）未知。处埋缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种 更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A,如果结点n包含6个A=1和4个 A=0的实例,那么A（x）=l的概率是0.6,而A（x）=0的概率是0.4。于是，实例X的60%被分配到A=1的分支,40%被 分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属 性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使

18、用这种方法处理缺少的属性值。（4）抑制了用信息增益来选择属性时偏向选择值多的属性的缺乏。（5）采用了一种后剪枝方法防止树的高度无节制的增长，防止过度拟合数据，该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是 否真正剪枝。方法中使用的公式如下：其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率.，c 为置信度（C4.5算法的一个输入参数，默认值为0.25）, z为对应于置信度c的标准差，其值可根据c的设定值通 过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个 悲观的估计：通过判断剪枝前后

19、e的大小，从而决定是否需要剪枝。树剪枝在决策树的创立时.，由于数据中的噪声和离群点，许多分枝反映的是训练数据中的异常。剪枝方法是用来处理这 种过分拟合数据的问题。通常剪枝方法都是使用统计度量，剪去最不可靠的分枝。剪枝一般分两种方法：先剪枝和后剪枝。先剪枝方法中通过提前停顿树的构造（比方决定在某个节点不再分裂或划分训练元组的子集）而对树剪枝。一旦 停顿，这个节点就变成树叶，该树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法，比方（1） 当决策树到达一定的高度就停顿决策树的生长；（2）到达此节点的实例具有一样的特征向量，而不必一定属于同 一类，也可以停顿生长（3）到达此节点的实例个数

20、小于某个阈值的时候也可以停顿树的生长，缺乏之处是不能处 理那些数据量对比小的特殊情况（4）计算每次扩展对系统性能的增益，如果小于某个阈值就可以让它停顿生长。 先剪枝有个缺点就是视野效果问题，也就是说在样的标准下，也许当前扩展不能满足要求，但更进步扩展又能 满足要求。这样会过早停顿决策树的生长。另一种更常用的方法是后剪枝，它由完全成长的树剪去子树而形成。通过删除节点的分枝并用树叶来替换它。树 叶一般用子树中最频繁的类别来标记。C4.5采用悲观剪枝法，它使用训练集生成决策树又用它来进展剪枝，不需要独立的剪枝集。悲观剪枝法的 基本思路是：设训练集生成的决策树是T,用T来分类训练集中的N的元组，设K为

21、到达某个叶 子节点的元组个数，其中分类错误地个数为J。由于树T是由训练集生成的，是适合训练集的，因此J/K不能可信地 估计错误率。所以用(J+0.5)/K来表示。设S为T的子树，其叶节点个数为L(s), NAJ为到达此子树的叶节点的元 组个数总和，2/为此子树中被错误分类的元组个数之和。在分类新的元组时，则其错误分类个数为XAL(S)/2|其标准错误表示为：为分类错误个数，当下面的式子成立时，则删掉子树S,用叶节点代替，且S的子树不必再计算。 缺点：(1)构造树的过程中，需要对数据集进展屡次的顺序扫描和排序，因而导致算法的低效。(2) C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在

22、内存容纳时程序无法运行。(3)在构造树的过程中，需要对数据集进展屡次的顺序扫描和排序，因而导致算法的低效。改良：(1) SLIQ 算法SLIQ算法对C4.5决策树分类算法的实现方法进展了改良，在决策树的构造过程中采用了 “预排序和“广度 优先策略两种技术。1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对训练集按照该属性的取值进展排序, 而排序是很浪费时间的操作。为此，SLIQ算法采用了预排序技术。所谓预排序，就是针对每个属性的取值，把所 有的记录按照从小到大的顺序进展排序，以消除在决策树的每个结点对数据集进展的排序。具体实现时，需要为 训练数据集的每个属性创立一个属性列表，

23、为类别属性创立一个类别列表。2)广度优先策略。在C4.5算法中，树的构造是按照深度优先策略完成的，需要对每个属性列表在每个结点处都 进展一遍扫描，费时很多，为此，SLIQ采用广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表 扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。SLIQ算法由于采用了上述两种技术，使得该算法能够处理比C4.5大得多的训练集，在一定范围内具有良好的 随记录个数和属性个数增长的可伸缩性。然而它仍然存在如下缺点：1)由F需要将类别列表存放于内存，而类别列表的元组数与训练集的元组数是一样的，这就一定程度上限制了可 以处理的数据集的大小。2)由于采用了预

24、排序技术，而排序算法的复杂度本身并不是与记录个数成线性关系，因此，使得SLIQ算法不可 能到达随记录数目增长的线性可伸缩性。(2) SPRINT 算法为了减少驻留于内存的数据量，SPRINT算法进一步改良了决策树算法的数据构造，去掉了在SUQ中需要驻留 于内存的类别列表，将它的类别列合并到每个属性列表中。这样，在遍历每个属性列表寻找当前结点的最优分裂 标准时，不必参照其他信息，将为结点的分裂表现在对属性列表的分裂，即将每个属性列表分成两个，分别存放 属于各个结点的记录。SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进展分 裂变得很困难。解决的方

25、法是对分裂属性进展分裂时用哈希表记录下每个记录属于哪个孩子结点，假设内存能够 容纳卜整个哈希表，其他属性列表的分裂只需参照该哈希表即可;由于哈希表的大小与训练集的大小成正比，当 训练集很大时，哈希表可能无法在内存容纳，此时分裂只能分批执行，这使得SPRINT算法的可伸缩性仍然不是很 好。（3）随机森林（Random Forest）（对C4.5JD3改良，提高准确率）随机森林是个最近对比火的算法，它有很多的优点：在数据集上表现良好在当前的很多数据集上，相对其他算法有着很大的优势它能够处理很高维度（feature很多）的数据，并且不用做特征选择在训练完后，它能够给出哪些能ature对比重要在创立随

26、机森林的时候，对generlization error使用的是无偏估计训练速度快在训练过程中，能够检测到feature间的互相影响容易做成并行化方法实现对比简单随机森林顾名思义，是用随机的方式建设一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间 是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进展一下判 断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。在建设每一棵决策树的过程中，有两点需要注意-采样与完全分裂。首先是两个随机采样的过程，random forest 对输入的数据要进展行、列

27、的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重 复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是 全部的样本，使得相对不容易出现over-fitting。然后进展列采样，从M个feature中，选择m个（m Bagging 与 Boosting 的区别二者的主要区别是取样方式不同。Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分 类精度要优于Bagging. Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boosting的各轮训练集的 选择与前面各轮的学习

28、结果有关；Bagging的各个预测函数没有权重，而Boosting是有权重的；Bagging的各个预测 函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging 可通过并行训练节省大量时间开销。bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在 有些数据集中,boosting会引起退化Overfit。Boosting思想的一种改良型Ada Boost方法在邮件过滤、文本分类方面都有很好的性能。3、AdaboostfAdaptive Boosting)算法简介A

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

30、示：1.先通过对N个训练样本的学习得到第一个弱分类器；2,将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器； 3.将1和2都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三 个弱分类器；4.最终经过提升的强分类器。即某个数据被分为哪一类要由各分类器权值决定。 算法优点：高精度；简单，无需做特征筛选；可以使用各种方法构建子分类器，Adaboost算法提供的是框架； 当使用简单分类器时，计算出的结果是可以理解的，而且弱分类器构造极其简单；不会过度拟合。对于boosting算法，存在两个问题：1 .若何调整训练集，

31、使得在训练集上训练的弱分类器得以进展；2 .若何将训练得到的各个弱分类器联合起来形成强分类器。针对以上两个问题，Adaboost算法进展了调整：1.使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在对比难分的训练数据样本上； 2.将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分 类效果差的分类器具有较小的权重。与Boosting算法不同的是，Adaboost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并 且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。 算法缺

32、点：训练时间过长，执行效果依赖于弱分类器的选择。对噪声数据和离群值敏感。 改良：限制样本权重的调整在各目标类内部进展1、权值更新方法的改良Allende等人提出了 RADA算法，该算法是对原算法中误分类样本权值抑制的方法。算法最突出的奉献有三点：第一 点是对的抑制，第二点，用当前层分类器来判断样本是否分类正确，而非原算法中的当前弱分类器，第三点，增加age变量记录误分类情况，并作了阈值限制，这里有效缓解了过 拟合的问题。RADA比传统AdaBoost算法更加稳定，有效解决了误分类样本权值偏高的问题。2、训练方法的改良MeHer等人提出了 AdaBoost的并行计算方法P-AdaBoost算法。

33、其主要思想是，将AdaBoost训练过程分为 两个阶段，第一阶段和原算法一样，经过多轮训练，获得一个较为可靠的样本分布3i(s),第二阶段采用并行方 法提高训练效率，训练中不再对样本权值进展更新，而统一采用3心)，最后输出为H(x)yc M (x),其中 c(上当.仁，2 et采用这种方法能大大减少训练成本，与原算法相比，多了S轮的样本分布初始化工作，并且防止了差样本因屡次分 类而造成权值过大的问题。3、多算法结合的改良Yunlong提出了 EAdaBoost算法，是Ada Boost结合k近邻算法的产物。Ada Boost算法具有高度拟合的特点， 噪声会对训练产生很大的影响，Yunlong等

34、人在AdaBoost算法的根基之上参加/ kNN算法，对噪声样本进展了 有效处理，提高了算法的准确度。EAdaBoost算法的主要过程如卜.：(a)准备训练样本，对样本权值进展初始化。(b)计算训练误差，并挑选最优的弱分类器。(c)更新样本权值。(d)用KNN算法排除噪声样本，将权值设为Oo该算法中有两个非常关键的问题，什么样的样本称为噪声样本和每次要处理多少个噪声样本的问题，原文 中称之为suspect sample,算法中取的是那种难于学习、让分类器出错过多的样本。4、综合方法的改良Rong Xiao等人提出了 Boosting Chain算法，用链表的方式来组织分类器，算法先用boost

35、ing特征快速排除 大量非人脸窗口,再用boosting chain和SVM分类器进展再判别，实验效果相比FloatBoost还要略好。AdaboostingLecture 6 Introduction to Association Rule Mining(1) Apriori Algorithms算法思想：Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭 代方法，“K-1项集用于搜索K项集。首先，找出频繁“1项集”的集合，该集合记作L10 L1用于找频繁“2 项集的集合L2,而L2用于找L3。如此下去，直到不能找到“K项集。找每个Lk都需

36、要一次数据库扫描。一、挖掘步骤：1 .依据支持度找出所有频繁项集(频度)2 .依据置信度产生关联规则(强度)二、一些定义：对于A-B支持度：P(AAB),既有A又有B的概率置信度：P(B|A),在A发生的事件中同时发生B的概率p(AB)/P(A)如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集“同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。候选集：通过向下合并得出的项集。频繁集：支持度大于等于特定的最小支持度(Minimum Support/minsup)的项集。注意，频繁集的子集一定是 频繁集。核心思想：连接步和剪枝步。连接步是自连接，

37、原则是保证前k-2项一样，并按照字典顺序连接。剪枝步，是使任 一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频 繁的，从而可以将其从CK中删除。简单的讲，1、发现频繁项集，过程为(1)扫描(2)计数(3)对比(4)产 生频繁项集(5)连接、剪枝，产生候选项集，重复步骤(1)(5)直到不能发现更大的频集2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下：(1)对于每个频繁项集L,产生L的所有非空子集；(2)对于L的每个非空子集S,如果 P (L) /P (S) minsup则输出规则“SdL-S注：L-S表示在项集L中除去

38、S子集的项集优点：Apriori (先验的，推测的)算法应用广泛，可用于消费市场价格分析，猜想顾客的消费习惯；网络安全领 域中的入侵检测技术：可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助 学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。缺点：此算法的的应用非常广泛，但是他在运算的过程中会产生大量的侯选集，而且在匹配的时候要进展整个数 据库的扫描(重复扫描)，因为要做支持度计数的统计操作，在小规模的数据上操作还不会有大问题，如果是大型 的数据库上呢，他的效率还是有待提高的。改良：方法一、Apriori优化：Fp-tree算法关键

39、点：以树形的形式来展示、表达数据的形态；可以理解为水在不同河流分支的流动过程；生成Fp-tree的几个点：1 .扫描原始工程集；2 .排列数据；3 .创立ROOT节点；4 .按照排列的数据进展元素的流动；5 .节点+1；方法二、Apriori优化：垂直数据分布关键点：相当于把原始数据进展行转列的操作，并且记录每个元素的个数Lecture6有5种改良方法：1 .基于哈希的项集数：小于阈值的哈希桶数的k项集不是频繁的2 .缩减事务：在子频繁集中扫描时，不包含任何k项频繁集的事务是无用的3 .划分DB： DB中的任何频繁项集在局部DB中也一定是频繁的4 .采样：用一个小的支持阈值和方法挖掘给定数据的

40、子集5 .动态规划项集数：只有当他们的所有子集预计为频繁时才添加一个新的候选项(1)基于hash的方法。基于哈希的算法仍是将所有所有数据放入内存的方法。只要在计算的过程中能够满足算 法对内存的大量需求，针对C2候选项对过大，一些算法提出用来减少C2的大小。这里我们首先考虑PCY算法， 这个算法使用了在Apriori算法的第一步里大量没使用的内存。接着，我们考虑Multistage (多步哈希)算法，这个 算法使用PCY的技巧，但插入了额外的步骤来更多的减少C2的大小。类似的还有Multihash。(2)基于划分的方法。Savasere等设计了一个基于划分(partition)的算法.这个算法先

41、把数据库从逻辑上分成几个 互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集, 最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而 算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。(3)基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改良的算法，Mannila 等先考虑了这一点，他们认为采样是发现规则的一个有效途径。(2) FP-tree Algorithms算法思想：参考：做60578FP-tree在不生成候选项的情况下，完成Apriori算法的功能

42、.通过合并一些重复路径，实现了数据的压缩，从 而使得将频繁顶集加载到内存中成为可能。之后以树遍历的操作，替代了 Apriori算法中最消耗时间的事务记录遍 历，从而大大提高了运算效率。算法步骤如下：1 .扫描一遍数据库，删除频率小于最小支持度的项，并降序排列。并将每个事务中的项都要按照这个顺序进展排列。 处理后的数据库记录为：2 .构建FP-Tree,把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中，同时在每个结点处记录 该结点出现的支持度。如果插入时频繁项节点已经存在了，则把该频繁项节点支持度加1；如果该节点不存在，则 创立支持度为1的节点，并把该节点链接到项头表中。3 .求

43、出每个节点的条件模式基4 .为每个节点建设FP-Tree5 .递归调用FP-growth(Tree, null)开场进展挖掘。伪代码如下：procedure FP_growth（Tree, a）if ee含单个路径Pthenfor路径尸中结点的每个组合（记作b）产生模式bUa,其支持度suppoM=b中结点的最小支持度； else for each a,在77ee的头部（按照支持度由低到高顺序进展扫描）产生一个模式 b = a 13 a,其支持度 support = a, -support； 构造b的条件模式基，然后构造b的条件FP-树Treeb；if Treeb不为空 then调用 FP_g

44、rowth （Treeb, b）；）FP-growth的执行过程：1）在FP-growth递归调用的第一层，模式前Ba=NULL,得到的其实就是频繁1-项集。2）对每一个频繁1-项，进展递归调用FP-growth（）获得多元频繁项集。优点：（ppt翻译）1 .算法构造拥有完整性：1）没有破坏事务的长模式；2）能保存频繁模式挖掘的完整信息。2 .算法构造拥有紧凑性：1）不相关的项被删除；2）事务项按照频率降序排列，因为更频繁的项更可能被找到；3）如果不计算链接和节点数目，存储空间小于原始数据库。3 .FP算法的效率比Apriori算法快一个数量级,效率快的原因有以下4个：1）没有候选集，没有候选测试2）有紧凑的数据构造3）消除重复的数据库遍历4）根基操作是计数和FP-Tree的建设缺点：（参考 ： doc88 Zp-0009219670599.html）1 .FP-Tree要递归生成条件数据库和条件FP-tree,所以内存开销大改良方法一：将项映射成整数，再存储到FP树的节点，减小fp树的存储空间改良方法二：删除FP树节点一样的所有子树，并用支持度数组来记录被删除的子树信息，以此节省FP树所占的内 存空间。改良方法三：在挖掘过程中，只从父节点到子节点扫描而不进展子节点到父节点的扫描，去掉了 FP树中的parent 域，减少F