数据挖掘技术概述讲义

数据挖掘技术

赵卫东博士

复旦大学软件学院

wdzhao@

1分类和预测2分类对离散数据的分类称为分类，对数值数据的分类称为预测。分类要解决的问题是为一个事件或对象归类，即确定一个特定的对象属于哪一类。分类函数或分类模型(分类器)分类模型是通过那些已知历史数据训练出来的。这里用于建立模型的数据称为训练集，通常是已经掌握的历史数据。在训练集中每个对象都赋予一个类别的标记，不同的类别具有不同的标记。分类就是通过分析训练集中的数据，为每个类别做出准确的描述或建立分析模型或挖掘出分类规则，然后用这个分类规则对其它数据对象进行分类。3分类规则实例低风险收入>￥40,000工作时间>5年高负债高风险高风险低风险否否否是是是If收入￥40,000而且工作时间>5年then低风险4分类数据ThedatausedtobuildaclassificationmodelconsistsofAsetofrecords.Eachrecordhasthesamenumberoffields.Onefieldintheserecordcontainsindicatorsofclasseswhichrecordsbelongto.Thisfieldiscalledtargetfield.Otherfieldsarecalledindependentfieldswhichdescribetheindividualobjectsrepresentedbytherecords.5决策表实例6决策树arewidelyusedindatamining.weredevelopedinmachinelearningandstatistics.areusedtobuildclassificationandpredictionmodels.arewidelyavailable.判定树分类算法output训练集决策树input新数据分类7使用决策树进行分类决策树一个树形的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分类决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪：去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到叶子节点8决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时所有的实例都在根节点属性都是分类型(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如信息增益)停止分割的条件一个节点上的实例都属于同一个类别；没有属性可以再用于对数据进行分割9属性选择择的统计计度量信息增益益—Informationgain(ID3/C4.5)所有属性性假设都都是分类类型字段段经过修改改之后可可以适用用于数值值型字段段基尼指数数—Giniindex(IBMIntelligentMiner)能够适用用于分类类和数值值字段其他10信息增益益度度量量(ID3/C4.5)任意样本本分类的的期望信信息：I(s1,s2,……,sm)=－∑∑Pilog2(pi)(i=1..m)其中，数数据集为为S，m为S的分类数数目，PiCi为某分类类标号，，Pi为任意样样本属于于Ci的概率，，si为分类Ci上的样本本数由A划分为子子集的熵熵：E(A)=∑∑j(|s1j|+………+|smj|)/|s|*I(s1j，………，smj)A为属性，，具有V个不同的的取值信息增益益：Gain(A)=I(s1,s2,………,sm)－－E(A)11训练集12使用信息息增益进进行属性性选择ClassP:buys_computer=““yes”ClassN:buys_computer=““no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly0.69413分枝14决策树age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..4015决策树在在犯罪分分析中的的应用有无固定职业家庭经济状况年龄文化程度有无特长社会关系犯罪记录违法记录家庭和睦状况犯罪记录次数是否经常赌博犯罪程度无差30-40初中否有差有4是严重有中20-30中专否无差无0是较轻有差<20高中否无中无1否较轻无差30-40初中有无中有1是严重无差>40初中有有差无2是严重有差20-30高中有有中有6是严重有差20-30中专否无中有1否较轻有差30-40大专有有差无3是严重无中<20初中有无好有5是严重无差20-30初中否有差无0否严重有好<20高中否无差有1否较轻无差30-40初中有无中有0是严重无中30-40初中否无差有1是较轻有差>40小学否有中无2否严重无差>40初中否无差无0否严重无差30-40高中否无好无4否较轻无好20-30中专有无差有2否较轻16犯罪潜在风风险决策树树1718典型的银行行卡顾客分分类树19基尼指数（（GiniIndex）集合T包含n个类别的记记录，那么么其Gini指数就是pj类别j出现的频率率如果集合T分成两部分分N1andN2。那么这个分分割的Gini就是提供最小Ginisplit就被选择作作为分割的的标准.20过拟合问题题训练数据测试数据此处剪枝决策树深度错误率剪枝避免过拟合合决策树泛化化21PruningTree目的：消除决策树树的过拟合合(OverFitting)问题实质：消除除训练集中中的异常和和噪声两种方法：：先剪枝法(Public算法)后剪枝法(Sprint算法)22误分类率

C1 C2 C3C1 0 r12

r13

C2

r21 0 r23C3

r31

r32 0实际类别分类类别Cost(orloss)matrix23决策树算法法的可伸缩缩性ID3、C4.5等算法对规规模较小，，可以一次次放入内存存的训练样样本集很有有效，但实实际上数以以百万计样样本的超大大型训练集集是常见的的，大多数数情况下无无法把训练练样本集全全部放入内内存，导致致这些算法法的有效性性降低。因因此需要增增加可伸缩缩的方法以以节省空间间。IBM的研究人员员运用一些些特殊数据据结构，例例如属性表表和类表，，在1996年提出了一一种快速的的、可伸缩缩的SLIQ算法，可以以处理离散散属性和连连续属性。。SLIQ算法首先把把训练样本本集划分成成若干子集集，使每一一个子样本本集都能放放入内存，，然后对每每个子样本本集分别构构造一棵决决策树，再再把这些决决策树综合合，得到最最终决策树树。SLIQ算法可以处处理大规模模的训练样样本集，具具有较好的的伸缩性。。与传统决决策树算法法相比，减减少了运行行时间。SLIQ算法在执行行过程中需需要随时修修改类表，，类表常驻驻内存，而而类表的大大小会随着着训练样本本集的增大大而增大，，因此SLIQ算法对内存存容量有一一定的要求求。24常用的决策策树算法ID3,C4.5,C5.0CARTCHAID25CART算法CART算法采用一一种二分递递归分割的的方法，每每次都把当当前样本集集分割为两两个子样本本集，使生生成的决策策树的非叶叶结点都有有两个分枝枝，因此CART算法生成的的决策树是是结构简单单的二叉树树。这种算算法选择分分枝属性A的判别函数数如下：式中pL和pR分别是属性性A的左右分枝枝的样本数数占总体的的比例，p(iL)和p(iR)分别表示属属性A的左右分枝枝中样本子子集属于类类别i的比例，m为分类类别别数。使Ф（A）最大的属属性A作为分枝的的属性，因因为这需要要满足下面面的条件：：左右分枝样样本的数量量差不多。。左右分枝的的样本集尽尽量不要属属于同一类类。此外，CART算法也使用用后剪枝。。在决策树树生成过程程中，考虑虑到多展开开一层就会会有更多信信息被发现现，CART算法运行到到不能再长长出分枝为为止，从而而得到一棵棵最大的决决策树。然然后CART对生成的决决策树进行行剪枝。剪剪枝算法使使用独立于于训练样本本集的测试试样本集对对子树的分分类错误进进行计算，，找出分类类错误最小小的子树作作为最终的的分类模型型。26评估分类算算法的准确确性K次交叉校验验（k-foldcrossvalidation:把数据集分分为k子集，用k-1个子集为训训练集，1个子集作为为测试集，，然后k次交叉验证证。如何提高分分类算法的的准确率？？27Bagging基本思想是是用一个不不稳定（数数据集小的的变化可能能使分类结结果有显著著的变化））、弱学习习算法（准准确率不高高），对一一个训练集集用该算法法使用多次次，得到多多个分类模模型。对于于新样本的的分类，可可以用这些些分类模型型进行投票票（得票最最多的类别别作为结果果），结果果会提高决决策树的分分类准确率率。28Boosting基本思想是是每个样本本都赋予权权重，每次次迭代对分分类错误的的样本增加加权重，以以便下次的的样本关注注这些样本本。这种方方法也能提提高不稳定定分类算法法的准确率率。Boosting和Bagging的区别是Bagging的训练集是是随机选择择，相互独独立的，分分类模型可可以并行生生成；而Boosting的训练集不不是独立的的，与前一一轮的学习习有关，分分类模型只只能顺序生生成。29神经网络30神经网络的的组成神经网络是是由许多人人工神经元元通过一定定的互联方方式组成。。这些神经经元的结构构比较简单单，但它们们复杂的连连接（拓扑扑结构）会会形成功能能很强的网网络。如下图所示示，神经元元一般有多多个输入x1,…,xn，这些输入入通过组合合函数加权权求和，然然后再利用用神经元的的激活函数数f产生输出y。神经元之间间的连接强强度用权值值w表示。神经经元的输入入和输出之之间的关系系用函数表表示：其中是神神经元的偏偏置，在网网络初始化化时赋予小小的随机数数。激活函函数（activationfunction）常用Sigmoid函数（还有有线性函数数和双曲正正切函数等等）。神经元x1x2…xny输入输出w1wnw2θ31典型的多层层前馈神经经网络x1x2x3输入层隐层输出层wijwjkOjOkOi不同层次神神经元之间间的连接强强度用相应应的权wij、wjk表示，这些些权在网络络初始化时时被赋予很很小的随机机数，例如如-0.5到0.5或-1.0到1.0之间的值。。整个信息息的处理是是单向的，，网络没有有环形结构构。输入xi直接提供给给输入层的的神经元，，对于输入入层的神经经元i，它的输出出Oi等于输入Ii：Oi=Ii。这些神经经元的加权权和同时提提供隐层的的神经元，，隐层神经经元的输出出构成输出出层神经元元的输入，，输出层的的神经元给给定样本的的分类或预预测。隐层神经元元j的输入是其其输入的线线性组合：：用激活函数数Sigmoid函数作用于于隐层的神神经元j，j的输出Oj用下式计算算：输出层神经经元的输入入和输出与与隐层神经经元的情况况类似。隐隐层和输出出层的非线线性激活关关系使神经经网络可以以近似任何何函数。32BP神经网络的的训练（1）分析业务问问题。选择训练样样本集，对对其输入值值和输出值值进行预处处理。依靠经验确确定网络的的拓扑结构构，并对神神经元的权权值和偏置置进行初始始化。利用反向传传播等算法法训练网络络，不断调调整网络权权值减少预预测误差，，获得网络络的最佳权权。用测试集检检验网络的的分类或预预测质量。。预测未知样样本的分类类。BP神经网络是是一种监督督学习方法法，使用反反向传播的的学习算法法：通过迭迭代处理一一组训练样样本，把每每个样本的的网络输出出值Tk与实际值Ok比较，然后后按一定的的方式调整整网络权和和神经元的的偏置，使使得实际值值和网络输输出值之间间的误差平平方和最小小：式中sample为样本集。。这种网络络权的调整整“后向””进行，即即由输出层层，经由隐隐层，多次次重复训练练，直到满满足误差要要求。33BP神经网络的的训练（2）为使ERR最小，可以以利用最优优化理论的的梯度下降降法更新网网络权值。。通常有两两种方法更更新权和偏偏置：一种种是每训练练一个样本本就更新权权和偏置，，另一种是是在处理训训练集中的的所有样本本之后再更更新权和偏偏置。这实实际上是以以wij和wjk为变量的多多元函数ERR的最小化问问题。利用用梯度下降降法，权的的更新方式式如下：式中是学习率，，这个参数可可避免陷入入局部最小小。学习率率太小，会会使网络学学习速度慢慢，而太大大的学习率率可能使学学习过程振振荡。通常常在网络训训练的初期期学习率设设置大一些些，随着训训练误差的的减少，学学习率可逐逐渐变小。。34神经网络的的应用(1)在财务方面面，神经网网络可用来来协助投资资公司预测测普通股的的表现、公公司的债券券等级或公公司破产的的可能性。。VISA国际公司用用神经网络络来帮助侦侦测信用卡卡欺诈，它它监控所有有VISA交易并且注注意持卡人人消费形态态的改变。。收入负债年龄付款记录信誉良好风险值信誉不良风险值35神经网络的的应用(2)股票拐点趋趋势预测:利用历史价价格数据预预测中短期期（从2到10或15天）的价格格走势。36贝叶斯分类类器37贝叶斯定理理假设X和Y在分类中可可以分别表表示样本的的属性集和和类别。P(X,Y)表示它们的的联合概率率，p(X|Y)和p(Y|X)表示条件概概率，其中中是后验概概率，而称称为Y的先验概率率。X和Y的联合概率率和条件概概率满足下下列关系：：变换后得到到38朴素贝叶斯斯分类器对于属性集集，，如如果之之间相互互独立，即即，有朴素贝贝叶斯分类类器：其中是是常数，，先验概率率可可以通过训训练集中每每类样本所所占的比例例估计。给给定，，如果要估估计测试样样本X的分类，由朴素贝叶叶斯分类器器得到y类的后验概概率：只要找出使使最大的类类别y即可。39贝叶斯分类类器在供电电电容生产产中的应用用（1）假设某段时时期内某电电脑主板制制造商所用用的供电电电容是由三三家电容生生产厂提供供的。对制制造商在这这段时期内内的业务数数据进行抽抽样，得到到下表。因为三家电电容工厂的的供电电容容在电脑主主板生产商商的仓库中中是均匀混混合的，并并无明显的的区别标志志。现在电电脑主板生生产商想通通过对数据据进行分析析，解决下下面两个问问题：（1）随机地从从仓库中取取一只供电电电容是次次品的概率率。（2）从仓库中中随机地取取一只供电电电容，若若已知取到到的是一只只次品，想想分析此次次品来自哪哪家工厂的的可能性最最大。40贝叶斯分类类器在供电电电容生产产中的应用用（2）41贝叶斯分类类器在垃圾圾邮件处理理中的应用用贝叶斯分类类器是对邮邮件的内容容进行分析析，不仅考考虑关键词词在垃圾邮邮件中出现现的概率，，也考虑关关键词在正正常邮件中中的概率。。当一封新新的邮件到到达时，这这封邮件的的内容将被被分解成字字串。依据据数据库中中这些词的的概率通过过公式进行行计算，用用贝叶斯定定理计算出出的垃圾邮邮件可能性性高于某个个阈值时就就判定这封封邮件是垃垃圾邮件。。贝叶斯过滤滤防范有一一定的智能能性，通过过一定的学学习方法可可以对数据据库词的概概率进行更更新，可以以适应垃圾圾邮件的变变化情况。。42K-最近邻分类类遗传算法粗糙集理论论模糊理论…其他分类方方法43聚类Clustering44聚类-DefinitionofclusteringClusteringisaprocessofpartitioningasetofobjectssuchascustomersintogroupsinwhichtheobjectsinthesamegrouparesimilartoeachotherandtheobjectsindifferentgroupsaredissimilar,accordingtosomesimilaritymeasure.-聚类就是把把整个数据据分成不同同的组，并并使组与组组之间的差差距尽可能能大，组内内数据的差差异尽可能能小。-Clusteringisoftencalledunsupervisedclassification-Clusteringisusedforcustomersegmentation45聚类分析簇（Cluster）:一个数据对对象的集合合聚类分析把一个给定定的数据对对象集合分分成不同的的簇；聚类是一种种无监督分分类法:没没有预先先指定的类类别；典型的应用用作为一个独独立的分析析工具，用用于了解数数据的分布布；作为其它算算法的一个个数据预处处理步骤；；CustomerSegmentation-Customersegmentationisaprocesstodividecustomersintogroupsorsegments.Customersinthesamesegmenthavesimilarneedsorbehaviorssothatsimilarmarketingstrategiesorservicepoliciescanbeappliedtothem.-SegmentationaccordingtosomevariablesE.g.,usecustomertypevariabletodividecustomersintocorporatecustomersandindividualcustomers-SegmentationusingadataminingtechniquesE.g.,aclusteringalgorithmordecisiontreealgorithm47发现客户的特特征客户分割（segmentation）是一种发现用用户特性的方方法。数据驱驱动的分割将将一个基于数数据的客户信信息的自然客客户分组：从从而给你一个个客户信息的的概况，这可可以直接转化化为增加客户户的经营策略略。新浪微博兴趣趣圈自动挖掘（/a2012/0220/1314/000001314065.shtml）48与分类的区别别与分类不同，，在开始聚集集之前用户并并不知道要把把数据分成几几组，也不知知分组的具体体标准，聚类类分析时数据据集合的特征征是未知的。。聚类根据一定定的聚类规则则，将具有某某种相同特征征的数据聚在在一起也称为为无监督学习习。分类用户户则知道数据据可分为几类类，将要处理理的数据按照照分类分入不不同的类别，，也称为有监监督学习。49聚类问题的数数学描述给定数据集合合V，根据数据对象象间的相似程程度将数据集集合分成组，，并满足：则该过程称为为聚类。Ci称为簇。50基本概念ClustercenterClustersizeClusterdensityClusterdescriptions一个好的聚类类方法要能产产生高质量的的聚类结果——簇，这些簇簇要具备以下下两个特点：：高的簇内相似似性低的簇间相似似性51聚类需求可伸缩性能够处理不同同类型的属性性能发现任意形形状的簇在决定输入参参数的时候，，尽量不需要要特定的领域域知识；能够处理噪声声和异常对输入数据对对象的顺序不不敏感能处理高维数数据能产生一个好好的、能满足足用户指定约约束的聚类结结果结果是可解释释的、可理解解的和可用的的52计算对象之间间的相异度通常使用距离离来衡量两个个对象之间的的相异度。常用的距离度度量方法有:明考斯基距离离（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维的数据对象象,q是一个正整数数。当q=1时,d称为曼哈坦距离（Manhattandistance）53SimilarityandDissimilarity当q=2时,d就成为为欧几里里德距距离:距离函函数有有如下下特性性：d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)可以根根据每每个变变量的的重要要性赋赋予一一个权权重54二元变变量二元变变量的的可能能性表表其中每每个对对象有有p个变量量，且且p=a+b+c+dObjectiObjectj55二元变变量对称的的如果一一个二二元变变量的的两个个状态态是同同等价价值的的，具具有相相同的的权重重。即即可以以任取取其中中一种种状态态编码码为1或者者0。。对于于对称称的二二元变变量，，采用用简单匹匹配系系数来评价价两个个对象象之间间的相相异度度56二元变变量非对称称的如果变变量的的两个个状态态不是是同样样重要要的，，则称称该变变量是是不对对称的的。将将比较较重要要通常常也是是出现现概率率比较较小的的状态态编码码为1，将将另一一种状状态编编码为为0。。对于于非对对称的的二元元变量量，采采用Jaccard系数来评价价两个个对象象之间间的相相异度度57二元变变量的的相异异度计计算gender是一个个对称称的二二元变变量其它的的都是是非对对称的的二元元变量量将值Y和P编码为为1,值值N编码为为0，根根据Jaccard系数计计算得得：58标称变变量（（NominalVariables）标称变变量是是二元元变量量的推推广，，它可可以具具有多多于两两个的的状态态，比比如变变量量map_color可以有有red,yellow,blue,green四种状状态。。有两两种计计算相相异度度的方方法：方法1:简简单单匹配配方法法m是匹配配的数数目,p是全部部变量量的数数目方法2:使使用用二元元变量量为每一一个状状态创创建一一个新新的二二元变变量，，可以以用非非对称称的二二元变变量来来编码码标称称变量量。59序数型型变量量一个序序数型型变量量可以以是离离散的的也可可以是是连续续的离散的的序数数型变变量类类似于于标称称变量量，除除了它它的M个状态态是以以有意意义的的序列列排序序的，，比如如职称称。连续的的序数数型变变量类类似于于区间间标度度变量量，但但是它它没有有单位位，值值的相相对顺顺序是是必要要的，，而其其实际际大小小并不不重要要。60聚类算算法K-meansalgorithmsKohonenneuralnetwork(self-organizingmap)Hierarchicalclusteringmethods其他61K-均值算算法（（1）InputAsetofnumericrecordsAnintegerk>1(numberofclusterstobefound).OutputApartitionofrecordsintokclusters.Eachrecordisidentifiedasoneofthekclusters.x11,x12x21,x22…xn1,xn2x11,x121x21,x222…xn1,xn2162K-均值算算法过过程631.Selectkdistinctrecordsasinitialmeans,eachrepresentingacluster.2.Foreachrecordindata,calculatethesquaredEuclideandistancesbetweenitandthemeans.Assigntherecordtotheclusterwhosemeanisthenearesttotherecord.3.Afterallrecordsareassignedacluster,calculatethenewmeanforeachclusterastheaverageofallrecordsinthecluster.4.Ifthenewmeansequaltothepreviousmeans,stop,otherwise,gotoStep2.K-均值算算法（（2）给定k，从n个对象象中任任意选选择k个对象象作为为初始始聚类类中心心；repeat计算每每个对对象与与聚类类中心心的距距离，，把它它们划划到不不同的的簇；；重新计计算每每个簇簇的聚聚类中中心；；until聚类中中心不不再发发生变变化641x11,x122x21,x223x31,x324x41,x425x51,x526x61,x62C1C21x11,x1212x12,x1213x13,x1224x14,x1215x15,x1226x16,x122C1C21x11,x1212x12,x1223x13,x1224x14,x1215x15,x1216x16,x121C1C2实例65K-均值算算法性性质EfficientinclusteringlargedataSolutiondependsoninitialmeansSensitivetooutliersSphericalclustersNumericdata66K-均值算算法局局限非球形形的簇簇67K-means算法在在中药药种植植区域域划分分中的的应用用无论是是种植植业还还是养养殖业业，生生产都都与当当地的的气候候条件件关系系密切切，尤尤其是是中药药种植植。中中药材材的生生长发发育、、产量量和品品质都都与气气候息息息相相关。。以中药药材当当归为为例，，对A地区的的气候候资料料进行行分析析，并并参照照当归归产地地B地区的的气候候资料料划分分A地区的的当归归适宜宜种植植区和和不适适宜种种植区区，以以供引引种参参考。。当归归喜冷冷凉阴阴湿气气候，，怕暑暑热高高温，，要求求土壤壤质地地疏松松，有有机质质含量量高，，适宜宜在高高寒阴阴湿区区种植植。据此选选择下下列因因素作作为聚聚类的的气候候变量量：x1：年平平均气气温，，x2：年降降水量量，x3：≥0℃℃积温，，x4：7月平均均气温温，x5：8月平均均气温温。下下表给给出了了B地区所所属各各气象象站多多年（（1971年至1990年）平平均气气候资资料。。68B地区气气象资资料区域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.5478.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-means算法在在安全全检测测中的的应用用应用k-means聚类算算法，，分析析入侵侵检测测模型型数据据库，，自动动地分分析原原有数数据，，从中中挖掘掘出潜潜在的的模式式，预预测用用户的的行为为。下表以以目标标端口口与当当前连连接相相同次次数和和目标标主机机不同同连接接所占占百分分比作作为特特征，，列出出了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异常72聚类类结结果果原始始数数据据聚类类结结果果73基于于IBMDB2IntelligentMiner的数数据据聚聚类类顾客客数数据据聚类类结结果果74k-modes算法法k-modes算法法把把k-means算法法扩扩展展到到可可分分类类数数据据，，定定义义了了新新的的度度量量可可分分类类数数据据相相异异度度的的距距离离公公式式，，并并给给出出相相应应的的更更新新聚聚类类中中心心的的方方式式，，能能够够迅迅速速处处理理可可分分类类型型数数据据。。k-modes算法法根根据据可可分分类类属属性性值值出出现现的的频频率率更更新新聚聚类类中中心心，，聚聚类类中中出出现现频频率率最最高高的的属属性性值值被被选选为为聚聚类类中中心心，，即即modes（类类模模式式））。。k-modes算法法改改变变了了k-means算法法的的相相异异度度测测量量方方法法，，用用一一个个简简单单的的相相异异度度测测量量对对数数据据进进行行聚聚类类。。假假设设X，Y是数数据据集集中中的的两两个个对对象象，，它它们们用用m维属属性性描描述述，，则则这这两两个个对对象象之之间间的的相相异异度度为为：：75k-modes算法法过过程程k-modes算法法不不断断更更新新modes，使使得得所所有有对对象象与与其其最最近近modes的相相异异度度总总和和最最小小：：首首先先计计算算每每一一簇簇在在某某一一属属性性值值的的对对象象所所占占百百分分数数。。然然后后，，取取每每个个簇簇中中频频率率最最大大的的一一个个属属性性值值作作为为类类模模式式Q。分分别别对对每每个个属属性性进进行行上上述述计计算算，，最最后后得得到到类类模模式式Q，即即初初始始聚聚类类中中心心。。k-modes算法法与与k-means的步步骤骤类类似似：：①预预先先定定义义好好k类，，确确定定各各个个类类的的初初始始类类模模式式Q。②根根据据类类模模式式Q把每每个个对对象象赋赋给给最最近近邻邻的的类类，，然然后后更更新新类类模模式式Q。③不不断断重重复复②②，，直直到到不不再再发发生生变变化化为为止止。。76k-prototypes算法法在实实际际应应用用中中，，数数据据可可能能是是数数值值型型的的，，同同时时也也有有可可分分类类型型的的。。k-prototypes算法法综综合合了了k-means和k-modes算法法，，采采用用新新的的距距离离度度量量方方法法，，能能够够快快速速处处理理混混合合类类型型数数据据集集的的聚聚类类问问题题。。k-prototypes算法法的的聚聚类类中中心心由由数数值值型型数数据据的的聚聚类类中中心心和和可可分分类类数数据据的的聚聚类类中中心心两两部部分分加加权权组组成成，，其其中中数数值值型型属属性性的的聚聚类类中中心心和和k-means算法类似似，通过过计算数数值型属属性的平平均值得得到。而而可分类类型属性性的中心心采用类类似k-modes算法聚类类中心的的更新方方式，通通过计算算可分类类属性值值出现的的频率确确定。77其他聚类类方法除了以上上基于划划分的聚聚类算法法外，还还有基于于层次的的聚类算算法。层层次聚类类（hierarchicalclustering）方法把把数据组组织成若若干簇，，并形成成一个相相应的树树状图进进行聚类类。基于划分分的聚类类和基于于层次的的聚类还还有其他他实现方方法，例例如基于于密度的的聚类、、基于网网格的聚聚类、基基于模型型的聚类类以及模模糊聚类类等，每每种方法法都有各各自的优优缺点，，适用范范围也有有限。选选择哪种种聚类方方法，需需要考虑虑实际的的应用需需求、簇簇的类型型与特征征、数据据的特性性、数据据质量、、数据集集的规模模（样本本个数、、样本属属性个数数）等因因素。78基于密度度的聚类类基于密度度的聚类类方法与与k-means算法使用用簇的中中心不同同，它使使用密度度的概念念。这种种聚类方方法根据据样本点点周围的的密度不不断增长长聚类，，这就克克服了基基于距离离的算法法只能发发现凸形形分布数数据聚类类的缺点点。基于密度度的聚类类方法首首先计算算一个区区域中的的点的密密度，如如果大于于某个阈阈值就把把它添加加到相近近的聚类类中去，，主要算算法包括括DBSCAN算法和OPTICS算法（DBSCAN的扩展算算法）等等。79DBSCAN算法DBSCAN算法是一一种常见见的基于于密度的的聚类方方法，大大致过程程如下：：首先把把所有的的样本标标记为核核心点、、边界点点或噪声声点。其其中一个个样本是是核心点点，满足足在该样样本的邻邻域（由由距离函函数和用用户指定定的参数数R确定）内内的样本本的个数数大于给给定的阈阈值Min。边界点点是位于于某核心心样本邻邻域的非非核心样样本，而而噪声点点指既非非核心样样本又不不是边界界样本的的样本。。然后对对每个样样本，做做如下处处理：删删除噪声声点，而而足够靠靠近的核核心点（（它们的的距离小小于R）聚集在在同一簇簇中，与与核心点点足够靠靠近（它它们的距距离小于于R）的边界界点也聚聚集在与与核心点点相同的的簇中。。DBSCAN算法可以以有效地地发现数数据库中中任意形形状的簇簇，自动动确定聚聚类的簇簇个数，，但也存存在一定定的局限限性，例例如参数数R和Min仍然需要要用户依依靠经验验设置。。80聚类可视视化TotalPopulationThisClass性别FM050001000015000200002500030000350004000045000500000102030percentTotalPopulationThisClass收入81聚类结果果–信用卡用用户聚类类82聚类结果果–高花费用用户83聚类的典典型应用用84偏离（异异常）检检测85偏离检测测在数据库库中寻找找含有你你不希望望出现的的值的记记录或记记录系列列。应用实例例：用它它来识别别欺诈行行为模式式或控制制生产过过程的质质量。86异常探测测异常探测测是数据据挖掘中中一个重重要方面面，用来来发现““小的模模式”(相对于聚聚类)，即数据据集中显显著不同同于其它它数据的的对象。。异常探测测应用电信和信信用卡欺欺骗贷款审批批药物研究究气象预报报金融领域域客户分类类网络入侵侵检测等等87什么是异异常（outlier）？Hawkins(1980)给出了异异常的本本质性的的定义：：异常是在数据集集中与众众不同的的数据，，使人怀怀疑这些些数据并并非随机机偏差，，而是产产生于完完全不同同的机制制。聚类算法法对异常常的定义义：异常常是聚类类嵌于其其中的背背景噪声声。异常常探测算算法对异异常的定定义：异异常是既既不属于于聚类也也不属于于背景噪噪声的点点。他们们的行为为与正常常的行为为有很大大不同。。88关联分析析associationanalysis89关联若两个或或多个变变量的取取值之间间存在某某种规律律性，就就称为关关联。关联规则则是寻找找在同一一个事件件中出现现的不同同项的相相关性，，比如在在一次购购买活动动中所买买不同商商品的相相关性。。关联分析析即利用用关联规规则进行行数据挖挖掘。关联规则则是形式式如下的的一种规规则，““在购买买计算机机的顾客客中，有有30％％的人也也同时购买了打打印机””。从大量的的商务事事务记录录中发现现潜在的的关联关关系，可可以帮助助人们作作出正确确的商务务决策。。90啤酒和尿布布问题反映一个事事件和其他他事件之间间依赖或关关联的知识识。如果两两项或多项项属性之间间存在关联联，那么其其中一项的的属性值就就可以依据据其他属性性值进行预预测。在美国，一一些年轻的的父亲下班班后经常要要到超市去去买婴儿尿尿布，超市市也因此发发现了一个个规律，在在购买婴儿儿尿布的年年轻父亲们们中，有30%～40%的人人同时要买买一些啤酒酒。超市随随后调整了了货架的摆摆放，把尿尿布和啤酒酒放在一起起，明显增增加了销售售额。91购物篮分析析此类关联分分析在零售售业，如超超市等得到到广泛应用用，企业可可以获得注注入产品间间的关联，，或者产品品类别和购购买这些类类别的产品品的顾客的的统计信息息之间的关关联规则。。关联分析又又称购物篮篮分析，在在销售配货货、商店商商品的陈列列设计、超超市购物路路线设计、、产品定价价和促销等等方面得到到广泛应用用。92什么是关联联挖掘?关联规则挖挖掘：在交易数据据、关系数数据或其他他信息载体体中，查找找存在于项项目集合或或对象集合合之间的频频繁模式、、关联结构构。应用：购物篮分析析、交叉销售、、产品目录录设计、聚集和分类类等。举例：规则形式：：“Body——>Head[support,confidence]”.buys(x,““diapers””)—>buys(x,“beers””)[0.5%,60%]major(x,““CS””)^takes(x,“DB”)——>grade(x,““A”)[1%,75%]93关联规则问问题的形式式化描述项项目定义1：集集合I={i1，i2，…,im}为标识符的的集合，其其中m为正整数，，ik（k=1，，2，…,m)称为项目。。项目是一个个从具体问问题中抽象象出的一个个概念。在在超市的关关联规则挖挖掘问题中中，项目表表示各种商商品，如旅旅游鞋等。。由于在超超市的关联联规则挖掘掘中并不关关心顾客购购买的商品品数量和价价格等，因因此顾客的的一次购物物可以用该该顾客所购购买的所有有商品的名名称来表示示，称为事事务，所有有事务的集集合构成关关联规则挖挖掘的数据据集，称为为事务数据据库。94事务定义2：关关联规则挖挖掘的数据据库记为D，事务数据库库D中的每个元元组称为事事务。一条条事务T是I中项目的集集合。一条条事务仅包包含其涉及及到的项目目，而不包包含项目的的具体信息息。在超级级市场的关关联规则挖挖掘问题中中事务是顾顾客一次购购物所购买买的商品，，但事务中中并不包含含这些商品品的具体信信息，如商商品的数量量、价格等等。事务数据集集的矩阵表表示

项目事务i1i2i3i4i5i610111000201010003010010040010011事务数据集集事务购买商品（项集）10i1，i2，i320i1，i330i1，i440i2，i5，i695项目集定义3：项项目集是由由I中项目构成成的集合。。若项目集集包含的项项目数为k，则称此项目目集为k-项目集。定义4：任任意的项目目集X和事务T若满足：TX，则称事务T包含项目集集X。在超市的关关联规则挖挖掘问题中中项目集可可以看成一一个或多个个商品的集集合。若某某顾客一次次购买所对对应的事务务T包含项目集集X，就说该顾客客在这次购购物中购买买了项目集集X中的所有商商品。96频繁项目集集定义5：对对任意的项项目集X，若事务数据据库D中ɛ%的事务包含含项目集X，则项目集的的支持率为为ɛ，记为support（X）=ɛ，其中包含项项目集X的事务数称称为项目集集X的频度，记记为count（X）。。若项目集X的支持率大大于或等于于用户指定定的最小支支持率（minsupport），则项目集X称为频繁项目集集（或大项目目集），否否则项目集集X为非频繁项项目集（或或小项目集集）。如果果数据库D中的事务数数记为|D|，频繁项目集集是至少被被ɛ%x|D|条事务包含含的项目集集.97支持度和置置信度定义6:关关联规则是是形如X->Y的规则，其其中X，Y为项目集且且XY=。。定义7：在在数据库D中，若s%的事务包含含XY，则关联规则则X->Y的支持度为为s%；在数据库D中，若c%的包含项目目集X的事务也包包含项目集集Y，则关联规则则X->Y的置信度为为c%:p（Y│X））＝p（XY）/p(X)。置信度反应应了关联规规则的可信信度—购买买了项目集集X中的商品的的顾客同时时也购买了了Y中商品的可能性有多大。98强关联规则则定义8：若若关联规则则X->Y的支持度和和置信度分分别大于或或等于用户户指定的最最小支持率率minsupport和最小置信信度minconfidence，则称关联规规则X->Y为强关联规则则，否则称关关联规则X->Y为弱关联规规则。关联规则挖挖掘的核心心就是要找找出事务数数据库D中的所有强强相关规则则。99关联规则挖挖掘问题的的分解给定数据库库D，关联规则的的挖掘就是是找出所有有存在于数数据库D中的强关联联规则。因因此整个关关联规则挖挖掘过程可可以分解为为以下两个个子问题：：找出出所所有有的的频频繁繁项项目目集集；；根据据找找到到的的频频繁繁项项目目集集导导出出所所有有的的强强关关联联规规则则。。100强关关联联规规则则的的产产生生第一一个个子子问问题题的的求求解解，，需需要要多多次次扫扫描描数数据据库库D，，这意意味味着着关关联联规规则则挖挖掘掘算算法法的的效效率率将将主主要要取取决决于于数数据据库库扫扫描描、、I/O操作作和和频频繁繁项项目目集集的的计计算算上上。。因因此此如如何何迅迅速速、、高高效效地地找找出出所所有有的的频频繁繁项项目目集集是是关关联联规规则则挖挖掘掘的的中中心心问问题题第二二个个子子问问题题的的求求解解比比较较容容易易，，R.Agrawal等人人已已提提出出了了有有效效的的解解决决办办法法，，具具体体过过程程如如下下：：对每每个个频频繁繁项项目目集集I，，产生生所所有有的的非非空空真真子子集集：：对对I的任任意意非非空空真真真真子子集集m，，若support（（I））/Support（（m））minconfidence，，则产产生生强强关关联联规规则则m->(l-m)。。101规则则度度量量：：支支持持度度与与可可信信度度查找找所所有有的的规规则则X&YZ具有有最最小小支支持持度度和和可可信信度度支持持度度,s,交易易中中包包含含{X、、Y、、Z}的可能能性性可信信度度,c,包含含{X、、Y}的交交易易中中也也包包含含Z的条件件概概率率设最最小小支支持持度度为为50%,最小小可可信信度度为为50%,则可可得得到到AC(50%,66.6%)CA(50%,100%)买尿尿布布的的客客户户二者者都都买买的的客客户户买啤啤酒酒的的客客户户102关联联规规则则挖挖掘掘：：路路线线图图布尔尔vs.定量量关关联联(基基于于处处理理数数据据的的类类型型)buys(x,““SQLServer””)^buys(x,““DMBook””)®buys(x,““DBMiner””)[0.2%,60%]age(x,““30..39””)^income(x,““42..48K””)®buys(x,““PC””)[1%,75%]单维维vs.多关关联联(例例子子同同上上)单层层vs.多层层分分析析哪个个品品牌牌的的啤啤酒酒与与那那个个牌牌子子的的尿尿布布有有关关系系?各种种扩扩展展相关关性性、、因因果果分分析析关联联并并不不一一定定意意味味着着相相关关或或因因果果添加加约约束束如哪哪些些““小小东东西西””的的销销售售促促发发了了““大大家家伙伙””的的买买卖卖？？103关联联规规则则挖挖掘掘例例子子对于于AC：：support=support({A、C})=50%confidence=support({A、C})/support({A})=66.6%Apriori的基基本本思思想想:频繁繁项项集集的的任任何何子子集集也也一一定定是是频频繁繁的的最小小支支持持度度50%最小小置置信信度度50%104Apriori算法法连接接:用用Lk-1自连连接接得得到到Ck修剪:一个k-项集，如果它它的一个k-1项集（它的子子集）不是是频繁的，那那它本身也不不可能是频繁繁的。伪代码:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturnkLk;105项集格非频繁项集i1i2i1i3i1i4i2i3i1i2i4i1i3i4i2i3i4i1i2i3i4频繁项集NULLi1i2i3i4i2i4i1,i2,i3106如何生成候选选集假定Lk-1中的项按顺序序排列第一步:自自连接Lk-1insertintoCkselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1<q.itemk-1第二步:修修剪forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk107生成候选集的的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3abc和abd得到abcdacd和ace得到acde修剪:ade不在L3中，删除acdeC4={abcd}108Apriori算法例子数据库D扫描DC1L1L2C2扫描DC3L3扫描D{2,3}->{5}109Apriori算法在超市的的应用某日超市的购购物记录交易时间购买商品14：25i1，i2，i415：07i1，i2，i