数据仓库和数据挖掘技术.ppt

《数据仓库和数据挖掘技术.ppt》由会员分享，可在线阅读，更多相关《数据仓库和数据挖掘技术.ppt（89页珍藏版）》请在三一办公上搜索。

1、2023年2月11日星期六,数据仓库与数据挖掘技术,1,数据仓库和数据挖掘技术,什么是数据挖掘?几种主要数据挖掘模型和算法复杂类型数据的挖掘,2023年2月11日星期六,数据仓库与数据挖掘技术,2,数据挖掘都干了些什么?,英国电信需要发布一种新的产品，需要通过直邮的方式向客户推荐这种产品通过数据挖掘的方法使直邮的回应率提高了100GUS日用品零售商店需要准确的预测未来的商品销售量，降低库存成本通过数据挖掘的方法使库存成本比原来减少了3.8%,2023年2月11日星期六,数据仓库与数据挖掘技术,3,美国国防财务部需要从每年上百万比的军火交易中发现可能存在的欺诈现象发现可能存在欺诈的交易，进行深入

2、调查，节约了大量的调查成本汇丰银行需要对不断增长的客户群进行分类，对每种产品找出最有价值的客户。营销费用减少了30,数据挖掘都干了些什么?,2023年2月11日星期六,数据仓库与数据挖掘技术,4,什么是数据挖掘？,通过采用自动或半自动的手段，在海量数据中发现有意义的行为和规则的探测和分析活动。数据挖掘能够帮助你选择正确，瞄准潜在目标，向现有的客户提供额外的产品，识别那些准备离开的好客户。数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构 数据挖掘大部分的价值在于利用数据挖掘技术改善预言模型,2023年2月11日星期六,数据仓库与数据挖掘技术,5,数据挖掘应用领域,电信：流失银行：

3、聚类（细分）,交叉销售百货公司/超市：购物篮分析（关联规则）保险：细分，交叉销售，流失（原因分析）信用卡：欺诈探测，细分电子商务：网站日志分析税务部门：偷漏税行为探测警察机关：犯罪行为分析医学：医疗保健,2023年2月11日星期六,数据仓库与数据挖掘技术,6,(Big Bank&Credit Card Company),目的：发现新客户,数据挖掘效益分析(直邮）,2023年2月11日星期六,数据仓库与数据挖掘技术,7,Data Mining:A KDD Process,Data mining:the core of knowledge discovery process.,Data Clean

4、ing,Data Integration,Databases,Data Warehouse,Knowledge,Task-relevant Data,Selection,Data Mining,Pattern Evaluation,2023年2月11日星期六,数据仓库与数据挖掘技术,8,Data Mining:Confluence of Multiple Disciplines,Data Mining,Database Technology,Statistics,OtherDisciplines,InformationScience,MachineLearning(AI),Visualizat

5、ion,2023年2月11日星期六,数据仓库与数据挖掘技术,9,数据仓库和数据挖掘技术,什么是数据仓库（What is a data warehouse）?多维数据模型（A multi-dimensional data model）数据仓库体系结构（Data warehouse architecture）什么是数据挖掘（What is a Data Mining）?几种主要数据挖掘模型和算法复杂类型数据的挖掘,2023年2月11日星期六,数据仓库与数据挖掘技术,10,Data Mining Functionalities(1),Concept description:Characterizat

6、ion and discriminationGeneralize,summarize,and contrast data characteristics,e.g.,dry vs.wet regionsAssociation(correlation and causality)Multi-dimensional vs.single-dimensional association age(X,“20.29”)income(X,“20.29K”)buys(X,“PC”)support=2%,confidence=60%contains(T,“computer”)contains(x,“softwar

7、e”)1%,75%,2023年2月11日星期六,数据仓库与数据挖掘技术,11,Data Mining Functionalities(2),Classification and Prediction Finding models(functions)that describe and distinguish classes or concepts for future predictionPresentation:decision-tree,classification rule,neural networkPrediction:Predict some unknown or missing

8、numerical values Cluster analysisClass label is unknown:Group data to form new classes,e.g.,cluster houses to find distribution patternsClustering based on the principle:maximizing the intra-class similarity and minimizing the interclass similarity,2023年2月11日星期六,数据仓库与数据挖掘技术,12,Data Mining Functional

9、ities(3),Outlier analysisOutlier:a data object that does not comply with the general behavior of the dataIt can be considered as noise or exception but is quite useful in fraud detection,rare events analysisTrend and evolution analysisTrend and deviation:regression analysisSequential pattern mining,

10、periodicity analysisSimilarity-based analysisOther pattern-directed or statistical analyses,2023年2月11日星期六,数据仓库与数据挖掘技术,13,概念描述（Concept Description）,产生数据的特征化和比较描述特征化：提供给定数据汇集的简介汇总比较（也称区分）：提供两个或多个数据汇集的比较描述,2023年2月11日星期六,数据仓库与数据挖掘技术,14,数据概化和基于汇总的特征化,数据概化是一个过程，它将大的任务相关的数据集从较低的概念层抽象到较高的概念层.概化方法数据立方体(OLAP

11、approach)面向属性的归纳方法,2023年2月11日星期六,数据仓库与数据挖掘技术,15,面向属性的归纳,KDD Workshop(89)中提出方法介绍：使用SQL收集相关数据通过数据移除和数据概化来实现概化聚集通过合并相等的广义元组，并累计他们对应的计数值进行和使用者之间交互式的呈现方式.,基本方法,数据聚焦:选择和当前分析相关的数据，包括维。属性移除:如果某个属性包含大量不同值，但是1)在该属性上没有概化操作，或者2）它的较高层概念用其它属性表示。属性概化:如果某个属性包含大量不同值，同时在该属性上有概化操作符，则运用该操作符进行概化。属性阈值控制:typical 2-8,speci

12、fied/default.概化关系阈值控制:控制最终关系的大小,特征化的一个例子,Prime Generalized Relation,Initial Relation,挖掘类比较,比较:比较两个或者更多类.方法:将相关的数据分成目标类和比较类。将两个类别的数据概化到相同的层次。用相同层次的描述对元组进行比较。对于每个元组展现其描述和两个衡量标准将差异很大的元组特别显示出来相关性分析:发现最能体现类别之间差异的属性.,2023年2月11日星期六,数据仓库与数据挖掘技术,19,例子：分析性比较,Prime generalized relation for the target class:Gra

13、duate students,Prime generalized relation for the contrasting class:Undergraduate students,2023年2月11日星期六,数据仓库与数据挖掘技术,20,从大型数据库中挖掘关联规则,关联规则挖掘：在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。举例：规则形式：“Body Head support,confidence”.buys(x,“diapers”)buys(x,“beers”)0.5%,60%major(x,“CS”)takes(x,“DB”)

14、grade(x,“A”)1%,75%,2023年2月11日星期六,数据仓库与数据挖掘技术,21,关联规则：基本概念,给定:(1)交易数据库(2)每笔交易是：一个项目列表(消费者一次购买活动中购买的商品)查找:所有描述一个项目集合与其他项目集合相关性的规则应用*护理用品(商店应该怎样提高护理用品的销售？)家用电器*(其他商品的库存有什么影响?)在产品直销中使用附加邮寄,2023年2月11日星期六,数据仓库与数据挖掘技术,22,Transactions Example,ITEMS:A=milkB=breadC=cerealD=sugarE=eggs,Instances=Transactions,2

15、023年2月11日星期六,数据仓库与数据挖掘技术,23,Definitions,Item:attribute=value pair or simply valueusually attributes are converted to binary flags for each value,e.g.product=“A”is written as“A”Itemset I:a subset of possible itemsExample:I=A,B,E(order unimportant)Transaction:(TID,itemset)TID is transaction ID,2023年2月

16、11日星期六,数据仓库与数据挖掘技术,24,Support and Frequent Itemsets,Support of an itemset sup(I)=no.of transactions t that support(i.e.contain)IIn example database:sup(A,B,E)=2,sup(B,C)=4 Frequent itemset I is one with at least the minimum support count sup(I)=minsup,2023年2月11日星期六,数据仓库与数据挖掘技术,25,Association Rules,A

17、ssociation rule R:Itemset1=Itemset2Itemset1,2 are disjoint and Itemset2 is non-emptymeaning:if transaction includes Itemset1 then it also has Itemset2ExamplesA,B=E,CA=B,C,2023年2月11日星期六,数据仓库与数据挖掘技术,26,From Frequent Itemsets to Association Rules,Q:Given frequent set A,B,E,what are possible association

18、 rules?A=B,EA,B=EA,E=BB=A,EB,E=AE=A,B _=A,B,E(empty rule),or true=A,B,E,2023年2月11日星期六,数据仓库与数据挖掘技术,27,规则度量：支持度与可信度,查找所有的规则 X&Y Z 具有最小支持度和可信度支持度,s,一次交易中包含X、Y、Z的可能性可信度,c,包含X、Y的交易中也包含Z的条件概率,设最小支持度为50%,最小可信度为 50%,则可得到A C(50%,66.6%)C A(50%,100%),买尿布的客户,二者都买的客户,买啤酒的客户,2023年2月11日星期六,数据仓库与数据挖掘技术,28,Associati

19、on Rules Example:,Q:Given frequent set A,B,E,what association rules have minsup=2 and minconf=50%?A,B=E:conf=2/4=50%A,E=B:conf=2/2=100%B,E=A:conf=2/2=100%E=A,B:conf=2/2=100%Dont qualify A=B,E:conf=2/6=33%A,E:conf=2/7=28%A,B,E:conf:2/9=22%50%,2023年2月11日星期六,数据仓库与数据挖掘技术,29,Find Strong Association Rules

20、,A rule has the parameters minsup and minconf:sup(R)=minsup and conf(R)=minconfProblem:Find all association rules with given minsup and minconfFirst,find all frequent itemsets,2023年2月11日星期六,数据仓库与数据挖掘技术,30,Finding itemsets:next level,Apriori algorithm(Agrawal&Srikant)Idea:use one-item sets to generat

21、e two-item sets,two-item sets to generate three-item sets,If(A B)is a frequent item set,then(A)and(B)have to be frequent item sets as well!In general:if X is frequent k-item set,then all(k-1)-item subsets of X are also frequentCompute k-item set by merging(k-1)-item sets,2023年2月11日星期六,数据仓库与数据挖掘技术,31

22、,An example,Given:five three-item sets(A B C),(A B D),(A C D),(A C E),(B C D)Lexicographic order improves efficiencyCandidate four-item sets:(A B C D)Q:OK?A:yes,because all 3-item subsets are frequent(A C D E)Q:OK?A:No,because(C D E)is not frequent,2023年2月11日星期六,数据仓库与数据挖掘技术,32,Generating Association

23、 Rules,Two stage process:Determine frequent itemsets e.g.with the Apriori algorithm.For each frequent item set I for each subset J of Idetermine all association rules of the form:I-J=JMain idea used in both stages:subset property,2023年2月11日星期六,数据仓库与数据挖掘技术,33,Apriori算法 例子,数据库 D,扫描 D,C1,L1,L2,C2,C2,扫描

24、 D,C3,L3,扫描 D,2023年2月11日星期六,数据仓库与数据挖掘技术,34,如何计算候选集的支持度,计算支持度为什么会成为一个问题？候选集的个数非常巨大 一笔交易可能包含多个候选集方法:用 hash-tree 存放候选集树的叶子节点 of存放项集的列表和支持度内部节点 是一个hash表Subset 函数:找到包含在一笔交易中的所有候选集,2023年2月11日星期六,数据仓库与数据挖掘技术,35,生成候选集的例子,L3=abc,abd,acd,ace,bcd自连接:L3*L3abc 和 abd 得到 abcd acd 和 ace 得到 acde修剪:ade 不在 L3中，删除 acde

25、C4=abcd,2023年2月11日星期六,数据仓库与数据挖掘技术,36,提高Apriori效率的方法,基于Hash的项集计数:如果一个 k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。减少交易记录:不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集分割:一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。采样:在给定数据的子集上挖掘，使用小的支持度+完整性验证方法动态项集计数:在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。,2023年2月11日星期六,数据仓库与数据挖掘技术,37,Apriori 够快了吗

26、?性能瓶颈,Apriori算法的核心:用频繁的(k 1)-项集生成候选的频繁 k-项集用数据库扫描和模式匹配计算候选集的支持度Apriori 的瓶颈:候选集生成巨大的候选集:104 个频繁1-项集要生成 107 个候选 2-项集要找尺寸为100的频繁模式，如 a1,a2,a100,你必须先产生2100 1030 个候选集多次扫描数据库：如果最长的模式是n的话，则需要(n+1)次数据库扫描,2023年2月11日星期六,数据仓库与数据挖掘技术,38,挖掘频繁集 不用生成候选集,用Frequent-Pattern tree(FP-tree)结构压缩数据库,高度浓缩，同时对频繁集的挖掘又完备的避免代价

27、较高的数据库扫描开发一种高效的基于FP-tree的频繁集挖掘算法采用分而治之的方法学：分解数据挖掘任务为小任务避免生成关联规则:只使用部分数据库!,2023年2月11日星期六,数据仓库与数据挖掘技术,39,用交易数据库建立 FP-tree,最小支持度=0.5,TIDItems bought(ordered)frequent items100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300 b,f,h,j,of,b400 b,c,k,s,pc,b,p500 a,f,c,e,l,p,m,nf,c,a,m,p,步骤:扫描数据库一次，得到频繁1-

28、项集把项按支持度递减排序再一次扫描数据库，建立FP-tree,2023年2月11日星期六,数据仓库与数据挖掘技术,40,FP-tree 结构的好处,完备:不会打破交易中的任何模式包含了序列模式挖掘所需的全部信息紧密去除不相关信息不包含非频繁项支持度降序排列:支持度高的项在FP-tree中共享的机会也高决不会比原数据库大（如果不计算树节点的额外开销)例子:对于 Connect-4 数据库,压缩率超过 100,2023年2月11日星期六,数据仓库与数据挖掘技术,41,用 FP-tree挖掘频繁集,基本思想(分而治之)用FP-tree地归增长频繁集方法 对每个项，生成它的 条件模式库,然后是它的 条

29、件 FP-tree对每个新生成的条件FP-tree，重复这个步骤直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子路径对应的相集都是频繁集),2023年2月11日星期六,数据仓库与数据挖掘技术,42,多层关联规则,项通常具有层次底层的项通常支持度也低某些特定层的规则可能更有意义交易数据库可以按照维或层编码可以进行共享的多维挖掘,2023年2月11日星期六,数据仓库与数据挖掘技术,43,挖掘多层关联规则,自上而下，深度优先的方法：先找高层的“强”规则：牛奶 面包 20%,60%.再找他们底层的“弱”规则：酸奶 黄面包 6%,50%.多层关联规则的变种层次交叉的关联规则：酸奶 复旦面

30、包房 黄面包不同种分层方法间的关联规则：酸奶 复旦面包房面包,2023年2月11日星期六,数据仓库与数据挖掘技术,44,关联规则结果显示(Table Form),2023年2月11日星期六,数据仓库与数据挖掘技术,45,关联规则可视化Using Plane Graph,2023年2月11日星期六,数据仓库与数据挖掘技术,46,关联规则可视化Using Rule Graph,2023年2月11日星期六,数据仓库与数据挖掘技术,47,分类与预测,数据分类是基于训练数据集和类标号对数据进行分类，建立模型，描述预定的数据类集或概念集预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的属性值或

31、值区间,2023年2月11日星期六,数据仓库与数据挖掘技术,48,Classification Process(1):Model Construction,TrainingData,ClassificationAlgorithms,IF rank=professorOR years 6THEN tenured=yes,Classifier(Model),2023年2月11日星期六,数据仓库与数据挖掘技术,49,Classification Process(2):Use the Model in Prediction,Classifier,TestingData,Unseen Data,(Jef

32、f,Professor,4),Tenured?,2023年2月11日星期六,数据仓库与数据挖掘技术,50,Training Dataset,This follows an example from Quinlans ID3,2023年2月11日星期六,数据仓库与数据挖掘技术,51,Output:A Decision Tree for“buys_computer”,age?,overcast,student?,credit rating?,no,yes,fair,excellent,=30,40,no,no,yes,yes,yes,30.40,2023年2月11日星期六,数据仓库与数据挖掘技术,

33、52,决策树算法,基本算法（贪心算法）自上而下分而治之的方法开始时，所有的数据都在根节点属性都是种类字段(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如,information gain)停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割,2023年2月11日星期六,数据仓库与数据挖掘技术,53,属性选择的统计度量,Information gain(ID3/C4.5)所有属性假设都是种类字段经过修改之后可以适用于数值字段Gini index(IBM IntelligentMiner)能够适用于种类和数

34、值字段,2023年2月11日星期六,数据仓库与数据挖掘技术,54,Information Gain(ID3/C4.5),选择属性的标准：具有最高Information Gain假设有两个类,P 和 N假设集合S中含有p个类别P的记录,n个类别N的记录决定任意一个记录属于类别P或者N所需要的information.,2023年2月11日星期六,数据仓库与数据挖掘技术,55,Information Gain 在决策树中的使用,假设使用属性A将把集合S分成 V份 S1,S2,Sv 如果 Si 中包含 pi 个类别为 P的记录,ni 个类别为 N,的记录。那么熵就是(entropy),从而这个信息增益

35、就是,2023年2月11日星期六,数据仓库与数据挖掘技术,56,使用信息增益进行属性选择,Class P:buys_computer=“yes”Class N:buys_computer=“no”I(p,n)=I(9,5)=0.940Compute the entropy for age:,HenceSimilarly,2023年2月11日星期六,数据仓库与数据挖掘技术,57,Gini Index(IBM IntelligentMiner),集合T包含N个类别的记录，那么其Gini指标就是pj 类别j出现的频率如果集合T分成两部分 N1 and N2。那么这个分割的Gini就是提供最小Gini

36、split 就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).,2023年2月11日星期六,数据仓库与数据挖掘技术,58,几种经典算法介绍,CART min(P(c1),P(c2)2P(c1)P(c2)P(c1)logP(c1)+P(c2)logP(c2)C4.5(ID3)C4.5(ID3)对种类字段处理时，缺省是对每个值作为一个分割Gain和Gain RatioCHAID在Overfitting前停止树的生成必须都是种类字段选择分割。X2检验,2023年2月11日星期六,数据仓库与数据挖掘技术,59,Scalable Decision Tree Induction 数据挖掘中

37、提出的方法,SLIQ(EDBT96 Mehta et al.)SPRINT(VLDB96 J.Shafer et al.)PUBLIC(VLDB98 Rastogi&Shim)RainForest(VLDB98 Gehrke,Ramakrishnan&Ganti)builds an AVC-list(attribute,value,class label),2023年2月11日星期六,数据仓库与数据挖掘技术,60,结果显示(一),什么是聚类分析?,簇（Cluster）:一个数据对象的集合在同一个类中，对象之间具有相似性；不同类的对象之间是相异的。聚类分析把一个给定的数据对象集合分成不同的簇；聚

38、类是一种无监督分类法:没有预先指定的类别；典型的应用作为一个独立的分析工具，用于了解数据分布；作为其它算法的一个数据预处理步骤；,2023年2月11日星期六,数据仓库与数据挖掘技术,62,应用聚类分析的例子,市场销售:帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；土地使用:在一个陆地观察数据库中标识那些土地使用相似的地区；保险:对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；城市规划:根据类型、价格、地理位置等来划分不同类型的住宅；地震研究:根据地质断层的特点把已观察到的地震中心分成不同的类；,2023年2月11日星期六,数据仓库与数据挖掘技术,63,

39、什么是一个好的聚类方法?,一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；,2023年2月11日星期六,数据仓库与数据挖掘技术,64,Major Clustering Approaches,Partitioning algorithms:Construct various partitions and then evaluate them by some criterionHierarchy algorithms

40、:Create a hierarchical decomposition of the set of data(or objects)using some criterionDensity-based:based on connectivity and density functionsGrid-based:based on a multiple-level granularity structureModel-based:A model is hypothesized for each of the clusters and the idea is to find the best fit

41、of that model to each other,2023年2月11日星期六,数据仓库与数据挖掘技术,65,划分方法:基本概念,划分方法:将一个包含n个数据对象的数据库组织成k个划分（k=n），其中每个划分代表一个簇（Cluster）。给定一个k，要构造出k个簇，并满足采用的划分准则：全局最优:尽可能的列举所有的划分；启发式方法:k-平均和k-中心点算法k-平均(MacQueen67):由簇的中心来代表簇；k-中心点或 PAM(Partition around medoids)(Kaufman&Rousseeuw87):每个簇由簇中的某个数据对象来代表。,2023年2月11日星期六,数据

42、仓库与数据挖掘技术,66,K-平均算法,给定k，算法的处理流程如下:1.随机的把所有对象分配到k个非空的簇中；2.计算每个簇的平均值，并用该平均值代表相应的簇；3.将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；4.回到第二步，直到不再有新的分配发生。,2023年2月11日星期六,数据仓库与数据挖掘技术,67,K-平均算法,例子,2023年2月11日星期六,数据仓库与数据挖掘技术,68,K-平均算法,优点 相对高效的:算法复杂度O(tkn),其中n 是数据对象的个数,k 是簇的个数,t是迭代的次数，通常k,t n.算法通常终止于局部最优解；缺点只有当平均值有意义的情况下才能使用，

43、对于类别字段不适用；必须事先给定要生成的簇的个数；对“噪声”和异常数据敏感；不能发现非凸面形状的数据。,2023年2月11日星期六,数据仓库与数据挖掘技术,69,K-平均算法的变种,一些变种在下面几个方面有所不同：初始k个平均值的选择；相异度的计算；计算簇的平均值的策略；处理种类字段:k-模算法(Huang98)用模来替代平均值；用新的相异度计算方法来处理类别字段；用基于频率的方法来修改簇的模；k-原型算法：综合k-平均和k-模算法，能同时处理类别字段和数值字段。,2023年2月11日星期六,数据仓库与数据挖掘技术,70,K-中心点算法,找出簇中位置最中心的对象，即中心点来代表簇PAM(Par

44、titioning Around Medoids,1987)设定一个中心点的初始集合，然后反复的用非中心点对象来替代中心点对象，以改进聚类的质量；PAM 算法在大数据集上效率较低，没有良好的可伸缩性；CLARA(Kaufmann&Rousseeuw,1990)CLARANS(Ng&Han,1994):Randomized sampling,2023年2月11日星期六,数据仓库与数据挖掘技术,71,层次方法,采用距离作为衡量聚类的标准。该方法不在需要指定聚类的个数，但用户可以指定希望得到的簇的数目作为一个结束条件。,2023年2月11日星期六,数据仓库与数据挖掘技术,72,AGNES(Agglo

45、merative Nesting),由 Kaufmann 和 Rousseeuw 提出；(1990)使用单链接方法和差异度矩阵；合并那些具有最小差异度的节点；Go on in a non-descending fashion最后所有的对象合并形成一个簇。,2023年2月11日星期六,数据仓库与数据挖掘技术,73,A Dendrogram Shows How the Clusters are Merged Hierarchically,Decompose data objects into a several levels of nested partitioning(tree of clust

46、ers),called a dendrogram.A clustering of the data objects is obtained by cutting the dendrogram at the desired level,then each connected component forms a cluster.,2023年2月11日星期六,数据仓库与数据挖掘技术,74,DIANA(Divisive Analysis),由 Kaufmann 和 Rousseeuw 提出(1990)AGNES算法的逆过程；最终每个新的簇只包含一个对象；,2023年2月11日星期六,数据仓库与数据挖掘

47、技术,75,More on Hierarchical Clustering Methods,层次方法的主要缺点：没有良好的伸缩性:时间复杂度至少是 O(n2)一旦一个合并或分裂被执行，就不能修复；综合层次聚类和其它的聚类技术：BIRCH(1996):uses CF-tree and incrementally adjusts the quality of sub-clustersCURE(1998):selects well-scattered points from the cluster and then shrinks them towards the center of the clu

48、ster by a specified fractionCHAMELEON(1999):hierarchical clustering using dynamic modeling,2023年2月11日星期六,数据仓库与数据挖掘技术,76,复杂类型数据的挖掘,空间数据挖掘多媒体数据挖掘时间序列数据挖掘文本数据挖掘Web数据挖掘,2023年2月11日星期六,数据仓库与数据挖掘技术,77,空间数据挖掘,是对空间数据库中非显式存在的知识、空间关系或其他有意义的模式等的提取空间数据挖掘在地理信息系统、地理市场、遥感、图像数据库探测、医学图像处理、导航、交通控制、环境研究等使用空间数据的领域中有广泛应用

49、,2023年2月11日星期六,数据仓库与数据挖掘技术,78,Refining or combining searches,Search for“blue sky”(top layout grid is blue),Search for“blue sky andgreen meadows”(top layout grid is blue and bottom is green),Search for“airplane in blue sky”(top layout grid is blue and keyword=“airplane”),Mining Multimedia Databases,2

50、023年2月11日星期六,数据仓库与数据挖掘技术,79,Mining Multimedia Databases in,MultiMediaMiner,2023年2月11日星期六,数据仓库与数据挖掘技术,80,Classification in MultiMediaMiner,2023年2月11日星期六,数据仓库与数据挖掘技术,81,时序数据和序列数据的挖掘,趋势分析相似性搜索与时间有关的序列模式挖掘周期模式挖掘,2023年2月11日星期六,数据仓库与数据挖掘技术,82,文本数据挖掘,文本数据分析和信息检索文本检索的基本度量（查准率、查全率）基于关键字和基于相似性的检索潜在语义标引其他文本检索标