移动终端位置信息聚类技术在公共安全领域的应用

李伟　陈忠红

摘要：移动通信、互联网及空间定位技术的成熟极大地促进了LBS（Location Based Services）的发展，也产生了越来越多的位置大数据。合理地使用时空数据挖掘技术可有效进行知识发现及价值提取，在追踪目标用户，维护公共安全等方面具有重要意义。本文以移动终端位置信息为研究对象，从推断目标用户敏感信息的角度出发，研究了基于时空数据挖掘的空间位置聚类方法，并总结了当前各类技术的不足，并指出了今后发展方向。

关键词：移动终端；位置信息；聚类技术；公共安全

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）29-0034-02

1 概述

随着移动互联网的普及，网络虚拟世界中人们通过网络ID以匿名方式进行社交活动，使得对违法活动的溯源追踪更加困难。而位置信息是连接现实世界和虚拟世界的桥梁，通过收集手机入网所在基站号，采集手机APP提交地理坐标，网络爬虫采集LBSN上用户签到的语义化地点，甚至直接通过服务提供商获取等途径都可以获取手机位置信息的大数据。近年来，随着大数据时代的兴起，通过机器学习和数据挖掘的手段可以从海量位置数据中获取有价值的信息。在维护公共安全方面，这种方法可以实现对目标人的追踪。

这种跟踪手段可以有很多应用，如网警可以通过分析移动终端社交APP（微信、微博、QQ、人人、陌陌）上传的历史位置信息，可有效追捕在此类社交网站散步不良信息者或网络诈骗者。同样，警察可以通过分析手机基站定位信息，推断犯罪嫌疑人住址，为实施抓捕提供有效情报。

2014年11月20日，在首届世界互联网大会分论坛“网络空间安全和国际合作”上，以色列网络安全专家Shai Schiller发表题为《从大数据当中发现情报》的演讲。他使用Deep Analytics系统检索在Facebook、Twitter等社交平台上与“占中”相关的活跃用户及其消息记录。Deep Analytics系统可以获取这些用户的资料、相互关系、地理位置等，并通过数据挖掘技术进行分析和过滤，查出活动的“重要成员的主要信息、参加活动的地方和参加活动的具体情况”等，并根据历史位置信息，对某个区域“建立一个围墙”，监管区域内所有人的Twitter数据。这一应用充分说明了利用手机位置大数据信息在追踪目标人，维护公共安全中的重要意义。

2 时空数据挖掘实现位置信息聚类

20世纪90年代中后期，数据挖掘领域的一些较成熟的技术，如关联规则挖掘、分类、预测与聚类等被逐渐用于时间序列数据挖掘和空间数据挖掘，以发现与时间或空间相关的有价值的模式。时空数据挖掘是综合利用各种数据挖掘技术从具有海量、高维、高噪声和非线性等特性的时空数据中提取出隐含的、人们事先不知道的、但又潜在有用的信息及知识的过程。对于移动终端位置大数据的分析，在获得时间、空间、用户ID三种属性的条件下，借助时空挖掘技术对位置信息进行聚类分析，可实现对用户敏感信息，如用户居住地位置、用户之间是否存在社会关系、用户即将到达的位置等的推断。

但在现实中，由于人们使用移动设备的习惯不同，很难获得等间隔、规律性的定位信息。更重要的是，由于隐私法规等约束，这种位置信息也并非实时的，而是历史位置信息。这一类数据在位置信息中占较大比重，使得追踪目标人变得更加困难。

然而，研究人员证明，大多数人平时往返于固定的地点，而且活动带有很强的规律性。这就意味着通过对历史位置数据进行有效挖掘，可以推断得知目标住所、工作地点等重要信息。正所谓“跑得了和尚跑不了庙”，通过这种手段，结合目标作息规律，可以预知目标所在位置。

在处理位置信息时，由于用户所在建筑物形状不同、定位误差、采集数据的误差、人为干扰等因素，首先需要抛开时间尺度，对位置进行聚类。所谓聚类（分析）即根据数据中发现的描述对象及其关系的信息，将数据对象分组[24]。算法的种类主要分为基于划分的聚类、基于层次的聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类等5大方法。

1）基于划分的聚类方法

其基本思想是简单地将数据对象集划分为不重叠的子集，从而使每个数据对象恰在一个子集中。假设给定一个包含n个对象或数据的集合，将数据集划分为k个子集，其中每个子集均代表一个聚类（k

2）基于层次的聚类方法

其基本思想是通过将数据组织为若干组并形成一个相应的树来进行聚类的，可分为自顶向下的分裂算法和自底向上的凝聚算法两种。分裂聚类算法，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或达到了某个终止条件。而凝聚聚类算法则相反，首先将每个对象作为一个簇，然后将相互邻近的簇合并为一个大簇，直到所有的对象都在一个簇中，或达到了某个终止条件。其代表算法有CURE、ROCK、BIRCH等。

3）基于密度的聚类方法

其基本思想是利用数据集本身的结构特征，判断某一区域内数据集的密度来判断是否归类的方法。密度聚类算法的优点是，它能够应用于任何形状的数据集处理中，而且它不用预先设定类的数量。基于密度的方法可用来过滤“噪音”孤立点数据，以发现任意形状的簇"其主要思想是只要临近区域的密度（样本数目）超过某个阀值则继续聚类。即对于给定簇中的每个样本，在一个给定范围的区域中必须至少包含某个数目的样本。

4）基于网格的聚类方法

基于网格的空间聚类方法采用了一个多分辨率的网格数据结构.该类算法首先将数据空间划分为有限个单元的网格结构，所有的处理都以单个的单元为对象.这样处理的一个突出的优点就是处理速度快，通常与目标数据库中记录的个数无关，只与把数据空间分成多少个单元有关。代表算法有STING、Wavecluster和CLIQUE算法。

5）基于模型的聚类方法

基于模型的取类方法为每个簇假定一个模型，并在数据中寻找对给定模型的最佳拟合。目前主要研究的是利用概率统计模型进行概念取类和利用神经网络技术进行自组织聚类等方面。它们面对的主要问题仍然是如何适用于大数据源的聚类应用。基于模型的空间聚类方法包括基于统计的空间聚类方法和基于神经网络的空间聚类方法等。如EM、COBWEB、SOM算法等。是给每一个聚类假定一个模型，然后去寻找能够很好地满足这个模型的数据集。

1996年，Martin Ester等人提出了一种DBSCAN算法[1]，该算法采用空间索引技术来搜索对象的邻域，引入了“核心点”、“边界点”、“噪声点”和“密度可达”等概念，如图 2所示，从核心点出发，以超球状区域内数据对象的数量来衡量此区域密度的高低，把所有密度可达的对象组成一个簇。该算法可以发现任意形状的簇，能够有效排除噪声点和离群点。

然而，DBSCAN算法存在许多不足，如对输入参数敏感，致使参数选择困难等。针对这一问题，Feng Pingjiang提出了一种自适应DBSCAN算法[3]，该算法在选取固定minPts的条件下，采用不同的Eps参数进行聚类，最后对每次聚类的有效性进行对比，并从中取最优。这种方法通过“试”的方法，在一定程度上解决了参数选取问题，但也带来了可观的时间代价。夏鲁宁等人[4]提出了一种SA-DBSCAN算法，该算法通过分析数据集统计特性以确定Eps和MinPts参数，避免了聚类分析过程中的人工干预，防止了人为选择参数不当带来的误差，实现了聚类分析的自动化。

2014年，Alex Rodriguez等人在《Science》上提出了一种新型、简洁、高效的聚类算法[2]。该算法的假设是类簇的中心由一些局部密度比较低的点围绕，并且这些点距离其他有高局部密度的点的距离都比较大。通过计算最近邻距离，得到聚类中心，并依据密度大小排序，将剩余点划分至所属类别。该算法只需计算一次距离，且不需要参数，不需迭代，可针对各种类型的点集进行聚类。

空间位置数据具有高维度、非线性、稀疏性等特征，因此在选用聚类算法上应综合考虑数据特性。基于划分的聚类方法需要给出簇的个数，而采集的位置数据没有这一先验信息。而人类活动一般具有较强的规律性，因此，所到重点区域通常较为频繁，抛开时间维度，从空间看，这就造成了重点区域密度不同。基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合于对未知内容的数据集进行聚类[5]。

3 总结

本文研究了空间位置聚类、对时空挖掘技术在移动终端位置信息推断在公共安全领域的应用。以下将对目前聚类方法中存在的问题以及在这些问题上所做的改进做一个总结：

1）从以上对传统的聚类分析方法所做的总结来看，不管是k-means方法，还是CURE方法，在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在现实数据中，聚类的数目是未知的，通常要经过不断的实验来获得合适的聚类数目，得到较好的聚类结果。

2）随着信息时代的到来，对大量的数据进行分析处理是很庞大的工作，这就关系到计算效率的问题。有文献提出了一种基于最小生成树的聚类算法，该算法通过逐渐丢弃最长的边来实现聚类结果，当某条边的长度超过了某个阈值，那么更长边就不需要计算而直接丢弃，这样就极大地提高了计算效率，降低了计算成本。

3）目前的许多算法都只是理论上的，经常处于某种假设之下，比如聚类能很好地被分离，没有突出的孤立点等，但是现实数据通常是很复杂的，噪声很大，因此如何有效的消除噪声的影响，提高处理现实数据的能力还有待进一步的提高。

参考文献：

[1] Ester M， Kriegel H， Sander J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise.[C]. In： Kdd.1996. 226-231.

[2] Rodriguez A， Laio A. Clustering by fast search and find of density peaks[J]. SCIENCE. 2014， 344（6191）： 1492-1496.

[3] Pingjiang F， Lindong G. Adaptive DBSCAN-based algorithm for constellation reconstruction and modulation identification[C]. In： Radio Science Conference， 2004. Proceedings. 2004 Asia-Pacific.IEEE， 2004. 177-180.

[4] 丰江帆，熊雨虹. 一种基于个人位置信息的重要地点识别方法[J]. 小型微型计算机系统，2013（3）： 503-507.

[5] Kumar N， Sivasathya S. Density-Based Spatial Clustering with Noise–A Survey[J]. 2014.

[6] Vesanto J， Alhoniemi E. Clustering of the self-organizing map[J]. Neural Networks， IEEE Transactions on. 2000， 11（3）： 586-600.