基于邻近关系对连接的负co-location模式挖掘方法

摘要

本发明提出了一种邻近连接关系对的负co‑location模式挖掘方法，属于数据挖掘领域。该方法包括：(1)通过一个空间对象集找出其中的邻近连接对；(2)通过k‑1阶频繁负co‑location模式与k‑1阶频繁co‑location模式组合或k‑1阶频繁负co‑location模式和k‑1阶频繁负co‑location模式组合，生成k阶的候选负co‑location模式；(3)根据本发明提出的剪枝方法，快速剪枝，去掉无用的模式，得到频繁负co‑location模式。通过实际数据验证，该方法的算法简单、效率高、计算复杂低。

说明书

技术领域

本发明涉及空间数据挖掘领域，特别是co-location挖掘模式，具体而言，涉及基于邻近关系对连接的负co-location模式挖掘方法。

技术背景

随着科技的迅速发展，各行各业以及各个领域都产生了大量含有有用信息和新颖模式的数据和资料。目前，仅依靠现存的数据库查询技术以及统计学方法难以获取这些有用的信息和新颖模式。在这种情况下，数据挖掘(Data Mining)技术应运而生。

生活中的大部分数据是空间数据。由于空间自相关性，空间数据具有连续性，其类型和关系具有复杂性。由此导致空间数据挖掘存在极大困难。Co-location模式挖掘是空间数据挖掘的一个分支，可以解释地理中的关联现象，为很多应用提供重要信息。

负co-location模式是co-location模式的一个分支。Co-location模式是研究空间数据正相关关系，而负co-location模式是研究空间数据负相关关系。比如，丁香种在铃兰香的旁边，会立即萎篶。丁香的香味也会危机及水仙的生命。将丁香、紫罗兰、郁金香、勿忘我养在一起，彼此都会受害。所以，研究负co-location具有重要实际应用价值。

就负co-location模式而言，Jiang等人提出的负co-location模式挖掘算法，挖掘难度大、效率低，需要先挖掘出所有的co-location模式，然后再进行负co-location模式挖掘。因此，他们的算法难度大、效率低、计算复杂度高。

发明内容

本发明是针对上述算法缺陷，提供了一种基于邻近连接的负 co-location模式挖掘方法，以解决现有的负co-location模式挖掘算法难度大、效率低、计算复杂度高的问题。

为了达到上述目的，本发明提供如下技术方案：

基于邻近连接的负co-location模式挖掘方法，所述方法包括如下步骤：

(1)根据空间特征，计算出其实例的co-location关系和参与度值。

(2)根据参与度值得到邻近关系对。

(3)根据邻近关系对，生成高阶候选负co-location模式。

(4)根据剪枝方法，得到频繁负co-location模式。

优选地，步骤(1)中，根据Y.Huang等人提出的co-location的连接算法，计算出当前空间对象集F＝{f

优选地，步骤(2)中，所述邻近关系对的定义为：C是一个邻近关系对，即是2阶频繁co-location模式或者2阶的频繁负co-location 模式。

优选地，步骤(3)中，所述生成方法为以下两种：

1)一种是频繁正co-location模式与频繁负co-location模式组合，例如，{A,B}和

2)另一种组合方式是两个频繁负co-location模式的组合，例如:

优选地，步骤(3)中，所述组合方法之所以能成立，是因为：

引理1对任意一个负co-location模式

证明：(1)假设

(2)假设

∵

＝1-MaxPR(M′,X)

PI(N,X)＝1-MaxPR(N′,X)∴PR(N,X)≤PR(M,X)

当且仅当MaxPR(M′,X)＝MaxPR(N′,X)时，等号成立

(3)假设

∵

＝1-MaxPR(M′,X)

PI(N,X)＝1-MaxPR(N′,X)∴PR(N,X)≤PR(M,X)

当且仅当MaxPR(M′,X)＝MaxPR(N′,X)时，等号成立优选地，步骤(4)中，所述剪枝方法为如下引理：

引理2.如果

证明：因为

本发明与现有技术相比，具有如下的优点有益效果：

本发明在获得空间对象的空间邻近对后，直接将其进行组合，避免了需要将所有频繁和非频繁co-location模式及其参与度都求出来后才能求出候选负co-location模式。本发明极大减少了计算复杂度，可直接求出候选负co-location模式，并且采用了剪枝策略，可快速求出频繁负co-location模式。

附图说明

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

图1是空间数据集实例

图2是生成邻近关系对和候选负co-location的流程图

图3是2阶co-location模式及其表实例、参与度

图4是候选2阶负co-location模式及其参与度

具体实施方式

下面将结合本发明实施例中的附图，对本发明实例中的技术方案进行清楚、完整的描述。显然，所描述的实例仅仅是本发明的一部分实例，而不是全部的实施例。基于本发明实施例，本领域普通技术人员所获得的所有其他实施例，都属于本发明实施例保护的范围。

为了更清楚地说明本发明专利的方法，下面以图1为空间数据集示例进行演示。

步骤1：首先根据图1和co-location定义，连接符合关系R的空间对象实例，生成2阶候选co-location模式。

{A,B}＝{{A.1,B.2},{A.2,B.1},{A.4,B.3}{A.5,B.1}},

{A,C}＝{{A.1,C.3},{A.2,C.1},{A.3,C.1},{A.4,C.2}},

{A,D}＝{{A.2,D.1}},

{B,C}＝{{B.2,C.3}}

{B,D}＝{{B.4,D.2},{B.3,D.1}}

{C,D}＝{{C.1,D.1}}

步骤2：

计算各个2阶co-location的PI即minPR，与所设阈值比较，选出 2阶频繁co-location模式。本实施例中，设min_prev＝0.6

根据计算公式

PR({A,B},A)＝4/5,PR({A,B},B)＝3/4,即minPR({A,B}) ＝3/4.

PR({A,C},A)＝4/5,PR({A,C},C)＝3/3＝1,即minPR({A,B}) ＝4/5.

PR({A,D},A)＝1/5,PR({A,D},D)＝1/2,即minPR({A,D}) ＝1/5.

PR({B,C},B)＝1/4,PR({B,C},C)＝1/3,即minPR({B,C}) ＝1/4.

PR({B,D},B)＝2/4＝1/2,PR({B,D},D)＝1,即minPR({B,D}) ＝1/2

PR({C,D},C)＝1/3,PR({C,D},D)＝1/2,即minPR({A,B}) ＝1/3.

所述各2阶候选co-location模式的PI值通过与阈值的比较，最终得出，co-location模式{A,B},{A,C}是频繁的。

步骤3：

通过步骤2计算出的非频繁co-location模式可以得出所有的候选 2阶负co-location模式，计算所有的2阶负co-location模式的PI值与所设阈值比较,本实施例设min_negative_prev＝0.6。

所述的2阶候选负co-location模式的PI值与阈值的比较，最终得出

步骤4：

根据所述的计算数据，邻近关系对为

{A,B},{A,C},

根据所述方法，生成3阶候选负co-location模式为：

步骤5:

对所述3阶候选负co-location进行剪枝,判别方法在发明内容中已列出；

因为

因为

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包括这些改动和变型在内。