数据挖掘(实用机器学习技术)摘录

数据挖掘：从数据中寻找模式机器学习：从大量的数据中自动或半自动地寻找模式的过程，而且这个模式必须是游泳的。3输出：知识表达决策表决策树：通常从决策树上读取出的规则的复杂度远远超出所需，所以常常需要对决策树的规则进行剪枝。决策树不易表示出隐含在一个规则集里的不通过规则间的逻辑或关系，所以讲一个普通的规则集合转换成据册数并不是十分直截了当的。分类规则（if…thenclass=…）关联规则（A=B，支持度和置信度）包含例外的规则（default..exceptif…then…/if…then…else…）包含关系的规则数值预测树（线性回归、回归树、模型树）基于实例的表达规则与决策树：规则可以是对称的，而树必须首先选择一个属性进行分裂，这会导致树比一个等效的规则集大很多。在多类情况下，决策树分裂将考虑所有类别的情况，试图使分裂的纯度最大化，而规则建立法一次只集中处理一个类别，并不考虑其他类别上发生的情况。4基本方法4.1推断基本规则（1R）使用单个属性作为决策的依据，选择其中工作性能最好的那个属性。4.2统计建模（贝叶斯方法）朴素贝叶斯有独立属性的假设，这是它成为朴素的原因。1）简单的方法通常能很好地工作2）朴素贝叶斯处理属性的时候，认为属性是完全独立的，所以一些冗余属性会破坏及其学习过程。属性之间的依赖性不可避免地会降低朴素贝叶斯识别数据中究竟会发生什么的能力。然而，这种情况可以通过在决策过程中，进行属性子集选择来避免。3）对于数值型数据，正太分布假设是朴素贝叶斯的另一个限制。也可以采用其他分布形式，或者核密度估计（不把属性值的分布假设成人和特定形式的分布），或者首先将数据离散化。拓展：用于文档分类的贝叶斯模型、LDA4.3分治法：创建决策树分治法：每次只考虑一个单独的属性建立规则，然后在每个分治上递归地重复这个过程，建立决策树。几个概念：信息量=熵增益量=根节点信息量-属性节点信息量分裂信息量=节点分裂成子节点的信息量增益率=增益量/分裂信息量一些情况下，增益率修正法补偿过度，会造成倾向于选择某个属性的原因，仅仅是因为这个属性的内在信息值比其他属性要小很多。一个标准的弥补方法是选择能够得到最大增益率的属性，且那个属性的信息增益至少要等于所有属性信息增益的平均值。分治法也成为自上而下的决策树归纳法4.4覆盖算法：建立规则覆盖算法和分治算法都牵涉到要寻找某个属性进行分裂的过程，但是两者寻找最佳属性的标准是不同的。分治算法，选择一个属性能使信息增益最大化，而覆盖算法，则要选择一个属性-值配对能够使期望类别概率达到最大化。PRISM方法，可以描述为割治算法（separate-and-conquer）顺序规则（决策列）：规则顺序执行，规则之间不会冲突顺序独立的规则：规则具有模块性，但规则可能会有冲突4.5挖掘关联规则步骤：1）产生达到制定最小覆盖量（支持度）的项集；从每个项集中找出能够达到最小正确率（置信度）的规则。建立关联规则所需的计算量取决于制定的最小覆盖率（支持度），正确率的影响力较小，因为它不会影响到访问整个数据集的次数。4.6线性模型适用于数值属性的情况。4.6.1数值预测：线性回归参数求解可采用梯度下降法、最小二乘法、最大似然法4.6.2线性分类：Logistic回归()()11()1TTxzhxgxegze多分类：成对分类法，建立k(k-1)/2个分类器，如若机器学习算法需要花费与n成比例的时间去执行，则该方法需要(k-1)n的时间。这种方法耗时与类别数量呈线性关系。4.6.3使用感知器的线性分类基本思想：寻找分类超平面，也即权向量w使用条件：数据线性可分4.6.4使用winnow的线性分类使用条件：二值型属性数据集。和感知器一样，当出现错分的实例时，winnow才更新权值向量，它是错误驱动型的。Winnow算法是对于跟踪数据集上的相关属性非常有效的方法，为此称为有效属性学习期。如果一个数据集存在很多二值属性，并且其中的大部分属性不相关，那么winnow也许是一个好的候选算法。4.7基于实例的学习（最近邻）寻找一个初始的最近邻点与树的深度相关，输的深度由树的节点个数取对数；回所并检查是否存在最近邻的工作量有一小部分取决于树，另一部分取决于初始近似点的好坏程度。对于一个结构良好的树，它的节点近似于方形，这部分工作量也是取决于节点个数的对数。kD树构建要点：选择最大方差对应的轴，然后建立一个与该轴垂直的分割超平面。位置一般是取轴向的中间值或者平均值（更好，有次产生的树也不是完美平衡的，但是它的区域趋向于方形）。处理不均匀分布的数据集时呈现一个基本的冲突：既要求树有完美的平衡结构，又要求区域近似方形。更重要的是，矩形，甚至方形，并不是最好的使用形状，因为他们都有角。问题：1）每一个属性在决策上具有相同的影响力；2）很容易受干扰样本的破坏。解决方案：采用k最近邻；明智地挑选样本，然后加入数据集。最近邻法分类速度慢。当实例空间的维数增加时，这些树效率变得很低，只有当属性数量很小，最高为10，它才有应用价值。4.8聚类5可信度（性能评估）5.1训练和测试训练数据、验证数据、测试数据一般来说，训练集越大，分类器性能越好。当训练集超过一定限度时，性能提高会有所减缓。测试集越大，误差估计月准确。数据源不充足时，怎样合理地划分训练集合测试集？5.2预测性能若测试集成功率为f，则真实的成功率p（正态总体，均值为p方差为p(1-p)）在置信度为α下的置信区间为f−𝑡α2√𝑓(1−𝑓)/𝑁≤p≤f+𝑡α2√𝑓(1−𝑓)/𝑁5.3交叉验证旁置法：保留一定数量的数据作为测试，剩余的数据用于训练。分层：保证分割每一部分中类比例和整个数据集中类比例基本一致交叉验证：将数据集分成k份，其中k-1份进行训练，剩余1份进行验证，取误差率的平均值作为模型误差率估计值。预测某种机器学习技术误差率的标准方法：分层10折交叉验证。5.4其他估计法留一法：n折交叉验证（n为样本数量）缺点：计算成本高；不能分层自引导法：有放回随机抽样。自引导法对于非常小的数据集来说，可能是最佳的误差率估计方法，但是和留一法一样，也有缺陷。5.5机器学习方案比较如果要提出一个新的学习算法，需要证明信算法对问题的解决是有改进的，并且要证明观察到的改进辻估计过程中所产生的偶然结果。如果是配对样本，使用方差分析方法。5.6预测概率二次损失函数2()jjjpa信息损失函数2logip5.7计算成本不考虑成本问题，一般使用分类正确率和Kappa系数0/1ccKappaPPP式中，0P为观测一致率/oiiPPn，cP为期望一致率2/ciiPPPn。5.7.1成本敏感分类给出成本矩阵，可以计算学习模型在某个测试集上的成本5.7.2成本敏感学习在模型训练中考虑错分成本。对于二类问题，一个简单的常用方法是改变训练集实例比例（可以通过复制数据集中的实例来实现）。很多学习方案允许对实例进行加权5.7.3上升图原则：考虑投入成本，选择最优收益的样本。给定一个学习方案，输出每个测试数据集实例的类预测概率，按照预测yes概率降序排序，读取要求数量的实例。5.7.4ROC曲线ROC（receiveroperatingcharactering），用来体现击中率和虚报率之间的平衡。5.7.5反馈率-精确率曲线5.7.6讨论预测类真实类TP（正确肯定）FN错误（错误否定/漏检率）TP（错误肯定/虚报率）FN错误（正确否定）信息检索中使用的两种方法是4点平均反馈率和11点平均反馈率5.7.7成本曲线5.8评估数值预测均方误差、均方根误差、平均绝对误差、相对平方误差、相对平方根误差、相对绝对误差、相关系数5.9最短描述长度Occam剃刀原理：最好的科学理论应该是最简单的，但能揭示所有的事实真相。MDL理论和训练集描述长度之和为：(|)()MDLLETLTMDL原理和概率理论之间存在显著的联系。给定一个训练集E，我们寻找可能性最大的理论T，即寻找能使后验概率p(T|E)即样本出现后验概率最大的理论。如同贝叶斯规则的条件概率：(|)()(|)()pETpTpTEpE取其负对数求最大值，也即log((|))log(())pETpT最大。6机器学习方案6.1决策树（DecisionTree）问题：数值数型；决策树剪枝，避免过拟合；决策数转化为分类规则补充：决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。ID3算法由RossQuinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（besimple简单理论）。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性--就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。C4.5是ID3的一个改进算法，继承了ID3算法的优点。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足，在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。CART算法的全称是ClassificationAndRegressionTree，采用的是Gini指数（选Gini指数最小的特征s）作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据GINI系数来选择测试属性的决策树算法CART。决策树适用于数值型和标称型。决策树模型也有一些缺点，比如处理缺失数据时的困难、过度拟合以及忽略数据集中属性之间的相关性等。://blog.csdn.net/suipingsp/article/details/419272476.1.1数值属性二元分裂：一般在数值一半的地方设置断点并不需要对每个子节点的实例自己按照属性值重新排序6.1.2残缺值6.1.3剪枝大多数决策树采用后剪枝（可以便面暗码锁combination-lock）。决策树剪枝包含两种操作：子树置换和子树上升（只能提升最为普及的分支）。6.1.4估计误差率为何进行子树置换或者子树上升？必须使用一个独立的测试集在某个节点处进行期望误差率估计。若新的字数估计误差率较小，则用它替换原来的子树。这种估计是一种启发式估计并且建立在几个虚弱的假设上：置信度上限的使用、正太分布假设以及采用在训练集上取得的统计数据。C4.5中默认执行度为25%。6.1.5决策树归纳的复杂度O(mnlogn)+O(n(logn)^2)6.1.6从决策树到规则使用误差率估计进行规则剪枝。方法一：减少-误差（reduced-error）修剪：保留一部分原始数据作为测试集。缺点是决策树是在较少数据上建立的。方法二