0 引言

空间co-location模式是指一组空间对象的子集，其实例频繁地关联^[1]。例如，鲜红斑痣通常与胎儿发育不良有关；植物学家们发现生石花有90%会长在岩床缝隙、石砾之中^[2-4]。现实世界中，模糊对象无处不在，比如“红色的枣子”“高个子的人”“蓝色的天空”等，对模糊对象的空间co-location模式挖掘就是发现一系列在空间上频繁并置的模糊对象特征集^[1]。

目前，许多学者对空间co-location模式挖掘进行了深入研究并提出大量算法。例如，针对确定数据，Shekhar等^[2]提出一种用户指定的社区概念以及挖掘频繁模式的空间坐标模式；Huang等^[3-4]根据无支持阈值的可信co-location规则挖掘方法，提出了最大参与度系数以及join_based算法，采用邻域和参与系数进行co-location模式挖掘；Yoo等^[5-6]改进了join_based算法，分别提出partial_join算法^[5]和join_less算法^[6]，在不丢失co-location实例的同时有效降低了挖掘的时间代价。针对不确定数据，陆叶等^[7]提出了不确定数据集上的Ujoin_based算法；Zheng等^[8]研究了模糊对象的K最近邻(K-Nearest Neighbor, KNN)查找问题，提出了AKNN(Ad Hoc KNN)和RKNN(Range KNN)方法；Wang等^[9]研究了从区间数据表示的不确定对象中挖掘co-location模式。针对模糊对象的研究也越来越多，欧阳志平等^[10]改进了join_based算法，提出了关于模糊对象空间co-location模式挖掘的剪枝对象-减少实例间连接-优化剪枝步(PO_RI_PC)算法，后续又研究了实例位置模糊的空间co-location模式挖掘方法^[10]；Qian等^[11]研究了基于kNNG(k-Nearest Neighbor Graph)方法的区域co-location模式挖掘方法；温佛生等^[12]提出了基于模糊对象的极大co-location挖掘算法等。

虽然空间co-location模式挖掘算法很多，但针对不均匀模糊对象的研究并不多见。而在许多涉及数据分类的应用中，如医疗诊断、文本分类、天气预报等，经常会遇到数据集分布不均匀的情况^[13-15]。上述研究均未考虑不均匀分布模糊对象的空间频繁并置现象，将空间数据集看作是均匀的，如PO_RI_PC算法^[1]等，利用单一的距离参数进行空间数据的挖掘。如图 1所示，数据集大致均匀分布，使用一个恰当的距离参数即可挖掘出空间co-location模式^[1]。

但在实际情况中，常出现如图 2所示的不均匀分布点集，选择不同的距离参数会挖掘出不同的空间co-location模式。图 2为选择距离参数1挖掘出的co-location模式，若使用距离参数2挖掘出的结果会更加准确。显然，不适当的距离参数会导致co-location模式的遗漏，进而使整个co-location模式的挖掘结果不准确。

为避免这种情况的出现，与针对均匀分布模糊对象的挖掘算法PO_RI_PC对比，本文提出一种分层次的空间数据模式挖掘方法，以实现对不均匀分布模糊对象的co-location模式挖掘。

1 相关问题及定义

本文对模糊对象的处理源于模糊集理论，将模糊逻辑引入数据挖掘分类系统，允许定义“模糊”域值或边界。模糊逻辑使用0.0和1.0之间的数值表示一个实例属于某个类别的可能性，而不是采用类或集合的精确判断^[16]。模糊逻辑提供了在高抽象层处理的便利。

以下对模糊对象、邻域关系图、距离变化系数、区域量级、不均匀度以及距离参数进行定义。

定义1   模糊对象^[1]。本文中的模糊对象，表示为一个空间中离散点的集合，定义如下：A={〈a, u(a)〉| 0 < u(a) < 1}，其中A表示模糊对象，a表示实例，u(a)表示实例a属于模糊对象A的隶属度。如图 3所示，实例a₁、a₂和a₃对模糊对象A的隶属度分别为0.23、0.01和0.45。

从图 3可以看出，a₂隶属于A的可能性非常低，对于这样的实例，在挖掘co-location模式时可以将其排除，因为这样的实例对研究问题的帮助不大。例如厨具分类问题，假设锅勺对它的隶属度为0.8，擀面杖对它的隶属度为0.02，由于擀面杖的隶属度非常小，对于研究对象的贡献不大，可以将其排除。实验时可通过最小模糊度参数将隶属度小的实例排除。

定义2   邻域关系图^[11]。邻域关系图由顶点和连接顶点之间的边构成，如图 4所示，每个顶点代表一个模糊空间实例，边用来连接属于不同对象的两个实例，每条边上的权值为两个模糊空间实例之间的欧氏距离。可以表示如下：

$ G = \left\langle {V,E,W} \right\rangle $

(1)

其中:G代表邻域关系图，V代表顶点集合，E代表边的集合，W代表权值的集合。

本文通过寻找距离邻域关系图最近的区域，不断扩大邻域关系图的范围，基于距离变化系数，确定预融合在一起的区域是否具有均匀性和连续性。

定义3  距离变化系数。距离变化系数是区域内数据点保持均匀性和连续性所必需的界定值，定义为区域内边权值的标准差与边权值平均数的比值，可记为dvc(distance variation coefficient)，计算公式如式(2)所示：

$ dvx = \sqrt {\frac{1}{{en}}\sum\limits_{i = 1}^{en} {{{\left( {{w_i} - \bar w} \right)}^2}} } /\bar w $

(2)

其中: en表示区域内边的数目，w_i表示第i条边的权值，w表示区域内所有边权值的平均值。距离变化系数可用于判断区域是否可以融合，该系数小于指定距离变化阈值的区域均可融合。

定义4  区域量级。区域量级是指区域内能容纳的最大点数，是防止区域间过度融合导致不精确的情况而设定的参数。当融合区域内点数超过给定的区域量级时终止算法，完成层次划分。

定义5  不均匀度。不均匀度是指整个数据空间被分成不均匀小区间的个数。划分的小区间越多，则不均匀度越大。在实验过程中，根据不均匀度对数据分布区域进行划分，基于不同的概率分布，区域可具有不同的不均匀度。

定义6   距离参数。距离参数是指两个空间数据点能成为邻接点的最大距离。

2 本文算法

基于上述定义，本文提出一种不均匀模糊对象的分层次co-location挖掘算法，记为FU_HI_MP(FUzzy_HIerarchy_Mining_Process)算法。

2.1 算法思想

现实数据空间中，数据点分布大多不均匀，即不同区域的数据密度各不相同，现有模糊对象co-location模式挖掘方法大多未考虑该问题。如文献[1]所提出的PO_RI_PC算法等，均是以单一的距离参数衡量不同对象实例间的距离，会导致部分co-location模式的遗漏，因此挖掘结果不准确。

为此，FU_HI_MP算法针对不均匀模糊空间对象进行分层次模式挖掘，将空间区域按照不均匀度进行划分，对不同密度区域采用不同的距离参数，基于距离变化系数构建每个子区域的邻域关系图，采用增量变化的方式生成融合区域，以减少时间花费，并在进行区域融合时充分考虑实例间的关联性，优先处理关联性高的实例集，从而有效地实现co-location模式挖掘。

算法首先随机产生不均匀分布模糊对象数据集，舍弃隶属度不符合阈值要求的实例，对不均匀数据集进行层次划分后，根据构建邻域关系图的方法，每次预加入最近的一个区域；然后计算距离变化系数，判断预加入区域是否能融入现有区域，构成一个新的区域集合。通过不断迭代，直到区域量级或距离变化系数不再满足条件为止。

2.2 参数说明

算法中涉及的参数描述如表 1所示。

表 1中:δ用于设定数据集的空间范围，θ用于判断区域间可否融合，α用于排除隶属度过小的实例，β用于限定区域大小，γ用于排除距离矩阵中的0值影响。

2.3 算法描述 2.3.1 随机产生不均匀数据集

为了方便与针对均匀分布模糊对象的挖掘算法PO_RI_PC^[1]进行对比，本文提出一种随机产生不均匀点集的方法，以产生类似n*n点集。具体步骤如算法1所述。

算法1   Initiate_set ()。

输入   δ, num, ω, n, ts;

输出  不均匀数据集PointSet。

1)PointSet ←ø;

2)按照x值从小到大将δ*δ的区域划分为n等份;

      //分别为1号, 2号, …, n号区域

3)Initiate ref_arr;

      //用n*n个1~n的整数初始化参考数组ref_arr

4)cn ← 0;

5)Repeat:

6)  index ← randi([1, n*n]);

      //随机生成1~n*n的一个整数

7)  Repeat:

8)  x ← δ * rand();

9)y ← δ * rand();

      //随机生成实例a的位置(x, y)

10)  Until (x的值在ref_arr[index]区域中);

11)  type← randi([1, ts]);

      //随机生成a所属的类型编号(1~ts)

12)  fuzziness ← rand();

      //随机生成实例a的隶属度

13)  probability ← rand();

      //随机生成实例a的概率值

14)  if (probability > ω) then

15)  将该点point:〈x, y, type, fuzziness〉添加到

    ref_arr[index]区域中;

16)  cn ← cn +1;

17)  PointSet ← PointSet ∪ point中;

18)  End if

19)Until (cn==num);

20)return PointSet

算法1根据实例数目、不均匀度、空间范围、概率阈值等参数生成了不均匀点集。首先划分区域并初始化参考数组ref_arr和实例个数(第1)~4)行)；然后基于参考数组的约束随机生成实例的位置及其所属的类编号、隶属度和概率值(第6)~13)行)；最后，将概率值大于阈值ω的实例添加到数据集中，得到随机生成的不均匀数据集(第14)~20)行)。

2.3.2 舍弃隶属度过小的数据点

在随机产生的不均匀点集中，会存在隶属度很小的实例，这样的实例对研究没有贡献，应将其舍弃，具体步骤如算法2所述。

算法2   Discard_set(PointSet)。

输入  PointSet, α；

输出  隶属度符合规定的新不均匀数据集PointSeta。

1) PointSeta ←ø        ;//处理结果集初始化

2) for i=1 to PointSet.count do

3)  PointSet(i).exist ← 1;     //数据点状态的初始化

4)End for

5)for i=1 to PointSet.count do

6)  if (PointSet(i).fuzziness < α) then

7)   PointSet(i).exist ← 0;

8)  End if

9)End for

10)for i=1 to PointSet.count do

11)  if (PointSet(i).exist==1) then

12)  PointSeta ←PointSeta ∪ PointSet(i);

13)  End if

14)End for

15)return PointSeta

算法2删除了隶属度小于阈值的实例。首先对处理结果数据集和数据点的状态进行初始化(第1)~4)行)；然后根据阈值α对数据点状态进行设置(第5)~9)行)；最后，根据数据点的状态值生成舍弃小隶属度实例的处理结果集(第10)~14)行)，并得到隶属度符合规定的新不均匀数据集(第15)行)。

2.3.3 FU_HI_MP算法

基于算法1和算法2，提出的FU_HI_MP算法具体步骤如算法3所示。

算法3   FU_HI_MP算法。

输入  δ, num, θ, ω, n, ts, α, β, γ, ε；

输出  不同区域的co-location模式集Colocation_Set。

1)  PointSet ← Initiate_set()；      //执行算法1

2)  PointSet ← Discard_set(PointSet);     //执行算法2

3)  for i=1 to PointSet.count do

4)    for j=1 to PointSet.count do

5)    DistArr(i, j) ← the distance between PointSet(i) and

     PointSet(j);

6)   End for

7) End for

8) for i=1 to PointSet.count do

9)    DistArr(i, i) ← γ;

10) End for

11) Loop:

12) min_d ←min(DistArr);  //min_d为距离矩阵中的最小值

13) [mi, mj] ← find(DistArr==min_d);

       //mi, mj为拥有最小距离的两点序号

14) if (PointSet(mi).type~=PointSet(mj).type and min_d < ε) then

15)    add an edge between PointSet(mi) and PointSet(mj);

16)   calculate the dvc using Eq. (2);   //距离变化系数

17)   set_count ← the sum of points in two sets;

18)   if (dvc < θ and set_count < β) then

19)     immerge the two sets;     //进行合并

20)     record the immerge_set;     //记录融合的区域

21)   End if

22)   End if

23)  DistArr(mi, mi) ← γ;

24)  if (the non-γ value existing in the DistArr) then

25)   goto Loop;

26)  End if;

27)Colocation_Set ← a set of immerge_sets;

28)return Colocation_Set       //返回融合区域集

算法3在算法1和算法2的基础上，挖掘出co-location模式集合。首先通过算法1计算一阶频繁集并初始化所有参数(第1)行)；其次通过算法2舍弃所有隶属度不够大的空间实例(第2)行)；然后计算实例之间的距离矩阵DistArr(第3)~7)行)；最后，针对子区域的邻域关系图，通过融合不断扩大区域，挖掘出空间co-location模式(第8)~28)行)。为了合并相连的区域，将实例按照距离融入一个与它最相近的区域，要求融合后区域的均匀度满足指定条件。其中，第8)~13)行计算出距离最小值及其涉及的实例，以便选择预加入区域；第14)行判定融合的实例是否属于相同对象类型以及计算距离是否小于距离参数；第15)行将符合要求的实例加以融合；第16)~17)行计算融合后的距离变化系数和融合数据集中实例总数；第18)行判定距离变化系数是否小于距离变化阈值并且判断点集范围是否小于给定区域量级；第19)~28)行挖掘出所有区域的空间co-location模式。

2.4 算法时间复杂度分析

算法1随机产生一个不均匀数据集，时间复杂度为O(num)，num为初始实例数目；算法2舍弃隶属度小于指定阈值的实例，需扫描数据集3趟，时间代价为3num，时间复杂度为O(num)；算法3是在算法1和算法2的基础上进行操作的，由于基于隶属度剪枝和增量融合策略，计算距离矩阵花费的时间小于[num(num-1)]/2，区域融合花费的时间为n*(num/n) lb (num/n)，即num lb (num/n)，即num lb (num/n)n为不均匀度(n≪num)。

因此，一般情况下算法3总的花费时间T₁小于：num+3*num+[num(num-1)/2]+num lb (num/n)，时间复杂度为O(num+3*num+(num(num-1)/2)+num lb (num/n))=O(num*num)。PO_RI_PC算法^[1]的时间花费T₂为k*num*num，k为频繁模式的阶数(k>2且k≪num)，时间复杂度也为O(num*num)，显然T₁ < T₂。

虽然时间复杂度和PO_RI_PC算法相当，但是在处理不均匀模糊集的问题时，FU_HI_MP算法挖掘co-location模式的结果更加准确，时间花费更少。

3 实验 3.1 实验环境

本节通过点集实验，将对不均匀模糊对象co-location模式挖掘的FU_HI_MP算法与文献[1]提出的PO_RI_PC算法进行对比，以验证本文算法的有效性及优越性。本文中所有算法均采用Matlab实现，软硬件环境为：Intel Core2 Duo 3.3 GHz CPU，4 GB内存，Windows 7操作系统。

3.2 实验数据集

采用两个随机产生的不均匀分布数据集分别加以验证。其中，模糊对象的种类为10，随机产生从0~1的隶属度。

实验数据集1，随机产生并不均匀分布在100×100空间里；实验数据集2，随机产生并不均匀分布在150×150空间里。表 2给出了两个实验数据集的参数设定值。

3.3 实验结果

算法效果通过得到的co-location集个数加以衡量，co-location集的个数越多，表明挖掘的效果越好，空间频繁关联的模糊实例集更多。因此，本节基于co-location集的个数和运行时间两个指标评价算法的挖掘效果和执行效率。

3.3.1 实例数目对co-location集个数的影响

首先考虑随着参与实验实例个数的增多所产生的co-location个数对比情况，保持不均匀度为2。基于不同数据集，实验结果对比如图 5所示。

从图 5可以看出，基于不同大小的数据集，随着实例个数的增加，本文方法FU_HI_MP显著提升了对空间实例co-location模式挖掘的效率，优于文献[1]提出的PO_RI_PC算法，同比平均提高约25%。这是因为FU_HI_MP算法充分考虑了实例间的关联关系，优先处理关联性高的实例集，从而挖掘到更多的co-location模式。由于本文的实例均是随机产生的，每次产生结果可能有很小的差异，但这并不影响对结果的判断。

3.3.2 不均匀度对co-location集个数的影响

本节实验考虑随着数据分布的不均匀度逐渐增大，FU_HI_MP算法和PO_RI_PC算法进行空间co-location挖掘时产生的结果对比。为了产生指定个数的不均匀数据空间，在使用随机数的同时，将整个坐标轴均分为指定的个数并赋予不同大小的数据产生概率，进而产生不均匀分布的各个数据空间。

基于数据集1，实例个数均初始化为4 500，基于数据集2，实例个数均初始化为10 000，结果对比如图 6所示。

从图 6可以看出，基于不同大小的数据集，不均匀度的变化对PO_RI_PC算法影响都较大，而对本文算法影响都较小。对PO_RI_PC算法来说，随着不均匀度的不断增大，基于设定好的距离参数能挖掘到的co-location个数越来越少，误差也越来越大。这是因为PO_RI_PC算法采用单一的距离参数，未考虑实例分布不均问题，无法有效处理基于不同概率分布的实例空间，从而导致挖掘的co-location集个数大量丢失。本文提出的FU_HI_MP算法所挖掘出来的co-location集个数虽然也在一定程度上减少，但这是由于区间内实例的多样性变小所导致的，在合理的范围内。

3.3.3 实例数目对算法执行时间的影响

最后考虑两种算法随着实例个数的变化对执行时间的影响，默认不均匀度为1。

基于数据集1，实例个数从500增加到3 000，基于数据集2，实例个数从100增加到8 000，运行结果如图 7所示。

从图 7可以看出，基于不同大小的数据集，随着实例数目的增加，算法的执行时间也随之增加。本文算法基于实例数目对执行时间的影响不同于传统算法的线性变化，这是由于本文实例对象的一个重要属性是隶属度，随机产生的实例隶属度不同，所以在算法开始被排除掉的实例个数不同，但这个特点并不影响对结果的判断，且本文提出的FU_HI_MP算法在执行效率上也优于PO_RI_PC算法，这是因为本文算法基于概率值和隶属度进行实例集的剪枝处理，能为后续处理节省更多的时间。

基于上面的多组比较结果可以得出，FU_HI_MP算法实现了对不均匀空间模糊数据完整、准确的挖掘。

4 结语

如今，模糊数据广泛出现在各行各业，模糊集理论已成功地应用于模式识别、智能控制、机器学习和人工智能等诸多领域。然而模糊数据集通常是不均匀出现的，故对不均匀模糊数据的挖掘研究是必要的。

目前，co-location模式已经得到广泛的研究，关于模糊数据的挖掘也有报道，但关于空间不均匀模糊数据的co-location模式挖掘的研究很少。本文就空间不均匀模糊数据进行研究，提出了一种基于有效的层次挖掘法来进行空间co-location模式挖掘的方法(FU_HI_MP)。从实验结果可以看出，本文方法在减少执行时间的情况下，实现了空间数据更准确的挖掘，对模糊对象co-location模式的挖掘更具有实际意义。本文未考虑挖掘过程中的隐私泄露问题，下一步将在此基础上，研究如何实现隐私保护的空间co-location模式挖掘。