顾及空间实例距离权重的自适应同位模式获取方法和装置

摘要

本发明提供一种顾及空间实例距离权重的自适应同位模式获取方法和装置；所述方法，包括：将同一空间特征的实例作为目标图层，构建泰森多边形，基于当前目标图层的实例与其它特征实例在泰森多边形影响范围的连接关系，构建归一化实例对偶表；对归一化实例对偶表的距离集合进行分布参数计算，获得归一化距离截断参数；利用归一化距离截断参数构造距离回馈函数，计算任意两个不同特征的连接实例对的距离回馈值；在所述距离回馈阈值下，获取最终的基于距离回馈函数计算的同位模式。解决了常规同位模式挖掘方法在区域适应性、高效性和有效性方面的不足。

说明书

技术领域

本发明涉及空间数据模式挖掘领域，尤其涉及一种针对空间点要 素数据的自适应的，并且考虑点要素邻近距离权重的同位模式挖掘方 法和装置。

背景技术

空间同位模式是指一系列空间特征的组合，这些组合的点实例要 素在同一地点频繁的出现，往往表征着它们在空间上有某种普遍的依 赖关系。同位模式挖掘目前已经在种群分布、移动通讯、公共安全、 环境管理、城市规划等领域有广泛的应用，其挖掘的结果可以为学者 进一步研究空间特征分布的内在机理提供线索，也可以辅助决策者进 行科学的预判。以城市规划为例，有人发现某一新城大部分的学校周 边1000米没有邮政点，而利用北京核心功能区的设施数据进行同位 模式挖掘，其结果表明学校和邮政点属于显著度为89％的同位模式， 基于该事实，决策者可适量的将邮政引入学校周边，以减小人口流动 半径，缓建交通压力，降低各方面的资源浪费。

传统的同位模式挖掘方法普遍需要用户自行设定统一的距离阈 值，即使其中有一些由于所处理的数据类型和挖掘目标有所拓展而在 原来距离度量的指标上做了改进而换成了其它指标，如把距离阈值改 为密度阈值。然而，这种仅凭用户经验来设定距离阈值的方法很不现 实：区域具有特异性，区域上的数据分布也有疏密之分，偏小的距离 阈值难以挖出有用的模式，偏大的距离阈值会导致大量无用的模式产 生。虽然目前已有一些改进方法不需要用户设置距离阈值，但他们普 遍利用最近邻思路或迭代优化的方法对算法进行改造，很难对实例间 的距离特征有全局的认识，而考虑全局连接关系的效率问题会限制算 法在大数据集上的计算。其次，传统方法基于参与度的流行模式判定 方法，在计算中并没有考虑实例之间的连接紧密程度，即没有讨论实 例之间的距离权重对模式流行程度的影响。而实际上，根据地理学第 一定律，相近的事物联系更紧密，所以近距离实例关系对模式流行程 度大小的影响，要大于远距离的实例关系。因此，需要构建一种新型 有效的计算体系来评价模式的显著性。

总之，目前没有相关的文献或公开的方法，能够在同时考虑区域 数据疏密和实例之间距离权重影响的情况下，高效快速的发现空间上 的同位模式。

发明内容

本发明旨在解决上面描述的问题。本发明的一个目的是提供一种 解决以上问题中的任何一个的顾及空间实例距离权重的自适应同位 模式获取方法和装置。具体为：

本发明的一方面提供了一种顾及空间实例距离权重的自适应同 位模式获取方法，包括：

将同一空间特征的实例作为目标图层，构建泰森多边形，基于当 前目标图层的实例与其它特征实例在泰森多边形影响范围的连接关 系，构建归一化实例对偶表；

对归一化实例对偶表的距离集合进行分布参数计算，获得归一化 距离截断参数；

利用归一化距离截断参数构造距离回馈函数，计算任意两个不同 特征的连接实例对的距离回馈值；

在所述距离回馈阈值下，获取最终的基于距离回馈函数计算的同 位模式。

本发明提供的方法还具有如下特点：所述构建归一化实例对偶表 的步骤包括：

针对每一类空间特征e_i，将其实例作为目标图层，创建泰森多边 形图；

基于泰森多边形图所划定的目标实例的影响区间，建立每一个实 例与其它特征e_j的实例的关联关系，并将这些关联的实例对和它 们的距离存储在二维哈希表table_instance_vor中；其中， table_instance_vor(e_i,e_j)为二阶有序模式(e_i,e_j)的Cell信息，表示以e_i为目 标图层，特征为e_j的实例与目标图层实例进行连接所获取的行实例 信息，表示特征为e_i的第k个实例，Cell信息包括二阶有序模式 (e_i,e_j)的可连接实例对insPair和其对应的距离值dis；

通过公式(1)，计算不同特征的连接实例对之间的归一化距离， 替换所述二维哈希表的距离值：

$Nordis\left(p_k^{e_i},p_w^{e_j}\right)=\frac{dis\left(p_k^{e_i},p_w^{e_j}\right)-\min \left({\mathrm{Dis}}_{VP}\right)}{\max \left({\mathrm{Dis}}_{VP}\right)-\min \left({\mathrm{Dis}}_{VP}\right)}---\left(1\right),$

其中，dis(a,b)表示两个实例a,b之间的欧氏距离，

Dis_VP表示table_instance_vor中所有的实例对的距离集合，

min(T)和max(T)分别表示取集合T的最小和最大值；

对所述二维哈希表进行无序处理，得到归一化实例对偶表 步骤包括：

把满足j>i的table_instance_vor(e_j,e_i)中的任意有序二阶模式Cell信息 的实例对顺序互换后，得到新的二维哈希表

将所述新的二维哈希表中满足j>i的的Cell 信息与原table_instance_vor(e_i,e_j)对应的Cell信息进行求并处理，得到最终 的归一化实例对偶表

本发明提供的方法还具有如下特点：对于实例数大于12000的数 据集，利用所述归一化实例对偶表中的归一化距离集合，在显著水平 α＝0.05的前提下，进行广义极大值分布函数的参数拟合，对于χ²检 验中拟合优度大于0.8的情况，设定所述的归一化距离截断为 μ±stderr；其中μ表示广义极值极大值拟合函数的位置参数，stderr 表示拟合的残差；或者，

对于其它不符合实例数和拟合优度条件的情况，将归一化距离的 均值作为截断值。

本发明提供的方法还具有如下特点：利用所述归一化距离截断参 数，构建距离回馈函数，计算任意两个不同特征的连接实例对的距离回馈值：

$\mathrm{Re}ward\left(p_k^{e_i},p_w^{e_j}\right)=\left(\begin{array}{cc}{\left(\frac{l_{close}-Nordis\left(p_k^{e_i},p_w^{e_j}\right)}{l_{close}}\right)}^2& Nordis\left(p_k^{e_i},p_w^{e_j}\right)<l_{close}\\ -{\left(\frac{Nordis\left(p_k^{e_i},p_w^{e_j}\right)-l_{far}}{1-l_{far}}\right)}^2& Nordis\left(p_k^{e_i},p_w^{e_j}\right)>l_{far}\\ 0& l_{close}\le Nordis\left(p_k^{e_i},p_w^{e_j}\right)\le l_{far}\end{array}\right)---\left(2\right),$

其中，l_close＝μ-stderr，且l_far＝μ+stderr。

本发明提供的方法还具有如下特点：在所述距离回馈阈值下，获 取最终的基于距离回馈函数计算的同位模式的步骤包括：

以所述归一化实例对偶表的行列位置所对应的特征对{e_i,e_j}为初 始的候选同位模式c，迭代以下子步骤1-5，直到|c|阶同位模式没有 大于距离回馈阈值的成员，其中，j>i，

当|c|＝2时，省略子步骤1-2，直接跳转到子步骤3；

子步骤1：对于候选模式c＝{e_i...e_k}，根据所述归一化实例对偶表 中的实例对，求出候选模式的团实例insClique_c，其中，候选模式c中 包含的特征按照字典序进行排列，即满足k≥j>i，insClique_c是指基于 泰森多边形，在空间上有全连接关系的不同特征的实例的组合，即团 实例中抽取的任意两个实例对，在归一化实例对偶表中都能找到对应 项；

子步骤2：根据公式(3)，求算候选模式c中包含的任意两个 二阶模式{e_i,e_j}的实例对在insClique_c约束下的距离回馈值：

${\mathrm{Reward}}_c\left(p_k^{e_i},p_w^{e_j}\right)=\left(\begin{array}{cc}\mathrm{Re}ward\left(p_k^{e_i},p_w^{e_j}\right)& \left(p_k^{e_i},p_w^{e_j}\right)\in {\pi }_{\left\{e_i,e_j\right\}}\left({\mathrm{insClique}}_c\right)\\ -\left|\right|\mathrm{Re}ward\left(p_k^{e_i},p_w^{e_j}\right)\left|\right|& \left(p_k^{e_i},p_w^{e_j}\right)\notin {\pi }_{\left\{e_i,e_j\right\}}\left({\mathrm{insClique}}_c\right)\end{array}\right)---\left(3\right),$

其中，表示求取二阶模式{e_i,e_j}在insClique_c上的投 影；

子步骤3：通过公式(4)，求算二阶模式{e_i,e_j}在c＝{e_i...e_k}约束 下的距离回馈值：

$\begin{array}{c}{\mathrm{Reward}}_c\left(e_i,e_j\right)=\\ avg\left\{{\mathrm{Reward}}_c\left(p_k^{e_i},p_w^{e_j}\right)|\left(p_k^{e_i},p_w^{e_j}\right)\in table\_{\mathrm{instance}}_{\overline{vor}}\left(e_i,e_j\right).insPair\right\}\end{array}---\left(4\right),$

其中，表示二阶模式{e_i,e_j}对应的归一 化实例对偶表中的所有实例对集合，avg表示求算平均值；

子步骤4：通过公式(5)，求算模式c＝{e_i...e_k}的基于距离回馈 函数计算的流行程度：

Reward_c＝min_i＜j≤k{Reward_c(e_i,e_j)}(5)，

将大于给定距离回馈阈值θ的候选模式判定为最终的|c|阶同位 模式，即最终的同位模式需满足Reward_c＞θ；

子步骤5：以|c|阶同位模式为依据，将前|c|-1位具有相同特征 的同位模式求并，获取|c|+1阶候选同位模式c’，令c＝c’。

本发明的另一个方面还提供了一种顾及空间实例距离权重的自 适应同位模式获取装置，包括：

归一化实例对偶表构建模块，用于将同一空间特征的实例作为目 标图层，构建泰森多边形，基于当前目标图层的实例与其它特征实例 在泰森多边形影响范围的连接关系，构建归一化实例对偶表；

归一化距离截断参数获取模块，用于对归一化实例对偶表的距离 集合进行分布参数计算，获得归一化距离截断参数；

实例对距离回馈值计算模块，用于利用归一化距离截断参数构造 距离回馈函数，计算任意两个不同特征的连接实例对的距离回馈值；

同位模式获取模块，用于在所述距离回馈阈值下，获取最终的基 于距离回馈函数计算的同位模式。

本发明提供的装置还具有如下特点：所述归一化实例对偶表构建 模块具体用于：

泰森多边形创建单元，用于针对每一类空间特征e_i，将其实例作 为目标图层，创建泰森多边形图；

二维哈希表创建单元，用于基于泰森多边形图所划定的目标实例 的影响区间，建立每一个实例与其它特征e_j的实例的关联关系， 并将这些关联的实例对和它们的距离存储在二维哈希表 table_instance_vor中；其中，table_instance_vor(e_i,e_j)为二阶有序模式(e_i,e_j)的 Cell信息，表示以e_i为目标图层，特征为e_j的实例与目标图层实例 进行连接所获取的行实例信息，表示特征为e_i的第k个实例，Cell 信息包括二阶有序模式(e_i,e_j)的可连接实例对insPair和其对应的距 离值dis；

归一化距离计算单元，用于计算不同特征的连接实例对之间的归 一化距离，替换所述二维哈希表的距离值，见公式(1)：

$Nordis\left(p_k^{e_i},p_w^{e_j}\right)=\frac{dis\left(p_k^{e_i},p_w^{e_j}\right)-\min \left({\mathrm{Dis}}_{VP}\right)}{\max \left({\mathrm{Dis}}_{VP}\right)-\min \left({\mathrm{Dis}}_{VP}\right)}---\left(1\right),$

其中，dis(a,b)表示两个实例a,b之间的欧氏距离，

Dis_VP表示table_instance_vor中所有的实例对的距离集合，

min(T)和max(T)分别表示取集合T的最小和最大值；

无序处理单元，用于对所述二维哈希表进行无序处理，得到归一 化实例对偶表

所述无序处理单元，具体用于：

把满足j>i的table_instance_vor(e_j,e_i)中的任意有序二阶模式Cell信息 的实例对顺序互换后，得到新的二维哈希表

将所述新的二维哈希表中满足j>i的的Cell 信息与原table_instance_vor(e_i,e_j)对应的Cell信息进行求并处理，得到最终 的归一化实例对偶表

本发明提供的装置还具有如下特点：所述归一化距离截断参数获 取模块具体用于：

对于实例数大于12000的数据集，利用所述归一化实例对偶表中 的归一化距离集合，在显著水平α＝0.05的前提下，进行广义极大值 分布函数的参数拟合，对于χ²检验中拟合优度大于0.8的情况，设定 所述的归一化距离截断为μ±stderr；其中μ表示广义极值极大值拟合 函数的位置参数，stderr表示拟合的残差；或者，

对于其它不符合实例数和拟合优度条件的情况，将归一化距离的 均值作为截断值。

本发明提供的装置还具有如下特点：所述实例对距离回馈值计算 模块具体用于，计算任意两个不同特征的连接实例对的距离 回馈值，见公式(2)：

$\mathrm{Re}ward\left(p_k^{e_i},p_w^{e_j}\right)=\left(\begin{array}{cc}{\left(\frac{l_{close}-Nordis\left(p_k^{e_i},p_w^{e_j}\right)}{l_{close}}\right)}^2& Nordis\left(p_k^{e_i},p_w^{e_j}\right)<l_{close}\\ -{\left(\frac{Nordis\left(p_k^{e_i},p_w^{e_j}\right)-l_{far}}{1-l_{far}}\right)}^2& Nordis\left(p_k^{e_i},p_w^{e_j}\right)>l_{far}\\ 0& l_{close}\le Nordis\left(p_k^{e_i},p_w^{e_j}\right)\le l_{far}\end{array}\right)---\left(2\right),$

其中，l_close＝μ-stderr，且l_far＝μ+stderr。

本发明提供的装置还具有如下特点：所述同位模式获取模块，具 体用于：

以所述归一化实例对偶表的行列位置所对应的特征对{e_i,e_j}为初 始的候选同位模式c，迭代以下子步骤1-5，直到|c|阶同位模式没有 大于距离回馈阈值的成员，其中，j>i，

当|c|＝2时，省略子步骤1-2，直接跳转到子步骤3；

子步骤1：对于候选模式c＝{e_i...e_k}，根据所述归一化实例对偶表 中的实例对，求出候选模式的团实例insClique_c，其中，候选模式c中 包含的特征按照字典序进行排列，即k≥j>i，insClique_c是指基于泰森 多边形，在空间上有全连接关系的不同特征的实例的组合，即团实例 中抽取的任意两个实例对，在归一化实例对偶表中都能找到对应项；

子步骤2：根据公式(3)，求算候选模式c中包含的任意两个 二阶模式{e_i,e_j}的实例对在insClique_c约束下的距离回馈值：

${\mathrm{Reward}}_c\left(p_k^{e_i},p_w^{e_j}\right)=\left(\begin{array}{cc}\mathrm{Re}ward\left(p_k^{e_i},p_w^{e_j}\right)& \left(p_k^{e_i},p_w^{e_j}\right)\in {\pi }_{\left\{e_i,e_j\right\}}\left({\mathrm{insClique}}_c\right)\\ -\left|\right|\mathrm{Re}ward\left(p_k^{e_i},p_w^{e_j}\right)\left|\right|& \left(p_k^{e_i},p_w^{e_j}\right)\notin {\pi }_{\left\{e_i,e_j\right\}}\left({\mathrm{insClique}}_c\right)\end{array}\right)---\left(3\right),$

其中，表示求取二阶模式{e_i,e_j}在insClique_c上的投 影；

子步骤3：通过公式(4)，求算二阶模式{e_i,e_j}在c＝{e_i...e_k}约束 下的距离回馈值：

$\begin{array}{c}{\mathrm{Reward}}_c\left(e_i,e_j\right)=\\ avg\left\{{\mathrm{Reward}}_c\left(p_k^{e_i},p_w^{e_j}\right)|\left(p_k^{e_i},p_w^{e_j}\right)\in table\_{\mathrm{instance}}_{\overline{vor}}\left(e_i,e_j\right).insPair\right\}\end{array}---\left(4\right),$

其中，表示二阶模式{e_i,e_j}对应的归一 化实例对偶表中的所有实例对集合，avg表示求算平均值；

子步骤4：通过公式(5)，求算模式c＝{e_i...e_k}的基于距离回馈 函数计算的流行程度：

Reward_c＝min_i＜j≤k{Reward_c(e_i,e_j)}(5)，

将大于给定距离回馈阈值θ的候选模式判定为最终的|c|阶同位 模式，即最终的同位模式需满足Reward_c＞θ；

子步骤5：以|c|阶同位模式为依据，将前|c|-1位具有相同特征 的同位模式求并，获取|c|+1阶候选同位模式c’，令c＝c’。

同位模式是一组空间特征的子集，表示他们的实例组合在空间上 频繁的出现。现有相关技术中，很难在同时考虑区域数据疏密和实例 之间距离权重影响的情况下，高效快速的发现空间上的同位模式。

本发明针对该问题，提出了一种基于泰森多边形和距离回馈函数 的同位模式挖掘方式，利用泰森多边形的特性，在实例的影响区域内 确立不同特征实例间的领域关系，并以此为依据，获得实例之间的极 大距离统计特征，而后将特征参数用于构建候选模式的距离回馈函数， 来度量模式的流行程度。

该方法的优点在于：1)省去了用户预先设定距离阈值的操作， 规避了在未知区域上进行挖掘的不确定性；

2)考虑了实例之间距离权重对模式流行程度的影响，更符合实 际应用场景；

3)泰森多边形的使用，极大降低了实例对连接的计算量，使得 运算效率大幅提高。

参照附图来阅读对于示例性实施例的以下描述，本发明的其它特 性特征和优点将变得清晰。

附图说明

并入到说明书中并且构成说明书的一部分的附图示出了本发明 的实施例，并且与描述一起用于解释本发明的原理。在这些附图中， 类似的附图标记用于表示类似的要素。下面描述中的附图是本发明的 一些实施例，而不是全部实施例。对于本领域普通技术人员来讲，在 不付出创造性劳动的前提下，可以根据这些附图获得其它的附图。

图1为本发明的实施例一提供的一种顾及空间实例距离权重的 自适应同位模式获取方法的流程图；

图2为构建归一化实例对偶表的方法示意图；

图3为从二阶候选同位模式，获取最终的基于距离回馈函数计算 的同位模式的迭代流程图；

图4为本发明的实施例二提供的一种顾及空间实例距离权重的 自适应同位模式获取装置的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结 合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、 完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是 全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有 做出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护 的范围。需要说明的是，在不冲突的情况下，本申请中的实施例及实 施例中的特征可以相互任意组合。

为了更好的对本发明的实施例所提供的技术方案进行阐述，首先 对如下概念进行说明：

泰森多边形：是由一组连接两邻接点的直线的垂直平分线组成的 连续多边形几何。它按照最邻近原则划分平面，每个点与它的最近邻 区域相关联。

SHP数据类型：shapefile的简称，是ESRI公司开发的一种空间 数据开放格式。

有序模式：是指一系列有排序的空间特征的向量。

广义极值分布：符合高峰胖尾的曲线特征，是极值理论的一个重 要分支，统一了Gumbel,Fréchet和Weibull三种极值分布模型，用于 模拟变量为极值序列的应用场景，在气象、经济学上已有广泛的应用。 该分布函数涉及三个关键参数，即位置参数μ，尺度参数σ，和形状 参数k。

下面结合附图，对本发明的实施例一进行说明。

本发明提供一种顾及空间实例距离权重的自适应同位模式获取 方法，输入为欧式空间的点状SHP数据P＝{p₁,p₂,...p_n}，以及这些数 据所涉及到的空间特征类型E＝{e₁,e₂,...e_m}，其中，每个点实例包含 编号、类型和X、Y坐标(为了强调实例的空间特征，以下将特征为 e_i的第j个实例表示为)。该方法的流程如图1所示，包括：

步骤101、将同一空间特征的实例作为目标图层，构建泰森多边 形，基于当前目标图层的实例与其它特征实例在泰森多边形影响范围 的连接关系，构建归一化实例对偶表；

归一化实例对偶表的构建理念源于自然界的一个性质：大多数物 体在空间上会处于它们形成的场力的平衡点。两种类型(A、B)的 物体若在空间上存在某种关系，那属于类型A的物体更倾向于受到它 周边场力最大的B类型的物体的影响，反之亦然。由此可推理出，若 A,B类型相互吸引，那么它们的实例大多会分布在彼此影响区域的核 地带，反之则会分布在彼此场力最薄弱的边缘地带。由于其连接操作 被限制在单个实例的影响范围内，因此其连接数相比传统的方法，有 很大程度的减少。该步骤涉及三个子步骤：

子步骤1：利用泰森多边形来确定所有特征对应实例的领域对象。 对于每一类空间特征e_i，将该特征下的实例作为目标图层，创建泰森 多边形图。这样，每一个实例相关的其它特征的实例可表示为：