数据挖掘5概念描述特征化与比较课件.ppt

1、2022-8-121概念描述概念描述2022-8-122特征化和比较特征化和比较n什么是概念描述什么是概念描述?n数据概化和基于汇总的特征化数据概化和基于汇总的特征化n解析特征化解析特征化:分析属性之间的关联性分析属性之间的关联性n挖掘类比较挖掘类比较:获取不同类之间的不同处获取不同类之间的不同处n在大型数据库中挖掘描述统计度量在大型数据库中挖掘描述统计度量n讨论讨论n总结总结2022-8-123什么是概念描述什么是概念描述?n描述性 vs.预测性 数据挖掘n描述性数据挖掘描述性数据挖掘:n预测性数据挖掘预测性数据挖掘:n概念描述:n特征化特征化:对所选择的数据集给出一个简单明了的描述，汇总n

2、比较比较:提供对于两个或多个数据集进行比较的描述2022-8-124概念描述和概念描述和OLAPOLAP区别区别n概念描述:n 能够处理复杂的数据类型和各种汇总方法n 更加自动化nOLAP:OLAP:n只能限制于少量的维度和数据类型n用户控制的流程2022-8-125特征化和比较特征化和比较n什么是概念描述?n数据概化和基于汇总的特征化数据概化和基于汇总的特征化n分析特征化:分析属性之间的关联性n挖掘类比较:获取不同类之间的不同处n在大型数据库中挖掘描述统计度量n讨论n总结2022-8-126数据概化和基于汇总的特征化数据概化和基于汇总的特征化n数据概化n将大量的相关数据从一个较低的概念层次抽

3、象、转化到一个比较高的层次n方法:nOLAP方法：n面向属性的归纳2022-8-127OLAPOLAP方法方法n在数据立方体上进行计算和存储结果n优点n效率高n能够计算多种汇总n如：count,average,sum,min,maxn还可以使用roll-down和roll-up操作n限制n只能处理非数值化数据和数值数据的简单汇总。n只能分析，不能自动的选择哪些字段和相应的概念层次2022-8-128面向属性的归纳nKDD Workshop(89)中提出n不限制于种类字段和特定的汇总方法n方法介绍：n使用SQL等收集相关数据n通过数据属性值删除和属性值概化来实现概化n聚集通过合并相等的广义元组，

4、并累计他们对应的计数值进行n和使用者之间交互式的呈现方式.2022-8-129基本方法基本方法n数据聚焦数据聚焦:选择和当前分析相关的数据，包括维。n属性删除属性删除:如果某个属性包含大量不同值，但是 1)在该属性上没有概化操作，或者2）它的较高层概念用其它属性表示。n属性概化属性概化:如果某个属性包含大量不同值，同时在该属性上有概化操作符，则运用该操作符进行概化。n属性阈值控制属性阈值控制:typical 2-8,specified/default.n概化关系阈值控制概化关系阈值控制:控制最终关系的大小2022-8-1210基本算法基本算法nInitialRelInitialRel:得到相关

5、数据，形成初始关系表nPreGen:通过统计不同属性的含有的不同值的个数决定是丢弃该属性还是对其进行汇总。nPrimeGen:根据上一步的计算结果，对属性概化到相应的层次，计算汇总值，得到主概化关系。n结果的表示结果的表示:概化关系、交叉表、3D立方体2022-8-1211示例示例nDMQL:use Big_University_DBmine characteristics as“Science_Students”in relevance to name,gender,major,birth_place,birth_date,residence,phone#,gpafrom studentwh

6、ere status in“graduate”n相应的相应的SQL:SQL:Select name,gender,major,birth_place,birth_date,residence,phone#,gpafrom studentwhere status in“Msc”,“MBA”,“PhD”2022-8-1212类特征化：示例类特征化：示例NameGenderMajorBirth-PlaceBirth_dateResidencePhone#GPAJimWoodman M CSVancouver,BC,Canada 8-12-763511 Main St.,Richmond687-459

7、83.67ScottLachance M CSMontreal,Que,Canada28-7-75345 1st Ave.,Richmond253-91063.70Laura Lee FPhysicsSeattle,WA,USA25-8-70125 Austin Ave.,Burnaby420-52323.83RemovedRetainedSci,Eng,BusCountryAge rangeCityRemovedExcl,VG,.GenderMajorBirth_regionAge_rangeResidenceGPACount MScience Canada 20-25RichmondVer

8、y-good 16 FScience Foreign 25-30BurnabyExcellent 22 Birth_RegionGenderCanadaForeignTotal M 16 14 30 F 10 22 32 Total 26 36 62Prime Generalized RelationInitial Relation2022-8-1213概化结果的表示概化结果的表示n概化关系:n一个表格，其中有属性字段，后附汇总方法。n交叉表:n二维交叉表n可视化方法:nPie charts,bar charts,curves,cubes,and other visual forms.n量化特

9、征规则:(上表与上表与136页例页例4.26).%47:)(_%53:)(_)(tforeignxregionbirthtCanadaxregionbirthmalexgender2022-8-1214表达方式表达方式-概化关系概化关系(133页例页例4.22)2022-8-1215表达方式表达方式交叉表交叉表(133页例页例4.23)2022-8-1216使用使用CubeCube技术进行实现技术进行实现n对给定的数据动态创建数据立方体：对给定的数据动态创建数据立方体：n便于有效的下钻操作n可能增加响应时间n解决方法：实现存储一些较高层次的统计信息。n使用预定义的数据立方体：使用预定义的数据立

10、方体：n预先构建数据立方体nCube计算的花费和额外的存储空间2022-8-1217特征化和比较n什么是概念描述?n数据概化和基于汇总的特征化n分析特征化分析特征化:分析属性之间的关联性分析属性之间的关联性n挖掘类比较:获取不同类之间的不同处n在大型数据库中挖掘描述统计度量n讨论n总结2022-8-1218属性相关性分析属性相关性分析nwhy?n哪些维需要包括?n需要概化到什么层次?n减少属性；从而容易理解模型结果nWhat?n使用统计的方法进行数据预处理n过滤掉一些不相关或者相关性比较弱的字段n保留并对相关属性进行排序n相关性和维度、层次有关n分析特征化，分析比较 2022-8-1219属性

11、相关性分析属性相关性分析n步骤：n数据收集n使用保守的AOI进行预相关分析n相关性分析，删除不相关和弱相关属性n使用AOI产生概念描述2022-8-1220相关性度量标准相关性度量标准n相关性度量标准决定了如何对属性进行判断的标准n方法n信息增益information gain(ID3)n增益比gain ratio(C4.5)nGini索引gini indexn不确定性n相关系数2022-8-1221Entropy 和 Information Gainn集合S中类别Ci的记录个数是si 个 i=1,m n期望信息n属性A的熵是n信息增益ssss,.,s,ssimiim2121log)I()s,

12、.,s(Iss.sE(A)mjjvjmjj111E(A)s,.,s,I(sGain(A)m212022-8-1222一个例子一个例子(131页例页例5.9)n任务n使用分析特征化来了解研究生的一般特征n属性名称 gender,major,birth_place,birth_date,phone#,and gpanGen(ai)=concept hierarchies on ainUi=attribute analytical thresholds for ainTi=attribute generalization thresholds for ainR=attribute relevance

13、 threshold2022-8-1223例子：分析特征化（续）例子：分析特征化（续）n1.数据收集ntarget class:graduate studentncontrasting class:undergraduate studentn2.使用 Ui分析概化n属性删除nremove name and phone#n属性概化n generalize major,birth_place,birth_date and gpanaccumulate countsn候选关系:gender,major,birth_country,age_range and gpa2022-8-1224例子：分析特征

14、化例子：分析特征化(2)(2)Candidate relation for Target class:Graduate students(=120)Candidate relation for Contrasting class:Undergraduate students(=130)2022-8-1225例子：分析特征化例子：分析特征化(3)(3)n3.相关性分析n计算期望信息n计算每个属性的熵998802501302501302501202501201301202221.loglog),I()s,I(sFor major=”Science”:S11=84S21=42I(s11,s21)=0

15、.9183For major=”Engineering”:S12=36S22=46I(s12,s22)=0.9892For major=”Business”:S13=0S23=42I(s13,s23)=0Number of grad students in“Science”Number of undergrad students in“Science”2022-8-1226例子：分析特征化例子：分析特征化(4)(4)n得出每个属性的熵n计算每个属性的Information GainnInformation gain for all attributes787302504225082250126

16、231322122111.)s,s(I)s,s(I)s,s(IE(major)2115021.E(major)s,I(s)Gain(majorGain(gender)=0.0003Gain(birth_country)=0.0407Gain(major)=0.2115Gain(gpa)=0.4490Gain(age_range)=0.59712022-8-1227例子：分析特征化例子：分析特征化(5)(5)n4.Initial working relation(W0)derivationnR=0.1n删除不相关或者弱相关的属性=drop gender,birth_countryn删除比较类的关

17、系n5.在W0进行AOI分析Initial target class working relation W0:Graduate students2022-8-1228特征化和比较n什么是概念描述?n数据概化和基于汇总的特征化n分析特征化:分析属性之间的关联性n挖掘类比较挖掘类比较:获取不同类之间的不同处获取不同类之间的不同处n在大型数据库中挖掘描述统计度量n讨论n总结2022-8-1229挖掘类比较挖掘类比较n比较:比较两个或者更多类.n方法:n将相关的数据分成目标类和比较类。n将两个类别的数据概化到相同的层次。n用相同层次的描述对元组进行比较。n对于每个元组展现其描述和两个衡量标准:nsup

18、port-distribution within single classncomparison-distribution between classesn将差异很大的元组特别显示出来n相关性分析:n发现最能体现类别之间差异的属性.2022-8-1230例子：分析性比较例子：分析性比较(133页例页例5.10)nTaskn使用区别规则来分析本科生和研究生nDMQL queryuse Big_University_DBmine comparison as“grad_vs_undergrad_students”in relevance to name,gender,major,birth_plac

19、e,birth_date,residence,phone#,gpafor“graduate_students”where status in“graduate”versus“undergraduate_students”where status in“undergraduate”analyze count%from student2022-8-1231例子：分析性比较例子：分析性比较(2)(2)n条件：nattributes name,gender,major,birth_place,birth_date,residence,phone#and gpanGen(ai)=concept hier

20、archies on attributes ainUi=attribute analytical thresholds for attributes ainTi=attribute generalization thresholds for attributes ainR=attribute relevance threshold2022-8-1232例子：分析性比较例子：分析性比较(3)(3)n1.数据收集n目标类和比较类n2.属性相关性分析nremove attributes name,gender,major,phone#n3.同步概化ncontrolled by user-specif

21、ied dimension thresholdsnprime target and contrasting class(es)relations/cuboids2022-8-1233例子：分析性比较例子：分析性比较(4)(4)Birth_country Age_rangeGpaCount%Canada20-25Good5.53%Canada25-30Good2.32%CanadaOver_30Very_good5.86%OtherOver_30Excellent4.68%Prime generalized relation for the target class:Graduate stude

22、ntsBirth_country Age_rangeGpaCount%Canada15-20Fair5.53%Canada15-20Good4.53%Canada25-30Good5.02%OtherOver_30Excellent0.68%Prime generalized relation for the contrasting class:Undergraduate students2022-8-1234例子：分析性比较例子：分析性比较(5)(5)n4.在目标和比较类别上，Drill down,roll up and other OLAP operations，确定概化层次.n5.展现方

23、式n generalized relations,crosstabs,bar charts,pie charts,or rulesn比较性的度量，以体现目标类和比较类之间的差别ne.g.count%2022-8-1235量化区分规则量化区分规则nCj=目标类nqa=概化元组n也覆盖比较类别的元组nd-weightn范围:0,1n量化区别规则miiaja)Ccount(q)Ccount(qweightd1d_weight:dX)condition(ss(X)target_claX,2022-8-1236例子例子:量化区别规则量化区别规则n量化区别规则(135页例页例5.11)nwhere 90/

24、(90+120)=30%StatusBirth_countryAge_rangeGpaCountGraduateCanada25-30Good90UndergraduateCanada25-30Good210Count distribution between graduate and undergraduate students for a generalized tuple%30:)(3025)(_)(_)(_,dgoodXgpaXrangeageCanadaXcountrybirthXstudentgraduateX2022-8-1237类别描述类别描述n量化特征规则n必要n量化区别规则

25、n充分n量化描述规则n必要和充分w:d,w:t.w:d,w:tnn111(X)condition(X)conditionss(X)target_claX,nd_weight:dX)condition(ss(X)target_claX,t_weight:tX)condition(ss(X)target_claX,2022-8-1238例子例子:量化描述规则量化描述规则(136页例页例5.13)n对于目标类Europe的量化描述规则(137页例页例5.14)Location/item TV Computer Both_items Count t-wt d-wt Count t-wt d-wt Co

26、unt t-wt d-wt Europe 80 25%40%240 75%30%320 100%32%N_Am 120 17.65%60%560 82.35%70%680 100%68%Both_ regions 200 20%100%800 80%100%1000 100%100%Crosstab showing associated t-weight,d-weight values and total number(in thousands)of TVs and computers sold at AllElectronics in 199830%:d75%,:t)computer(ite

27、m(X)40%:d25%,:t)TV(item(X)Europe(X)X,2022-8-1239特征化和比较n什么是概念描述?n数据概化和基于汇总的特征化n分析特征化:分析属性之间的关联性n挖掘类比较:获取不同类之间的不同处n在大型数据库中挖掘描述统计度量在大型数据库中挖掘描述统计度量n讨论n总结2022-8-1240挖掘数据散布特征挖掘数据散布特征n动机n更好的了解数据:集中趋势,差别 和 分布n数据散布特征 nmedian,max,min,quantiles,outliers,variance,等.2022-8-1241衡量中心趋势衡量中心趋势n平均值n带权平均n中位数:一个整体度量n如果

28、是奇数，则为中间数，偶数则为中间两数的平均n用插值的方法进行估计n模n出现次数最多的值nUnimodal,bimodal,trimodalnEmpirical formula:niixnx11niiniiiwxwx11cflfnLmedianmedian)(2/(1)(3medianmeanmodemean2022-8-1242衡量离散趋势衡量离散趋势n四分位数四分位数,异常异常 和和 盒图盒图n四分位数四分位数:Q1(25th percentile),Q3(75th percentile)n中间四分位区间中间四分位区间:IQR=Q3 Q1 n五数概括五数概括:min,Q1,M,Q3,maxn

29、盒图盒图:ends of the box are the quartiles,median is marked,whiskers,and plot outlier individuallyn异常异常:usually,a value higher/lower than 1.5 x IQRn方差和标准差nVariance s2:(algebraic,scalable computation)nStandard deviation s is the square root of variance s2niniiiniixnxnxxns1122122)(111)(112022-8-1243 盒图分析盒

30、图分析n五数概括五数概括:Minimum,Q1,M,Q3,Maximumn盒图盒图n数据用盒子的形式表现n盒子的两端分别是两个分位数，i.e.,the height of the box is IRQn中位数用一条线来表示。n延长线:从盒子延长到最大和最小值2022-8-1244A BoxplotA boxplot2022-8-1245数据分布的可视化：盒图分析数据分布的可视化：盒图分析2022-8-1246在大型数据库中挖掘统计信息在大型数据库中挖掘统计信息n方差方差n标准差标准差:方差的平方根n衡量分散程度n当且仅当所有值一样的时候为0。n方差和标准差都是代数的22122111)(11ii

31、niixnxnxxns2022-8-1247直方图（频率直方图）直方图（频率直方图）n图形化表示类描述的基本统计信息n频率直方图2022-8-1248分位数图分位数图2022-8-1249分位数分位数-分位数分位数(Q-Q)(Q-Q)图图2022-8-1250散布图散布图2022-8-1251Loess Loess 曲线曲线2022-8-1252图形化的表示基本统计描述图形化的表示基本统计描述n直方图直方图:n盒图盒图:n分位数图分位数图:each value xi is paired with fi indicating that approximately 100 fi%of data a

32、re xi n分位数分位数-分位数图分位数图(q-q):graphs the quantiles of one univariant distribution against the corresponding quantiles of anothern散布图散布图:each pair of values is a pair of coordinates and plotted as points in the planenLoess(local regression)Loess(local regression)曲线曲线:add a smooth curve to a scatter plo

33、t to provide better perception of the pattern of dependence2022-8-1253特征化和比较n什么是概念描述?n数据概化和基于汇总的特征化n分析特征化:分析属性之间的关联性n挖掘类比较:获取不同类之间的不同处n在大型数据库中挖掘描述统计度量n讨论讨论n总结2022-8-1254面向属性的归纳 vs.示例学习方法n原理和基本假设的不同n机器学习：正负样本。n概念描述：只有正样本。n训练样本集的大小n机器学习：训练样本集小n概念描述：训练样本集大。n概化方法的不同n机器学习：按照元组概化n概念描述：按照属性概化2022-8-1255特征化和比较特征化和比较n什么是概念描述?n数据概化和基于汇总的特征化n分析特征化:分析属性之间的关联性n挖掘类比较:获取不同类之间的不同处n在大型数据库中挖掘描述统计度量n讨论n总结