03《大数据》配套PPT之四：第3章数据挖掘算法(下)

全国高校标准教材《云计算》姊妹篇，剖析大数据核心技术和实战应用大数据刘鹏主编张燕张重生张志立副主编BIGDATA刘鹏教授，清华大学博士。现任南京大数据研究院院长、中国信息协会大数据分会副会长、中国大数据技术与应用联盟副理事长。主持完成科研项目25项，发表论文80余篇，出版专业书籍15本。获部级科技进步二等奖4项、三等奖4项。主编的《云计算》被全国高校普遍采用，被引用量排名中国计算机图书第一名。创办了知名的中国云计算（chinacloud.cn）和中国大数据（thebigdata.cn）网站。曾率队夺得2002PennySort国际计算机排序比赛冠军，两次夺得全国高校科技比赛最高奖，并三次夺得清华大学科技比赛最高奖。荣获“全军十大学习成才标兵”（排名第一）、南京“十大杰出青年”、江苏省中青年科学技术带头人、清华大学“学术新秀”等称号。3.1数据挖掘概述全国高校标准教材《云计算》姊妹篇，剖析大数据核心技术和实战应用第三章数据挖掘算法3.2分类3.3聚类3.1数据挖掘概述3.5预测规模习题3.6数据挖掘算法综合应用3.4关联规则of6533.4关联规则关联规则是数据挖掘中最活跃的研究方法之一，是指搜索业务系统中的所有细节或事务，找出所有能把一组事件或数据项与另一组事件或数据项联系起来的规则，以获得存在于数据库中的不为人知的或不能确定的信息，它侧重于确定数据中不同领域之间的联系，也是在无指导学习系统中挖掘本地模式的最普通形式。More应用市场：市场货篮分析、交叉销售（CrossingSale）、部分分类（PartialClassification）、金融服务（FinancialService），以及通信、互联网、电子商务······第三章数据挖掘算法of6543.4关联规则第三章数据挖掘算法一般来说，关联规则挖掘是指从一个大型的数据集（Dataset）发现有趣的关联（Association）或相关关系（Correlation），即从数据集中识别出频繁出现的属性值集（SetsofAttributeValues），也称为频繁项集（FrequentItemsets，频繁集），然后利用这些频繁项集创建描述关联关系的规则的过程。3.4.1关联规则的概念关联规则挖掘问题：发现所有的频繁项集是形成关联规则的基础。通过用户给定的最小支持度，寻找所有支持度大于或等于Minsupport的频繁项集。通过用户给定的最小可信度，在每个最大频繁项集中，寻找可信度不小于Minconfidence的关联规则。发现频繁项集生成关联规则如何迅速高效地发现所有频繁项集，是关联规则挖掘的核心问题，也是衡量关联规则挖掘算法效率的重要标准。of6553.4关联规则第三章数据挖掘算法3.4.2频繁项集的产生及其经典算法格结构（LatticeStructure）常常被用来枚举所有可能的项集。图3-10项集的格of6563.4关联规则第三章数据挖掘算法3.4.2频繁项集的产生及其经典算法格结构（LatticeStructure）常常被用来枚举所有可能的项集。查找频繁项目集经典的查找策略基于精简集的查找策略基于最大频繁项集的查找策略按照挖掘的策略不同经典的挖掘完全频繁项集方法基于广度优先搜索策略的关联规则算法基于深度优先搜索策略的算法Apriori算法、DHP算法FP-Growth算法、ECLAT算法COFI算法与经典查找不同方法基于精简集的方法基于最大频繁项目集的方法A-close算法MAFIA算法、GenMax算法DepthProject算法of6573.4关联规则第三章数据挖掘算法3.4.2频繁项集的产生及其经典算法1．Apriori算法Apriori算法基于频繁项集性质的先验知识，使用由下至上逐层搜索的迭代方法，即从频繁1项集开始，采用频繁k项集搜索频繁k+1项集，直到不能找到包含更多项的频繁项集为止。Apriori算法由以下步骤组成，其中的核心步骤是连接步和剪枝步：生成频繁1项集L1连接步剪枝步生成频繁k项集Lk重复步骤（2）～（4），直到不能产生新的频繁项集的集合为止，算法中止。性能瓶颈Apriori算法是一个多趟搜索算法可能产生庞大的候选项集of6583.4关联规则第三章数据挖掘算法3.4.2频繁项集的产生及其经典算法2．FP-Growth算法频繁模式树增长算法（FrequentPatternTreeGrowth）采用分而治之的基本思想，将数据库中的频繁项集压缩到一棵频繁模式树中，同时保持项集之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树，每个条件子树对应一个频繁项，从而获得频繁项集，最后进行关联规则挖掘。FP-Growth算法由以下步骤组成：扫描事务数据库D，生成频繁1项集L1将频繁1项集L1按照支持度递减顺序排序，得到排序后的项集L1构造FP树通过后缀模式与条件FP树产生的频繁模式连接实现模式增长1234图3-11FP树的构造of6593.4关联规则第三章数据挖掘算法3.4.2频繁项集的产生及其经典算法3．辛普森悖论虽然关联规则挖掘可以发现项目之间的有趣关系，在某些情况下，隐藏的变量可能会导致观察到的一对变量之间的联系消失或逆转方向，这种现象就是所谓的辛普森悖论（Simpson’sParadox）。为了避免辛普森悖论的出现，就需要斟酌各个分组的权重，并以一定的系数去消除以分组数据基数差异所造成的影响。同时必须了解清楚情况，是否存在潜在因素，综合考虑。of65103.4关联规则第三章数据挖掘算法3.4.3分类技术分类技术或分类法（Classification）是一种根据输入样本集建立类别模型，并按照类别模型对未知样本类标号进行标记的方法。根据所采用的分类模型不同基于决策树模型的数据分类基于统计模型的数据分类基于神经网络模型的数据分类基于案例推理的数据分类基于实例的数据分类1．决策树决策树就是通过一系列规则对数据进行分类的过程。决策树分类算法通常分为两个步骤：构造决策树和修剪决策树。of65113.4关联规则第三章数据挖掘算法3.4.3分类技术构造决策树修剪决策树根据实际需求及所处理数据的特性，选择类别标识属性和决策树的决策属性集在决策属性集中选择最有分类标识能力的属性作为决策树的当前决策节点根据当前决策节点属性取值的不同，将训练样本数据集划分为若干子集①子集中的所有元组都属于同一类。②该子集是已遍历了所有决策属性后得到的。③子集中的所有剩余决策属性取值完全相同，已不能根据这些决策属性进一步划分子集。针对上一步中得到的每一个子集，重复进行以上两个步骤，直到最后的子集符合约束的3个条件之一根据符合条件不同生成叶子节点对决策树进行修剪，除去不必要的分枝，同时也能使决策树得到简化。常用的决策树修剪策略基于代价复杂度的修剪悲观修剪最小描述长度修剪按照修剪的先后顺序先剪枝（Pre-pruning）后剪枝（Post-pruning）of65123.4关联规则第三章数据挖掘算法3.4.3分类技术2．k-最近邻最临近分类基于类比学习，是一种基于实例的学习，它使用具体的训练实例进行预测，而不必维护源自数据的抽象（或模型）。它采用n维数值属性描述训练样本，每个样本代表n维空间的一个点，即所有的训练样本都存放在n维空间中。若给定一个未知样本，k-最近邻分类法搜索模式空间，计算该测试样本与训练集中其他样本的邻近度，找出最接近未知样本的k个训练样本，这k个训练样本就是未知样本的k个“近邻”。其中的“邻近度”一般采用欧几里得距离定义：两个点和的Euclid距离是。12(,,,)nXxxx12(,,,)nYyyy21(,)()niiidXYxy最近邻分类是基于要求的或懒散的学习法，即它存放所有的训练样本，并且直到新的（未标记的）样本需要分类时才建立分类。其优点是可以生成任意形状的决策边界，能提供更加灵活的模型表示。of65133.4关联规则第三章数据挖掘算法3.4.4案例：保险客户风险分析1．挖掘目标由过去大量的经验数据发现机动车辆事故率与驾驶者及所驾驶的车辆有着密切的关系，影响驾驶人员安全驾驶的主要因素有年龄、性别、驾龄、职业、婚姻状况、车辆车型、车辆用途、车龄等。因此，客户风险分析的挖掘目标就是上述各主要因素与客户风险之间的关系，等等。2．数据预处理数据准备与预处理是数据挖掘中的首要步骤，高质量的数据是获得高质量决策的先决条件。在实施数据挖掘之前，及时有效的数据预处理可以解决噪声问题和处理缺失的信息，将有助于提高数据挖掘的精度和性能。去除数据集之中的噪声数据和无关数据，处理遗漏数据和清洗“脏”数据等。数据清洗处理通常包括处理噪声数据、填补遗漏数据值/除去异常值、纠正数据不一致的问题，等等。在处理完噪声数据后，就可以对数据进行转化，主要的方法有：聚集忽略无关属性连续型属性离散化等。数据清洗数据转化of65143.4关联规则第三章数据挖掘算法3.4.4案例：保险客户风险分析3．关联规则挖掘影响驾驶人员安全驾驶的主要因素年龄性别驾龄职业婚姻状况车辆车型车辆用途车龄其他根据前述关联规则的生成方法，得到挖掘出来的客户风险关联规则序号关联规则支持度置信度1驾龄（X，A）∧被保车辆的价值（X，A）年赔付金额（X，B）0.18250.29652投保人年龄（X，A）∧驾龄（X，A）年赔付次数（X，B）0.16790.25713驾龄（X，B）∧车辆用途（X，A）年赔付金额（X，B）0.16630.33374驾龄（X，B）∧车辆用途（X，B）年赔付次数（X，A）0.17890.48515驾龄（X，B）∧被保车辆的价值（X，C）年赔付金额（X，C）0.18090.30036驾龄（X，C）∧车辆用途（X，B）年赔付次数（X，A）0.19940.58647驾龄（X，C）∧被保车辆的价值（X，C）∧车辆用途（X，C）年赔付次数（X，A）0.10310.66398驾龄（X，A）∧被保车辆的价值（X，A）∧车辆用途（X，B）年赔付金额（X，B）0.10250.36549投保人年龄（X，B）∧驾龄（X，A）∧被保车辆的价值（X，D）年赔付金额（X，D）0.09340.454610驾龄（X，B）∧被保车辆的价值（X，A）∧车辆用途（X，A）年赔付金额（X，B）0.09680.448711投保人年龄（X，C）∧被保车辆的价值（X，C）∧车辆用途（X，C）年赔付金额（X，B）0.09090.353112投保人年龄（X，C）∧驾龄（X，B）∧被保车辆的价值（X，C）年赔付次数（X，A）0.08270.6094表3-7客户风险关联规则详细分析所得数据，可以为公司业务提供数据支撑，针对不同客户提供偏好服务，既能确保公司收益，又能给予用户更多的实惠。of65153.4关联规则3.1数据挖掘概述全国高校标准教材《云计算》姊妹篇，剖析大数据核心技术和实战应用第三章数据挖掘算法3.2分类3.3聚类3.4关联规则习题3.6数据挖掘算法综合应用3.5预测规模of65163.5预测模型3.5.1预测与预测模型第三章数据挖掘算法预测分析是一种统计或数据挖掘解决方案，包含可在结构化与非结构化数据中使用以确定未来结果的算法和技术，可为预测、优化、预报和模拟等许多其他相关用途而使用。时间序列预测是一种历史资料延伸预测，以时间序列所能反映的社会经济现象的发展过程和规律性，进行引申外推预测发展趋势的方法。从时间序列数据中提取并组建特征，仍用原有的数据挖掘框架与算法进行数据挖掘将时间序列数据作为一种特殊的挖掘对象，找寻对应的数据挖掘算法进行专门研究依据研究的方式分类相似性问题挖掘时态模式挖掘依据研究的内容分类依据研究的对象分类事件序列的数据挖掘事务序列的数据挖掘数值序列的数据挖掘时间序列预测及数据挖掘分类of65173.5预测模型3.5.1预测与预测模型第三章数据挖掘算法预测方案分类时间序列预测定性预测方法依据预测方法的性质因果关系预测时间序列的统计特征1）均值函数t[]()ttEXxfxdx2）自协方差函数,(,)[()()]tststtssCovxxExExxEx3）自相关函数,,,,tststtss