TALK ABOUT 数据挖掘-十大经典法 QianShi Li-Design

Presentation on theme: "TALK ABOUT 数据挖掘-十大经典法 QianShi Li-Design"— Presentation transcript:

1 TALK ABOUT 数据挖掘-十大经典法 QianShi Li-Design
For understanding, learning, reporting TALK ABOUT 数据挖掘-十大经典法

2 1 数据挖掘简介 2 十大经典算法粗谈 3 C4.5算法 4 K-means 算法 CONTENTS 目 录 PPT 仅供展示， 不设立场。

3 1 数据挖掘简介 2 十大经典算法粗谈 3 C4.5算法 4 K-means 算法

4 数据挖掘 2 1 3 5 4 Why What 数据挖掘的5W问题 Who Where Which 2 数据挖掘是什么？
2 数据挖掘是什么？ 1 为什么要用数据挖掘？ 面对山一样高，海一样广的数据，分析挖掘出合适的产品推荐给用户 从海量的数据中挖掘出有价值的金矿 What Why 3 谁在用数据挖掘？ 数据挖掘的5W问题 2 1 分析师、管理者、决策者、营销经理。。。 数据挖掘 3 5 Who 4 Where 5 用数据挖掘用在哪些领域？ 电信用户价值细分、精准化营销及流失预警等 预测金融市场的变化趋势，对用户科学分类以及信行信用评估等 对保费和保单的风险分析以及保险投资组合等 4 用什么挖掘方法？ Which 聚类、逻辑回归、决策树。关联规则、贝叶斯。。。

5 数据挖掘主要四大模型 分类 聚类 预测 关联 依据历史数据形成刻画用户特征的类标识,进而可以预测未来数据的归类情况。
一种无指导的学习，在事先不知道数据分类的情况下，根据数据之间的相似程度进行划分，目的是使得同类别的数据对象之间的差别尽可能的小，不同类别的数据对象之间的差别尽可能的大。 数据挖掘主要四大模型 预测 关联 基与输入的用户信息，通过模型的训练学习，找出数据中的归律和趋势，以确定未来目标数 据的预测值。 购物篮分析： 从购物篮商品集中找出商品与商品之间的关系，有助于 发现不同商品之间的联系。

6 1 数据挖掘简介 2 十大经典算法粗谈 3 C4.5算法 4 K-means 算法

7 The top ten algorithms in data mining
十大算法粗谈 K-Means SVM C4.5 Apriori The top ten algorithms in data mining CART   EM PageRank NaiveBaye KNN AdaBoost

8 C4.5，是机器学习算法中的一个分类决策树算法，它是决策树核心算法ID3的改进算法，所以基本上了解了
一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的 分类条件。 1 K-Means（k均值聚类），n个对象根据他们的属性分为k个分割(k < n)。它与处理混合正态分布的最大 期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目 标是使各个群组内部的均方误差总和最小。 2 SVM （支持向量机），支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔 超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。 3 Apriori ，是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。APRIORI算法的挖掘步骤如下：（1）依据支持度找出所有频繁项集（频度） （2）依据置信度产生关联规则（强度） 既有A又有B的概率，即P(A ∩ B)= 𝐴和𝐵同时出现次数 事务总次数 。 在A发生的事件中同时发生B的概率，即P(B|A)= 𝐴和𝐵同时出现次数 𝐴出现的次数 。 4 EM（最大期望），在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。 最大期望经常用在机器学习和计算机视觉的数据集聚领域。 5

9 PageRank（网页排名），PageRank根据网站的外部链接和内部链接的数量和质量，衡量网站的价值。
投票越多。 6 Adaboost（自适应增强），是一种迭代算法，其思想是针对同一个训练集训练不同的弱分类器，然后把 这些弱分类器集合起来，构成一个更强的最终分类器。其算法本身是通过改变数据分布来实现的，它根据每次 训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值 的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器融合起来，作为最后的决策分类器。 7 KNN （K最近邻分类），是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。 8 Naive Bayes （贝叶斯分类），其基础是概率推理，就是在各种条件的存在不确定，仅知出现概率的情况下，如何完成推理和决策任务。贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。举个例子，如果一种水果其具有红，圆，直径大概4英寸等特征，该水果可以被判定为是苹果。 贝叶斯公式 公式描述：公式中，事件Bi的概率为P(Bi)，事件Bi已发生条件下事件A的概率为P(A│Bi)，事件A发生条件下事件Bi的概率为P(Bi│A)。 9 CART（分类回归树），也属于一种决策树， 分类回归树是一棵二叉树，且每个非叶子节点都有两个孩子 ，所以对于第一棵子树其叶子节点数比非叶子节点数多1。 10

10 1 数据挖掘简介 2 十大经典算法粗谈 3 C4.5算法 4 K-means 算法

11 1 C4.5算法简介 C4.5是ID3算法的改进算法，不仅可以处理离散型描述属性，还能处理连续性描述属性。C4.5采用了信息增益比作为选择分枝属性的标准，弥补了ID3算法的不足。 决策树是一个类似于人们决策过程的树结构，从根节点开始，每个分枝代表一个新的决策事件，会生成两个或多个分枝，每个叶子代表一个最终判定所属的类别。 C4.5比ID3改进的地方： 1 2 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足 在树构造过程中进行剪枝 能够完成对连续属性的离散化处理 能够对不完整数据进行处理 信息分类树决策节点拆分熵量测 枝干属性高增益 从根到叶成规则 3 4

12 C4.5 算法模型的分类流程 01 02 03 C4.5的算法流程： C4.5算法简介 选择节点分类属性 建立新节点，划分数据集
判断节点是否到生长停止条件，如果是，终止生长，如果不是，转到步骤1

13 2 C4.5算法原理 选取节点 决策树的枝干和节点是如何生成的？ 熵（Entropy）：我们把一个事件的不确定性叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息。 公式：H(X) = E[I( 𝑥 𝑖 )] = E[ 𝑙𝑜𝑔 𝑝( 𝑥 𝑖 ) ] = -∑ 𝑝( 𝑥 𝑖 )𝑙𝑜𝑔 𝑝( 𝑥 𝑖 ) 其中𝑝( 𝑥 𝑖 )表示xi事件发生的概率，i=1,2,..n 年龄>30 否 是 接受 收入>3000 否 是 拒绝 接受 增益（Information Gain）：在信息增益中，衡量标准是看特征能够对分类系统带来多少信息，带来的信息越多，该特征越重要。对一个特征而言，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量。所谓信息量，就是熵。系统原先的熵是H(X)，在条件Y已知的情况下系统的熵（条件熵）为H(X|Y) 。 条件熵： H(X|Y)= - 𝑖 𝑗 𝑝( 𝑥 𝑖 , 𝑦 𝑗 ) 𝑙𝑜𝑔 𝑝( 𝑥 𝑖 | 𝑦 𝑗 ) 信息增益：IG=H(X) - H(X|Y) 基于信息熵的原理！

14 C4.5算法原理 FOR EX: outlook temperature humidity windy play sunny hot high FALSE no TRUE overcast yes rainy mild cool normal (1) (2) outlook temperature humidity windy play yes no sunny 2 3 hot high 4 FALSE 6 9 5 overcast mild normal 1 TRUE rainy cool 如果选取outlook作为决策树的根节点，则H(X|Y)中的Y集合{sunny、overcast、rainy},此时的条件熵为计算得H(X|Y)=0.693。即选取outlook作为决策树的根节点时，信息增益为 =0.247，再同样方法计算当选取temperature、humidity、windy作为跟节点时系统的信息增益，选取具有最高信息增益的特征属性作为拆分节点； 从最后目标属性paly可得，打球概率是9/14，不打球是5/14，因此在没有任何先验信息的情况下，系统的熵（不确定性）为： H(X)= log log 5 14 =0.94 (3) 增益比：增益/属性熵 计算outlook属性的熵，得到增益比。同样方法计算当选取temperature、humidity、windy作为跟节点时系统的信息增益和属性熵，选取增益比最大的作为最终根节点。

15 连续性变量处理 生长停止条件 缺失值处理 过拟合处理 C4.5算法原理 C4.5算法是以二值离散的方式处理连续型数据。
二值离散：对连续性属性进行排序，得到多个候选阈值，选取产生最大信息增益的阈值作为分裂阈值。 FOR EX: Temperature : Paly: no no yes yes yes yes 生长停止条件 节点内的数据以及完全属于同一类别。 节点内测数据样本数所得的信息增益不大于0时，分支的拆分停止 所有属性都已经被分裂过。 缺失值处理 1 如何计算具有缺失值的属性的信息增益率？ 2 具有缺失值的样本进行数据分裂时，分配给那个子数据集？ 3 怎样处理对新样板进行分类时，缺失值导致样本到达叶子节点？ 忽略该类样本 选择常用值或均值来填充 依据缺失比例，折算信息增益/信息增益率 对缺失值赋予独特的值参与训练 忽略该类样本 选择常用值或均值来填充 依据缺失比例，分配到子数据集中 对缺失值建立单独分支 有缺失值单独分支，走单独分支 走最常见的值的分支 确定最可能的值，走相应分支 走所以分支，根据不同输出结果的概率进行组合 不进行分类，直接赋予最有可能的值 过拟合处理 过拟合：有监督算法需要考虑泛化能力，在有限的样本条件下，决策树超过一定规模后，训练错误率减小，但测试错误率会增加。这时便需要进行对决策树进行剪枝。 剪枝：控制决策树规模的方法。一种是先剪枝，即控制决策树的生长；一种是后剪枝，即对完全生成的决策树进行剪枝。

16 3 FOR EX: 用户信用等级分类树 C4.5算法应用 保险 银行 电信 金融 其他行业，如税务、互联网都广泛应用
推荐不同用户最适合的投保产品； 预测用户是否有投保的倾向； 用户偿付能力 用户信用等级评估分类； 信用卡诈欺； 电信 金融 预测用户是否是外来工； 预测用户的离网概率； 用户的消费信用度的评价； 对用户科学进行特征群体分类； 对用户进行信用评估； 其他行业，如税务、互联网都广泛应用

17 1 数据挖掘简介 2 十大经典算法粗谈 3 C4.5算法 4 K-means 算法

18 Summary: K-means是用均值算法把数据分成K个类的算法！
1 K-means 算法简介 什么是K-means 算法？ 聚类分析是研究数据对象之间可能存在的相似性，并根据相似程度的大小，对它们进行归类分组。使得同一类中的对象趋于相似，差别较小；不同类中的对象趋于不相似，差别较大。 Q1：K是什么？ A1：K是聚类算法中类的个数 Q2：means是什么？ A2：means就是均值算法 Summary: K-means是用均值算法把数据分成K个类的算法！

19 2  K-means 算法原理过程 K-means 算法原理 （1）取K个初始中心点 （2）把每个点划分到相应的簇 （3）重新计算中心点
（4）重新聚类 全部元素按照新的中心重新聚类 （5）收敛 重复第2步直到聚类的中心不再移动，此时算法收敛 K-Means迭代的条件可以有如下几个：     · 每个聚类内部元素不在变化，这是最理想的情况了。     · 前后两次迭代，J的值相差小于某个阈值。     · 迭代超过一定的次数。 注：K=3 按照初始的中心点位置为每个数据点着上颜色，重新计算 3 个中心点。 由于初始的中心点是随机选的，这样得的结果并不是很好，重新计算k个类各自的中心，然后得到新聚类结果。 3 个中心点被随机初始化，所有的数据点都还没有进行聚类，默认全部都标记为红色。 再经过两次迭代之后，基本上就收敛了，最终结果

20 距离公式: distance K-means 算法原理
公式：d( x, y)= ( 𝑥 1 − 𝑦 1 ) 2 +( 𝑥 2 − 𝑦 2 ) 2 +…+ ( 𝑥 𝑛 − 𝑦 𝑛 ) 2 其意义就是两个元素在欧式空间中的集合距离，因为直观易懂且可解释性强，被广泛用于标识两个变量元素的相异度。 曼哈顿距离： d(x , y)=| 𝑥 1 − 𝑦 1 |+| 𝑥 2 − 𝑦 2 |+…+| 𝑥 𝑛 − 𝑦 𝑛 | d(x , y)= 𝑝 | 𝑥 1 − 𝑦 1 | 𝑝 +| 𝑥 2 − 𝑦 2 | 𝑝 +…+ | 𝑥 𝑛 − 𝑦 𝑛 | 𝑝 distance

21 3 K-means 算法应用 (0) 问题提出 (1) 数据处理 (2) 选取初始聚类中心 (3) 计算点到中心的距离
(4) 重新调整聚类中心 (5) 计算距离重新聚类

22 Thanks