《大数据导论》课件 第5章 大数据分析与挖掘

第5章

大数据分析与挖掘演讲人2024/12/24本章学习目标了解数据分析的常用方法了解数据挖掘的典型算法培养分析问题的辩证观，以及探索未知、追求卓越的品质目录5.1引言5.2描述性数据分析5.3回归分析5.4关联分析的简介5.5分类算法的简介5.6聚类算法的简介5.7分布式数据挖掘算法5.8数据挖掘的典型应用5.9小结5.1引言数据分析是指用传统的统计学方法对收集的数据进行分析，提取有用的信息并形成结论，然后对数据加以详细的研究和概括总结的过程。数据分析可以划分为描述性数据分析、探索性数据分析和验证性数据分析。其中，描述性数据分析主要是对数据做统计性描述，包括数据的频数分析、集中趋势分析、离散趋势分析等；探索性数据分析侧重于在数据中发现新的特征；而验证性数据分析则侧重于对已有假设的证实或证伪。数据挖掘是指从大量的数据中提取隐含的、先前未知的、有价值的知识和规律的过程。数据挖掘是深层次的数据分析，数据分析是浅层次的数据挖掘，数据挖掘更偏重于探索性数据分析，因为数据挖掘的重点是从数据中发现知识和规律。5.1引言数据分析与数据挖掘的具体区别如下。（1）数据分析主要侧重于通过观察数据来对历史数据进行统计学分析；而数据挖掘通过从数据中发现知识和规律来对未来的某些可能性做出预测分析，其更注重分析数据间的内在联系。（2）数据分析往往从一个假设出发，需要自行建立方程或模型来检验是否与假设吻合；而数据挖掘一般不需要假设，可以自动建立和训练模型，如关联规则和聚类分析。（3）数据分析往往处理常规的数据类型，如数值型或标称型数据；而数据挖掘能够处理更多类型的数据，如图像、视频、声音、文本等多媒体数据。5.1引言图5-1KDD过程示意图从大量数据中提取对人们有用的信息是一个知识挖掘的过程，因此数据挖掘也被称为“基于数据库的知识发现”（KnowledgeDiscoveryinDatabase，KDD），是指从数据中提取有效的、新颖的、潜在有用的、最终可被理解的模式的过程。图5-1所示为KDD的过程示意图，整个KDD的过程可以被分为数据清洗与集成、数据选择与转换、数据分析与挖掘、模式评估与知识表示4个阶段。5.2描述性数据分析所谓描述性数据分析是指用统计学方法，描述数据的统计特征量，分析数据的分布特性。主要包括数据的集中趋势分析（CentralTendency）、数据离散趋势分析（DispersionTendency）、数据的频率分布（FrequencyDistribution）等。5.2描述性数据分析5.2.1数据的集中趋势度量1.均值截断均值：去掉最高值和最低值后计算的均值，可以抵消少数极端值的影响，如薪水的截断均值可以消除超高收入极端值对平均薪资的影响。5.2描述性数据分析2.中位数中位数指的是按顺序排列的一组数据中居于中间位置的数，它是奇数个数据的中间值，或是偶数个数据的中间两个值的平均值。【案例5-1】求20个数57,55,85,24,33,49,94,2,8,51,71,30,91,6,47,50,65,43,41,7的中位数。首先对数据从小到大排序，结果为：2，6，7，8，24，30，33，41，43，47，49，50，51，55，57，65，71，85，91，94。中间两个数为47和49，因此该组数据的中位数为48。相较于均值，中位数有着更好的抗干扰性，例如，在99个年收入10万的人中加入一个年收入1000万的人，可以把平均年收入提高到19.9万，但这一均值实际上并没有很好地反映出这个人群的年收入特征，而中位数对这个问题并没有那么敏感。5.2描述性数据分析3.众数众数是指在一组数据中出现次数最多的数，即出现频率最高的那个数，众数也被称作数据的“模”。图5-2所示为对称数据、右偏数据和左偏数据的中位数、均值和众数的位置示意图，可以观察到以下现象：①对称数据的中位数、均值和众数是重合的；②右偏态（正偏态）数据的均值位于中位数和众数的右侧；③左偏态（负偏态）数据的均值位于中位数和众数的左侧。5.2描述性数据分析3.众数图5-2对称数据、右偏数据和左偏数据的中位数、均值和众数的位置示意图。提示：所谓左偏态和右偏态指的是均值相对于众数的位置，均值在众数左边则为左偏态，在众数右边则为右偏态。5.2描述性数据分析5.2.2数据的离散趋势度量1.方差在统计描述中，方差用来计算每一个变量（观察值）与平均值之间的差异，它是集合中每个数据与均值差的平方和。总体方差的计算公式为在实际计算中，总体均值难以得到时，应用样本统计量代替总体均值，经校正后，样本方差的计算公式为方差的值越大说明该数据集的波动越大。当数据分布比较分散时，各个数据与平均值之差的平方和较大，方差就较大；当数据分布比较集中时，各个数据与平均值之差的平方和较小，方差就较小。5.2描述性数据分析2.四分位数四分位数也称四分位点，将所有数值按大小顺序排列并分成四等份，处于三个分割点位置的就是四分位数，如图5-3所示。（1）第一四分位数（Q1），又称下四分位数，等于该样本中所有数值由小到大排列后第25%的数字。（2）第二四分位数（Q2），又称中位数，等于该样本中所有数值由小到大排列后第50%的数字。（3）第三四分位数（Q3），又称上四分位数，等于该样本中所有数值由小到大排列后第75%的数字。（4）四分位距（InterQuartileRange，IQR）：第三四分位数与第一四分位数之差。图5-3四分位数的示意图5.2描述性数据分析2.四分位数例如，有一组数据：6,7,15,36,39,40,41,42,43,47,49，将其分为四等份，根据四分位数的定义可知15是第一四分位数，40是第二四分位数，43是第三四分位数。5.2描述性数据分析3.五数概括数据分布形状的完整概括可以用“五数概括”来描述，包括中位数、第二四分位数和第三四分位数、最小值和最大值。五数概括通常用箱形图（盒图）进行可视化表示。箱形图又称盒图，其将五数概括可视化，数据分布用一个盒子来表示，如图5-4所示。图5-4箱形图示例5.2描述性数据分析3.五数概括在箱形图中，盒子两端是第一四分位数和第三“四分位数”，“中位数”在盒子里用一条线标记出来，“外边界”是盒子外面延伸到最大值和最小值的两条线，也称为“胡须”。例如，图5-5所示为学生成绩分布的箱形图示例，可以从图中观察到学生的英语成绩相对其他科目普遍较好，而数学成绩则大多位于80分以下，成绩集中在65～78之间。图5-5学生成绩分布的箱形图示例5.2描述性数据分析4.离散系数离散系数又称变异系数，样本的离散系数是样本的标准差与样本的平均值之比：

。在公式中，表示标准差。5.2描述性数据分析4.离散系数【案例5-2】表5-1中有两组分别代表成人和幼儿身高的数据，用离散系数比较这两组数据的分布特性。表5-1成人与幼儿的数据两组数据平均值相差很大，标准差不能判断各自数据差异的大小。但通过计算离散系数可以看出，虽然成人组的标准差大于幼儿组，但是幼儿组的离散系数明显大于成人组，因此可以说明，幼儿组的身高差异比成人组大。组别数据/cm均值标准差离散系数成人166，167，169，169，169，170，170，171，171，171，171，172，173，173，173，175，175，176，177，179171.853.330.0194幼儿67，68，69，70，70，71，71，71，72，72，72，72，72，72，73，74，75，76，76，77722.640.03675.2描述性数据分析5.2.3数据的偏态特性度量1.偏度偏度是描述分布偏离对称程度的特征数，也称为偏态系数，是统计数据分布偏斜方向和程度的度量，是统计数据分布非对称程度的数字特征。5.2描述性数据分析1.偏度图5-6所示为是偏度分别等于0、大于0和小于0的三类数据分布特性示意图。图5-6偏度与数据分布特性示意图偏度大于0为正偏态（也称右偏态）分布，这种情况的数据平均值大于中位数（平均值在中位数右边），中位数又大于众数。曲线的形态是右侧偏长、左侧偏短。偏度小于0为负偏态（也称左偏态）分布，这种情况的数据平均值小于中位数（平均值在中位数左边），中位数又小于众数。曲线的形态是左侧偏长、右侧偏短。5.2描述性数据分析2.峰度峰度系数是用来反映频数分布曲线顶端尖峭或扁平程度的指标。通过对峰度系数的测量，我们能够判定数据分布相对于正态分布是更陡峭还是平缓。5.2描述性数据分析2.峰度图5-7所示为不同峰度的数据曲线的形状示意图。图5-7不同峰度的数据曲线的形状示意图5.2描述性数据分析5.2.4使用Excel软件对数据进行描述统计使用Excel软件可以很方便地对数据进行描述统计，在使用该功能前，需要先在“加载项”对话框中勾选“分析工具库”复选框，然后单击“数据”菜单中的“数据分析”按钮，在打开的“数据分析”对话框中选择“描述统计”选项，完成后即可实现该功能。在Excel中对数据进行描述统计的示意图如图5-8所示。图5-8在Excel中对数据进行描述统计的示意图5.3回归分析所谓回归分析，是在现有观察数据的基础上，利用数理统计方法建立因变量与自变量之间的回归关系函数表达式（回归方程）。这种技术通常用于预测分析、时间序列模型以及探索变量之间的因果关系。“回归”一词是由英国著名统计学家弗朗西斯高尔顿（FrancisGalton,1822—1911年）引入的，他是最先应用统计方法研究两个变量之间关系问题的人。弗朗西斯高尔顿对父母身高与儿女身高之间的关系很感兴趣，并致力于该方面的研究。弗朗西斯高尔顿发现，虽然有一个趋势：父母高，儿女也高；父母矮，儿女也矮，但从平均意义上讲，尽管父母双亲都异常高或异常矮，儿女的身高也并非普遍地异常高或异常矮，而是具有“回归”于人口总平均身高的趋势。5.3回归分析在回归分析中，当研究的因果关系只涉及因变量和一个自变量时，叫作一元回归分析；当研究的因果关系涉及因变量和两个或两个以上的自变量时，叫作多元回归分析。此外，在回归分析中，又依据描述自变量与因变量之间关系的函数表达式是线性的还是非线性的，将回归分析分为线性回归分析和非线性回归分析。5.3回归分析5.3.1一元线性回归模型回归模型是用来描述因变量如何依赖自变量和随机误差项的方程，线性回归通过使用最佳的拟合直线（也就是回归线）来建立因变量和一个或多个自变量之间的联系。5-9所示为一元线性回归示意图。在图中，小圆点表示原始数据，直线表示回归线。图5-9一元线性回归示意图5.3回归分析5.3.1一元线性回归模型5.3回归分析5.3.1一元线性回归模型最小二乘估计是求解线性回归方程的最常用方法，最小二乘法的原理就是所选的样本回归函数使得所有y的估计值与真实值差的平方和最小。【案例5-3】用Excel软件进行某家公司广告费与销售额的一元线性回归分析。某家公司每月的广告费和销售额如表5-2所示。表5-2某家公司每月的广告费和销售额广告费/万元489871261069销售额/万元92022151723182510205.3回归分析5.3.1一元线性回归模型如果我们把广告费和销售额画在二维坐标系内，就能够得到一个散点图，如果想探索广告费和销售额的关系，可以利用一元线性回归做出一条回归线方程，结果（取小数点后4位）为

y=2.2516+1.9808x该例子中的样本数据点与回归线如图5-10所示。图5-10样本数据点与回归线5.3回归分析5.3.1一元线性回归模型我们用Excel软件对该例子进行回归分析。首先在Excel表中输入X和Y两列数据（见图5-11）；接着在“数据”菜单中单击“数据分析”按钮，在打开的“数据分析”对话框中选择“回归”选项，最后单击“确定”按钮，出现如图5-12所示的对话框。5.3回归分析5.3.1一元线性回归模型图5-11用Excel进行回归分析示意图5.3回归分析5.3.1一元线性回归模型在“回归”对话框中选中“Y值输入区域”和“X值输入区域”数值框，在“输出选项”街区中单击“新工作表组”单选按钮，在“残差”选区中勾选“线性拟合图”复选框，单击“确定”按钮，则会在新工作表中出现计算结果，如图5-12所示。其中Coefficients的两个值2.25159915和1.98081023就是线性回归方程的两个系数（截距和斜率）。图5-12回归对话框5.3回归分析5.3.1一元线性回归模型图5-13回归分析结果5.3回归分析5.3.1一元线性回归模型表5-3回归分析结果中部分参数的说明注：为了与图5-13所示的回归分析结果一致，表格中的变量均用正体字母表示。参数含义MultipleR表示自变量X和因变量Y的相关系数，一般在-1～1之间，绝对值越靠近1则相关性越强，越靠近0则相关性越弱RSquare（R²）是拟合优度（GoodnessofFit）的统计量，拟合优度是指回归线对观测值的拟合程度。R²的最大值为1。R²的值越接近1，说明回归直线对观测值的拟合程度越好；反之，R²的值越小，说明回归直线对观测值的拟合程度越差FF值越大，越能说明总体回归关系越强SignificanceF显著性指标，一般以小于0.05为显著，小于0.01为非常显著df自由度的个数SS离均差平方和MS方差tStatT检验，主要用于样本含量较小（如n<30）且总体标准差σ未知的正态分布5.3回归分析5.3.2其他类型的回归模型1.多元线性回归模型在回归分析中，如果有两个或两个以上的自变量，就称为多元回归分析，多元线性回归模型可以表示为对于多元线性回归模型，同样可以用最小二乘法估计回归方程的参数，具体过程不再赘述。5.3回归分析5.3.2其他类型的回归模型【案例5-4】用Excel软件进行多元线性回归分析。表5-4所示为我国某个城市的用电量指标统计表，将“年用电量”作为因变量Y，将“GDP”和“全社会投资额”作为自变量X，进行多元线性回归分析。。表5-4某个城市的用电量指标统计表5.3回归分析5.3.2其他类型的回归模型用Excel软件中的回归分析工具，得到如图5-14所示的结果。该例子的多元线性回归方程为 年用电量=28925.98+0.046188×GDP+0.118491×全社会投资额从结果可以看到两个自变量都通过了T-检验，SignificanceF的值为2.94929E-12，效果非常好。如果回归模型的因变量是自变量的一次以上函数形式，回归规律在图形上表现为形态各异的各种曲线（见图5-15），那么将其称为非线性回归。图5-15非线性回归的示意图5.3回归分析2.非线性回归模型5.3回归分析2.非线性回归模型求解非线性回归问题需要预先选择适配的曲线类型，基本方法如下:（1）确定变量间的依存关系，根据实际资料做散点图。（2）按照图形的分布形状选择合适的非线性回归模型（回归函数的类型），常见的函数有多项式回归、双曲线函数、幂函数、二次函数和对数函数等。（3）用某种优化方法确定回归模型中的未知参数。5.4关联分析的简介关联分析也称为关联规则挖掘（AssociationRulesMining），是指在交易数据、关系数据或其他信息载体中，发现对象之间隐含关系与规律的过程。关联分析的一个典型例子是购物篮分析。商家通过对顾客购物行为的分析，可以发现顾客放入其购物篮中不同商品之间的联系，以此分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，挖掘商品之间的联系，这种联系的发现可以帮助零售商制定营销策略。5.4关联分析的简介5.4.1“啤酒与尿布”的故事“啤酒与尿布”之间的联系是关联分析中的经典案例，被人津津乐道。这个故事发生于20世纪90年代的美国沃尔玛超市中，超市管理人员分析销售数据时发现在某些特定的情况下，“啤酒”与“尿布”看上去毫无关系的两件商品会经常出现在同一个购物篮中，这种独特的现象引起了管理人员的注意。经过后续调查发现，这种现象时常出现在年轻的父亲身上。在美国有婴儿的家庭中，一般是母亲在家中照看婴儿，年轻的父亲负责去超市购买尿布。父亲在购买尿布时，往往会顺便为自己购买啤酒，这样就会出现啤酒与尿布这两件看上去不相干的商品经常会出现在同一个购物篮中的现象。5.4关联分析的简介5.4.1“啤酒与尿布”的故事沃尔玛超市发现了这一独特的现象，开始在卖场尝试将啤酒与尿布摆放在相同的区域，让年轻的父亲可以很容易地同时找到这两件商品，没想到这个举措居然使啤酒和尿布的销量都大幅增加了。在这个故事中，通过分析购物篮中的商品集合数据，找出商品之间的联系，发现客户的购买模式，采取相应举措，从而获得更多的商品销售收入。5.4关联分析的简介5.4.2常用的关联分析算法简介常用的关联分析算法包含Apriori算法、FP-Growth算法、灰色关联分析法和Eclat算法等，表5-5所示为几种常用的关联分析算法。表5-5几种常用的关联分析算法算法名称算法描述Apriori算法关联分析经典的算法，它可以用来找出数据集中频繁出现的项集FP-Growth算法FP-Growth算法是一种对Apriori算法改进的算法，它将提供频繁项集的数据库压缩到高效的数据结构频繁模式树（FP-tree）上，减少候选频繁项集的数量Eclat算法一种深度优先算法，采用垂直数据表示形式，在概念格理论的基础上利用基于前缀的等价关系将搜索空间划分为较小的子空间灰色关联分析法分析和确定各个因素之间的影响程度，或是基于若干个子因素（子序列）对主因素（母序列）的贡献度而进行的一种分析方法5.4关联分析的简介5.4.2常用的关联分析算法简介接下来用一个实例来介绍Apriori算法的基本原理。表5-6所示为去一家超市购物的几名客户购买的商品列表，表中的一条记录被称为“交易”，每个物品被称为“项”。5-6客户购买的商品列表订单编号购买的商品T1牛奶、面包、尿布T2面包、尿布、啤酒、可乐T3牛奶、尿布、啤酒、鸡蛋T4牛奶、面包、尿布、啤酒T5牛奶、面包、尿布、可乐5.4关联分析的简介1.Apriori算法的几个术语首先结合表5-6中的数据介绍在Apriori算法中用到的几个术语。1）支持度支持度指的是某个商品组合出现的次数与总次数之间的比例。在表5-6的5笔订单中，“牛奶”出现了4次，那么在这5笔订单中“牛奶”的支持度就是4/5；“牛奶＋面包”出现了3次，那么“牛奶+面包”的支持度为3/5，可以表示为support({牛奶,面包})=3/55.4关联分析的简介2）置信度（confidence）置信度是指购买了商品A，会有多大的概率购买商品B。置信度是一个条件概率，就是在A发生的情况下，B发生的概率是多少。根据表5-6的数据，可以观察到：置信度（牛奶→啤酒）=2/4；置信度（啤酒→牛奶）=2/3，可以表示为

confidence(啤酒→牛奶)=2/35.4关联分析的简介3）提升度提升度表示的是A的出现，对B出现的概率提升的程度。

lift(A→B)=confidence(A→B)/support(B)这个公式是用来衡量在A出现的情况下，是否会对B出现的概率有所提升。所以提升度有如下3种可能。（1）提升度

(A→B)>1：代表有提升。（2）提升度

(A→B)=1：代表没有提升，也没有下降。（3）提升度

(A→B)<1：代表有下降。5.4关联分析的简介2.Apriori算法的工作流程首先我们把上面案例中的商品用ID来代表，将牛奶、面包、尿布、可乐、啤酒、鸡蛋的ID分别设置为1～6，表5-6就变为表5-7所示的形式。表5-7物品编号的客户购买的商品列表订单编号购买的商品T11、2、3T22、3、5、4T31、3、5、6T41、2、3、5T51、2、3、45.4关联分析的简介2.Apriori算法的工作流程Apriori算法其实就是查找频繁项集的过程，所以首先需要定义什么是频繁项集。频繁项集就是支持度大于或等于最小支持度阈值的项集，项集可以是单个的商品，也可以是商品的组合。小于最小支持度的项集就是非频繁项集。在这个例子中，假设指定的最小支持度是0.5，接下来看Apriori算法是如何运算的。首先计算单个商品的支持度，也就是得到k=1项的支持度（注：k=1表示项集的事件只包含1个元素），如表5-8所示。表5-8k=1项的支持度商品项集支持度14/524/535/542/553/561/55.4关联分析的简介2.Apriori算法的工作流程因为最小支持度是0.5，所以商品4、6不属于频繁项集，于是经过筛选后的频繁项集如表5-9所示。在这个基础上，我们将表5-9中所列的商品（1、2、3和5）两两组合，得到k=2项的支持度，如表5-10所示。商品项集支持度14/524/535/553/5表5-9

大于最小支持度的k=1项（频繁项集）5.4关联分析的简介2.Apriori算法的工作流程表5-10k=2项的支持度商品项集支持度1，23/51，34/51，52/52，34/52，52/53，53/55.4关联分析的简介2.Apriori算法的工作流程我们再筛掉小于最小值支持度0.5的商品组合，可以得到如表5-11所示的结果。表5-11大于最小支持度的k=2项商品项集支持度1，23/51，34/52，34/53，53/55.4关联分析的简介2.Apriori算法的工作流程我们再将商品进行K=3项的组合，可以得到如表5-12所示的结果。表5-12

k=3项的支持度商品项集支持度1，2，33/51，3，52/52，3，52/51，2，51/55.4关联分析的简介2.Apriori算法的工作流程我们再筛掉小于最小值支持度0.5的商品组合，可以得到如表5-13所示的结果。表5-13频繁项集的最终结果商品项集支持度1，2，33/5通过上面这个过程，我们最终可以得到K=3项的频繁项集{1,2,3}，也就是{牛奶、面包、尿布}的组合。5.4关联分析的简介3.Apriori算法的流程Apriori算法的流程如下。（1）K=1，计算K项集的支持度。（2）筛选掉小于最小支持度的项集。（3）如果项集为空，则对应K-1项集的结果为最终结果。（4）否则K=K+1，重复1-3步。5.4关联分析的简介3.Apriori算法的缺点Apriori算法的缺点如下。（1）采用排列组合的方式，把所有可能的项集都组合出来了，可能产生大量的候选集。（2）每次计算都需要重新扫描数据集，来计算每个项集的支持度。如果这是一个大型的数据集，这种扫描会大大增加系统的开销。为了改进Apriori算法的不足，韩嘉炜等人于2000年提出FP-Growth算法，它将提供频繁项集的数据库压缩到高效的数据结构FP-tree上，减少候选频繁项集的数量。5.5分类算法的简介分类算法的目标是找到每个样本到类别的对应法则，前提是训练数据的类别是已存在的，即是有标签的数据，属于有监督学习类型。其典型的应用有信贷审批、故障诊断、欺诈检测、客户类型判别等。分类算法的流程分为两大步骤（见图5-16）。（1）模型构建：用有标签的数据构建分类模型。（2）预测：预测无标签数据的类别。图5-16分类算法的流程示意图5.5分类算法的简介

主要的分类算法有：k最近邻（K-NearestNeighbor，KNN）算法、决策树（DecisionTree）算法、贝叶斯分类（BayesianClassification）算法、支持向量机（SupportVectorMachine，SVM）算法、人工神经网络（ArtificialNeuralNetwork，ANN）算法和逻辑回归（LogisticRegression，LR）算法等。5.5分类算法的简介5.5.1近邻分类算法近邻分类算法，或称为KNN算法，它是数据挖掘分类技术中最经典的算法之一。该算法由于简单有效，已经被广泛应用于众多领域，并派生出了各种改进版本，例如基于距离权重的KNN算法、基于特征权重的KNN算法和基于代表点的KNN算法（如KNNModel算法）等。5.5分类算法的简介1.KNN算法的核心思想对于一个需要预测的输入向量x，我们只需要在训练数据集中寻找k个与x最近的向量集合，然后把x的类别预测为这k个样本中类别数最多的那一类。KNN算法的流程如下。步骤1：读取数据集，并对数据进行预处理。步骤2：设定参数，如近邻个数k。步骤3：对于每个要预测的测试样本x，从训练数据集中找出最近的k个样本，构成x的近邻集合NN。步骤4：确定NN中样本的多数类别，并将其作为测试样本x的类别。步骤5：测试完毕后计算评价指标，继续设定不同的k值重新进行训练，最后取评价指标最优的k值。5.5分类算法的简介2.k值的设定k值的设定在KNN算法中十分关键。k取值过大易产生欠拟合效果，取值过小易产生过拟合效果。例如，在图5-17中，圆要被决定赋予哪个类，是三角形还是正方形？如果k=3，由于三角形所占的比例为2/3，圆将被赋予三角形那个类，如果k=5，由于正方形的比例为3/5，因此圆将被赋予正方形那么类。图5-17k值对近邻分类结果的影响5.5分类算法的简介5.k值的设定为了确定合适的k值，可以通过交叉验证法，从选取一个较小的k值开始，不断增加k的值，然后计算验证集合的方差，最终找到一个比较合适的k值。如图5-18所示，该图为k值（K-Value）与分类错误率(Errorrate)的关系图，图中的曲线表示验证错误（Validationerror）曲线，从中可以看出，选择k=10，可以让分类效果更好。图5-18用交叉验证法选择k值的示意图5.5分类算法的简介5.5.2决策树算法决策树算法通过训练数据构建决策树，对未知的数据进行分类。决策树的每个内部节点代表在一个特征上的测试，每个分枝代表该测试的一个输出，而每个树叶结点存放着一个类标号。对于一个决策树算法，最关键的是节点的分枝策略（将节点划分为子节点的策略），其中包含两个要点。（1）如何选择最优划分特征。（2）如何在最优划分特征上确定分裂点。节点的最优特征选择策略，在于选取对训练数据具有最强分类能力的特征，目的是使决策树的分枝节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。5.5分类算法的简介5.5.2决策树算法常见的ID3算法基于信息增益作为最优分裂属性选择的度量，C4.5算法基于信息增益比作为最优分裂属性选择的度量，CART算法基于基尼指数作为最优分裂属性选择的度量。例如，有如表5-14所示的西瓜数据集，用ID3算法构建的一个判断西瓜好坏的决策树如图5-19所示。表5-14西瓜数据集5.5分类算法的简介5.5.2决策树算法图5-19用ID3算法构建的一个判断西瓜好坏的决策树5.6聚类算法的简介聚类的目的是把大型数据划分成不同的簇，它所针对的是无标签类别的数据，因此聚类属于无监督学习类型。所谓“簇”，是指数据对象的集合，同一簇中的对象之间彼此相似，不同簇之间的对象相异。图5-20所示为聚类算法的示意图。图5-20聚类算法的示意图6聚类算法的简介聚类算法有非常广泛的应用场景，其应用示意图如图5-21所示。（1）客户细分：发现顾客中独特的群组，然后利用他们的特性发展目标营销项目。（2）土地利用：在土地观测数据库中发现相似的区域。（3）保险：识别平均索赔额度较高的机动车辆保险客户群组。（4）网络社区发现：运用聚类算法发现复杂网络中的社区结构。5.6聚类算法的简介（a）客户细分

（b）网络社区发现图5-21聚类算法的应用示意图5.6聚类算法的简介5.6.1主要的聚类算法类型目前主要的聚类算法可以分为四大类型。1．划分聚类算法2．层次聚类算法3．基于密度的聚类算法4．基于网格的聚类算法5.6聚类算法的简介1.划分聚类算法给定一个有n个对象的数据集，划分聚类算法将构造数据划分成k个（k≤n）。每一个划分就代表一个簇，并要求每一个簇至少包含一个对象，每一个对象属于且仅属于一个簇。代表算法：k均值聚类算法、k-medoids聚类算法和CLARANS算法等。5.6聚类算法的简介2.层次聚类算法层次聚类是将所有的样本自底向上合并成一棵“树”，或自顶向下分裂成一棵“树”的过程，这两类过程分别被称为“凝聚的层次聚类”和“分裂的层次聚类”。凝聚的层次聚类：采用自底向上的策略，它首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到某个终结条件被满足。代表算法：BRICH算法、CURE算法和ROCK等算法。5.6聚类算法的简介3.基于密度的聚类算法基于密度的聚类算法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。这类算法能克服基于距离的聚类算法只能发现“类圆形”的聚类的缺点，它可发现任意形状的聚类，且对噪声数据不敏感。代表算法：DBSCAN算法、OPTICS算法和DENCLUE等算法。5.6聚类算法的简介4.基于网格的聚类算法该算法使用多分辨率的网格数据结构，它将对象的空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在该结构上进行。代表算法：CLIQUE算法、STING等算法。5.6聚类算法的简介单击此处添加文本具体内容，简明扼要的阐述您的观点。图5-22所示为目前常见的聚类算法和典型的代表算法的归类和总结，供读者参考。图5-22目前常见的聚类算法和典型的代表算法法的归类和总结5.6聚类算法的简介5.6.2k均值聚类算法k均值聚类算法的每个簇的中心由簇中对象的平均值表示，所以称之为k均值聚类算法。该算法初始确定k个簇中心，然后把每个点归类到其最近的簇中心，然后重新计算新的簇中心，通过迭代的方法不断地更新簇中心，其基本流程示意图如图5-23所示。图5-23k均值聚类算法的基本流程示意图5.6聚类算法的简介5.6.2k均值聚类算法1．k均值聚类算法的基本流程k均值聚类算法的基本流程如下。算法名称：k均值聚类算法。输入：k表示簇数目，D表示包含n个样本的数据集。输出：簇中心集合。算法流程如下。步骤1：从数据集中随机取k个对象，将其作为k个簇的初始聚类中心。步骤2：计算剩下的对象到k个簇中心的相似度，将这些对象分别划分到相似度最高的簇。步骤3：根据聚类结果，更新k个簇的中心，计算方法是取簇中所有对象各自维度的算术平均值。5.6聚类算法的简介5.6.2k均值聚类算法步骤4：将数据集中的全部元素按照新的中心重新聚类。步骤5：满足算法的停止条件，转至步骤6；否则转至步骤3。步骤6：输出聚类结果。k均值聚类算法的停止条件可以有如下多种。（1）设定迭代次数。（2）聚类中心不再变化。（3）前后两次聚类结果的目标函数（如采用聚类质量度量指标）变化很小。5.6聚类算法的简介5.6.2k均值聚类算法2．k均值聚类算法的优缺点均值聚类算法的优点是效率相对较高，其时间复杂度为O(tkn)，其中n为样本数，k为簇数，t为迭代次数，通常情况下，k、t<<n。k均值聚类算法的缺点主要表现在如下方面。（1）只有在数据样本的均值有定义的情况下才能使用。（2）必须事先给定簇的数量k。（3）不能处理噪声和离群点。（4）不适于发现非凸形状的簇。例如，对于如图5-24所示的流形数据，的效果就很差。图5-24流形数据的聚类示意图5.6聚类算法的简介5.6.3层次聚类算法的简介层次聚类算法通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树，不同类别的原始数据点是树的最底层，树的顶层是一个聚类的根节点。层次聚类算法分为两类：自上而下和自下而上。自下而上的算法在一开始就将每个数据点视为一个单一的聚类，然后依次合并类，直到所有类合并成一个包含所有数据点的单一聚类。AGNES(AGglomerativeNESting)算法和DIANA(DIvisiveANAlysis)算法分别是传统的凝聚型层次聚类算法和分裂型层次聚类算法的代表，图5-25演示了这两种算法在一个包含5个样本的数据集｛a,b,c,d,e｝上的处理过程。6聚类算法的简介6.3层次聚类算法的简介图5-25中的凝聚型层次聚类算法AGNES算法的流程如下。（1）首先将每个数据点作为一个单个簇，如图5-27中的a、b、c、d和e分别为初始的5个簇。（2）接着根据选择的度量方法计算两两簇之间的相似度（或称为邻近度）。图5-25两种层次聚类算法的处理过程示意图5.6聚类算法的简介5.6.3层次聚类算法的简介（3）对所有簇中最为相似的两个簇进行组合，形成具有最小平均连接的簇，如a和b连接为一个簇，d和e连接为一个簇。（4）重复迭代步骤（2）和（3）直到簇中所有的对象满足最开始的簇数目为止。分裂型层次聚类算法以相反的方法处理。初始时所有的对象形成一个簇，然后根据某种规则将该簇分裂；分裂的过程反复进行，直到最终每个簇只包含一个样本。层次聚类算法计算两个簇之间相似度的常用方法有单链、全链和组平均方法。（1）单链：两个簇的相似度为两个簇中任意两个点之间的最短距离。（2）全链：两个簇的相似度为两个簇中任意两个点之间的最长距离。5.6聚类算法的简介5.6.3层次聚类算法的简介（3）组平均：两个簇的相似度为两个簇中任意两个点之间的平均距离。层次聚类算法的优点是比较简单、容易理解，不需要设置复杂的参数。在某些应用中，想把数据分成不同层次的组群，使之形成层次结构，在这种应用场景中，层次聚类算法就很适用。例如，在进化研究中，可以利用层次聚类算法按照动物的生物学特征对它们分组，使其形成物种的层次结构，从而发现进化路径。5.7分布式数据挖掘算法将传统的数据挖掘算法应用于大数据时，数据量的剧增，使得计算时间和对内存空间的占用量迅速增加，通常难以正常执行。为了解决这样的困境，分布式计算模型的引入就成为一种必然。分布式计算将计算任务分解成许多个小部分，分配给多台计算机协作处理，这样就可以节约整体的计算时间，大大提高了计算效率。Hadoop所提供的MapReduce计算模型能够将计算任务分配到集群中的多台服务器上执行，每台服务器可以从本地读取数据完成对子任务的计算，最后将中间结果进行合并计算。因此，分布式存储在集群中的大数据就不必非得读取到同一个节点进行集中处理，大大节约了数据传输量，并且可以协同集群中的多台服务器共同完成计算任务，减少了计算时间。7分布式数据挖掘算法MapReduce能够解决的问题有一个共同特点：任务可以被分解为多个子问题，且这些子问题相对独立，可以并行处理这些子问题。在实际应用中，这类问题非常多，在谷歌的相关论文中提到了MapReduce的一些典型应用，包括分布式grep、URL访问频率的统计、Web连接图的反转、倒排索引的构建、分布式排序等问题。Mahout是Apache的一个开源项目，提供一些可扩展的机器学习领域经典算法的实现，旨在帮助开发人员更加方便快捷地创建智能应用程序，并且Mahout还提供了对ApacheHadoop的支持，把诸多经典的算法转换到MapReduce的计算框架下，大大提高了算法可处理的数据量和处理性能，使这些算法可以更高效地运行在分布式环境中。5.7分布式数据挖掘算法Mahout最大的优点就是基于Hadoop的实现，把很多以前运行在单机上的算法，转化成了MapReduce模式，这样大大提升了算法可处理的数据量和处理性能。从Mahout所实现的MapReduce算法可以看出，许多经典的数据挖掘算法可以被改造成分布式算法在Hadoop平台上执行，但要求这些算法在执行过程中能够被划分成多个相互独立的子任务并行执行。5.8数据挖掘的典型应用经过了大约30多年的发展，数据挖掘技术取得了辉煌的成果，逐步形成了一套基本的理论基础，主要包括：分类、聚类、异常检测、模式挖掘和规则提取等。目前，随着大数据时代的来临，无论是数据的变化速率，还是数据的种类都在不断更新，数据挖掘变得越来越复杂但也越来越重要。在大数据时代，数据挖掘技术与其他大数据处理技术之间相辅相成、协调发展，被广泛应用于人类社会的各个方面。接下来介绍数据挖掘的一些典型应用领域和案例。5.8数据挖掘的典型应用5.8.1数据挖掘在生物信息学中的应用随着基因测序技术和生物信息学的发展，越来越多的生物信息数据产生。生物信息学是一门存储、分析和利用生物学数据（如基因组数据、转录组数据、蛋白质组数据、微生物数据、代谢组数据、阵列芯片，数据以及通过湿法实验生成的数据）信息的科学。目前，通过数据挖掘技术对生物信息数据进行挖掘并有效利用，变得越来越重要。在动植物研究领域，对不同的物种数据库中的数据进行整合分析，研究不同物种之间的进化关系。对同一物种的不同组学数据库中的数据进行整合分析，全面系统地对此物种的生物学机制进行研究。在生物医学领域，使用数据挖掘技术有助于在生物医学产业的特定领域内进行全面的研究，并且使研究人员可以更好地了解生物学机制，以便在医疗保健和生命知识领域发现新的治疗方法。5.8数据挖掘的典型应用5.8.2数据挖掘在市场营销领域中的应用在市场营销中，经常需要使用数据挖掘技术。例如，利用聚类分析能够了解消费者的消费行为，从而推断出其消费动机与消费习惯，进而让企业实现精准营销。如果要设计一款新产品，需要先进行市场调查，以收集消费者的偏好和习惯，根据市场定位找到合适的目标人群，等到产品设计出来还需要针对不同的地点进行投放，并收集消费者的反馈。所有这些过程都需要使用数据挖掘技术进行详细分析，以便营销人员能够设计有针对性的营销计划。在市场营销领域中的数据挖掘技术，可以实现客户细分、交叉营销、客户获取、客户维护等功能。5.8数据挖掘的典型应用1.客户细分客户细分是指按照一定的标准或规范，将企业所处理的异质用户群体划分为多个同质的子群体，子群体中的用户具有相同或相似的价值或个人行为特征，而不同群体中的用户具有不同的价值或个人行为特征。很显然，这可以运用数据挖掘中的聚类算法，根据用户的特性将整个用户群体划分为多个类别。5.8数据挖掘的典型应用2.交叉营销交叉营销是指企业向用户提供当前消费产品以外的产品的营销活动。数据挖掘技术（如推荐系统）可以对用户的个人数据进行分析，向其推荐可能感兴趣的其他商品或服务。例如，当用户登录淘宝或京东时，网站会向用户推荐可能感兴趣的商品，其实这就是根据用户之前购买、评价或浏览商品的记录，通过背后的智能推荐算法得出的推荐结果。5.8数据挖掘的典型应用3.客户获取客户获取是公司开拓新市场的关键途径。虽然营销人员可以使用许多传统方法来进行大规模的营销活动，但如果他们能够将获取到的大量市场信息作为其活动计划的一部分，他们的成功概率肯定会更大。数据挖掘技术可以帮助营销人员选择潜在用户，营销人员所要做的就是将数据挖掘技术提供的潜在用户与他们感兴趣的活动联系起来。5.8数据挖掘的典型应用4.客户维护由于市场需求日益激烈，获取新用户的成本越来越高，维护原有用户的价值也越来越高。