一种应用于LBSN网络的基于地理标签的热点区域事件探测系统

技术领域

本发明涉及一种地理标签的签到技术领域，更特别地说，是指一种应用于 LBSN网络的基于地理标签的热点区域事件探测系统，其中热点区域是基于标签 和地理位置的聚类进行的划分。

背景技术

地理标签(Geo Tags)是指用于描述兴趣点所处地理位置的数据信息，其信 息内容包括有兴趣点地址信息、兴趣点经纬度信息。地理标签能够更好的数字化 兴趣点的地理位置信息，有利于全球数据定位及地理位置信息追溯。地理标签也 称为地理标识。签到记录是指社会主体在兴趣点进行签到得到的数据信息。

目前，基于位置的社交网络(LBSN Location-based Social Networking) 越来越流行。由于快速的第四代移动通信网络的快速发展，以及对地图服务和内 嵌GPS模块智能手机强大的接口支持，它很容易为移动用户识别他们的位置，并 分享他们的LBSN数据库。在一个LBSN数据库中，用户可以发现和创建兴趣点 (poi point of interest)，可以在他们的当前位置进行签到，发表评论和意见以 及添加好友等。因此，LBSN网络如Foursquare、Facebook Places、新浪微博 等，已经采取了不同的机制来吸引用户，并激励用户分享他们的签到信息。并且， 已经有一些研究开始利用这些有用户产生的带有地理标签签到信息。因为这些数 据可以允许研究者以数据驱动的方式去分析社会层次的利益问题，并且根据签到 信息发现用户的移动模式，预测好友关系，更好的理解城市的不同方面。也可以 利用签到信息来发现热点区域。

目前基于含有地理标签的热点区域事件发现主要有一种方式：首先人工划分 好地理网格，然后统计各自区域上的签到信息，签到总量达到一定阈值则标识为 热点区域。这种方法存在三个问题，(1)首先，预先划分区域可能将实际的区域 进行分割到不同网格，无法反映实际热点区域。(2)热点区域的判断标准是该预 先划分区域的签到总数量是否达到了一个阈值，达到则标识为热点区域，但没有 考虑时间因素的影响。(3)网格划分的区域比较大，难以定位更加精确的区域。

发明内容

针对LBSN签到数据的特征，以及对现有热点区域事件发现处理方法的不足， 本发明提出了一种基于地理标签的热点区域事件探测系统。该热点区域事件探测 系统综合考虑了用户在近期的签到历史记录，结合地理空间信息来构建粗粒度区 域划分，然后，采用地理标签的聚类算法来计算细粒度区域范围，最后在区域内 计算出一定时间窗口下的热点区域。本发明设计的基于地理标签的热点区域事件 探测系统内嵌于LBSN数据库中，跟随着LBSN网络运行。

本发明设计的一种应用于LBSN网络的基于地理标签的热点区域事件探测系 统，所述LBSN网络中的LBSN数据库(2)与用户(1)之间设置所述基于地理 标签的热点区域事件探测系统(3)；

所述基于地理标签的热点区域事件探测系统(3)包括有签到聚类模块(31)、 基于标签聚类的区域计算模块(32)和热点区域事件计算模块(33)；所述热点 区域事件计算模块(33)为LBSN数据库(2)与用户(1)之间的衔接接口；

签到聚类模块(31)第一方面用于向LBSN数据库(2)发出含有地理标签 的签到请求信息Q_31-2，所述Q_31-2＝R_POI_p(x,y),POI；

R_POI_p(x,y)表示签到点地理位置，x表示经度，y表示纬度；

POI表示地理标签；所述POI中的任意一个地理标签记为a，另一个地理标签记 为b，a,b∈POI；

签到聚类模块(31)第二方面依据Q_31-2＝R_POI_p(x,y),POI能够在 LBSN数据库(2)中搜索出与地理标签POI匹配的签到记录，记为签到返回信 息Q_2-31；

签到聚类模块(31)第三方面对接收到的签到返回信息Q_2-31依据聚类间隔时 间kcluster-span进行k-means聚类方法处理，得到区域块信息Q_31-32，所述 Q_31-32＝{regX₁,regX₂,…,regX_y}，然后将Q_31-32输出给基于标签聚类的区域计 算模块(32)；

regX₁表示任意一个地理区域R中的第一个区域块；

regX₂表示任意一个地理区域R中的第二个区域块；

regX_y表示任意一个地理区域R中的最后一个区域块；

y表示区域块个数；

基于标签聚类的区域计算模块(32)第一方面用于接收区域块信息 Q_31-32＝{regX₁,regX₂,…,regX_y}；

基于标签聚类的区域计算模块(32)第二方面依据地理标签聚类策略POI-CP 对Q_31-32＝{regX₁,regX₂,…,regX_y}进行处理，得到收敛地理标签区域块Q_32-2； 并将收敛地理标签区域块写入到LBSN数据库(2)；

热点区域事件计算模块(33)第一方面接受用户(1)的热点区域查询请求 Request，所述Request＝{Geo(x,y),dist,Hot}，并将 Request＝{Geo(x,y),dist,Hot}转发给LBSN数据库(2)；

热点区域事件计算模块(33)第二方面依据 Request＝{Geo(x,y),dist,Hot}能够在LBSN数据库(2)中搜索出与 Geo(x,y)匹配的热点区域，记为查询返回信息Q_2-33；

热点区域事件计算模块(33)第三方面依据时间窗口下的签到频数策略 POI-TP对所述Q_2-33进行计算处理，得到区域热点事件和排名ChecFreq，并将所 述ChecFreq反馈给用户(1)。

在本发明中，所述的地理标签聚类策略POI-CP有下列步骤：

提取属于同一区域块regX_y中的地理标签POI的步骤；

计算属于同一区域块regX_y中的地理标签POI的位置个数的步骤；

计算地理标签POI与地理标签位置的位置中心点 之间的最大直线距离然后判断所述 与区域半径阈值r_阈值的大小，若则将r_阈值赋值给所 属区域中的区域块距离相关性半径若则选取最大直线 距离作为所属区域中的区域块距离相关性半径进而通过a地理标签的距 离相关性半径与b地理标签的距离相关性半径之和比上地理标签 POI中任意两个地理标签a,b之间的中心点距离得到距离相关性 ${H\_\mathrm{rel}}_{a-b}^{{\mathrm{regX}}_y}=\frac{{\mathrm{rD}}_a^{{\mathrm{regX}}_y}+{\mathrm{rD}}_b^{{\mathrm{regX}}_y}}{{\mathrm{CLD}}_{a-b}^{{\mathrm{regX}}_y}}$的步骤；

计算地理标签POI中任意两个地理标签a,b之间的的语义相关性 ${S\_\mathrm{rel}}_{a-b}^{Q_{31-32}}=1-\frac{E_{a-b}^{Q_{31-32}}}{\max \left(L_{a-b}^{Q_{31-32}}\right)}$的步骤；

依据所述的和所述的与距离相关性阈值rel_距离、语义 相关性阈值rel_语义进行对比，并依据对比结果合并区域块regX_y的步骤；

若且时，将b地理标签的签到位置 合并到a地理标签的签到位置

若或时，则b地理标签的签到位置 不与a地理标签的签到位置进行区域块合并。

在本发明中，所述的时间窗口下的签到频数策略POI-TP的具体方式为：热点 区域事件计算模块(33)会实时计算用户(1)请求任意一区域regX_y的热点事 件，当向热点区域聚类数据库(2)请求各自区域内截止到当前时刻t的历史含有 地理签到记录Q_2-33，则事件描述为$\mathrm{Trend}=\frac{{\mathrm{ChecFreq}}^t-{\mathrm{ChecFreq}}^{t-1}}{\mathrm{\Delta T}},$ΔT表 示时间窗口，ΔT＝|t-(t-1)|，t表示当前时刻，t-1表示前一时刻，ChecFreq^t表 示当前时刻t的签到频数，ChecFreq^t-1表示前一时刻t-1的签到频数；

事件的活跃程度Rank与ΔT的签到频数和签到持续事件成正比，即：

$\mathrm{Rank}=\underset{i=1}{\overset{{\mathrm{regX}}_y}{\Sigma }}\frac{{\mathrm{ChecFreq}}_i^t}{{\Omega }_i}\times \sqrt{1+\frac{\underset{{j\in \mathrm{regX}}_j}{\max }\left({\mathrm{CU}}^j\right)}{{\mathrm{regX}}_y}};$

其中表示在时间窗口ΔT内的签到频数，regX_y表示任意一区域，即 求和元素，i表示求和指标，Ω_i表示在时间窗口ΔT内用户(1)所请求范围内区 域签到总数量，表示当前所有热点区域中的时间窗口个数的 最大值，j表示时间窗口个数最大的区域标识号。

本发明设计的基于地理标签的热点区域事件探测系统的优点在于：

①在LBSN数据库使用本发明热点区域事件探测系统解决了采用人工划分区域 造成的热点区域精度低的缺陷。本发明热点区域事件探测系统首先在地里标签 空间上对热点区域进行聚类，得到粗略的热点区域划分，减少了聚类过程中的 数据量。

②本发明热点区域事件探测系统采用粗粒度簇内进行细粒度的挖掘，得到与事实 相符的热点区域，使得获取的热点区域事件发现更佳符合实际需求。

③本发明热点区域事件探测系统采用时间窗口划分热点区域，通过签到变化率阈 值搜索出热点区域，使得LBSN网络的查询时间缩短，提高了响应速度。

④本发明热点区域事件探测系统采用模块化的设计方式，且LBSN网络通过热点 区域事件计算模块为衔接接口，实现与用户交互，提高了用户查询热点区域事 件的效率。

附图说明

图1是本发明基于地理标签的热点区域事件探测系统的结构框图。

图2是本发明基于地理标签的热点区域事件探测系统的时序图。

具体实施方式

下面将结合附图对本发明做进一步的详细说明。

图1中给出了根据本发明的基于用户签到的热点区域事件探测系统结构框 图。在现有LBSN数据库2与用户1之间设置本发明设计的基于地理标签的热点 区域事件探测系统3，该系统包括有签到聚类模块31、基于标签聚类的区域计算 模块32和热点区域事件计算模块33。所述热点区域事件计算模块33为LBSN 数据库2与用户1之间的衔接接口。

在本发明中，利用基于位置的社交网络(LBSN Location-based Social  Networking)构成的LBSN数据库2提供的历史签到信息进行热点区域事件探测， 即是寻找出热点区域关联信息的数据源。

在本发明中，任意一个地理区域中的兴趣点POI签到信息记为 R_POI_p(x,y),POI。R表示地理区域，POI表示在R中的字符串，即所在地 理区域的兴趣点的地理标签，也是语义分析中所需的源文件串，POI的字符长度 记为L_POI，p表示社会主体在POI签到的次数，POI_p(x,y)表示第p次的签到 点地理位置，x表示经度，y表示纬度。

一般地，为了本专利申请内容的表述，地理标签POI可以设置为任意一区域 R中的食堂A、医院B、图书馆C、教学楼D等；地理标签POI采用集合形式 表达为POI＝{A,B,C,D}，为了广义表达地理标签POI，所述POI中任意一个 地理标签记为a，另一个地理标签记为b，a,b∈POI。基于地理标签的描述为：

任意一个地理区域R中的食堂A签到信息记为R_A_α(x,y),A；R表示地理 区域，A表示在R中的字符串，A的字符长度记为L_A(即“地理区域”“食堂”， L_A＝12，一个汉字2个字节)，a表示社会主体在A签到的次数，A_α(x,y)表示 签到点地理位置，x表示经度，y表示纬度。

任意一个地理区域R中的医院B签到信息记为R_B_β(x,y),B；R表示地理 区域，B表示在R中的字符串，B的字符长度记为L_B(即“地理区域”“医院”， L_A＝12)，β表示社会主体在B签到的次数，B_β(x,y)表示签到点地理位置，x 表示经度，y表示纬度。

任意一个地理区域R中的图书馆C签到信息记为R_C_γ(x,y),C；R表示地 理区域，C表示在R中的字符串，C的字符长度记为L_C(即“地理区域”“图书 馆”，L_A＝14)，γ表示社会主体在C签到的次数，C_γ(x,y)表示签到点地理位置， x表示经度，y表示纬度。

任意一个地理区域R中的教学楼D签到信息记为R_D_θ(x,y),D；R表示地 理区域，D表示在R中的字符串，D的字符长度记为L_D(即“地理区域”“教学 楼”，L_A＝14)，θ表示社会主体在D签到的次数，D_θ(x,y)表示签到点地理位 置，x表示经度，y表示纬度。

用户1

用户1在使用本发明设计的基于地理标签的热点区域事件探测系统3时，第 一方面将兴趣请求Request＝{Geo(x,y),dist,Hot}发送给热点区域事件计算 模块33；第二方面用于接收热点区域事件计算模块33返回的聚类实时热点区域 信息ChecFreq。

所述推荐请求Request＝{Geo(x,y),dist,Hot}中的Geo(x,y)表示请求 用户所在的地理位置，x为经度，y为纬度；dist表示用户设置的兴趣距离半径； Hot表示用户关注的热点区域。

参见图1和图2所示，在本发明中，基于地理标签的热点区域事件探测系统3 包括有签到聚类模块31、基于标签聚类的区域计算模块32和热点区域事件计算 模块33。下面将详细说明各个模块：

签到聚类模块31

签到聚类模块31第一方面用于向LBSN数据库2发出含有地理标签的用户 签到信息Q_31-2＝R_POI_p(x,y),POI；

签到聚类模块31第二方面依据Q_31-2＝R_POI_p(x,y),POI能够在LBSN 数据库2中搜索出多个与地理标签POI匹配的签到记录Q_2-31；

签到聚类模块31第三方面对接收到的返回签到信息Q_2-31依据聚类间隔时 间kcluster-span进行k-means聚类方法处理，得到区域块信息 Q_31-32＝{regX₁,regX2_,…,regX_y}，然后将Q_31-32输出给基于标签聚类的区域计 算模块32。

在本发明中，所述Q_31-2＝R_POI_p(x,y),POI中的R_POI_p(x,y)表示签 到点地理位置，x表示经度，y表示纬度。POI表示地理标签，即R_POI_p(x,y) 所在的地理名称，也是源文件串记载的内容；所述POI＝{A,B,C,D}，A为食 堂地理标签，B为医院地理标签，C为图书馆地理标签，D为教学楼地理标签。

在本发明中，区域块信息Q_31-32＝{regX₁,regX₂,…,regX_y}中的regX₁表 示任意一个地理区域R中的第一个区域块，regX₂表示任意一个地理区域R中的 第二个区域块，regX_y表示任意一个地理区域R中的最后一个区域块，y表示区 域块个数。regX_y也称为在任意一个地理区域R中划分出的任意一个区域块。

列举，满足食堂A的签到记录有R_A₁(x,y),A、R_A₂(x,y),A、 R_A₃(x,y),A、R_A₄(x,y),A、R_A₅(x,y),A、……、R_A_α(x,y),A；

R_A₁(x,y)表示食堂A的第一个签到点位置；

R_A₂(x,y)表示食堂A的第二个签到点位置；

R_A₃(x,y)表示食堂A的第三个签到点位置；

R_A₄(x,y)表示食堂A的第四个签到点位置；

R_A₅(x,y)表示食堂A的第五个签到点位置；

R_A_α(x,y)表示食堂A的最后一个签到点位置；为了方便说明， R_A_α(x,y)也称为食堂A的任意一个签到点位置；

列举，满足医院B的签到记录有R_B₁(x,y),B、R_B₂(x,y),B、 R_B₃(x,y),B、R_B₄(x,y),B、R_B₅(x,y),B、……、R_B_β(x,y),B；

R_B₁(x,y)表示医院B的第一个签到点位置；

R_B₂(x,y)表示医院B的第二个签到点位置；

R_B₃(x,y)表示医院B的第三个签到点位置；

R_B₄(x,y)表示医院B的第四个签到点位置；

R_B₅(x,y)表示医院B的第五个签到点位置；

R_B_β(x,y)表示医院B的最后一个签到点位置；为了方便说明， R_B_β(x,y)也称为医院B的任意一个签到点位置；

列举，满足图书馆C的签到记录有R_C₁(x,y),C、R_C₂(x,y),C、 R_C₃(x,y),C、R_C₄(x,y),C、R_C₅(x,y),C、……、R_C_γ(x,y),C；

R_C₁(x,y)表示图书馆C的第一个签到点位置；

R_C₂(x,y)表示图书馆C的第二个签到点位置；

R_C₃(x,y)表示图书馆C的第三个签到点位置；

R_C₄(x,y)表示图书馆C的第四个签到点位置；

R_C₅(x,y)表示图书馆C的第五个签到点位置；

R_C_γ(x,y)表示图书馆C的最后一个签到点位置；为了方便说明， R_C_γ(x,y)也称为图书馆C的任意一个签到点位置；

列举，满足教学楼D的签到记录有R_D₁(x,y),D、R_D₂(x,y),D、 R_D₃(x,y),D、R_D₄(x,y),D、R_D₅(x,y),D、……、R_D_θ(x,y),D；

R_D₁(x,y)表示教学楼D的第一个签到点位置；

R_D₂(x,y)表示教学楼D的第二个签到点位置；

R_D₃(x,y)表示教学楼D的第三个签到点位置；

R_D₄(x,y)表示教学楼D的第四个签到点位置；

R_D₅(x,y)表示教学楼D的第五个签到点位置；

R_D_θ(x,y)表示教学楼D的最后一个签到点位置；为了方便说明， R_D_θ(x,y)也称为教学楼D的任意一个签到点位置。

依据举例出的食堂A、医院B、图书馆C、教学楼D，则与地理标签POI 匹配的签到记录Q_2-31；

$Q_{2-31}=\left(\begin{array}{ccccccc}R\_A:A_1(x,y)& A_2(x,y)& A_3(x,y)& A_4(x,y)& A_5(x,y)& ···& A_{\alpha }(x,y)\\ R\_B:B_1(x,y)& B_2(x,y)& B_3(x,y)& B_4(x,y)& B_5(x,y)& ···& B_{\alpha }(x,y)\\ R\_C:C_1(x,y)& C_2(x,y)& C_3(x,y)& C_4(x,y)& C_5(x,y)& ···& C_{\alpha }(x,y)\\ R\_D:D_1(x,y)& D_2(x,y)& D_3(x,y)& D_4(x,y)& D_5(x,y)& ···& D_{\alpha }(x,y)\end{array}\right).$

列举，第一个区域块regX₁包括的签到记录有R_A₂(x,y),A、R_A₃(x,y),A、 R_A₄(x,y),A、R_A₅(x,y),A、R_A_α(x,y),A、R_B₁(x,y),B、 R_B₂(x,y),B、R_B₃(x,y),B、R_B₄(x,y),B、R_C₁(x,y),C、 R_C₂(x,y),C、R_D₁(x,y),D和R_D_θ(x,y),D；第一个区域块regX₁采 用集合形式表达为：

${\mathrm{regX}}_1=\left(\begin{array}{c}[R\_A_2(x,y),A],[R\_A_3(x,y),A],[R\_A_4(x,y),A],\\ [R\_A_5(x,y),A],[R\_A_{\alpha }(x,y),A],\\ [R\_B_1(x,y),B],[R\_B_2(x,y),B],[R\_B_3(x,y),B],\\ [R\_B_4(x,y),B],\\ [R\_C_1(x,y),C],[R\_C_2(x,y),C],\\ [R\_D_1(x,y),D],[R\_D_{\theta }(x,y),D]\end{array}\right).$

列举，第二个区域块regX₂包括的签到记录有R_A₁(x,y),A、 R_B₅(x,y),B、R_B_β(x,y),B、R_C₃(x,y),C、R_C₄(x,y),C、 R_C₅(x,y),C和R_C_γ(x,y),C；第二个区域块regX₂采用集合形式表达为：

${\mathrm{regX}}_2=\left(\begin{array}{c}[R\_A_1(x,y),A],\\ [R\_B_5(x,y),B],[R\_B_{\beta }(x,y),B],\\ [R\_C_3(x,y),C],[R\_C_4(x,y),C],[R\_C_5(x,y),C],\\ [R\_C_{\gamma }(x,y),C]\end{array}\right).$

列举，最后一个区域块regX_y包括的签到记录有R_D₂(x,y),D、 R_D₃(x,y),D、R_D₄(x,y),D和R_D₅(x,y),D；最后一个区域块regX_y采 用集合形式表达为：

${\mathrm{regX}}_y=\left(\begin{array}{c}[R\_D_2(x,y),D],[R\_D_3(x,y),D],[R\_D_4(x,y),D],\\ [R\_D_5(x,y),D]\end{array}\right).$

记录下各个区域块，采用集合形式表达区域块信息为 Q_31-32＝{regX₁,regX₂,…,regX_y}。

在本发明中，k-means聚类方法请参考《大数据互联网大规模数据挖掘与分 布式处理》，王斌译，2012年9月第1版。

在本发明中，签到聚类模块31设置为简单任务，是为了在庞大的LBSN数 据库2当中获得粗略的签到记录，将粗略的签到记录应用k-means聚类方法处理， 能够将签到记录聚集到各自区域。

使用k-means聚类方法处理数据库中的R_POI_p(x,y)，不对外提供线上 实时处理服务，签到聚类模块31的目的是大致划分出区域CR的范围(即称为粗 粒度的划分区域)；另外，区域CR的范围在签到空间上变化不明显，可以依据聚 类间隔时间kcluster-span在线下处理区域CR的划分。

基于标签聚类的区域计算模块32

基于标签聚类的区域计算模块32第一方面用于接收区域块信息 Q_31-32＝{regX₁,regX₂,…,regX_y}；

基于标签聚类的区域计算模块32第二方面依据地理标签聚类策略POI-CP对 Q_31-32＝{regX₁,regX₂,…,regX_y}进行处理，得到收敛地理标签区域块Q_32-2； 并将收敛地理标签区域块Q_32-2写入到LBSN数据库2。

在本发明中，下面列举说明对地理标签的具体处理，即地理标签聚类策略 POI-CP的实施步骤：

(一)第一区域块

在本发明中，对第一个区域块regX₁中的地理标签进行地理标签聚类策略 POI-CP的处理步骤为：

步骤101：提取出属于同一区域块中的地理标签

从Q_31-32＝{regX₁,regX₂,…,regX_y}中提取出满足第一个区域块regX₁的 地理标签，若第一个区域块regX₁中的地理标签包括有A、B和C，则满足regX₁的地理标签采用集合描述为；

${\mathrm{regX}}_1=\left(\begin{array}{c}[R\_A_1(x,y),A],[R\_A_2(x,y),A],[R\_A_3(x,y),A],\\ [R\_A_4(x,y),A],[R\_A_5(x,y),A],[R\_A_{\alpha }(x,y),A],\\ [R\_B_1(x,y),B],[R\_B_2(x,y),B],[R\_B_3(x,y),B],\\ [R\_B_4(x,y),B],\\ [R\_C_1(x,y),C],[R\_C_2(x,y),C]\end{array}\right).$

步骤102：地理标签的位置个数获取；

对第一个区域块regX₁中的地理标签A进行位置归类，得到满足regX₁中的A 地理标签位置${\mathrm{Add}}_A^{X_1}=\left(\begin{array}{c}R\_A_1(x,y),R\_A_2(x,y),R\_A_3(x,y),\\ R\_A_4(x,y),R\_A_5(x,y),R\_A_{\alpha }(x,y)\end{array}\right);$所述A在 regX₁中出现的次数记为且

对第一个区域块regX₁中的地理标签B进行位置归类，得到满足regX₁中的B 地理标签位置${\mathrm{Add}}_B^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y)\end{array}\right);$所述B在 regX₁中出现的次数记为且

对第一个区域块regX₁中的地理标签C进行位置归类，得到满足regX₁中的C 地理标签位置${\mathrm{Add}}_C^{X_1}=\{R\_C_1(x,y),R\_C_2(x,y)\};$所述C在regX₁中出现的 次数记为且${\alpha }_C^{{\mathrm{regX}}_1}=2.$

对第一个区域块regX₁中的地理标签D进行位置归类，得到满足regX₁中的 D地理标签位置${\mathrm{Add}}_D^{X_1}=\{R\_D_1(x,y),R\_D_{\theta }(x,y)\};$所述D在regX₁中出现 的次数记为且${\alpha }_D^{\mathrm{reg}{X}_1}=2.$

在本发明中，统计在第一个区域块regX₁中的所有地理标签的签到次数，记为 且${\alpha }_{\mathrm{POI}}^{{\mathrm{regX}}_1}={\alpha }_A^{{\mathrm{regX}}_1}+{\alpha }_B^{{\mathrm{regX}}_1}+{\alpha }_C^{{\mathrm{regX}}_1}+{\alpha }_D^{\mathrm{reg}{X}_1}.$

步骤103：距离相关性

步骤103－1：解析${\mathrm{Add}}_A^{X_1}=\left(\begin{array}{c}R\_A_1(x,y),R\_A_2(x,y),R\_A_3(x,y),\\ R\_A_4(x,y),R\_A_5(x,y),R\_A_{\alpha }(x,y)\end{array}\right)$中 的经度平均值$\bar{x}\_A=\frac{\underset{i=1}{\overset{{\alpha }^{X_1}}{\Sigma }}R\_A_i\left(x\right)}{{\alpha }^{X_1}}$和纬度平均值$\bar{y}\_A=\frac{\underset{i=1}{\overset{{\alpha }^{X_1}}{\Sigma }}R\_A_i\left(y\right)}{{\alpha }^{X_1}},$i表示 求和关系中的求和指标，得到满足regX₁中的A地理标签位置的位置中 心点解析 ${\mathrm{Add}}_A^{X_1}=\left(\begin{array}{c}R\_A_1(x,y),R\_A_2(x,y),R\_A_3(x,y),\\ R\_A_4(x,y),R\_A_5(x,y),R\_A_{\alpha }(x,y)\end{array}\right)$中每个标签点位置到 的距离，并选取出最大直线距离，记为

解析${\mathrm{Add}}_B^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y)\end{array}\right)$中的经度平均值 $\bar{x}\_B=\frac{\underset{j=1}{\overset{{\beta }^{X_1}}{\Sigma }}R\_B_j\left(x\right)}{{\beta }^{X_1}}$和纬度平均值$\bar{y}\_B=\frac{\underset{j=1}{\overset{{\beta }^{X_1}}{\Sigma }}R\_B_j\left(x\right)}{{\beta }^{X_1}},$j表示求和关系中的 求和指标，得到满足regX₁中的B地理标签位置的位置中心点 解析 ${\mathrm{Add}}_B^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y)\end{array}\right)$中每个标签点位置到 的距离，并选取出最大直线距离记为

解析${\mathrm{Add}}_C^{X_1}=\{R\_C_1(x,y),R\_C_2(x,y)\}$中的经度平均值 $\bar{x}\_C=\frac{\underset{m=1}{\overset{{\gamma }^{X_1}}{\Sigma }}R\_C_m\left(x\right)}{{\gamma }^{X_1}}$和纬度平均值$\bar{y}\_C=\frac{\underset{m=1}{\overset{{\gamma }^{X_1}}{\Sigma }}R\_C_m\left(y\right)}{{\gamma }^{X_1}},$m表示求和关系中 的求和指标，得到AC地理标签位置的位置中心点解析${\mathrm{Add}}_C^{X_1}=\{R\_C_1(x,y),R\_C_2(x,y)\}$中每个标签点位置到 的距离，并选取出最大直线距离记为

解析${\mathrm{Add}}_D^{X_1}=\{R\_D_1(x,y),R\_D_{\theta }(x,y)\}$中的经度平均值 $\bar{x}\_D=\frac{\underset{n=1}{\overset{{\theta }^{X_1}}{\Sigma }}R\_C_n\left(x\right)}{{\theta }^{X_1}}$和纬度平均值$\bar{y}\_D=\frac{\underset{n=1}{\overset{{\theta }^{X_1}}{\Sigma }}R\_C_n\left(y\right)}{{\theta }^{X_1}},$n表示求和关系中的 求和指标，得到AD地理标签位置的位置中心点解析${\mathrm{Add}}_D^{X_1}=\{R\_D_1(x,y),R\_D_{\theta }(x,y)\}$中每个标签点位置到 的距离，并选取出最大直线距离记为

在本发明中，统计在第一个区域块regX₁中的所有地理标签与地理标签位置的 位置中心点之间的最大直线距离且 ${\mathrm{LD}}_{\mathrm{POI}-\max }^{\mathrm{reg}{X}_1}=\{{\mathrm{LD}}_{A-\max }^{X_1},{\mathrm{LD}}_{B-\max }^{X_1},{\mathrm{LD}}_{C-\max }^{X_1},{\mathrm{LD}}_{D-\max }^{X_1}\}.$

步骤103－2：设置区域块半径阈值记为r_阈值；

若最大直线距离小于区域半径阈值r_阈值，则将r_阈值赋值给所属区域中的区域块 距离相关性半径

若最大直线距离大于等于区域半径阈值r_阈值，则选取最大直线距离作为所属区 域中的区域块距离相关性半径

同理可得：a地理标签的距离相关性半径记为b地理标签的距离相 关性半径记为

列举，若则将r_阈值赋值给满足regX₁中的区域块距离相关性 半径若则将赋值给满足regX₁中的区域块距离相 关性半径

列举，若则将r_阈值赋值给满足regX₁中的区域块距离相关性 半径若则将赋值给满足regX₁中的区域块距离相 关性半径

列举，若则将r_阈值赋值给满足regX₁中的区域块距离相关性 半径若则将赋值给满足regX₁中的区域块距离 相关性半径

列举，若则将r_阈值赋值给满足regX₁中的区域块距离相关性 半径若则将赋值给满足regX₁中的区域块距离 相关性半径

步骤103－3：计算满足regX₁中的任意两个地理标签位置的中心点距离；

与的中心点距离记为

与的中心点距离记为

与的中心点距离记为

与的中心点距离记为

与的中心点距离记为

在本发明中，统计在第一个区域块regX₁中的地理标签POI中任意两个地理 标签a,b之间的中心点距离记为

步骤103－4：定义满足regX₁中的距离相关性

列举，与的距离相关性记为 $H\_{\mathrm{rel}}_{A-B}^{X_1}=\frac{r{D}_A^{X_1}+r{D}_B^{X_1}}{{\mathrm{CLD}}_{A-B}^{\mathrm{reg}{X}_1}};$

列举，与的距离相关性记为 $H\_{\mathrm{rel}}_{A-C}^{X_1}=\frac{r{D}_A^{X_1}+r{D}_C^{X_1}}{{\mathrm{CLD}}_{A-C}^{\mathrm{reg}{X}_1}};$

列举，与的距离相关性记为 $H\_{\mathrm{rel}}_{A-D}^{X_1}=\frac{r{D}_A^{X_1}+r{D}_D^{X_1}}{{\mathrm{CLD}}_{A-D}^{\mathrm{reg}{X}_1}};$

列举，与的距离相关性记为 $H\_{\mathrm{rel}}_{B-C}^{X_1}=\frac{r{D}_B^{X_1}+r{D}_C^{X_1}}{{\mathrm{CLD}}_{B-C}^{\mathrm{reg}{X}_1}}.$

列举，与的距离相关性记为 $H\_{\mathrm{rel}}_{B-D}^{X_1}=\frac{r{D}_B^{X_1}+r{D}_D^{X_1}}{{\mathrm{CLD}}_{B-D}^{\mathrm{reg}{X}_1}}.$

在本发明中，平面距离为公知距离公式计算得到，如 $\left|\mathrm{AB}\right|=\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2}.$

在本发明中，统计在第一个区域块regX₁中的距离相关性记为 $H\_{\mathrm{rel}}_{a-b}^{\mathrm{reg}{X}_1}=\frac{r{D}_a^{\mathrm{reg}{X}_1}+r{D}_b^{\mathrm{reg}{X}_1}}{{\mathrm{CLD}}_{a-b}^{\mathrm{reg}{X}_1}}.$

步骤104：语义相关性

在本发明中，定义语义距离为POI之间的编辑距离，即E_POI。所述编辑距离 E_POI为把源文件串POI＝{A,B,C,D}转换成目标串TPOI＝{A,B,C,D}代价 最低的操作序列。编辑距离的计算请参考2009年12月第1版第14次印刷的《算 法导论》第218－219页，(美)Thomas H.Cormen Charles E.Leiserson  Ronald L.Rivest Clifford Stein著，潘金贵、顾铁成、李成法、叶懋译。

列举，在第一个区域块regX₁中的食堂A的字符串长度记为医院B的字 符串长度记为图书馆C的字符串长度记为教学楼D的字符串长度记为

列举，在第一个区域块regX₁中的食堂A与医院B的编辑距离记为食 堂A与图书馆C的编辑距离记为食堂A与教学楼D的编辑距离记为医院B与图书馆C的编辑距离为医院B与教学楼D的编辑距离记为

列举，在第一个区域块regX₁中的食堂A与医院B的语义相关性记为 $S\_{\mathrm{rel}}_{A-B}^{X_1}=1-\frac{E_{A-B}^{X_1}}{\max (L_A^{X_1},L_B^{X_1})};$

列举，在第一个区域块regX₁中的食堂A与图书馆C的语义相关性记为 $S\_{\mathrm{rel}}_{A-C}^{X_1}=1-\frac{E_{A-C}^{X_1}}{\max (L_A^{X_1},L_C^{X_1})};$

列举，在第一个区域块regX₁中的食堂A与教学楼D的语义相关性记为 $S\_{\mathrm{rel}}_{A-D}^{X_1}=1-\frac{E_{A-D}^{X_1}}{\max (L_A^{X_1},L_D^{X_1})};$

列举，在第一个区域块regX₁中的医院B与图书馆C的语义相关性记为 $S\_{\mathrm{rel}}_{B-C}^{X_1}=1-\frac{E_{B-C}^{X_1}}{\max (L_B^{X_1},L_C^{X_1})}.$

列举，在第一个区域块regX₁中的医院B与教学楼D的语义相关性记为 $S\_{\mathrm{rel}}_{B-D}^{X_1}=1-\frac{E_{B-D}^{X_1}}{\max (L_B^{X_1},L_D^{X_1})}.$

在本发明中，在区域信息Q_31-32中的任意两个地理标签的语义相关性记为 $S\_{\mathrm{rel}}_{a-b}^{Q_{31-32}}=1-\frac{E_{a-b}^{Q_{31-32}}}{\max \left(L_{a-b}^{Q_{31-32}}\right)}.$

步骤105：区域块是否合并

设置距离相关性阈值记为rel_距离、语义相关性阈值记为rel_语义，并依据rel_距离和rel_语义是否进行区域块的合并处理；

步骤105－1：若且时，将 ${\mathrm{Add}}_B^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y)\end{array}\right)$合并到 ${\mathrm{Add}}_A^{X_1}=\left(\begin{array}{c}R\_A_1(x,y),R\_A_2(x,y),R\_A_3(x,y),\\ R\_A_4(x,y),R\_A_5(x,y),R\_A_{\alpha }(x,y)\end{array}\right)$中，则更新为 ${\mathrm{Add}}_{A\_\mathrm{new}}^{X_1}=\left(\begin{array}{c}R\_A_2(x,y),R\_A_3(x,y),R\_A_4(x,y),\\ R\_A_5(x,y),R\_A_{\alpha }(x,y),\\ R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y)\end{array}\right);$并将输出给 LBSN数据库，执行步骤105－2；

步骤105－2：若或时，则与 不进行区域块合并；并将和输出给LBSN数据库，执行步骤 105－3；

步骤105－3：若且时，将 ${\mathrm{Add}}_C^{X_1}=\{R\_C_1(x,y),R\_C_2(x,y)\}$合并到 ${\mathrm{Add}}_A^{X_1}=\left(\begin{array}{c}R\_A_2(x,y),R\_A_3(x,y),R\_A_4(x,y),\\ R\_A_5(x,y),R\_A_{\alpha }(x,y)\end{array}\right)$中，则更新为 ${\mathrm{Add}}_{A\_\mathrm{new}}^{X_1}=\left(\begin{array}{c}R\_A_2(x,y),R\_A_3(x,y),R\_A_4(x,y),\\ R\_A_5(x,y),R\_A_{\alpha }(x,y),\\ R\_C_1(x,y),R\_C_2(x,y)\end{array}\right);$并将输出给 LBSN数据库，执行步骤105－4；

步骤105－4：若或时，则与 不进行区域块合并；并将和输出给LBSN数据库，执行步骤 105－5；

步骤105－5若且时，将 ${\mathrm{Add}}_D^{X_1}=\{R\_D_1(x,y),R\_D_{\theta }(x,y)\}$合并到 ${\mathrm{Add}}_A^{X_1}=\left(\begin{array}{c}R\_A_2(x,y),R\_A_3(x,y),R\_A_4(x,y),\\ R\_A_5(x,y),R\_A_{\alpha }(x,y)\end{array}\right)$中，则更新为 ${\mathrm{Add}}_{A\_\mathrm{new}}^{X_1}=\left(\begin{array}{c}R\_A_2(x,y),R\_A_3(x,y),R\_A_4(x,y),\\ R\_A_5(x,y),R\_A_{\alpha }(x,y),\\ R\_D_1(x,y),R\_D_{\theta }(x,y)\end{array}\right);$并将

步骤105－6：若或时，则与 不进行区域块合并；并将和输出给LBSN数据库，执行步骤 105－7；

步骤105－7：若且时，将 ${\mathrm{Add}}_C^{X_1}=\{R\_C_1(x,y),R\_C_2(x,y)\}$合并到 ${\mathrm{Add}}_B^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y)\end{array}\right)$中，则更新为 ${\mathrm{Add}}_{B\_\mathrm{new}}^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y),\\ R\_C_1(x,y),R\_C_2(x,y)\end{array}\right);$并将输出给 LBSN数据库，执行步骤105－8；

步骤105－8：若或时，则与 不进行区域块合并；并将和输出给LBSN数据库，执行步骤 105－9；

步骤105－9：若且时，将 ${\mathrm{Add}}_D^{X_1}=\{R\_D_1(x,y),R\_D_{\theta }(x,y)\}$合并到 ${\mathrm{Add}}_B^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y)\end{array}\right)$中，则更新为 ${\mathrm{Add}}_{B\_\mathrm{new}}^{X_1}=\left(\begin{array}{c}R\_B_1(x,y),R\_B_2(x,y),R\_B_3(x,y),\\ R\_B_4(x,y),\\ R\_D_1(x,y),R\_D_{\theta }(x,y)\end{array}\right);$并将输出给 LBSN数据库，执行步骤105－10；

步骤105－10：若或时，则与 不进行区域块合并；并将和输出给LBSN数据库。

在本发明中，将第一个区域块regX₁的写入LBSN数据库2的签到点位置信 息采用集合形式表达为$Q_{2-33}=\left\{{\mathrm{checkin}}_{{\mathrm{regX}}_1}\right\}.$

(二)第二区域块

在本发明中，对第二个区域块regX₂中的地理标签进行地理标签聚类策略 POI-CP的处理步骤为：

步骤201：提取出属于同一区域块中的地理标签

从Q_31-32＝{regX₁,regX₂,…,regX_y}中提取出满足第二个区域块regX₂的 地理标签，若第二个区域块regX₂中的地理标签包括有B和C，则满足regX₂的 地理标签采用集合描述为；

${\mathrm{regX}}_2=\left(\begin{array}{c}[R\_B_5(x,y),B],[R\_B_{\beta }(x,y),B],\\ [R\_C_3(x,y),C],[R\_C_4(x,y),C],[R\_C_5(x,y),C],\\ [R\_C_{\gamma }(x,y),C]\end{array}\right).$

步骤202：地理标签的位置个数获取；

对第二个区域块regX₂中的地理标签B进行位置归类，得到满足regX₂中的 B地理标签位置${\mathrm{Add}}_B^{X_2}=\{R\_B_5(x,y),R\_B_{\beta }(x,y)\};$所述B在regX₂中出现 的次数记为且${\alpha }_B^{{\mathrm{regX}}_2}=2.$

对第二个区域块regX₂中的地理标签C进行位置归类，得到满足regX₂中的 C地理标签位置${\mathrm{Add}}_C^{X_2}=\left(\begin{array}{c}R\_C_3(x,y),R\_C_4(x,y),R\_C_5(x,y),\\ R\_C_{\gamma }(x,y)\end{array}\right);$所述C 在regX₂中出现的次数记为且

在本发明中，统计在第二个区域块regX₂中的所有地理标签的签到次数，记 为且${\alpha }_{\mathrm{POI}}^{{\mathrm{regX}}_2}={\alpha }_B^{\mathrm{reg}{X}_2}+{\alpha }_C^{{\mathrm{regX}}_2}.$

步骤203：距离相关性

步骤203－1：解析${\mathrm{Add}}_B^{X_2}=\{R\_B_5(x,y),R\_B_{\beta }(x,y)\}$中的经度平均值 $\bar{x}\_B=\frac{\underset{j=1}{\overset{{\beta }^{X_2}}{\Sigma }}R\_B_j\left(x\right)}{{\beta }^{X_2}}$和纬度平均值$\bar{y}\_B=\frac{\underset{j=1}{\overset{{\beta }^{X_2}}{\Sigma }}R\_B_j\left(x\right)}{{\beta }^{X_2}},$j表示求和关系中的 求和指标，得到满足regX₂中的B地理标签位置的位置中心点 解析${\mathrm{Add}}_B^{X_2}=\{R\_B_5(x,y),R\_B_{\beta }(x,y)\}$中每个标签点 位置到的距离，并选取出最大直线距离，记为

解析${\mathrm{Add}}_C^{X_2}=\left(\begin{array}{c}R\_C_3(x,y),R\_C_4(x,y),R\_C_5(x,y),\\ R\_C_{\gamma }(x,y)\end{array}\right)$中的经度平均值 $\bar{x}\_C=\frac{\underset{m=1}{\overset{{\gamma }^{X_2}}{\Sigma }}R\_C_m\left(x\right)}{{\gamma }^{X_2}}$和纬度平均值$\bar{y}\_C=\frac{\underset{m=1}{\overset{{\gamma }^{X_2}}{\Sigma }}R\_C_m\left(y\right)}{{\gamma }^{X_2}},$m表示求和关系中 的求和指标，m∈γ′，得到满足regX₂中的C地理标签位置的位置中心点 解析 ${\mathrm{Add}}_C^{X_2}=\left(\begin{array}{c}R\_C_3(x,y),R\_C_4(x,y),R\_C_5(x,y),\\ R\_C_{\gamma }(x,y)\end{array}\right)$中每个标签点位置到 的距离，并选取出最大直线距离，记为

在本发明中，统计在第二个区域块regX₂中的所有地理标签与地理标签位置 的位置中心点之间的最大直线距离且 ${\mathrm{LD}}_{\mathrm{POI}-\max }^{\mathrm{reg}{X}_2}=\{{\mathrm{LD}}_{B-\max }^{X_1},{\mathrm{LD}}_{C-\max }^{X_1}\}.$

步骤203－2：设置区域块半径阈值记为r_阈值；

若最大直线距离小于区域半径阈值r_阈值，则将r_阈值赋值给所属区域中的区域块 距离相关性半径rD_POI；

若最大直线距离大于等于区域半径阈值r_阈值，则选取最大直线距离为所属区域 中的区域块距离相关性半径rD_POI；

同理可得：a地理标签的距离相关性半径记为b地理标签的距离相 关性半径记为

列举，若则将r_阈值赋值给满足regX₂中的区域块距离相关性 半径若则将赋值给满足regX₂中的区域块距离 相关性半径

列举，若则将r_阈值赋值给满足regX₂中的区域块距离相关性 半径若则将赋值给满足regX₂中的区域块距离 相关性半径

步骤203－3：计算满足regX₂中的任意两个地理标签位置的中心点距离；

与的中心点距离记为

步骤203－4：定义满足regX₂中的距离相关性

列举，与的距离相关性记为 $H\_{\mathrm{rel}}_{B-C}^{X_2}=\frac{r{D}_B^{X_2}+r{D}_C^{X_2}}{\mathrm{CL}{D}_{B-C}^{\mathrm{reg}{X}_2}}.$

在本发明中，统计在第二个区域块regX₂中的距离相关性记为 $H\_{\mathrm{rel}}_{a-b}^{{\mathrm{regX}}_2}=\frac{r{D}_a^{\mathrm{reg}{X}_2}+r{D}_b^{{\mathrm{regX}}_2}}{\mathrm{CL}{D}_{a-b}^{\mathrm{reg}{X}_2}}.$

步骤204：语义相关性

列举，在第二个区域块regX₂中的医院B的字符串长度记为图书馆C的 字符串长度记为

列举，在第二个区域块regX₂中医院B与图书馆C的编辑距离为

列举，在第二个区域块regX₂中的医院B与图书馆C的语义相关性记为 $S\_\mathrm{re}{l}_{B-C}^{X_2}=1-\frac{E_{B-C}^{X_2}}{\max (L_B^{X_2},L_C^{X_2})}.$

在本发明中，在区域信息Q_31-32中的地理标签的语义相关性记为 $S\_\mathrm{re}{l}_{\mathrm{POI}}^{Q_{31-32}}=1-\frac{E_{\mathrm{POI}}^{Q_{31-32}}}{\max \left(L_{\mathrm{POI}}^{Q_{31-32}}\right)}.$

步骤205：区域块是否合并

设置距离相关性阈值记为rel_距离、语义相关性阈值记为rel_语义，并依据rel_距离和rel_语义是否进行区域块的合并处理；

步骤205－1：若且时，将 ${\mathrm{Add}}_C^{X_2}=\left(\begin{array}{c}R\_C_3(x,y),R\_C_4(x,y),R\_C_5(x,y),\\ R\_C_{\gamma }(x,y)\end{array}\right)$合并到 ${\mathrm{Add}}_B^{X_2}=\{R\_B_5(x,y),R\_B_{\beta }(x,y)\}$中，则更新为 ${\mathrm{Add}}_{B\_\mathrm{new}}^{X_2}=\left(\begin{array}{c}R\_B_5(x,y),R\_B_{\beta }(x,y),\\ R\_C_3(x,y),R\_C_4(x,y),R\_C_5(x,y),\\ R\_C_{\gamma }(x,y)\end{array}\right);$并将输出给 LBSN数据库，执行步骤205－2；

步骤205－2：若或时，则与 不进行区域块合并，并将和输出给LBSN数据库。

在本发明中，将第二个区域块regX₂的写入LBSN数据库2的签到点位置信 息采用集合形式表达为$Q_{2-33}=\left\{{\mathrm{checkin}}_{{\mathrm{regX}}_2}\right\}.$

(三)第三区域块

在本发明中，对最后一个区域块regX_y进行地理标签进行地理标签聚类策略 POI-CP的处理步骤为：

步骤301：提取出属于同一区域块中的地理标签

从Q_31-32＝{regX₁,regX₂,…，regX_y}中提取出满足最后一个区域块regX_y的地理标签，若最后一个区域块regX_y中的地理标签仅为D，则满足regX_y的地 理标签为；

${\mathrm{regX}}_y\left(\begin{array}{c}[R\_D_2(x,y),D],[R\_D_3(x,y),D],[R\_D_4(x,y),D],\\ [R\_D_5(x,y),D]\end{array}\right).$

步骤302：地理标签的位置个数获取；

对最后一个区域块regX_y中的地理标签D进行位置归类，得到满足regX_y中 的D地理标签位置${\mathrm{Add}}_D^{X_y}=\left(\begin{array}{c}R\_D_2(x,y),R\_D_3(x,y),R\_D_4(x,y),\\ R\_D_5(x,y)\end{array}\right);$所述 D在regX_y中出现的次数记为且

步骤303：距离相关性

步骤303－1：解析${\mathrm{Add}}_D^{x_y}=\left(\begin{array}{c}R\_D_2(x,y),R\_D_3(x,y),R\_D_4(x,y),\\ R\_D_5(x,y)\end{array}\right)$ 中的经度平均值$\bar{x}\_A=\frac{\underset{i=1}{\overset{{\alpha }^{X_y}}{\Sigma }}R\_A_i\left(x\right)}{{\alpha }^{X_y}}$和纬度平均值$\bar{y}\_A=\frac{\underset{i=1}{\overset{{\alpha }^{X_y}}{\Sigma }}R\_A_i\left(y\right)}{{\alpha }^{X_y}},$i表 示求和关系中的求和指标，得到满足regX_y中的D地理标签位置的位 置中心点解析 ${\mathrm{Add}}_D^{x_y}=\left(\begin{array}{c}R\_D_2(x,y),R\_D_3(x,y),R\_D_4(x,y),\\ R\_D_5(x,y)\end{array}\right)$中每个标签点位置到 的距离，并选取出最大直线距离，记为

在本发明中，统计在最后一个区域块regX_y中的所有地理标签与地理标签位 置的位置中心点之间的最大直线距离且${\mathrm{LD}}_{\mathrm{POI}-\max }^{{\mathrm{regX}}_y}=\left\{{\mathrm{LD}}_{D-\max }^{X_y}\right\}.$

步骤303－2：设置区域块半径阈值记为r_阈值；

若最大直线距离小于区域半径阈值r_阈值，则将r_阈值赋值给所属区域中的区域块 距离相关性半径rD_POI；

若最大直线距离大于等于区域半径阈值r_阈值，则选取最大直线距离作为所属区 域中的区域块距离相关性半径rD_POI；

列举，若则将r_阈值赋值给满足regX_y中的区域块距离相关性 半径若则将赋值给满足regX_y中的区域块距离 相关性半径

步骤303－3：计算满足regX_y中的任意两个地理标签位置的中心点距离；

由于满足regX_y中的地理标签只有D，故r_阈值为中心点距离记为

步骤303－4：定义满足regX_y中的距离相关性

列举，将的距离相关性记为

步骤304：语义相关性

列举，在最后一个区域块regX_y中的教学楼D的字符串长度记为

列举，在最后一个区域块regX_y中由于只有教学楼D，故D的编辑距离记为 且$E_{D-0}^{X_y}=0.$

列举，在最后一个区域块regX_y中的教学楼D的语义相关性记为 $S\_\mathrm{re}{l}_{D-0}^{X_y}=1-\frac{E_{D-0}^{X_y}}{\max (L_D^{X_y},0)},$且$S\_{\mathrm{rel}}_{D-0}^{X_y}=1.$

步骤305：区域块是否合并

设置距离相关性阈值记为rel_距离、语义相关性阈值记为rel_语义，并依据rel_距离 和rel_语义是否进行区域块的合并处理；

在本发明中，由于$E_{D-0}^{X_y}=0$和$S\_{\mathrm{rel}}_{D-0}^{X_y}=1,$因此和 故最后一个区域块regX_y不需要进行区域合并。

在本发明中，将最后一个区域块regX_y的写入LBSN数据库2的签到点位置 信息采用集合形式表达为$Q_{2-33}=\left\{{\mathrm{checkin}}_{{\mathrm{regX}}_y}\right\}.$

热点区域事件计算模块33

热点区域事件计算模块33第一方面接受用户1的热点区域查询请求 Request，所述Request＝{Geo(x,y),dist,Hot}，并将 Request＝{Geo(x,y),dist,Hot}转发给LBSN数据库2；

热点区域事件计算模块33第二方面依据Request＝{Geo(x,y),dist,Hot} 能够在LBSN数据库2中搜索出与Geo(x,y)匹配的热点区域，记为查询返回信 息Q_2-33；

热点区域事件计算模块33第三方面依据时间窗口下的签到频数策略POI-TP 对所述Q_2-33进行计算处理，得到区域热点事件和排名ChecFreq，并将所述 ChecFreq反馈给用户1。

在本发明中，热点区域事件计算模块33会实时计算用户1请求范围内区域的 热点事件，具体是向热点区域聚类数据库2请求各自区域内截止到请求时刻(即 当前时刻t)的历史含有地理签到记录 $Q_{2-33}=\{{\mathrm{checkin}}_{{\mathrm{regX}}_1},{\mathrm{checkin}}_{{\mathrm{regX}}_2},···,{\mathrm{checkin}}_{\mathrm{reg}{X}_y}\}.$

在本发明中，以任意一区域regX_y根据历史地理签到标签检测出热点事件为 例，定义时间窗口为ΔT，在所述ΔT时间段内出现的签到频数为ChecFreq。所述 签到频数ChecFreq是指在ΔT里相同热点区域签到的次数。所述ΔT＝|t-(t-1)|， 当前时刻为t，前一时刻为t-1。

在本发明中，事件定义为任意一区域regX_y中签到频数ChecFreq的变化量， 则事件描述表达形式为Trend：

$\mathrm{Trend}=\frac{{\mathrm{ChecFreq}}^t-{\mathrm{ChecFreq}}^{t-1}}{\mathrm{\Delta T}}$

当Trend超出一定事件检测阈值Trend_阈值时，热点区域事件计算模块33将 区域regX_y标记为热点事件。并根据Trend值的正负把事件标记为激增类型或者 陡降类型。

在本发明中，对热点事件进行排位，即热点事件时间窗口个数越多的排位在前。 在任意一个regX_y里，存在有连续的时间窗口ΔT下，若热点事件的签到频数 ChecFreq超过签到频数阈值ChecFreq_阈值，则选取超过阈值的热点事件连续持续的 时间窗口个数，记为同理可知，在所有的热点区域里，热点事件连续持 续的时间窗口个数，记为$\mathrm{RCU}=\{{\mathrm{CU}}^{{\mathrm{regX}}_1},{\mathrm{CU}}^{{\mathrm{regX}}_2},···,{\mathrm{CU}}^{{\mathrm{regX}}_y}\}.$

事件的活跃程度Rank与ΔT的签到频数和签到持续事件成正比，即：

$\mathrm{Rank}=\underset{i=1}{\overset{{\mathrm{regX}}_y}{\Sigma }}\frac{{\mathrm{ChecFreq}}_i^t}{{\Omega }_i}\times \sqrt{1+\frac{\underset{j\in {\mathrm{regX}}_y}{\max }\left({\mathrm{CU}}^j\right)}{{\mathrm{regX}}_y}}$

其中表示在时间窗口ΔT内的签到数量，regX_y表示任意一区域，即 求和元素，i表示求和指标，Ω_i表示在时间窗口ΔT内用户1所请求范围内区域签 到总数量。表示当前所有热点区域中的时间窗口个数的最大 值，j表示时间窗口个数最大的区域标识号。

本发明提出的一种基于地理标签签到的热点区域事件探测系统，该系统属于基 于位置的社交网中的事件检测技术领域。首先系统会一直不间断得运行LBSN爬 取模块，经向LBSN数据库中写入含有地理标签的签到记录，接下来会采用签到 聚类算法获得大概的地区聚类；然后系统的区域聚类模块会采用含有地理标签的 区域聚类算法计算出精确区域；热点区域计算模块会相应用户的请求，这是系统 唯一对外提供的服务接口，首先该模块会根据用户提交的查询参数，向数据库提 交对应的查询，并对返回来的数据进行区域热点事件检测算法，计算得出热点事 件和事件的排名，并返回给请求用户。

实施例

参见图1、图2所示，假设在LBSN数据库中满足地理标签的用户签到信息 Q_31-2＝R_POI_p(x,y),POI的搜索结果有多个，则应用聚类间隔时间 kcluster-span进行k-means聚类方法处理，得到区域块信息 Q_31-32＝{regX₁,regX₂,…,regX_y}。所述的Q_31-2＝R_POI_p(x,y),POI只是 原始记录，还并没有进行聚类。

假设Q_31-32＝{regX₁,regX₂,…,regX_y}聚类后的粗粒度地理区域为6个，则 区域块数y＝6，即Q_31-32＝{regX₁,regX₂,regX₃,regX₄,regX₅,regX₆}。

在Q_31-32内，区域间的距离关系如下表：

假设请求用户发出当地热点区域查询请求时，系统的运行过程如下：

步骤1：请求用户的推荐请求信息为 Request＝{Geo(x,y),dist,Hot}＝{inR₃,2000,Hot}，inR₃为请求的位置点， 它与其它地区的距离为：

可以看到，在请求范围内，有3个区域满足条件，即regX₁，regX₃，regX₄。 用户的请求首先会被热点区域事件探测系统的热点区域事件计算模块33接收。

步骤2：热点区域事件计算模块33将用户传进来的参数构造成合理的查询语 句请求数据库，数据库则将满足要求的这三个区域regX₁，regX₃，regX₄和它 们的带有地理标签的历史签到记录$Q_{2-33}=\{{\mathrm{checkin}}_{{\mathrm{regX}}_1},{\mathrm{checkin}}_{{\mathrm{regX}}_2},···,{\mathrm{checkin}}_{\mathrm{reg}{X}_y}\}$返回给热点区域事件计算模块33。

步骤3：热点区域事件计算模块33得到签到记录后，开始进行计算。ΔT的 值为1小时，签到频数阈值ChecFreq_阈值为100条，事件检测阈值Trend_阈值为50 条/h，向前寻找4个时间窗口，第一个时间窗口T₁＝t-3ΔT，第二个时间窗口 T₂＝t-2ΔT，第三个时间窗口T₃＝t-ΔT，第四个时间窗口T₄＝t，。

在区域regX₁内，某一事件的签到频数ChecFreq为：

它的最大连续活跃时间窗口值为3(即热点事件连续持续的时间窗口个数 ${\mathrm{CU}}^{{\mathrm{regX}}_1}=3$)。

在区域regX₃内，某一事件的签到频数ChecFreq为：

它的最大连续活跃时间窗口值为3。

在区域regX₄内，当前时段的签到频数ChecFreq为：

它的最大连续活跃时间窗口值为1。

按照${\mathrm{Trend}}_{{\mathrm{regX}}_1}=\frac{{\mathrm{ChecFreq}}^t-{\mathrm{ChecFreq}}^{t-1}}{\mathrm{\Delta T}}=66,$超过了事件检测阈值； 未达到事件检测阈值；超过了事件检测阈值。可 以看到有两个热点区域。分别是regX₁和regX₄。

对于regX₁，它的连续活跃时间窗口值为3，它的事件的活跃程度排名：

${\mathrm{Rank}}_{{\mathrm{regX}}_1}=\underset{i=1}{\overset{4}{\Sigma }}\frac{{\mathrm{ChecFreq}}_i}{{\Omega }_i}\times \sqrt{1+\frac{3}{4}}=0.89\times 1.48=1.31.$

对于regX₄，它的连续活跃时间窗口值为1，它的事件的活跃程度排名：

${\mathrm{Rank}}_{{\mathrm{regX}}_4}=\underset{i=1}{\overset{4}{\Sigma }}\frac{{\mathrm{ChecFreq}}_i}{{\Omega }_i}\times \sqrt{1+\frac{1}{4}}=0.66\times 1.11=0.73.$

热点区域事件计算模块33将计算结果返回给用户。即ChecFreq返回结果为 ChecFreq＝{regX₁:1,regX₄:2}。