D0I:10.13374/.issn1001-053x.2012.01.008 第34卷第1期 北京科技大学学报 Vol.34 No.1 2012年1月 Journal of University of Science and Technology Beijing Jan.2012 一种实时有效的蜂群模式挖掘算法 齐悦于彦伟邝俊何杰王沁 北京科技大学计算机与通信工程学院，北京100083 区通信作者，E-mail:uyanwei0530@gmail..com 摘要针对实时相关运动模式挖掘应用的需求，提出了一种实时地发现关闭蜂群模式的簇重组算法(CLU).该算法维护 一个候选蜂群模式列表，在每个时间戳采用基于密度的聚类算法对移动目标进行聚类，根据聚类结果组合所有的最大移动目 标集，记录相应的时间集，然后构建候选蜂群模式，并更新到候选列表.算法给出了三种更新规则和一种插入规则，用于实现 候选蜂群模式列表的更新，同时降低了候选列表的冗余度，提高了算法的效率.在每个时间戳结束时可通过关闭检测规则实 时地发现当前时刻的关闭蜂群模式.在合成数据上的综合实验验证了CLUR算法的正确性、实时性和高效性，CLUR算法适用 于实时相关运动模式挖掘系统. 关键词数据挖掘：轨迹：聚类算法：簇重组：实时系统 分类号TP274 Efficient algorithm for real-time mining swarm patterns QI Yue,YU Yan-ei,KUANG Jun,HE Jie,WANG Qin School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:yuyanwei0530@gmail.com ABSTRACT Due to urgent demands for real time relative motion patterns mining applications,an efficient cluster-recombinant (CLUR)algorithm for real time discovering closed swarm patterns was proposed.The algorithm maintains a candidate swarm list,and at each timestamp carries out cluster analysis on moving objects using the clustering algorithm based on density,and according to the clustering results it recombines the maximum moving object set and records the corresponding maximum time set,further constructs a candidate swarm pattern and then finally updates the candidate swarm list up to date by using three update rules and an insert rule.The rules greatly reduce the redundancy of the candidate list and improve the efficiency of the algorithm.At the end of each timestamp,the current closed swarm patterns can be real time obtained by closuring checking rules.Comprehensive empirical studies on large synthetic data demonstrate the correctness,real time and efficiency of the CLUR algorithm.The CLUR algorithm can be applicable to real time relative motion pattern mining systems KEY WORDS data mining:trajectories:clustering algorithms:cluster recombination:real time systems 随着GPS、无线射频技术、智能手机等电子跟踪 设备等获取到的海量轨迹数据的分析和应用瓶颈 设备的快速发展，人们可以更快捷地收集到移动目 目前，轨迹数据挖掘已广泛应用于各种研究领域，如 标海量的时间空间数据.例如，微软亚洲研究院在 智能交通管理、野生动物迁徙研究、行为学研究和实 北京跟踪收集了164名用户在2.5a内所有的GPS 时跟踪监控回 数据，并进行了一系列的实验0.这些包含时间信 Laube等)首先提出了一种有用的轨迹数据挖 息的位置数据构成了移动目标的轨迹数据.为了能 掘任务，找出一起相关运动的移动目标组合.最新 够利用这些轨迹数据，需要一种有效地方法去管理 研究0提出了一种蜂群模式：一组相关运动的移动 和分析轨迹数据，从中发现新颖的、有趣的知识模 目标，目标之间并不总是紧密接近，而是沿大致的方 式，用于解决GPS、室内定位系统(PS)和电子跟踪 向运动，且在某些时间点聚集在一块.相比其他运 收稿日期：201103-25 基金项目：国家自然科学基金资助项目(61172049：61003251)：教有部博士点基金项目(20100006110015)
第 34 卷 第 1 期 2012 年 1 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 1 Jan． 2012 一种实时有效的蜂群模式挖掘算法 齐 悦 于彦伟 邝 俊 何 杰 王 沁 北京科技大学计算机与通信工程学院，北京 100083 通信作者，E-mail: yuyanwei0530@ gmail． com 摘 要 针对实时相关运动模式挖掘应用的需求，提出了一种实时地发现关闭蜂群模式的簇重组算法( CLUR) ． 该算法维护 一个候选蜂群模式列表，在每个时间戳采用基于密度的聚类算法对移动目标进行聚类，根据聚类结果组合所有的最大移动目 标集，记录相应的时间集，然后构建候选蜂群模式，并更新到候选列表． 算法给出了三种更新规则和一种插入规则，用于实现 候选蜂群模式列表的更新，同时降低了候选列表的冗余度，提高了算法的效率． 在每个时间戳结束时可通过关闭检测规则实 时地发现当前时刻的关闭蜂群模式． 在合成数据上的综合实验验证了 CLUR 算法的正确性、实时性和高效性，CLUR 算法适用 于实时相关运动模式挖掘系统． 关键词 数据挖掘; 轨迹; 聚类算法; 簇重组; 实时系统 分类号 TP274 Efficient algorithm for real-time mining swarm patterns QI Yue，YU Yan-wei ，KUANG Jun，HE Jie，WANG Qin School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China Corresponding author，E-mail: yuyanwei0530@ gmail． com ABSTRACT Due to urgent demands for real time relative motion patterns mining applications，an efficient cluster-recombinant ( CLUR) algorithm for real time discovering closed swarm patterns was proposed． The algorithm maintains a candidate swarm list，and at each timestamp carries out cluster analysis on moving objects using the clustering algorithm based on density，and according to the clustering results it recombines the maximum moving object set and records the corresponding maximum time set，further constructs a candidate swarm pattern and then finally updates the candidate swarm list up to date by using three update rules and an insert rule． The rules greatly reduce the redundancy of the candidate list and improve the efficiency of the algorithm． At the end of each timestamp，the current closed swarm patterns can be real time obtained by closuring checking rules． Comprehensive empirical studies on large synthetic data demonstrate the correctness，real time and efficiency of the CLUR algorithm． The CLUR algorithm can be applicable to real time relative motion pattern mining systems． KEY WORDS data mining; trajectories; clustering algorithms; cluster recombination; real time systems 收稿日期: 2011--03--25 基金项目: 国家自然科学基金资助项目( 61172049; 61003251) ; 教育部博士点基金项目( 20100006110015) 随着 GPS、无线射频技术、智能手机等电子跟踪 设备的快速发展，人们可以更快捷地收集到移动目 标海量的时间空间数据． 例如，微软亚洲研究院在 北京跟踪收集了 164 名用户在 2. 5 a 内所有的 GPS 数据，并进行了一系列的实验［1］． 这些包含时间信 息的位置数据构成了移动目标的轨迹数据． 为了能 够利用这些轨迹数据，需要一种有效地方法去管理 和分析轨迹数据，从中发现新颖的、有趣的知识模 式，用于解决 GPS、室内定位系统( IPS) 和电子跟踪 设备等获取到的海量轨迹数据的分析和应用瓶颈． 目前，轨迹数据挖掘已广泛应用于各种研究领域，如 智能交通管理、野生动物迁徙研究、行为学研究和实 时跟踪监控［2］． Laube 等［3］首先提出了一种有用的轨迹数据挖 掘任务，找出一起相关运动的移动目标组合． 最新 研究［4］提出了一种蜂群模式: 一组相关运动的移动 目标，目标之间并不总是紧密接近，而是沿大致的方 向运动，且在某些时间点聚集在一块． 相比其他运 DOI:10.13374/j.issn1001-053x.2012.01.008
·38 北京科技大学学报 第34卷 动模式，蜂群模式没有一段连续时间的约束，运动模 O(n),但对噪声比较敏感；LCSS和EDR在抑制噪 式更松弛，也更符合某些实际情况.ⅵ等面同时提 声上有比较好的效果，能得到质量较好的聚类，时间 出了一种发现关闭蜂群模式（时间集和目标集同时 复杂度都为O(n2);ERP采用了距离的度量，需要 最大的蜂群模式)的目标集增长算法(object-- 设置代价值，代价值的设置影响对噪声的处理能力 Growth),该算法还需要等待轨迹数据收集完成以后 和聚类的效果：DTW在度量弱时间特性的轨迹距离 才能开始挖掘.对于实时目标跟踪与监管、交通导 时有很好的效果，时间复杂度也为O(n).这几种 航等应用，监控人员无法对众多移动目标的海量轨 方法在总体上能较好地衡量轨迹数据的距离，但不 迹进行实时分析处理，而数据处理的实时性对这些 适用于单个时间戳的距离测量. 应用来说又非常重要，因此只能借助实时轨迹处理 Lee和Han介绍了一种基于密度的轨迹线段 来解决这一问题.目前大多相关运动模式的挖掘都 聚类算法，可以发现轨迹中的线段簇。ⅱ等提出 基于静态数据库存储的大规模轨迹数据，难以应用 了一种增量轨迹聚类方法TCMM,以解决逐渐增加 于实时轨迹数据处理 的轨迹数据的增量聚类问题.Piciarelli和Foresti 本文提出了一种实时挖掘关闭蜂群模式的簇重 提出一种在线的轨迹聚类算法，通过线段轨迹聚类 组算法(cluster-recombinant algorithm,CLUR),该算 检测异常轨迹.以上聚类算法在处理整段轨迹数据 法从最大的移动目标组合的可能性方面考虑，根据 时有较好的效果，但不能应用于实时发现蜂群模式 每个时间戳的聚类结果，构成移动目标的组合情况， 的单时间戳聚类.本文采用的DBSCAN算法同是一 而非穷举移动目标的所有组合.随着时间的推移， 种典型的基于密度的聚类算法，该算法采用欧氏距 不断重组移动目标的组合情况，并记录组合相应的 离，在多维数据的聚类上有非常好的效果 时间戳信息.在每个时间戳结束，通过关闭检测规 则实时发现关闭蜂群模式，而不需要花费大量时间 2候选蜂群模式 收集轨迹数据后再开始挖掘运动模式. 设定OB={01,02,…,0m}为移动目标的集合； 1 相关工作 Ts={t1,2,…,tn}为所有时间戳的集合；0为ODB 的一个子集：T为T的一个子集；IO1、IT1分别为 多移动目标的相关运动模式挖掘一直是一个研 集合0和集合T中的元素个数. 究热点.最初，Laube等回提出了群集、领导者、集 簇及其表示：在每个时间戳，通过聚类算法得到 合和偶遇等运动模式，群集模式同用于发现每个时 一组簇的集合.集合C,={C:,C,…,C}为在时间 间戳都在同一圆形区域的相关移动目标组合，领导 者模式描述的是一组特殊的群集模式，用于发现被 戳t得到的簇的集合，其中C={o1,02,…,0m}为 多个移动目标跟随了一定连续时间的移动目标因 时间戳t时的一个簇 Kalnis等m提出了一种运动簇模式，试图发现一段 定义1（最大移动目标集）所谓的最大移动目 连续时间戳上的移动空间簇，该模式设定了两个连 标集O,是一组过去所有时间戳聚类得到簇的交 续时间戳的簇内移动目标的重合率阈值日，但日值 集中移动目标的集合.若0={0,02，…，0u}是一 的设定不同，发现的相关运动模式差异较大.Jeung 个最大移动目标集，则{o,0n,…,0n}二C%∩C∩ 等圆为发现所有一起紧密行驶的车队问题提出了 …∩C(k≤i)且101≥minO.min0是蜂群模式给 车队模式，要求移动目标在一段连续时间内以任意 定的最小目标集个数阈值.根据每个时间戳的聚类 形状聚集运动，而不像群集模式所定义的在同一圆 结果，可确定当前时间戳t,所有的最大移动目标集. 形区域 定义2（候选蜂群模式）若O,T)表示一个候 车队模式和蜂群模式在衡量移动目标的聚集时 选蜂群模式，则0={01,02，…，0m}是一个最大移 都使用了簇的概念，基于密度的聚类是基于距离聚 动目标集，且T={t:t2,…,t}. 类方法的一种，可以发现任意形状聚集的移动目标 存放候选蜂群模式的一个队列，被称作候选列 组合.在基于距离聚类方法中常用的距离计算方法 表，用L表示.在时间戳t,时，候选列表L内存放了 有：欧氏距离、动态时间弯曲(DTV)回、最长共同子 当前所有的候选蜂群模式 序列(LCSS)o、实数代价编辑距离(ERP)四和实 数序列编辑距离(EDR)☒.采用欧氏距离能很快 3簇重组算法 地对大规模数据进行聚类，时间复杂度较低，约为 本节首先介绍了簇重组算法的基本思想，然后
北 京 科 技 大 学 学 报 第 34 卷 动模式，蜂群模式没有一段连续时间的约束，运动模 式更松弛，也更符合某些实际情况． Li 等［4］同时提 出了一种发现关闭蜂群模式( 时间集和目标集同时 最大 的 蜂 群 模 式) 的目标集增长算法 ( objectGrowth) ，该算法还需要等待轨迹数据收集完成以后 才能开始挖掘． 对于实时目标跟踪与监管、交通导 航等应用，监控人员无法对众多移动目标的海量轨 迹进行实时分析处理，而数据处理的实时性对这些 应用来说又非常重要，因此只能借助实时轨迹处理 来解决这一问题． 目前大多相关运动模式的挖掘都 基于静态数据库存储的大规模轨迹数据，难以应用 于实时轨迹数据处理． 本文提出了一种实时挖掘关闭蜂群模式的簇重 组算法( cluster-recombinant algorithm，CLUR) ，该算 法从最大的移动目标组合的可能性方面考虑，根据 每个时间戳的聚类结果，构成移动目标的组合情况， 而非穷举移动目标的所有组合． 随着时间的推移， 不断重组移动目标的组合情况，并记录组合相应的 时间戳信息． 在每个时间戳结束，通过关闭检测规 则实时发现关闭蜂群模式，而不需要花费大量时间 收集轨迹数据后再开始挖掘运动模式． 1 相关工作 多移动目标的相关运动模式挖掘一直是一个研 究热点． 最初，Laube 等［3］提出了群集、领导者、集 合和偶遇等运动模式，群集模式［5］用于发现每个时 间戳都在同一圆形区域的相关移动目标组合，领导 者模式描述的是一组特殊的群集模式，用于发现被 多个移动目标跟随了一定连续时间的移动目标［6］． Kalnis 等［7］提出了一种运动簇模式，试图发现一段 连续时间戳上的移动空间簇，该模式设定了两个连 续时间戳的簇内移动目标的重合率阈值 θ，但 θ 值 的设定不同，发现的相关运动模式差异较大． Jeung 等［8］为发现所有一起紧密行驶的车队问题提出了 车队模式，要求移动目标在一段连续时间内以任意 形状聚集运动，而不像群集模式所定义的在同一圆 形区域 . 车队模式和蜂群模式在衡量移动目标的聚集时 都使用了簇的概念，基于密度的聚类是基于距离聚 类方法的一种，可以发现任意形状聚集的移动目标 组合． 在基于距离聚类方法中常用的距离计算方法 有: 欧氏距离、动态时间弯曲( DTW) ［9］、最长共同子 序列( LCSS) ［10］、实数代价编辑距离( ERP) ［11］和实 数序列编辑距离( EDR) ［12］． 采用欧氏距离能很快 地对大规模数据进行聚类，时间复杂度较低，约为 O( n) ，但对噪声比较敏感; LCSS 和 EDR 在抑制噪 声上有比较好的效果，能得到质量较好的聚类，时间 复杂度都为 O( n2 ) ; ERP 采用了距离的度量，需要 设置代价值，代价值的设置影响对噪声的处理能力 和聚类的效果; DTW 在度量弱时间特性的轨迹距离 时有很好的效果，时间复杂度也为 O( n2 ) ． 这几种 方法在总体上能较好地衡量轨迹数据的距离，但不 适用于单个时间戳的距离测量． Lee 和 Han ［13］介绍了一种基于密度的轨迹线段 聚类算法，可以发现轨迹中的线段簇． Li 等［14］提出 了一种增量轨迹聚类方法 TCMM，以解决逐渐增加 的轨迹数据的增量聚类问题． Piciarelli 和 Foresti ［15］ 提出一种在线的轨迹聚类算法，通过线段轨迹聚类 检测异常轨迹． 以上聚类算法在处理整段轨迹数据 时有较好的效果，但不能应用于实时发现蜂群模式 的单时间戳聚类． 本文采用的 DBSCAN 算法［3］是一 种典型的基于密度的聚类算法，该算法采用欧氏距 离，在多维数据的聚类上有非常好的效果． 2 候选蜂群模式 设定 ODB = { o1，o2，…，om } 为移动目标的集合; TDB = { t1，t2，…，tn } 为所有时间戳的集合; O 为 ODB 的一个子集; T 为 TDB的一个子集; | O |、| T | 分别为 集合 O 和集合 T 中的元素个数． 簇及其表示: 在每个时间戳，通过聚类算法得到 一组簇的集合． 集合 Ct = { C1 t ，C2 t ，…，Ck t } 为在时间 戳 t 得到的簇的集合，其中 C1 t = { oi1，oi2，…，oim } 为 时间戳 t 时的一个簇． 定义 1( 最大移动目标集) 所谓的最大移动目 标集 Omax，是一组过去所有时间戳聚类得到簇的交 集中移动目标的集合． 若 O = { oj 1 ，oj 2 ，…，ojk } 是一 个最大移动目标集，则{ oj 1 ，oj 2 ，…，ojm } Cj 1 ti 1∩Cj 2 ti2∩ …∩Cjk tik ( k≤i) 且 | O | ≥minO． minO 是蜂群模式给 定的最小目标集个数阈值． 根据每个时间戳的聚类 结果，可确定当前时间戳 ti所有的最大移动目标集． 定义 2( 候选蜂群模式) 若〈O，T〉表示一个候 选蜂群模式，则 O = { oj1，oj2，…，ojm } 是一个最大移 动目标集，且 T = { ti，ti2，…，tik } ． 存放候选蜂群模式的一个队列，被称作候选列 表，用 L 表示． 在时间戳 ti时，候选列表 L 内存放了 当前所有的候选蜂群模式． 3 簇重组算法 本节首先介绍了簇重组算法的基本思想，然后 ·38·
第1期 齐悦等：一种实时有效的蜂群摸式挖掘算法 ·39 给出了算法的更新规则、插入规则和关闭检测规则， 戳集合，构建候选蜂群模式，并放入候选列表.在当 最后通过对算法伪代码的分析详细阐述了算法 前时间戳结束时，通过阈值minT,实时地发现满足 过程 最小时间集的候选蜂群模式，即为关闭蜂群模式。 3.1算法思想 实时挖掘关闭蜂群模式的过程就是在每个时间戳逐 objectGrowth算法为了发现关闭蜂群模式，采用 步构建、更新候选蜂群模式列表，最后通过关闭检测 了先验剪枝和向后剪枝策略以减少移动目标组合的 策略从候选项中实时发现关闭蜂群模式， 搜索空间，但目标组合的搜索空间仍然较大，同时关 图1展示了CLUR算法的一个运行实例，系统包 闭检测也需要较大的运行时间. 含了九个移动目标(1,2，，9)，并运行了四个时间长 既然挖掘目标是为了实时发现关闭蜂群模式， 度(1,213).时间戳从t1开始，每运行一个时间单 即当前时刻满足最大时间集的最大移动目标组合 位，根据聚类结果构造最大移动目标集，并将最大移 本文考虑从每个时间戳的聚类结果组合最大移动目 动目标集和相应时间集更新到候选列表L.23和 标集，然后统计这些最大目标集在同一簇内的时间 ta时刻的候选列表分别为L、L2、Lg和La T个 12 579 579 0 0 T 0 1.23 1.2341 1.23t3 1.2.31l 4.6.81 4.681 4.681 4.6.81 5.7.9t.t43 5.7911 57.943 5.7.91…23 6.8 Ilt 6.8tt3 6.8‘52 1.2.3.4 5.6.79‘3 1.2.3.42 12.3.45 1.2t,w4 5.6.7.93 6.7 4 3.54 4.6.7.814 图1CLUR算法运行实例 Fig.1 An example of the CLUR algorithm 3.2算法规则 3.2.2候选项插入规则 3.2.1候选项更新规则 根据候选蜂群模式的定义，可以得出候选列表 根据图1示例，在每个时间戳聚类结束后，需要 的特性. 对候选列表L进行更新。更新的方法是依次对候选 特性1设t:-1时刻后得到的候选蜂群列表L, 列表中每一个候选项进行更新.设时间戳t:的聚类 对于列表L中任意两个候选项，=O,T）,2= 结果为C={C,C,…,C}. 02,T2),若01二02，则T12T2 规则1对于任意候选项v=《O,T)∈L,若0C 设定t:-1时刻后候选列表为L',t:时刻已插入L C(1≤i≤k),则候选项u更新为O,TU{t}〉. 的候选项构成△L,根据列表的特性和更新候选项规 规则2对于任意候选项v=(O,T)∈L,若 则得出候选项的插入规则如下 10nC.I≥min0且0nC.≠0(1≤i≤k),则新建候 规则4对于时间戳t,时新建的候选蜂群模式 选蜂群模式(O∩C,TU{t,}),并按插入规则插入 U=0,T〉，若存在候选项1=(O,T）∈L',则不需 候选列表L中. 要插入；否则判断△L中是否存在2=0，T),若 规则3对于任意C∈C:(1≤j≤k),新建候选 存在则更新2为O,TUT〉，反之直接将插入到 蜂群模式(C,{t,}〉，并按插入规则插入到候选列表 列表L中 L中. 上述插入规则有效减少了候选蜂群模式列表中
第 1 期 齐 悦等: 一种实时有效的蜂群模式挖掘算法 给出了算法的更新规则、插入规则和关闭检测规则， 最后通过对算法伪代码的分析详细阐述了算法 过程． 3. 1 算法思想 objectGrowth 算法为了发现关闭蜂群模式，采用 了先验剪枝和向后剪枝策略以减少移动目标组合的 搜索空间，但目标组合的搜索空间仍然较大，同时关 闭检测也需要较大的运行时间． 既然挖掘目标是为了实时发现关闭蜂群模式， 即当前时刻满足最大时间集的最大移动目标组合． 本文考虑从每个时间戳的聚类结果组合最大移动目 标集，然后统计这些最大目标集在同一簇内的时间 戳集合，构建候选蜂群模式，并放入候选列表． 在当 前时间戳结束时，通过阈值 minT，实时地发现满足 最小时间集的候选蜂群模式，即为关闭蜂群模式． 实时挖掘关闭蜂群模式的过程就是在每个时间戳逐 步构建、更新候选蜂群模式列表，最后通过关闭检测 策略从候选项中实时发现关闭蜂群模式． 图 1 展示了 CLUR 算法的一个运行实例，系统包 含了九个移动目标( 1，2，…，9) ，并运行了四个时间长 度( t1，t2，t3，t4 ) ． 时间戳从 t1开始，每运行一个时间单 位，根据聚类结果构造最大移动目标集，并将最大移 动目标集和相应时间集更新到候选列表 L． t1、t2、t3和 t4时刻的候选列表分别为 Lt1、Lt2、Lt3和 Lt4 ． 图 1 CLUR 算法运行实例 Fig． 1 An example of the CLUR algorithm 3. 2 算法规则 3. 2. 1 候选项更新规则 根据图 1 示例，在每个时间戳聚类结束后，需要 对候选列表 L 进行更新． 更新的方法是依次对候选 列表中每一个候选项进行更新． 设时间戳 ti的聚类 结果为 Cti = { C1 ti，C2 ti，…，Ck ti} ． 规则 1 对于任意候选项 v =〈O，T〉∈L，若O Cj ti ( 1≤i≤k) ，则候选项 v 更新为〈O，T∪{ ti} 〉． 规则 2 对于任意候选项 v =〈O，T〉∈L，若 |O∩Cj ti |≥minO 且 O∩Cj ti≠O( 1≤i≤k) ，则新建候 选蜂群模式〈O∩Cj ti，T∪{ ti} 〉，并按插入规则插入 候选列表 L 中． 规则 3 对于任意 Cj ti∈Cti ( 1≤j≤k) ，新建候选 蜂群模式〈Cj ti，{ ti} 〉，并按插入规则插入到候选列表 L 中． 3. 2. 2 候选项插入规则 根据候选蜂群模式的定义，可以得出候选列表 的特性． 特性 1 设 ti － 1时刻后得到的候选蜂群列表 L， 对于列表 L 中任意两个候选项 v1 =〈O1，T1〉，v2 = 〈O2，T2〉，若 O1O2，则 T1T2 ． 设定 ti － 1时刻后候选列表为 L'，ti 时刻已插入 L 的候选项构成 ΔL，根据列表的特性和更新候选项规 则得出候选项的插入规则如下． 规则 4 对于时间戳 ti时新建的候选蜂群模式 v =〈O，T〉，若存在候选项 v1 =〈O，T1〉∈L'，则不需 要插入 v; 否则判断 ΔL 中是否存在 v2 =〈O，T'〉，若 存在则更新 v2 为〈O，T∪T'〉，反之直接将 v 插入到 列表 L 中． 上述插入规则有效减少了候选蜂群模式列表中 ·39·
·40* 北京科技大学学报 第34卷 冗余的候选项，提高了算法的效率 7: u.T←-.TU{t,};break; 3.2.3关闭蜂群模式检测规则 8: else 通过使用候选项更新规则和插入规则，CLUR在每 9: candidate'←-<u.O∩c,u.TU 个时间戳更新候选列表，在时间戳结束后，从候选列表 {t}>;/新建候选模式 中找出关闭蜂群模式的关闭检测，检测规则如下. 10: insertCanList (L,lenth);// 规则5对于任意的候选项v=(O,T)∈L,若 入候选列表 ITl≥minT,则v是当前时刻的一个关闭蜂群模式. 11:foreach candidate veL do 由于候选列表中每个候选项(O,T)的目标集O l2:iflu.Tl≥minT then L←-L.esU{v}; 是最大目标集，满足目标关闭模式(objectClosed 13:foreach cluster ceC:do pattern）,且IO1≥minO,同时时间集T一直被更新 14:if lel≥min 0 then 为最大时间集，若ITI>minT,即相对当前时间是时 15: candidate v'←-e,{t,}）; 间关闭模式(timeClosed pattern).所以满足目标关 16: insertCanList(v',L,lenth); 闭和时间关闭的候选项为关闭蜂群模式。 17:Lnem←-L: 3.3算法描述 Subroutine:insertCanList(u,L,lenth)/插入规则 CLUR算法仅维护一个候选列表，在每个时间 l8:exist←-false; 戳依次按规则1、规则2和规则3更新候选列表，在 l9:fori←0 to lenth do 更新中需要插入新的候选项时，按照规则4插入候 20:if v.0=v.0,vL.get (i)then 选项.每个时间戳结束时通过规则5实时发现当前 21: exist--true;break 时刻的关闭蜂群模式 22:if exist false then 算法1是CLUR算法的伪代码，每个时间戳执 23:for ilenth to L.lenth do 行该算法之前，本文采用了DBSCAN算法对每个时 24: if v.0=v.0,vL.get (i)then 间戳获取的移动目标位置进行聚类，聚类得到簇的 25: vT←-vTUu.T:break; 集合标记为C:,算法维护的候选列表采用线性列 26:if exist flase then 表数据结构，伪代码第2~10行描述了对候选列表 27:L←-LU{}; 中所有候选项进行更新，首先判断是否满足规则1 CLUR算法由聚类结果组合所有最大的移动目 的条件，若满足则按规则1进行更新，否则按规则2 标组合，因此最大目标集的个数和聚类结果紧密相 进行更新：13~16行描述了规则3的操作，即每个 关，聚类的结果对算法的运行效率有很大影响.当 时间戳得到的簇都是该时间戳的最大移动目标集。 前时间戳，在最坏情况下的时间复杂度为O(IL!× insertCandidateList子函数(l8~27行)描述了候选 IC:),而1L|又和前i-1个时间戳的聚类结果有 项插入规则，插入规则尽可能减少候选列表中候选 关，所以算法在最坏情况下的时间复杂度和每个时 项的冗余，也保证了经过规则5检测后的模式即为 间戳聚类得到簇的个数成正比，即O(t)=kIC,I× 关闭蜂群模式.11~12行描述了实时发现当前时间 ICeI×…×IC:I(k为常量).DBSCAN算法有Eps 时刻的关闭蜂群模式的过程 和min Pts两个参数，两参数的设置直接影响聚类结 算法1CLUR(L,t,minO,minT,Ci) 果，所以聚类算法的参数设置对算法的效率有较大 输入L:候选列表；t,:当前时间戳；minO和 影响 minT:最小阈值；Ce:聚类集合. 由于算法需要一直维护一个候选列表，所以算 输出La:当前时间戳的候选列表；Lh:当前 法的空间复杂度最坏情况下为kIC,I×IC2I× 时间的蜂群模式列表. …×IC:I(k为常量). l:lenth←-L.lenth;Lreslt←-☑； 4实验测试 2:for i0 to lenth do 3:candidate v←-L.get(i);/取出候选列表中 本文用大规模合成数据对CLUR算法进行了正 第i个候选项 确性验证，同时对CLUR算法和objectGrowth算法在 4:foreach cluster cC.:do 各参数变化下的运行时间进行了对比.所有的算法 5: iflu.O∩cl≥min O then 采用C#实现，整个实验在vs2008环境下进行测试， 6: if.O∩c=v then 实验平台配置为7920处理器，4G内存，操作系统
北 京 科 技 大 学 学 报 第 34 卷 冗余的候选项，提高了算法的效率． 3. 2. 3 关闭蜂群模式检测规则 通过使用候选项更新规则和插入规则，CLUR 在每 个时间戳更新候选列表，在时间戳结束后，从候选列表 中找出关闭蜂群模式的关闭检测，检测规则如下． 规则 5 对于任意的候选项 v =〈O，T〉∈L，若 | T |≥minT，则 v 是当前时刻的一个关闭蜂群模式． 由于候选列表中每个候选项〈O，T〉的目标集 O 是最 大 目 标 集，满足目标关闭模式 ( objectClosed pattern) ，且|O| ≥minO，同时时间集 T 一直被更新 为最大时间集，若 | T | ＞ minT，即相对当前时间是时 间关闭模式( timeClosed pattern) ． 所以满足目标关 闭和时间关闭的候选项为关闭蜂群模式． 3. 3 算法描述 CLUR 算法仅维护一个候选列表，在每个时间 戳依次按规则 1、规则 2 和规则 3 更新候选列表，在 更新中需要插入新的候选项时，按照规则 4 插入候 选项． 每个时间戳结束时通过规则 5 实时发现当前 时刻的关闭蜂群模式． 算法 1 是 CLUR 算法的伪代码，每个时间戳执 行该算法之前，本文采用了 DBSCAN 算法对每个时 间戳获取的移动目标位置进行聚类，聚类得到簇的 集合标记为 Cti ． 算法维护的候选列表采用线性列 表数据结构，伪代码第 2 ～ 10 行描述了对候选列表 中所有候选项进行更新，首先判断是否满足规则 1 的条件，若满足则按规则 1 进行更新，否则按规则 2 进行更新; 13 ～ 16 行描述了规则 3 的操作，即每个 时间戳得到的簇都是该时间戳的最大移动目标集． insertCandidateList 子函数( 18 ～ 27 行) 描述了候选 项插入规则，插入规则尽可能减少候选列表中候选 项的冗余，也保证了经过规则 5 检测后的模式即为 关闭蜂群模式． 11 ～ 12 行描述了实时发现当前时间 时刻的关闭蜂群模式的过程． 算法 1 CLUR ( L，ti，minO，minT，Cti ) 输入 L: 候选列表; ti : 当前时间戳; minO 和 minT: 最小阈值; Cti : 聚类集合． 输出 Lnext : 当前时间戳的候选列表; Lresult : 当前 时间的蜂群模式列表． 1: lenth←L．lenth; Lresult←; 2: for i←0 to lenth do 3: candidate v←L．get( i) ; / /取出候选列表中 第 i 个候选项． 4: foreach cluster c∈Cti do 5: if |v．O∩c|≥min O then 6: if v．O∩c = v then 7: v．T←v．T∪{ ti} ; break; 8: else 9: candidate v' ← ＜ v．O ∩ c，v．T∪ { ti} ＞ ; / /新建候选模式 10: insertCanList( v'，L，lenth) ; / /插 入候选列表 11: foreach candidate v∈L do 12: if |v．T |≥minT then Lresult←Lresult∪{ v} ; 13: foreach cluster c∈Cti do 14: if |c|≥min O then 15: candidate v'←〈c，{ ti} 〉; 16: insertCanList( v'，L，lenth) ; 17: Lnext←L; Subroutine: insertCanList( v，L，lenth) / / 插入规则 18: exist←false; 19: for i←0 to lenth do 20: if v．O = v'．O，v'←L．get( i) then 21: exist←true; break; 22: if exist = false then 23: for i←lenth to L．lenth do 24: if v．O = v'．O，v'←L．get( i) then 25: v'．T←v'．T∪v．T; break; 26: if exist = flase then 27: L←L∪{ v} ; CLUR 算法由聚类结果组合所有最大的移动目 标组合，因此最大目标集的个数和聚类结果紧密相 关，聚类的结果对算法的运行效率有很大影响． 当 前时间戳 ti在最坏情况下的时间复杂度为 O( | L | × | Cti | ) ，而| L | 又和前 i － 1 个时间戳的聚类结果有 关，所以算法在最坏情况下的时间复杂度和每个时 间戳聚类得到簇的个数成正比，即 O( t) = k | Ct1 | × | Ct2 | × … × | Cti | ( k 为常量) ． DBSCAN 算法有 Eps 和 min Pts 两个参数，两参数的设置直接影响聚类结 果，所以聚类算法的参数设置对算法的效率有较大 影响． 由于算法需要一直维护一个候选列表，所以算 法的空间复杂度最坏情况下为 k | Ct1 | × | Ct2 | × … × | Cti | ( k 为常量) ． 4 实验测试 本文用大规模合成数据对 CLUR 算法进行了正 确性验证，同时对 CLUR 算法和 objectGrowth 算法在 各参数变化下的运行时间进行了对比． 所有的算法 采用 C#实现，整个实验在 vs2008 环境下进行测试， 实验平台配置为 I7--920 处理器，4 G 内存，操作系统 ·40·
第1期 齐悦等：一种实时有效的蜂群模式挖掘算法 ·41· 为Windows7. 4.2性能测试 测试实验使用的合成数据采用Brinkhoff实 本小节对CLUR算法和objectGrowth算法的运 现的基于网络的移动目标生成器合成，包括200个 行效率进行了比较 移动目标、400个时间戳的数据，并提取前200个时 4.2.1效率测试 间戳的较稳定的数据，共4×10条数据 DBSCAN算法参数设置：Eps=40,min Pts=4, 4.1正确性验证 蜂群模式参数minO和minT都设为8，时间戳从0 DBSCAN算法的参数设定为Eps=40,min 开始到200，每10个时间单位执行挖掘算法，分别 Pts=4进行聚类，给定的阈值minO和minT都设置 记录CLUR算法和objectGrowth算法运行时间. 为8.在时间戳0至200之间每隔10个时间戳分别 运行时间分析如图2(b)所示，objectGrowth算 执行objectGrowth和CLUR算法对数据进行挖掘，记 法在各时间戳的执行过程是相互独立，随着时间戳 录挖掘出的关闭蜂群模式及个数.对测试数据的分 的增加，运行时间势必递增，运行时间如图2(b)中 析如图2(a)所示.CLUR算法发现的关闭蜂群模式 所示.CLUR算法记录的是当前时刻的运行时间，由 个数和objectGrowth算法一致，且挖掘出的蜂群模 于CLUR执行过程在前一时间戳的基础上，仅处理 式和objectGrowth对比的正确率达100%，充分验证 当前时间戳的移动目标位置，运行时间相对非常短， 了CLUR算法的正确性. 如图2(b). 400r (a) 60 0.16 (b) 300 50 CLUR 0.12 objectGrowth 40 30 0.08 -objectGrowth 0.04 10 CLUR 0房导2R元88里3832玉 30 60 90120150180210 时间截 时间登 图2CLUR和objectGrowth算法比较.(a)关闭蜂群模式数：(b)运行时间 Fig.2 Comparison of CLUR and objectGrowth algorithms:(a)number of closed swarm pattemns:(b)running time 4.2.2聚类参数Eps和min Pts对算法的影响 算法的总运行时间和objectGrowt山h算法的运行时间 在参数minT=8和minO=8的情况下，通过改 进行了对比测试 变聚类参数Eps和min Pts的大小，对运行2O0个时 从图3(c)可以看出：minT对CLUR算法基本 间戳的CLUR算法的总运行时间和objectGrowth算 没有影响，因为CLUR本身仅从聚类结果组合最大 法的运行时间进行了对比测试. 移动目标集，所以inT不会影响算法的运行时间， 图3(a)和(b)显示了Eps和min Pts对算法的 仅会影响发现关闭蜂群模式的数量；随着minT的增 影响.随着Es的增长，聚类得到的簇间差异较小， 加，objectGrowth算法剪枝掉的搜索空间越大，效率 蜂群模式个数会迅速递增，CLUR算法的运行时间 也会越来越高.从图3(d)可以看出：随着minO的 也随着递增，而objectGrowth算法同样会受聚类结 增加，CLUR算法的候选蜂群模式列表增长较慢，运 果的影响，运行时间也急速递增.随着min Pts的减 行时间也会越短，但运行时间由聚类时间和发现时 少，每个时间戳聚类得到的簇的个数增多，但簇内的 间组成，聚类时间没有变化，运行时间缩短的程度并 目标数目减少，由于CLUR算法最大移动目标集根 不明显；对objectGrowth来说，minO只用于关闭模式 据阈值inO入候选列表，候选列表的个数并未急 的检测，对算法基本没有影响 速增加，因此CLUR算法的运行时间并未急速增加： 综合上述实验可以看出：CLUR算法的效率高 而objectGrowth算法同样会受min Pts的影响，运行 于objectGrowth算法；聚类参数Eps和minPts对 时间较CLUR算法增长更快. CLUR算法有一定影响，但算法中采用了阈值minO 4.2.3蜂群模式阈值min0和minT对算法的影响 入候选列表的策略减少了这种影响，且相对CLUR 设定聚类参数Eps=40,min Pts=4,通过对蜂 来说，objectGrowth同样受较大影响；minO和minT 群模式参数的改变，对运行200个时间戳的CLUR 对CLUR算法基本没有影响
第 1 期 齐 悦等: 一种实时有效的蜂群模式挖掘算法 为 Windows 7． 测试实验使用的合成数据采用 Brinkhoff ［16］实 现的基于网络的移动目标生成器合成，包括 200 个 移动目标、400 个时间戳的数据，并提取前 200 个时 间戳的较稳定的数据，共 4 × 104 条数据． 4. 1 正确性验证 DBSCAN 算法的参数设定为 Eps = 40，min Pts = 4 进行聚类，给定的阈值 minO 和 minT 都设置 为 8． 在时间戳 0 至 200 之间每隔 10 个时间戳分别 执行 objectGrowth 和 CLUR 算法对数据进行挖掘，记 录挖掘出的关闭蜂群模式及个数． 对测试数据的分 析如图 2( a) 所示． CLUR 算法发现的关闭蜂群模式 个数和 objectGrowth 算法一致，且挖掘出的蜂群模 式和 objectGrowth 对比的正确率达 100% ，充分验证 了 CLUR 算法的正确性． 4. 2 性能测试 本小节对 CLUR 算法和 objectGrowth 算法的运 行效率进行了比较． 4. 2. 1 效率测试 DBSCAN 算法参数设置: Eps = 40，min Pts = 4， 蜂群模式参数 minO 和 minT 都设为 8，时间戳从 0 开始到 200，每 10 个时间单位执行挖掘算法，分别 记录 CLUR 算法和 objectGrowth 算法运行时间． 运行时间分析如图 2 ( b) 所示，objectGrowth 算 法在各时间戳的执行过程是相互独立，随着时间戳 的增加，运行时间势必递增，运行时间如图 2( b) 中 所示． CLUR 算法记录的是当前时刻的运行时间，由 于 CLUR 执行过程在前一时间戳的基础上，仅处理 当前时间戳的移动目标位置，运行时间相对非常短， 如图 2( b) ． 图 2 CLUR 和 objectGrowth 算法比较． ( a) 关闭蜂群模式数; ( b) 运行时间 Fig． 2 Comparison of CLUR and objectGrowth algorithms: ( a) number of closed swarm patterns; ( b) running time 4. 2. 2 聚类参数 Eps 和 min Pts 对算法的影响 在参数 minT = 8 和 minO = 8 的情况下，通过改 变聚类参数 Eps 和 min Pts 的大小，对运行 200 个时 间戳的 CLUR 算法的总运行时间和 objectGrowth 算 法的运行时间进行了对比测试． 图 3( a) 和( b) 显示了 Eps 和 min Pts 对算法的 影响． 随着 Eps 的增长，聚类得到的簇间差异较小， 蜂群模式个数会迅速递增，CLUR 算法的运行时间 也随着递增，而 objectGrowth 算法同样会受聚类结 果的影响，运行时间也急速递增． 随着 min Pts 的减 少，每个时间戳聚类得到的簇的个数增多，但簇内的 目标数目减少，由于 CLUR 算法最大移动目标集根 据阈值 minO 入候选列表，候选列表的个数并未急 速增加，因此 CLUR 算法的运行时间并未急速增加; 而 objectGrowth 算法同样会受 min Pts 的影响，运行 时间较 CLUR 算法增长更快． 4. 2. 3 蜂群模式阈值 minO 和 minT 对算法的影响 设定聚类参数 Eps = 40，min Pts = 4，通过对蜂 群模式参数的改变，对运行 200 个时间戳的 CLUR 算法的总运行时间和 objectGrowth 算法的运行时间 进行了对比测试． 从图 3( c) 可以看出: minT 对 CLUR 算法基本 没有影响，因为 CLUR 本身仅从聚类结果组合最大 移动目标集，所以 minT 不会影响算法的运行时间， 仅会影响发现关闭蜂群模式的数量; 随着 minT 的增 加，objectGrowth 算法剪枝掉的搜索空间越大，效率 也会越来越高． 从图 3( d) 可以看出: 随着 minO 的 增加，CLUR 算法的候选蜂群模式列表增长较慢，运 行时间也会越短，但运行时间由聚类时间和发现时 间组成，聚类时间没有变化，运行时间缩短的程度并 不明显; 对 objectGrowth 来说，minO 只用于关闭模式 的检测，对算法基本没有影响． 综合上述实验可以看出: CLUR 算法的效率高 于 objectGrowth 算 法; 聚 类 参 数 Eps 和 minPts 对 CLUR 算法有一定影响，但算法中采用了阈值 minO 入候选列表的策略减少了这种影响，且相对 CLUR 来说，objectGrowth 同样受较大影响; minO 和 minT 对 CLUR 算法基本没有影响． ·41·