数据挖掘(DM)ppt课件

1,Datamining&BusinessIntelligence,数据挖掘与商务智能,2,.,课程内容,汇总统计、数据可视化&OLAP,分类、关联分析、聚类分析、异常检测,各类数据挖掘工具简介,参考书籍：IntroductiontoDataMining美P.N.Tanet.al.,参考书籍：MaterialsfromtheInternet商务智能与数据挖掘MicrosoftSQLserver应用，谢邦昌,课件下载邮箱：gdutwwPsw:gdutww,3,.,2数据挖掘具体方法,2.3关联分析,怎样进行关联规则挖掘,4,.,基本概念：关联规则挖掘,关联规则：关联规则是形如X-Y的蕴涵表达式，其中X和Y是不相交的项集，即。关联规则挖掘：从一个数据集中发现关联规则，该规则显示了给定数据集中经常一起出现的属性值条件元组。,Market-Basket事务集,ExampleofAssociationRules,DiaperBeer,Milk,BreadEggs,Coke,Beer,BreadMilk,注意：两个事务组相互关联，只是两者经常同时发生，而并不一定是两者一定具有因果关系。,2.3.1,5,.,实例,通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？这种信息可以引导销售，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步引导客户在商店里同时购买这些商品。,“啤酒与尿布”的关联规则,2.3.1,6,.,一些基本定义,项集一个或多个项的集合如:Milk,Bread,Diaperk-项集包含有k个子项的项集支持度计数()一个项集在事务集中出现的频率E.g.(Milk,Bread,Diaper)=2支持度包含某个项集的事务数量比例E.g.s(Milk,Bread,Diaper)=2/5频繁项集支持度高于或等于阈值minsup的项集,2.3.1,为什么要使用支持度？支持度是一种重要的度量，因为支持度很低的规则只是偶然出现，从商业角度来看，低支持度的规则多半也不是令人感兴趣的，因为对顾客很少同时购买的商品进行促销可能并无益处。,7,.,一些基本定义,Example:,关联规则形如XY的蕴涵式，其中X和Y是项集。例如:Milk,DiaperBeer关联规则强度的衡量指标支持度（缩写：s)同时包含X和Y的事务比例置信度(缩写：c)Y在包含X的事务中出现的频繁程度。,2.3.1,8,.,怎样进行关联规则挖掘,给定事务集T,关联规则挖掘的任务就是寻找满足以下条件的关联规则。支持度minsupthreshold置信度minconfthreshold一种“原始野蛮”的方法:列出所有的规则分别计算每条规则的置信度和支持度剔除未达到minsup阈值和minconf阈值的规则Computationallyprohibitive!,2.3.2,整体上是经常出现的，相互的关联度是大的,9,.,怎样进行关联规则挖掘,ExampleofRules:Milk,DiaperBeer(s=0.4,c=0.67)Milk,BeerDiaper(s=0.4,c=1.0)Diaper,BeerMilk(s=0.4,c=0.67)BeerMilk,Diaper(s=0.4,c=0.67)DiaperMilk,Beer(s=0.4,c=0.5)MilkDiaper,Beer(s=0.4,c=0.5),Observations:所有上述规则都是产生于以下项集:Milk,Diaper,Beer产生于相同项集的规则具有相同的支持度但是不同的置信度。因此需要区分开置信度和支持度的要求。,2.3.2,10,.,怎样进行关联规则挖掘,采用“两步走”的方法:先产生频繁项集即找出supportminsup的所有项集生成规则从频繁项集中产生具有高置信度的规则，每条规则本质上其实就是频繁项集的一个划分。产生频繁项集的过程运算量仍然是非常大的！,2.3.2,11,.,给定d个项，则可以产生2d个候选项集。,怎样进行关联规则挖掘,2.3.2,生成频繁项集,格结构：常常用来枚举所有可能的项集,12,.,原始的方法:列出所有可能项集（如右图），即候选的频繁项集扫描事务数据库（左图），计算每个候选项集的支持度。将每个事务与候选项集相匹配，生成关联规则。算法复杂度O(NMw)=ExpensivesinceM=2d!,2.3.2,怎样进行关联规则挖掘,13,.,算法复杂度,给定d个事务项:项集的总数=2d可以生成的规则总数是:,Ifd=6,R=602rules,2.3.2,14,.,如何降低产生频繁项集的计算复杂度,减少候选项集的数目(M)完全的搜索:M=2d可以采用一些剪枝的方法减少M减少比较次数(NM)可以使用更高级的数据结构存储事务或候选项集（HashTree）有些事务和候选项集并不一定需要进行比较。减少事务数目(N),2.3.2,15,.,减少候选项集的策略,先验原理:如果一个项集是频繁的，则它的所有子集也一定是频繁的。即：先验原理成立是因为支持度具有以下特性:一个项集的支持度决不会超过其子集的支持度。这个性质也称为支持度度量的反单调性。,2.3.2,16,.,先验原理应用示例,Prunedsupersets,如果一个项集是非频繁的，则它的超集也一定是非频繁的,2.3.2,17,.,先验原理应用示例(续),Items(1-itemsets),Pairs(2-itemsets)(NoneedtogeneratecandidatesinvolvingCokeorEggs),Triplets(3-itemsets),MinimumSupport=3,Ifeverysubsetisconsidered,6C1+6C2+6C3=41Withsupport-basedpruning,6+6+1=13,2.3.2,18,.,Apriori算法(频繁项集的生成）,Method:Letk=1产生长度为1的频繁项集重复以下过程直到没有新的频繁项集产生从k个频繁项集中生成长度为k+1的候选项集对包含非频繁、且长度为k的子集的候选项集进行剪枝。扫描数据库，统计每个候选项集的支持度剔除非频繁项集，保留频繁项集,2.3.2,19,.,给定频繁项集L,找到所有的非空子集fL使得规则fLf可以满足最小置信度的要求如果A,B,C,D是一个频繁项集,则候选规则有:ABCD,ABDC,ACDB,BCDA,ABCD,BACD,CABD,DABCABCD,ACBD,ADBC,BCAD,BDAC,CDAB,如果|L|=k,将有2k2个候选的关联规则(因为忽略了L和L),2.3.2,Apriori算法(规则的生成）,20,.,怎样从频繁项集中高效的生成规则？一般而言,置信度并不具有单调性（这与支持度度量是不同的）例如：c(ABCD)canbelargerorsmallerthanc(ABD)但如果是由同一个候选项集产生的规则则具有单调性如，L=A,B,C,D:c(ABCD)c(ABCD)c(ABCD)因为当时，显然,2.3.2,Apriori算法(规则的生成）,21,.,Latticeofrules,LowConfidenceRule,2.3.2,Apriori算法(规则的生成）,22,.,2.3.2,Apriori算法(规则的生成）,23,.,2数据挖掘具体方法,2.4聚类分析,聚类的经典方法,24,.,什么是聚类分析?,聚类分析又称为“同质分组”或者“无监督的分类”，指把一组数据分成不同的“簇”，每簇中的数据相似而不同簇间的数据则距离较远。,2.4.1,25,.,聚类分析的应用,例如：将文档进行聚类以便于浏览将基因和蛋白质进行聚类以考察他们之间的相似功能对波动情况相似的股票进行聚类以供股民参考；帮助汇总减少大规模数据集的数据量,ClusteringprecipitationinAustralia,2.4.1,26,.,哪些不是聚类分析,有监督分类已经知道类标签信息，但不知道分类的规则简单分割例如：在注册时，根据学生的姓名音序进行分组。查询返回的结果这种分组是外部指定的结果。,2.4.1,27,.,聚类的一些概念可能是模棱两可的,2.4.1,28,.,聚类的不同类型,整个簇集合通常称为聚类层次聚类与划分聚类的不同点划分聚类简单地将数据对象划分成不重叠的子集（簇），使得每个数据对象恰好在一个子集中。层次聚类层次聚类是嵌套簇的集簇，组织成一棵有层次的树。,2.4.1,29,.,划分聚类,OriginalPoints,APartitionalClustering,2.4.1,30,.,层次聚类,TraditionalHierarchicalClustering,Non-traditionalHierarchicalClustering,Non-traditionalDendrogram,TraditionalDendrogram,2.4.1,31,.,不同的簇类型,明显分离的簇:每个点到同簇中任意点的距离比到不同簇中所有点的距离更近。,3个明显分离的簇,2.4.1,32,.,不同的簇类型,基于中心的簇每个点到其簇中心的距离比到其他簇中心的距离更近。Thecenterofaclusterisoftenacentroid,theaverageofallthepointsinthecluster,oramedoid,themost“representative”pointofacluster,4个基于中心的簇,2.4.1,33,.,不同的簇类型,连续簇(又称为“基于临近的簇”)每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近,8个连续簇,2.4.1,34,.,不同的簇类型,基于密度的簇簇是被低密度分开的高密度区域在簇不规则或缠结的情况下使用，或者当有噪声和离群点出现的时候使用。,6density-basedclusters,2.4.1,35,.,聚类算法,K均值（K-means）算法及其变化版本层次聚类算法基于密度聚类算法,2.4.2,36,.,基本的K均值聚类,每个簇内有一个质心centroid(通常定义为簇内样本点的平均值)每个样本划入离其最近的质心所在的簇K值是预先给定的基本思想是：首先，随机选择k个数据点做为聚类中心；然后，计算其它点到这些聚类中心点的距离，通过对簇中距离平均值的计算，不断改变这些聚类中心的位置，直到这些聚类中心不再变化为止。,2.4.2,37,.,K均值聚类,初始的质心是随机选择的.相同样本集上先后聚类，所得的簇往往不一样.质心通常就是簇内样本点的平均值。通常使用Euclidean距离、余弦相似性以及相关性等来表征样本间的相似度.在上述相似性度量下，多数K均值聚类算法可以收敛，并且只需要少数几次迭代即可收敛。算法中的停止条件也可以变成Untilrelativelyfewpointschangeclusters算法复杂度为o(n*K*I*d)n=样本总数,K=簇的个数,I=迭代次数,d=属性个数,2.4.2,38,.,两种不同的聚类结果,Sub-optimalClustering,OptimalClustering,OriginalPoints,2.4.2,39,.,具体过程（1）,2.4.2,40,.,具体过程（1）,2.4.2,41,.,具体过程（2）,2.4.2,42,.,具体过程（2）,2.4.2,43,.,初始点选择的困难性,假设样本集确实存在K个簇，则恰好从每个簇中选择一个初始质心的概率其实上也很小。IK越大时候，机会就越小。简单计算一下，假设每个簇都包含n个样本点，则例如,加入K=10,则这种概率=10!/1010=0.00036有时候，在迭代的过程中，算法能朝正确的方向修正初始质心，并最终获得正确的聚类，但有的时候算法却无法得到修正初始质心。以下是一个包含5对簇的例子。,2.4.2,44,.,例子,Startingwithtwoinitialcentroidsinoneclusterofeachpairofclusters,2.4.2,45,.,例子,Startingwithtwoinitialcentroidsinoneclusterofeachpairofclusters,2.4.2,46,.,例子,Startingwithsomepairsofclustershavingthreeinitialcentroids,whileotherhaveonlyone.,2.4.2,47,.,例子,Startingwithsomepairsofclustershavingthreeinitialcentroids,whileotherhaveonlyone.,2.4.2,48,.,解决方法,重复运行K均值聚类，取最佳结果Helps,butprobabilityisnotonyourside抽样并使用层次聚类算法决定初始质心选择多于k个样本点，而后从中彼此间距离最大的k个作为初始质心。后处理：拆散一个簇、合并两个簇采用二分K均值算法Notassusceptibletoinitializationissues,2.4.2,49,.,二分K均值算法,二分K均值算法K均值算法的变化版本,2.4.2,50,.,二分K均值算法,2.4.2,51,.,2数据挖掘具体方法,2.5异常检测,常用方法,52,.,异常检测,什么是异常样本/离群样本?在样本的散布图中，远离其他数据点的样本称为异常样本/离群样本。异常检测的目标发现与大部分其他对象不同的对象（即异常样本）。异常样本检测的应用领域:信用卡欺诈检测网络入侵检测生态系统失调监测公共卫生事件监测,2.5.1,53,.,异常检测的重要性,臭氧层空洞1985年，三位学者(Farman,GardinarandShanklin)从南极洲勘测数据中发现南极洲的臭氧含量较正常水平低了10%。但是Nimbus7卫星记录的数据却未显示臭氧含量降低这一情况。Why？事实上，卫星早已监测到了这一异常情况，但是因为记录显示臭氧含量过低，从而被卫星上的计算机程序当成异常样本而过滤掉了!,Sources:.au/ozone.html/ozone/science/hole/size.html,2.5.1,54,.,异常检测需要解决的问题,问题数据中有多少离群点?Findingneedleinahaystack麦芒中找针，沙里淘金异常样本本身是没有类标签的（无监督方法）有效性检测有一定的困难(类似于聚类)必要的假设:在数据中，正常样本的数量在一定程度上多于异常样本。,2.5.2,55,.,异常样本检测方法,大致步骤建立“正常”样本模型这种模型可以是统计模型也可以是其他的规律性模型使用正常样本模型检测异常样本异常样本的特征异于正常模型异常监测方法可以有以下类型基于图形&基于统计模型基于距离,2.5.2,56,.,基于图形的方法,可以使用盒图，散点图Boxplot(1-D),Scatterplot(2-D)缺点耗时比较主观,2.5.2,57,.,凸包法,极端点被认为是异常样本。使用凸包法监测极端值缺点：无法检测出出现在数据集中心的异常样本。,2.5.2,58,.,统计方法,使用参数模型描述样本集的分布情况(e.g.,正态分布)统计检测有赖于以下几点数据分布情况统计模型的参数(如,样本均值,方差)异常样本的数量(影响到置信区间的选择),2.5.2,了解,59,.,统计方法（1）：Grubbs检验法,假设样本分布服从于正态分布每次检测一个异常样本，将其从样本集中删去，而后重复检验以下假设H0:样本集中已没有异常样本HA:样本集中至少还有一个异常样本Grubbs检验统计量:如果下式成立，则拒绝H0,2.5.2,了解,60,.,假设数据集D包含两种样本，分别产生于不同的概率分布。M(正常样本的分布)A(异常样本的分布)大致方法:在初始阶段，假设所有样本都服从于M分布。令Lt(D)为t时刻D的log似然值。对于属于M的每个数据点xt,将其移至A令Lt+1(D)为新的log似然值.计算两者差距=Lt(D)Lt+1(D)如果c(some