流数据上的时空共现模式发现及应用

时空共现模式在流数据上的发现汇报人：霍江涛2013年3月22日概要背景知识相关工作研究工作总结和展望背景知识时空共现模式定义R(A,B)<Ð共现率ρA:NxB:NyÑ=0.5(A,B)=(x,y)ρ:Min(x/Nx,y/Ny)ρ>=0.5时空共现模式属性ABC(23-1)(A,B,C,AB,AC,BC,ABC)ABCD(24-1)(A,B,C,D,AB,AC,BC…,BCD,ABCD)(ABCDE)(25-1)…(ABCDEFGHIJ)(210-1)类别N----时间复杂度O(2N-1)研究动机时空共现模式在社会诸多领域有着应用广泛查询建议朋友推荐服务推荐科学,生态学,医药卫生,….目前的研究集中于静态的数据集不能有效的反应出时空共现模式中的变化趋势不能反应当前模式与先前模式之间的关系相关工作空间共现模式发现时空共现模式发现基于时间序列的模式发现与匹配相关工作空间共现模式发现相关工作时空共现模式发现时空阈值(θs,θt)单次时间：多次时间：相关工作基于时间序列的模式发现与匹配模式发现模式匹配研究工作基于流数据新的参与度计算方法渐增交叉性时空共现模式发现共现模式随时间演化的趋势发现权重：W(A)=（A在相关共现事件参与次数）哈希树：存储每次共现事件类型。哈希表：存储与每个类型事件共现的其他事件。ABCDEF…..111111处理流程Input:(t0)A1 1.6 1.6A2 1.3 1.6A3 2.6 2.5A4 2.7 0.2A5 2.8 0.7B1 1.8 1.8B2 1.7 1.4B3 1.3 1.3B4 1.6 1.1B5 0.5 0.5B6 0.3 0.2B7 2.5 2.7C1 1.5 0.9C2 1.8 0.9C3 0.25 0.4………交叉性时空共现模式发现度量要点决定需要处理的网格决定需要处理的事件将交叉性共现事件映射到下一个时间片冲突解决处理网格假设在一个网格中共有k种事件，每种事件的数量为Ni(1<=i<=k)一个网格中所有事件总数为：Sum(objects)=N1+N2+…..+Nk假设我们一共有M个网格，那么每个网格的平均事件数为：

P=Sum(objects)/M需要处理的网格阈值为:θ=λ1P(λ1=0.8)需要处理的事件数量阈值为:Ni>λ2Sum(objects)冲突处理映射相关网格包含有相同数据集忽略事件ID，直接映射映射网格中相关类型事件数量达到一定比例：当Ñi>λ3Sum(objects)/k（λ3=2），不再映射进新网格当前时空共现模式时间序列:t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10...定义衰减因子λ各时间片内共现模式t0:(A,B)-(X0AB,Y0AB),(A,C)-(X0AC,Y0AC)…(N0A,N0B,N0C)t1:(A,B)-(X1AB,Y1AB),(A,C)-(X1AC,Y1AC)…(N1A,N1B,N1C)….整合入历史数据后的共现模式t10:(A,B)-(X10AB,Y10AB),(A,C)-(X10AC,Y10AC)…(N10A,N10B,N10C)T(A,B)=(XAB,YAB)-----(NA,NB)XAB=X10AB+λX9AB+λ2X8AB+…..+λ10X0AB

YAB=Y10AB+λY9AB+λ2Y8AB+…..+λ10Y0AB

NA=N10A+λN9A+λ2N8A+….+λ10N0A

NB=N10B+λN9B+λ2N8B+….+λ10N0B共现率T(A,B):min(XAB/NA,YAB/NB)最终共现模式的正确性共现率T(A,B):min(XAB/NA,YAB/NB)，阈值为μXAB/NA=(X10AB+λX9AB+…..+λ10X0AB)/(N10A+λN9A

….+λ10N0A

)在上式中有，(1)X10AB/N10A>(μN10A)/N10A

…X0AB/N0A>(μN0A)/N0A

(2)N0A/N10A=α0，N1A/N10A=α1，N2A/N10A=α2，…..，N9A/N10A=α9(3)XAB/NA

=(X10AB+λX9AB+…..+λ10X0AB)/(N10A+λN9A

….+λ10N0A

)=(X10AB+λX9AB+…..+λ10X0AB)/(N10A+λα9N10+λ2

α8N10+…+λ10α10N10)>(μN10A+λμ

α9N10+…+λ10μα10N10)/(N10A+λα9N10+λ2

α8N10+…+λ10α10N10)=μ(N10A+λα9N10+λ2

α8N10+…+λ10α10N10)/(N10A+λα9N10+λ2

α8N10+…+λ10α10N10)=μ同理，可知,B亦满足以上规律。综上所述，最终共现模式依然满足共现条件。简化XAB/NA=(X10AB+λX9AB+…..+λ10X0AB)/(N10A+λN9A

….+λ10N0A

)简化的模式共现发现，最终共现模式为TK(A,B)T0(A,B):(X0,Y0)-(M0A,M0B)，有(X0,Y0)=(X0AB,Y0AB),(M0A,M0B)=(N0A,N0B)则T1(A,B):(X1,Y1)-(M1A,M1B),t1(A,B)=(X1AB,Y1AB)---(N1A,N1B)有X1/M1A=(X1AB+λX0AB)/(N1A+λN0A)=(X1AB+λX0)/(N1A+λM0)T2(A,B):(X2,Y2)-(M2A,M2B),t2(A,B)=(X2AB,Y2AB)---(N2A,N2B)有X2/MOA=(X2AB+λX1AB+λ2X0AB)/(N2A+λN1A+λ2N0A) =(X2AB+λ(X1AB+λX0AB))/(N2A+λ(N1A+2N0A)) =(X2AB+λX1)/(N2A+λM1)因此，最终共现模式TK(A,B)=(XK,YK)-(MKA,MKB)等价于(XkAB+λXk-1,YKAB+λYK-1)—(NKA+λMk-1A,NKB+λMk-1B)综上，在计算当前共现模式的时候，可以直接采用上次时间片中的最终共现模式，而不必处理更早的共现模式。重要性序列ABCDEF…(B)(5/8)(C)(12/15)(B,C)(4/8,9/15)。。。。。。。。。。。。S(AB)=5*2+4*3+•••S(AC)=12*2+9*3+•••A(CB…..)。。。。。。BC