文档介绍：摘 要
随着计算机术、数据获取技术和存储技术的快速发展，在短时间内，各种大量的资
料被收集，需要从大规模的数据库中抽取有潜在使用价值的、隐含的、非平凡的、未知
的信息，因而产生了数据挖掘技术。随着大量移动对象路径数据如车辆位置数据、轮船
运动路径数据、台风路径数据以及动物移动数据等被收集，需要发现这些隐藏在路径数
据中的模式以便进行规划设计、分类研究等，还需要发现隐藏在这些数据中的异常信息
以便及时防范。因此，本文将数据挖掘中的聚类分析和孤立点挖掘技术应用于移动对象
的路径分析中，提出了两种算法分别用于路径聚类和异常路径检测。
本文首先分析了移动对象的路径特点，讨论了几种路径的表示方式与划分方法。再
对划分后的子路径使用最长公共子序列来度量它们之间的相似性，得到子路径之间的相
似度矩阵。
在聚类分析方面，分析了 DBSCAN（Density Based Spatial Clustering of Applications
with Noise）算法，并指出其应用于移动对象路径聚类时的局限性，提出了基于对称邻
域 的 快 速 路 径 聚 类 算 法 （ the Fast Path Clustering Algorithm based on Symmetric
Neighborhood, FPCSN）。FPCSN 算法引入了密度因子的概念。通过查询子路径的 k 邻域
和反向 k 邻域得到子路径的密度因子，再对子路径进行聚类，并对邻域的查询操作进行
优化。该算法能够从大的、稀疏的数据集中识别出小、的稠密的数据集，实现了多密度
数据集的快速聚类，并降低了查询时间提高了算法效率。
在异常路径检测方面，分析了 LOF（Local Outlier Factor）算法，针对该算法应用
于移动对象异常路径检测时的局限性，提出了基于平均相似度的异常路径检测算法（the
Detection Algorithm of Abnormal Path based on the Average Similarity, APAS）。APAS算法
通过单个子路径相似度与平均相似度的比较，初步去除非孤立子路径，得到候选孤立子
路径集。减少了子路径的查找次数，提高了效率。另外，本算法还应用了对称邻域的概
念，使得该算法能够识别多密度的路径集中的异常子路径，提高识别的准确率。
最后，本文开发了 移动对象路径检测系统，将 FPCSN 和 APAS算法应用到该系统
中，使得该系统能够用于对移动对象路径进行聚类分析和异常路径检测。实验表明，
FPCSN 算法和 APAS算法分别能够对移动对象的路径数据进行聚类和异常路径检测，检
测结果具有较好的质量，并在算法性能方面有了一定的提高。
关键词：聚类；相似度；FPCSN；APAS
I
Abstract
With the rapid development of computer, data acquisition and storage technology, a large
amount of data are collected in the short time. The information which has potential value is
needed to be extracted from large ,data mining technique appeared.
Nowadays,a large number of data which are produced by moving objects are collected , Such
as the paths produced by moving vehicles, ships, hurricane, animals and so on. So it is needed
to find the hided information in these data in oder to plan or research. Also it is needed to find
the abnormal information in order to provide some security measure. In this th