空间关联规则挖掘

高勇北京大学遥感与地理信息系统研究所v 频繁模式频繁模式(frequent pattern)频繁出现在数据集中的模式，如项集、子序列、子结构 频繁项集、（频繁）序列模式、（频繁）结构模式v 关联规则挖掘关联规则挖掘 发现大量数据中项集之间有趣的关联 在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、因果结构 主要面向事务数据库(transaction-based databases)v 应用应用 购物篮分析 交叉销售和贩卖分析 分类设计等v购物篮购物篮 在商场中拥有大量的商品（项目），如：牛奶、面包等 顾客将所购买的商品放入到自己的购物篮中v通过发现顾客放入购物篮中的不同商品之间的联系，通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯分析顾客的购买习惯 哪些物品经常被顾客购买？同一次购买中，哪些商品经常会被一起购买？一般顾客的购买过程中是否存在一定的购买时间序列？v具体应用：利润最大化具体应用：利润最大化 商品货架设计：更加适合客户的购物路径 货存安排：实现超市的零库存管理 用户分类：提供个性化的服务v 购物篮问题的关联规则表示购物篮问题的关联规则表示 如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示 通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示v 关联规则的两个兴趣度度量关联规则的两个兴趣度度量 支持度(support)、置信度(confidence)支持度和置信度分别是衡量实用性和确定性的指标 支持度2%：所有事务（购买记录）中的2%同时购买了计算机和软件 置信度60%：意味着购买了计算机的人中，60%也购买了软件%60%,2),(),(confidencesupportsoftwareXbuyscomputerXbuysv 给定：给定：项的集合：I=i1,i2,.,in。项的集合称为项集 任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得 。每个事务由事务标识符TID标识 设A为项集，事务T包含A当且仅当v 关联规则是如下蕴涵式：关联规则是如下蕴涵式：其中 并且 规则 在事务集D中成立，并且具有支持度s和置信度c s是事务集合D中包含AB的百分比 c是事务集合D中包含A的事务中同时也包含B的百分比 关联规则是有趣的，如果它满足最小支持度(min_sup)阈值与最小置信度(min_conf)阈值，并称之为强规则IT TA ,csBA IBIA,BABA)()(BAPBAsupport)(/)()|()(APBAPABPBAconfidence前提条件结论 支持度,置信度 v 项项(item)的集合称为项集的集合称为项集(itemset)包含k个项的项集称为k项集v 项集的出现频率项集的出现频率 包含项集的事务数目，简称项集的频率、支持度计数、计数 概率定义的支持度称为相对支持度，出现频率（或支持度计数）称为绝对支持度v 频繁项集频繁项集 如果项集I的相对支持度满足预定义的最小支持度阈值（绝对支持度满足最小支持度计数阈值），则I是频繁项集 频繁k项集的集合记为Lk 置信度可以由支持度导出 因此，挖掘关联规则的问题可以归结为挖掘频繁项集)(_)(_)()()|()(AcountsupportBAcountsupportAsupportBAsupportABPBAconfidenceA C (50%,66.6%)C A (50%,100%)Min.support=50%Min.confidence=50%v 二个步骤二个步骤 找出所有频繁项集 频繁性大于等于预定义的最小支持度计数 由频繁项集产生强关联规则 满足最小支持度和最小置信度的规则v 问题问题 如果一个项集是频繁的，则它的每个子集也是频繁的 频繁项集个数太大，计算机无法存储和计算v 闭频繁项集和极大频繁项集闭频繁项集和极大频繁项集 如果不存在真超项集Y，使得Y与X在S中有相同的支持度计数，则称项集X在数据集S中是闭的 项集X是S中的闭频繁项集，如果X在S中是闭的和频繁的 项集X是S中的极大频繁项集（或极大项集），如果X是频繁的，并且不存在X的超项集Y在S中是频繁的 闭频繁项集包含了频繁项集的完整信息v 根据关联规则的类型根据关联规则的类型 正关联规则 负关联规则：负负，负正，正负v 根据挖掘的模式的完全性根据挖掘的模式的完全性 频繁项集的完全集 闭频繁项集 极大频繁项集 被约束的频繁项集：满足用户指定的一组约束的频繁项集 近似的频繁项集：只推导被挖掘的频繁项集的近似支持度计数 接近匹配的频繁项集:与接近或几乎匹配的项集的支持度相符的项集 最频繁的k个项集v 根据规则集所涉及的抽象层根据规则集所涉及的抽象层v 单层关联规则v 多层关联规则（在不同的抽象层发现关联规则）),(),(printerXbuyscomputerXbuys),(),(printerXbuysputerlaptop comXbuysv 根据规则中涉及的数据维根据规则中涉及的数据维 单维关联规则(single-dimensional association rule)关联规则中的项或属性只涉及一个维 多维关联规则(multidimensional association rule)关联规则涉及两个或多个维v 根据规则中所处理的值类型根据规则中所处理的值类型 布尔关联规则 规则考虑的关联是项是否出现 量化关联规则 规则描述的是量化的项或属性间的关联性),(),(softwareXbuyscomputerXbuys仅涉及buys这个维),()48.42 ,()39.30 ,(computerXbuyskkXincomeXage),(),(HP printerXbuyscomputerXbuys),()48.42 ,()39.30 ,(computerXbuyskkXincomeXagev 根据所挖掘的规则类型根据所挖掘的规则类型 关联规则 相关规则(correlation rule)对关联规则进一步分析，发现统计相关 强梯度联系(strong gradient relationship)梯度：项集与它的父母(泛化的项集)、子女(特殊化的项集)、兄弟(可比较的项集)相比之下的度量比率 例如：iphone与ipod销售的关联，都是Apple的产品v 根据所挖掘的模式类型根据所挖掘的模式类型 频繁项集挖掘 从事务或关系数据集挖掘频繁项集 序列模式挖掘 从序列数据集中搜索频繁子序列 序列记录了事件的次序 结构模式挖掘 在结构化数据集中搜索频繁子结构 结构：图、格、树、序列、集合、单个项，或这些结构的组合v Apriori算法算法(R Agrawal&R Srikant,1994)挖掘布尔关联规则频繁项集的算法 是一种逐层搜索的迭代方法：用k项集探求(k+1)项集 首先找出频繁1项集，该集合记为L1 用L1找出频繁2项集的集合L2 如此继续下去，直到找到最大频繁项集v Apriori性质性质 频繁项集的所有非空子集也一定是频繁的 AB模式不可能比A更频繁的出现 Apriori算法是反单调的 一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试 Apriori的性质用于压缩搜索空间，来提高频繁项集逐层产生的效率v 连接步连接步 为了找Lk，通过将Lk-1与自己连接产生候选k项集的集合，该候选k项集记为Ck Lk-1中的两个项集l1和l2可以执行连接操作 的条件是 连接的结果项集是v 剪枝步剪枝步 Ck是Lk的超集 它的成员可能不是频繁的，但是所有频繁的k项集都在Ck中 扫描数据库，通过计算每个k项集的支持度，得到Lk 压缩Ck 使用Apriori性质，即如果一个k项集的(k-1)子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除21ll)1 1()22(.)22()1 1(21212121klklklklllll)1,1,.,2,1(2111klklll销售记录表D最小支持计数：最小支持计数：2扫描DC1L1C2C2扫描DL2C3C3L3v强关联规则满足最小支持度和最小置信度强关联规则满足最小支持度和最小置信度 频繁项集满足最小支持度 置信度计算v关联规则的产生关联规则的产生 对于每个频繁项集l，产生l的所有非空子集 对于l的每个非空子集s，如果 则输出规则)(_)(_)|()(AcountsupportBAcountsupportBAPBAconfidenceconfscountsupportlcountsupportmin_)(_)(_)(slsvl=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%v如果最小置信度阈值为如果最小置信度阈值为70%，则强关联规则为，则强关联规则为I5I2I1I2I5I1I1I5I2I5I2I1I5I1I2I2I1I5销售记录表D频繁项集I2I5I1I1I5I2I2I1I5v 数据项中经常会形成概念分层数据项中经常会形成概念分层 底层的数据项，其支持度往往也较低v 多层关联规则多层关联规则 在多个抽象层上挖掘数据产生的关联规则 在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的AllcomputeraccessorysoftwarelaptopofficemousecolorprintercomputerdesktopIBMIDEMicrosoftb/wHPSonywristpadLogitechErgowayTIDItemT1IBM D/C,Sony b/wT2Ms.IDE.Sw.,Ms.office.SwT3Logi.mouse,Ergoway wrist padT4IBM D/C,Ms.office.Sw.T5IBM D/Cv 使用置信度支持度框架，基于概念分层，采用自顶向下策略使用置信度支持度框架，基于概念分层，采用自顶向下策略 概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度 由概念层1开始，向下到较低的更特定的概念层，在每个概念层累积计数计算频繁项，直到不能再找到频繁项集 每一层的关联规则挖掘可以使用Apriori等多种方法v 搜索策略搜索策略 一致支持度：对于所有层使用一致的最小支持度 递减支持度：在较低层使用递减的最小支持度 基于分组的支持度：使用基于项或基于分组的最小支持度v 冗余问题冗余问题 由于项间的“祖先”关系，有些发现的规则将是冗余的 规则R1是R2的祖先，如果R1能够通过将R2中的项用它的概念分层的祖先替换得到v 单维关联规则（维内关联规则）单维关联规则（维内关联规则）包含单个谓词 buys(X,“milk”)buys(X,“bread”)v 多维关联规则多维关联规则 涉及两个或多个维或谓词的关联规则 维间关联规则(inter-dimensional association rule)具有不重复谓词的多维关联规则 age(X,”19-25”)occupation(X,“student”)=buys(X,“coke”)混合维关联规则(hybrid-dimensional association rule)具有重复谓词的多维关联规则 age(X,”19-25”)buys(X,“popcorn”)=buys(X,“coke”)v 多维关联规则挖掘多维关联规则挖掘 搜索的不是频繁项集，而是频繁谓词集 k谓词集是包含k个合取谓词的集合v 数据属性数据属性 分类属性 具有有限个不同值，值之间无序 量化属性 数值类型的值，并且值之间有一个隐含的序v 多维关联规则挖掘根据量化属性的处理分为多维关联规则挖掘根据量化属性的处理分为2种方法种方法 量化属性的静态离散化 使用预定义的概念分层对量化属性进行静态地离散化 离散化在挖掘之前进行（动态）量化关联规则 根据数据的分布，将量化属性离散化或聚类到“箱”离散化的过程是动态的，在挖掘过程中进行，以满足某种挖掘标准v 量化属性用预定义的概念分层或离散化技术，在挖掘前离散化量化属性用预定义的概念分层或离散化技术，在挖掘前离散化 数值属性的值用区间代替 分类属性可以泛化到较高的概念层v 数据立方体技术非常适合挖掘多维关联规则数据立方体技术非常适合挖掘多维关联规则 n维方体的单元用于存放对应n谓词集的计数或支持度 0-D方体用于存放任务相关数据的事务总数 如果包含感兴趣的维的数据立方体已经存在并物化，挖掘将会很快 可以利用Apriori性质 频繁谓词集的每个子集也必须是频繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)v 量化关联规则量化关联规则 多维关联规则。其中数值属性根据某种挖掘标准（如最大化置信度），进行动态的离散化v 2-维量化关联规则：维量化关联规则：Aquan1 Aquan2 Acat 两个量化属性和一个分类属性间的关联 例如：age(X,”30-39”)income(X,”42K-48K”)buys(X,”HDTV”)挖掘方法：关联规则聚类系统(ARCS)(1)分箱；(2)找出频繁谓词集；(3)关联规则聚类),()40.31,()34,(HDTVXbuysKKXincomeXage),()40.31,()35,(HDTVXbuysKKXincomeXage),()50.41,()34,(HDTVXbuysKKXincomeXage),()50.41,()35,(HDTVXbuysKKXincomeXage),()50.31,()35.34,(HDTVXbuysKKXincomeXagev 下表数据可以得出下表数据可以得出 buys(X,“computer games”)buys(X,“videos”)40%,66%v 但其实全部人中购买录像带的人数是但其实全部人中购买录像带的人数是75%，比，比66%多多v 事实上录像带和游戏是负相关的。事实上录像带和游戏是负相关的。v 由此可见由此可见A B的置信度有欺骗性，它只是给出的置信度有欺骗性，它只是给出A,B条件概率的条件概率的估计，而不度量估计，而不度量A,B间蕴涵的实际强度间蕴涵的实际强度买游戏买游戏不买游戏不买游戏合计合计买录像买录像400035007500不买录像不买录像20005002500合计合计6000400010000v 相关规则相关规则 A B support,confidence,correlation 不仅用支持度和置信度度量，而且用A和B之间的相关度量 相关度量：提升度(lift)项集A的出现独立于项集B的出现，如果P(AB)=P(A)P(B)；否则作为事件项集A和B是依赖的(dependent)和相关的(correlated)如果lift1，则A和B是正相关的，一个的出现蕴含另一个的出现 如果lift=1，则A和B是独立的，没有相关性 如果lift0.5，正相关=0.5，独立10billion)adjacent_to(X,water)80%目标要素类：city 相关要素类：highway,water 谓词（非空间属性）：is_a,GDP 谓词（空间谓词）：intersects,adjacent_tov 给定给定 谓词的集合：F=f1,f2,.,fn，包括非空间属性和空间谓词 空间对象集S，是目标要素类和相关要素类的实例的集合 每个实例在S中只有一个元组v 空间关联规则空间关联规则 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是强的(strong)，如果谓词集PQ大并且PQ/S的置信度高%)(.11cQQPPnmv 基本策略基本策略 空间谓词组织成一个粒度由粗到细的层次结构 先计算粗粒度的空间谓词，发现较高概念层次的模式与关联规则 然后自顶向下细化空间谓词，逐步发现较低概念层次的关联规则v 步骤步骤 计算各个目标空间对象与相关空间对象的空间谓词，将空间谓词组织为一个事务数据库，同一个目标对象的所有谓词构成一个事务 在谓词事务数据库中进行单层布尔型关联规则挖掘v 空间谓词的提取：空间连接空间谓词的提取：空间连接(spatial join)目标要素类T，实例t，相关要素集合W，相关要素类O，实例o T=t1,t2,tn,W=O1,Oi,Om,Oi=oi1,oi2,oiq 计算每个t与所有o的空间关系 概念层次：数据的概念层次，谓词（空间关系）的概念层次v 空间关联规则挖掘的计算复杂度空间关联规则挖掘的计算复杂度 谓词的数量远小于事务数据库中项的数量，计算复杂度依赖于 空间谓词的提取，空间对象的数量，空间对象的表达v 数据表：数据表：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,.)v 挖掘挖掘British Columbia中大城市与其他附近的空间对象的关联规则中大城市与其他附近的空间对象的关联规则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.admin_region_2 in U.S.A.v 空间数据空间数据 目标要素：town 相关要素：road,water,mines,boundaryv 概念层次关系概念层次关系 数据的概念层次关系 关系的概念层次关系v(1)数据检索数据检索 根据需要检索空间数据v(2)近似空间关系计算：近似空间关系计算：g_close_to 计算(large)town与其他四类地物的g_close_to关系 粗分辨率、快速计算 MBR、R*-tree或其他近似算法 得到空间谓词集 计算支持度 类Apriori算法：删除小于最小支持度阈值的项，如Mine 产生关联规则 不同概念层次的v 精确计算：基于精确计算：基于g_close_to结果表结果表 精化空间关系，计算intersect,adjacent_to,close_to,inside等 k-谓词计算 类Apriori算法：依次计算k-谓词(k=1,n)及其支持度，删除小于阈值的 提取关联规则v 提取其他概念层次的关联规则提取其他概念层次的关联规则 在较低概念层次上，最小支持度和置信度阈值需要降低 第2层 第3层 提取关联规则v 归纳逻辑程序设计归纳逻辑程序设计(Inductive logic programming,ILP)由机器学习与逻辑程序设计相结合，利用背景知识学习一阶规则v 给定给定 先验背景知识BK，空间数据库SDB 参照对象(reference object)集合S：目标对象集 相关对象集Rk，1km，在其上定义空间层次结构 每个层次l的最小支持度minsupl和最小置信度minconflv 定义定义 SDB归结为归纳数据库DDB，记为D(S)记录参照对象与相关对象的空间关系 基于一阶逻辑记录先验知识：空间层次，空间模式和关联规则的约束，领域知识(Malerba 2001)v spatial observation D(S)中的元组，ground fact，每个由相应的参照对象sS唯一标识 Os|s包含s的属性及其与ri的空间关系 Ori|s包含ri的属性及其与sS的空间关系 与Os关联的唯一参照对象可用于定义支持度和置信度 形式：(RefObj,TaskRelevantObj)is_a断言由BK导出v 原子与原子集原子与原子集 原子(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中原子集形式化定义v 模式模式 模式P由Ll表达为一个量化合取式eqc(P)模式P覆盖Os，如果epc(P)在O(s)BK中为真 例：P覆盖Obarletta P的支持度：(P)=|Op|/|O|O为D(S)中的spatial observation的集合 Op为O中由P覆盖的spatial observation的子集vv 精化算子精化算子(refinement operator)精化过程产生的模式的支持度逐渐降低 非频繁模式P的所有精化(P)都是非频繁的v 挖掘步骤挖掘步骤 候选集产生(candidate generation)精化(refinement)对之前产生的频繁模式使用-subsumption精化算子 剪枝(pruning)检验候选模式是否-subsume任何非频繁模式，是则剪枝 候选集评价(candidate evaluation)检验l层次的支持度，保留频繁模式v 多变量关联规则挖掘多变量关联规则挖掘 将每个空间属性作为一个图层，点图层 对每个图层上的数据点进行聚类 针对聚类产生的空间簇（或区域）进行关联规则挖掘v 垂直视角方法垂直视角方法(Vertical-view)&水平视角方法水平视角方法(Horizontal-view)给定位置S，具有n个属性，每个属性对应一个图层 对于属性ni，如果S位于图层Li的某个簇（区域中），则ni=1，否则ni=0 垂直视角 属性立方体(attribute cube)：每个S具有一个属性立方体 水平视角 图层叠加(overlay)使用交集的面积在结果图层中发现关联规则v 关联规则关联规则 形如：layer(1)layer(2)layer(3)(c%)属性图层垂直视角(属性立方体)水平视角(叠加求交)v 挖掘方法挖掘方法 对每个点数据图层进行空间聚类 将所有图层分割为有限大小的规则格网，每个格网生产一个属性立方体 建立mn的关系表，记录0,1值 m为属性立方体的数目，n为图层的数目 minj=1，如果属性立方体mi满足图层nj的特征(位于簇内)对关系表，使用基于事务的关联规则挖掘方法 图层（属性）代替项，位置代替事务v 定义：定义：P为点数据图层，R为实数且0R1 P上基于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 聚类空间关联规则 CSARv 挖掘方法挖掘方法 对于X和Y中的每个点图层P，计算CwR(P)提取每个CwR的簇的边界 计算每个点图层的CwR的多边形面积 计算每个多边形图层的多边形面积 将X和Y进行叠加运算 应用关联规则挖掘算法，发现CSARv long,sharable patterns in Trajectories(Gidofalvi 2009)vtrajectory 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 time frequent T-patterns supportD,N(S,A)smin Region of Interest(RoI)density-based methodvTrajectory pattern mining T-patterns with static RoI compute RoIs first then mine pattrens T-patterns with dynamic RoI from to