《大数据》配套之四：第章数据挖掘算法下

全国高校标准教材《云计算》姊妹篇，剖析大数据核心技术和实战应用大数据刘鹏主编张燕张重生张志立副主编BIGDATA刘鹏教授，清华大学博士。现任南京大数据研究院院长、中国信息协会大数据分会副会长、中国大数据技术与应用联盟副理事长。主持完成科研项目25项，发表论文80余篇，出版专业书籍15本。获部级科技进步二等奖4项、三等奖4项。主编的《云计算》被全国高校普遍采用，被引用量排名中国计算机图书第一名。创办了知名的中国云计算（）和中国大数据（）网站。曾率队夺得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关联规则第三章数据据挖掘算法分类技术分类技术或分分类法（Classification）是一种根据据输入样本集集建立类别模模型，并按照照类别模型对对未知样本类类标号进行标标记的方法。。根据所采用的的分类模型不不同基于决策树模模型的数据分分类基于统计模型型的数据分类类基于神经网络络模型的数据据分类基于案例推理理的数据分类类基于实例的数数据分类1．决策树决策树就是通通过一系列规规则对数据进进行分类的过过程。决策树分类算算法通常分为为两个步骤：：构造决策树树和修剪决策策树。of65113.4关联规则第三章数据据挖掘算法分类技术构造决策树修剪决策树根据实际需求及所所处理数据的的特性，选择择类别标识属属性和决策树树的决策属性性集在决策属性集集中选择最有有分类标识能能力的属性作作为决策树的的当前决策节节点根据当前决策策节点属性取取值的不同，，将训练样本本数据集划分分为若干子集集①子集中的所有元组都属于同一类。②该子集是已遍历了所有决策属性后得到的。③子集中的所有剩余决策属性取值完全相同，已不能根据这些决策属性进一步划分子集。针对上一步中得到的每一个子集，重复进行以上两个步骤，直到最后的子集符合约束的3个条件之一根据符合条件不同同生成叶子节节点对决策树进行行修剪，除去去不必要的分分枝，同时也也能使决策树树得到简化。。常用的决策树树修剪策略基于代价复杂杂度的修剪悲观修剪最小描述长度修剪按照修剪的先先后顺序先剪枝（Pre-pruning）后剪枝枝（Post-pruning）of65123.4关联规规则第三章章数数据挖挖掘算算法分类技术2．k-最近邻邻最临近分类基于类比学习，是一种基于实例的学习，它使用具体的训练实例进行预测，而不必维护源自数据的抽象（或模型）。它采用n维数值属性描述训练样本，每个样本代表n维空间的一个点，即所有的训练样本都存放在n维空间中。若给定一个未知样本，k-最近邻分类法搜索模式空间，计算该测试样本与训练集中其他样本的邻近度，找出最接近未知样本的k个训练样本，这k个训练样本就是未知样本的k个“近邻”。其中的“邻近度”一般采用欧几里得距离定义：两个点

和

的Euclid距离是

。最近邻邻分类类是基基于要要求的的或懒懒散的的学习习法，，即它它存放放所有有的训训练样样本，，并且且直到到新的的（未未标记记的））样本本需要要分类类时才才建立立分类类。其其优点点是可可以生生成任任意形形状的的决策策边界界，能能提供供更加加灵活活的模模型表表示。of65133.4关联规规则第三章章数数据挖挖掘算算法案例：保险险客户户风险险分析析1．挖掘掘目标标由过去去大量量的经经验数数据发发现机机动车车辆事事故率率与驾驾驶者者及所所驾驶驶的车车辆有有着密密切的的关系系，影影响驾驾驶人人员安安全驾驾驶的的主要要因素素有年年龄、、性别别、驾驾龄、、职业业、婚婚姻状状况、、车辆辆车型型、车车辆用用途、、车龄龄等。因此，，客户户风险险分析析的挖挖掘目目标就就是上上述各各主要要因素素与客客户风风险之之间的的关系系，等等等。。2．数据据预处处理数据准准备与与预处处理是是数据据挖掘掘中的的首要要步骤骤，高高质量量的数数据是是获得得高质质量决决策的的先决决条件件。在在实施施数据据挖掘掘之前前，及及时有有效的的数据据预处处理可可以解解决噪噪声问问题和和处理理缺失失的信信息，，将有有助于于提高高数据据挖掘掘的精精度和和性能能。去除数据集集之中中的噪噪声数数据和和无关关数据据，处处理遗遗漏数数据和和清洗洗“脏脏”数数据等。数据清清洗处处理通通常包包括处处理噪噪声数数据、、填补补遗漏漏数据据值/除去异异常值值、纠纠正数数据不不一致致的问问题，，等等等。在处理理完噪噪声数数据后后，就就可以以对数数据进进行转转化，，主要要的方方法有：聚集忽略无关属性连续型型属性离离散化化等。数据清清洗数据转转化of65143.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预测模模型预测与预测测模型型第三章章数数据挖挖掘算算法预测分分析是是一种种统计计或数数据挖挖掘解解决方方案，，包含含可在在结构构化与与非结结构化化数据据中使使用以以确定定未来来结果果的算算法和和技术术，可可为预预测、、优化化、预预报和和模拟拟等许许多其其他相相关用用途而而使用用。时间序序列预预测是是一种种历史史资料料延伸伸预测测，以以时间间序列列所能能反映映的社社会经经济现现象的的发展展过程程和规规律性性，进进行引引申外外推预预测发发展趋趋势的的方法。从时间间序列列数据据中提提取并并组建建特征征，仍用用原有的的数据据挖掘掘框架架与算算法进进行数数据挖挖掘将时间间序列列数据据作为为一种种特殊殊的挖挖掘对对象，，找寻寻对应应的数数据挖挖掘算法进进行专门研研究依据研研究的的方式式分类类相似性性问题题挖掘时态模模式挖掘依据研研究的的内容容分类类依据研研究的对象分类事件序序列的的数据据挖掘掘事务序序列的的数据据挖掘掘数值序序列的的数据据挖掘掘时间序序列预预测及及数据据挖掘分类of65173.5预测模模型预测与预测测模型型第三章章数数据挖挖掘算算法预测方方案分分类时间序列预测定性预测方法依据预测方法的性质因果关系预测时间序列的统计特征1）均值函函数2）自协方方差函函数3）自相相关函函数of65183.5预测模模型预测与预测测模型型第三章章数数据挖挖掘算算法1）自回归模型2）移动平均模型3）自回归移动平均模型of6519时间序列模型预测方方案分分类3.5预测模模型时间序序列预测第三章章数数据挖挖掘算算法时间序序列：：对按时时间顺顺序排排列而而成的的观测测值集集合，，进行行数据据的预预测或或预估估。典型的的算法法：序序贯模模式挖挖掘SPMGC算法序贯模模式挖挖掘算算法SPMGC（SequentialPatternMiningBasedonGeneralConstrains）SPMGC算法可可以有有效地地发现现有价价值的的数据据序列列模式式，提提供给给大数数据专专家们们进行行各类类时间间序列列的相相似性性与预预测研究。。项集间的时间限制Cgap序列持续时间限制Cduration数据约束Cdata项的约束Citem序列长度的约束CLength其他约束时间序序列领领域约约束规规则of65203.5预测模模型时间序序列预测第三章章数数据挖挖掘算算法SPMGC算法的的基本本处理理流程程扫描时时间序序列数数据库库，获获取满满足约约束条条件且且长度度为1的序列列模式式L1，以序序列模模式L1作为初初始种种子集集根据长长度为为i-1的种子子集Li-1，通过过连接接与剪剪切运运算生生成长长度为为i并且满满足约约束条条件的的候选选序列列模式式Ci，基于于此扫扫描序序列数数据库库，并并计算算每个个候选选序列列模式式Ci的支持数数，从从而产产生长长度为I的序列模模式Li，将Li作为新新种子子集在此重复上一步，直至至没有有新的的候选选序列列模式式或新新的序序列模模式产生SPBGC算法首首先对对约束束条件件按照照优先先级进进行排排序，，然后后依据据约束束条件件产生生候选选序列列。SPBGC算法说说明了了怎样样使用用约束束条件件来挖挖掘序序贯模模式，，然而而，由由于应应用领领域的的不同同，具具体的的约束束条件件也不不尽相相同，，同时时产生生频繁繁序列列的过过程也也可采采用其其他序序贯模模式算算法。。of65213.5预测模模型案例：地震震预警警第三章章数数据挖挖掘算算法1．地震波波形数数据存存储和和计算算平台台南京云云创大大数据据有限限公司司为山山东省省地震震局研研发了了一套套可以以处理理海量量数据据的高高性能能地震震波形形数据据存储储和计计算平平台，，将从从现有有的光光盘中中导入入地震震波形形数据据并加加以管管理，，以提提供集集中式式的地地震波波形数数据分分析与与地震震预测测功能能，为为开展展各种种地震震波形形数据据应用用提供供海量量数据据存储储管理理和计计算服服务能能力。。图3-12山东省省地震震波测测数据据云平平台的的显示示界面面of65223.5预测模模型案例：地震震预警警第三章章数数据挖挖掘算算法2．地震震波形形数据据存储储和计计算平平台的的主要要性能能指标标数据存存储和和处理理指标标系统响响应时时间指指标地震波波形数数据存存储性性能指指标每年的的原始始地震震波形形数据据及相相关辅辅助信信息约约为15TB，为保保证数数据存存储的的可靠靠性，，要求求采用用3倍副本本方式式保存存数据据，云云平台台每年年需要要提供供约45TB的总存存储量量，同同时系系统必必须能能实时时接收收和处处理高高达10MB/s的入库库数据据千兆网网络环环境下下，局局域网网客户户端从从分布布式文文件存存储系系统中中读取取4096B存储内内容的的响应应时间间不高高于50毫秒采用HDFS格式进进行数数据读读取，，读取取性能能为40～80MB/s节点，，数据据规模模10PB，数据据负载载均衡衡时间间可依依据流流量配配置而而确定定，集集群重重新启启动时时间按按10PB规模计计算达达到分分钟级级别of65233.5预测模模型案例：地震震预警警第三章章数数据挖挖掘算算法3．地震震波形形数据据存储储和计计算平平台的的功能能设计计21345数据解解析数据入入库数据存存储管管理云计算算平台台的数数据应应用接接口数据异异地修修复功能设设计of65243.5预测模模型案例：地震震预警警第三章章数数据挖挖掘算算法4．平台台的组组成、、总体体构架架与功功能模模块图3-13地震波波形数数据云云平台台总体体构架架与功功能模模块of65253.5预测模模型案例：地震震预警警第三章章数数据挖挖掘算算法5．地震震中的的时间间序列列预测测地震预预测的的主要要手段段也就就是对对地震震序列列进行行特征征研究究。通通过对对地震震序列列的特特征研研究，，可以以帮助助判断断某大大地震震发生生后地地质活活动的的规律律，掌掌握一一定区区域内内地震震前后后震级级次序序间的的某种种内在在关联联性，，有利利于判判断次次地震震发生生后，，震区区地质质活动动的客客观趋趋势1）地地震震数数据据收收集集和和预预处处理理采用用SPBGC算法法，预处处理理的的流流程程步步骤骤具具体体如下下：设定定地震震序序列列的的空空间间跨跨度度，，并并划划分分震震级级标标准准M依据据地震震目目录录数数据据库库，，将将震震级级大大于于或或等等于于震震级级标标准准M的地地震震信信息息存存入入大大地地震震文件件获取取大大地地震震文文件件中中的的每每一一条条记记录录E，并并取取得得震震级级M与震震中中所所在在位位置置G扫描描地震震目目录录数数据据，，对对每每一一地地震震记记录录E，均均判判断断当当前前地地震震位位置置与与震震中中G的距距离离是是否否满满足足设设定定的的空空间间跨跨度度。。如如果果满满足足空空间间跨跨度度，，则则将将该该记记录录标标注注为为与与震震中中等等同同的的序序列列号号，，同同时时将将震震中中为为圆圆心心的的区区域域范范围围内内地地震震的的次次数数加加l；否否则则继继续续处处理理下下一一条条地地震震记录录大地地震震文文件件处处理理完完毕毕后后，，该该阶阶段段地地震震数数据据收收集集和和预预处处理理阶阶段段结束束of65263.4关联规则3.1数据挖掘概述全国国高高校校标标准准教教材材《云计计算算》姊妹妹篇篇，，剖剖析析大大数数据据核核心心技技术术和和实实战战应应用用第三章数据挖掘算法3.2分类3.3聚类3.5预测规模习题3.4关联规则3.6

数据挖掘算法综合应用of65273.6数据据挖挖掘掘算算法法综综合合应应用用案例例分析析：：精精确确营营销销中中的的关关联联规规则则应应用用数据据挖挖掘掘在在各各领领域域的的应应用用非非常常广广泛泛，，只只要要该该产产业业拥拥有有具具备备分分析析价价值值与与需需求求的的数数据据仓仓储储或或数数据据库库，，都都可可以以利利用用挖挖掘掘工工具具进进行行有有目目的的的的挖挖掘掘分分析析。。一一般般较较常常见见的的应应用用案案例例多多发发生生在在零零售售业业、、制制造造业业、、财财务务金金融融保保险险、、通通信信业业及及医医疗疗服服务务等等。。？如何何通通过过交交叉叉销销售售，，得得到到更更大大的的收收入入？？如何何在在销销售售数数据据中中发发掘掘顾顾客客的的消消费费习习性性，，并并由由交交易易记记录录找找出出顾顾客客偏偏好好的的产产品品组组合合？？如何何找找出出流流失失顾顾客客的的特特征征与与推推出出新新产产品品的的时时机机点？通过过关关联联规规则则挖挖掘掘来来发发现现和和捕捕捉捉数数据据间间隐隐藏藏的的重重要要关关联联，，从从而而为为产产品品营营销销提提供供技技术术支支撑撑。。第三三章章数数据据挖挖掘掘算算法法of65283.6数据据挖挖掘掘算算法法综综合合应应用用挖掘掘目标标的的提提出出第三三章章数数据据挖挖掘掘算算法法电子子商商务务网网站站中中的的商商品品推荐荐为例例客户户忠忠诚诚度度影响响因因素素其他他因因素素：如社会会文文化化、、国国家家政政策策等等客户户自自身身原原因因企业业原原因因数据据挖挖掘掘技技术术可可以以建建立立客客户户忠忠诚诚度度分分析析模模型型，，了了解解哪哪些些因因素素对对客客户户的的忠忠诚诚度度有有较较大大的的影影响响，，从从而而采采取取相相应应措措施施。。因因此此，，基基于于数数据据挖挖掘掘技技术术的的客客户户忠忠诚诚度度分分析析具具有有重重要要的的应应用用价价值值。。of65293.6数据据挖挖掘掘算算法法综综合合应应用用分析析方法法与与过过程程第三三章章数数据据挖挖掘掘算算法法图3-14电子子商商务务网网站站操操作作流流程程of65303.6数据据挖挖掘掘算算法法综综合合应应用用分析析方法法与与过过程程第三三章章数数据据挖挖掘掘算算法法在电电子子商商务务系系统统中中，，忠忠诚诚度度分分析析所所需需要要的的客客户户信信息息和和交交易易信信息息分分别别存存放放在在网网站站数数据据库库的的客客户户表表、、订订单单表表及及订订单单明明细细表表中中。。将客客户户的的忠忠诚诚度度分分为为4个等等级级：：0———忠忠诚诚；；1———由由忠忠诚诚变变为为不不忠忠诚诚；；2———由由不不忠忠诚诚变变为为忠忠诚诚；；3———不不忠忠诚诚。。客户编号性别年龄（岁）教育程度……距最近一次购买

时间（天）月均购买频率已消费

金额忠诚度级别20120001男40大专……53.4801.6020120002女28本科……111.9246.31………………………………………………表3-9经抽抽取取而而成成的的客客户户信信息息表表所得得到到的的用用户户数数据据很很难难做做到到完完整整全全面面，，用用户户在在注注册册时时可可能能选选择择不不填填注注册册信信息息的的几几项项，，造造成成数数据据项项空空缺缺。。对对于于空空缺缺的的数数据据项项，，要要视视情情况况排排除除或或填填入入默默认认值值。按照一般般的统计计划分经经验来对对属性值值进行分分段，实实现离散散化。of65313.6数据挖掘掘算法综综合应用用分析方法与过过程第三章数数据挖挖掘算法法客户编号性别年龄（岁）教育程度……距最近一次购买时间（天）月均购买频率已消费金额（元）忠诚度级别20120001男30～40大专……0～102～4800～1000020120002女20～30本科……10～200～20～5001………………………………………………表3-10经离散变变换后的的客户信信息表本案例采采用基于于信息论论的ID3决策树分分类算法法进行客客户忠诚诚度分析析。客户群细分使得得公司可以以更好地地识别不不同的客客户群体体，区别别对待不不同客户户，采取取不同的的客户策策略，达达到最优优