基于子空间聚类算法的时空轨迹聚类.docx

第 ３０卷 第 ４期２０１４年 ７月地理与地理信息科学 ＧｅｏｇｒａｐｈｙａｎｄＧｅｏ－ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅＶｏｌ．３０ Ｎｏ．４ Ｊｕｌｙ２０１４ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６７２－０５０４．２０１４．０４．００２基于子空间聚类算法的时空轨迹聚类马 林 兵，李鹏（中山大学地理科学与规划学院 ，广 东 广州 ５１０２７５）摘要 ：已有的时空轨迹聚类方法一般以整条轨迹作为聚类单元 ，聚类效果较低 且不能识别轨迹局部特征 ；另 一种轨 迹聚类方法是以划分后轨迹段为聚类单元 ，算法效率较低且不能很好地支持多 属性聚类。 该文提出基于子空间聚 类算法的时空轨迹聚类。首先引入数据归约的思想 ，将轨迹进行离散化处理 ，再 运用 ＣＬＩＱＵＥ 算法对 离 散 化 后 的 轨迹段进行聚类。实验结果表明 ，此轨迹聚类方法 具有较高的伸缩性 ，能有效地处理多维轨迹数据并识别轨迹的 局部聚类特征 ，能揭示时空轨迹在不同子空间的运动规律 。关键词 ：轨 迹聚类 ；子 空间 ；ＣＬＩＱＵＥ 算法中图分类号 ：Ｐ２０８ 文献标识码 ：Ａ 文章编号 ：１６７２－０５０４（２０１４）０４－０００７－０５０ 引言随着遥感、ＧＰＳ、无 线通讯、智 能终端、物 联网等 技术的发展，人们可以获得 大量的时空轨迹数据 ，如 移动用户的空间行为轨迹 、车 辆的行驶轨迹、动 物的 迁徙轨迹、飓 风 的 移 动 轨 迹 等［１－３］。 越 来 越 多 的 轨 迹数据被应用于时间地理学 、交 通地理学、生 态地理 学、医学等相关研 究［４－７］，这 些轨迹中蕴含着大量有 价值的信息与知识。 通过对这些时空轨迹数据进行 聚类分析，可以提取时空轨迹数据中的相似性与异常 特征，并有助于发现其中有意义的轨迹模式［５，８－１３］。目前，轨迹聚类的主要方 法可分为两类 ：一 类是 以整条轨迹为分类对象进行 分 类［１２，１４］，其 在 评 价 轨 迹对象之间的相似性方面比较直观 ，用 户输入参 数 的影响比较小，但是对于复 杂的轨迹，此 类方法无法 分辨出轨迹的局部特征 ，且 对高维度的轨迹数据 的 聚类效果不 好［９］；另 一 类 是 将 复 杂 轨 迹 按 照 某 种 标 准分割为相对平滑的轨迹段 ，然 后以分割得到的 轨 迹段为分类对象进行分类［１０］，可 以很好地识别轨迹 的局部特征，有效地处理高 维度的轨迹数据 ，结 合基 于密度的聚类方法，能 够很好地发现任意形状的 轨 迹段聚类。但是轨迹分割方法对聚类结果有较大的 影响，不 少 专 家 学 者 提 出 了 许 多 不 同 的 分 割 方 法［８－１０，１３，１５］，适用于不同 的应用领域 ，领 域知识对聚 类结果的影响较大。从已有的研 究 成 果 来 看，大多是利用移动对象 轨迹的空间形态进行聚类 ，但 是对于具体应用而言，轨迹除了具有空间形态特征之外 ，移 动对象本身 在 轨迹不同位置还具有多维度的非空间属性信息。 因 此，本文引入数据归约的思 想对轨迹进行划分 ，利 用ＣＬＩＱＵＥ（ＣｌｕｓｔｅｒｉｎｇＩｎ Ｑｕｅｓｔ）聚 类 算 法［１６］对 划 分 后的数据集进行聚类分析 ，提 出一个时空轨迹离 散 化及其子空间聚类的方法，并进行了验证。１ 子空间聚类算法子空间聚类算法又称 ＣＬＩＱＵＥ 算法，其 基本思 想是：将数据空间划分为互 不相交的长方形单元，统 计每个单元中的数据密度 ，根 据设定的模型参数 识 别其中的密集单元。簇被定义为相连的密集单元的 最大集合。对 于 每 个 簇，它 确 定 覆 盖 相 连 的 密 集 单 元的最大区 域，然 后 确 定 最 小 覆 盖。 此 方 法 处 理 速 度快，处理时间仅依赖于 量化空间中每一维上的 单 元数目，且能有效处理多维数据［１６，１７］。ＣＬＩＱＵＥ 算法的基本流程如下 ：１）给 定一 个 高 维数 据，其 在 数 据 空 间 中 的 分 布 通 常 是 不 均 衡 的。 首先将高维数据空间分割为有限的网格单元 ，利 用 每个网格单元中数据点的密度判定数据的全局空间 分布模式，并 通过用户设定的阈值识别其中的密 集 单元，该步 骤对数据空间中 的 每 一 维 进 行。 如 果 想 要找出包含聚类的子空间 ，最 直接的方法就是由 用 户划分数据空间中的每一维 ，然 后根据每一维的 划 分将数据空间划分为不同单元 ，之 后统计每个单 元 中的数据密度，从 而根据用户设定的密度阈值识 别 高密单元。２）这一步的输 入是由步骤 １ 生成的密集收稿日期 ：２０１３－１０－１５； 修回日期 ：２０１４－０１－１０基金项目 ：“十 二五”国家科技支撑项目（２０１３ＢＡＪ１３Ｂ０４）作者简介 ：马 林兵（１９６８－），男 ，博 士 ，副 教授 ，主要