《空间关联规则挖掘.ppt》由会员分享，可在线阅读，更多相关《空间关联规则挖掘.ppt（48页珍藏版）》请在三一办公上搜索。
1、空间关联规则挖掘Spatial Association Rule Mining,高勇北京大学遥感与地理信息系统研究所,关联规则挖掘,频繁模式(frequent pattern)频繁出现在数据集中的模式，如项集、子序列、子结构频繁项集、（频繁）序列模式、（频繁）结构模式关联规则挖掘发现大量数据中项集之间有趣的关联在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、因果结构主要面向事务数据库(transaction-based databases)应用购物篮分析交叉销售和贩卖分析分类设计等,购物篮分析（1）,购物篮在商场中拥有大量的商品（项目），如：牛奶
2、、面包等顾客将所购买的商品放入到自己的购物篮中通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯哪些物品经常被顾客购买？同一次购买中，哪些商品经常会被一起购买？一般顾客的购买过程中是否存在一定的购买时间序列？具体应用：利润最大化商品货架设计：更加适合客户的购物路径货存安排：实现超市的零库存管理用户分类：提供个性化的服务,购物篮分析（2）,购物篮问题的关联规则表示如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示关
3、联规则的两个兴趣度度量支持度(support)、置信度(confidence)支持度和置信度分别是衡量实用性和确定性的指标支持度2%：所有事务（购买记录）中的2%同时购买了计算机和软件置信度60%：意味着购买了计算机的人中，60%也购买了软件,关联规则,给定：项的集合：I=i1,i2,.,in。项的集合称为项集 任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得。每个事务由事务标识符TID标识设A为项集，事务T包含A当且仅当关联规则是如下蕴涵式：其中 并且 规则 在事务集D中成立，并且具有支持度s和置信度cs是事务集合D中包含AB的百分比c是事务集合D中包含A的事务中同时也包含B的
4、百分比关联规则是有趣的，如果它满足最小支持度(min_sup)阈值与最小置信度(min_conf)阈值，并称之为强规则,前提条件结论支持度,置信度,频繁项集,项(item)的集合称为项集(itemset)包含k个项的项集称为k项集项集的出现频率包含项集的事务数目，简称项集的频率、支持度计数、计数概率定义的支持度称为相对支持度，出现频率（或支持度计数）称为绝对支持度频繁项集如果项集I的相对支持度满足预定义的最小支持度阈值（绝对支持度满足最小支持度计数阈值），则I是频繁项集频繁k项集的集合记为Lk置信度可以由支持度导出因此，挖掘关联规则的问题可以归结为挖掘频繁项集,关联规则的示例,A C(50%,
5、66.6%)C A(50%,100%),Min.support=50%Min.confidence=50%,关联规则挖掘的步骤,二个步骤找出所有频繁项集频繁性大于等于预定义的最小支持度计数由频繁项集产生强关联规则满足最小支持度和最小置信度的规则问题如果一个项集是频繁的，则它的每个子集也是频繁的频繁项集个数太大，计算机无法存储和计算闭频繁项集和极大频繁项集如果不存在真超项集Y，使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的项集X是S中的闭频繁项集，如果X在S中是闭的和频繁的项集X是S中的极大频繁项集（或极大项集），如果X是频繁的，并且不存在X的超项集Y在S中是频繁的闭频繁项集包
6、含了频繁项集的完整信息,关联规则挖掘的分类（1）,根据关联规则的类型正关联规则负关联规则：负负，负正，正负根据挖掘的模式的完全性频繁项集的完全集闭频繁项集极大频繁项集被约束的频繁项集：满足用户指定的一组约束的频繁项集近似的频繁项集：只推导被挖掘的频繁项集的近似支持度计数接近匹配的频繁项集:与接近或几乎匹配的项集的支持度相符的项集最频繁的k个项集根据规则集所涉及的抽象层单层关联规则多层关联规则（在不同的抽象层发现关联规则）,关联规则挖掘的分类（2）,根据规则中涉及的数据维单维关联规则(single-dimensional association rule)关联规则中的项或属性只涉及一个维多维关联
7、规则(multidimensional association rule)关联规则涉及两个或多个维根据规则中所处理的值类型布尔关联规则规则考虑的关联是项是否出现量化关联规则规则描述的是量化的项或属性间的关联性,仅涉及buys这个维,关联规则挖掘的分类（3）,根据所挖掘的规则类型关联规则相关规则(correlation rule)对关联规则进一步分析，发现统计相关强梯度联系(strong gradient relationship)梯度：项集与它的父母(泛化的项集)、子女(特殊化的项集)、兄弟(可比较的项集)相比之下的度量比率例如：iphone与ipod销售的关联，都是Apple的产品根据所挖掘
8、的模式类型频繁项集挖掘从事务或关系数据集挖掘频繁项集序列模式挖掘从序列数据集中搜索频繁子序列序列记录了事件的次序结构模式挖掘在结构化数据集中搜索频繁子结构结构：图、格、树、序列、集合、单个项，或这些结构的组合,Apriori算法,Apriori算法(R Agrawal&R Srikant,1994)挖掘布尔关联规则频繁项集的算法是一种逐层搜索的迭代方法：用k项集探求(k+1)项集首先找出频繁1项集，该集合记为L1用L1找出频繁2项集的集合L2如此继续下去，直到找到最大频繁项集Apriori性质频繁项集的所有非空子集也一定是频繁的AB模式不可能比A更频繁的出现Apriori算法是反单调的一个集合
9、如果不能通过测试，则该集合的所有超集也不能通过相同的测试Apriori的性质用于压缩搜索空间，来提高频繁项集逐层产生的效率,Apriori算法的步骤,连接步为了找Lk，通过将Lk-1与自己连接产生候选k项集的集合，该候选k项集记为CkLk-1中的两个项集l1和l2可以执行连接操作 的条件是连接的结果项集是剪枝步Ck是Lk的超集它的成员可能不是频繁的，但是所有频繁的k项集都在Ck中扫描数据库，通过计算每个k项集的支持度，得到Lk 压缩Ck使用Apriori性质，即如果一个k项集的(k-1)子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除,Apriori算法：示例,销售记录表D,最小
10、支持计数：2,由频繁项集产生关联规则,强关联规则满足最小支持度和最小置信度频繁项集满足最小支持度置信度计算关联规则的产生对于每个频繁项集l，产生l的所有非空子集对于l的每个非空子集s，如果则输出规则,由频繁项集产生关联规则：示例,l=I1,I2,I5，其关联规则 confidence=2/4=50%confidence=2/2=100%confidence=2/2=100%confidence=2/6=33%confidence=2/7=29%confidence=2/2=100%如果最小置信度阈值为70%，则强关联规则为,销售记录表D,频繁项集,多层关联规则,数据项中经常会形成概念分层底层的
11、数据项，其支持度往往也较低多层关联规则在多个抽象层上挖掘数据产生的关联规则在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的,挖掘多层关联规则的方法,使用置信度支持度框架，基于概念分层，采用自顶向下策略概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度由概念层1开始，向下到较低的更特定的概念层，在每个概念层累积计数计算频繁项，直到不能再找到频繁项集每一层的关联规则挖掘可以使用Apriori等多种方法搜索策略一致支持度：对于所有层使用一致的最小支持度递减支持度：在较低层使用递减的最小支持度基于分组的支持度：使用基于项或基于分组的最小支持度冗余问题由于项间的“祖先”关系，有些发
12、现的规则将是冗余的规则R1是R2的祖先，如果R1能够通过将R2中的项用它的概念分层的祖先替换得到,多维关联规则,单维关联规则（维内关联规则）包含单个谓词buys(X,“milk”)buys(X,“bread”)多维关联规则涉及两个或多个维或谓词的关联规则维间关联规则(inter-dimensional association rule)具有不重复谓词的多维关联规则age(X,”19-25”)occupation(X,“student”)=buys(X,“coke”)混合维关联规则(hybrid-dimensional association rule)具有重复谓词的多维关联规则age(X,”1
13、9-25”)buys(X,“popcorn”)=buys(X,“coke”)多维关联规则挖掘搜索的不是频繁项集，而是频繁谓词集k谓词集是包含k个合取谓词的集合,多维关联规则挖掘的技术,数据属性分类属性具有有限个不同值，值之间无序量化属性数值类型的值，并且值之间有一个隐含的序多维关联规则挖掘根据量化属性的处理分为2种方法量化属性的静态离散化使用预定义的概念分层对量化属性进行静态地离散化离散化在挖掘之前进行（动态）量化关联规则根据数据的分布，将量化属性离散化或聚类到“箱”离散化的过程是动态的，在挖掘过程中进行，以满足某种挖掘标准,量化属性静态离散化挖掘多维关联规则,量化属性用预定义的概念分层或离散
14、化技术，在挖掘前离散化数值属性的值用区间代替分类属性可以泛化到较高的概念层数据立方体技术非常适合挖掘多维关联规则n维方体的单元用于存放对应n谓词集的计数或支持度0-D方体用于存放任务相关数据的事务总数如果包含感兴趣的维的数据立方体已经存在并物化，挖掘将会很快可以利用Apriori性质频繁谓词集的每个子集也必须是频繁的,挖掘量化关联规则,量化关联规则多维关联规则。其中数值属性根据某种挖掘标准（如最大化置信度），进行动态的离散化2-维量化关联规则：Aquan1 Aquan2 Acat两个量化属性和一个分类属性间的关联例如：age(X,”30-39”)income(X,”42K-48K”)buys(
15、X,”HDTV”)挖掘方法：关联规则聚类系统(ARCS)(1)分箱；(2)找出频繁谓词集；(3)关联规则聚类,强关联规则的问题,下表数据可以得出buys(X,“computer games”)buys(X,“videos”)40%,66%但其实全部人中购买录像带的人数是75%，比66%多事实上录像带和游戏是负相关的。由此可见A B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵的实际强度,由关联挖掘到相关分析,相关规则A B support,confidence,correlation不仅用支持度和置信度度量，而且用A和B之间的相关度量相关度量：提升度(lift)项集A的
16、出现独立于项集B的出现，如果P(AB)=P(A)P(B)；否则作为事件项集A和B是依赖的(dependent)和相关的(correlated)如果lift1，则A和B是正相关的，一个的出现蕴含另一个的出现如果lift=1，则A和B是独立的，没有相关性如果lift1，则A和B是负相关的2度量X的全置信度A和B余弦,0.5，正相关=0.5，独立0.5，负相关,空间规则,空间数据挖掘中的规则(Koperski,1995)空间特征规则(spatial characteristic rule)关于一个空间数据集的一般性描述例：一系列地理区域的天气模式的描述空间判别规则(spatial discrimin
17、ant rule)关于不同类别空间数据之间的特征对比和判别的一般性描述例：两个地理区域的天气模式的比较空间关联规则(spatial association rule)空间数据库中一类空间对象与另一类空间对象之间关联的描述性规则例：加拿大的大部分大城市都位于美国-加拿大边境附近,空间关联规则,空间关联规则的特殊性：空间关系空间关联规则的形式：A B cA and B are sets of predicates,at least one element is a spatial predicates:the support of a pattern A in a set of spatial o
18、bjects Sthe probability that a member of S satisfies pattern Ac:the confidence of AB the probability that pattern B occurs if pattern A occurs例：is_a(X,city)within(X,bc)adjacent_to(X,water)close_to(X,us)92%92%of cities within British Columbia(bc)and adjacent to water are close to U.S.A.associates pre
19、dicates:is_a,within,adjacent_to,close_to spatial predicate:within,adjacent_to,close_to,基于事务的空间关联规则挖掘,特征spatial association rules represents object/predicate relationships containing spatial predicates(Koperski1995)类别事务绑定（Transaction-Bonded）方法利用空间实体之间同时出现的空间信息创建事务，使用基于Apriori的算法进行进行挖掘Reference featur
20、e centric model(Koperski1995)以目标对象为参考，寻找给定目标对象与相关对象组成的空间谓词将空间谓词按照目标对象组织为事务Data partition model(Morimoto 2001)将空间划分为一系列互不相交的区域，将每个区域作为一个事务事务自由（Transaction-Free）方法不直接产生事务邻域窗口处理：遍历所有可能的邻域窗口，用邻域窗口代替事务空间同位规则：co-location,Reference feature centric model方法,空间要素目标要素：target features/objects相关要素：relevant featu
21、res/objects特征事务对应目标要素类(target feature type)的实例目标要素类：e.g.city；实例：e.g.New York项对应谓词每个谓词与目标要素类的非空间属性或与空间谓词相关空间谓词是目标要素类实例与相关要素类(relevant feature type)的实例之间的关系示例 is_a(X,city)intersects(X,highway)GDP(X,10billion)adjacent_to(X,water)80%目标要素类：city相关要素类：highway,water谓词（非空间属性）：is_a,GDP谓词（空间谓词）：intersects,adja
22、cent_to,RFCM定义,给定谓词的集合：F=f1,f2,.,fn，包括非空间属性和空间谓词空间对象集S，是目标要素类和相关要素类的实例的集合每个实例在S中只有一个元组空间关联规则P1,Pm,Q1,QnF是谓词，其中至少有一个是空间谓词谓词集的支持度s(P/S)，P=P1 Pm，S中满足P的对象的概率规则的置信度c(PQ/S)=(PQ/S)/(P/S)，S中满足P的对象满足Q的概率1个谓词称为1-谓词；k个谓词的合取称为k-谓词k-谓词集P在S中是大的(large，即频繁的)，如果(P/S)大于最小支持度k规则PQ/S的置信度在k阶是高的(high)，如果大于最小置信度k规则PQ/S是强的
23、(strong)，如果谓词集PQ大并且PQ/S的置信度高,RFCM挖掘方法,基本策略空间谓词组织成一个粒度由粗到细的层次结构先计算粗粒度的空间谓词，发现较高概念层次的模式与关联规则然后自顶向下细化空间谓词，逐步发现较低概念层次的关联规则步骤计算各个目标空间对象与相关空间对象的空间谓词，将空间谓词组织为一个事务数据库，同一个目标对象的所有谓词构成一个事务在谓词事务数据库中进行单层布尔型关联规则挖掘空间谓词的提取：空间连接(spatial join)目标要素类T，实例t，相关要素集合W，相关要素类O，实例oT=t1,t2,tn,W=O1,Oi,Om,Oi=oi1,oi2,oiq计算每个t与所有o的
24、空间关系概念层次：数据的概念层次，谓词（空间关系）的概念层次空间关联规则挖掘的计算复杂度谓词的数量远小于事务数据库中项的数量，计算复杂度依赖于空间谓词的提取，空间对象的数量，空间对象的表达,RFCM示例(1)目标,数据表：geo为几何字段town(name,type,population,geo,.)road(name,type,geo,.)water(name,type,geo,.)mine(name,type,geo,)boundary(name,type,admin_region_l,admin_region_2,geo,.)挖掘British Columbia中大城市与其他附近的空间对
25、象的关联规则discover spatial association rulesinside British_Columbiafrom road R,water W,mines M,boundary Bin relevance to town Twhere g_close_to(T.geo,X.geo)and X in R,W,M,B and T.type=large and R.type in divided_highway and W.type in sea,ocean,large_lake,large_river and B.admin_region_l in B.C.and B.adm
26、in_region_2 in U.S.A.,RFCM示例(2)数据,空间数据目标要素：town相关要素：road,water,mines,boundary概念层次关系数据的概念层次关系关系的概念层次关系,RFCM示例(3)粗挖掘,(1)数据检索根据需要检索空间数据(2)近似空间关系计算：g_close_to计算(large)town与其他四类地物的g_close_to关系粗分辨率、快速计算MBR、R*-tree或其他近似算法得到空间谓词集计算支持度类Apriori算法：删除小于最小支持度阈值的项，如Mine产生关联规则不同概念层次的,RFCM示例(4)精挖掘,精确计算：基于g_close_to
27、结果表精化空间关系，计算intersect,adjacent_to,close_to,inside等k-谓词计算类Apriori算法：依次计算k-谓词(k=1,n)及其支持度，删除小于阈值的提取关联规则,RFCM示例(5)多层次,提取其他概念层次的关联规则在较低概念层次上，最小支持度和置信度阈值需要降低第2层第3层提取关联规则,基于ILP的空间关联规则挖掘方法,归纳逻辑程序设计(Inductive logic programming,ILP)由机器学习与逻辑程序设计相结合，利用背景知识学习一阶规则给定先验背景知识BK，空间数据库SDB参照对象(reference object)集合S：目标对象
28、集相关对象集Rk，1km，在其上定义空间层次结构每个层次l的最小支持度minsupl和最小置信度minconfl定义SDB归结为归纳数据库DDB，记为D(S)记录参照对象与相关对象的空间关系基于一阶逻辑记录先验知识：空间层次，空间模式和关联规则的约束，领域知识,(Malerba 2001),IPL空间关联规则定义(1),spatial observationD(S)中的元组，ground fact，每个由相应的参照对象sS唯一标识Os|s包含s的属性及其与ri的空间关系Ori|s包含ri的属性及其与sS的空间关系与Os关联的唯一参照对象可用于定义支持度和置信度形式：(RefObj,TaskRe
29、levantObj)is_a断言由BK导出,IPL空间关联规则定义(2),原子与原子集原子(atom)的集合A=a1,a2,al，原子ai为变量或约束表达空间特征的原子由D(S)定义，表达先验知识的原子由BK定义指代参照对象的原子称为关键原子(key atom)关键原子：is_a(X,large_town)空间原子：close_to(X,Y)，intersects(X,Y)，adjacent_to(X,Y)分类原子（知识）：is_a(X,road)，is_a(X,water)，is_a(X,sea)A中原子的合取称为原子集(atomsets)l层的模式语言Ll由A中原子集形式化定义模式模式P由
30、Ll表达为一个量化合取式eqc(P)模式P覆盖Os，如果epc(P)在O(s)BK中为真例：P覆盖ObarlettaP的支持度：(P)=|Op|/|O|O为D(S)中的spatial observation的集合Op为O中由P覆盖的spatial observation的子集,IPL空间关联规则定义(2),IPL空间关联规则的挖掘,精化算子(refinement operator)精化过程产生的模式的支持度逐渐降低非频繁模式P的所有精化(P)都是非频繁的挖掘步骤候选集产生(candidate generation)精化(refinement)对之前产生的频繁模式使用-subsumption精化
31、算子剪枝(pruning)检验候选模式是否-subsume任何非频繁模式，是则剪枝候选集评价(candidate evaluation)检验l层次的支持度，保留频繁模式,基于聚类的空间关联规则挖掘,多变量关联规则挖掘将每个空间属性作为一个图层，点图层对每个图层上的数据点进行聚类针对聚类产生的空间簇（或区域）进行关联规则挖掘垂直视角方法(Vertical-view)&水平视角方法(Horizontal-view)给定位置S，具有n个属性，每个属性对应一个图层对于属性ni，如果S位于图层Li的某个簇（区域中），则ni=1，否则ni=0垂直视角属性立方体(attribute cube)：每个S具有一
32、个属性立方体水平视角图层叠加(overlay)使用交集的面积在结果图层中发现关联规则关联规则形如：layer(1)layer(2)layer(3)(c%),属性图层,垂直视角(属性立方体),水平视角(叠加求交),聚类关联规则挖掘：垂直视角,挖掘方法对每个点数据图层进行空间聚类将所有图层分割为有限大小的规则格网，每个格网生产一个属性立方体建立mn的关系表，记录0,1值m为属性立方体的数目，n为图层的数目minj=1，如果属性立方体mi满足图层nj的特征(位于簇内)对关系表，使用基于事务的关联规则挖掘方法图层（属性）代替项，位置代替事务,聚类关联规则挖掘：水平视角（1）,定义：P为点数据图层，R为
33、实数且0R1P上基于R的簇记为CwR(P)R为聚类半径，RC上一个簇的点数目/P上所有点数目X和Y分别是点图层的集合令X为规则前提(antecedent)，Y为规则结论(consequent)clusters_areas(Xi)是图层Xi上簇多边形的集合clusters_areas(X)是所有clusters_areas(Xi|XiX)的交的多边形面积和聚类支持度(Clustered Support)CS聚类置信度(Clustered Confidence)CC聚类空间关联规则 CSAR,聚类关联规则挖掘：水平视角（2）,挖掘方法对于X和Y中的每个点图层P，计算CwR(P)提取每个CwR的簇的
34、边界计算每个点图层的CwR的多边形面积计算每个多边形图层的多边形面积将X和Y进行叠加运算应用关联规则挖掘算法，发现CSAR,聚类关联规则挖掘：实例,空间频繁模式挖掘 实例1,long,sharable patterns in Trajectories(Gidofalvi 2009),空间频繁模式挖掘 实例2(1),trajectory pattern(Giannotti 2007)a set of individual trajectories that share the property of visiting the same sequence of places with similar travel times.(i)the regions of interest(ii)the typical travel timefrequent T-patternssupportD,N(S,A)sminRegion of Interest(RoI)density-based method,空间频繁模式挖掘 实例2(2),Trajectory pattern miningT-patterns with static RoIcompute RoIs firstthen mine pattrensT-patterns with dynamic RoIfrom to,
