1、-商业商业数据的分析、挖掘和应用数据的分析、挖掘和应用华东师范大学出版社华东师范大学出版社l 数据挖掘概论l 决策树l 关联规则l 聚类分析l产生l概念l技术及过程l应用随着世界信息技术的迅猛发展，信息量也呈几何指数增长。特别是随着云时代的来临，海量数据发展到大数据（Big Data）已日益明显，现在许多单位与组织在日常运营中生成、累积的各种数据，规模是如此庞大，以至于不能用G或T来衡量。例如，一天之中，互联网产生的全部内容可以刻满1.6亿多张DVD；发出的邮件有2940亿封之多（相当于美国两年的纸质信件数量）；发出的社区帖子达200万个（相当于时代杂志770年的文字量）；卖出的手机为37.8
2、万台，高于全球每天出生的婴儿数量37.1万（2011年数据）如何从巨量、复杂的数据中获取有用的信息，成为了信息技术研究领域的热门课题。在这样的背景下，数据挖掘技术诞生并成为了近年来的研究热点。机器学习、数据库技术和数理统计是数据挖掘的三个技术支柱。机器学习数据库技术数理统计从技术角度看：数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。从商业角度看：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。数据
3、挖掘是从海量数据中提取隐含在其中的有用信息和知识的过程。它可以帮助企业对数据进行微观、中观乃至宏观的统计、分析、综合和推理，从而利用已有数据预测未来，帮助企业赢得竞争优势。数据挖掘任务主要有很多种，常见的有监督学习（或称为分类学习）、无监督学习（或称为聚类分析）、关联规则挖掘、预测、时序挖掘和偏差分析等等。l分类学习l聚类分析l关联规则l预测l时序模式l偏差分析一般来说，数据挖掘需要经历以下过程：确定挖掘对象（理解研究的业务领域）、收集数据（理解业务领域中的数据属性）、数据预处理（对获得的数据进行清洗等各种处理）、数据挖掘（用数据挖掘算法和模型来进行数据挖掘）和信息解释（对得到的数据挖掘模型进
4、行评估，评估有效后再在实际环境中使用），在数据挖掘过程中如能配以可视化的方法，则可大幅度提高效果。图7-1.数据挖掘过程数据挖掘工具目前国际上广泛应用的数据挖掘工具有很多lSAS Enterprise Miner lSPSS公司的Clementine（被IBM公司收购后改名为Modeler）lSQL Sever中的数据挖掘模块lWaikato大学开发的Weka平台lIBM公司的Intelligent Minerl开源软件R语言数据挖掘应用场景 数据挖掘在商业分析领域的一些应用如下：l金融领域l营销领域l电子政务l电信领域l工业生产l生物和医学数据挖掘应用场景金融领域l客户信用等级评估l客户透支
5、分析l客户利润分析l客户消费行为分析 l客户消费异常行为分析l定义l分类与作用l常用算法l剪枝理解什么是决策树，决策树有什么作用之前，我们先给出一个决策树的基本结构。它的形状是一棵倒置的树，包括节点和分支。有三种类型的节点：父节点、内部节点和叶节点。图7-2.决策树示意图决策树(Decision Tree)是一种以实例为基础的归纳学习算法，是一种从无次序、无规则的训练样本集中推理出决策树表示形式的分类规则的方法，它提供了一种展示类似在什么条件下会得到什么值这类规则的方法。工作过程：图7-3.决策树工作过程决策树主要应用于分类预测。分类预测的结果有定性和定量两种。例如，预测天气，定性有下雨或不下
6、雨；定量则是下多少雨，具体的数值。在实际应用中，我们将定性的分类预测称为分类，用来确定类别属性；定量的分类预测成为预测，用来预测具体的数值。分类是一种重要的数据挖掘技术。分类的目的是根据数据集的特点构造一个分类函数或分类模型（也常常称作分类器），该模型能把未知类别的样本映射到给定类别中的某一个。因此，决策树可以分为两类：分类决策树，简称分类树，实现对分类型输出变量的分类；回归决策树，简称回归树，完成对数值型输出变量的预测。决策树的两大核心问题：l决策树的生长：在样本数据中选择哪一个属性作为根节点，然后如何分支，如何选择内部节点，直到生长出树叶，即到达叶节点，这一系列过程可称为决策树的分枝准则，
7、即具体算法；l决策树的剪枝：防止决策树生长过于茂盛，无法适应实际应用的需要。决策树常用算法：l基于信息论的方法：nID系列算法nC4.5nC5.0l最小GINI指标的方法：l CART l SLIQ lSPRINT决策树剪枝方法：l预修剪(Pre-Pruning)l后修剪(Post-Pruning)决策树常用算法ID3算法 1986年，J.R.Quinlan提出了ID3(Iterative Dichotomizer)算法。该算法是以信息论为基础，运用信息熵理论，采用自顶向下的贪心搜索算法。其核心思想是在决策树中各级节点上选择分裂属性。用信息增益作为属性选择的标准，使每个非叶子节点测试时，能获得
8、关于被测试例子最大的类别信息。使用该属性将训练样本集分成子集后，系统的信息熵值最小。决策树常用算法ID3算法 信息熵与信息增益 信息论之父申农（C.E.Shannonm）把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式，他把信息熵定义为离散随机事件的出现概率。总而言之，信息熵的基本作用就是消除人们对事物的不确定性。ID3算法根据信息论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益度量，信息增益值越大，不确定性越小。因此，算法在每个非叶子节点选择信息增益最大的属性作为分裂属性。24 n=16n=16n n1 1=4=4I(16,4)=-I(16,4)
9、=-(4/16)(4/16)*loglog2 2(4/16)+(12/16)(4/16)+(12/16)*loglog2 2(12/16)=0.8113(12/16)=0.8113E(E(年齡年齡)=(6/16)=(6/16)*I(6,1)+(10/16)I(6,1)+(10/16)*I(10,3)=I(10,3)=0.79460.7946Gain(Gain(年齡年齡)=I(16,4)-E()=I(16,4)-E(年齡年齡)=0.0167)=0.0167nGain(Gain(年齡年齡)=0.0167)=0.0167nGain(Gain(性別性別)=0.0972)=0.0972nGain(Gai
10、n(家庭所得家庭所得)=0.0177)=0.0177nMax:Max:作為第一個分類依據作為第一個分類依據图7-4a.ID3工作过程示意图a25nGain(家庭所得)=0.688I(7,3)=-(3/7)*log2(3/7)+(4/7)*log2(4/7)=0.9852nGain(年齡)=0.9852nGain(年齡)=0.2222I(9,1)=-(1/9)*log2(1/9)+(8/9)*log2(8/9)=0.5032nGain(家庭所得)=0.5032图7-4b.ID3工作过程示意图b26分類規則IF IF 性別性別=Female AND=Female AND 家庭所得家庭所得=低所得低
11、所得 THEN THEN 購買購買RVRV房車房車=否否IF IF 性別性別=Female AND=Female AND 家庭所得家庭所得=小康小康 THEN THEN 購買購買RVRV房車房車=否否IF IF 性別性別=Female AND=Female AND 家庭所得家庭所得=高所得高所得 THEN THEN 購買購買RVRV房車房車=是是IF IF 性別性別=Male AND=Male AND 年齡年齡35 35 THEN THEN 購買購買RVRV房車房車=否否IF IF 性別性別=Male AND=Male AND 年齡年齡35 35 THEN THEN 購買購買RVRV房車房車=
12、是是n資料nDecision Tree图7-4c.ID3工作过程示意图c决策树常用算法C5.0算法 C4.5算法在ID3算法的基础上进行了改进，增加了对连续属性的离散型的处理。对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。而C5.0则是在C4.5的基础上改进了执行效率和内存使用，应用于大数据集的分类算法。它采用Boosting方式来提高模型准确率。决策树是用样本的属性作为结点，用属性的取值作为分枝的树结构的。属性的度量标准有很多，C5.0采用信息增益率作为属性的度量标准。决策树常用算法C5.0算法（1）信息增益率 在1993年JRQuinla
13、n提出信息增益率。信息增益率克服了在计算信息增益时偏向于选择取值较多的属性的缺点，能够在树的生成中或完成后对树进行剪枝。信息增益率的计算公式如下式：其中，是属性A的信息熵。决策树常用算法C5.0算法（2）Boosting技术 Boosting是一种提高任意给定学习算法准确度的方法。在C5.0中是用来提高模型准确度的。Boosting中最基本的是Adaboost算法，其他算法的主要原理都差不多，只是实现手段或者说采用的数学公式不同。Adaboost算法在现实生活中的经典使用领域就是用于人脸识别。图7-5.基于Adaboost算法的人脸识别示意图决策树常用算法CART算法它是由统计学家L.Brei
14、man，J.Friedman，R.Olshen和C.Stone在出版的著作分类与回归树中提出的一种产生二叉决策树分类模型的技术。它与前面Quinlan提出的ID系列算法和C4.5不同的是，它使用的属性度量标准是Gini指标。CARTCART与与C4.5/C5.0C4.5/C5.0算法的最大相异之处是其在每一个节点上都是采用二分算法的最大相异之处是其在每一个节点上都是采用二分法，也就是一次只能够有两个子节点，法，也就是一次只能够有两个子节点，C4.5/5.0C4.5/5.0则在每一个节点上可以则在每一个节点上可以产生不同数量的分枝。产生不同数量的分枝。CARTCART模型适用于目标变量为模型适用
15、于目标变量为连续型连续型和和类别型类别型的变量，如果目标变量是类的变量，如果目标变量是类别型变量，则可以使用分类树（别型变量，则可以使用分类树（classification treesclassification trees），目标变量是），目标变量是连续型的，则可以采用回归树（连续型的，则可以采用回归树（regression treesregression trees）。）。决策树常用算法CART算法Gini指标Gini指标主要是度量数据划分或训练数据集D的不纯度为主，系数值的属性作为测试属性，Gini值越小，表明样本的“纯净度”越高。Gini指标的计算公式如下式：其中Pi是类别Ci在D中出
16、现的概率。如果集合如果集合T T分成两部分分成两部分N1 and N2N1 and N2。则此分割的。则此分割的GiniGini就是就是：提供最小提供最小GinisplitGinisplit就被选择作为分割的标准就被选择作为分割的标准(对于每个属性都要经过所有可以的分割方法对于每个属性都要经过所有可以的分割方法)。)()()(2211TginiNNTginiNNTginisplitExample(Example(G Giniini)例：顾客数据库/训练数据D 例中，预测变量为buycomp,是否购买电脑。Ageincomestudentcred都为非连续变量。对于离散性属性，选择该属性产对于离
17、散性属性，选择该属性产生最小的生最小的Gini指标的子集作为它的分指标的子集作为它的分裂子集；对于连续值属性，必须考虑裂子集；对于连续值属性，必须考虑每个可能的分裂点，选择某一分裂点每个可能的分裂点，选择某一分裂点导致最小的导致最小的Gini指标。指标。样本D中：10（yes），4（no）D的不纯度为按下列公式：459.014414101)(22DGini类别出现的频率为 jpnjpjTginij,121)(为找出D中元组的分裂准则，需要计算每个属性的Gini指标。对age的二元分组可以有：取其中2个一组，剩下的一组同样对income的二元分组可以有：取其中2个一组，剩下的一组Example(
18、Example(G Giniini)highincomeGini“income low,medium，形成形成D1，8（yes),2(no)“income high，形成形成D2，2（yes),2(no)32.00120181)(221DGini5.042421)(222DGini21,371.05.014432.01410)(144)(1410)(highincomemediumlowincomeGinixxDGiniDGiniDGini例如：例如：income属性，假设考虑子集属性，假设考虑子集low，medium,这将这将D中的元组二元划分。中的元组二元划分。D中的中的元组元组10个元组
19、满足条件个元组满足条件“income low,medium，形成，形成D1，其余的，其余的4组划组划分到分到D2，income high.同样可计算得出：407.0107.03.0)41()43(1(144)103()107(1(14102222xxGinilowincome387.0119.0268.0)61()65(1(146)83()85(1(1482222xxGinimediumincome剪枝 现实世界的数据一般不可能是完美的，可能某些属性字段上缺值；可能缺少必要的数据而造成数据不完整；可能数据不准确、含有噪声甚至是错误的。基本的决策树构造算法没有考虑噪声，因此生成的决策树完全与训练
20、例子拟合。在有噪声情况下，完全拟合将导致过分拟合，即对训练数据的完全拟合反而使对现实数据的分类预测性能下降。剪枝是一种克服噪声的基本技术，同时它也能使树得到简化而变得更容易理解。决策树剪枝方法前剪枝 前期剪枝(Forward-Pruning)是提前停止树的构造而对树进行剪枝。停止决策树的生长的方法大体上可以归纳为以下几种：l在决策树到达一定高度的情况下就停止树的生长；l到达此结点的实例具有相同的特征向量，而不必一定属于同一类，也可停止生长；l到达此结点的实例个数小于某一个阈值也可停止树的生长；l计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展；如果在最好情况下的扩展增益都小
21、于阈值，即使有些叶子结点的实例不属于同一类，也停止树的增长。决策树剪枝方法后剪枝 后剪枝(Post-Pruning)首先构造完整的决策树，允许决策树过度拟合训练数据，然后对那些置信度不够的结点的子树用叶子结点来替代，这个叶子结点所应标记的类别为子树中大多数实例所属的类别。ID3算法、C5.0算法和CART算法都是先建树再剪枝，属于后剪枝。后剪枝方法现在得到比较广泛地使用。常用的后剪枝算法有：lCCP(Cost Complexity Pruning)lREP(Reduced Error Pruning)lPEP(Pessimistic Error Pruning)lMEP(Minimum Err
22、or Pruning)l定义l分类l算法原理l常用算法关联规则主要用于发现大量数据之间有趣的关联或相关联系。关联规则挖掘的一个典型例子是购物篮分析除此以外，关联规则分析还可以应用于客户交叉营销、风险防范等方面。例如，为了高效率地营销信用卡业务，营销人员可以通过关联规则的分析，在众多银行产品客户中选择可信度较高的群体进行交叉营销，如基金客户、外汇交易客户等。图7-6.关联规则工作过程示意图 基于规则中处理变量的类型，关联规则可以分为布尔型和数值型。布尔型考虑的是项集的存在与否，而数值型则是量化的关联。基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。基于规则中涉及到的数据维数，可以分
23、为单维关联规则和多维关联规则。原理关联规则的挖掘就是在事务数据库D中找出具有用户给定的最小支持度（Minimum Support,minsup）和最小置信度(Minimum Confidence,minconf)的关联规则。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集或大项集。步骤Step1 根据最小支持度阈值找出数据集D中所有频繁项目集；Step2 根据频繁项目集和最小置信度阈值产生所有关联规则。基本模型算法算法1算法算法2数据集数据集规则规则用用 户户最小支持度最小支持度最小置信度最小置信度图图7-7.关联规则挖掘的基本模型关联规则挖掘的基本模型基本算法l搜索算法l分
24、层算法(宽度优先算法)l深度优先算法l划分算法l抽样算法Apriori算法介绍Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。Apriori算法两大缺点一是可能产生大量的候选集；二是可能需要重复扫描数据库。Apriori算法基本思路Apriori算法使用频繁项集的先验知识（称为逐层搜索的迭代方法），k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2
25、，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。Apriori算法剪枝步Ck是Lk的超集，也就是说，Ck的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的；反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。Apriori算法连接步为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与
26、自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记lij表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集li，li1li2lik-1。将Lk-1与自身连接，如果(l11=l21)&(l12=l22)&(l1k-2=l2k-2)&(l1k-1l2k-1)，那认为l1和l2是可连接。连接l1和l2 产生的结果是l11,l12,l1k-1,l2k-1。Apriori算法连接步为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是L
27、k-1中的成员。记lij表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集li，li1li2lik-1。将Lk-1与自身连接，如果(l11=l21)&(l12=l22)&(l1k-2=l2k-2)&(l1k-1l2k-1)，那认为l1和l2是可连接。连接l1和l2 产生的结果是l11,l12,l1k-1,l2k-1。Apriori算法实例上表7-1某商场的交易记录，共有9个事务。交易交易IDID商品商品IDID列表列表T100T100I1，I2，I5T200T200I2，I4T300T300I2，I3T400T400I1，I2，I4T500T500
28、I1，I3T600T600I2，I3T700T700I1，I3T800T800I1，I2，I3，I5T900T900I1，I2，I3Apriori算法实例利用Apriori算法求得所有的频繁项集过程如下图：图图7-8.关联关联规则规则Apriori算法实例算法实例FP-Tree算法介绍FP-Growth算法是韩家炜老师在2000年提出的关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（Frequent Pattern-growth,FP-Tree），但仍保留项集关联信息。FP-Tree算法与Apriori算法的区别一是FP-Tree不产生候选集；二是FP-Tree只
29、需要两次遍历数据库，大大提高了效率。FP-Tree算法基本思路不断地迭代FP-tree的构造和投影过程。FP-Tree算法具体描述 对于每个频繁项，构造它的条件投影数据库和投影FP-tree；对每个新构建的FP-tree重复这个过程，直到构造的新FP-tree为空，或者只包含一条路径；当构造的FP-tree为空时，其前缀即为频繁模式；当只包含一条路径时，通过枚举所有可能组合并与此树的前缀连接即可得到频繁模式。l定义l聚类与分类的区别l应用领域l分类l常用算法l异常检测“物以类聚，人以群分物以类聚，人以群分”俗话说：“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的聚类问题。所谓类，通
30、俗地说，就是指相似的元素的集合。聚类分析是对样品或指标进行分类的一种多元统计分析方法。聚类分析的起源是分类学，但是与分类不同的是，它要划分的类是未知的。聚类就是将数据对象分组成为多个有意义或有用簇，在同一个簇中的对象具有较高的相似度，而不同的簇中的对象差别很大。聚类就是把整个数据集分成不同的“簇”，并且要使簇与簇之间的区别尽可能的大，而簇内的数据的差异尽可能小。图图7-9.聚类的理解聚类的理解聚类是一种无指导学习（无监督学习），即从样本的特征向量出发研究通过某种算法将特征相似的样本聚集在一起，从而达到区分具有不同特征样本的目的。分类则是一种有指导学习（有监督学习），它具有先验知识（分类号），而
31、无监督聚类学习并不具有这种先验知识。聚类与分类不同的是，它要划分的类是未知的。即聚类是一种无指导学习，它不依赖预先定义的类和带类标号的训练实例。由于这个原因，聚类是观察式学习，而不是示例式学习。聚类分析在许多实际问题上都有应用：l商务领域l生物领域l地理l保险行业l电子商务l 划分方法(Partitioning Methods)n k-meansn k-medoidsl 层次的方法(Hierarchical Methods)n 凝聚和分裂的层次聚类 n BIRCH(Clustering Feature)n ROCK:分类属性层次聚类算法 n CURE:使用代表点聚类方法 n Chameleon
32、:动态建模层次聚类l 基于网络的方法(Grid-based Methods)n STING：统计信息网格聚类n WaveCluster：利用小波变换聚类l 基于模型的方法(Model-based Methods)K-Means算法介绍K-Means算法，也称K-平均算法，用来根据样本属性值之间的相似度来对样本进行分组。其基本思路是，以K 为参数，把n个对象划分为K个簇，从而使每个簇内具有较高的相似度。但不同的簇的样本则非常相异。K-Means是一种迭代算法，初始的K个簇被随机地定义之后，这些簇将被不断地更新，并在更新中被优化，当无法再进一步优化（或者达到一定的迭代次数）时算法停止。K-Mean
33、s算法具体流程 从数据集中选择聚类的K个质心，作为初始的簇中心；计算每个对象到各质心的距离，把样本指派给距离最小的簇；根据每个簇当前所拥有的所有对象更新质心；根据每个对象与各个簇中心的距离，分配给最近的簇；然后转，重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。图图7-10.聚类聚类K-Means实例示意图实例示意图两步聚类算法介绍两步聚类是一种探索性的聚类方法，是随着人工智能的发展而发展起来的智能聚类方法中的一种。它最显著的特点就是它分两步进行聚类，主要用于处理非常大的数据集，可以处理连续属性和离散属性。它只需遍历数据集一次。两步聚类算法特点 同时处理离散变量和连续变量的
34、能力。自动选择聚类数。通过预先选取样本中的部分数据构建聚类模型。可以处理超大样本量的数据。两步聚类算法步骤第一步：预聚类。遍历一次的数据，对记录进行初始的归类，用户自定义最大类别数。通过构建和修改特征树（CFTREE）来完成；第二步：聚类。对第一步完成的初步聚类进行再聚类并确定最终的聚类方案，使用层次聚类的方法将小的聚类逐渐合并成越来越大的聚类，这一过程不需要再次遍历数据。层次聚类的好处是不要求提前选择聚类数。许多层次聚类从单个记录开始聚类，逐步合并成更大的类群。基于聚类的异常检测方法：l基于统计的方法l基于距离的方法l基于偏差的方法l基于密度的方法l高维数据的异常检测Click to edit company
