一种位置兴趣点聚类方法和相关装置

摘要

本发明实施例公开了一种位置兴趣点聚类方法和相关装置，其中，一种位置兴趣点聚类方法，包括：获取预定时间段内用户的定位点集合；根据定位点集合生成驻留点集合，其中，驻留点集合中的每个驻留点代表一个热区，上述热区满足如下条件：热区中的任意两个定位点的地理位置距离小于两个定位点的定位精度中的较大定位精度；热区中定位点间的时间间隔的最大值大于预设时间阈值；计算驻留点集合中各个驻留点的可信度；根据驻留点集合中各个驻留点的可信度，从驻留点集合中筛选出可信驻留点；将密度相连的可信驻留点聚类成一个位置兴趣点。本发明提供的技术方案能够有效提高POI的可靠性和参考价值。

说明书

技术领域

本发明涉及地理信息处理技术领域，尤其涉及一种位置兴趣点聚类方法 和相关装置。

背景技术

位置兴趣点（POI，Point Of Interest）指的是用户频繁长时间逗留的位置 区域，例如家、办公室、经常光顾的超市等对用户而言有重要意义的区域。

利用手机等终端的Wi-Fi网络、全球定位系统（GPS，Global Positioning  System）、基站标识号（ID，Identity）定位功能等可以获取用户日常活动的轨 迹信息，而这些轨迹信息是由大量具有定位偏差的定位坐标点组成，研究如 何从这些轨迹信息中抽取出用户的POI，对于情境感知和基于位置的服务 （LBS，Location-based Service）应用与服务来说具有重要的价值，目前也是 学术界研究的热点。

目前存在一种基于多个用户GPS轨迹信息挖掘POI的方法，其主要思想 是先利用树状分层图来对多个用户的历史位置数据进行建模，然后基于树状 分层图提出基于超文本主体搜索的推理模型，对个体的一次到访建立从用户 到位置的链接。

然而，上述方法通过时空维度抽取用户的驻留点，该驻留点仅能代表用 户单次到访，不能代表对用户有重要意义的POI地点，且挖掘POI时只是参 考了用户的历史位置数据，挖掘出的POI的可靠性和参考价值低。

发明内容

本发明实施例提供了一种位置兴趣点聚类方法和相关装置，用于提高POI 的可靠性和参考价值。

本发明第一方面提供了一种位置兴趣点聚类方法，包括：

获取预定时间段内用户的定位点集合；

根据上述定位点集合生成驻留点集合，其中，上述驻留点集合中的每个 驻留点代表一个热区，上述热区满足如下条件：上述热区中的任意两个定位 点的地理位置距离小于上述两个定位点的定位精度中的较大定位精度；上述 热区中定位点间的时间间隔的最大值大于预设时间阈值；

计算上述驻留点集合中各个驻留点的可信度，其中，驻留点代表的热区 中的所有定位点的运动状态所对应的平均速度越小，该驻留点的可信度越高；

根据上述驻留点集合中各个驻留点的可信度，从上述驻留点集合中筛选 出可信驻留点，其中，上述可信驻留点的可信度大于预设可信度阈值；

将密度相连的可信驻留点聚类成一个位置兴趣点，其中，上述密度相连 是指两个可信驻留点所代表的热区的范围直接相接或间接相接。

基于本发明第一方面，在第一种可能的实现方式中，

上述根据上述定位点集合生成驻留点集合，包括：

确定满足上述条件的热区；

确定上述热区的几何中心点为代表上述热区的驻留点。

基于本发明第一方面，或者本发明第一方面的第一种可能的实现方式， 在第二种可能的实现方式中，上述计算上述驻留点集合中各个驻留点的可信 度，包括：

获取上述各个驻留点代表的热区中包含的各个定位点的运动状态；

根据公式以及上述各个驻留点代表的热区中包含 的各个定位点的运动状态，计算上述驻留点集合中各个驻留点的可信度，其 中，Conf_i表示驻留点i的可信度，n表示n种可能的运动状态，W_k表示第k 种运动状态的可信度权重，n_k表示驻留点i所代表的热区中运动状态为第k种 运动状态的定位点的个数，其中，每种运动状态对应一个可信度权重，且运 动状态对应的运动速度越小，该运动状态的可信度权重越大。

基于本发明第一方面的第二种可能的实现方式，在第三种可能的实现方 式中，上述获取上述定位点集合中的各个定位点的运动状态，具体为：

根据用户的终端上的传感器数据或者Wi-Fi网络的强度和个数变化，获取 上述定位点集合中的各个定位点的运动状态。

基于本发明第一方面，或者本发明第一方面的第一种可能的实现方式， 或者本发明第一方面的第二种可能的实现方式，或者本发明第一方面的第三 种可能的实现方式，在第四种可能的实现方式中，上述将密度相连的可信驻 留点聚类成一个位置兴趣点，包括：

将密度相连的所有可信驻留点中的所有叶子驻留点依次连接形成的封闭 区域确定为一个位置兴趣点的区域，其中，以叶子驻留点为中心的预设半径 覆盖范围内的所有驻留点的可信度之和均不大于预设门限值。

本发明第二方面提供了一种位置兴趣点聚类装置，包括：

获取单元，用于获取预定时间段内用户的定位点集合；

驻留点生成单元，用于根据上述获取单元获取的定位点集合生成驻留点 集合，其中，上述驻留点集合中的每个驻留点代表一个热区，上述热区满足 如下条件：上述热区中的任意两个定位点的地理位置距离小于上述两个定位 点的定位精度中的较大定位精度；上述热区中定位点间的时间间隔的最大值 大于预设时间阈值；

计算单元，用于计算上述驻留点集合中各个驻留点的可信度，其中，驻 留点代表的热区中的所有定位点的运动状态所对应的平均速度越小，该驻留 点的可信度越高；

过滤单元，用于根据上述计算单元计算出的上述驻留点集合中各个驻留 点的可信度，从上述驻留点集合中筛选出可信驻留点，其中，上述可信驻留 点的可信度大于预设可信度阈值；

聚类单元，用于将密度相连的可信驻留点聚类成一个位置兴趣点，其中， 上述密度相连是指两个可信驻留点所代表的热区的范围直接相接或间接相 接。

基于本发明第二方面，在第一种可能的实现方式中，

上述驻留点生成单元，包括：

第一确定单元，用于确定满足上述条件的热区；

第二确定单元，用于确定上述热区的几何中心点为代表上述热区的驻留 点。

基于本发明第二方面，或者本发明第二方面的第一种可能的实现方式， 在第二种可能的实现方式中，

上述计算单元，包括：

子获取单元，用于获取上述各个驻留点代表的热区中包含的各个定位点 的运动状态；

子计算单元，用于根据公式以及上述子获取单元获 取的上述各个驻留点代表的热区中包含的各个定位点的运动状态，计算上述 驻留点集合中各个驻留点的可信度，其中，Conf_i表示驻留点i的可信度，n表 示n种可能的运动状态，W_k表示第k种运动状态的可信度权重，n_k表示驻留 点i所代表的热区中运动状态为第k种运动状态的定位点的个数，其中，每种 运动状态对应一个可信度权重，且运动状态对应的运动速度越小，该运动状 态的可信度权重越大。

基于本发明第二方面的第二种可能的实现方式，在第三种可能的实现方 式中，上述子获取单元具体用于：根据上述用户的终端上的传感器数据或者 Wi-Fi网络的强度和个数变化，获取上述定位点集合中的各个定位点的运动状 态。

基于本发明第二方面，或者本发明第二方面的第一种可能的实现方式， 或者本发明第二方面的第二种可能的实现方式，或者本发明第二方面的第三 种可能的实现方式，在第四种可能的实现方式中，所示聚类单元具体用于： 将密度相连的所有可信驻留点聚类成一个位置兴趣点；将密度相连的所有可 信驻留点中的所有叶子驻留点依次连接形成的封闭区域确定为一个位置兴趣 点的区域，其中，以叶子驻留点为中心的预设半径覆盖范围内的所有驻留点 的可信度之和均不大于预设门限值。

从以上技术方案可以看出，本发明实施例具有以下优点：

由上可见，本发明实施例中根据定位精度和时间阈值将多个定位点形成 一个驻留点，通过定位精度和时间阈值的约束，能够将大部分短暂停留点、 定位跳变点和途经点滤除，同时，结合驻留点中的定位点的运动状态计算驻 留点的可信度并根据驻留点的可信度筛选掉可信度较低的驻留点，能够进一 步滤除一部分的途中噪音驻留点（如堵车路段、等红灯、缓慢步行等产生的 伪驻留点），使得最终由密度相连的可信驻留点聚类成的位置兴趣点的可靠性 和参考价值更高。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实 施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面 描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲， 在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明提供的一种位置兴趣点聚类方法一个实施例流程示意图；

图2-a为本发明提供的一种应用场景下的定位点集合轨迹示意图；

图2-b为本发明提供的一种应用场景下形成的驻留点集合示意图；

图2-c为本发明提供的一种应用场景下筛选出的可信度驻留点集合示意；

图2-d为本发明提供的一种应用场景下聚类出的POI示意图；

图3为本发明提供的一种位置兴趣点聚类装置一个实施例结构示意图；

图4为本发明提供的一种位置兴趣点聚类装置另一个实施例结构示意图；

图5为本发明提供的一种位置兴趣点聚类装置再一个实施例结构示意图。

具体实施方式

本发明实施例提供了一种位置兴趣点聚类方法和相关装置。

为使得本发明的发明目的、特征、优点能够更加的明显和易懂，下面将 结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整 地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而非全部实施 例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前 提下所获得的各个其他实施例，都属于本发明保护的范围。

下面对本发明实施例提供的一种位置兴趣点聚类方法进行描述，请参阅 图1，本发明实施例中的位置兴趣点聚类方法，包括：

101、获取预定时间段内用户的定位点集合；

本发明实施例中定位点集合包含一个或者多个定位点，定位点用于指示 用户的位置信息。

可选地，定位点为由一个经度值和一个纬度值所代表的GPS位置点，则 位置兴趣点聚类装置从用户的GPS位置数据中获取预定时间段内该用户的定 位点集合。

102、根据上述定位点集合生成驻留点集合；

其中，上述驻留点集合中的每个驻留点代表一个热区，上述热区满足如 下条件：上述热区中的任意两个定位点的地理位置距离小于上述两个定位点 的定位精度中的较大定位精度；上述热区中定位点间的时间间隔的最大值大 于预设时间阈值。

举例说明，假设定位点集合{P_j,P_j+1,...,P_j+L}构成一个可形成驻留点的热区， 则定位点集合{P_j,P_j+1,...,P_j+L}需满足以下两个条件：

1、{P_j,P_j+1,...,P_j+L}中任意两个定位点的地理位置距离小于空间阈值Dth， 其中，Dth不是固定值，它根据所涉及的定位点的不同而不同，具体为两个定 位点的定位精度的最大值，即D_th(P_n,P_m)=max(Radius(P_n),Radius(P_m))。举例说明， 假设定位点P₁的定位精度为5米，定位点P₂的定位精度为10米，则对于定 位点P₁和定位点P₂，D_th(P₁,P₂)等于定位点P₁和定位点P₂中的较大定位精度， 即D_th(P₁,P₂)等于10米，若定位点P₃的定位精度为15米，则对于定位点P₁和 定位点P₃，D_th(P₁,P₃)等于定位点P₁和定位点P₃中的较大定位精度，即D_th(P₁,P₃) 等于15米。

2、由于不同的定位点是在不同的时间点测得，因此，每两个定位点间存 在时间间隔，例如，假设定位点P₁在10：00测得，定位点P₂在10：03测得， 则定位点P₁和定位点P₃的时间间隔为3分钟。本发明实施例中，{P_j,P_j+1,...,P_j+L} 还需要满足：{P_j,P_j+1,...,P_j+L}中定位点间的时间间隔的最大值大于预设时间阈值 T_th（例如，T_th可取5分钟、7分钟或10分钟等），即{P_j,P_j+1,...,P_j+L}中最先测得 的定位点和最后测得的定位点之间的时间间隔大于T_th。其中，T_th可以根据实 际需要具体设定，此处不作限定。

可选地，在确定满足上述条件的热区后，确定上述热区的几何中心点为 代表上述热区的驻留点，该驻留点可以代表热区中的所有定位点。当然，也 可以采用其它方式确定一个热区所对应的驻留点，例如，取热区的重心作为 代表该热区的驻留点，其中，热区的重心与热区内定位点分布情况相关。

103、计算上述驻留点集合中各个驻留点的可信度；

其中，驻留点代表的热区中的所有定位点的运动状态所对应的平均速度 越小，该驻留点的可信度越高。

在一种实现方式中，位置兴趣点聚类装置获取上述驻留点集合中各个驻 留点代表的热区所包含的各个定位点的运动状态，根据上述驻留点集合中各 个驻留点代表的热区所包含的各个定位点的运动状态以及公式 计算上述驻留点集合中各个驻留点的可信度，其中， Conf_i表示驻留点i的可信度，n表示n种可能的运动状态，W_k表示第k种运动 状态的可信度权重，n_k表示驻留点i所代表的热区中运动状态为第k种运动状 态的定位点的个数，其中，每种运动状态对应一个可信度权重，且运动状态 对应的运动速度越小，该运动状态的可信度权重越大。例如，假设用户可能 的运动状态为静止、步行或乘车，则对于这三种运动状态，由于运动状态对 应的运动速度由小到大依次为：静止、步行或乘车，因此，运动状态的可信 度权重由大到小依次为：静止、步行或乘车。

可选地，位置兴趣点聚类装置根据上述用户的终端（如手机、平板电脑、 车载终端等）上的传感器数据（如加速度、陀螺仪等）或者Wi-Fi网络的强度 和个数变化，获取上述定位点集合中的各个定位点的运动状态；或者，位置 兴趣点聚类装置也可以从其它定位设备（如服务器）获取上述定位点集合中 的各个定位点的运动状态，此处不作限定。

104、根据上述驻留点集合中各个驻留点的可信度，从上述驻留点集合中 筛选出可信驻留点；

其中，上述可信驻留点的可信度大于预设可信度阈值。

本发明实施例中，位置兴趣点聚类装置从上述驻留点集合中筛选出可信 驻留点（即可信度大于预设可信度阈值的驻留点），剔除可信度不大于预设可 信度阈值的驻留点。

105、将密度相连的可信驻留点聚类成一个POI；

其中，上述密度相连是指两个可信驻留点所代表的热区的范围直接相接 或间接相接。举例说明，假设可信驻留点P₁的覆盖范围与可信驻留点P₂的覆 盖范围相交，则称可信驻留点P₁和可信驻留点P₂所代表的热区的范围直接相 接，在这种情况下，可信驻留点P₁和可信驻留点P₂密度相连；或者，假设可 信驻留点P₁的覆盖范围与可信驻留点P₃的覆盖范围相交，可信驻留点P₂的覆 盖范围与可信驻留点P₄的覆盖范围相交，可信驻留点P₃的覆盖范围与可信驻 留点P₄的覆盖范围相交，则称可信驻留点P₁和可信驻留点P₂密度所代表的热 区的范围间接相接，在这种情况下，也称可信驻留点P₁和可信驻留点P₂密度 相连。

可选地，若可信驻留点P₁（可以是叶子驻留点，也可以是内部驻留点） 从内部驻留点o密度可达，可信驻留点P₂（可以是叶子驻留点，也可以是内 部驻留点）从内部驻留点o密度可达，则称可信驻留点P₁和信驻留点P₂密度 相连。下面对“内部驻留点”、“叶子驻留点”和“密度可达”进行说明。

内部驻留点：以该驻留点为中心的预设半径覆盖内的所有驻留点的可信 度之和大于预设门限值。

叶子驻留点：以该驻留点为中心的预设半径覆盖内的所有驻留点的可信 度之和不大于预设门限值。

密度可达：给定一串可信驻留点p₁，p₂，......p_n，其中p_i（0<i<n）必需是 内部驻留点，p_n可以是叶子驻留点或内部驻留点，P=p₁，Q=p_n，假设p_i从p_i-1（1<i<(n+1)）直接密度可达，那么驻留点Q从内部驻留点P密度可达。

直接密度可达：如果一个可信驻留点P（可以是叶子驻留点，也可以是内 部驻留点）在某一可信驻留点Q的覆盖半径内，并且可信驻留点Q为内部驻 留点，那么称可信驻留点P从可信驻留点Q直接密度可达。

可选地，将密度相连的所有可信驻留点聚类成一个POI，并且，将密度相 连的所有可信驻留点中的所有叶子驻留点依次连接形成的封闭区域确定为一 个POI的区域，或者，POI的区域也可以为包含密度相连的所有可信驻留点 的最小圆形区域或者方形区域，此处不作限定。

由上可见，本发明实施例中根据定位精度和时间阈值将多个定位点形成 一个驻留点，通过定位精度和时间阈值的约束，能够将大部分短暂停留点、 定位跳变点和途经点滤除，同时，结合驻留点中的定位点的运动状态计算驻 留点的可信度并根据驻留点的可信度筛选掉可信度较低的驻留点，能够进一 步滤除一部分的途中噪音驻留点（如堵车路段、等红灯、缓慢步行等产生的 伪驻留点），使得最终由密度相连的可信驻留点聚类成的位置兴趣点的可靠性 和参考价值更高。

为便于更好地理解本发明技术方案，下面以一具体应用场景对本发明实 施例中的位置兴趣点聚类方法进行描述。

假设预定时间段内用户的定位点集合的轨迹如图2-a所示。

步骤一：位置兴趣点聚类装置使用动态空间阈值和时间阈值，从图2-a 所示的定位点集合中确定满足如下两个条件的热区：1、热区中的任意两个定 位点的地理位置距离小于上述两个定位点中的较大定位精度；2、热区中定位 点间的时间间隔的最大值大于预设时间阈值。在确定出满足条件的热区后， 确定热区中的几何中心点作为代表该热区的驻留点，形成若干个驻留点，得 到如图2-b所示的驻留点轨迹图，其中，图2-b中的每个小黑点代表一个形成 的驻留点，每个驻留点能够表征用户在同一地点逗留时所产生的大量定位点， 将图2-b与图2-a比较后可见，图2-b中滤除掉了大部分短暂停留点、定位跳 变点和途径点。

步骤二：位置兴趣点聚类装置依据形成一个驻留点的所有定位点上用户 的运动状态（如静止、步行、乘车等），分别计算出各个驻留点的可信度，其 中，若用户在一个驻留点的所有定位点的运动状态所对应的平均运动速度越 小，则该驻留点的可信度越大，比如，若一个驻留点上，运动状态为静止（即 运动速度为0）的定位点占形成该驻留点的所有定位点的比重越多，则该驻留 点的可信度越大，反之，若一个驻留点上，运动状态为乘车（即运动速度远 大于0）的定位点占形成该驻留点的所有定位点的比重越多，则该驻留点的可 信度越小。在计算出每个驻留点的可信度后，从图2-b所示的驻留点集合中剔 除可信度不大于预设可信度阈值的驻留点，即从图2-b所示的驻留点集合中筛 选出可信度大于预设可信度阈值的驻留点，得到如图2-c所示的可信驻留点集 合。将图2-c与图2-b比较后可见，图2-c对一部分途中噪音驻留点（例如： 堵车路段、等红灯、缓慢步行对应的伪驻留点）进行了滤除。

步骤三、对上述驻留点进行基于可信度的聚类，找出所有密度相连的最 大驻留点集合（即该集合中任意两个可信驻留点都为密度相连），将该最大驻 留点集合聚成一个POI，该POI的区域可以由该最大驻留点集合中所有叶子驻 留点依次连接形成的封闭多边形来表示，如图2-d所示的聚类得到的POI示意 图。步骤三在聚类过程中考虑各驻留点的可信度，能提高POI聚类的可靠性， 使POI包含的区域范围更趋近于真实情况。

本发明实施例还提供一种位置兴趣点聚类装置，如图3所示，本发明实 施例中的位置兴趣点聚类装置300，包括：获取单元301，驻留点生成单元302， 计算单元303，过滤单元304和聚类单元305。

其中：

获取单元301，用于获取预定时间段内用户的定位点集合；

本发明实施例中定位点集合包含一个或者多个定位点，定位点用于指示 用户的位置信息。

可选地，定位点为由一个经度值和一个纬度值所代表的GPS位置点，则 位置兴趣点聚类装置从用户的GPS位置数据中获取预定时间段内该用户的定 位点集合。

驻留点生成单元302，用于根据获取单元301获取的定位点集合生成驻留 点集合，其中，上述驻留点集合中的每个驻留点代表一个热区，上述热区满 足如下条件：上述热区中的任意两个定位点的地理位置距离小于上述两个定 位点的定位精度中的较大定位精度；上述热区中定位点间的时间间隔的最大 值大于预设时间阈值；

可选地，在图3所示实施例的基础上，如图4所示的位置兴趣点聚类装 置400，驻留点生成单元302包括：第一确定单元3021，用于确定满足上述 条件的热区；第二确定单元3022，用于确定上述热区的几何中心点为代表上 述热区的驻留点。

计算单元303，用于计算上述驻留点集合中各个驻留点的可信度，其中， 驻留点代表的热区中的所有定位点的运动状态所对应的平均速度越小，该驻 留点的可信度越高；

可选地，在图3或图4所示实施例的基础上，计算单元303包括：

子获取单元，用于获取上述各个驻留点代表的热区中包含的各个定位点 的运动状态；

子计算单元，用于根据公式以及上述子获取单元获 取的上述各个驻留点代表的热区中包含的各个定位点的运动状态，计算上述 驻留点集合中各个驻留点的可信度，其中，Conf_i表示驻留点i的可信度，n表 示n种可能的运动状态，W_k表示第k种运动状态的可信度权重，n_k表示驻留 点i所代表的热区中运动状态为第k种运动状态的定位点的个数，其中，每种 运动状态对应一个可信度权重，且运动状态对应的运动速度越小，该运动状 态的可信度权重越大。

可选地，上述子获取单元具体用于：根据上述用户的终端上的传感器数 据（如加速度、陀螺仪等）或者Wi-Fi网络的强度和个数变化，获取上述定位 点集合中的各个定位点的运动状态。

过滤单元304，用于根据计算单元303计算出的上述驻留点集合中各个驻 留点的可信度，从上述驻留点集合中筛选出可信驻留点，其中，上述可信驻 留点的可信度大于预设可信度阈值；

聚类单元305，用于将密度相连的可信驻留点聚类成一个位置兴趣点，其 中，上述密度相连是指两个可信驻留点所代表的热区的范围直接相接或间接 相接。

可选地，聚类单元305还用于：将密度相连的所有可信驻留点聚类成一 个位置兴趣点；将密度相连的所有可信驻留点中的所有叶子驻留点依次连接 形成的封闭区域确定为一个位置兴趣点的区域，其中，以叶子驻留点为中心 的预设半径覆盖范围内的所有驻留点的可信度之和均不大于预设门限值。

需要说明的是，本发明实施例中的位置兴趣点聚类装置可以为终端（如 手机、平板电脑、笔记本、台式计算机或其它具备定位功能的终端等），或者， 位置兴趣点聚类装置可以为独立于终端，且能够与该终端通过有线或者无线 方式进行通讯的装置，此处不作限定。

需要说明的是，本发明实施例中的位置兴趣点聚类装置可以如上述方法 实施例中的位置兴趣点聚类装置，可以用于实现上述方法实施例中的全部技 术方案，其各个功能模块的功能可以根据上述方法实施例中的方法具体实现， 其具体实现过程可参照上述实施例中的相关描述，此处不再赘述。

由上可见，本发明实施例中根据定位精度和时间阈值将多个定位点形成 一个驻留点，通过定位精度和时间阈值的约束，能够将大部分短暂停留点、 定位跳变点和途经点滤除，同时，结合驻留点中的定位点的运动状态计算驻 留点的可信度并根据驻留点的可信度筛选掉可信度较低的驻留点，能够进一 步滤除一部分的途中噪音驻留点（如堵车路段、等红灯、缓慢步行等产生的 伪驻留点），使得最终由密度相连的可信驻留点聚类成的位置兴趣点的可靠性 和参考价值更高。

本发明实施例还提供一种计算机存储介质，其中，该计算机存储介质存 储有程序，该程序执行包括上述方法实施例中记载的部分或全部布置。

下面对本发明实施中的另一种应用于对等网络的设备进行描述，请参阅 图5，本发明实施例中的位置兴趣点聚类装置500包括：

输入装置501、输出装置502、存储器503以及处理器504（位置兴趣点 聚类装置500的处理器504的数量可以是一个或者多个，图5以一个处理器 为例）。在本发明的一些实施例中，输入装置501、输出装置502、存储器503 以及处理器504可以通过总线或其它方式连接，如图5所示是以通过总线连 接为例。其中，存储器503中用来储存从输入装置501输入的数据，且还可 以储存处理器504处理数据的必要文件等信息；输入装置501和输出装置502 可以包括位置兴趣点聚类装置500与其他设备通信的端口，且还可以包括位 置兴趣点聚类装置500外接的输出设备比如显示器、键盘、鼠标和打印机等， 具体地输入装置501可以包括鼠标和键盘等，而输出装置502可以包括显示 器等，在本实施例中输入装置501和输出装置502中与其他设备通信的端口 为天线和/或通信线缆。

其中，处理器504执行如下步骤：

获取预定时间段内用户的定位点集合；

根据上述定位点集合生成驻留点集合，其中，上述驻留点集合中的每个 驻留点代表一个热区，上述热区满足如下条件：上述热区中的任意两个定位 点的地理位置距离小于上述两个定位点的定位精度中的较大定位精度；上述 热区中定位点间的时间间隔的最大值大于预设时间阈值；

计算上述驻留点集合中各个驻留点的可信度，其中，驻留点代表的热区 中的所有定位点的运动状态所对应的平均速度越小，该驻留点的可信度越高；

根据上述驻留点集合中各个驻留点的可信度，从上述驻留点集合中筛选 出可信驻留点，其中，上述可信驻留点的可信度大于预设可信度阈值；

将密度相连的可信驻留点聚类成一个位置兴趣点，其中，上述密度相连 是指两个可信驻留点所代表的热区的范围直接相接或间接相接。

可选地，定位点为由一个经度值和一个纬度值所代表的GPS位置点，则 处理器504用于从用户的GPS位置数据中获取预定时间段内该用户的定位点 集合。

可选地，处理器504在确定满足上述条件的热区后，确定上述热区的几 何中心点为代表上述热区的驻留点，该驻留点可以代表热区中的所有定位点。 当然，也可以采用其它方式确定一个热区所对应的驻留点，例如，取热区的 重心作为代表该热区的驻留点，其中，热区的重心与热区内定位点分布情况 相关。

可选地，处理器504获取上述驻留点集合中各个驻留点代表的热区所包 含的各个定位点的运动状态，根据上述驻留点集合中各个驻留点代表的热区 所包含的各个定位点的运动状态以及公式计算上述驻 留点集合中各个驻留点的可信度，其中，Conf_i表示驻留点i的可信度，n表示 n种可能的运动状态，W_k表示第k种运动状态的可信度权重，n_k表示驻留点i 所代表的热区中运动状态为第k种运动状态的定位点的个数，其中，每种运 动状态对应一个可信度权重，且运动状态对应的运动速度越小，该运动状态 的可信度权重越大。例如，假设用户可能的运动状态为静止、步行或乘车， 则对于这三种运动状态，由于运动状态对应的运动速度由小到大依次为：静 止、步行或乘车，因此，运动状态的可信度权重由大到小依次为：静止、步 行或乘车。

可选地，处理器504根据上述用户的终端上的传感器数据（如加速度、 陀螺仪等）或者Wi-Fi网络的强度和个数变化，获取上述定位点集合中的各个 定位点的运动状态；或者，位置兴趣点聚类装置也可以从其它定位设备（如 服务器）获取上述定位点集合中的各个定位点的运动状态，此处不作限定。

可选地，处理器504将密度相连的所有可信驻留点聚类成一个POI，并且， 将密度相连的所有可信驻留点中的所有叶子驻留点依次连接形成的封闭区域 确定为一个POI的区域，或者，POI的区域也可以为包含密度相连的所有可 信驻留点的最小圆形区域或者方形区域，此处不作限定。

需要说明的是，本发明实施例中的位置兴趣点聚类装置可以为终端（如 手机、平板电脑、笔记本、台式计算机或其它具备定位功能的终端等），或者， 位置兴趣点聚类装置可以为独立于终端，且能够与该终端通过有线或者无线 方式进行通讯的装置，此处不作限定。

需要说明的是，本发明实施例中的位置兴趣点聚类装置可以如上述方法 实施例中的位置兴趣点聚类装置，可以用于实现上述方法实施例中的全部技 术方案，其各个功能模块的功能可以根据上述方法实施例中的方法具体实现， 其具体实现过程可参照上述实施例中的相关描述，此处不再赘述。

由上可见，本发明实施例中根据定位精度和时间阈值将多个定位点形成 一个驻留点，通过定位精度和时间阈值的约束，能够将大部分短暂停留点、 定位跳变点和途经点滤除，同时，结合驻留点中的定位点的运动状态计算驻 留点的可信度并根据驻留点的可信度筛选掉可信度较低的驻留点，能够进一 步滤除一部分的途中噪音驻留点（如堵车路段、等红灯、缓慢步行等产生的 伪驻留点），使得最终由密度相连的可信驻留点聚类成的位置兴趣点的可靠性 和参考价值更高。

需要说明的是，对于前述的各方法实施例，为了简便描述，故将其都表 述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并不受所描 述的动作顺序的限制，因为依据本发明，某些步骤可以采用其它顺序或者同 时进行。在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中 没有详述的部分，可以参见其它实施例的相关描述。

在本申请所提供的几个实施例中，应该理解到，所揭露的装置和方法， 可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的， 例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外 的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或 一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或 直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连 接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作 为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方， 或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或 者全部单元来实现本实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中， 也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单 元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单 元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售 或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本 发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的 全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个 存储介质中，包括若干指令用以使得一台计算机设备（可以是个人计算机， 服务器，或者网络设备等）执行本发明各个实施例所述方法的全部或部分步 骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器（ROM，Read-Only  Memory）、随机存取存储器（RAM，Random Access Memory）、磁碟或者光盘 等各种可以存储程序代码的介质。

以上对本发明所提供的一种位置兴趣点聚类方法和相关装置进行了详细 介绍，对于本领域的一般技术人员，依据本发明实施例的思想，在具体实施 方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对 本发明的限制。