16时空异常扫描和关联规则挖掘

时空异常扫描关联规则挖掘2014.4.21《GIS空间分析方法》第十六讲本讲的主要内容时空异常扫描关联规则挖掘1.空间异常扫描SpatialScanStatistic任务：使用扫描统计方法在空间点集中发现聚类(如发现疾病发生的空间聚集区域)。主要研究内容：二项分布的概率表达式扫描窗口(ScanWindow)的形状和大小的定义及空间扫描的过程目标函数乳腺癌的实例不规则异常区域的识别空间扫描二项分布的概率•掷一枚硬币，独立掷5次，求2次正面朝上的概率。cnccnppCP)1()(32252121CP其中，c为朝上的次数，n为掷硬币的次数，p为硬币朝上的概率。•假设：存在两个二项分布模式（其一为病例高发区；其二为背景）。•目标函数的建立：求在概率最大的情况下，两个二项式分布的空间区域。空间异常区域空间二项式似然函数)()()()()!()]!()[()!(!)!(!cCnNcCcncnNcCnNnNcCcCcCnNnNncnncccnnL)()()()()()(~)()(!)!(!cCnNcCcnccCnNcCcncnNcCnNnNcCncnncLnNcCnNnNcCncnncCCNNL其中，c为异常区内的case,n为异常区内的总pop.,C为整个区域的case,N为整个区域的pop.BreastCancerMortalityNortheasternUnitedStatesStates:Maine,N.H.,Vermont,Mass.,R.I.,Connecticut,N.Y.,N.J.,Pennsylvania,Delaware,Maryland,D.C.Years:1988-1992Deaths:58,943Population:29,535,210GeographicalAggregation:245countiesAuthor:MKulldorff,EFeuer,BMiller,LFreedmanNCI-NationalCancerInstitute采用SatScan软件()。BreastCancerMortality假定每个县内死亡数符合泊松分布假设：不同年龄段，各县死亡风险相同（区域内经年龄调整的死亡率为常数）圆形窗口平移圆心在县重心，半径依次增大，覆盖面积不超过一半人口最大似然Breastcancermortalityp=0.0001BreastcancermortalityMostlikelyclusterMostLikelyClustersLocationObsExpRRLLRpNY/Philadelphia24,04423,0401.07435.70.001Buffalo1,4161,2801.1097.10.12WashingtonDC7126181.1546.90.15Boston5,9665,7261.0475.50.40EasternMaine2672291.1663.00.99RRRiskratio,Relativeratio相对危险度Log-likelihoodratio(LLR)极大似然估计值优点Spatialscanstatistic14可调整任意混杂因素不需要预定聚类的大小和位置，减少预选偏差基于似然法的统计检验返回检验p值原有假设被拒绝时，可确定出引起拒绝的聚类的位置不规则空间异常区域00.20.40.60.8100.20.40.60.8100.20.40.60.8100.20.40.60.8100.20.40.60.8100.20.40.60.8100.20.40.60.8100.20.40.60.81SatScan的结果原始数据ABCDEFGHIGKIMNOPQRS背景信息A(0.4)B(0.1)C(0.1)D(0.4)E(0.1)F(0.4)G(0.15)H(0.1)I(0.1)G(0.4)K(0.1)I(0.4)M(0.1)N(0.1)O(0.1)P(0.4)Q(0.15)R(0.1)S(0.1)异常区域最优路径属性信息空间点蚁群算法节点网络基于蚁群算法的异常区域识别方法PeiT,etal.2011.Detectingarbitrarilyshapedclustersusingantcolonyoptimization.InternationalJournalofGeographicalInformationScience,DOI:10.1080/13658816.2010.533674.()18食物源蚁穴A侧B侧食物源蚁穴A侧B侧路径构建•随机比例规则：对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率为：,0)(,)(),()],([)],([)],([)],([ikjiqjikJuiuijijipJkμβαβαητητ信息素更新11(,)(1)(,)(,),(,)(,)0,()其他mkkkkijijijijkijRCm是蚂蚁个数；ρ是信息素的蒸发率，规定0ρ≤1，通常设置为ρ=0.5；是第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数；Ck表示路径长度，它是Rk中所有边的长度和。),(jikτ原始数据(1973-1975)(来源:肿瘤研究所)SAScan结果AntScan2.0结果研究实例－华北地区食管癌高发区的识别2空间关联规则挖掘•关联规则及概念•什么是空间关联规则•基于配置的关联规则挖掘2.1关联•事件A的发生和事件B的发生存在一致性•一致性的含义（同时、同地、先后、方位…）“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。关联规则挖掘基本概念可信度（confidence）在事务集W中，如果支持数据项集A的事务中有c%也同时支持数据项集B，则c%称为关联规则A－B的可信度。购买面包的顾客中有70％的人也购买了黄油，因此购买黄油和面包的关联规则可信度为70％。支持度（support）如果事务集W中有s%的事务同时支持数据项集A和B，则s%称为关联规则的支持度。如果某天共有1000个顾客去商场购物，其中有100个顾客同时购买了面包和黄油，那么上述的关联规则的支持度就是10％。从关系数据库中挖掘规则数据库1维项集数据库2维项集数据库三维项集数据库1维项集支持度2维项集支持度3维项集支持度BCDF{A}2{AB}1{ACE}2ACE{B}4{AC}2{ABC}1BE{C}4{AD}0{ACD}0BCDE{D}2{AE}2{ABE}1ABCE{E}4{BC}3{BDE}1{F}1{BD}2{BCD}2{BE}3{BCE}2{CD}2{CE}3{DE}1挖掘单维布尔关联规则Apriori算法是根据有关频繁项集性质的先验知识而命名的。该算法使用一种逐层搜索的迭代方法，利用k-项集探索(k+1)-项集。具体做法：首先找出频繁1-项集的集合，记为L1；再用L1找频繁2-项集的集合L2；再用L2找L3…如此下去，直到不能找到频繁k-项集为止。找每个Lk需要一次数据库扫描。26Apriori算法25Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2MaximalvsClosedItemsetsFrequentItemsetsClosedFrequentItemsetsMaximalFrequentItemsets2.2什么是空间关联规则•事件之间的一致性为空间关系2.3时空配置关联规则挖掘解决问题：多变量之间的复杂时空规则(难以用函数表达的关系)创新点：包含多种不同性质的空间变量属性之中包含空间配置、相关信息同时考虑“时间”和“空间”的信息洄游方向洄游方向温锋（蓝色）与渔场（红色）形成的空间位置关系示意图空间配置关联规则挖掘渔场与温锋之间空间关系难以定量刻画空间化示意图栅格的空间示意图邻域取值点特定渔区图例T1TaT9TbTdTcTeTfTgT2T1T3T5T4T6T7T8北周次T1T6T7TbTaTgTg-T1WC880111.514.214.11715.1186.50890111.711.212.112.311.313.82.14170900113.314121514.7162.7127591011313.11313.814.8152.02650920114.213.713.714.314.615.21093011313.912.914141741112940112.314.8151413.417.14.8740950112.512.712.3131416.43.90960112.712.611.613.513.114.61.90970111.51313.913.911.716.550空间数据—关系数据库•对温度值离散化：A:~12.9；B:13.0~15.0；C:15.1~•对平均网产离散化：有：WC500箱/网；无：WC=500箱/网（箱=20公斤）•Tg-T1值离散化：Y:Tg-T1=2;N:Tg-T12关系数据库—离散化weekT1T6T7TbTaTgTg-t1WC8801ABBCCCY无8901AAAAABY有9001BBABBCY有9101BBBBBBY有9201BBBBBCN无9301BBABBCY有9401ABBBBCY有9501AAABBCN无9601AAABBBY无9701ABBBABY无离散关系数据库(ta，b)∧(t6，b)∧（tg-t1，Y)→(渔场，有)可信度80％，支持度40％。是否形成渔场取决于左边的温度以及东南与西北的温差。该渔区要形成渔场的条件是：左边两角的温度处于13℃—15℃间且东南与西北温差大于2℃，则形成渔场。WC依赖于{ta，t6，tg-t1}，也就是空间配置{ta，t6，tg-t1}决定{WC}关联规则提取结果思考问题•空间异常扫描目标函数的及扫描原理。•空间关联规则挖掘的基本概念及关联规则聚合原理。•StaTScan•裴韬主页=446&v=140资料