商务智能课件：5_Techniques_of_DMNEW

《商务智能课件：5_Techniques_of_DMNEW》由会员分享，可在线阅读，更多相关《商务智能课件：5_Techniques_of_DMNEW（185页珍藏版）》请在装配图网上搜索。

1、1数据挖掘技术数据挖掘技术2分类和预测分类和预测3分类分类n对离散数据的分类称为分类，对数值数据的分类称为预测。n分类要解决的问题是为一个事件或对象归类，即确定一个特定的对象属于哪一类。分类函数或分类模型分类函数或分类模型(分类器分类器)n分类模型是通过那些已知历史数据训练出来的。n这里用于建立模型的数据称为训练集，通常是已经掌握的历史数据。n在训练集中每个对象都赋予一个类别的标记，不同的类别具有不同的标记。n分类就是通过分析训练集（决策表）中的数据，为每个类别做出准确的描述或建立分析模型或挖掘出分类规则，然后用这个分类规则对其它数据对象进行分类。4决策树决策树判定树分类算法output训练集

2、决策树input新数据分类5使用决策树进行分类使用决策树进行分类n决策树 n一个树形的结构n内部节点上选用一个属性进行分割n每个分叉都是分割的一个部分n叶子节点表示一个分类n决策树生成算法分成两个步骤n树的生成n开始，数据都在根节点n递归的进行数据分片n树的修剪：去掉一些可能是噪音或者异常的数据n决策树使用:对未知数据进行分割n按照决策树上采用的分割属性逐层往下，直到叶子节点6决策树算法决策树算法n基本算法（贪心算法）n自上而下分而治之的方法n开始时所有的实例都在根节点n属性都是分类型(如果是连续的，将其离散化)n所有记录用所选属性递归的进行分割n属性的选择是基于一个启发式规则或者一个统计的度

3、量(如信息增益)n停止分割的条件n一个节点上的实例都属于同一个类别；n没有属性可以再用于对数据进行分割7属性选择的统计度量属性选择的统计度量n信息增益Information gain(ID3/C5.0)n所有属性假设都是分类型字段n经过修改之后可以适用于数值型字段n信息增益率（C4.5)n基尼指数Gini index(IBM Intelligent Miner)n能够适用于分类和数值字段n2检验(CHAID)n其他8信息增益信息增益(ID3)n任意样本分类的期望信息：nI(s1,s2,sm)=Pi log2(pi)(i=1.m)n其中，数据集为S，m为S的分类数目，PinCi为某分类标号，Pi

4、为任意样本属于Ci的概率，si为分类Ci上的样本数n由A划分为子集的熵：nE(A)=j(|s1j|+|smj|)/|s|*I(s1j，smj)nA为属性，具有V个不同的取值n信息增益：Gain(A)=I(s1,s2,sm)E(A)|SSi9训练集训练集ageincome studentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40medium

5、noexcellentno10使用信息增益进行属性选择使用信息增益进行属性选择gClass P:buys_computer=“yes”gClass N:buys_computer=“no”gI(p,n)=I(9,5)=0.940gCompute the entropy for age:HenceSimilarlyagepiniI(pi,ni)40320.971971.0)2,3(145)0,4(144)3,2(145)(IIIageE048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain)(),()(ageEnpIageGain0

6、.69411分枝分枝12决策树决策树age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.4013决策树在犯罪分析中的应用决策树在犯罪分析中的应用 有无固定有无固定职业职业家庭经济家庭经济状状况况年龄年龄文化程度文化程度有无特长有无特长社会关系社会关系犯犯罪罪记录记录违法违法记录记录家庭家庭和睦和睦状况状况犯罪犯罪记录记录次数次数是否是否经常经常赌博赌博犯罪程度犯罪程度无差30-40初中否有差有4是严重有中20-30中专否无差无0是较轻有差40初中有有差无2是严重有差20-30高中有有中有6是严重有差20-3

7、0中专否无中有1否较轻有差30-40大专有有差无3是严重无中20初中有无好有5是严重无差20-30初中否有差无0否严重有好40小学否有中无2否严重无差40初中否无差无0否严重无差30-40高中否无好无4否较轻无好20-30中专有无差有2否较轻14犯罪潜在风险决策树犯罪潜在风险决策树 15典型的分类树典型的分类树(规则）规则）典型的分类树典型的分类树(决策树）决策树）16信息增益率信息增益率nC4.5算法继承了ID3算法的优点，算法基本过程与ID3算法相似，但在选择决策树的分枝属性时用信息增益率选择属性，克服了选择属性时信息增益偏向选择取值种类较多的属性的不足。n属性A信息增益率 的定义为：式中

8、v为属性A的不同取值 的个数，从中可以看出，当v比较大时，就会降低增益率。1718基尼指数（基尼指数（Gini Index）n集合T包含n个类别的记录，那么其Gini指数就是pj 类别j出现的频率n如果集合T分成两部分 N1 and N2。那么这个分割的Gini就是n提供最小Ginisplit 就被选择作为分割的标准.njpjTgini121)()()()(2211TginiNNTginiNNTginisplit19过拟合问题过拟合问题训练数据测试数据此处剪枝决策树深度错误率剪枝剪枝n 避免过拟合n决策树泛化20Pruning Treen目的：n消除决策树的过拟合(Over Fitting)问

9、题n实质：消除训练集中的异常和噪声n两种方法：n先剪枝法(Public 算法)n后剪枝法(Sprint 算法)21误分类率误分类率C1C2C3C10r12r13C2r210r23C3r31r320实际类别分类类别Cost(or loss)matrix22决策树算法的可伸缩性决策树算法的可伸缩性 nID3、C4.5等算法对规模较小，可以一次放入内存的训练样本集很有效，但实际上数以百万计样本的超大型训练集是常见的，大多数情况下无法把训练样本集全部放入内存，导致这些算法的有效性降低。因此需要增加可伸缩的方法以节省空间。nIBM的研究人员运用一些特殊数据结构，例如属性表和类表，在1996年提出了一种快

10、速的、可伸缩的SLIQ算法，可以处理离散属性和连续属性。SLIQ算法首先把训练样本集划分成若干子集，使每一个子样本集都能放入内存，然后对每个子样本集分别构造一棵决策树，再把这些决策树综合，得到最终决策树。SLIQ 算法可以处理大规模的训练样本集，具有较好的伸缩性。与传统决策树算法相比，减少了运行时间。SLIQ算法在执行过程中需要随时修改类表，类表常驻内存，而类表的大小会随着训练样本集的增大而增大，因此SLIQ算法对内存容量有一定的要求。23常用的决策树算法常用的决策树算法n ID3,C4.5,C5.0算法n CART（C&R)算法n CHAID算法n QUEST算法24CART算法算法 nCA

11、RT算法（C&R算法）采用一种二分递归分割的方法，每次都把当前样本集分割为两个子样本集，使生成的决策树的非叶结点都有两个分枝，因此CART算法生成的决策树是结构简单的二叉树。这种算法选择分枝属性A的判别函数如下：式中pL和pR分别是属性A的左右分枝的样本数占总体的比例，p(iL)和p(iR)分别表示属性A的左右分枝中样本子集属于类别i的比例，m为分类类别数。使（A）最大的属性A作为分枝的属性，因为这需要满足下面的条件：n左右分枝样本的数量差不多。n左右分枝的样本集尽量不要属于同一类。nCART 算法也使用后剪枝。在决策树生成过程中，考虑到多展开一层就会有更多信息被发现，CART 算法运行到不能

12、再长出分枝为止，从而得到一棵最大的决策树。然后CART 对生成的决策树进行剪枝。剪枝算法使用独立于训练样本集的测试样本集对子树的分类错误进行计算，找出分类错误最小的子树作为最终的分类模型。1()2|()()|mLRLRiAp pp ip iQUEST算法算法nQUEST（quick unbiased efficient statistical tree）算法是1997年Loh等提出的二元决策树分类方法。nQUEST算法也需要确定分支属性和分割值等问题，但是以不同的策略处理分支属性选择和分隔值的确定，运算过程比CART算法简单有效。nQUEST算法的输入变量可以使分类型变量和数值型变量，但目标变

13、量（输出变量）是二值型（多值的变量要通过聚类转化为二值的）。nQUEST算法中确定分支属性时，需要检验属性对目标变量的独立性，以便确定分支属性。2526评估分类算法的准确性评估分类算法的准确性nk次交叉校验（k-fold cross validation:把数据集分为k子集，用k-1个子集为训练集，1个子集作为测试集，然后k次交叉验证。n如何提高分类算法的准确率？27Baggingn基本思想是用一个不稳定（数据集小的变化可能使分类结果有显著的变化）、弱学习算法（准确率不高），对一个训练集用该算法使用多次，得到多个分类模型。对于新样本的分类，可以用这些分类模型进行投票（得票最多的类别作为结果），

14、结果会提高决策树的分类准确率。n可以处理大数据集。28BoostingnC5.0使用来提高模型准确率。nBoosting的基本思想是每个样本都赋予权重，每次迭代对分类错误的样本增加权重，以便下次的样本关注这些样本。这种方法也能提高不稳定分类算法的准确率。nBoosting和Bagging的区别是Bagging的训练集是随机选择，相互独立的，分类模型可以并行生成；而Boosting的训练集不是独立的，与前一轮的学习有关，分类模型只能顺序生成。29神经网络神经网络30神经网络的组成神经网络的组成n神经网络是由许多人工神经元通过一定的互联方式组成。这些神经元的结构比较简单，但它们复杂的连接（拓扑结构

15、）会形成功能很强的网络。n如下图所示，神经元一般有多个输入x1,xn，这些输入通过组合函数加权求和，然后再利用神经元的激活函数f产生输出y。n神经元之间的连接强度用权值w表示。神经元的输入和输出之间的关系用函数表示：其中 是神经元的偏置，在网络初始化时赋予小的随机数。激活函数（activation function）常用Sigmoid函数（还有线性函数和双曲正切函数等）。()iiyfwx11xye神经元 x1x2xny输入输出w1wnw231典型的多层前馈神经网络典型的多层前馈神经网络 x1x2x3输入层隐层输出层wijwjkOjOkOi不同层次神经元之间的连接强度用相应的权wij、wjk表示

16、，这些权在网络初始化时被赋予很小的随机数，例如-0.5到0.5或-1.0到1.0之间的值。整个信息的处理是单向的，网络没有环形结构。输入xi直接提供给输入层的神经元，对于输入层的神经元i，它的输出Oi等于输入Ii：Oi=Ii。这些神经元的加权和同时提供隐层的神经元，隐层神经元的输出构成输出层神经元的输入，输出层的神经元给定样本的分类或预测。jiiijjOwIjIjeO11隐层神经元j的输入是其输入的线性组合：用激活函数Sigmoid函数作用于隐层的神经元j，j的输出Oj用下式计算：输出层神经元的输入和输出与隐层神经元的情况类似。隐层和输出层的非线性激活关系使神经网络可以近似任何函数。32BP神

17、经网络的训练（神经网络的训练（1）n分析业务问题。n选择训练样本集，对其输入值和输出值进行预处理。n依靠经验确定网络的拓扑结构，并对神经元的权值和偏置进行初始化。n利用反向传播等算法训练网络，不断调整网络权值减少预测误差，获得网络的最佳权。n用测试集检验网络的分类或预测质量。n预测未知样本的分类。BP神经网络是一种监督学习方法，使用反向传播的学习算法：通过迭代处理一组训练样本，把每个样本的网络输出值Tk与实际值Ok比较，然后按一定的方式调整网络权和神经元的偏置，使得实际值和网络输出值之间的误差平方和最小：2()kksamplekERROT 式中sample为样本集。这种网络权的调整“后向”进行

18、，即由输出层，经由隐层，多次重复训练，直到满足误差要求。33BP神经网络的训练（神经网络的训练（2）ijijijERRwwwjkjkjkERRwww01为使ERR最小，可以利用最优化理论的梯度下降法更新网络权值。通常有两种方法更新权和偏置：一种是每训练一个样本就更新权和偏置，另一种是在处理训练集中的所有样本之后再更新权和偏置。这实际上是以wij和wjk为变量的多元函数ERR的最小化问题。利用梯度下降法，权的更新方式如下：式中是学习率，这个参数可避免陷入局部最小。学习率太小，会使网络学习速度慢，而太大的学习率可能使学习过程振荡。通常在网络训练的初期学习率设置大一些，随着训练误差的减少，学习率可逐

19、渐变小。34神经网络的应用神经网络的应用(1)n在财务方面，神经网络可用来协助投资公司预测普通股的表现、公司的债券等级或公司破产的可能性。nVISA国际公司用神经网络来帮助侦测信用卡欺诈，它监控所有VISA交易并且注意持卡人消费形态的改变。收入负债年龄付款记录信誉良好风险值信誉不良风险值35神经网络的应用神经网络的应用(2)n股票拐点趋势预测:利用历史价格数据预测中短期（从2到10或15天）的价格走势。IBM SPSS Modeler神经网络神经网络3637贝叶斯分类器贝叶斯分类器 38贝叶斯定理贝叶斯定理 n假设X和Y在分类中可以分别表示样本的属性集和类别。P(X,Y)表示它们的联合概率，p

20、(X|Y)和p(Y|X)表示条件概率，其中是后验概率，而称为Y的先验概率。X和Y的联合概率和条件概率满足下列关系：n变换后得到(,)(|)()(|)()p X Yp Y X p Xp X Y p Y(|)()(|)()pXYpYpYXpX39朴素贝叶斯分类器朴素贝叶斯分类器 n对于属性集 ，如果 之间相互独立，即 ，有朴素贝叶斯分类器：其中 是常数，先验概率 可以通过训练集中每类样本所占的比例估计。给定 ，如果要估计测试样本X的分类，由朴素贝叶斯分类器得到y类的后验概率：只要找出使最大的类别y即可。12,.,nXXXX12,.,nXXX1(|)(|)niip X Yp XY1()(|)(|)(

21、)niip Yp XYp YXp X()p X()p YYy1()(|)(|)()niip Yyp XYyp YyXp X40贝叶斯分类器在供电电容生产中的应用（贝叶斯分类器在供电电容生产中的应用（1）n假设某段时期内某电脑主板制造商所用的供电电容是由三家电容生产厂提供的。对制造商在这段时期内的业务数据进行抽样，得到下表。n因为三家电容工厂的供电电容在电脑主板生产商的仓库中是均匀混合的，并无明显的区别标志。现在电脑主板生产商想通过对数据进行分析，解决下面两个问题：（1）随机地从仓库中取一只供电电容是次品的概率。（2）从仓库中随机地取一只供电电容，若已知取到的是一只次品，想分析此次品来自哪家工厂

22、的可能性最大。41贝叶斯分类器在供电电容生产中的应用（贝叶斯分类器在供电电容生产中的应用（2）42贝叶斯分类器在垃圾邮件处理中的应用贝叶斯分类器在垃圾邮件处理中的应用 n贝叶斯分类器是对邮件的内容进行分析，不仅考虑关键词在垃圾邮件中出现的概率，也考虑关键词在正常邮件中的概率。当一封新的邮件到达时，这封邮件的内容将被分解成字串。依据数据库中这些词的概率通过公式进行计算，用贝叶斯定理计算出的垃圾邮件可能性高于某个阈值时就判定这封邮件是垃圾邮件。n贝叶斯过滤防范有一定的智能性，通过一定的学习方法可以对数据库词的概率进行更新，可以适应垃圾邮件的变化情况。43nK-K-最近邻分类（最近邻分类（KNNKN

23、N）n遗传算法遗传算法n粗糙集理论粗糙集理论n模糊理论模糊理论n 其他分类方法其他分类方法IBM SPSS Modeler KNN4445聚类聚类Clustering46聚类聚类-聚类就是把整个数据分成不同的组，并使组与组之间的差距尽可大，组内数据的差异尽可能小。聚类分析聚类分析n簇（Cluster）:一个数据对象的集合n聚类分析n把一个给定的数据对象集合分成不同的簇；n聚类是一种无监督分类法:没有预先指定的类别；n典型的应用n作为一个独立的分析工具，用于了解数据的分布；n作为其它算法的一个数据预处理步骤；48发现客户的特征发现客户的特征n客户分割（segmentation）是一种发现用户特性

24、的方法。数据驱动的分割将一个基于数据的客户信息的自然客户分组：从而给你一个客户信息的概况，这可以直接转化为增加客户的经营策略。新浪微博兴趣圈自动挖掘49与分类的区别与分类的区别n与分类不同，在开始聚集之前用户并不知道要把数据分成几组，也不知分组的具体标准，聚类分析时数据集合的特征是未知的。n聚类根据一定的聚类规则，将具有某种相同特征的数据聚在一起也称为无监督学习。分类用户则知道数据可分为几类，将要处理的数据按照分类分入不同的类别，也称为有监督学习。50聚类问题的数学描述聚类问题的数学描述n给定数据集合V，根据数据对象间的相似程度将数据集合分成组，并满足：则该过程称为聚类。Ci称为簇。1|1,2

25、,.,jiijkiiCjkCVCCCV 51基本概念基本概念n 聚类中心n 类大小n 类密度n 类描述n一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：n高的簇内相似性n低的簇间相似性52聚类需求聚类需求 n可伸缩性n能够处理不同类型的属性n能发现任意形状的簇n在决定输入参数的时候，尽量不需要特定的领域知识；n能够处理噪声和异常n对输入数据对象的顺序不敏感n能处理高维数据n能产生一个好的、能满足用户指定约束的聚类结果n结果是可解释的、可理解的和可用的53计算对象之间的距离（计算对象之间的距离（1）n通常使用距离来衡量两个对象之间的相异度。n常用的距离度量方法有:明考斯基距

26、离明考斯基距离（Minkowski distance）:其中 i=(xi1,xi2,xip)和 j=(xj1,xj2,xjp)是两个p维的数据对象,q是一个正整数。当q=1时,d 称为曼哈坦距离曼哈坦距离（Manhattan distance）qqppqqjxixjxixjxixjid)|.|(|),(2211|.|),(2211ppjxixjxixjxixjid54计算对象之间的距离（计算对象之间的距离（2）n当q=2时,d 就成为欧几里德距离欧几里德距离:n距离函数有如下特性：nd(i,j)0nd(i,i)=0nd(i,j)=d(j,i)nd(i,j)d(i,k)+d(k,j)n可以根据每

27、个变量的重要性赋予一个权重)|.|(|),(2222211ppjxixjxixjxixjid55二元变量二元变量n二元变量的可能性表其中每个对象有p个变量，且p=a+b+c+dpdbcasumdcdcbabasum0101Object iObject j56二元变量二元变量n对称的 如果一个二元变量的两个状态是同等价值的，具有相同的权重。即可以任取其中一种状态编码为1或者0。对于对称的二元变量，采用简单匹配系数简单匹配系数来评价两个对象之间的相异度dcbacb jid),(57二元变量二元变量n非对称的如果变量的两个状态不是同样重要的，则称该变量是不对称的。将比较重要通常也是出现概率比较小的状

28、态编码为1，将另一种状态编码为0。对于非对称的二元变量，采用Jaccard系数系数来评价两个对象之间的相异度cbacb jid),(58二元变量的相异度计算二元变量的相异度计算ngender 是一个对称的二元变量n其它的都是非对称的二元变量n将值 Y和 P 编码为1,值 N 编码为 0，根据Jaccard系数计算得：Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryja

29、ckd59标称变量（标称变量（Nominal Variables）n标称变量是二元变量的推广，它可以具有多于两个的状态，比如 变量map_color可以有 red,yellow,blue,green四种状态。有两种计算相异度的方法：n方法1:简单匹配方法nm是匹配的数目,p是全部变量的数目n方法2:使用二元变量n为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标称变量。pmpjid),(60常用聚类算法常用聚类算法n K均值（K-means）算法n两步聚类nKohonen神经网络n层次聚类n其他61K-均值算法输入和输出均值算法输入和输出输入：输入：数值型记录集k 1 的正整数输

30、出：输出：k组样本 每个样本划归到一个类别x11,x12x21,x22xn1,xn2x11,x12 1x21,x222xn1,xn2162K-均值算法聚类过程均值算法聚类过程63K-均值算法均值算法给定k，从n个对象中任意选择k个对象作为初始聚类中心；repeat 计算每个对象与聚类中心的距离，把它们划到不同的簇；重新计算每个簇的聚类中心；until 聚类中心不再发生变化641 x11,x122 x21,x223 x31,x324 x41,x425 x51,x526 x61,x62C1C21 x11,x12 12 x12,x12 13 x13,x12 24 x14,x12 15 x15,x12

31、 26 x16,x12 2C1C21 x11,x12 12 x12,x12 23 x13,x12 24 x14,x12 15 x15,x12 16 x16,x12 1C1C2实例实例65K-均值算法局限均值算法局限非球形的簇IBM SPSS Modeler聚类分析聚类分析6667 K-均值算法在中药种植区域划分中的应用均值算法在中药种植区域划分中的应用 n无论是种植业还是养殖业，生产都与当地的气候条件关系密切，尤其是中药种植。中药材的生长发育、产量和品质都与气候息息相关。n以中药材当归为例，对A地区的气候资料进行分析，并参照当归产地B地区的气候资料划分A地区的当归适宜种植区和不适宜种植区，以供

32、引种参考。当归喜冷凉阴湿气候，怕暑热高温，要求土壤质地疏松，有机质含量高，适宜在高寒阴湿区种植。n据此选择下列因素作为聚类的气候变量：x1：年平均气温，x2：年降水量，x3：0 积温，x4：7月平均气温，x5：8月平均气温。下表给出了B地区所属各气象站多年（1971年至1990年）平均气候资料。68B B地区气象资料地区气象资料区域区域x1x2x3x4x515.7579.92592.616.115.725.3583.02568.316.315.936.1532.92833.317.517.146.3667.22699.417.016.155.9630.62723.916.616.366.547

33、8.32911.117.717.076.8500.43011.218.817.685.1536.32438.016.015.399.2283.43544.921.220.169聚类结果聚类结果 新中心新中心x1x2x3x4x5第类5.7599.42604.416.415.9第类6.5503.92918.51817.2第类9.2283.43544.921.220.170k-k-均值算法在安全检测中的应用均值算法在安全检测中的应用 n应用k-means聚类算法，分析入侵检测模型数据库，自动地分析原有数据，从中挖掘出潜在的模式，预测用户的行为。n下表以目标端口与当前连接相同次数和目标主机不同连接所占

34、百分比作为特征，列出了20条网络访问数据。其中坐标轴横轴x1为目标端口与当前连接相同的连接次数，纵轴x2表示目标主机不同连接所占百分比。71网络访问记录网络访问记录序号序号目标端口与当前连接相同的连接次数目标端口与当前连接相同的连接次数x1目标主机不同连接所占百分比目标主机不同连接所占百分比x2聚类结果聚类结果150.6正常240.5正常3250攻击490异常5130.3异常6100异常720正常820正常930.33正常1050.55正常1160.5正常12100.15异常1390异常1450.45正常1540.65正常1640正常1750.1正常1860.2正常19130.2异常20110

35、异常72聚类结果聚类结果原始数据聚类结果73k-modesk-modes算法算法 nk-modes算法把k-means算法扩展到可分类数据，定义了新的度量可分类数据相异度的距离公式，并给出相应的更新聚类中心的方式，能够迅速处理可分类型数据。nk-modes算法根据可分类属性值出现的频率更新聚类中心，聚类中出现频率最高的属性值被选为聚类中心，即modes（类模式）。nk-modes算法改变了k-means算法的相异度测量方法，用一个简单的相异度测量对数据进行聚类。假设X，Y是数据集中的两个对象，它们用m维属性描述，则这两个对象之间的相异度为：74k-modesk-modes算法过程算法过程nk-

36、modes算法不断更新modes，使得所有对象与其最近modes的相异度总和最小：首先计算每一簇在某一属性值的对象所占百分数。然后，取每个簇中频率最大的一个属性值作为类模式Q。分别对每个属性进行上述计算，最后得到类模式Q，即初始聚类中心。k-modes算法与k-means的步骤类似：预先定义好k类，确定各个类的初始类模式Q。根据类模式Q把每个对象赋给最近邻的类，然后更新类模式Q。不断重复，直到不再发生变化为止。75k-prototypesk-prototypes算法算法 n在实际应用中，数据可能是数值型的，同时也有可分类型的。k-prototypes算法综合了k-means和k-modes算法

37、，采用新的距离度量方法，能够快速处理混合类型数据集的聚类问题。nk-prototypes算法的聚类中心由数值型数据的聚类中心和可分类数据的聚类中心两部分加权组成，其中数值型属性的聚类中心和k-means算法类似，通过计算数值型属性的平均值得到。而可分类型属性的中心采用类似k-modes算法聚类中心的更新方式，通过计算可分类属性值出现的频率确定。二步（阶）聚类算法二步（阶）聚类算法n二步聚类算法（two step cluster)是一种层次聚类算法（hierarchical algorithms)，主要处理比较大的数据，可自动确定类的数目，能够处理连续变量和分类变量的混合数据。n二步聚类算法分2

38、步进行：第一步是准聚类（pre-cluster step)，第二步进行具体的聚类分析。n准聚类是分层聚类中针对大样本聚类产生的BIRCH(balance iterative reducing and clustering using hierarchies)算法，分成一些子类。具体的聚类分析利用分层聚类方法再次聚类，使用对数似然函数作为测量公式，利用准聚类的结果对每个样本进行再次聚类，对在一定的范围每个聚类成员计算判别值，并用于估计类的最初数目。76IBM SPSS ModelerIBM SPSS Modeler两步聚类两步聚类77层次型聚类（层次型聚类（1 1）n层次聚类（hierarchi

39、cal clustering）方法把数据组织成若干簇，并形成一个相应的树状图进行聚类。n聚合层次聚类采用自底向上的策略，首先把每个对象单独作为一类，然后根据一定的规则，例如把簇间距离最小的相似簇合并成为越来越大的簇，直到所有样本凝聚成一个大的簇，针对给定应用选择最好结果的聚类层次。n与聚合型方法相反，分裂聚类采用自顶向下的方法，先把所有的对象都看成一个簇，然后不断分解直至满足一定的条件。层次型聚类（层次型聚类（2 2）n层次聚类的一个重要问题是如何评价两个簇的相似性。大多数层次聚类方法都属于聚合型方法，它们对噪声、异常数据比较敏感。层次聚类常用的方法有BIRCH和CURE等。80其他聚类方法其

40、他聚类方法 n基于划分的聚类和基于层次的聚类还有其他实现方法，例如基于密度的聚类、基于网格的聚类、基于模型的聚类以及模糊聚类等，每种方法都有各自的优缺点，适用范围也有限。选择哪种聚类方法，需要考虑实际的应用需求、簇的类型与特征、数据的特性、数据质量、数据集的规模（样本个数、样本属性个数）等因素。81基于密度的聚类基于密度的聚类 n基于密度的聚类方法与k-means算法使用簇的中心不同，它使用密度的概念。这种聚类方法根据样本点周围的密度不断增长聚类，这就克服了基于距离的算法只能发现凸形分布数据聚类的缺点。n基于密度的聚类方法首先计算一个区域中的点的密度，如果大于某个阈值就把它添加到相近的聚类中去

41、，主要算法包括DBSCAN算法和OPTICS算法（DBSCAN的扩展算法）等。82基于密度的聚类基于密度的聚类 n基于密度的聚类方法与k-means算法使用簇的中心不同，它使用密度的概念。这种聚类方法根据样本点周围的密度不断增长聚类，这就克服了基于距离的算法只能发现凸形分布数据聚类的缺点。n基于密度的聚类方法首先计算一个区域中的点的密度，如果大于某个阈值就把它添加到相近的聚类中去，主要算法包括DBSCAN算法和OPTICS算法（DBSCAN的扩展算法）等。83DBSCAN DBSCAN 算法算法 nDBSCAN 算法是一种常见的基于密度的聚类方法，大致过程如下：首先把所有的样本标记为核心点、边

42、界点或噪声点。其中一个样本是核心点，满足在该样本的邻域（由距离函数和用户指定的参数R确定）内的样本的个数大于给定的阈值Min。边界点是位于某核心样本邻域的非核心样本，而噪声点指既非核心样本又不是边界样本的样本。然后对每个样本，做如下处理：删除噪声点，而足够靠近的核心点（它们的距离小于R）聚集在同一簇中，与核心点足够靠近（它们的距离小于R）的边界点也聚集在与核心点相同的簇中。DBSCAN算法可以有效地发现数据库中任意形状的簇，自动确定聚类的簇个数，但也存在一定的局限性，例如参数R和Min仍然需要用户依靠经验设置。84聚类的典型应用聚类的典型应用 n模式识别n空间数据分析 n在GIS中，通过聚类发

43、现特征空间来建立主题索引；n在空间数据挖掘中，检测并解释空间中的簇；n图象处理n经济学(尤其是市场研究方面)nWWW 文档分类；分析WEB日志数据来发现相似的访问模式nCluster analysis of datanCustomer segmentationnFraud detectionnMissing value prediction聚类是社会网络中的应用聚类是社会网络中的应用86偏离（异常）检测偏离（异常）检测87偏离检测偏离检测n在数据库中寻找含有你不希望出现的值的记录或记录系列。n应用实例：用它来识别欺诈行为模式或控制生产过程的质量。88异常探测异常探测n异常探测是数据挖掘中一个重

44、要方面，用来发现“小的模式”(相对于聚类)，即数据集中显著不同于其它数据的对象。n异常探测应用n电信和信用卡欺骗n贷款审批n药物研究n气象预报n金融领域n客户分类n网络入侵检测等 89什么是异常（什么是异常（outlieroutlier）？）？nHawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。n聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常探测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。IBM SPSS ModelerIBM SPSS Model

45、er异常分析异常分析9091关联分析关联分析association analysis92关联关联n若两个或多个变量的取值之间存在某种规律性，就称为关联。n关联规则是寻找在同一个事件中出现的不同项的相关性，比如在一次购买活动中所买不同商品的相关性。n关联分析即利用关联规则进行数据挖掘。n关联规则是形式如下的一种规则，“在购买计算机的顾客中，有30的人也同时同时购买了打印机”。n从大量的商务事务记录中发现潜在的关联关系，可以帮助人们作出正确的商务决策。93啤酒和尿布的故事啤酒和尿布的故事n反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他

46、属性值进行预测。n在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。94购物篮分析购物篮分析n此类关联分析在零售业，如超市等得到广泛应用，企业可以获得注入产品间的关联，或者产品类别和购买这些类别的产品的顾客的统计信息之间的关联规则。n关联分析又称购物篮分析，在销售配货、商店商品的陈列设计、超市购物路线设计、产品定价和促销等方面得到广泛应用。95什么是关联挖掘什么是关联挖掘?n关联规则挖掘：n在交易数据、关系数据或其他信息载体中，查找存

47、在于项目集合或对象集合之间的频繁模式、关联结构。n应用：n购物篮分析、交叉销售、产品目录设计、聚集和分类等。n举例：n规则形式：“Body Head support,confidence”.nbuys(x,“diapers”)buys(x,“beers”)0.5%,60%nmajor(x,“CS”)takes(x,“DB”)grade(x,“A”)1%,75%96关联规则问题的形式化描述项目关联规则问题的形式化描述项目n定义1：集合I=i1，i2，,im为标识符的集合，其中m为正整数，ik（k=1，2，,m)称为项目。n项目是一个从具体问题中抽象出的一个概念。在超市的关联规则挖掘问题中，项目表

48、示各种商品，如旅游鞋等。由于在超市的关联规则挖掘中并不关心顾客购买的商品数量和价格等，因此顾客的一次购物可以用该顾客所购买的所有商品的名称来表示，称为事务，所有事务的集合构成关联规则挖掘的数据集，称为事务数据库。97事务事务n定义2：关联规则挖掘的数据库记为D，事务数据库D中的每个元组称为事务。一条事务T是I中项目的集合。一条事务仅包含其涉及到的项目，而不包含项目的具体信息。在超级市场的关联规则挖掘问题中事务是顾客一次购物所购买的商品，但事务中并不包含这些商品的具体信息，如商品的数量、价格等。事务数据集的矩阵表示 项目项目事务事务i1i2i3i4i5i610111000201010003010

49、010040010011事务数据集事务事务购买商品（项集）购买商品（项集）10i1，i2，i320i1，i330i1，i440i2，i5，i698项目集项目集n定义3：项目集是由I中项目构成的集合。若项目集包含的项目数为k，则称此项目集为k-项目集。n定义4：任意的项目集X和事务T若满足：TX，则称事务T包含项目集X。n在超市的关联规则挖掘问题中项目集可以看成一个或多个商品的集合。若某顾客一次购买所对应的事务T包含项目集X，就说该顾客在这次购物中购买了项目集X中的所有商品。99频繁项目集频繁项目集n定义5：对任意的项目集X，若事务数据库D中%的事务包含项目集X，则项目集的支持率为，记为supp

50、ort（X）=，其中包含项目集X的事务数称为项目集X的频度，记为count（X）。若项目集X的支持率大于或等于用户指定的最小支持率（minsupport），则项目集X称为频繁项目集频繁项目集（或大项目集），否则项目集X为非频繁项目集（或小项目集）。如果数据库D中的事务数记为|D|，频繁项目集是至少被%x|D|条事务包含的项目集.100支持度和置信度支持度和置信度n定义6:关联规则是形如X-Y的规则，其中X，Y为项目集且XY=。n定义7：在数据库D中，若s%的事务包含XY，则关联规则X-Y的支持度为s%；在数据库D中，若c%的包含项目集X的事务也包含项目集Y，则关联规则X-Y的置信度为c%:np

51、（YX）p（XY）/p(X)。n置信度反应了关联规则的可信度购买了项目集X中的商品的顾客同时也购买了Y中商品的可能性可能性有多大。101强关联规则强关联规则n定义8：若关联规则X-Y的支持度和置信度分别大于或等于用户指定的最小支持率minsupport和最小置信度minconfidence，则称关联规则X-Y为强关联规则强关联规则，否则称关联规则X-Y为弱关联规则。n关联规则挖掘的核心就是要找出事务数据库D中的所有强相关规则。102关联规则挖掘问题的分解关联规则挖掘问题的分解n给定数据库D，关联规则的挖掘就是找出所有存在于数据库D中的强关联规则。因此整个关联规则挖掘过程可以分解为以下两个子问题

52、：n找出所有的频繁项目集；n根据找到的频繁项目集导出所有的强关联规则。103强关联规则的产生强关联规则的产生n第一个子问题的求解，需要多次扫描数据库D，这意味着关联规则挖掘算法的效率将主要取决于数据库扫描、I/O操作和频繁项目集的计算上。因此如何迅速、高效地找出所有的频繁项目集是关联规则挖掘的中心问题n第二个子问题的求解比较容易，R.Agrawal等人已提出了有效的解决办法，具体过程如下：n对每个频繁项目集I，产生所有的非空真子集：对I的任意非空真真子集m，若support（I）/Support（m）minconfidence，则产生强关联规则m-(l-m)。104规则度量：支持度与可信度规则

53、度量：支持度与可信度n查找所有的规则 X&Y Z 具有最小支持度和可信度n支持度,s,交易中包含X、Y、Z的可能性n可信度,c,包含X、Y的交易中也包含Z的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度为50%,最小可信度为 50%,则可得到A C (50%,66.6%)C A (50%,100%)买尿布的客买尿布的客户户二者都买二者都买的客户的客户买啤酒的客户买啤酒的客户105关联规则挖掘：路线图关联规则挖掘：路线图n布尔 vs.定量 关联(基于处理数据的类型)nbuys(x,“SQLServer”)buys(x,“DMBook”)bu

54、ys(x,“DBMiner”)0.2%,60%nage(x,“30.39”)income(x,“42.48K”)buys(x,“PC”)1%,75%n单维 vs.多关联(例子同上)n单层 vs.多层分析n哪个品牌的啤酒与那个牌子的尿布有关系?n各种扩展n相关性、因果分析n关联并不一定意味着相关或因果n添加约束n如哪些“小东西”的销售促发了“大家伙”的买卖？106关联规则挖掘例子关联规则挖掘例子对于 A C：support=support(A、C)=50%confidence=support(A、C)/support(A)=66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的交易

55、ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度A75%B50%C50%A,C50%最小支持度 50%最小置信度 50%107AprioriApriori算法算法n连接:用 Lk-1自连接得到Ckn修剪:一个一个k-项集，如果它的一个项集，如果它的一个k-1项集（它的子集项集（它的子集）不是频繁）不是频繁的，那它本身也不可能是频繁的。的，那它本身也不可能是频繁的。n伪代码:Ck:Candidate itemset of size kLk:frequent itemset of size kL1=frequent items;for(k=1;Lk!=;k

56、+)do begin Ck+1=candidates generated from Lk;for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 =candidates in Ck+1 with min_support endreturn k Lk;108 项集格项集格 109如何生成候选集如何生成候选集n假定 Lk-1 中的项按顺序排列n第一步:自连接 Lk-1 insert into Ckselect p.item1,p.

57、item2,p.itemk-1,q.itemk-1from Lk-1 p,Lk-1 qwhere p.item1=q.item1,p.itemk-2=q.itemk-2,p.itemk-1 5112Apriori Apriori 算法在超市的应用算法在超市的应用 某日超市的购物记录交易时间交易时间购买商品购买商品14：25i1，i2，i415：07i1，i2，i316：33i2，i317：05i1，i318：40i1，i2，i3，i518：55i2，i319：26i1，i2，i519：52i2，i420：03i1，i2，i320：16i1，i3 i1，i5 i2 i2，i5 i1 ；i5 i1

58、，i2 113IBM SPSS ModelerIBM SPSS Modeler构建关联模型构建关联模型 114Apriori Apriori 性能瓶颈性能瓶颈nApriori算法的核心:n用频繁的(k 1)-项集生成候选的频繁 k-项集n用数据库扫描和模式匹配计算候选集的支持度nApriori 的瓶颈:候选集生成n巨大的候选集:n多次扫描数据库：n如果最长的模式是n的话，则需要 n+1次数据库扫描115布尔型和数值型关联规则布尔型和数值型关联规则n根据处理的项目类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的项目都是离散的，它显示了这些变量之间的关系。例如性别=“女”职业=“秘书”，

59、是布尔型关联规则。而数值型关联规则可以和多维关联或多层关联规则结合起来。对数值型属性进行处理，参考连续属性离散化方法或统计方法把其进行分割，确定划分的区间个数和区间宽度。数值型关联规则中也可以包含可分类型变量。例如性别=“女”平均收入2300，这里的收入是数值类型，所以是一个数值型关联规则。又如，age(x，30，39)income(x，42，48)buys(x，“PC”)1%，75%。这里的项目用谓词表示，其中x是变量，泛指顾客，表示逻辑与。116多层关联规则多层关联规则n项通常具有层次。n底层的项通常支持度也低。n某些特定层的规则可能更有意义。n交易数据库可以按照维或层编码。n可以进行共享

60、的多维挖掘。食品面包牛奶脱脂奶光明统一酸奶白黄TID ItemsT1111,121,211,221T2111,211,222,323T3112,122,221,411T4111,121T5111,122,211,221,413117挖掘多层关联规则挖掘多层关联规则n自上而下，深度优先的方法：n先找高层的“强”规则：牛奶 面包 20%,60%.n再找他们底层的“弱”规则：酸奶 黄面包 6%,50%.n多层关联规则的变种n层次交叉的关联规则：酸奶 复旦面包房 黄面包n不同种分层方法间的关联规则：酸奶 复旦面包房面包118多层关联：冗余过滤多层关联：冗余过滤n由于“祖先”关系的原因，有些规则可能是多

61、余的。n例子n牛奶 白面包 support=8%,confidence=70%n酸奶 白面包 support=2%,confidence=72%n第一个规则是第二个规则的祖先n参考规则的祖先，如果它的支持度与“预期”的支持度近似的话，则这条规则是冗余的。119多维关联规则概念多维关联规则概念n单维规则：buys(X,“milk”)buys(X,“bread”)n多维规则：2个以上维/谓词n维间关联规则(谓词不重复)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)n混合维关联规则(谓词重复)age(X,”19-25”)buys(X,“popc

62、orn”)buys(X,“coke”)n类别属性n有限个值,值之间无顺序关系n数量属性n数字的，值之间隐含了顺序关系120分离关联规则分离关联规则n分离关联规则与一般的关联规则相似，只是在关联规则中出现项目的反转项，在购物篮分析中可发现不在一起购买的商品。例如购买牛奶的顾客一般不购买汽水。这里读者思考一下，如何发现分离关联规则？121FPFP增长算法增长算法 n与Apriori算法不同，频繁模式增长（frequent pattern growth）算法，简称FP增长算法使用一种称为FP树的数据结构，并且采用分而治之的策略，无需产生候选频繁项集就能得到全部的频繁项集。122nFP树是事务数据库的

63、压缩表示，每个事务都映射到FP树中的一条路径。不同的事务可能包含若干相同的项目，因此这些路径会有所重叠，使得事务数据能得到一定程度的压缩。FP增长算法挖掘频繁项集的过程如下：n首先搜索事务数据库D，找到1频繁项集及其支持数。n构造FP-树。创建FP树的根结点，用符号null标记。第二次搜索事务数据库D，按L中的次序排列每个事务的项集，并对每个事务创建由根结点null出发的路径。构造构造FPFP树树123利用利用FPFP树产生频繁项集树产生频繁项集 nFP增长算法以自底向上的方式搜索FP树，由L的倒序开始，对每个1频繁项目构造条件FP树，然后递归地对该条件FP树进行挖掘。挖掘条件FP树项项前缀路

64、径前缀路径条件条件FP树树产生的频繁项集产生的频繁项集i5（i2,i1,i3:1），（i2,i1:1）i2i5:2,i1i5:2,i2i1i5:2i4（i2,i1:1）（i2:1）i2i4:2i3（i2,i1:3），（i2:2）（i1:2）,i2,i1,i3:3，i2i3:5，i1i3:5i1i2:5i2 i1:5124其他关联规则挖掘算法其他关联规则挖掘算法 n约束性关联规则挖掘算法 n增量式关联规则挖掘算法 n多层关联规则挖掘 关联与分类的组合关联与分类的组合125126序列模式发现序列模式发现Sequential Patterns DiscoverySequential Patterns

65、 Discovery127序列模式分析序列模式分析n序列模式的发现是由RAgrawal于1995年首先提出的。序列模式寻找的是事件之间在顺序上的相关性。n例如，“凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒”，就是一个序列关联规则序列关联规则。n序列模式挖掘在交易数据库分析、Web访问日志分析以及通信网络分析等领域具有广泛的应用前景。128序列模式序列模式nIdentifies time-dependent sequences among transaction sets where each transaction includes a set of items.nExamp

66、lenGiven a set of ordered customer transactions“.nEach transaction contains a set of items“.nFind sequences:if a customer buys item Athen the customer will buy item X afterwards129实例（实例（1 1）Transaction TimeCustomerItems BoughtJune 20,1994 10:13 amJ.BrownJuice,CokeJune 20,1994 11:02 amF.ZappaBrandyJune 20,1994 11:47 amJ.BrownBeerJune 20,1994 2:32 pmB.MooreBeerJune 21,1994 9:22 amJ.BrownWine,Water,CiderJune 21,1994 3:19 pmJ.MitchellBeer,Gin,CiderJune 21,1994 5:27 pmB.AdamsBeer(Diapers?)June 21,199