[精选]数据挖掘技术概述讲义.pptx

《[精选]数据挖掘技术概述讲义.pptx》由会员分享，可在线阅读，更多相关《[精选]数据挖掘技术概述讲义.pptx（182页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、险收入￥40,000工作时间5年高负债高风险高风险低风险否否否是是是If 收入￥40,000 而且工作时间5年 then低风险4分类数据分类数据nThe data used to build a classification model consists ofnA set of records.nEach record has the same number of fields.nOne field in these record contains indicators of classes which records belong to.This field is called target

3、 field.nOther fields are called independent fields which describe the individual objects represented by the records.5决策表实例决策表实例6决策树决策树nare widely used in data mining.nwere developed in machine learning and statistics.nare used to build classification and prediction models.nare widely available.判定树分类

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

5、或者一个统计的度量 如信息增益n停止分割的条件n一个节点上的实例都属于同一个类别；n没有属性可以再用于对数据进行分割9属性选择的统计度量属性选择的统计度量n信息增益Information gain ID3/C4.5n所有属性假设都是分类型字段n经过修改之后可以适用于数值型字段n基尼指数Gini index IBM Intelligent Minern能够适用于分类和数值字段n其他10信息增益度度量信息增益度度量ID3/C4.5n任意样本分类的期望信息：nIs1,s2,sm=Pi log2pi i=1.mn其中，数据集为S，m为S的分类数目，PinCi为某分类标号，Pi为任意样本属于Ci的概率，

6、si为分类Ci上的样本数n由A划分为子集的熵：nEA=j|s1j|+|smj|/|s|*Is1j，smjnA为属性，具有V个不同的取值n信息增益：GainA=Is1,s2,sm EA11训练集训练集12使用信息增益进行属性选择使用信息增益进行属性选择gClass P:buys_ puter=“yesgClass N:buys_ puter=“nogIp,n=I9,5=0.940g pute the entropy for age:HenceSimilarly0.69413分枝分枝14决策树决策树age?overcaststudent?credit rating?noyesfairexcelle

7、nt40nonoyesyesyes30.4015决策树在犯罪分析中的应用决策树在犯罪分析中的应用 有无固定有无固定职职业业家庭家庭经济经济状状况况年年龄龄文化程度文化程度有无特有无特长长社会关系社会关系犯犯罪罪记录记录违违法法记录记录家庭家庭和睦和睦状况状况犯罪犯罪记录记录次数次数是否是否经经常常 博博犯罪程度犯罪程度无差30-40初中否有差有4是严重有中20-30中专否无差无0是较轻有差40初中有有差无2是严重有差20-30高中有有中有6是严重有差20-30中专否无中有1否较轻有差30-40大专有有差无3是严重无中20初中有无好有5是严重无差20-30初中否有差无0否严重有好40小学否有中无

8、2否严重无差40初中否无差无0否严重无差30-40高中否无好无4否较轻无好20-30中专有无差有2否较轻16犯罪潜在风险决策树犯罪潜在风险决策树 1718典型的银行卡顾客分类树典型的银行卡顾客分类树 19基尼指数基尼指数Gini Indexn集合T包含n个类别的记录，那么其Gini指数就是pj 类别j出现的频率n如果集合T分成两局部 N1 and N2。那么这个分割的Gini就是n提供最小Ginisplit 就被选择作为分割的标准.20过拟合问题过拟合问题训练数据测试数据此处剪枝决策树深度错误率剪枝剪枝n 防止过拟合n决策树泛化21Pruning Treen目的：n消除决策树的过拟合Over

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

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

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

12、ART 对生成的决策树进行剪枝。剪枝算法使用独立于训练样本集的测试样本集对子树的分类错误进行计算，找出分类错误最小的子树作为最终的分类模型。26评估分类算法的准确性评估分类算法的准确性nK次交叉校验k-fold cross validation:把数据集分为k子集，用k-1个子集为训练集，1个子集作为测试集，然后k次交叉验证。n如何提高分类算法的准确率？27Baggingn基本思想是用一个不稳定数据集小的变化可能使分类结果有显著的变化、弱学习算法准确率不高，对一个训练集用该算法使用屡次，得到多个分类模型。对于新样本的分类，可以用这些分类模型进行投票得票最多的类别作为结果，结果会提高决策树的分类

13、准确率。28Boostingn基本思想是每个样本都赋予权重，每次迭代对分类错误的样本增加权重，以便下次的样本关注这些样本。这种方法也能提高不稳定分类算法的准确率。nBoosting和Bagging的区别是Bagging的训练集是随机选择，相互独立的，分类模型可以并行生成；而Boosting的训练集不是独立的，与前一轮的学习有关，分类模型只能顺序生成。29神经网络神经网络30神经网络的组成神经网络的组成n神经网络是由许多人工神经元通过一定的互联方式组成。这些神经元的结构比较简单，但它们复杂的连接拓扑结构会形成功能很强的网络。n如以下图所示，神经元一般有多个输入x1,xn，这些输入通过组合函数加权

14、求和，然后再利用神经元的激活函数f产生输出y。n神经元之间的连接强度用权值w表示。神经元的输入和输出之间的关系用函数表示：其中 是神经元的偏置，在网络初始化时赋予小的随机数。激活函数activation function常用Sigmoid函数还有线性函数和双曲正切函数等。神经元 x1x2xny输入输出w1wnw231典型的多层前馈神经网络典型的多层前馈神经网络 x1x2x3输入层隐层输出层wijwjkOjOkOi不同层次神经元之间的连接强度用相应的权wij、wjk表示，这些权在网络初始化时被赋予很小的随机数，例如-0.5到0.5或-1.0到1.0之间的值。整个信息的处理是单向的，网络没有环形结

15、构。输入xi直接提供给输入层的神经元，对于输入层的神经元i，它的输出Oi等于输入Ii：Oi=Ii。这些神经元的加权和同时提供隐层的神经元，隐层神经元的输出构成输出层神经元的输入，输出层的神经元给定样本的分类或预测。隐层神经元j的输入是其输入的线性组合：用激活函数Sigmoid函数作用于隐层的神经元j，j的输出Oj用下式计算：输出层神经元的输入和输出与隐层神经元的情况类似。隐层和输出层的非线性激活关系使神经网络可以近似任何函数。32BPBP神经网络的训练神经网络的训练1 1n分析业务问题。n选择训练样本集，对其输入值和输出值进行预处理。n依靠经验确定网络的拓扑结构，并对神经元的权值和偏置进行初始

16、化。n利用反向传播等算法训练网络，不断调整网络权值减少预测误差，获得网络的最正确权。n用测试集检验网络的分类或预测质量。n预测未知样本的分类。BP神经网络是一种监督学习方法，使用反向传播的学习算法：通过迭代处理一组训练样本，把每个样本的网络输出值Tk与实际值Ok比较，然后按一定的方式调整网络权和神经元的偏置，使得实际值和网络输出值之间的误差平方和最小：式中sample为样本集。这种网络权的调整“后向进行，即由输出层，经由隐层，屡次重复训练，直到满足误差要求。33BPBP神经网络的训练神经网络的训练2 2为使ERR最小，可以利用最优化理论的梯度下降法更新网络权值。通常有两种方法更新权和偏置：一种

17、是每训练一个样本就更新权和偏置，另一种是在处理训练集中的所有样本之后再更新权和偏置。这实际上是以wij和wjk为变量的多元函数ERR的最小化问题。利用梯度下降法，权的更新方式如下：式中是学习率，这个参数可防止陷入局部最小。学习率太小，会使网络学习速度慢，而太大的学习率可能使学习过程振荡。通常在网络训练的初期学习率设置大一些，随着训练误差的减少，学习率可逐渐变小。34神经网络的应用神经网络的应用1n在财务方面，神经网络可用来协助投资公司预测普通股的表现、公司的债券等级或公司破产的可能性。nVISA国际公司用神经网络来帮助侦测信用卡欺诈，它监控所有VISA交易并且注意持卡人消费形态的改变。收入负债

18、年龄付款记录信誉良好风险值信誉不良风险值35神经网络的应用神经网络的应用2n股票拐点趋势预测:利用历史价格数据预测中短期从2到10或15天的价格走势。36贝叶斯分类器贝叶斯分类器 37贝叶斯定理贝叶斯定理 n假设X和Y在分类中可以分别表示样本的属性集和类别。PX,Y表示它们的联合概率，pX|Y 和pY|X表示条件概率，其中是后验概率，而称为Y的先验概率。X和Y的联合概率和条件概率满足以下关系：n变换后得到38朴素贝叶斯分类器朴素贝叶斯分类器 n对于属性集 ，如果 之间相互独立，即 ，有朴素贝叶斯分类器：其中 是常数，先验概率 可以通过训练集中每类样本所占的比例估计。给定 ，如果要估计测试样本X

19、的分类，由朴素贝叶斯分类器得到y类的后验概率：只要找出使最大的类别y即可。39贝叶斯分类器在供电电容生产中的应用贝叶斯分类器在供电电容生产中的应用1 1 n假设某段时期内某电脑主板制造商所用的供电电容是由三家电容生产厂提供的。对制造商在这段时期内的业务数据进行抽样，得到下表。n因为三家电容工厂的供电电容在电脑主板生产商的仓库中是均匀混合的，并无明显的区别标志。现在电脑主板生产商想通过对数据进行分析，解决下面两个问题：1随机地从仓库中取一只供电电容是次品的概率。2从仓库中随机地取一只供电电容，假设取到的是一只次品，想分析此次品来自哪家工厂的可能性最大。40贝叶斯分类器在供电电容生产中的应用贝叶斯

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

21、法其他分类方法43聚类聚类Clustering44聚类聚类-Definition of clusteringClustering is a process of partitioning a set of objects such as customers into groups in which the objects in the same group are similar to each other and the objects in different groups are dissimilar,according to some similarity measure.-聚类就是把

22、整个数据分成不同的组，并使组与组之间的差距尽可能大，组内数据的差异尽可能小。-Clustering is often called unsupervised classification-Clustering is used for customer segmentation45Customer Segmentation-Customer segmentation is a process to divide customers into groups or segments.Customers in the same segment have similar needs or behavio

23、rs so that similar marketing strategies or service policies can be applied to them.-Segmentation according to some variablesE.g.,use customer type variable to divide customers into corporate customers and individual customers-Segmentation using a data mining techniquesE.g.,a clustering algorithm or

24、decision tree algorithm47发现客户的特征发现客户的特征n客户分割segmentation是一种发现用户特性的方法。数据驱动的分割将一个基于数据的客户信息的自然客户分组：从而给你一个客户信息的概况，这可以直接转化为增加客户的经营策略。新浪微博兴趣圈自动挖掘 :/tech.it168./a2012/0220/1314/5.shtml 48与分类的区别与分类的区别n与分类不同，在开始聚集之前用户并不知道要把数据分成几组，也不知分组的具体标准，聚类分析时数据集合的特征是未知的。n聚类根据一定的聚类规则，将具有某种相同特征的数据聚在一起也称为无监督学习。分类用户则知道数据可分为几

25、类，将要处理的数据按照分类分入不同的类别，也称为有监督学习。49聚类问题的数学描述聚类问题的数学描述n给定数据集合V，根据数据对象间的相似程度将数据集合分成组，并满足：则该过程称为聚类。Ci称为簇。50基本概念基本概念n Cluster centern Cluster sizen Cluster densityn Cluster descriptionsn一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：n高的簇内相似性n低的簇间相似性51聚类需求聚类需求 n可伸缩性n能够处理不同类型的属性n能发现任意形状的簇n在决定输入参数的时候，尽量不需要特定的领域知识；n能够处理噪声

26、和异常n对输入数据对象的顺序不敏感n能处理高维数据n能产生一个好的、能满足用户指定约束的聚类结果n结果是可解释的、可理解的和可用的52计算对象之间的相异度计算对象之间的相异度n通常使用距离来衡量两个对象之间的相异度。n常用的距离度量方法有:明考斯基距离明考斯基距离 Minkowski distance:其中 i=xi1,xi2,xip 和 j=xj1,xj2,x 是两个p维的数据对象,q是一个正整数。当q=1时,d 称为曼哈坦距离曼哈坦距离 Manhattan distance53Similarity and DissimilaritySimilarity and Dissimilarityn

27、当q=2时,d 就成为欧几里德距离欧几里德距离:n距离函数有如下特性：ndi,j 0ndi,i=0ndi,j=dj,indi,j di,k+dk,jn可以根据每个变量的重要性赋予一个权重54二元变量二元变量n二元变量的可能性表其中每个对象有p个变量，且p=a+b+c+dObject iObject j55二元变量二元变量n对称的 如果一个二元变量的两个状态是同等价值的，具有相同的权重。即可以任取其中一种状态编码为1或者0。对于对称的二元变量，采用简单匹配系数简单匹配系数来评价两个对象之间的相异度 56二元变量二元变量n非对称的如果变量的两个状态不是同样重要的，则称该变量是不对称的。将比较重要通

28、常也是出现概率比较小的状态编码为1，将另一种状态编码为0。对于非对称的二元变量，采用Jaccard系数系数来评价两个对象之间的相异度57二元变量的相异度计算二元变量的相异度计算ngender 是一个对称的二元变量n其它的都是非对称的二元变量n将值 Y和 P 编码为1,值 N 编码为 0，根据Jaccard系数计算得：58标称变量标称变量Nominal Variablesn标称变量是二元变量的推广，它可以具有多于两个的状态，比方 变量map_color可以有 red,yellow,blue,green四种状态。有两种计算相异度的方法：n方法1:简单匹配方法nm是匹配的数目,p是全部变量的数目n方

29、法2:使用二元变量n为每一个状态创立一个新的二元变量，可以用非对称的二元变量来编码标称变量。59序数型变量序数型变量n一个序数型变量可以是离散的也可以是连续的离散的序数型变量类似于标称变量，除了它的M个状态是以有意义的序列排序的，比方职称。连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。60聚类算法聚类算法n K-means algorithmsn Kohonen neural network self-organizing mapn Hierarchical clustering methodsn其他61K-均值算法均值算法1Input A s

30、et of numeric records An integer k 1 number of clusters to be found.Output A partition of records into k clusters.Each record is identified as one of the k clusters.x11,x12x21,x22xn1,xn2x11,x12 1x21,x222xn1,xn2162K-均值算法过程均值算法过程631.Select k distinct records as initial means,each representing a cluste

31、r.2.For each record in data,calculate the squared Euclidean distances between it and the means.Assign the record to the cluster whose mean is the nearest to the record.3.After all records are assigned a cluster,calculate the new mean for each cluster as the average of all records in the cluster.4.If

32、 the new means equal to the previous means,stop,otherwise,go to Step 2.K-K-均值算法均值算法2 2给定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 26 x16,x12 2

33、C1C21 x11,x12 12 x12,x12 23 x13,x12 24 x14,x12 15 x15,x12 16 x16,x12 1C1C2实例实例65K-K-均值算法性质均值算法性质n Efficient in clustering large datan Solution depends on initial meansn Sensitive to outliersn Spherical clustersn Numeric data66K-K-均值算法局限均值算法局限非球形的簇67 K-meansK-means算法在中药种植区域划分中的应用算法在中药种植区域划分中的应用 n无论是种

34、植业还是养殖业，生产都与当地的气候条件关系密切，尤其是中药种植。中药材的生长发育、产量和品质都与气候息息相关。n以中药材当归为例，对A地区的气候资料进行分析，并参照当归产地B地区的气候资料划分A地区的当归适宜种植区和不适宜种植区，以供引种参考。当归喜冷凉阴湿气候，怕暑热高温，要求土壤质地疏松，有机质含量高，适宜在高寒阴湿区种植。n据此选择以下因素作为聚类的气候变量：x1：年平均气温，x2：年降水量，x3：0 积温，x4：7月平均气温，x5：8月平均气温。下表给出了B地区所属各气象站多年1971年至1990年平均气候资料。68B B地区气象资料地区气象资料区域区域x1x2x3x4x515.757

35、9.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.170

36、k-meansk-means算法在安全检测中的应用算法在安全检测中的应用 n应用k-means聚类算法，分析入侵检测模型数据库，自动地分析原有数据，从中挖掘出潜在的模式，预测用户的行为。n下表以目标端口与当前连接相同次数和目标主机不同连接所占百分比作为特征，列出了20条网络访问数据。其中坐标轴横轴x1为目标端口与当前连接相同的连接次数，纵轴x2表示目标主机不同连接所占百分比。71网络访问记录网络访问记录序号序号目标端口与当前连接相同的连接次数目标端口与当前连接相同的连接次数x1目标主机不同连接所占百分比目标主机不同连接所占百分比x2聚类结果聚类结果150.6正常240.5正常3250攻击490

37、异常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基于基于IBM DB2 Intelligent MinerIBM DB2 Intelligent Miner的数据聚类的数据聚类 顾客数据聚类结果74k-modesk-modes算法算法 nk-modes算法把k-means算法扩展到可分类数据，定义了新的度量可分类数据相异度的距离公式，并给出相应的更新聚类中心的

38、方式，能够迅速处理可分类型数据。nk-modes算法根据可分类属性值出现的频率更新聚类中心，聚类中出现频率最高的属性值被选为聚类中心，即modes类模式。nk-modes算法改变了k-means算法的相异度测量方法，用一个简单的相异度测量对数据进行聚类。假设X，Y是数据集中的两个对象，它们用m维属性描述，则这两个对象之间的相异度为：75k-modesk-modes算法过程算法过程nk-modes算法不断更新modes，使得所有对象与其最近modes的相异度总和最小：首先计算每一簇在某一属性值的对象所占百分数。然后，取每个簇中频率最大的一个属性值作为类模式Q。分别对每个属性进行上述计算，最后得到

39、类模式Q，即初始聚类中心。k-modes算法与k-means的步骤类似：预先定义好k类，确定各个类的初始类模式Q。根据类模式Q把每个对象赋给最近邻的类，然后更新类模式Q。不断重复，直到不再发生变化为止。76k-prototypesk-prototypes算法算法 n在实际应用中，数据可能是数值型的，同时也有可分类型的。k-prototypes算法综合了k-means和k-modes算法，采用新的距离度量方法，能够快速处理混合类型数据集的聚类问题。nk-prototypes算法的聚类中心由数值型数据的聚类中心和可分类数据的聚类中心两局部加权组成，其中数值型属性的聚类中心和k-means算法类似，

40、通过计算数值型属性的平均值得到。而可分类型属性的中心采用类似k-modes算法聚类中心的更新方式，通过计算可分类属性值出现的频率确定。77其他聚类方法其他聚类方法 n除了以上基于划分的聚类算法外，还有基于层次的聚类算法。层次聚类hierarchical clustering方法把数据组织成假设干簇，并形成一个相应的树状图进行聚类。n基于划分的聚类和基于层次的聚类还有其他实现方法，例如基于密度的聚类、基于网格的聚类、基于模型的聚类以及模糊聚类等，每种方法都有各自的优缺点，适用范围也有限。选择哪种聚类方法，需要考虑实际的应用需求、簇的类型与特征、数据的特性、数据质量、数据集的规模样本个数、样本属性

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

42、指定的参数R确定内的样本的个数大于给定的阈值Min。边界点是位于某核心样本邻域的非核心样本，而噪声点指既非核心样本又不是边界样本的样本。然后对每个样本，做如下处理：删除噪声点，而足够靠近的核心点它们的距离小于R聚集在同一簇中，与核心点足够靠近它们的距离小于R的边界点也聚集在与核心点相同的簇中。DBSCAN算法可以有效地发现数据库中任意形状的簇，自动确定聚类的簇个数，但也存在一定的局限性，例如参数R和Min仍然需要用户依靠经验设置。80聚类可视化聚类可视化TotalPopulationThis Class性别性别FM0500010000150002000025000300003500040000

43、45000500000102030percentTotalPopulationThis Class收入收入81聚类结果聚类结果 信用卡用户聚类信用卡用户聚类82聚类结果聚类结果 高花费用户83聚类的典型应用聚类的典型应用 84偏离异常检测偏离异常检测85偏离检测偏离检测n在数据库中寻找含有你不希望出现的值的记录或记录系列。n应用实例：用它来识别欺诈行为模式或控制生产过程的质量。86异常探测异常探测n异常探测是数据挖掘中一个重要方面，用来发现“小的模式相对于聚类，即数据集中显著不同于其它数据的对象。n异常探测应用n电信和信用卡欺骗n贷款审批n药物研究n气象预报n金融领域n客户分类n网络入侵检测等

44、 87什么是异常什么是异常outlier？nHawkins1980给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人疑心这些数据并非随机偏差，而是产生于完全不同的机制。n聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常探测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。88关联分析关联分析association analysis89关联关联n假设两个或多个变量的取值之间存在某种规律性，就称为关联。n关联规则是寻找在同一个事件中出现的不同项的相关性，比方在一次购置活动中所买不同商品的相关性。n关联分析即利用关联规则进行数据挖掘。n关

45、联规则是形式如下的一种规则，“在购置计算机的顾客中，有30的人也同时同时购置了打印机。n从大量的商务事务记录中发现潜在的关联关系，可以帮助人们作出正确的商务决策。90啤酒和尿布问题啤酒和尿布问题n反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。n在 ，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购置婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。91购物篮分析购物篮分析n此类关联分析在零售业，如超市等得到广泛应

46、用，企业可以获得注入产品间的关联，或者产品类别和购置这些类别的产品的顾客的统计信息之间的关联规则。n关联分析又称购物篮分析，在销售配货、商店商品的陈列设计、超市购物路线设计、产品定价和促销等方面得到广泛应用。92什么是关联挖掘什么是关联挖掘?n关联规则挖掘：n在交易数据、关系数据或其他信息载体中，查找存在于工程集合或对象集合之间的频繁模式、关联结构。n应用：n购物篮分析、交叉销售、产品目录设计、聚集和分类等。n举例：n规则形式：“Body Head support,confidence.nbuysx,“diapers buysx,“beers 0.5%,60%nmajorx,“CS takes

47、x,“DB gradex,“A 1%,75%93关联规则问题的形式化描述工程关联规则问题的形式化描述工程n定义1：集合I=i1，i2，,im为标识符的集合，其中m为正整数，ikk=1，2，,m称为工程。n工程是一个从具体问题中抽象出的一个概念。在超市的关联规则挖掘问题中，工程表示各种商品，如旅游鞋等。由于在超市的关联规则挖掘中并不关心顾客购置的商品数量和价格等，因此顾客的一次购物可以用该顾客所购置的所有商品的名称来表示，称为事务，所有事务的集合构成关联规则挖掘的数据集，称为事务数据库。94事务事务n定义2：关联规则挖掘的数据库记为D，事务数据库D中的每个元组称为事务。一条事务T是I中工程的集合

48、。一条事务仅包含其涉及到的工程，而不包含工程的具体信息。在超级市场的关联规则挖掘问题中事务是顾客一次购物所购置的商品，但事务中并不包含这些商品的具体信息，如商品的数量、价格等。事务数据集的矩阵表示 工程工程事事务务i1i2i3i4i5i610111000201010003010010040010011事务数据集事事务务购购置商品置商品项项集集10i1，i2，i320i1，i330i1，i440i2，i5，i695工程集工程集n定义3：工程集是由I中工程构成的集合。假设工程集包含的工程数为k，则称此工程集为k-工程集。n定义4：任意的工程集X和事务T假设满足：TX，则称事务T包含工程集X。n在超

49、市的关联规则挖掘问题中工程集可以看成一个或多个商品的集合。假设某顾客一次购置所对应的事务T包含工程集X，就说该顾客在这次购物中购置了工程集X中的所有商品。96频繁工程集频繁工程集n定义5：对任意的工程集X，假设事务数据库D中%的事务包含工程集X，则工程集的支持率为，记为supportX=，其中包含工程集X的事务数称为工程集X的频度，记为countX。假设工程集X的支持率大于或等于用户指定的最小支持率minsupport，则工程集X称为频繁工频繁工程集程集或大工程集，否则工程集X为非频繁工程集或小工程集。如果数据库D中的事务数记为|D|，频繁工程集是至少被%x|D|条事务包含的工程集.97支持度

50、和置信度支持度和置信度n定义6:关联规则是形如X-Y的规则，其中X，Y为工程集且XY=。n定义7：在数据库D中，假设s%的事务包含XY，则关联规则X-Y的支持度为s%；在数据库D中，假设c%的包含工程集X的事务也包含工程集Y，则关联规则X-Y的置信度为c%:npYXpXY/pX。n置信度反响了关联规则的可信度购置了工程集X中的商品的顾客同时也购置了Y中商品的可能性可能性有多大。98强关联规则强关联规则n定义8：假设关联规则X-Y的支持度和置信度分别大于或等于用户指定的最小支持率minsupport和最小置信度minconfidence，则称关联规则X-Y为强关联规则强关联规则，否则称关联规则X