A detection of multi-level co-location patterns based on column calculation and HDBSCAN clustering

Abstract

A spatial co-location pattern is a subset of a spatial feature set whose instances prevalently appear in nearby locations in space. The objective of spatial co-location pattern mining is to detect co-location patterns that are non-obvious, informative, or predictive. Due to the heterogeneity in the distribution of spatial instances, spatial co-location patterns are classified into global co-location patterns (GCPs) and local co-location patterns (LCPs). The technique that discovers both simultaneously is termed multi-level co-location pattern mining (MLCPM). However, existing MLCPM methods have room for improvement in efficiently identifying GCPs and perform poorly in discovering prevalent sub-areas of LCPs. To address these issues, we propose a novel MLCPM framework called ML-CCHDB. This framework enhances GCP mining efficiency by optimizing the column calculation method tailored for MLCPM. Furthermore, it utilizes the HDBSCAN clustering method to identify potential prevalent sub-areas of LCPs and develops an adaptive approach for generating input parameters to enhance detection efficiency and quality. Experimental results on both synthetic and real datasets demonstrate that the column calculation optimizations in ML-CCHDB effectively enhance efficiency. Moreover, HDBSCAN strikes a balance between efficiency and quality in prevalent sub-area mining. These results fully validate the proposed framework's effectiveness and efficiency.

Keywords

spatial data mining multi-level co-location pattern column calculation HDBSCAN

1 Introduction

In contemporary society, digital transformation is advancing rapidly on a global scale. Accompanying this process, related technologies such as satellite positioning, remote sensing, Geographic Information Systems (GIS), and sensor networks are also developing quickly. These technological advancements have led to the production of massive amounts of spatial data, which exhibits an explosive growth trend. This spatial data not only reflects the prosperity of the modern information society but also presents numerous opportunities and challenges. Consequently, spatial data mining technology has emerged, with the primary objective of extracting valuable knowledge and patterns from vast and complex spatial datasets. Spatial co-location pattern mining (SCPM), a major branch of spatial data mining, aims to discover implicit, instructive or predictive spatial co-location patterns.¹ A spatial co-location pattern (hereafter co-location) is a subset of a spatial feature set whose instances tend to occur nearby.² For instance, the co-location {School, Bookstore, Stationery Shop} indicates that these three often exist together in nearby geographical locations. Research on SCPM enhances our understanding of geographic space structure and provides substantial support for decision-making. It plays a crucial role in fields such as urban planning,³ geosciences,⁴ and public safety.⁵

The main objects of study in SCPM are global co-location patterns (GCPs) and local co-location patterns (LCPs). GCPs are prevalent across entire study areas, whereas LCPs are prevalent only in certain sub-areas. While the technology for mining GCPs has matured, mining LCPs continues to face many challenges. To tackle the challenge of identifying sub-areas that contain LCPs, which are unknown beforehand, researchers have developed multi-level co-location pattern mining (MLCPM) methods that simultaneously extract both GCPs and LCPs. Existing MLCPM methods primarily involve two core steps: first, detecting GCPs; second, considering non-globally prevalent patterns as candidate LCPs and discovering the sub-areas where they are prevalent. Current MLCPM methods typically use traditional co-location mining techniques (such as join-based² and joinless⁶ methods) and the column calculation method¹ to identify GCPs. Traditional methods are row-based, constructing table instances of patterns to calculate the participation index (see Section 3.1) and assess prevalence. In contrast, the column calculation method directly searches for participating instances without generating complete table instances. Although the column calculation method has largely resolved the efficiency issues in mining GCPs, its principal pruning technique based on global prevalence is no longer applicable in MLCPM. This is because non-globally prevalent patterns may be locally prevalent and thus still necessitate the search for participating instances to discover prevalent sub-areas. Therefore, there is still room for optimization in applying the column calculation method in MLCPM. Additionally, existing MLCPM methods either use (a) adaptive clustering,⁷ (b) partitioning by removing extremely long edges,⁸ or (c) simple quadratic iterative method⁹ to identify prevalent sub-areas of LCPs. However, method (a) clusters the centroids of all row instances of patterns, which results in high time costs; method (b) removes edges longer than a fixed percentage, which poorly adapts to different data distributions and leads to suboptimal partitioning; method (c) continuously divides the current region into four until it meets prevalent sub-areas constraints, but this simple strategy overlooks the actual instance distribution, also resulting in suboptimal partitioning.

To address these issues, this study proposes a novel MLCPM method based on adapted column calculation and adaptive HDBSCAN clustering, with the objective of improving the efficiency and quality of mining. The contributions of this study include three aspects:

(1)
We optimize the column calculation method to improve its efficiency in MLCPM, thereby enhancing the mining of GCPs and the acquisition of participating instances of LCPs.
(2)
To address the high time costs and poor results associated with existing methods for identifying prevalent sub-areas of LCPs, we propose using the HDBSCAN clustering method to improve efficiency and quality, along with an adaptive parameter generation method to accommodate different data distributions.
(3)
Experiments on both synthetic and real datasets demonstrate that the improvements in the column calculation method are efficient in comparison to the original, and the use of HDBSCAN strikes a balance between efficiency and quality in the discovery of prevalent sub-areas of LCPs.

2 Related work

2.1 Global co-location pattern mining

The concept of co-locations was first introduced by Shekhar et al.² Concurrently, they proposed a complete Apriori-like framework named join-based for mining co-locations, based on the concept of the participation index. This framework generates table instances of higher-size co-locations by joining row instances of lower-size co-locations, thereby detecting all GCPs. Subsequently, researchers^6,10–13 have actively explored various methods to enhance the mining efficiency of co-locations, including improving the materialization of neighbor relationships and fine-tuning the pruning strategy. In recent years, some scholars have also explored parallel mining methods based on MapReduce¹⁴ and GPUs,¹⁵ aiming to address the efficiency challenges of computing table instances using parallel techniques. All the aforementioned methods compute the participation indexes of co-locations by generating table instances, which in turn assesses the prevalence of co-locations. However, constructing complete table instances is not necessary. Therefore, Yang et al.¹ proposed the heuristic column calculation method that does not construct complete table instances but directly searches for participating instances that can form row instances to compute the participation index of co-locations. Compared to previous methods, the column calculation method greatly improves the mining efficiency of co-locations. The aforementioned methods all adopt the bottom-up mining framework proposed by Shekhar et al., resulting in a significant amount of redundant searching. Therefore, some researchers^16–18 have proposed top-down mining methods based on cliques. These methods initially create maximal spatial cliques based on neighbor relationships between instances and then discover co-locations from these cliques.

2.2 Local co-location pattern mining

Celik et al.¹⁹ proposed partitioning global areas using a quadtree index structure to then mine individual sub-areas for prevalent LCPs. This method can cope with the challenge of dynamic parameters and achieve dynamic mining of LCPs, but it requires complex a priori knowledge to determine the number and size of partitions. Subsequently, Ding²⁰ et al. proposed using a multi-resolution grid-based clustering method for area partition, intended to find interesting sub-areas based on their interest metrics, but similarly faced the problem of requiring complex a priori knowledge. To address these issues, Qian²¹ et al. proposed a hierarchical partitioning method based on the K-Nearest Neighbor Graph (KNNG), treating each KNNG as an independent area for mining LCPs. The method drives the mining process using a distance variation coefficient instead of a neighbor distance threshold, which can automatically determine the k-value for each area. The division of global areas by these methods can be considered a ‘hard division’, where each sub-area has a clear demarcation line. However, real-life applications often require a more flexible ‘soft division’, where a spatial instance can belong to multiple sub-areas, thus fuzzing the dividing lines between these sub-areas. Consequently, Jiang²² et al. proposed using a density peak clustering method based on fuzzy set theory to divide sub-areas, rendering the division more reasonable.

2.3 Multi-level co-location pattern mining

Deng et al.⁷ proposed an MLCPM method named ML. Initially, the method employs the join-based approach to discover GCPs and then considers globally non-prevalent patterns as candidate LCPs. Subsequently, it utilizes an adaptive spatial clustering method to mine LCPs and their prevalent sub-areas, and its main process is summarized as follows: First, for a candidate LCP, Delaunay triangulation is conducted by taking the centroids of all its row instances as vertices; Second, global and local long edges are removed from the Delaunay triangulation to obtain a set of connected subgraphs; Third, the prevalence of the candidate LCP within the sub-areas enclosed by the convex hulls of the subgraphs’ vertices is assessed. If it is prevalent, the sub-area is identified as a prevalent sub-area of the candidate LCP. Building on Deng's research, Liu et al.⁸ proposed a natural neighborhoods-based MLCPM method named ML-Miner. The method first defines natural neighborhoods based on the formation mechanism of co-locations and the local distribution of spatial features, and then adaptively builds neighbor relationships for instances between different features. Subsequently, GCPs are mined using the joinless method, and globally non-prevalent patterns are used as candidate LCPs. The ML-Miner method adopts the framework of the ML method to discover prevalent sub-areas of candidate LCPs, but its main differences are as follows: (1) In the first step, the ML-Miner method constructs the Delaunay triangulation using all participating instances of a candidate LCP as vertices; (2) In the second step, the ML-Miner method removes excessively long edges, specifically those longer than the 90th percentile, from the triangulation based on a percentile estimation formula developed for skewed distributions; (3) In the third step, if the candidate LCP is not prevalent in this sub-area, the ML-Miner uses a multi-directional optimization method based on the Voronoi diagram to discover prevalent sub-areas of the candidate LCP. The two methods all use the participation index to measure the prevalence of co-locations. However, the participation index only reflects the located degree of co-locations and cannot indicate the spatial distribution of co-locations. For example, a co-location identified as a GCP based on the participation index may have its instances distributed only within certain sub-areas. Therefore, Li et al.⁹ proposed a new MLCPM method, called MLCPM-SDF, which uses a relative distribution coefficient to determine the spatial distribution of co-locations, thus providing a more refined approach to mining GCPs and LCPs. The method first mines GCPs using the column calculation method, and then, uses a quadratic iterative approach to gradually divide the current area until prevalent sub-areas of eligible LCPs are found.

3 Related concepts and methods

This section introduces concepts and principles related to spatial co-location pattern mining and those of the methods related to the MLCPM framework designed for this research.

3.1 Spatial co-location pattern

In the domain of SCPM, a spatial feature f_i represents the type of different spatial objects within a spatial environment. For a specific spatial feature, its spatial instances refer to the spatial objects possessing that feature type, uniquely identified by the tuple <instance id, feature type, location>. The set of all spatial features is denoted as F = {f₁, f₂, …, f_n}. The set of all spatial instances is denoted as I = {i₁, i₂, …, i_m}. Two instances are considered to have a neighbor relationship if the distance between them is not greater than a given neighbor distance threshold d, denoted as R(i_x, i_y) ⇔ distance(i_x, i_y) ≤ d, where distance(i_x, i_y) represents the distance between instances i_x and i_y. In this study, we use the Euclidean distance formula to calculate the distance between instances. A spatial co-location pattern C = {f₁, f₂, …, f_k} (where k ≥ 2) is a subset of the spatial feature set whose instances prevalently appear in neighboring locations in space. The number of features contained in co-location C is called the size of C. The instance set RI = {i₁, i₂, …, i_k} represents a row instance of co-location C that satisfies two conditions: (1) the number of instances in RI is equal to the size of C, and RI contains all features in C; (2) any two instances within RI have the neighbor relationship. For example, the three instances connected by yellow triangles in Figure 1 constitute a row instance of a three-size co-location. The set of row instances of co-location C is called the table instance of C, denoted TIns(C). In a table instance, an instance with feature f_i is called a participating instance of f_i, and the corresponding set of participating instances is denoted as PIns(C, f_i) = {i_x | i_x ∈ TIns(C) $⋀$ i_x.feature = f_i}.

To measure the prevalence of co-locations in a global area, Shekhar et al.² proposed the concepts of participation ratio (PR) and participation index (PI). The participation ratio of a feature f_i in a k-size co-location C is defined as the ratio of the number of participating instances of f_i to the total number of instances of f_i, expressed as:

P R (C, f_{i}) = \frac{| P I n s (C, f_{i}) |}{| I_{i} |}

(1)

where I_i denotes the set of instances of f_i, and |·| denotes the count of elements in a set. Then, the participation index of C is defined as the minimum participation ratio of features in C, expressed as:

P I (C) = {min}_{i = 1}^{k} {P R (C, f_{i})}

(2)

Given a prevalence threshold min_prev, if PI(C) ≥ min_prev, then C is considered a prevalent co-location. Since the prevalence of C is measured globally, it is referred to as a GCP. For instance, in Figure 1, the PI({A, B, C}) = min{1,3/7,2/5} = 2/5. If min_prev = 0.3, then the pattern {A, B, C} is a GCP.

Figure 1.

A toy example of spatial datasets, where A.1 denotes an instance of feature A with id 1.

A co-location that may not appear prevalent in the global area could still be prevalent within specific sub-areas, due to the heterogeneity of spatial data distribution. Thus, an LCP is defined as LCP = (C, sub-area), where sub-area is a subset of the spatial instance set, indicating a prevalent sub-area of co-location C. To measure the prevalence of LCP in sub-areas, analogous to the participation ratio and the participation index, Mohan et al.⁵ proposed the concepts of local participation ratio (LPR) and local participation index (LPI). The local participation ratio of a feature f_i in a k-size co-location C is defined as the ratio of the number of participating instances of f_i to the total number of instances of f_i in a certain sub-area sub-area_s, expressed as:

L P R ((C, s u b - a r e a_{s}), f_{i}) = \frac{| L P I n s ((C, s u b - a r e a_{s}), f_{i}) |}{| # instances of f_{i} in s u b - a r e a_{s} |}

(3)

where

L P I n s ((C, s u b - a r e a_{s}), f_{i})

represents the set of participating instances of f_i in sub-area_s of C. Then, the local participation index of C is defined as the minimum value of the local participation ratio of features in C, expressed as:

L P I ((C, s u b - a r e a_{s})) = {min}_{i = 1}^{k} {L P R ((C, s u b - a r e a_{s}), f_{i})}

(4)

Given a co-location C in a sub-area sub-area_s, if LPI((C, sub-area_s)) ≥ min_prev, then C is considered a prevalent LCP in sub-area_s. For instance, in Figure 1, the PI({B,C,D}) = min{3/7, 3/10, 2/7} = 2/7; if min_prev = 0.3, then the pattern {B,C,D} is not prevalent in the global area, but the LPI(({B,C,D}, sub-area_BCD)) = min{1, 1, 2/3} = 2/3 ≥ min_prev, making pattern {B,C,D} a prevalent LCP in sub-area_BCD.

Lemma 1.

(1) If a k-size co-location is locally prevalent in at least one sub-area, then all its (k − 1)-size sub-patterns are also locally prevalent in at least one sub-area. (2) Conversely, if a k-size co-location is not locally prevalent in any sub-area, then all its (k + 1)-size super-patterns are not locally prevalent in any sub-area either.

Proof.

(1) Assume an LCP LCP_x = (C_j = {f₁, …, f_k}, sub-area_m), with LPI(LCP _x , sub-area_m) = ${min}_{i = 1}^{k} {L P R ((C_{j}, s u b - a r e a_{m}), f_{i})}$ ≥ min_prev, then for a co-location C′ = {f₁, …, f_k₋₁} ⊂ C_j in sub-area_m, there is LPI((C′, sub-area_m)) = ${min}_{i = 1}^{k - 1} {L P R ((C^{'}, s u b - a r e a_{m}), f_{i})}$ ≥min_prev, which leads to LCP_y = (C′, sub-area_m) being prevalent in sub-area_m. (2) For a co-location C_i = {f₁, …, f_k}, as long as the set of participating instances of C_i, PIns(C_i) ≠ ∅︀, there must exist a sub-area sub-area_m containing only PIns(C_i) such that LPI((C_i, sub-area_m)) = 1, i.e., C_i is locally prevalent in sub-area_m. In other words, if C_i is not prevalent in any sub-area, then there is PIns (C_i) = ∅︀. Then, for a co-location C^″ = {f₁, …, f_k₊₁} ⊃ C_i, if PIns(C_i) = ∅︀, then PIns(C^″) ⊂ PIns(C_i) = ∅︀ (see Lemma 2), i.e., C^″ is not locally prevalent in any sub-area.

Generation and pruning strategies for candidate co-locations. (1) Candidate GCPs: A (k + 1)-size candidate GCP is generated by joining two k-size prevalent GCPs that share the first k − 1 items, using the anti-monotonicity of the participation index.² If any k-size sub-pattern of the candidate is not globally prevalent, the candidate is pruned. (2) Candidate LCPs: By considering GCPs as a special case of LCP with the global area as the prevalent sub-area, and based on Lemma 1(2), a (k + 1)-size candidate LCP is formed by joining two k-size LCPs (including GCPs) with the same first (k − 1) items. In accordance with Lemma 1(1), if any k-size sub-pattern of the candidate is not globally or locally prevalent, it is pruned.

3.2 Column calculation method

This study adapts the column calculation method from reference 1 to obtain participating instances of GCPs and LCPs. This section introduces the basic concepts of the method and the optimization strategies we have designed.

3.2.1 Basic concepts

The neighbor set of instance i_x is defined as the collection of all instances that have the neighbor relationship with i_x, denoted as Neigh(i_x) = {i_y | i_y ∈ I, R(i_x, i_y)}. Further, by grouping the instances in Neigh(i_x) according to feature f_i, we can obtain the grouped neighbor set of i_x under feature f_i, denoted as groupN(i_x, f_i) = {i_y | i_y ∈ I, i_y ∈ Neigh(i_x), i_y.feature = f_i}. For instance, as illustrated in Figure 1, the grouped neighbor set of instance B.2 under feature C can be represented as groupN(B.2, C) = {C.1, C.2, C.4}.

Lemma 2.
For a k-size (k > 2) co-location C, and its (k + 1)-size super-pattern C′, with C⊂C′, if f_i is in both C and C′, then PIns(C′, f_i) is a subset of PIns(C, f_i).

The proof of Lemma 2 can be found in reference 1.¹ According to Lemma 2, the participating instances of a co-location C must be included in the participating instance sets of its sub-patterns. Therefore, the possible participating instances of feature f_i in a k-size co-location C, i.e., the candidate participating instance set of f_i, is the intersection of the participating instance sets of f_i in all (k − 1)-size sub-patterns of C that contain f_i, defined as:
$C P I n s (C, f_{i}) = ⋂_{S C \in C_{k - 1}^{f_{i}}} P I n s (S C, f_{i})$
(5)
Here, $C_{k - 1}^{f_{i}}$ denotes the set of all (k − 1)-size sub-patterns of C that include f_i. For an instance i_x of feature f_i in C, the set of instances of other features f_j (i ≠ j) that may form a row instance of C with i_x is called the instance search space of i_x on feature f_j within C, denoted as Iss(i_x, f_j, C), where
$I S S (i_{x}, f_{j}, C) = {\begin{array}{l} g r o u p N (i_{x}, f_{j}) \cap P I n s (C, f_{j}), P I n s (C, f_{j}) know \\ g r o u p N (i_{x}, f_{j}) \cap C P I n s (C, f_{j}), P I n s (C, f_{j}) unknow \end{array}$
(6)
The instance search space refers to the scope of the search for a candidate participating instance. For an instance i_x in the candidate participating instance set, verifying whether i_x can form a row instance with instances in the search space of different features in C allows for the determination of whether i_x is a participating instance. Meanwhile, instances of other features within the row instance are also validated. During the validation process, once a valid row instance is found using backtracking, the verification can be halted. This discovered instance is called a search row instance, with all search row instances of C denoted as SRIs(C) ⊆ TIns(C).
3.2.2 Optimization strategies

Pre-generation strategy for two-size candidate co-location patterns and their participating instance sets. In the column calculation method, the participating instance sets of co-location patterns are generated level-wise. When size k > 2, the participating instance sets are calculated by verifying candidate participating instances of the pattern. However, for two-size co-location patterns (i.e., k = 2), the column calculation method obtains the participating instance sets by traversing the neighbor relationships between instances of two features. The typical sequence of this process is as follows: first, calculation of neighbor relationships; second, generation of two-size candidate co-location patterns; and third, obtaining the participating instance sets of the co-location patterns. However, when calculating the neighbor relationships between instances, if it is found that instances i_x and i_y (i_x.feature ≠ i_y.feature) are neighboring, we can directly conclude that i_x and i_y are participating instances of the co-location pattern {i_x.feature, i_y.feature}. Thus, we synchronize the generation of two-size candidate co-location patterns with the construction of their participating instance sets during the neighbor relationship calculation process, thereby reducing the time required for their separate construction.

Grouped neighbor set storage optimization strategy. The grouped neighbor set is a crucial data structure involved in constructing the search space for each candidate participating instance. Therefore, we designed a three-layer nested hash structure (as shown in Figure 2) to store the grouped neighbor sets of instances. This design enables the algorithm to access groupN(i_x, f_j) with a time complexity of O(1) when verifying candidate participating instances, thereby reducing the obtaining time of ISS(i_x, f_j, C).

Figure 2.

Hash structure for groupN. The figure shows part of the groupN for instances B.2 in Figure 1, including groupN(B.2, A) = {A.3, A.4, A.5}, groupN(B.2, C) = {C.1, C.2, C.4}.

Feature search strategy. The original column calculation method is an efficient approach for mining global co-location patterns. During the verification of candidate participating instances, the method sorts features in ascending order based on the upper bound of feature participation rates(i.e., |CPIns(C, f_i)| / |I_i|, which is greater than or equal to |PIns(C, f_i)| / |I_i|) and verifies the participating instances of features in sequence to prune patterns that do not meet the prevalence threshold in advance. However, when applying column calculation to MLCPM, patterns that do not meet the threshold may still be LCPs and thus still require obtaining their participating instances. Therefore, we designed a feature search strategy suitable for MLCPM: the more candidate participating instances a feature has, the more participating instances it may have. Based on this consideration, we sort the features in the candidate co-location pattern in descending order according to their number of candidate participating instances and search for their participating instances in sequence. Through this design, when verifying the participating instances of the features at the top of the list, we can simultaneously identify as many participating instances of other features as possible, thereby improving overall efficiency.

3.3 HDBSCAN clustering

Prevalent sub-areas of LCPs are densely populated areas of instances, which can vary in density. Additionally, the distribution of co-location pattern instances is often irregular; for example, some patterns may be distributed along mountains, rivers, and lakes. Based on these characteristics, we adopted the HDBSCAN²³ technique to mine prevalent sub-areas of LCPs. HDBSCAN combines the advantages of hierarchical clustering and DBSCAN, generating clustering results without the need for manually selecting the neighbor radius (eps) and minimum number of points (min_pts), and identifying sub-areas with varying densities and irregularities. The basic steps of HDBSCAN include:

(1)
Density space transformation: Convert the input dataset into a density space by calculating the local density of each object to better identify dense regions.
(2)
Minimum spanning tree construction: Build a minimum spanning tree on the distance-weighted graph to connect all objects and minimize total edge weight, revealing potential clustering structures.
(3)
Cluster hierarchy construction: Gradually build a cluster hierarchy using the minimum spanning tree, allowing observation of clustering characteristics at different density levels.
(4)
Hierarchy compression: Compress the hierarchy based on a preset minimum cluster size to remove unstable small clusters and retain statistically significant clusters.
(5)
Extraction of stable clusters: Extract stable clusters from the compressed hierarchy that remain consistent across different density levels, representing the true structure and patterns in the data.
In the HDBSCAN model, only the key parameter—minimum cluster size (min_cluster_size)—is required to obtain the final clustering result. Therefore, this study designed an adaptive method to generate min_cluster_size for applying HDBSCAN to prevalent sub-area mining of LCPs. For a k-size co-location pattern C = {f₁, f₂, …, f_k}, it is expressed as follows:
$m i n_c l u s t e r_s i z e = max {| X | \times 0.05, 2 \times k}$
(7)
where X is the set of centroids of row instances in SRIs(C), and SRIs(C) covers all participating instances of pattern C. Clustering these centroids effectively reduces the number of clustering objects and ensures that participating instances of the same row instance belong to the same cluster, maintaining neighbor relationships between instances. In the best case, $| S R I s (C) | = {max}_{i = 1}^{k} {| P I n s (C, f_{i}) |}$ , meaning after verifying the feature with the most participating instances, the participating instances of other features are also verified. In the worst case, $| S R I s (C) | = | T I n s (C) |$ , meaning that all row instances must be searched to obtain all participating instances. Therefore, this method is more efficient than existing methods that cluster all row instance centroids to mine prevalent sub-areas.

Overall, we expect the minimum number of objects in a cluster to be the maximum of 5% of |SRIs(C)| and twice the size of the co-location pattern, meaning that a prevalent sub-area in a k-size co-location pattern should contain at least 2 × k row instances.
4 ML-CCHDB framework for mining multi-level co-location patterns

4.1 ML-CCHDB

Based on the basic concepts and principles of column calculation and HDBSCAN clustering methods, this study presents an MLCPM framework called ML-CCHDB (Multi-level Co-location Pattern Mining based on Column Calculation and HDBSCAN Clustering) (see Algorithm 1), which is designed to mine GCPs and LCPs simultaneously, and the mining process can be summarized as follows:

(1)
Inputting spatial dataset and parameters: including a spatial feature set F, a spatial instance set I, a neighbor distance threshold d, and a prevalence threshold min_prev.
(2)
Acquiring neighbor relationships (step 1): A grid plane scanning method²⁴ is used to identify neighbor relationships based on the neighbor distance threshold. The basic steps of the method are: (1) Divide the geographical space into grids of size d × d. (2) Traverse the instances in each grid and calculate the distance to other instances in the same grid and the adjacent top, top-right, right and bottom-right grids to determine neighbor relationships. This method avoids calculating the distance between each pair of instances, thus significantly reducing the time complexity to much less than O(|I|²). Then the grouped neighbor sets under different features of all instances are constructed and stored in the three-layer nested hash structure for further processing. Additionally, during this process, the two-size candidate co-location pattern C₂, its participating instance set C₂_PIns, and its search row instance set SRIs₂ are generated simultaneously.
(3)
Mining co-locations level-wise (steps 2–24): Initially, each spatial feature is treated as a one-size prevalent co-location, and k is set to two, marking the start of the iterative process to mine GCPs and LCPs (step 2). Subsequently, according to the candidate co-locations generation and pruning strategies, (k + 1)-size candidate co-locations are generated from the k-size prevalent co-locations (step 6, if k > 2). The column calculation method (see Algorithm 2) is then employed to obtain the participating instance sets and search row instances sets of these candidate co-locations (step 11, if k > 2). Following this, the participation indexes of the candidate co-locations are computed based on their participating instances (step 15). For each candidate co-location, if its participation index is not less than min_prev, the candidate co-location is marked as a GCP (steps 16–18). Otherwise, the IdentifyPrevalentSubareas(C, k, d, min_prev, SRIs(C)) process (see Algorithm 3) is applied to identify its prevalent sub-areas (steps 19–23). After mining all k-size co-locations, the value of k is incremented to proceed to the next iteration (step 24).
(4)
Outputting results (step 25): After completing the iterations, the ML-CCHDB framework outputs all mined GCPs and LCPs, along with the prevalent sub-areas of these LCPs.

In the GenerateParticipatingInstances(C, groupN) process (Algorithm 2), step 1 initializes the search row instance set SRIs(C) for pattern C as an empty set. Step 2–3 constructs the candidate participating instance set for each feature in C using Equation 5. Then, step 4 sorts the features in C in descending order based on the number of candidate participating instances and searches for participating instances of each feature in this order. Step 6 constructs the search space for candidate participating instance i_x using Equation 6. Step 8 employs a backtracking method to quickly search for row instances containing i_x. If such a row instance exists, i_x and other instances within that row instance are marked as participating instances, and the row instance is added to SRIs(C). The detailed steps of the backtracking search are available in reference 1.¹

In the IdentifyPrevalentSubareas(C, k, d, min_prev, SRIs(C)) process (Algorithm 3), step 2 first calculates the centroids of each row instance in the search row instance set SRIs(C) of pattern C, forming a set of centroids centroids to be used for subsequent clustering. Step 3 then uses Equation 7 to calculate the clustering parameter, the minimum cluster size min_cluster_size. Next, step 4 applies the HDBSCAN technique to cluster the centroids. After clustering, for each cluster, step 6 restores the centroids to the participating instances contained in the row instances they represent, forming a cluster of participating instances, ins_cluster. After that, steps 7–9 first construct the convex hull of ins_cluster and then examine the prevalence of C within the sub-area enclosed by this convex hull. If C is prevalent in this sub-area, the sub-area is marked as a prevalent sub-area of C.

4.2 Algorithm analysis

Time complexity. In the ML-CCHDB framework, the time complexity of step 1 to obtain the neighbor relationships is much less than O(|I|²). During the iterations of steps 3–24, the k-th iteration requires traversing each candidate co-location C in C_k, with a time complexity of O(|C_k|). For each C in C_k (k > 2), step 11 applies the column calculation method to obtain the participating instance set of C. For a k-size pattern C, the time complexity for sorting its features is O(k × logk). The time complexity of traversing the candidate participating instance set of each feature f_i is O(k × n₁), where n₁ denotes the average length of the candidate participating instance set for each feature. The column calculation method employs a backtracking approach to identify participating instances that form row instances with f_i. In the worst case, it requires searching all combinations of instances with different features, with a time complexity of O(n₂ ^k ^–1), where n₂ represents the average length of ISS(i_x, f_j, C). However, the backtracking search can stop upon finding a single row instance, thus the actual search length is much less than O(n₂ ^k ^–1). Consequently, the time complexity for searching the participating instances of C is O(k × (logk + n₁ × n₂ ^k ^–1)). Step 20, which mines LCPs and their prevalent sub-areas, is the most time-consuming. When step 20 calls Algorithm 2, the centroids of search row instances are first calculated, with a time complexity of O(|SRIs(C)|). Step 4 clusters the centroids using HDBSCAN, with a time complexity of O(|SRIs(C)| ²). In the worst case, |SRIs(C)| = |TIns(C)|, but in practice it is much smaller than |TIns(C)|. If the centroids are clustered into a clusters, each cluster must be traversed to restore the centroids into participating instances, forming the instance cluster ins_cluster, with a time complexity of O(|SRIs(C)|). Then the prevalence of pattern C within the convex hull of ins_cluster is examined, with a time complexity of O(n₄ × logn₄ + n₄), where n₄ is the average length of ins_cluster, n₄ × logn₄ is the time to construct the convex hull. Therefore, the time complexity for mining LCPs and their prevalent sub-areas is O(2×|SRIs(C)| + |SRIs(C)|² + a × (n₄ × logn₄ + n₄)).

Space complexity. The space complexity consumed by storing the three-layer nested hash table of groupN is O(|F| + |I| + (|I| × n₅) + (|I| × n₅× n₆)), where n₅ denotes the average of the number of features neighboring the second layer of instances, and n₆ denotes the average of the number of instances neighboring the second layer instances under each feature. The column calculation method constructs the candidate set of participating instances of C_k based on the set of participating instances of P_k−1, so the additional storage of the set of participating instances of P_k−₁ consumes a space complexity of O(|P_k₋₁| × k × n₇), where n₇ denotes the average length of the set of participating instances of PIns(C, f_i). The space complexity consumed by storing the search row instance sets is O(|C_k| × n₇), where n₇ denotes the average size of the search row instance sets for each candidate pattern. The space complexity consumed by storing prevalent sub-areas of LCPs is O(n₈ × n₉ × n₁₀), where n₈ denotes the total number of LCPs, n₉ denotes the average value of the number of prevalent sub-areas of the LCPs, and n₁₀ denotes the average value of the number of instances contained in the prevalent sub-areas.

Completeness and correctness. The ML-CCHDB method level-wise mines all GCPs and LCPs from lower to higher sizes, with the generation and pruning strategies for candidate co-locations ensuring the completeness of the generated candidate co-locations. Moreover, HDBSCAN clusters the centroids of the search row instances for each candidate pattern, ensuring that all clusters of candidate pattern instances are identified. It also guarantees that participating instances from the same row instance are grouped into the same cluster, preventing the division of neighbor relationships. This ensures completeness in mining prevalent sub-areas of LCPs. Concurrently, the clear definition of LCPs and the setting of prevalence thresholds ensure that LCPs are indeed prevalent within their prevalent sub-areas, thereby ensuring the correctness of the ML-CCHDB method.

5 Experimental evaluation

5.1 Experimental design

Application to real datasets. Two real datasets are used for experimental validation:

(1)
The vegetation distribution dataset from the Gaoligong Mountain (GM). It comprises 10 different vegetation features and 9636 spatial instances.
(2)
The vegetation distribution dataset from the Three Parallel Rivers Protected Area (TPR). It comprises 14 different vegetation features and 3902 spatial instances.
The distribution of the real datasets is shown in Figure 3. Each point represents an instance and different colors indicate different features.

Figure 3.
Distribution of the real datasets: (a) GM; (b) TPR.

Generation of synthetic datasets. To further analyse the performance of MLCPM methods, a synthetic dataset containing both GCPs and LCPs is required. Therefore, following the method described in reference 8, a synthetic data generator was designed with the following implementation steps: (1)
Divide a study area of size L × L into four equal sub-areas of size L/2 × L/2. Three of these sub-areas are used for generating data points, serving as data domains, while the remaining one is used for generating noise points, referred to as the noise domain. A parent point is generated at the center of each data domain (see Figure 4(a)).
(2)
Around each parent point, within a buffer zone with the parent point as the center and r_parent as the radius, n_child child points uniformly distributed around the parent point are generated, and then all parent points are deleted (see Figure 4(b)).
(3)
Around each child point, within a buffer zone with the child point as the center and r_child as the radius, n_grandchild grandchild points of different feature types are generated, and then all child points are deleted (see Figure 4(c)).
(4)
Within the noise domain, n_noise noise points of a given feature are randomly generated (see Figure 4(c)).

Figure 4.
Synthetic dataset generator: (a) Generate parent points; (b) Generate child points; (c) Generate descendant points and noise.

Each grandchild or noise point represents a spatial instance, and each buffer zone for the parent point represents a sub-area containing LCPs. When generating synthetic data, parameters can be adjusted to generate different synthetic datasets. Here, r_child controls the distance between instances of different features, r_parent and r_child together control the spatial distribution density of the instances, n_grandchild controls the number of features, and n_nosie controls the prevalence of co-locations.

Comparison algorithms. In the experiments, the proposed methods are compared with existing classical MLCPM methods, including the ML⁷ method, the ML-Miner⁸ method, and the MLCPM-SDF⁹ method presented in Section 2.3.

Evaluation metrics. This study adopts the evaluation method proposed in reference 25, which evaluates the quality of the mined LCPs by precision and recall, defined as:
$\begin{aligned} P r e c i s i o n & = \frac{| T P |}{| T P | + | F P |} \end{aligned}$
(8)

$\begin{aligned} R e c a l l & = \frac{| T P |}{| T P | + | F N |} \end{aligned}$
(9)
where, if the preset prevalent sub-area is represented as TPA, and the prevalent sub-area detected by a MLCPM method is represented as DPA, then TP = TPA ∩ DPA, FP = DPA − TPA, FN = TPA − DPA.

Experimental environment. All methods were implemented in Python. The hardware environment consisted of an Intel Core i7–8700K CPU @ 3.70GHz with 64GB of memory.
5.2 Influence of the number of spatial features

In this section, synthetic datasets are used to evaluate the impact of the number of spatial features on the performance of MLCPM methods. In the synthetic dataset generator, the number of spatial features corresponds to the value of n_grandchilid. To ensure consistency in the total number of instances I_num (excluding noise) and the density of the instance distribution ρ across different datasets, parameters were set as follows: L = 1200, r_chilid = 25, n_grandchild ∈ [3, 8], n_child = I_num / n_grandchild, r_parent = (n_child × n_grandchild) / (ρ × π), where π denotes the circumference. Regarding method parameter settings, for ML-CCHDB, MLCPM-SDF and ML methods, the neighbor distance threshold d was set to 2 × r_chilid to ensure that the methods consider a reasonable distance range when obtaining neighbor relationships. The prevalence threshold min_prev was set to 0.3 for the four MLCPM methods to ensure that the detected co-locations possess a certain level of universality and representativeness. The minimum relative distribution coefficient threshold min_rdc in MLCPM-SDF was set to 0.5, and the minimum edge length of the prevalent sub-area min_Reg was set to $\sqrt{2} \times d$ . In addition, to include both GCPs and LCPs in the synthetic data, n_noise was set to int[ n_child × 3 / min_prev − n_child × 3 ] + 1, where int[·] denotes taking the integer part of a floating point number. This setting allows the participation indexes of co-locations with noise features not to exceed min_prev, thereby considering such patterns as candidate LCPs. Finally, during the experimental process, I_num was set to 850 and ρ to 0.0015. The results of the experiments are shown in Figures 5 and 6. To represent the running time of the MLCPM methods, given the significant differences in their execution times, the vertical axis in the figure uses a logarithmic scale with base 10.

Figure 5.

Influence of the number of spatial features on the runtime of MLCPM methods.

Figure 5 presents a runtime comparison of the four MLCPM methods on synthetic datasets with varying numbers of features. The figure clearly illustrates that as the number of features increases, the execution time for both the ML-CCHDB, MLCPM-SDF and ML-Miner methods exhibits a marked upward trend. This phenomenon can be attributed to the increased number of candidate co-locations resulting from the higher number of features, which significantly escalates the computational time required to verify the prevalence of these patterns and mine LCPs. However, the runtime of the ML method does not exhibit this trend, which might be because, under the premise of a constant total number of instances, the increase in the number of features, while leading to an increase in the number of candidate co-locations, results in a corresponding decrease in the number of instances per pattern. This reduction in the number of instances decreases the time required for clustering operations to identify prevalent sub-areas of LCPs. Therefore, the figure reflects that the time taken by the ML method to mine GCPs increases with the number of features, but the time to mine LCPs decreases with the increase in the number of features. These opposing factors result in no significant overall trend in the time consumption of the ML method. Furthermore, when comparing the time taken by the four MLCPM methods to mine GCPs, it can be observed that the column calculation method used by the ML-CCHDB and MLCPM-SDF methods takes less than one second in most cases and is minimally affected by the increase in the number of features. Given the limited scale of the data, the efficiency advantage of our adapted column calculation method over the original method used by MLCPM-SDF is not yet apparent. However, compared to the traditional methods used by ML-Miner and ML, the column calculation method is still several times, or even orders of magnitude, more efficient. Moreover, although the ML-CCHDB method is not as fast as MLCPM-SDF in mining LCP, it still takes significantly less time than the other two methods. These results indicate that the ML-CCHDB method has a relative advantage in terms of efficiency.

Figure 6 presents the number, precision and recall of the prevalent sub-areas of the highest size (k = n_grandchild) LCPs mined by the four MLCPM methods when dealing with datasets of different numbers of spatial features. Among these evaluation metrics, the ML-CCHDB method exhibits higher precision and recall, indicating its ability to comprehensively and correctly detect LCPs. In contrast, the ML-Miner and ML methods exhibit lower precision because they cannot effectively separate the prevalent sub-areas of LCPs in the three closely related data domains. This shortcoming is due to the ML-Miner method's approach of using a fixed percentage (90%) to remove overly long edges to identify prevalent sub-areas. However, this fixed percentage setting does not perfectly adapt to data sets with different distributions, and thus neglects some long edges that should be removed. Similarly, the ML method's strategy of removing both global and local long edges to discover prevalent sub-areas also suffers from problems of omitting long edges. The HDBSCAN clustering method used in this study effectively distinguishes closely spaced clusters without requiring additional parameters from the user, resulting in better identification of prevalent sub-areas. Furthermore, while the MLCPM method demonstrates satisfactory precision, its recall is comparatively lower. Considering the number of prevalent sub-areas, this is attributable to the MLCPM-SDF method's use of a quadtree iterative approach to mine prevalent areas of LCPs. If a pattern does not meet the prevalent sub-area constraint in the current area, the area is divided into four and mining continues. However, this simple quadratic strategy overlooks the actual data distribution, leading to areas being reduced exponentially without reaching an appropriate scale.

Figure 6.

Evaluation of MLCPM methods with varying numbers of spatial features: (a) The number of prevalent sub-areas; (b) Precision; (c) Recall.

Figure 7.

Influence of spatial instance distribution density on the runtime of MLCPM methods.

5.3 Influence of the density of distribution of spatial instances

In this section, synthetic datasets are utilized to evaluate the impact of spatial instance distribution density on the performance of MLCPM methods. During the synthetic dataset generation process, we adjusted the parameters r_parent and r_child to create datasets with varying instance distribution densities. Specifically, within each data domain, the value of r_parent was randomly selected from the range [50, 80], and the value of r_child from [10, 20], in order to produce sub-areas with varying densities. Six datasets were ultimately generated and ranked according to their average density. To ensure consistency in the number of features and the total number of instances across different datasets, we set L = 300 and let n_grandchild = F_num, n_child = I_num / 3. In the experiments, F_num was set to 5, I_num to 180. Finally, we set d = 40, min_prev = 0.3, min_rdc = 0.5, min_Reg = $\sqrt{2} \times d$ . The experimental results are shown in Figures 7, 8 and Table 1.

Figure 8.

Evaluation of MLCPM methods with varying instance distribution densities: (a) The number of prevalent sub-areas; (b) Precision; (c) Recall.

Table 1.

Comparison of the number of participating instances, search row instances, and row instances produced by MLCPM methods.

	Density
Type	1	2	3	4	5	6
Participating instances (Generated by ML-CCHDB)	1830	2640	2642	2640	2640	2641
Search ow instances (Generated by ML-CCHDB)	1181	1786	1877	1833	1918	1955
Row instances (Generated by ML)	54,152	132,806	164,345	237,680	321,355	342,644

Figure 7 illustrates the runtime of four methods on synthetic datasets with varying instance distribution densities. Table 1 enumerates the number of participating instances, search row instances, and row instances generated during the execution of the ML-CCHDB and ML algorithms. From Figure 7, it is evident that as the instance distribution density increases, the runtime of the ML-CCHDB, MLCPM-SDF, and ML-Miner methods remains relatively stable, whereas the runtime of the ML algorithm increases significantly. This is because the ML-CCHDB, MLCPM-SDF, and ML-Miner methods cluster or partition the participating instances or search row instance centroids to mine prevalent sub-area of LCPs, while the ML algorithm clusters centroids of all row instances to identify prevalent sub-area. As demonstrated in Table 1, the number of participating instances and search row instances remains relatively constant with increased density, but the number of row instances grows substantially, making the ML method more sensitive to changes in density. Additionally, the number of search row instances is generally less than the number of participating instances, indicating that clustering search row instance centroids effectively reduces the number of clustering objects. These results suggest that the methods used by the ML-CCHDB, MLCPM-SDF, and ML-Miner algorithms to discover prevalent sub-areas are more efficient and versatile.

Figure 8 illustrates the number, precision, and recall of the highest-size (k = n_grandchild) prevalent sub-areas of LCPs mined by four methods when processing datasets with varying spatial instance distribution densities. Among these evaluation metrics, the ML-CCHDB algorithm consistently demonstrates high precision and recall. The ML-Miner algorithm, similar to its performance in Section 5.2, continues to fail to identify clusters that are nearby. Both the ML and MLCPM-SDF methods are unable to identify some pre-defined prevalent sub-areas. These results indicate that the ML-CCHDB method has advantages in handling datasets with varying instance distribution densities and containing sub-areas of different densities.

5.4 Influence of the number of spatial instances

In this section, synthetic datasets are utilized to evaluate the impact of the number of spatial instances on the performance of MLCPM methods. Specifically, we set the total number of instances I_num within the range of [20,000, 120,000] (including noise points), and set n_noise = int[I_num×(1-min_prev) / (4×min_prev + 1)] + 1, n_child = (I_num − n_noise) / 3, to ensure the dataset includes both GCPs and LCPs. To maintain consistent feature numbers and instance distribution density ρ across different datasets, we set L = 50,000, r_child = 30, n_grandchild = F_num, r_parent = (n_child × n_grandchild) / (ρ × π), Finally, we set F_num = 5, ρ = 0.0001, d = 60 and min_Reg = 800. Since the running time of the ML method is more than 20,000 seconds when I_num ≥ 40,000, only the experimental results of ML-CCHDB, MLCPM-SDF and ML-Miner are shown, as shown in Figures 9 and 10.

Figure 9.

Influence of the number of spatial instances on the runtime of MLCPM methods.

Figure 10.

Evaluation of MLCPM methods with varying numbers of spatial instances: (a) The number of prevalent sub-areas; (b) Precision; (c) Recall.

Figure 9 illustrates the runtime of three methods across datasets with varying numbers of instances. It is evident that the column computation methods used by ML-CCHDB and MLCPM-SDF require significantly less time for mining GCPs compared to the traditional methods employed by ML-Miner. This is because, as the number of instances increases, the number of instances with neighbor relationships also rises, causing the traditional method to take more time to generate row instances. Moreover, ML-CCHDB demonstrates superior efficiency in GCP mining compared to MLCPM-SDF, indicating that the optimizations for column computation in this study are effective. Meanwhile, as shown in Figure 10, the prevalent sub-areas mined by the ML-CCHDB method still maintain a high standard.

5.5 Influence of the parameters

In this section, the GM dataset is utilized to evaluate the impact of the neighbor distance threshold d and the prevalence threshold min_prev on the performance of MLCPM methods.

Neighbor distances threshold. As the ML-Miner method does not involve the neighbor distance threshold when obtaining neighbor relationships, this experiment presents the results of the ML-CCHDB, MLCPM-SDF and ML methods exclusively. During the experiment, the neighbor distance threshold d was set in the range [1000, 2600], with the prevalence threshold min_prev = 0.3. The results of the experiment are shown in Figure 11(a) (when d = 2600, the running time of the ML method exceeds 20,000 seconds, so it is not specifically displayed). It can be observed that as d increases, the time required by three methods to mine GCPs increases. This is because as d increases, more spatial instances are determined to have the neighbor relationships, thereby increasing the time required to identify the row instances or participating instances. Additionally, compared to the traditional GCPs mining method used by ML, the column calculation method employed by ML-CCHDB and MLCPM-SDF demonstrates good performance. When d is large, the running time difference between the three methods can reach up to a thousandfold.

Figure 11.

Influence of parameter variations on the runtime of MLCPM methods: (a) Neighbor distances threshold; (b) Prevalence threshold.

Prevalence threshold. During the experiment, the neighbor distance threshold d was set to 1000, and the prevalence threshold min_prev was set in the range [0.1, 0.5]. The experimental results are shown in Figure 11(b). It can be observed that as the min_prev increases, the time taken by the four MLCPM methods in mining LCPs increases accordingly. This is because, as the min_prev increases, the number of candidate LCPs increases. Furthermore, ML-CCHDB demonstrates the highest efficiency in the mining of GCPs, as well as a commendable efficiency in the mining of LCPs.

5.6 Mining multi-level co-location patterns in the dataset of distribution of rare vegetation in the three parallel rivers

In this section, the TPR dataset is used to validate the effectiveness of MLCPM methods. During the experiment, the prevalence threshold min_prev was set to 0.3 and the neighbor distance threshold d to 1000. For the MLCPM-SDF method, the relative distribution coefficient threshold min_rdc was set to 0.4 and the minimum edge length of the prevalent sub-area min_Reg was set to $\sqrt{2} \times d$ . The results are presented in Table 2 and Figure 12.

Table 2.
Partial results of MLCPM methods in mining GCPs and LCPs

Method

ML-CCHDB MLCPM-SDF ML-Miner ML

Pattern Type N_PA PI_min PI_max Type N_PA PI_min PI_max Type N_PA PI_min PI_max Type N_PA PI_min PI_max

A, C LCP 5 0.5 1 LCP 3 0.4 1 GCP - 0.40 LCP 2 0.48 0.49

B, G GCP - 0.37 LCP 7 0.35 1 GCP - 0.30 GCP - 0.37

B, L LCP 5 0.39 1 LCP 18 0.33 1 LCP 2 0.63 0.75 LCP 2 0.31 0.44

D, G LCP 5 0.33 1 LCP 8 0.5 1 GCP - 0.3 LCP 4 0.5 0.41

B, D, E LCP 4 1 1 LCP 3 0.68 0.96 LCP 2 0.8 0.85 LCP 3 0.49 1

B, E, G GCP - 0.33 LCP 3 0.40 0.68 LCP 1 0.61 GCP - 0.33

C, K, H LCP 8 0.90 1 LCP 3 0.40 0.82 LCP 2 0.84 0.95 LCP 2 0.49 0.70

C, K, L LCP 2 0.95 1 LCP 3 0.40 0.67 LCP 1 0.53 LCP 2 0.50 0.50

B, E, G, L LCP 8 0.84 1 LCP 6 0.47 0.86 LCP 1 0.46 LCP 2 0.44 0.90

	Method
A, C	LCP	5	0.5	1	LCP	3	0.4	1	GCP	-	0.40	LCP	2	0.48	0.49
B, G	GCP	-	0.37	LCP	7	0.35	1	GCP	-	0.30	GCP	-	0.37
B, L	LCP	5	0.39	1	LCP	18	0.33	1	LCP	2	0.63	0.75	LCP	2	0.31	0.44
D, G	LCP	5	0.33	1	LCP	8	0.5	1	GCP	-	0.3	LCP	4	0.5	0.41
B, D, E	LCP	4	1	1	LCP	3	0.68	0.96	LCP	2	0.8	0.85	LCP	3	0.49	1
B, E, G	GCP	-	0.33	LCP	3	0.40	0.68	LCP	1	0.61	GCP	-	0.33
C, K, H	LCP	8	0.90	1	LCP	3	0.40	0.82	LCP	2	0.84	0.95	LCP	2	0.49	0.70
C, K, L	LCP	2	0.95	1	LCP	3	0.40	0.67	LCP	1	0.53	LCP	2	0.50	0.50
B, E, G, L	LCP	8	0.84	1	LCP	6	0.47	0.86	LCP	1	0.46	LCP	2	0.44	0.90

N_PA: number of prevalent sub-areas; PI_min: (local) minimum participation index; PI_min: (local) maximum participation index.

Figure 12.

Partial prevalent sub-areas of LCPs: (a) LCP({B, D, E}); (b) LCP({K, L}); (c) LCP({E, L}); (d) LCP({B, E, G, L}).

Table 2 presents the partial results of four algorithms for mining GCPs and LCPs. It can be observed that the ML-CCHDB and ML methods demonstrate consistency in pattern-level determination, as both utilize neighbor distance thresholds to identify neighbor relationships, whereas the MLCPM-SDF additionally needs to determine whether a pattern is a GCP based on the relative distribution coefficient of its instances. Furthermore, the prevalent sub-areas of LCPs identified by ML-CCHDB tend to exhibit higher participation indices in their sub-areas compared to other methods. This is because the HDBSCAN method used by ML-CCHDB tends to cluster objects with consistent density, demanding high similarity among instances within the same cluster, resulting in more concentrated mined sub-areas.

Upon further examination of the frequent region diagrams of LCPs in Figure 12, it is evident that the ML-CCHDB method is particularly effective in identifying adjacent regions with distinct boundaries or density differences. These contrasts with other methods that tend to merge these sub-areas into a single prevalent sub-area. Additionally, the quadrant method used by MLCPM-SDF results in mined rectangular sub-areas that do not precisely match the actual pattern distribution. These examples demonstrate that the HDBSCAN clustering method employed by ML-CCHDB offers significant advantages in the rationality and interpretability of identifying prevalent sub-areas, indicating its greater precision and effectiveness in handling complex data distributions.

6 Conclusion

MLCPM is an efficient data mining technique that aims to mine GCPs and LCPs simultaneously. In this study, the limitations of the existing methods are deeply analyzed and a new method, named ML-CCHDB, is proposed, which effectively identifies the participating instances of the co-location patterns by optimizing the column computation technique to further mine the prevalent co-location patterns. Comparative experiments show that the optimization strategy of column computation is superior to the original method. In addition, ML-CCHDB applies the HDBSCAN clustering algorithm to identify the prevalent sub-areas of LCPs. Comparative experiments show that ML-CCHDB performs well in terms of mining efficiency as well as the reasonableness and interpretability of the prevalent sub-areas.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (62276227, 62266050, 62306266), the Project of Innovative Research Team of Yunnan Province (2018HC019), the Yunnan Fundamental Research Projects (202201AS070015, 202401AT070450), and the Postgraduate Research and Innovation Foundation of Yunnan University (KC-23235527, TM-23236884).

ORCID iD

Ting Yang

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

References

Yang

Wang

, et al. A spatial co-location pattern mining approach based on column calculation. Sci China Inf Sci 2022; 52: 1053.

Huang

Shekhar

Xiong

. Discovering colocation patterns from spatial data sets: a general approach. IEEE Trans Knowl Data Eng 2004; 16: 1472–1485.

Yao

Jiang

Wang

, et al. Efficiently mining maximal co-locations in a spatial continuous field under directed road networks. Inf Sci 2021; 542: 357–379.

Adilmagambetov

Jabbar

MSM

, et al. On discovering co-location patterns in datasets: a case study of pollutants and child cancers. GeoInformatica 2016; 20: 651–692.

Mohan

Shekhar

Shine

, et al. A neighborhood graph based approach to regional co-location pattern discovery: a summary of results. In: Proceedings of the 19th ACM SIGSPATIAL international conference on advances in geographic information systems. Chicago, Illinois: ACM, 2011, pp.122–132. doi: 10.1145/2093973.2093991.

Yoo

Shekhar

. A joinless approach for mining spatial colocation patterns. IEEE Trans Knowl Data Eng 2006; 18: 1323–1337.

Deng

Cai

Liu

, et al. Multi-level method for discovery of regional co-location patterns. Int J Geogr Inf Sci 2017; 31: 1846–1870.

Liu

Deng

, et al. An adaptive detection of multilevel co-location patterns based on natural neighborhoods. Int J Geogr Inf Sci 2021; 35: 556–581.

Wang

Yang

, et al. A novel algorithm for efficiently mining spatial multi-level co-location patterns. IEEE Trans Knowl Data Eng 2024; 36: 4361–4374.

10.

Yoo

Shekhar

Smith

, et al. A partial join approach for mining co-location patterns. In: Proceedings of the 12th annual ACM international workshop on geographic information systems. Washington, DC, USA: ACM, 2004, pp.241–249. doi: 10.1145/1032222.1032258.

11.

Wang

Tran

. Efficiently mining spatial co-location patterns utilizing fuzzy grid cliques. Inf Sci 2022; 592: 361–388.

12.

Zou

. A maximal ordered ego-clique based approach for prevalent co-location pattern mining. Inf Sci 2022; 608: 630–654.

13.

Baride

Saxena

Goyal

. Efficiently mining colocation patterns for range query. Big Data Res 2023; 31.

14.

Yoo

Boulware

Kimmey

. Parallel co-location mining with MapReduce and NoSQL systems. Knowl Inf Syst 2020; 62: 1433–1463.

15.

Andrzejewski

Boinski

. Efficient spatial co-location pattern mining on multiple GPUs. Expert Syst Appl 2018; 93: 465–483.

16.

Bao

Wang

. A clique-based approach for co-location pattern mining. Inf Sci 2019; 490: 244–264.

17.

Zhang

Wang

Tran

. CPM-MCHM: a spatial co-location pattern mining approach based on maximal clique and hash table. Chin J Comput 2022; 45: 526–541.

18.

Wang

Tran

, et al. Fast mining prevalent co-location patterns over dense spatial datasets. In: Proceedings of the 4th international conference on spatial data intelligence, 2023, pp.179–191. doi: 10.1007/978-3-031-32910-4_13.

19.

Celik

Kang

Shekhar

. Zonal co-location pattern discovery with dynamic parameters. In: Proceedings of the Seventh IEEE international conference on data mining (ICDM 2007). Omaha, NE, USA: IEEE, 2007, pp.433–438. doi: 10.1109/ICDM.2007.102.

20.

Ding

Eick

Yuan

, et al. A framework for regional association rule mining and scoping in spatial datasets. GeoInformatica 2011; 15: 1–28.

21.

Qian

Chiew

, et al. Mining regional co-location patterns with kNNG. J Intell Inf Syst 2014; 42: 485–505.

22.

Jiang

Wang

Tran

. A parallel algorithm for regional co-location mining based on fuzzy density peak clustering. Sci China Inf Sci 2023; 53: 1281–1298.

23.

McInnes

Healy

Astels

. Hdbscan: hierarchical density based clustering. J Open Source Softw 2017; 2: 05.

24.

Ouyang

Wang

. Spatial co-location pattern discovery from fuzzy objects. Int J Artific Intell Tools 2017; 26: 1750003.

25.

Guo

Wang

. Automatic region building for spatial analysis. Trans GIS 2011; 15(s1): 29–45.

	Method
	ML-CCHDB				MLCPM-SDF				ML-Miner				ML
Pattern	Type	N_PA	PI_min	PI_max	Type	N_PA	PI_min	PI_max	Type	N_PA	PI_min	PI_max	Type	N_PA	PI_min	PI_max
A, C	LCP	5	0.5	1	LCP	3	0.4	1	GCP	-	0.40		LCP	2	0.48	0.49
B, G	GCP	-	0.37		LCP	7	0.35	1	GCP	-	0.30		GCP	-	0.37
B, L	LCP	5	0.39	1	LCP	18	0.33	1	LCP	2	0.63	0.75	LCP	2	0.31	0.44
D, G	LCP	5	0.33	1	LCP	8	0.5	1	GCP	-	0.3		LCP	4	0.5	0.41
B, D, E	LCP	4	1	1	LCP	3	0.68	0.96	LCP	2	0.8	0.85	LCP	3	0.49	1
B, E, G	GCP	-	0.33		LCP	3	0.40	0.68	LCP	1	0.61		GCP	-	0.33
C, K, H	LCP	8	0.90	1	LCP	3	0.40	0.82	LCP	2	0.84	0.95	LCP	2	0.49	0.70
C, K, L	LCP	2	0.95	1	LCP	3	0.40	0.67	LCP	1	0.53		LCP	2	0.50	0.50
B, E, G, L	LCP	8	0.84	1	LCP	6	0.47	0.86	LCP	1	0.46		LCP	2	0.44	0.90