数据挖掘第九章ppt

2006年11月17日星期五DataMining:ConceptsandTechniques1数据挖掘概念与技术——第九章——JiaweiHan（加）著MichelineKamber第九章复杂类型数据的挖掘„复杂数据对象的多维分析和描述性挖掘„空间数据库挖掘„多媒体数据库挖掘„时序数据和序列数据的挖掘„文本数据库挖掘„Web挖掘„小结2006年11月17日星期五DataMining:ConceptsandTechniques3复杂性数据对象的挖掘：结构化数据的概化„集合值属性„将集合中的每一个值概化为其对应的更高级别的概念„导出集合的一般特征，如集合元素的个数，集合中类型或值的区间，或数字数据的加权平均„例如，业余爱好＝{网球，曲棍球，国际象棋，小提琴，任天堂游戏}可以概化为{体育，音乐，电子游戏}„列表值或序列值属性„类似集合值属性，所不同的是概化中要保持元素的次序2006年11月17日星期五DataMining:ConceptsandTechniques4空间和多媒体数据的概化„空间数据:„将一些具体的地理上的点概化为一些聚类区域，如根据土地的用途可概化为商业区，居民区，工业区和农业区等„这种概化需要通过空间操作把一组地理区域加以合并„图象数据:„通过聚集和（/或)近似计算可提取„尺寸，颜色，形状，纹理，方位和图象中所包含对象或区域的相对位置和结构„音乐数据:„其音调的汇总：根据近似计算重复出现的模式片段汇总„其风格的汇总：基于音调，节拍或主要演奏乐器汇总2006年11月17日星期五DataMining:ConceptsandTechniques5对象数据的概化„对象标志符：概化到类/子类层次的类昀低层„类复合层次„概化嵌套结构数据„只概化与当前类有紧密语义关联的对象„对象立方体的构造与挖掘„扩展面向属性的归纳方法„在不同的属性上应用基于类概化操作符序列„概化继续进行，直到结果类中所包含的概化对象数目较少，并且可以汇总为抽象层较高的简练规则„高效的实现„检查每个属性，把它概化到单值数据„构造一个多维数据立方体（对象立方体）„问题：并不总是可以把一组属性值概化为单值数据2006年11月17日星期五DataMining:ConceptsandTechniques6用分而治之法进行规划挖掘的一个例子„规划:行为的一个变量序列„例如:旅行（飞行）：旅行者，出发地点，到达地点，出发时间，到达时间，航班，价格，座位号„规划挖掘：从规划数据库(大型规划集合）中挖掘出重要的或有意义的概化（序列)模式„例如：从飞行数据库中发现旅行模式，或„从汽车修理数据库中的行为序列发现有意义的模式„方法„序列数据上的面向属性的归纳„一个概化旅行规划:small-big*-small„分而治之法：为每个子序列挖掘其特征„E.g.,见书p267，例9.42006年11月17日星期五DataMining:ConceptsandTechniques7规划挖掘的一个旅行数据库„例子：旅行规划数据库的挖掘plan#action#departuredepart_timearrivalarrival_timeairline…11ALB800JFK900TWA…12JFK1000ORD1230UA…13ORD1300LAX1600UA…14LAX1710SAN1800DAL…21SPI900ORD950AA…........................airport_codecitystateregionairport_size…11ALB800…12JFK1000…13ORD1300…14LAX1710…21SPI900…...............旅行规划表机场信息表2006年11月17日星期五DataMining:ConceptsandTechniques8多维分析„策略„按不同的方向概化规划库„找出概化的规划中的序列模式„导出高层规划规划数据库的多维视图2006年11月17日星期五DataMining:ConceptsandTechniques9多维概化Plan#Loc_SeqSize_SeqState_Seq1ALB-JFK-ORD-LAX-SANS-L-L-L-SN-N-I-C-C2SPI-ORD-JFK-SYRS-L-L-SI-I-N-N.........规划库的多维概化Plan#Size_SeqState_SeqRegion_Seq…1S-L+-SN+-I-C+E+-M-P+…2S-L+-SI+-N+M+-E+….........合并规划中连续相同的行为%]75[)()(),(_),(_),,(yregionxregionLysizeairportSxsizeairportyxflight=⇒∧∧2006年11月17日星期五DataMining:ConceptsandTechniques10基于概化的序列挖掘„使用维表按不同的方向概化规划数据库„在每一层使用不同的属性值（基数）来决定概化的正确层（层－“规划”）„使用合并操作符“+”,选择操作符“[]”来进一步概化模式„保留具有重要支持度的模式2006年11月17日星期五DataMining:ConceptsandTechniques11概化序列模式„满足昀小阈值的AirportSize-序列（应用合并操作符后）：S-L+-S[35%],L+-S[30%],S-L+[24.5%],L+[9%]„应用选择操作符后:[S]-L+-[S][98.5%]„大多数时间，人们飞经大机场到达昀终目的地„其它规划:1.5%机会,有其它的模式:S-S,L-S-L2006年11月17日星期五DataMining:ConceptsandTechniques12第九章复杂类型数据的挖掘„复杂数据对象的多维分析和描述性挖掘„空间数据库挖掘„多媒体数据库挖掘„时序数据和序列数据的挖掘„文本数据库挖掘„Web挖掘„小结2006年11月17日星期五DataMining:ConceptsandTechniques13空间数据仓库„空间数据仓库:用来进行数据分析和决策支持的，集成的,面向主题的,时变的和非易失的空间数据库„空间数据集成:一个大问题„特定的结构形式（基于光栅/向量的空间数据，面向对象模型/关系模型，各种各样的空间存储和索引结构，等等）„与特定厂家有关(ESRI,MapInfo,Integraph,等等.)„空间数据立方体:多维空间数据库„维和度量都可以包含空间2006年11月17日星期五DataMining:ConceptsandTechniques14空间数据库中的维和度量„维模型„非空间维„e.g.温度:25-30度概化到热„空间－非空间维„e.g.地区“B.C.”概化描述“westernprovinces”„空间－空间维„e.g.地区“Burnaby”概化到地区“LowerMainland”„度量„数字度量„分布的(e.g.count,sum)„代数的(e.g.average)„整体的(e.g.median,rank)„空间度量„空间指针的集合(e.g.指向七月气温在25－30度所有地区的指针)2006年11月17日星期五DataMining:ConceptsandTechniques15例子:BCweather模式分析„输入„具有散射在B.C中的大约3,000个气候探测器的地图„有关气温，降水，风速等日常数据„所有属性的概念层„输出„显示模式的地图:合并(相似)地区„目标„交互式分析(下钻，切片，切块，转轴，上卷)„快速的响应时间„昀小化使用的时间„挑战„一个合并的区域可能包含成百上千的“原始”地区2006年11月17日星期五DataMining:ConceptsandTechniques16BCWeather空间数据仓库的星型模式„空间数据仓库„维„region_name维„Time维„Temperature维„Precipitation维„度量„region_map„area„countFacttableDimensiontable2006年11月17日星期五DataMining:ConceptsandTechniques17空间合并Ê预计算所有可能的空间合并:太多的存储空间Ê在线合并:太昂贵2006年11月17日星期五DataMining:ConceptsandTechniques18空间数据立方体的计算方法„在线聚集:收集和存储一个空间数据立方体中指向空间对象的指针„昂贵且慢速，需要有效的聚集技术„预计算和存储所有可能的合并„大的空间花销„预计算和存储空间数据立方体的粗略近似„公平的精确性„选择性计算:只物化那些频繁访问的„一个合理的选择2006年11月17日星期五DataMining:ConceptsandTechniques19空间关联分析„空间关联规则:A⇒B[s%,c%]„A和B是空间或非空间谓词集„拓扑关系:intersects（交）,overlaps（重叠）,disjoint（分离）,etc.„空间方位:left_of（左边）,west_of（西部）,under（下面）,等.„距离信息:close_to（临近）,within_distance（远离）,等.„s%表示规则的支持度，c%表示规则的可信度„例子is_a(x,large_town)^intersect(x,highway)→adjacent_to(x,water)[7%,85%]is_a(x,large_town)^adjacent_to(x,georgia_strait)→close_to(x,u.s.a.)[1%,78%]2006年11月17日星期五DataMining:ConceptsandTechniques20逐步求精挖掘空间关联规则„空间关系层次:„g_close_to:near_by,touch,intersect,contain,等„首先搜索粗略关系，接着精化它„挖掘空间关联的两个步骤:„步骤1:粗略空间计算(作为一个过滤器)„使用MBR或R-tree来进行粗略的估计„步骤二:详细的空间算法„只应用到那些经过粗略空间关联测试的对象(不少于昀小支持度)2006年11月17日星期五DataMining:ConceptsandTechniques21„空间分类„分析空间对象导出与特定空间特征有关的分类模式，如地区，高速公路或河流等„例子:根据家庭的平均收入，把一个省的地区按贫富分类„空间趋势分析„根据空间维找出变化趋势„研究非空间或空间数据随空间变化的趋势„例子：观察离海洋越来越远时，气候和植物的变化趋势空间分类和空间趋势分析2006年11月17日星期五DataMining:ConceptsandTechniques22第九章复杂类型数据的挖掘„复杂数据对象的多维分析和描述性挖掘„空间数据库挖掘„多媒体数据库挖掘„时序数据和序列数据的挖掘„文本数据库挖掘„Web挖掘„小结2006年11月17日星期五DataMining:ConceptsandTechniques23多媒体数据的相似性搜索„基于描述的检索系统„在图象描述之上建立标引和执行对象检索,例如,关键字,标题,大小和创建时间„若手工完成很费力„若自动完成检索质量非常差„基于内容的检索系统„支持基于图象内容的检索,如颜色构成,质地,形状,对象和小波变换2006年11月17日星期五DataMining:ConceptsandTechniques24基于内容检索系统中的查询„基于图象样本的查询:„找出所有与给定样本相似的图象„把从样本中提取的特征向量和已经提取出并在图象数据库中已经索引过的图象特征向量比较„图象特征描述查询:„给出图象特征的描绘和概括,如颜色,质地,或形状,把其转化为特征向量„把此向量与数据库中已有的图象特征向量匹配2006年11月17日星期五DataMining:ConceptsandTechnique