交通拥堵是全球大城市都存在的问题。拥堵通常发生在某一特殊时段，如上下班或节假日出行期间。当城市交通网络中的某一路段发生拥堵时，可能会影响周边区域其他路段的交通，尤其是通往该拥堵路段的交通。此外，交通拥堵还会造成环境污染、资源浪费、社会效率降低，在给人们出行带来不便的同时还会引发心理上的负面情绪。

最早研究交通拥堵问题的学者采用基于传统交通流理论构建交通流模型，即运用基础数学方法将模型建立在二维平面上，以此研究交通流3个参数(流量Q、速度V、密度K)之间的关系^[1]，但由于模型的限制，未能发现交通流数据中特有的不连续“跳跃”现象，没有模拟出真实的交通拥堵现象。而后有学者尝试采用计算机建模的方法，设计出了California算法^[2]，该算法通过交通监测仪器中设置的环形线圈获取行驶车辆在路段中的占有率，并与路段截面大小进行比较，进而判断路段是否发生拥堵。在随后的时间里，不断有学者提出了各种新方法：首先，Diker等^[3]采用模糊数据挖掘技术，通过聚类的方法将交通拥堵划分为6个不同的等级，该方法具有良好的可扩展性。接着，Chu等^[4]提出了CTV-DBN(causal time-varying dynamic Bayesian network)，该方法主要基于静态交通流传感器数据获取局部时变道路交叉口的依赖关系。除此之外，Lakhouili等^[5]采用CRONOS (control of networks by optimization of switchovers)模型来计算城市道路的交通拥堵，随后他们团队又在文[5]的基础上提出了实时城市交通控制模型，并通过自适应算法提高模型的准确性^[6]。

空间并置模式挖掘是空间数据挖掘领域一个非常重要的研究方向，空间并置模式指的是不同空间特征的实例在地理空间中频繁并置出现^[7]，最早由Shekhar和Huang等^[8]提出。传统的空间并置模式挖掘框架主要通过低阶的频繁模式生成高阶的候选模式，其次生成候选模式的表实例，并通过表实例计算候选模式内各个特征的参与率，将最小的参与率作为候选模式的参与度，最后找出参与度不小于用户指定的参与度阈值的模式即为频繁的空间并置模式。然而，传统的空间并置模式挖掘算法的挖掘效率较低，不能够处理海量的数据，于是Yoo等^[9]和Yang等^[10]基于传统的挖掘框架提出了多种改进的挖掘方法。由于传统挖掘框架得到的频繁模式的数目较多，用户难以选择和利用，于是Wang等^[11-12]提出了极大频繁模式挖掘以及频繁模式的冗余约简。除此之外，其他研究人员还在传统挖掘框架的基础上提出了带稀有特征的空间并置模式挖掘^[13]、特征带效用的空间并置模式挖掘^[14]、基于模糊数据的空间并置模式挖掘^[15-16]和时空并置模式挖掘^[17-19]等。

随着GPS定位技术的快速发展，移动设备产生的大量交通数据为研究交通拥堵问题提供了有力的支持和保障。交通数据具有空间和时间两大属性，研究交通拥堵问题必须将这两大属性都考虑在内，否则得到的结果显然是不准确的。时空并置模式挖掘是将时间和空间都考虑在内的一种研究方法，He等^[20]在2018年将时空并置模式挖掘引入到交通拥堵的研究当中，并提出了APSTCP(algorithm of prevalent spatio-temporal co-location congestion pattern)算法。然而在文[20]中，关于时空拥堵实例和时空邻近关系的定义存在缺陷。首先，他们的时空拥堵实例是基于临界速度定义的，而临界速度是道路的平均速度，显然临界速度会受到异常值的影响，这就会导致得到的时空拥堵实例不准确。其次，文[20]仅考虑到了同一个时间点下的交通拥堵状态，没有考虑拥堵的“时延”特性，这就会丢失一些相关的拥堵实例，影响挖掘结果的正确性。除此之外，文[20]并没有考虑到拥堵概念本身具有模糊特性。

基于上述问题的考虑，本文首先将交通拥堵定义成一个模糊的概念，并采用隶属度定量地度量拥堵的程度。其次，将城市道路之间的空间关系加入到交通拥堵模式中。然后，加入时间属性，并定义了时空实例的时间邻近关系。最后，提出了时空并置模糊拥堵模式的概念。时空并置模糊拥堵模式在考虑地理空间邻近的同时也考虑了时间上的邻近，对道路拥堵情况的分析更为客观和准确。

在上述相关概念的基础上，本文提出了基于连接(join)方法的时空并置模糊拥堵模式挖掘算法(STF-join)以及相应的改进算法即基于邻近关系表的时空并置模糊拥堵模式挖掘算法(STF-table)。本文的主要贡献包括：

1) 基于模糊集理论，提出了模糊拥堵的隶属度计算公式，能够更准确地衡量交通拥堵状态。

2) 提出了时空并置模糊拥堵模式的概念，并设计了高效的时空并置模糊拥堵模式挖掘算法STF-join以及改进算法STF-table。

3) 在真实的数据集上对提出的算法进行了大量的实验评估和分析。

1 形式化定义和先验原理

本文的目的是挖掘在某一时间段下具有空间拓扑关系的多条路段频繁发生拥堵的情况，现给出如下相关定义。

定义1  (时空特征)  给定一个空间特征集F={f₁, f₂, …, f_m}和一个时间特征集T={t₁, t₂, …, t_n}，其中空间特征代表不同的路段，时间特征代表一天内时钟上某一个整点到后面某一个整点的时间段，而时空特征表示任意一个空间特征与时间特征的组合，一般用二元组表示为f_i-t_j=〈f_i, t_j〉(f_i∈F，t_j∈T)，时空特征集代表所有时空特征组成的集合，即空间特征集与时间特征集中所有元素的组合，记为FT={f₁-t₁, f₁-t₂, …, f_m-t_n-1, f_m-t_n}。

例1  假设给定的空间特征集F={A, B}，时间特征集T={t₁, t₂, t₃}，其中A、B分别表示A路段和B路段，t₁、t₂、t₃分别表示8点到9点的时间段、9点到10点的时间段和10点到11点的时间段，则时空特征集FT={A-t₁, A-t₂, A-t₃, B-t₁, B-t₂, B-t₃}。

定义2  (空间拓扑关系)  给定2个空间特征f_i和f_j，满足f_i-e=f_j-s且f_i-s≠f_j-e，即路段f_i的终点与路段f_j的起点相同，路段f_i的起点与路段f_j的终点不同，则称空间特征f_i和f_j满足空间拓扑关系，表示为f_i→f_j。相反，若f_i-e≠f_j-s且f_i-s=f_j-e，则f_j→f_i。

定义3  (时空实例)  时空实例是时空特征在某个时间片下对应的实例，时空实例集代表所有时空实例组成的集合。

例2  假设给定一个时空特征A-t，A表示A路段，t表示8点到9点的时间段，时间片为2 min，则a₁表示在第1个时间片下的实例，即在8:00:00—8:02:00时间片下路段A的状态。

定义4  (隶属度)  隶属度代表时空实例隶属于道路拥堵状态的程度，取值范围为[0, 1]。时空实例的瞬时速度代表时空实例通过路段的平均速度。假设给定一个时空特征f_i-t，时空实例o_l是对应时空特征f_i-t的第l个时间片的实例，则时空实例o_l的瞬时速度可形式化表示为

$ \overline {{v_{{o_l}}}} = {{\mathop{\rm length}\nolimits} _{{f_i}}}/{\rm{travel\_tim}}{{\rm{e}}_{{o_l}}}. $

(1)

其中：length_fi表示路段f_i的长度，travel_time_ol表示时空实例o_l的旅行时间。

道路的自由流速度指的是一辆车在不受上下游其他车辆影响下在该道路上正常的行驶速度。根据时空实例的瞬时速度和道路的自由流速度可以得到计算时空实例的隶属度值的公式如下：

$ \mu\left(o_{l}\right)=\left\{\begin{array}{ll} 0, & v_{f_{i}}<\overline{v_{o_{l}}}; \\ \left(v_{f_{i}}-\overline{v_{o_{l}}}\right) / v_{f_{i}}, & \text { 其他. } \end{array}\right. $

(2)

其中：v_fi表示路段f_i的自由流速度，$\overline {{v_{{o_l}}}} $表示时空实例o_l的瞬时速度。

说明：当$\overline {{v_{{o_l}}}} $大于v_fi时，此时道路必定不处于拥堵状态，即道路非常畅通，μ(o_l)=0；而当$\overline {{v_{{o_l}}}} $小于或等于v_fi时，μ(o_l)随着$\overline {{v_{{o_l}}}} $的减小而增大，当$\overline {{v_{{o_l}}}} $等于0时，μ(o_l)刚好为1，此时说明道路处于严重拥堵状态。

定义5  (时空拥堵特征的实例集)  时空拥堵特征的实例集定义为f-t={ < o, μ(o)>|μ(o)>0}，其中f-t表示一个时空拥堵特征，o表示空间特征f的实例，而μ(o)表示实例o属于时空拥堵特征f-t的隶属度值。

定义6  (拥堵时空实例集)  假设给定一个隶属度阈值f_threshold，若时空实例o满足μ(o)≥f_threshold，则称o为满足隶属度阈值的拥堵时空实例，并称集合(f-t)_{f_threshold}={o|μ(o)≥f_threshold}为时空拥堵特征f-t的拥堵时空实例集。

例3  假设图 1a是在t时间段下的时空拥堵特征及其实例集，时间片为2 min(说明：由于在挖掘过程中都是基于同一个时间特征进行的，因此在具体举例时，为了便于表述，时空特征一般不带时间特征，而是单独说明时间特征)，用户给定的隶属度阈值f_threshold=0.5，则拥堵时空实例集如图 1b所示。

定义7  (时间邻近关系)  时间邻近关系指的是在相同时间特征下, 2个不同空间特征的实例之间的时间跨度小于等于用户指定的时延阈值。

假设给定2个时空特征f₁-t和f₂-t，实例θ_u是时空特征f₁-t的第u个时间片对应的实例，实例φ_v是时空特征f₂-t的第v个时间片对应的实例，用户指定的时延阈值为t_threshold。若实例θ_u和φ_v满足2×|u-v|≤t_threshold(数字2表示时间片固定为2 min)，则称这2个实例满足时间邻近关系，表示为

$ {\mathop{\rm Time}\nolimits} \left( {{\theta _u}, {\varphi _v}} \right) < = > \left( {2 \times |u - v| \le {t_ - }{\rm{threshold}}} \right). $

(3)

例4  假设给定的时空拥堵特征及其时空实例如下所示(时间片为2 min)：A-t={(a₁, 0.2), (a₂, 0.4), (a₃, 0.8)}(a₁表示路段A在t时间段下第1个时间片对应的实例，以此类推)，B-t={(b₁, 0.4), (b₂, 0.6), (b₃, 0.9)}(b₁表示路段B在t时间段下第1个时间片对应的实例，以此类推)，t_threshold=2 min。由于a₁和b₁的时间跨度2×|1-1|=0 min＜t_threshold =2 min，因此a₁和b₁满足时间邻近关系。而对于a₁和b₃，由于时间跨度2×|1-3|=4 min>t_threshold =2 min，因此a₁和b₃不满足时间邻近关系。因此上述数据中能构成时间邻近关系的实例对有(a₁, b₁), (a₁, b₂), (a₂, b₁), (a₂, b₂), (a₂, b₃), (a₃, b₂)和(a₃, b₃)。

定义8  (时空并置模糊拥堵模式)  时空并置模糊拥堵模式是一组时空拥堵特征的集合c={f₁-t, f₂-t, …, f_k-t}，并且满足空间拓扑关系f_i→f_j(j=i+1且1≤i≤k-1)，其中t表示某一个时间段，显然c中所有的时空拥堵特征都处于同一个时间段下，k表示c所含时空拥堵特征的个数，即时空并置模糊拥堵模式c的阶。

定义9  (行实例和表实例)  给定一个时空并置模糊拥堵模式c，如果一个拥堵时空实例的集合I包含模式c中的所有特征，并且I中没有任何一个子集可以包含c中的所有特征，I中的实例两两之间满足时间邻近关系，则称集合I为模式c的一个行实例，所有行实例的集合称为模式c的表实例。

例5  假设给定一个拥堵时空实例集合I={a₁, b₁, b₂}，其中a₁是时空拥堵特征A-t的实例，b₁和b₂是时空拥堵特征B-t的实例，集合I中的元素两两之间满足时间邻近关系。显然，集合I不是时间特征t下模式{A, B}的行实例，因为集合{a₁, b₁}和{a₁, b₂}都已经包含了时空拥堵特征A-t和B-t, 所以集合{a₁, b₁}和{a₁, b₂}都是模式{A, B}的行实例。

定义10  (模糊参与率FPR与模糊参与度FPI)时空并置模糊拥堵模式c={f₁-t, f₂-t, …, f_k-t}中某个时空拥堵特征f_i-t(1≤i≤k)的模糊参与率表示为FPR(c, f_i-t)，它是f_i-t的时空实例在模式c的表实例中不重复出现的实例的隶属度之和与f_i-t的时空实例中满足隶属度阈值的拥堵实例个数的比率，公式如下：

$ {\mathop{\rm FPR}\nolimits} \left( {c, {f_i} - t} \right) = \frac{{\sum 1 \times \mu (a)}}{{\left| {{\rm{table\_instance}}\left( {\left\{ {{\mathit{f}_\mathit{i}}\mathit{ - t}} \right\}} \right)} \right|}}. $

(4)

其中: a∈Π_fi-t(table_instance(c))，Π是关系投影操作，table_instance(c)表示模式c的表实例。

c的模糊参与度表示为FPI(c)，是模式c中所有时空拥堵特征的FPR值的最小值，公式表示为

$ {\rm{FPI}}(c) = \min _{i = 1}^k\left\{ {{\rm{FPR}}\left( {c, {f_i} - t} \right)} \right\}. $

(5)

假设用户给定的最小参与度阈值为min_prev，如果FPI(c)≥min_prev，则称模式c是频繁时空并置模糊拥堵模式。

引理1  (时空并置模糊拥堵模式的反单调性)FPR和FPI随着时空并置模糊拥堵模式阶的增大而单调递减。

证明：假设某个满足隶属度阈值的拥堵时空实例包含在时空并置模糊拥堵模式c的行实例中，那么当有时空并置模糊拥堵模式c′⊆c时，这个拥堵时空实例也一定被包含在c′的行实例中，反之则不然。所以时空拥堵特征的FPR是单调递减的。

假设c={f₁-t, f₂-t, …, f_k-t}，并且存在空间拓扑关系f_k→f_k+1或f_k+1→f₁，则它们满足如下关系:

$ \begin{array}{*{20}{c}} {{\mathop{\rm FPI}\nolimits} \left( {c \cup {f_{k + 1}} - t} \right) = \min _{i = 1}^{k + 1}\left\{ {{\mathop{\rm FPR}\nolimits} \left( {c \cup {f_{k + 1}} - t, } \right.} \right.}\\ {\left. {\left. {{f_i} - t} \right)} \right\} \le \min _{i = 1}^k\left\{ {{\mathop{\rm FPR}\nolimits} \left( {c \cup {f_{k + 1}} - t, {f_i} - t} \right)} \right\} \le }\\ {\min _{i = 1}^k\left\{ {{\mathop{\rm FPR}\nolimits} \left( {c, {f_i} - t} \right)} \right\} = {\mathop{\rm FPI}\nolimits} (c).} \end{array} $

所以时空并置模糊拥堵模式的FPI也是单调递减的。

定理1  (模式的先验原理)  如果一个时空并置模糊拥堵模式c是频繁的，则它的所有子模式c′⊆c也是频繁的。相反，如果c是非频繁的，则所有包含c的超模式c′⊇c也一定是非频繁的。

证明：假设k阶的c={f₁-t, f₂-t, …, f_k-1-t, f_k-t}是频繁的，则根据引理1可知，k-1阶的c如{f₁-t, f₂-t, …, f_k-1-t}显然是频繁的。反之，如果k-1阶的时空并置模糊拥堵模式当中只要存在一个是非频繁的，显然就不能生成k阶的候选时空并置模糊拥堵模式，那么模式c一定是非频繁的。

2 挖掘频繁时空并置模糊拥堵模式

基于节1的相关定义和先验原理，本节首先介绍时空并置模糊拥堵模式挖掘的基本框架，然后给出基于连接的算法STF-join和基于邻近关系表的算法STF-table，并对2个挖掘算法进行时间复杂度和空间复杂度分析。

2.1 挖掘的基本框架

时空并置模糊拥堵模式挖掘的基本框架主要包含3部分：1)生成候选时空并置模糊拥堵模式，这是一个从低阶到高阶的过程，即从1阶的频繁时空并置模糊拥堵模式开始，结合空间拓扑关系，生成2阶的候选时空并置模糊拥堵模式，再由2阶的频繁模式生成3阶的候选模式，以此类推，一直到生成最高阶的候选时空并置模糊拥堵模式。在该过程中，根据先验原理，大量的候选模式会被剪枝，因为低阶的模式倘若是非频繁的，就不能够生成包含该低阶模式的高阶候选模式。2)生成候选时空并置模糊拥堵模式的表实例，这是一个非常耗时的过程。在本文中，2种挖掘算法正是在不同的表实例生成规则下得到的，其中STF-table算法是基于时间邻近关系表生成候选模式的表实例，而STF-join算法则是基于表实例的连接得到的。3)由候选时空并置模糊拥堵模式的表实例计算模式的FPI，并筛选出满足用户指定的最小参与度阈值的频繁时空并置模糊拥堵模式。

2.2 挖掘算法

根据节1的相关定义，本文首先设计了基于连接的STF-join算法，即算法在挖掘频繁时空并置模糊拥堵模式时，高阶候选模式的表实例是由低阶频繁模式的表实例连接生成的。算法1给出了STF-join算法的完整描述。

算法1： STF-join(通过k-1阶表实例连接生成k阶表实例的挖掘算法)。

输入：时空拥堵特征集FT={f₁-t, f₂-t, …, f_m-t}，空间拓扑关系TP={f_i→f_j|1≤i，j≤m}，时空实例集S，隶属度阈值f_threshold，时延阈值t_threshold，最小参与度阈值min_prev;

输出：满足最小参与度阈值的所有时空并置模糊拥堵模式;

步骤：

1.从S中筛选满足f_threshold的时空实例集S_{f_threshold};

2.由FT、S_{f_threshold}以及min_prev生成1阶的频繁时空并置模糊拥堵模式集P₁;

3. while(k-1阶的频繁时空并置模糊拥堵模式集P_k-1不为空)

3.1.由P_k-1和TP生成k阶的候选时空并置模糊拥堵模式集C_k;

3.2.由TI_k-1连接生成k阶的表实例集TI_k;

3.3.由TI_k计算C_k中对应模式的FPI，并与min_prev进行比较筛选出P_k;

3.4.阶数k自增;

4.返回所有的频繁时空并置模糊拥堵模式集(P₁, P₂, …, P_k)。

STF-join算法解释  算法的第1步根据用户给定的f_threshold从S中筛选出满足隶属度阈值的S_{f_threshold}。第2步首先根据FT生成1阶的候选模式，再由S_{f_threshold}生成1阶表实例，并通过表实例计算候选模式的FPI，最后找出FPI满足min_prev的1阶频繁模式存储到P₁中。第3步是一个由低阶到高阶反复迭代的过程，直到不能够生成更高阶的频繁模式为止。其中生成频繁模式的步骤如下：首先，3.1步由k-1阶的频繁模式和TP生成k阶的候选模式。然后，3.2步根据k-1阶的频繁模式的表实例连接生成k阶候选模式的表实例。最后，3.3步基于k阶候选模式的表实例计算模式的FPI筛选出满足min_prev的k阶频繁模式。至此，k阶频繁模式生成结束。3.4步阶数k自增，算法跳转到第3步执行while循环条件判断，若此时k-1阶的频繁模式集P_k-1不为空，则继续执行while循环体内部的子句；反之，若P_k-1为空，此时不能够生成k阶的候选模式，则会跳转到第4步，返回所有的频繁时空并置模糊拥堵模式集，算法结束。

图 2是在图 1所示拥堵时空实例集的基础上，STF-join算法的计算过程示例，其中TP={A→C, C→B}，t_threshold=4 min，min_prev=0.5。由于在时空并置模糊拥堵模式的挖掘过程中，时间特征始终是统一的，因此为了表述方便，图中的时空特征并没有带时间特征。

由于上述的STF-join算法是基于低阶频繁模式的表实例连接生成高阶候选模式的表实例，因此该算法存在2个缺陷：1)在挖掘过程中必须存储低阶频繁模式的表实例，这会使得算法的空间开销较大；2)如果低阶频繁模式的表实例数目庞大，这又会使得连接生成高阶候选模式的表实例的时间开销巨大。

基于上述考虑，本文又提出了一种基于时间邻近关系表的STF-table算法。该算法在挖掘频繁模式之前，首先根据时间邻近关系的定义将不同时空特征的实例之间的邻近关系计算出来并存储在一张表中，称为时间邻近关系表。然后，在生成候选模式的表实例时可以直接从该表中找出可能的表实例，这在一定程度上可以加速表实例的生成。由于该算法在生成高阶候选模式的表实例时不需要基于低阶频繁模式的表实例进行连接操作，故不需要存储低阶频繁模式的表实例。算法2给出了STF-table算法的完整描述。

算法2： STF-table(通过邻近关系表生成k阶表实例的挖掘算法)。

输入：时空拥堵特征集FT={f₁-t, f₂-t, …, f_m-t}，空间拓扑关系TP={f_i→f_j|1≤i，j≤m}，时空实例集S，隶属度阈值f_threshold，时延阈值t_threshold，最小参与度阈值min_prev;

输出：满足最小参与度阈值的所有时空并置模糊拥堵模式;

步骤：

1.从S中筛选满足f_threshold的时空实例集S_{f_threshold};

2.由FT、S_{f_threshold}以及t_threshold生成时间邻近关系表SN;

3.由FT、SN以及min_prev生成1阶的频繁时空并置模糊拥堵模式集P₁;

4. while(k-1阶的频繁时空并置模糊拥堵模式集P_k-1不为空)

4.1.由P_k-1和TP生成k阶的候选时空并置模糊拥堵模式集C_k，并将C_k赋给C_k^′;

4.2.对C_k^′中的所有候选模式按照字典序排序;

4.3.由C_k^′和SN生成k阶的表实例集TI_k;

4.4.由TI_k计算C_k中对应模式的FPI，并与min_prev进行比较筛选出P_k;

4.5.阶数k自增;

5.返回所有的频繁时空并置模糊拥堵模式集(P₁, P₂, …, P_k)。

STF-table算法解释  算法的第1步与STF-join算法的第1步相同，这里不再赘述。第2步由S_{f_threshold}和t_threshold生成时间邻近关系表SN，其中SN是按照字典序排列的。第3步首先由FT生成1阶的候选模式，然后根据SN生成1阶候选模式的表实例并基于表实例计算FPI，最后筛选出满足min_prev的频繁模式并存储到P₁中。第4步是一个由低阶生成高阶的过程，该过程反复迭代，直到不能生成更高阶的频繁模式为止。生成频繁模式的步骤如下：首先，4.1步由k-1阶的频繁模式和TP生成k阶的候选模式存储到C_k中，并将C_k赋值给临时数组C_k^′。其次，4.2步将C_k^′中的候选模式按照字典序排序，排序结果并不会影响C_k中的元素。然后，4.3步由C_k^′和SN生成对应于C_k^′中模式的表实例。最后，4.4步通过C_k^′中模式的表实例计算FPI，并将各个模式的FPI映射到C_k中的候选模式，即得到C_k中的候选模式的FPI，并从C_k中筛选出k阶的频繁模式。至此，k阶频繁模式生成结束。4.5步阶数k自增，算法跳转到第4步执行while循环条件判断。第5步与STF-join算法的第4步相同。

图 3是在图 1所示拥堵时空实例集的基础上建立的时间邻近关系表SN，其中t_threshold=4 min。图 4是在图 3所示时间邻近关系表的基础上，STF-table算法的计算过程示例。

2.3 算法的时间和空间复杂度

由于时空并置模糊拥堵模式挖掘的时间消耗主要集中在计算时间邻近关系、生成候选模式及其表实例上，故从这3个方面分析STF-join和STF-table算法的时间复杂度。而空间的消耗主要集中在表实例和邻近关系表的存储上，故从这2个方面分析STF-join和STF-table算法的空间复杂度。

STF-join算法的时间和空间复杂度分析如下：根据TP生成候选模式的时间复杂度为$\mathit{O}\left( {{\rm{|FT| + }}\sum\limits_{k = 1}^{w - 1} {\left| {{P_k}} \right|} } \right)$；基于连接生成表实例的时间复杂度为$O\left( {\sum\limits_{k = 1}^{w - 1} {(k - 1)} \left| {{\rm{T}}{{\rm{I}}_{k + 1}}} \right|\left| {{C_{k + 1}}} \right|} \right)$，其中w表示频繁模式的最大阶数。经过上述分析，STF-join算法的时间复杂度为

$ O\left( {\sum\limits_{k = 1}^{w - 1} {(k - 1)} \left| {{\rm{T}}{{\rm{I}}_{k + 1}}} \right|\left| {{C_{k + 1}}} \right|} \right). $

由于STF-join算法需要基于低阶频繁模式的表实例生成高阶候选模式的表实例，因此必须存储低阶频繁模式的表实例，该部分的空间复杂度为O(|TI_k-1|)；除此之外，算法在计算候选模式的FPI之前需要存储形成的表实例，该部分的空间复杂度为O(|TI_k|)；所以STF-join算法的空间复杂度为O(|TI_k-1|+|TI_k|)。

STF-table算法的时间和空间复杂度分析如下：计算不同时空特征下两两实例之间的时间邻近关系获取SN的时间复杂度最多为O(S_{f_threshold}²)；根据TP生成候选模式的时间复杂度为$\mathit{O}\left( {{\rm{|FT| + }}\sum\limits_{k = 1}^{w - 1} {\left| {{P_k}} \right|} } \right)$；基于SN生成表实例的时间复杂度为$O\left( {\sum\limits_{k = 1}^w {\left| {{\rm{SN}}} \right|} \left| {{C_k}} \right|} \right)$。经过上述分析，STF-table算法的时间复杂度为

$ O\left( {\sum\limits_{k = 1}^w {\left| {{\rm{SN}}} \right|} \left| {{C_k}} \right|} \right). $

由于STF-table算法在挖掘过程中需要一直存储SN，该部分的空间复杂度为O(|SN|)；除此之外，算法同样在计算候选模式的FPI之前需要存储形成的表实例，该部分的空间复杂度为O(|TI_k|)；所以STF-table算法的空间复杂度为O(|SN|+|TI_k|)。

3 实验评估

本文提出的STF-join和STF-table算法均由Java语言编写，Java环境为JDK1.8，开发平台为Eclipse。CPU为Intel(R) Core(TM) i7-3537U、主频为2.50 GHz、内存为8 G，操作系统为Windows 10。

3.1 实验数据

本实验所用数据集来源于2017年阿里天池智慧交通预测挑战赛，是由贵州省大数据发展管理局与贵州省交通运输厅提供的真实数据。数据集包含3部分内容，分别为各路段的属性信息、道路网络的空间拓扑结构信息以及各路段于2016年3月至6月在各个时间片(一个时间片为2 min)下的旅行时间信息，如表 1-3所示。其中各路段于2016年3月至6月在各个时间片下的旅行时间信息通过在各道路路段放置数据采集器获取，采集器每2 min采集一次。

3.2 算法的挖掘结果

为了评估本文所提出的算法的挖掘结果，将STF-table算法与文[20]提出的APSTCP算法在真实数据集上的挖掘结果进行了对比。本文首先基于2016年3月1日至7日的交通数据进行了实验，其中在STF-table算法中设置f_threshold=0.5，t_threshold =4 min，min_prev=0.5，而在APSTCP算法中设置拥堵系数p=0.5、时间跨度阈值t_win=4，min_prev=0.5。其中图 5是2个算法生成的候选模式和频繁模式数目的比较，图 5表明STF-table算法在2016年3月1日至7日生成的候选模式和频繁模式的数目基本上都比APSTCP算法多。而图 6是2个算法生成的频繁模式的最高阶数的对比，图 6表明在前5天中2个算法的最高阶数相同，而到了后2天STF-table算法挖掘出的频繁模式的最高阶数始终比APSTCP算法的更大。出现以上情况的原因是APSTCP算法没有考虑拥堵的时延，而在STF-table算法中，当t_threshold增大时，其候选模式的行实例会增多，这就使得候选模式具备更大的可能性成为频繁模式。故在参数取值相当的情况下，STF-table算法比APSTCP算法能够挖掘出更多更长的模式。

接下来，本文将上述的2个算法基于前面的参数设置，将在2016年3月1日的交通数据中挖掘出的频繁模式进行比较，如表 4所示(表中的数字代表的是不同的路段编号，由于在实际数据中路段总共有132条，故将路段编号处理为1—132)。由表 4所示的挖掘结果可以看出，STF-table算法挖掘出的频繁模式能够完整覆盖APSTCP算法的挖掘结果。经过分析发现，如果STF-table算法通过隶属度阈值筛选出来的拥堵实例集包含所有由APSTCP算法通过拥堵临界速度筛选出来的时空拥堵实例，则STF-table算法生成的候选模式的表实例必定包含APSTCP算法生成的表实例。因为根据APSTCP算法中实例的邻近关系的定义，其生成的每个行实例必定是处于同一个时间片下，而对于STF-table算法，当t_threshold=0时就能确保生成的每个行实例都处于同一个时间片下，然而t_threshold>0，故STF-table算法生成的候选模式的表实例必定包含APSTCP算法生成的表实例，此时STF-table算法生成的频繁模式也会包含APSTCP算法的结果。

3.3 参数取值对算法挖掘效率的影响

为了评估不同的参数取值对算法挖掘效率的影响，本文分别将STF-join和STF-table算法在真实数据集(132条路段、80 000个时空实例)上进行实验。图 7是在保持t_threshold=4 min，min_prev=0.5不变的情况下，改变f_threshold取值对2个算法执行时间的影响。由图 7可知，随着f_threshold增大，2个算法的执行时间呈现下降的趋势，并且STF-table算法的变化较为明显，而STF-join算法没有太大的变化。原因是筛选出的时空实例越来越少，能够生成的表实例也就越来越少，导致执行时间减少。图 7同时也表明在上述条件下，STF-join算法的时间开销始终低于STF-table算法，这是因为表实例较小，连接生成并不耗时，反而是计算时间邻近关系表比较耗时。图 8是在f_threshold=0.5，min_prev=0.5保持不变的情况下，改变t_threshold对2个算法执行时间的影响。由图 8可知，随着t_threshold增大，2个算法的执行时间呈现上升的趋势。其中，当t_threshold >6 min时，STF-join算法的执行时间增加得较为明显，而整个过程中STF-table算法的执行时间变化不大。因为只要f_threshold保持不变，需要计算时间邻近关系的实例就不变。而对于STF-join算法，当t_threshold的取值越大，需要连接生成的表实例越多，时间开销也就越大。图 9是在f_threshold=0.5，t_threshold=4 min保持不变的情况下，改变min_prev对2个算法执行时间的影响。显然，2个算法的执行时间都随着min_prev增大而减少，因为当min_prev增大时，生成的频繁模式越少，导致执行时间减少。

3.4 时空实例数对算法挖掘效率的影响

由于APSTCP算法与本文提出的算法的挖掘结果不同，比较APSTCP算法与本文提出的算法的挖掘效率意义不大，因此并没有将本文提出的算法与APSTCP算法进行挖掘效率的比较。

虽然节2已经分析了所提出的2个算法的时间复杂度，但是并不能够直接得出哪个算法的执行效率更高，所以本节将从改变时空实例数的角度出发，讨论2个算法的执行效率。其中图 10和11都是在f_threshold=0.5，min_prev=0.5保持不变的情况下进行的实验，唯一的区别是图 10设置的t_threshold=4 min，而图 11设置的t_threshold=6 min。图 10和11的结果都表明：随着时空实例数的增加，2个算法的执行时间都在增加。但是在图 10中，随着实例个数的增加，STF-join算法的执行效率要高于STF-table算法。而在图 11中，随着实例个数的增加，STF-table算法的执行效率始终高于STF-join算法。结合图 8的分析可知，随着t_threshold增大，时空实例之间的时间邻近关系增多，形成的表实例增多，那么基于连接的STF-join算法需要的时间开销也就越大。而对于STF-table算法，当实例数不变的情况下，生成时间邻近关系表的时间消耗并不会改变，所以t_threshold对STF-table算法影响较小。当t_threshold较小时，由于时空实例之间的时间邻近关系较少，基于连接的STF-join算法反而更有优势，这是因为STF-table算法需要生成时间邻近关系表，相比而言需要消耗更多的时间。所以，2个算法的执行时间才会出现图 10和11的结果。

4 总结

本文首先分析了现有的基于时空并置模式挖掘道路交通拥堵模式的方法所存在的缺陷。其次考虑到拥堵是一个模糊的概念，所以本文结合模糊集理论，提出了度量拥堵程度的隶属度的计算方法。然后在时空并置模式的基础上提出了时空并置模糊拥堵模式的概念，并设计了2个挖掘时空并置模糊拥堵模式的算法。最后基于真实数据集对所提出的算法在挖掘结果和挖掘效率上进行了相应的实验评估。实验结果表明，本文所提出的算法的挖掘结果优于现有的基于时空并置模式挖掘交通拥堵模式的算法，即在交通拥堵的衡量中引入模糊集理论能够挖掘出更加合理的结果。