模糊邻近关系(FNR)。以空间实例集S中两两实例间的欧氏距离D作为论域D=[0,∞)。模糊邻近关系(FNR)是基于距离D的邻近关系的集合。空间任意两个实例si,sj间的欧氏距离记为d,给定下面映射关系:FNR:D→[0,1],d→µ(si,sj),则称µ确定了D上的一个模糊子集FNR,µ为FNR的隶属函数,µ(si,sj)为距离d对FNR的隶属度,也称邻近度。
空间实例集S中的任意两个实例si和sj的模糊邻近关系FNR表示为:
给定用户自定义距离阈值d1,d2,其中µ(si,sj)定义为:
空间特征A,B,C,D,E的实例分布如图1,给定距离阈值d1=100,d2=300,选取任意两个空间实例A.1和B.1,假设A.1和B.1的欧式距离dist(A.1,B.1)=140,则A.1和B.1的模糊邻近度µ(A.1,B.1)。
图1
图2 二阶到三阶实例变化(>0.1)
FNR的ɑ-截集。给定用户自定义的邻近度阈值α,模糊邻近关系FNR的α-截集FNRα定义为实例si和sj邻近度µ(si,sj)不小于α的FNR的子集,即
其中µ(si,sj)≥α表示为实例si和sj满足α邻近关系,也可表示为µα(si,sj)。
给定邻近度阈值α=0.1,A.1和B.1的邻近为0.8,那么空间实例A.1和B.1满足α邻近关系,即µ0.1(A.1,B.1)。
基于模糊邻近关系的co-location模式c的一个模糊行实例I是空间实例集,即I S。I具备以下特征:(1)在邻近关系下形成团;(2) I包含了模式c中的所有特征;(3)没有任意一个I的子集可以包含c中所有的特征。模式c的模糊行实例记为FR(c),模式c的所有模糊行实例的集合称为模糊表实例,记为FT(c)。
例2,如图1空间实例集{A.1,B.1,C.2}是co-location模式{A,B,C}的一个模糊行实例,模式{A,B,C}的模糊表实例为FT({A,B,C})={{A.1,B.1,C.2},{A.3,B.2,C.3},{A.4,B.4,C.2},{A5,B5,C1}}
模糊星型邻居(FSN)。给定一个空间特征集O,一个度量实例模糊邻近关系的隶属函数,一个邻近度阈值,特征ouO(1≤u≤n),对于任意特征实例,实例的模糊星型邻居定义为它本身和其所有特征类型大于它的模糊邻居以及它们之间的邻近度的集合,即
其中,ou称为中心特征,称为中心实例。
根据图1中空间实例分布及实例间模糊邻近度,可以列出如下表的空间实例集的模糊星型邻居集。
中心
模糊邻居实例
中心
模糊邻居实例
特征
实例
特征
实例
A
A.1
A.1,B.1(0.8),C.2(1)
B
B.1
B.1,C.2(0.8)
A.2
A.2,B.3(0.6),C.3(0.2)
B.2
B.2,C.3(0.8)
A.3
A.3,B.2(0.8),C.3(0.9)
B.3
B.3
A.4
A.4,B.4(0.6),C.2(0.6)
B.4
B.4,C.2(0.6)
A.5
A.5,B.5(0.7),C.1(0.8)
B.5
B.5,C.1(0.25)
A.6
A.6,C.1(0.2)
B.6
B.6,C.1(0.5)
A.7
A.7,C.4(0.9)
B.7
B.7,C.4(0.2)
A.8
A.8,C.5(0.6)
B.8
B.2,C.5(0.9)
A.9
A.9,C.5(0.8)
C
C.1
C.1
C.2
C.2
C.3
C.3
C.4
C.4
C.5
C.5
表1
在表1中空间实例A.1的模糊邻居和邻近度为{A.1,B.1(0.8),C.2(1),D.2(0.7)}。
实例的贡献。实例的贡献是指co-location模式c的模糊行实例FR(c)={s1,s2,…,sm}中某个实例si(1≤u≤n)与模糊行实例中其它实例之间的模糊邻近度之和的平均值,即
例3,图1中co-location模式{A,B,C}的行实例{A.1,B.1,C.2}中实例A.1的贡献为Contri({A.1,B.1,C.2},A.1)=avg((dist(A.1,B.1)),(dist(A.1,C.2)))=(0.8+1)/2=0.9。
模糊参与率(FPR)和模糊参与度(FPI)。给定一个co-location模式c={o1,o2,…,ok},特征ouc(1≤u≤k)的模糊参与率为ou参与在模式c的模糊表实例中不重复参与实例的贡献的平均值之和与ou的实例总数的比值,即
co-location模式c={o1,o2,…,ok}的模糊参与度(FPI)是模式c中所有特征的模糊参与率最小值,即
(7)
图1通过计算特征A,B,C在模式{A,B,C}中的模糊参与率分别为:,,所以模式{A,B,C}的模糊参与度为
模糊损失率(FLR)。给定一个k(k>2)阶频繁co-location模式ck={o1,o2,…,ok}, 的任一k-1阶子模式ck-1={o1,o2,…,ok-1},对ck-1中的任一特征oi(oick-1)(1≤i≤k-1),oi由ck-1到ck的损失率是特征oi参与在ck-1的模糊表实例中不重复参与实例的贡献的平均值之和与oi参与在ck的模糊表实例中不重复参与实例的贡献的平均值之和相减再与oi总实例个数的比率,即oi由ck-1到ck模糊参与率相减
(8)
模糊损失度(FLI)。给定一个k(k>2)阶频繁co-location模式ck={o1,o2,…,ok},ck的一个k-1阶子模式ck-1={o1,o2,…,ok-1},模式ck-1到ck的模糊损失度是ck-1中的特征到ck的损失率的最小值,即
(9)
其中oi是模式ck-1到ck的某一公共特征,FLI(ck-1,ck)计算的是ck-1到ck的所有公共特征从ck-1到ck模糊损失率的最小值。
• 给定>0.1,则特征“A”从{A,B}到{A,B,C}的损失率为:LR({A,B},{A,B,C},A)=(3.5-3.1)/9=0.04,LR({A,B},{A,B,C},B)=(3.5-2.675)/8=0.1,则{A,B}到{A,B,C}的损失度为LI({A,B},{A,B,C})=min(LR({A,B},{A,B,C},A),LR({A,B},{A,B,C},B))=0.04
同样的LI({A,C},{A,B,C})=0.165,LI({B,C},{A,B,C})=0.17
特征影响度(FII)。给定一个k(k>2)阶频繁co-location模式ck={o1,o2,…,ok},特征oi(oick,1≤i≤k),ck的一个k-1阶子模式ck-1(oick-1),则oi在模式ck中的影响度定义为1减模式ck-1到ck模糊损失度,即
(10)
其中oi=ck-ck-1,特征影响度FII(ck,oi)代表了特征oi对频繁模式ck中其它特征的影响,FII(ck,oi)越大,越多ck中的特征实例被特征oi的实例主导。
例6:对于频繁co-location模式{A,B,C},特征A,B,C分别对模式的影响度为:FII({A,B,C},A)=1-LI({B,C},{A,B,C})=1-0.17=0.83,FII({A,B,C},B)=1-LI({A,C},{A,B,C})=1-0.165=0.835,FII({A,B,C},C)=1-LI({A,B},{A,B,C})=1-0.04=0.96
特征影响比(FIR)。给定一个k(k>2)阶频繁co-location模式ck={o1,o2,…,ok},特征oi,oj(oi,ojck)满足FII(ck,oi)≥FII(ck,oj),则oi对oj的影响比定义为1减去两个特征的影响度的比值,即
(11)
特征影响比指数度量了模式中特征间的影响差异,影响比指数FIR(oi,oj)越大,特征oi对特征oj主导性越强。
例7:在图1中,模式{A,B,C}中特征C对特征A的影响比FIR(C,A)=1-0.83/0.96=0.14
主导特征和主导特征模式。给定一个k(k>2)阶频繁co-location模式ck={o1,o2,…,ok}和特征影响比阈值min_fir. 如果特征oick满足以下条件,则oi为主导特征,模式ck为主导特征模式.
• FII(ck,oi)≥FII(ck,oj)
• FIR(oi,omin)≥min_fir (其中omin=argminFIR(ck,oi))
例8:给定特征影响比阈值min_fir=0.1,通过计算模式{A,B,C}是主导特征模式,主导特征为C,可以计算出特征C主导特征A和B的共存。
问题描述. 给定空间特征集合O,空间实例集合S,一个实例集S的模糊邻近关系的隶属度函数,一个邻近度阈值(0≤≤1),一个最小模糊参与度阈值min_fprev和影响比阈值min_fir ,挖掘频繁co-location模式中的所有主导特征及主导特征模式.
挖掘算法.含主导特征的单一邻近度阈值co-location模式挖掘算法(ADFSPTCM)
算法包含如下四个步骤。
步骤(1)采用模糊星型模型物化空间实例集(第1-2行)。根据给定模糊邻近关系的隶属函数,使用网格划分技术,计算空间数据集的模糊邻近关系,获取满足邻近度阈值的模糊邻近对,并生成模糊星型邻居集。
步骤(2)生成2阶频繁co-location模式(第3-6行)。由空间特征集生成2阶候选co-location模式,从模糊邻居对中生成候选模式的表实例,筛选出模糊参与度不小于模糊参与度阈值的频繁co-location模式。
步骤(3)挖掘含有主导特征的co-locaion模式(第8-24行)。对于满足模糊参与度阈值的模式,第12行与该模式的k-1阶子模式集合计算模糊损失度并得到每个特征的特征模糊影响度。第15-19行取出模式中最小特征影响度的特征,并将模式中特征与最小影响度特征fmin的影响度比值大于特征影响比阈值min_fir的特征放入集合DF_set(c )。第20-22行如果DF_set(c)不为空则加入DFCP集合中。
步骤(4)迭代生成高阶co-locaion模式(第7-15行)。循环执行以下过程:①如果k-1(k>2)阶频繁co-location模式集不为空,则由k-1阶频繁co-location模式互相连接生成k阶频繁co-location模式;②从模糊星型邻居集中获取k阶候选模式的模糊星型实例;③对于候选co-location模式的星型实例的团关系进行检验,得到候选co-location模式的模糊表实例;④计算候选模式的模糊参与度,筛选出模糊参与度不小于模糊参与度阈值的co-location模式。
算法 ADFSPTCM
输入:
O: 空间特征集,S: 空间实例集,: 模糊邻近关系的隶属度函数,: 邻近度阈值
min_fprev: 最小模糊参与度阈值,min_fir: 最小特征影响比阈值
变量:
k: co-location模式的阶,FSN: 模糊星型邻居集,Ck: k阶候选co-location模式
FSk: k阶候选模式的模糊星型实例集,FTk: k阶候选co-location模式的模糊表实例,
FPR_c: k阶co-location模式c的模糊参与率集, Pk: k阶频繁co-location模式集,
P: 频繁co-location模式集
输出:
含主导特征的co-location频繁模式集DFCP_set及所有DFCP的主导特征集
步骤:
• FNR = get_fuzzy_neighbor_relationship(S, ); //生成模糊邻近关系
• FSN = get_star_neighbor(O, S, FNR); //生成模糊星型邻居集(满足成团)
• C2 = gen_candidate_co-location(O); //二阶候选co-location模式
• FT2 = get_star_instances(C2, FNR); //二阶模糊表实例
• P2 = select_prevalent_co-locations(C2, FT2, min_fprev); //二阶频繁co-location模式
• P = P∪P2; k=3;
• while(not empty Pk-1) do
• Ck = gen_candidate_colocation(Pk-1);
• for each c∈Ck do
• if calculate FPI(c) ≥ min_fprev do //计算模式参与度
• for each p∈Pk-1(c) and FPR_c do
• FLI(p,c)=calculate_FLI(FPR(p),FPR(c)); //计算模式p到模式c的模糊损失度
• FII_set(c)←{1-FLI(p,c),c-p} //计算模式中所有特征影响度
• end do
• omin=argmin{FII_set(c)}; //计算模式中最小特征影响度
• for each oi∈c do
• if FIR(oi,omin)≥min_fir do
• DF_set(c)←oi ; //将主导特征放入主导特征集中
• end do
• if DF_set(c) ∅ do
• DFCP←{c,DF_set(c)}; //含主导特征的频繁模式集
• end do
• end do
• end do
• FSk = get_star_instances(Ck, FSN);
• FTk = check_clique_instance(Ck, FSk); //检查是否成团
• Pk = select_prevalent_co-location(Ck, FTk, min_fprev); //生成k阶频繁模式
• P= P∪Pk;
• k = k+1;
• end do
算法 ADFSPTCM
输入:
O: 空间特征集,S: 空间实例集,: 模糊邻近关系的隶属度函数,: 邻近度阈值
min_fprev: 最小模糊参与度阈值,min_fir: 最小特征影响比阈值
变量:
k: co-location模式的阶,FSN: 模糊星型邻居集,Ck: k阶候选co-location模式
FSk: k阶候选模式的模糊星型实例集,FTk: k阶候选co-location模式的模糊表实例,
FPR_c: k阶co-location模式c的模糊参与率集, Pk: k阶频繁co-location模式集,
P: 频繁co-location模式集
输出:
含主导特征的co-location频繁模式集DFCP_set及所有DFCP的主导特征集
步骤:
• FNR = get_fuzzy_neighbor_relationship(S, ); //生成模糊邻近关系
• FSN = get_star_neighbor(O, S, FNR); //生成模糊星型邻居集(满足成团)
• C2 = gen_candidate_co-location(O); //二阶候选co-location模式
• FT2 = get_star_instances(C2, FNR); //二阶模糊表实例
• P2 = select_prevalent_co-locations(C2, FT2, min_fprev); //二阶频繁co-location模式
• P = P∪P2; k=3;
• while(not empty Pk-1) do
• Ck = gen_candidate_colocation(Pk-1);
• for each c∈Ck do
• if calculate FPI(c) ≥ min_fprev do //计算模式参与度
• for each p∈Pk-1(c) and FPR_c do
• FLI(p,c)=calculate_FLI(FPR(p),FPR(c)); //计算模式p到模式c的模糊损失度
• FII_set(c)←{1-FLI(p,c),c-p} //计算模式中所有特征影响度
• end do
• omin=argmin{FII_set(c)}; //计算模式中最小特征影响度
• for each oi∈c do
• if FIR(oi,omin)≥min_fir do
• DF_set(c)←oi ; //将主导特征放入主导特征集中
• end do
• if DF_set(c) ∅ do
• DFCP←{c,DF_set(c)}; //含主导特征的频繁模式集
• end do
• end do
• end do
• FSk = get_star_instances(Ck, FSN);
• FTk = check_clique_instance(Ck, FSk); //检查是否成团
• Pk = select_prevalent_co-location(Ck, FTk, min_fprev); //生成k阶频繁模式
• P= P∪Pk;
• k = k+1;
• end do