How Is the Confidentiality of Crime Locations Affected by Parameters in Kernel Density Estimation?

Abstract

Kernel density estimation (KDE) is widely adopted to show the overall crime distribution and at the same time obscure exact crime locations due to the confidentiality of crime data in many countries. However, the confidential level of crime locational information in the KDE map has not been systematically investigated. This study aims to examine whether a kernel density map could be reverse-transformed to its original map with discrete crime locations. Using the Epanecknikov kernel function, a default setting in ArcGIS for density mapping, the transformation from a density map to a point map was conducted with various combinations of parameters to examine its impact on the deconvolution process (density to point location). Results indicate that if the bandwidth parameter (search radius) in the original convolution process (point to density) was known, the original point map could be fully recovered by a deconvolution process. Conversely, when the parameter was unknown, the deconvolution process would be unable to restore the original point map. Experiments on four different point maps—a random point distribution, a simulated monocentric point distribution, a simulated polycentric point distribution, and a real crime location map—show consistent results. Therefore, it can be concluded that the point location of crime events cannot be restored from crime density maps as long as parameters such as the search radius parameter in the density mapping process remain confidential.

1. Introduction

Kernel density estimation (KDE) is widely adopted to show the overall crime distribution and at the same time obscure exact crime locations due to the confidentiality of crime data in many countries [1,2,3,4,5,6]. In the field of crime prediction, KDE is widely used to generate hotspots, which are then used to guide police for targeted intervention. Compared to the city-wide patrol practice, hotspot-targeted patrol strategies could save police resources and deter crime [7,8]. Another benefit of KDE is that it could maintain the confidentiality of crime locations due to its ability to obscure locational information [4,9,10,11,12,13,14].

Compared to the large body of research and applications for density maps, the confidential level of crime locational information in KDE maps has not been systematically investigated [9,11,15,16]. This study aims to examine whether a kernel density map could be reverse-transformed to its original map with discrete crime locations. Considering the fact that the predictability of density maps could be affected by the bandwidth for KDE, the impact of KDE’s parameters on the confidentiality of density maps will be extensively examined in our current literature [17,18]. The conclusions are expected to answer whether—and to what extent—the locational information of a kernel density map is retained.

2. Literature Review

One important goal for crime prediction research is to identify crime hotspots. Crimes are not evenly distributed but concentrated within limited areas, which are usually called hotspots [7,10,19,20,21,22,23,24,25]. KDE is a popular method for crime mapping and hotspot detection [26]. Hotspot maps can also be used to indicate future crime risk [27,28]. Due to the attractiveness of hotspots to potential offenders [29,30,31,32,33,34], targeted intervention could help reduce and prevent future crime. Compared to the random patrol strategy, characterized as “a drop in the bucket” over a whole city, the hotspots provide targets for proactive policing patrol, saving great police effort and improving the efficiency of crime prevention initiatives [35,36,37].

The confidentiality of crime locations is of concern in many countries. Crime locations could lead to revealing victims’ locations, disclosing opportunity information to potential offenders, or even imparting experience to potential offenders [14,38]. To avoid such problems, various types of location protecting techniques have been used to protect these privacies [4,5,9,11,13,14]. Geocoding of crime events to a street segment or a city block can encrypt their precise geographic locations [4,5,6]. Transforming a point map to a density map can help mask the exact location of crime events [4,5,11,16,39]. KDE is one of the most commonly used locational protecting methods due to its outstanding ability to obscure location information and at the same time show the spatial distribution patterns of crimes [15,26,40,41].

With the aim of testing the confidentiality of crime locations in density maps, several research works have aimed to recover point maps from density maps [16]. For example, Lee, Chun and Griffith proposed a geometric center-based method to recover point maps [16], while Seidl, et al., evaluated the confidential level of masked maps [15]. Both studies were conducted on the spatial domain, and their recovering accuracies are extremely low for smooth density surfaces. It is acknowledged that most KDE calculations were conducted in the frequency domain rather than spatial domain [42,43,44]. Therefore, the confidentiality of density maps generated in the frequency domain should be examined in the frequency domain rather than the spatial domain. More importantly, the smoothness of density maps is closely related to the parameters (e.g., bandwidth) of kernel functions. The impact of the parameters of a kernel function on the confidentiality level of density map needs to be further investigated.

3. Research Questions and Methodology

To fill the aforementioned gap, this research aims to design a series of experiments to answer the following questions:

• Question 1: How does kernel function’s parameter affect the confidential level of density maps?
• Question 2: How does crime distribution pattern affect the confidential level of density maps?
• Question 3: To what extent can a density map be recovered?

3.1. Convolution and Deconvolution

The process of transforming a point map to an undulated density map is a convolution process. Convolution can be mathematically interpreted as an operation on two functions to generate a third function that expresses how the shape of one is modified by another (Figure 1). In contrast, the process of transforming a density map to a point map is called deconvolution. A kernel function will be used to transform a density surface to a point map in this process. Deconvolution is used to remove the effect of one function on another and thus recover the original data. Convolution could be expressed with the formula [45,46]

$$g=f\ast h$$

(1)

where $g$ is the processed data, $f$ is the original data, and h is the kernel function. Deconvolution is used to eliminate the effect of kernel function on a density map using algorithms to reverse the effects of convolution on point data. Deconvolution is usually performed in the frequency domain by computing the Fourier transformation of h and g separately. When ignoring the absence of noise, deconvolution could be computed as:

$$F=G/H$$

(2)

where F, G, and H are the Fourier transforms of f, g, and h respectively. Following this calculation, F will be transformed to the estimated deconvolved signal or image f by inverse Fourier transform.

If the noise is considered, a deconvolution could be expressed as

$$g=f\ast h+n$$

(3)

where $n$ is the noise [47]. Correspondingly, its Fourier transformation could be expressed as

$$G=FH+N$$

(4)

where N is the fourier transformation of noise. To calculate this equation, we could use

$$\widehat{F}=WG$$

(5)

where $\widehat{F}$ is the recovered map.

$$W=\frac{H^{*}}{{\left|H\right|}^2+K}$$

(6)

where $H^{*}$ is the Fourier transformation of the kernel function used for generating the density map; $K=\raisebox{1ex}{${\left|F\right|}^2$}\!\left/ \!\raisebox{-1ex}{${\left|N\right|}^2$}\right.$. If $K=0$ then $W=\frac{1}{H}$, Equation (5) equals Equation (2). If $K\gg \left|H\right|$, then high frequencies are attenuated. In this process, least squares are used to narrow the results’ error: $\widehat{F}-F$.

In this research, when the parameters are known for deconvolution, Equation (2) will be used to derive the original map. When the parameters are unknown for deconvolution, Equation (3) will be used to recover the original map. The errors caused by mismatching parameter values between convolution and deconvolution will be considered as noise, $n$.

3.2. Experimental Design

The experiment in this study is illustrated in a flowchart in Figure 2. Three maps containing a pre-specified number of points (such as 100) with different spatial distribution patterns will be generated (Figure 3). The three simulated point maps include a random point map, a monocentric point map and a polycentric distribution. A convolution process will be carried out on each map to create a density map, followed by a deconvolution process converting the density map back to the point map. The confidentiality of the density map will be analyzed through the accuracy evaluation of the recovered map in comparison to the original point map. Following the three simulated maps, real crime data will be used to test whether a kernel density map could be recovered to the original point map.

As a common type of kernel function used in ArcGIS (ESRI, Redlands, CA, USA), the Epanecknikov kernel will be adopted in this study [48]:

$$\mathrm{f}\left(\mathrm{x}\right)=\frac{1}{nh}{\displaystyle \sum }_{t=1}^{n}K\left(\frac{x-x_t}{h}\right)$$

(7)

where h is the bandwidth, $n$ is the number of events, $x-x_t$ is the distance from the center to each incident t, and K is the quadratic kernel function:

$$\mathrm{K}\left(\mathrm{x}\right)=\frac{3}{4}\left(1-x^2\right), \left|x\right|\le 1$$

(8)

The bandwidth is the shorter one between the width or height of the output extent in the output spatial reference, divided by 30 (in the versions before 10.2.1 of ArcGIS Desktop). In the versions after 10.2.1, the default bandwidth was changed to be calculated using a new function [49]:

$$\mathrm{Bandwidth}=0.9\ast \min \left(SD, \sqrt{\frac{1}{ln\left(2\right)}}\ast D_m\right)\ast n^{-0.2}$$

(9)

where SD is the standard distance calculated by the standard deviation of distances between each pair of points. $D_m$ is the medium distance. The bandwidth in the past ArcGIS versions was determined by the width of the study area while the bandwidth in the new versions was determined by the distribution pattern of points.

In a deconvolution process, the bandwidth cannot be acquired because there are no points in a density map. Therefore, the bandwidth calculation method in the past ArcGIS versions will be adopted in our current study. In order to assess the accuracy of recovered maps, two indicators will be adopted. Mean Integrated Squared Error (MISE) was proposed by Delaigle and Gijbels to assess the accuracy of the recovered map after deconvolution [50].

$$\mathrm{MISE}\left(h\right)=\frac{1}{B}{\displaystyle \sum }_{b=1}^B\int {[\widehat{fx}\left(x;h\right)-fx\left(x\right)]}^{2}dx$$

(10)

where B is the number of cells in the map, $\widehat{fx}\left(x;h\right)$ and $fx\left(x\right)$ represent the recovered map after deconvolution and the original point map respectively. h is the selected bandwidth.

The capture rate (CR), as a common index in crime prediction literature, was previously utilized to evaluate the accuracy of crime prediction map [26]. CR is the percentage of crime events for a measured data time period falling into the areas where crimes are predicted to occur.

$$CR=\frac{n\ast 100}{N\ast 100}$$

(11)

where N is the maximum number of crimes that could be captured in the prediction area, n is the number of crimes in areas where crimes are predicted to occur. The standard deviation is calculated by the standard deviation of all cell values in the recovered map. In our current research, this indicator is used to evaluate the scale of error distribution.

4. Experimental Results

The deconvolution process with unknown bandwidth is implemented. The maximum bandwidth is set to half of the dimension of the original point map. For each bandwidth value for kernel convolution, all possible bandwidth values will be applied to the deconvolution, and this process is repeated for all possible bandwidth values for kernel convolution. The accuracy of the recovered point map in deconvolution will be compared to the original point map by the error (MISE) and capture rate (CR) for each combination of bandwidth in convolution and bandwidth in deconvolution. The MISE and CR values are recorded in a two dimensional matrix (Figure 4).

Figure 4a,b indicate the error and capture rate of the recovered random point map for the random point map. When the bandwidth for deconvolution is the same as that used in convolution, the point map could be recovered with a very high accuracy (Figure 4a diagonal values < 0.01, Figure 4b diagonal values = 1). In contrast, when the bandwidth for deconvolution is different from that of convolution, the original map cannot be exactly recovered due to the great noise values (Figure 4a, non-diagonal values: [0.37, 29.31]; Figure 4b, non-diagonal values: [0,0.07]).

The results of the monocentric distribution (Figure 4c,d) are similar to those of the random distribution. When the bandwidth is known, the original point map can be recovered from a density map at high accuracy (Figure 4c, diagonal values <0.01; Figure 4d, diagonal values = 1). In contrast, when the bandwidth is unknown, the accuracy of the recovered map would be very low (Figure 4c, non-diagonal values: [0.62, 25.38]; Figure 4d, non-diagonal values: [0,0.12]).

Likewise, the results of the polycentric distribution (Figure 4e,f) are similar to those of the random distribution. When the bandwidth is known, the original point map could be recovered from a density map at high accuracy (Figure 4e, diagonal values <0.01; Figure 4f, diagonal values = 1). In contrast, when the bandwidth is unknown, the accuracy of the recovered map would be very low (Figure 4e, non-diagonal values: [0.62, 24.22]; Figure 4f, non-diagonal values: [0,0.08]).

Other than the diagonal cells, the rest of the cells on the accuracy maps (Figure 4a–f) do not show any discernable pattern, thus making the minimization of the errors impossible. Therefore, when the bandwidth is unknown for convolution process, the original point map cannot be restored by a deconvolution process in frequency domain.

5. Case Study

5.1. Data Source and Study Area

The research area is N city, one of the largest cities in southeast China. The downtown area of N city consists of four administrative districts and 7.17 million people. As one of the most populated cities in China, the population density of the research area is 6367 persons per square kilometer. For two districts located in the city center, the population density is over 21,000 persons per square kilometer, which is comparable to the population density in the center urban area of Beijing and Shanghai. Additionally, as a regional political, economic and transportation center, N city is one of the biggest cities in the Yangtze River Delta Region. The floating population (relocated from nearby cities) of N city is around 2 million. The population and economic characteristics has allowed the economy of N city to develop rapidly. These characteristics make N city highly representative in China (Figure 5).

The current research uses an official crime dataset provided by the local Public Security Bureau. The full dataset includes a total of 9965 burglary records from 1st January 2015 to 30th December 2017. Each record of the data includes location (XY coordinates) and the occurrence date.

5.2. Deconvolution Analysis with Crime Data

In this experiment, we will first generate the scatter plot with criminal points and then convert the point map to the density map which is usually provided in patrol practice. Secondly, the deconvolution process will be conducted to convert a density map into a grid map. Finally, the error of recovered maps will be statistically analyzed.

Figure 6a indicates that the burglary events are concentrated in the central longitudinal axis area of N city. The maximum bandwidth size is set to 10 km, which is nearly half of the dimension of the study area.

If the BT is known for deconvolution, the map could be accurately restored (Figure 6b,d). The accuracies of the recovered map (Figure 6e,f) indicate a similar pattern to those of the simulated data (Figure 4a,c,e). If the parameters for deconvolution are known, the accuracies of the recovered maps is very high (Figure 6e, diagonal values <0.1; Figure 6f, diagonal values = 1). However, if the parameters for deconvolution are unknown, the accuracies of the recovered maps are very low (Figure 6e, non-diagonal values: [1.82, 126.04]; Figure 6f, non-diagonal values: [0.005, 0.1506]).

6. Discussion

With the above results of the experiments and the case study, let us revisit the research questions set forth earlier in the paper. With regard to Question 1, the deconvolution process varied significantly with the change of parameters. In the frequency domain, even a small difference of bandwidth could introduce a great error to the convolution/deconvolution process. Therefore, the possibility of recovering a density map to a point map largely depends on whether the parameters can be inferred. The results indicate that the errors vary as a function of the bandwidth. Importantly, the error distribution does not apparently indicate any pattern which might be helpful to infer the bandwidth used in convolution. This situation makes it more difficult to restore a point map from a kernel density map. In summary, the parameters exert a great impact on the convolution and deconvolution process.

With regard to Question 2, the point distribution pattern does not affect the accuracy of the deconvoluted maps. Three different point distribution patterns were used in this study. The results indicated that the error did not change much with the changed crime distribution patterns. When the bandwidth for deconvolution was known, the point map could be recovered, while when the bandwidth for deconvolution was unknown, the recovered point map was drastically different from the original point map.

With regard to Question 3, the impact of parameters on deconvolution was very small. A point map can be recovered from a density map at a high accuracy level when parameters are known for deconvolution. In contrast, a point map is nearly impossible to recover from a density map when the parameters are unknown. The impact of the parameter adopted in the convolution process was thoroughly examined. The answer agrees with the statement in the previous literature that “KDE could protect locational privacy” very well when parameters for deconvolution are unknown [13].

The results using real crime data indicate similar results: the errors of point maps generated by unknown parameters are much larger than the others. Importantly, the errors did not indicate a significant pattern for parameter change. The highest capture rate of non-diagonal units could reach 15.06%. Importantly, the high capture rate occurred when the bandwidth for convolution was very large and bandwidth for deconvolution was very small. It could be inferred that most of the captured crimes were captured by hotspots because a large bandwidth would generate a smooth surface and a small bandwidth could remove the high-frequency information, leaving the low-frequency information (e.g., the smoothness hotspots) as a “recovered map”. Therefore, the accuracy of recovered maps is still at a low accuracy level. The locational information of crimes was still confidentially preserved. Such a confidentiality rate indicates that most of the locational information of crimes were masked at a high level.

7. Conclusions

The confidentiality of crime locations is of concern in many countries. KDE can help to mask the exact location of crime events by transforming a point map to a density map. However, an accurate recovery of point locations from a density map (i.e., a reverse transformation) may reveal the original point locations. With the aim of testing the confidentiality of crime locations in density maps, this study investigated the impact of parameters for the deconvolution process from a density map to a point map.

Using the default kernel function in ArcGIS, the possibility of transferring a density map to a point map was first examined using known parameters for deconvolution followed by using unknown parameters for deconvolution. The experimental results indicate that, although the point distribution pattern and the parameters of kernel function changed, the point map could be recovered at a high accuracy when the parameters for deconvolution were known. When the parameters for deconvolution were unknown, the errors of the recovered point maps were very large compared to the original point map. Using two widely used indicators in the crime prediction research field, the MISE index indicated that the values of recovered maps are on a much higher level of accuracy compared to the original map, while the CR value indicated that a low percentage of points was correctly predicted by the recovered point maps. More importantly, the number of points and the point distributions differed to the original point map to a large extent. In summary, KDE performs well at preserving locational information because it is nearly impossible to recover a density map to a point map with unknown parameters.