Search

A co-location pattern is a set of spatial features that are strongly correlated in space. However, some of these patterns could be neglected if the prevalence metrics are based solely on the clique (or star) relationship. Hence, the l -reachability co-location pattern is proposed by introducing the l -reachability clique where the members of each instance pair can be reachable to each other in a given step length l. Because the average size of l -reachability co-location patterns tends to be longer, maximal l -reachability co-location pattern mining is researched in this paper. First, some sparsification strategies are introduced to shorten star neighborhood lists of instances in an updated graph called the l -reachability neighbor relationship graph, and then, they are grouped by their corresponding patterns. Second, candidate maximal l -reachability co-location patterns are iteratively detected in a size-independent way on bi-graphs that contain group keys and their intersection sets. Third, the prevalence of each candidate maximal l -reachability co-location pattern is checked in a binary search way with a natural l -reachability clique called the ⌊ l / 2 ⌋ -reachability neighborhood list. Finally, the effectiveness and efficiency of our model and algorithms are analyzed by extensive comparison experiments on synthetic and real-world spatial data sets. [ABSTRACT FROM AUTHOR]

Spatial co-location pattern mining (SCPM) aims to discover subsets of spatial features frequently located together in proximate areas. Previous studies of SCPM solely concern the inter-features association of a pattern, but neglect the interesting intra-feature behavior. In this paper, we propose the task of spatial co-location pattern mining with coupling relation consideration (SCPM-CR) to capture complex relations embedded in a co-location. Specifically, InterPCI measure is designed to capture the inter-features coupling by considering the comprehensive interaction of objects for the features in a pattern, and luckily it possesses the anti-monotone property. Another measure, IntraCAI, is proposed to capture the congregating behavior of intra-feature objects under the restriction of a co-location. A general framework is designed for SCPM-CR task and experiments show that a large fraction of computation time is devoted to identifying the participating objects of a candidate pattern. To tackle this calculation bottleneck, a novel candidate-and-search algorithm is suggested, CS-HBS, equipped with heuristic backtracking search. Extensive experiments are conducted on real and synthetic datasets to demonstrate the superiority of SCPM-CR compared with traditional SCPM methods, and also to validate the efficiency and scalability of CS-HBS. Experimental results show that CS-HBS outperforms the baselines by several times or even orders of magnitude. [ABSTRACT FROM AUTHOR]

Spatial co-location patterns represent the subsets of spatial features which are frequently located together in a geographic space. Spatial co-location pattern mining has been a research hot in recent years. However, maybe the features in a prevalent co-location pattern further have more interesting relationships such as symbiotic relationships, competitive relationships or causal relationships. This paper mines symbiotic relationships implied in prevalent co-location patterns from dynamic spatial databases. Firstly, after analyzing the existed definition of symbiotic patterns, a criterion of judging strong symbiotic patterns is proposed. Secondly, a novel algorithm to mine strong symbiotic patterns from prevalent co-location patterns is presented, named basic algorithm. Third, for improving the efficiency of the basic algorithm, an improved algorithm which integrates two expensive operations of the basic algorithm into together, and a pruning strategy with two pruning lemmas are presented. The experiments evaluate the effectiveness and efficiency of the proposed algorithms with “real + synthetic” data sets and the results show that strong symbiotic patterns are more concise and actionable compared to traditional prevalent co-location patterns. [ABSTRACT FROM AUTHOR]

Spatial co-location pattern mining is an interesting and important task in spatial data mining which discovers the subsets of spatial features frequently observed together in nearby geographic space. However, the traditional framework of mining prevalent co-location patterns produces numerous redundant co-location patterns, which makes it hard for users to understand or apply. To address this issue, in this paper, we study the problem of reducing redundancy in a collection of prevalent co-location patterns by utilizing the spatial distribution information of co-location instances. We first introduce the concept of semantic distance between a co-location pattern and its super-patterns, and then define redundant co-locations by introducing the concept of δ-covered, where $\delta \,(0\leq \delta \leq 1)$ is a coverage measure. We develop two algorithms RRclosed and RRnull to perform the redundancy reduction for prevalent co-location patterns. The former adopts the post-mining framework that is commonly used by existing redundancy reduction techniques, while the latter employs the mine-and-reduce framework that pushes redundancy reduction into the co-location mining process. Our performance studies on the synthetic and real-world data sets demonstrate that our method effectively reduces the size of the original collection of closed co-location patterns by about 50 percent. Furthermore, the RRnull method runs much faster than the related closed co-location pattern mining algorithm. [ABSTRACT FROM AUTHOR]

• A new cell-based method for mining co-locations on extended objects was presented. • Cell-relation operations replaced instance computing to speed up the calculation. • Neighbor relations were materialized into feature transactions of cells. • The algorithm was compared with the latest algorithm and the classical one. Spatial co-location pattern mining (SCPM) is intended to discover subsets of spatial features whose instances are frequently located together in geographic areas. Traditional SCPM methods are designed for point spatial instances. However, in reality, instances are mostly in the form of extended objects, e.g., lines, polygons. In addition, current SCPM methods with extended objects are less well researched and have two disadvantages: (1) Existing researches cannot effectively capture neighborhood relationships between extended objects and their mining results cannot properly reflect the distribution dependence of features; (2) These methods are not efficient enough with large datasets. This paper proposes a novel framework called cell-relation operations framework to overcome these issues. To eliminate the first shortcoming, the framework uses the area overlapping of buffers between objects to gain the neighbor relationships between extended objects and introduces participation index under buffer size k to identify prevalent co-location patterns. To address the second problem, our framework employs cell-relation operations rather than instance relation computing as the basic computing unit for co-location mining, which substantially speeds up the computation. The framework obtains spatial co-locations by counting the feature transactions of the cells and calculates the feature overlap ratio of the cells to generate co-locations. We implement experiments with real datasets to demonstrate that our framework's mining results are more reasonable and the proposed framework's runtime outperforms the baselines by 2 to 4 orders of magnitude. [ABSTRACT FROM AUTHOR]

A spatial co-location pattern is a group of spatial objects whose instances are frequently located in the same region. The spatial co-location pattern mining problem has been investigated extensively in the past due to its broad range of applications. In this paper we study this problem for fuzzy objects. Fuzzy objects play an important role in many areas, such as the geographical information system and the biomedical image database. In this paper, we propose two new kinds of co-location pattern mining for fuzzy objects, single co-location pattern mining (SCP) and range co-location pattern mining (RCP), to mining co-location patterns at a membership threshold or within a membership range. For efficient SCP mining, we optimize the basic mining algorithm to accelerate the co-location pattern generation. To improve the performance of RCP mining, effective pruning strategies are developed to significantly reduce the search space. The efficiency of our proposed algorithms as well as the optimization techniques are verified with an extensive set of experiments. [ABSTRACT FROM AUTHOR]

A spatial colocation pattern is a group of spatial features whose instances are frequently located together in geographic space. Discovering colocations has many useful applications. For example, colocated plant species discovered from plant distribution data sets can contribute to the analysis of plant geography, phytosociology studies, and plant protection recommendations. In this paper, we study the colocation mining problem in the context of uncertain data, as the data generated from a wide range of data sources are inherently uncertain. One straightforward method to mine the prevalent colocations in a spatially uncertain data set is to simply compute the expected participation index of a candidate and decide if it exceeds a minimum prevalence threshold. Although this definition has been widely adopted, it misses important information about the confidence which can be associated with the participation index of a colocation. We propose another definition, probabilistic prevalent colocations, trying to find all the colocations that are likely to be prevalent in a randomly generated possible world. Finding probabilistic prevalent colocations (PPCs) turn out to be difficult. First, we propose pruning strategies for candidates to reduce the amount of computation of the probabilistic participation index values. Next, we design an improved dynamic programming algorithm for identifying candidates. This algorithm is suitable for parallel computation, and approximate computation. Finally, the effectiveness and efficiency of the methods proposed as well as the pruning strategies and the optimization techniques are verified by extensive experiments with “real $(+)$ synthetic” spatially uncertain data sets. [ABSTRACT FROM AUTHOR]

• A novel maximal prevalent co-location pattern mining framework is presented. • The time and space costs are reduced efficiently by maximal cliques and hash tables. • Enumerating maximal cliques is accelerated by bit string operations. • The performance of the proposed method is proved by comparative experiments. Co-location patterns refer to subsets of Boolean spatial features with instances of these features frequently appear in nearby geographic space. Maximal co-location patterns are a compact representation of these patterns that lead users more easily to absorb results and make meaningful inferences. The current algorithms for maximal co-location pattern mining are based on a generate-test candidate model. The main execution time of this model is occupied by collecting co-location instances of candidates, which makes discovering maximal co-location patterns is still very challenging when data is big and/or dense. To take up the challenge, a novel maximal co-location pattern mining framework based on maximal cliques and hash tables (MCHT) is developed in this study. First, all maximal cliques that can compactly represent neighbor relationships between instances of a spatial data set are enumerated. The advantages of bit string operations are fully utilized to speed up the process of enumerating maximal cliques. Next, a participating instance hash table structure is constructed based on these maximal cliques. Then information about the co-location instances of maximal patterns can be queried and collected efficiently from the hash table. After that, by calculating participation indexes of these patterns to measure their prevalence, maximal prevalent co-location patterns can be filtered efficiently. Finally, a series of experiments is conducted on both synthetic and real-facility data sets to demonstrate that the proposed algorithm can efficiently reduce both the computational time and the memory consumption compared with the existing algorithms. [ABSTRACT FROM AUTHOR]

The potential applications and challenges of uncertain data mining have recently attracted interests from researchers. Most uncertain data mining algorithms consider aleatory (random) uncertainty of data, i.e. these algorithms require that exact probability distributions or confidence values are attached to uncertain data. However, knowledge about uncertainty may be incomplete in the case of epistemic (incomplete) uncertainty of data, i.e. probabilities of uncertain data may be imprecise, coarse, or missing in some applications. The paper focuses on uncertain data which miss probabilities, specially, value-uncertain discrete objects which miss probabilities (for short uncertain objects). On the other hand, classification is one of the most important tasks in data mining. But, to the best of our knowledge, there is no method to learn Naïve Bayesian classifier from uncertain objects. So the paper studies Naïve Bayesian classification of uncertain objects. Firstly, the paper defines interval probabilities of uncertain objects from probabilistic cardinality point of view, and bridges the gap between uncertain objects and the theory of interval probability by proving that interval probabilities are F-probabilities. Secondly, based on the theory of interval probability, the paper defines conditional interval probabilities including the intuitive concept and the canonical concept, and the conditional independence of the intuitive concept. Further, the paper gives a formula to effectively compute the intuitive concept. Thirdly, the paper presents a Naïve Bayesian classifier with interval probability parameters which can handle both uncertain objects and certain objects. Finally, experiments with uncertain objects based on UCI data show satisfactory performances. [ABSTRACT FROM AUTHOR]