一种基于人员行为规律和数据挖掘方法的群体识别方法

摘要

本发明公开了一种基于人员行为规律和数据挖掘方法的群体识别方法，属于数据挖掘领域，尤其涉及一种基于人员行为规律的大型活动中重点群体识别的方法。利用人员的轨迹数据信息抽取其停留区域及人员去往各个停留区域的频繁度，然后基于提取出的人员停留区域信息，进一步提取各区域语义信息以更准确表达用户行为，结合人员行为规律和特征相似度，利用数据挖掘方法进行群体聚类，最终从目标人群中识别出重点特殊群体。

说明书

技术领域

本发明属于数据挖掘领域，涉及一种基于人员行为规律的大型活动中重点群体识别的方法。

背景技术

随着市场经济活动的增多和人民物质文化生活水平的提升，各种大型活动的举办愈加频繁，这些大型活动对活动的安全进行、预防突发事件提出了严峻的挑战。而做好大型活动的安全防范工作极其重要的首要问题就是如何识别目标人群中的特殊群体以提前做好预防工作。同时无线通信技术的飞速发展催生了大量的移动对象数据，这些数据刻画了个体和群体的时空动态性，蕴含着移动对象的行为信息，通过分析目标人员移动数据可以帮助人们了解目标人员行为规律、群体动向等。

而近年来，卫星通信、GPS设备、RFID、无线传感器、物联网通信、视频跟踪等技术的不断发展与广泛应用，使得全球范围内的各种大小的移动对象都得到较为准确定位和有效跟踪。通过这些技术，信号接收设备可以从定位终端上采集到大量移动对象数据，这些数据蕴含着非常丰富的信息，比如位置信息、时间信息等，而且随着时间的推移，数据量会变得越来越庞大、复杂。同时这些移动对象数据也成为了一种新的数据分析途径，尤其是在重大活动事件之前，研究相关群体的运动轨迹可以帮助人们进行群体识别、了解群体动向、分析群体行为规律，进而使人们可以有针对性地为大型活动做好预防工作。

该技术采用数据挖掘中的聚类方法挖掘数据信息，相似人群往往具有相似特征，根据提取出的人员特征信息数据，设计人员之间相似度计算公式，选取适当的聚类算法，从目标人群中识别出重点特殊群体。

发明内容

本发明提供一种基于人员行为规律和数据挖掘方法的群体识别方法，利用人员的轨迹数据信息抽取其停留区域及人员去往各个停留区域的频繁度，然后基于提取出的人员停留区域信息，进一步提取各区域语义信息以更准确表达用户行为，结合人员行为规律和特征相似度，利用数据挖掘方法进行群体聚类，最终从目标人群中识别出重点特殊群体。

一种基于人员行为规律和数据挖掘方法的群体识别方法，该方法的步骤为：

步骤一：用人员的轨迹数据信息抽取其停留区域及人员去往各个停留区域的频繁度。

步骤1.1：提取人员单条轨迹停留点。停留点表示人员停留一段时间的地理位置，通过从人员轨迹提取出的每一个停留点都和真实的地理位置相关联，这些地理位置能够在某种程度上反应人员的活动情况。定义单条轨迹为T＝(p₁,p₂,…,p_n)，其中p_i＝(lat_i,lon_i,t_i),0≤i≤n，(lat_i,lon_i)表示位置点i处的经纬度，t_i表示处于位置点i处的时间。

给定一段轨迹序列t＝(p_i,…,p_i+m)，如果distance(p_i,p_x)≤θ_d，|t_i-t_x|≥θ_t，i≤x≤i+m，p_x表示轨迹序列中的第x个轨迹点，m是一个0到n-i之间的整数，θ_d和θ_t分别为地理距离阈值和时间阈值，则p(lat,lon)即为停留点，其中

步骤1.2：人员在经常到访的区域停留点多，反之，在少到访的区域停留点少。DBSCAN算法应用在此处时间复杂度较高而且输入参数较多，因此设计一种简单聚类算法(SC)，速度较快且只需要一个输入参数即距离阈值τ，通过遍历每个停留点，将每个停留点指派到和它距离小于τ的簇中，如果没有任何一个簇和此点的距离小于τ，则此点自己作为一个新簇。

每个簇即为一个停留区域，记为为此停留区域中所有点，lat和lon为此停留区域点集的中心点，r为此停留区域的半径。

步骤二：基于提取出的人员停留区域信息，并进一步提取各区域语义信息。

步骤2.1：有时候仅通过地理位置信息并不能准确判断人员之间的关系，还需要停留区域的语义信息。POI(Point of information)描述了这些地理实体的空间和属性信息，如实体的名称、地址、种类和坐标等，因此在很大程度上增强了对实际地理位置的描述能力，一定程度上能够反映出用户行为活动。多数情况下人员停留区域语义信息并不单一，因此不能简单地将停留区域内的所有类别信息归结为一种，而是要记录多种类别及其占比，sem＝(<catg₁,freq₁＞,<catg₂,freq₂＞,…,<catg_n,freq_n＞),n≥1。sem表示停留区域中的语义信息，<catg₁,freq₁＞表示第一种语义信息的类别和人员到访此语义对应地理位置的频度。

采用LDA主题模型对停留区域内语义信息进行建模，将停留区域内的POI信息类比成文档，区域中的语义信息比成主题，每个POI作为单词。使用建模模型抽取出每个人员停留区域内的语义信息，首先将人员所有停留区域POI信息当作输入数据对模型进行训练，进而利用训练好的模型推测出每个停留区域内的语义信息。

将抽取语义信息之后的停留区域重定义为为停留区域以r为半径的圆内的代表性语义信息。

步骤2.2：去除无意义语义信息。

A人员的语义信息集合为(<住宅区,150>，<咖啡厅,5>，<健身房,45>)，B人员的语义信息集合为(<住宅区,200>，<科研机构,59>，<音乐厅,3>)，圆括号内的两项表示语义位置信息(简单描述起见，这里只用一种语义信息代表该区域语义)和到访该位置的频度。可以看出，在这个例子中，“住宅区”这项在两者的语义信息集合中占有较大权重，“住宅区”在比较两者语义信息相似性上不具有实际意义甚至是一个干扰项，去掉干扰项后的A与B真实相似度很低。

通常“住宅区”语义信息应该是人员们共同拥有的语义信息，每个人的轨迹语义信息都会包含该信息，该语义信息的明显特征就是到访频度高，停留时间段固定。去除无意义语义信息方法过程如下：

1)循环判断每条语义信息，从区域语义信息上判断该区域是否可能是住宅区，若是，转2)，否，转4)；

2)判断该停留区域内所有停留点平均停留时间分布是否正确，若是，转3)，否，转4)；

3)从语义信息集合中删除该语义信息；

4)跳出循环；

步骤三：结合人员行为规律和特征相似度，利用数据挖掘方法进行群体聚类，最终从目标人群中识别出重点特殊群体。

步骤3.1：相似性度量

从两方面来考虑相似度的计算，地理位置相似度和语义位置相似度。

第一方面，地理位置相似度。采用余弦相似度的扩展Tanimoto系数来比较两人相似度，不同于余弦相似度，它考虑了频度及向量长度的影响。给定人员A和人员B，两人地理位置频度向量分别为la和lb，表示为：

在判断两地理位置是否相同时，由于定位设备本身的误差，需要通过两个地理位置区域中停留点的重叠程度判断它们的位置关系。两个停留区域的重叠程度，或者说相似度定义为两区域相交区域内属于包含较少停留点的区域内的停留点数和包含较少停留点的区域内的所有停留点个数的比率。然后将该相似度作为权值加入到Tanimoto系数中形成新的加权地理位置相似性度量。公式如下：

第二方面，语义位置相似度。给定某个停留区域内的语义信息为sem＝(<c₁,f₁＞,<c₂,f₂>,...<c_n,f_n＞),n≥1，f_i代表c_i的概率，所以有在比较两停留区域内的语义信息是否相同时，和判断地理位置是否相同类似，也要考虑两者的相似程度。sem中包含了语义信息的概率分布(f₁,f₂,…,f_n)，因此使用KL距离来衡量两者概率分布距离。

在概率论和信息论中，KL距离(Kullback-Leibler Divergence)用来衡量相同事件空间里的两个概率分布的差异情况。给定A人员和B人员的某个停留区域中的语义信息集合概率分布分别为fa(x)和fb(x)，fa(x)和fb(x)之间KL距离表示为：

KL距离不具有对称性，即D_KL(fa||fb)≠D_KL(fb||fa)，所以它并不是一个真正的度量或者距离。JS距离是KL距离的对称改进，并且将距离定义在[0,1]的闭区间上。公式如下：

如果δ是两者语义信息的距离阈值，semA和senB分别是人员A和人员B的所有停留区域的语义信息集合，则两区域语义信息相似。

两人语义位置相似度计算方式同地理位置相似度计算方式一样，采用Tanimoto系数，公式如下：

sa和sb分别为两人语义信息频度向量，w为上文提到的JS距离组成的向量。

有了地理位置相似度和语义位置相似度，两人相似度定义两者的加权和，公式如下：

sim(A,B)＝∝·sim_loc(A,B)+(1-∝)·sim_sem(A,B)(6)

其中∝是一个处于[0,1]区间的值，它决定了语义信息的权重。

步骤3.2：群体聚类

采用一种基于共享最近邻的聚类，包含一个很重要的SNN相似度概念，SNN相似度表示两个对象的k近邻中公共项个数。正是由于SNN的特性，使得它擅长处理噪声和离群点，并且能够处理不同大小、形状和密度的簇，尤其擅长发现强相关对象的紧致簇。

在群体聚类中，分为三步进行聚类。第一步，根据人员特征信息数据和相似度量公式构造SNN邻近度矩阵，第二步利用邻近度矩阵构造SNN相似度图，第三步找出相似度图的所有连通分支，每个连通分支是一个簇，去掉只有一个点的簇，剩下的每个簇即为一个群体。通过设置合理最近邻个数k和SNN相似度阈值γ，有效地找出人群中有紧密关系的重点群体。

首先在构造邻近度矩阵算法中计算每个人员的k近邻人员，随后计算人员之间的SNN相似度，如果两人的共享最近邻个数超过阈值eps，即这两人在图中是连通的，因此在邻近度矩阵两人ID对应的位置记为1，如此往复保存所有人，直到SNN邻近度矩阵构建完成。然后利用SNN邻近度矩阵来构建图，在这里用邻接表数组表示构建图，邻接表是图的常用存储结构之一，邻接表将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的一张链表中。在构造SNN相似度图算法中，要添加一条v1与v2之间的边，将v1添加到v2的邻接表中并把v2添加到v1的邻接表中，直到添加完所有的边，便构建完成图。最后利用发现连通分支算法中查找图的所有连通分支，在这里使用深度优先搜索来探索图的连通性问题，因为深度优先搜索的时间复杂度和空间与V+E成正比，在常数时间内处理关于图的连通性查询。

附图说明

图1：系统流程图。

图2：人员轨迹图。

图3：人员停留点图。

图4：人员停留区域图。

图5：人员语义信息图。

图6：人员000与003的停留点位置图。

图7：人员007与036的停留点位置图。

图8：人员006与023的停留点位置图。

图9：群体聚类流程图。

图10：Silhouette index(轮廓系数)随k值变化图。

图11：Dunn index(邓恩指数)随k值变化图。

图12：k＝12或k＝13时的相似度矩阵图。

图13：聚类数目随k值变化图。

图14：k＝15时的相似度矩阵图。

图15：k＝19时的相似度矩阵图。

图16：k＝21时的相似度矩阵图。

具体实施方式

下面结合相关附图对本发明进行解释和阐述：

本发明采用的数据集是微软的开源项目Geolife，这个项目中收集了182名志愿者在五年间的GPS轨迹数据(2007.4～2012.8)。这个数据集中包含了17621条轨迹，总里程1292951千米，总时长50176小时。每条轨迹包含时间戳，经纬度和海拔。这些轨迹由不同的GPS采样设备采集，其中91.5％的采样都很密集，每隔5秒或每5～10米一个点。该数据集记录了广泛的人员户外活动，不仅包括回家和上班等生活习惯，还有一些娱乐和体育活动，如购物，观光，餐饮，徒步旅行和骑自行车。虽然这个数据集大量分布在中国30多个城市，甚至在美国和欧洲的一些城市，但大部分数据都是在北京海淀。

POI数据集采集自高德地图其包含北京市海淀区156500条对象，每条对象包含名称、地址、类别及三种坐标系下的坐标。

步骤一：用人员的轨迹数据信息抽取其停留区域及人员去往各个停留区域的频繁度。

附图2展示了一名学生几天时间内的运动轨迹，其中每种颜色标记的轨迹代表该人一天的运动轨迹。按照单条轨迹停留点提取方法提取停留点，提取出该人的停留点见附图3，然后对该人员所有停留点应用SC算法以划分停留区域，划分结果见附图4。

步骤二：基于提取出的人员停留区域信息，进一步提取各区域语义信息。

根据LDA主题模型计算该学生停留区域语义信息，部分语义信息见附图5。

步骤三：结合人员行为规律和特征相似度，利用数据挖掘方法进行群体聚类，最终从目标人群中识别出重点特殊群体。

步骤3.1：相似性度量

从数据集中抽取8名轨迹特征鲜明的人员，依据公式(6)比较在α＝0.3时各人员之间的相似度，如下表所示：

Person similarities(α＝0.3)

0000030060070230360410650001.000000.531240.038720.022510.016700.092820.008580.012530030.531241.000000.019270.020970.006630.043120.005310.006780060.038720.019271.000000.015550.319870.043170.150630.110270070.022510.020970.015551.000000.224390.311280.040050.040050230.016700.006630.319870.224391.000000.011720.071340.048780360.092820.043120.043170.311280.011721.000000.031540.045970410.008580.005310.150630.040050.071340.031541.000000.154810650.012530.006780.110270.040050.048780.045970.154811.00000

从上表中可以找出几对相似度较高的人员000和003、006和023、007和036。其中000和036的停留点分布如附图6所示，显然两人到访地理位置重叠较多，所以地理位置相似度较高，又由于语义信息是根据地理位置区域获取的，所以两人语义信息相似度也较高，因此两人相似度为0.53是符合预期的。007和036的停留点分布如附图7所示，这种情形跟000和003类似，地理位置高度相似致使语义信息，所以两人整体相似度较高。006和023的停留点分布如附图8所示，可以看出两人的停留区域几乎没有重叠的部分，但两人相似度却为0.32。显然，根据之前相似度定义，两人的语义信息相似度一定较高。事实也确实如此，图中两人停留点较为密集的部分分别位于北京航空航天大学和中央民族大学中，这两个位置附近的POI多为科教文化服务类。这说明了考虑语义相似度可以发现仅靠地理位置相似度发现不了的人群。

步骤3.2：群体聚类

群体聚类过程见附图9。以Geolife中全部181人的轨迹数据为例，采用Dunn index和Sihouette index作为聚类评价标准。

Dunn index:

其中C_i表示第i个簇，d(x,y)表示x和y之间的距离。它在最大化簇间距离的同时最小化簇内距离，因此它的值越大表明聚类效果越好。

Sihouette index：

其中NC是簇的个数，n_i是C_i中的点的个数。a(x)表示对象x到它所在簇中所有其它对象的平均距离，b(x)表示对于对象x和不包含该对象的任意簇，计算该对象到给定簇中所有对象的平均距离，关于所有的簇，找出的最小值。

附图10和附图11分别表示Silhouette index和Dunn index随最近邻个数k变化的变化趋势。最近邻个数k取值[10,30]，这是最具代表性的一种取值区间，忽略掉评价标准值非法的k，SNN相似度阈值γ＝10。从图中可以看出，当最近邻个数k取12或13时，两个评价标准达到最大值。这时候两者得出的聚类结果一样，都为两个簇，分别包含032，044和151，162。其相似度矩阵见附图12。

这表明我们从182人中找出了两组各自包含两人的高相似度人群，其余人员全部视为噪声点。这是评价标准给我们指示的最好聚类结果。

附图13表示的是聚类个数随k的变化情况。其中当k＝15，k＝19，k＝21时，所产生的聚类结果的相似度矩阵分别如附图14、15和16所示。分别产生了4、11和8个簇。虽然这三种聚类结果对评价标准来说都不是最优的，但它们也提供给了一些相对合理的结果，这表明通过本方法可以获取不同聚类数目下的相对合理的聚类结果，所以此方法能够有效识别出大规模人群中的高度相似群体。