# Understanding Public Safety Trends in Calgary through data mining

Zack Dewis  Dept. of Geomatics
University of Calgary
Calgary, Alberta
<EMAIL_ADDRESS>
30091912  Apratim Sen  Dept. of Geomatics
University of Calgary
Calgary, Alberta
<EMAIL_ADDRESS>
30202853  Jeffrey Wong  Dept. of Geomatics
University of Calgary
Calgary, Alberta
<EMAIL_ADDRESS>
30200496  Yujia Zhang  Dept. of Geomatics
University of Calgary
Calgary, Alberta
<EMAIL_ADDRESS>
30221253

###### Abstract

This paper utilizes statistical data from various open datasets in Calgary to
to uncover patterns and insights for community crimes, disorders, and traffic
incidents. Community attributes like demographics, housing, and pet
registration were collected and analyzed through geospatial visualization and
correlation analysis. Strongly correlated features were identified using the
chi-square test, and predictive models were built using association rule
mining and machine learning algorithms. The findings suggest that crime rates
are closely linked to factors such as population density, while pet
registration has a smaller impact. This study offers valuable insights for
city managers to enhance community safety strategies.

###### Index Terms:

Keywords—Statistical data, predictive model, crime, disorder, traffic
incidents, community characteristics, demographics, housing, pet registration,
geospatial visualization, correlation analysis, chi-square test, association
rule mining, machine learning algorithms, population density, community safety
strategies

##  I Introduction

###  I-A Research Background and Objectives

With the acceleration of urbanization,community crimes, disorders, and traffic
incidents have become increasingly prominent issues, severely impacting
residents’ quality of life and the sustainable development of cities. Data
mining techniques provide new perspectives for addressing these problems. This
study, using Calgary, Canada, as an example, aims to utilize multi-source
urban data including streetlights, trees, traffic accidents, crimes, pet
registrations, census data, community security, and traffic camera data to
explore the key factors affecting community safety and construct predictive
models, providing data support for urban management decisions. Clustering
algorithms such as K-Means and DBSCAN are commonly used in urban data mining,
but their clustering effectiveness for complex data needs improvement. This
paper proposes to introduce advanced clustering algorithms such as CLARANS and
CLIQUE, and enhance clustering performance through parameter optimization.

###  I-B Research Questions and Innovations

This study aims to address the following questions: (1) What are the
characteristics of public facilities, population structure, crime, and
accident distribution in various communities in Calgary? (2) Which community
factors are significantly correlated with safety issues? (3) Can effective
predictive models for crime, security incidents, and traffic accidents be
constructed?

The innovations of this study include: (1) Aggregating cutting-edge urban data
such as streetlights, trees, and pets to deconstruct the multidimensional
factors influencing community safety; (2) Introducing advanced clustering
algorithms such as CLARANS and CLIQUE, integrating optimized clustering with
predictive analysis; (3) Establishing predictive models based on real data,
providing new insights for fine-grained urban governance.

##  II Literature Review

The increasing prevalence of community crimes, disorders, and traffic
incidents due to rapid urbanization has become a major concern for city
dwellers and urban planners alike. These issues not only affect the quality of
life of residents but also pose significant challenges to the sustainable
development of cities. In recent years, data mining techniques have emerged as
a promising approach to tackle these problems by providing new perspectives
and insights. The present study focuses on Calgary, Canada, and aims to
identify the key factors influencing community safety by analyzing multi-
source urban data and developing predictive models that can support decision-
making in urban management [7, 9, 10].

K-Means and DBSCAN are among the most widely used clustering algorithms in
urban data mining. However, their performance on complex data sets often
leaves room for improvement. To address this issue, the current study explores
the use of advanced clustering algorithms, such as CLARANS and CLIQUE, and
seeks to optimize their performance through parameter tuning. This work builds
upon the foundations laid by Ng and Han [3] and Hartigan and Wong [1] in the
field of clustering algorithms. Moreover, the efficiency analysis of the
K-Means algorithm conducted by Kanungo et al. [2] offers valuable insights
into the data-sensitive nature of the algorithm’s running time, which is
particularly relevant to the data sets used in this study.

When it comes to analyzing crime data, regression analysis is a commonly used
approach. The methods employed in this study draw inspiration from the
correlated data regression analysis proposed by Liang and Zeger [6], which is
particularly useful when dealing with the inherent correlation issues often
encountered in biomedical research data. In addition, Schubert et al.’s [4]
critical review of the DBSCAN algorithm, which highlights the importance of
selecting appropriate parameters for optimal performance, is taken into
consideration. The density-based clustering structure of data sets, as
demonstrated by Ankerst et al. [5] using the OPTICS algorithm, also serves as
a guiding principle for the approach adopted in this study.

The methodology of this study is further informed by the work of other
researchers in the field of spatial data mining. For instance, Bernasco and
Elffers [11] provide a comprehensive overview of the statistical analysis of
spatial crime data, while Anselin et al. [12] demonstrate the application of
spatial analysis in crime research. These studies not only introduce new
methods for analyzing spatial data but also shed light on the intricate
relationship between crime and place.

In the era of big data, data integration presents a significant challenge that
must be addressed. Dong and Srivastava [7] delve into the progress made by the
data integration community in tackling issues such as schema mapping, record
linkage, and data fusion when working with large, dynamic, heterogeneous, and
varying quality data sources. By incorporating cutting-edge urban data, such
as information on streetlights, trees, and pets, this study aims to contribute
to the understanding of the multifaceted factors that influence community
safety in Calgary.

Although the primary focus of this study is on modeling large-scale, global
structures, the principles and techniques discussed by Hand [13] in the
context of detecting adverse drug reactions in the pharmaceutical industry can
also be applied to identify anomalies and outliers in urban crime data. This
approach contributes to a more comprehensive understanding of community
safety.

While this study makes notable contributions to the field, it is not without
limitations. Due to constraints in data availability, the study only covers a
limited set of community indicators and spans a relatively short time frame.
Future research could benefit from collecting more comprehensive data and
conducting long-term spatiotemporal analyses. Additionally, the complex and
diverse nature of the causes underlying urban safety issues makes it
challenging to establish clear causal relationships and mechanisms based
solely on data analysis. To address this, subsequent studies could incorporate
qualitative methods, such as expert interviews and case studies, to explore
the socioeconomic, institutional, and cultural factors that influence
community safety.

This study builds upon existing algorithms and methods from the literature,
making improvements and extensions to enable more effective processing and
analysis of urban safety data. By combining various clustering and regression
analysis techniques into predictive models, this research provides valuable
scientific evidence and insights that can inform urban governance and
contribute to the development of safer cities. The findings underscore the
crucial role that data mining techniques can play in addressing the challenges
posed by urbanization and promoting the well-being of city residents.

##  III Data Source and Preprocessing

The data used in this study were obtained from the City of Calgary’s open data
platform, including 2019 data on streetlights, public trees, traffic
incidents, crime statistics, licensed pets, census by community, community
disorder statistics, and traffic cameras.

###  III-A Data Cleaning and Geocoding

Despite all of the data being acquired from the same source, data cleaning was
still necessary in order to extract interesting patterns from the data and to
perform further analysis. Starting off, the data was manually inspected, where
any columns that were deemed unnecessary or blank were removed. Next, all the
datasets were loading into Panda dataframes for easy further cleaning. At this
stage all rows that were duplicate entries to another row in any of the seven
datasets were removed. For the columns that had either Na values of missing
values, these were modified on a case-by-case basis. If the column has located
in the crime dataset, the values were replaced with zero as the assumption was
made that this meant there was zero crime in this particular neighbourhood.
This occurred for the neighbourhoods that were still being developed in
Calgary when the 2019 census was being conducted and therefore any crime that
may have occurred was deemed irrelevant to the research goal.

Another issue that arose during the cleaning process was that not all the
datasets provided latitude and longitude coordinates for where each of the
attributes was located. This was solved by running a python script to join the
datasets and assign each a latitude and longitude to allow for clustering
analysis. Some datasets contained both latitude and longitude as well as a
community name or identifier, some contained just a community name and some
only contained latitude and longitude. The decision was made that each dataset
should be given both latitude and longitude coordinates and a community name
attached to it. To achieve this, three different methodologies were used
depending on what each individual dataset already contained. If the dataset
already contained latitude, longitude and a community name, no further action
was required. For datasets only containing a community name, the community
centroid coordinates were assigned to the data to provide it a latitude and
longitude. For datasets only containing latitude and longitude, a community
boundary shapefile was used, where a script was then ran to see which
community the points intersected and then a name was assigned.

At this point all of the necessary data cleaning had been performed for
analysis to be carried out. Geocoding had also been performed on all of the
datasets, allowing for summary statistics to then be calculated to perform
correlation and regression analysis.

###  III-B Feature Engineering and Data Integration

With the data cleaning and geocoding complete, the next step was to aggregate
the data to the same level in order to perform analysis. Community level was
selected as the resolution for all the data to be aggregated to. The reason
for this was that it was the finest resolution that was available to be used
without having to make assumptions and convert datasets to finer resolutions
than they are provided at. As the community census and crime was only at
community level, a more fine solution could not be used for aggregation.

At the community level, we calculated various indicators such as the number of
streetlights, average wattage, total wattage, number of trees, number of
traffic incidents, total number of crimes and crime categories, number of
community disorder events, total number of registered pets, and number of
registered cats and dogs. We also extracted demographic features of
communities from census data, such as total population, male-female ratio,
number of dwellings, and number of apartments.

Finally, all of these statistical indicators were compiled into a new geopanda
dataframe to be used for further analysis. The original dataframes were also
maintained and used for cluster analysis as many were at a finer resolution
and allowed for clustering to be performed on them. The data is now fully
ready for data mining processes to be performed with the goal of being able to
extract interesting patterns and insight from it.

##  IV Methodology

To best extract patterns from the dataset, several exploratory data analyses
and different data mining techniques were used in hopes of extracting
interesting patterns. This includes data summarization, visualization,
temporal analyses, clustering, correlation, regression, and association rule
mining.

###  IV-A Exploratory Data Analysis

Exploratory Data Analysis (EDA) is a crucial step in data analysis, especially
when dealing with new datasets. It involves exploring and summarizing the main
characteristics, patterns, and relationships present in the data. The primary
goal of EDA is to gain insights and understanding of the data to inform
further analysis or modeling tasks.

####  IV-A1 Data Summarization

Firstly, we started with summarizing the main characteristics of the data, by
categories and by community, for the total number of categorical features. For
the traffic incident dataset, there were no categorical data but only the
descriptions. We mapped some keywords in the description column to a new
column ’category’.

####  IV-A2 Geospatial Visualization

And visualizations of the data were created and manually analyzed to see if
there were any regions of interest within the city that should have further
inspection or analysis performed. To visually demonstrate the distribution
differences of various indicators among communities, we created interactive
maps using the Folium library. Specifically, we used community polygons as
basic plotting units, colored the polygons based on the values of each
indicator, and added legend explanations. Additionally, we experimented with
various color schemes to better highlight spatial patterns.

####  IV-A3 Temporal Analysis

Temporal analysis were performed to examine how community crimes, disorders,
and traffic incidents change over time.

###  IV-B Correlation Analysis

Then, correlation mining was also performed to determine which attributes were
positively or negatively correlated with each other within the city.

####  IV-B1 Correlation Analysis

To explore the correlations between factors and safety issues, we computed the
correlation matrix of gdf_comm and plotted heatmaps using the Seaborn library.
We focused on the correlations between demographic indicators, indicators
related to children and schools, streetlight and tree indicators, pet quantity
indicators, and crimes, security incidents, and traffic accidents

###  IV-C Cluster Analysis

To further explore the intrinsic structure and similarities among communities,
we employed various clustering algorithms onto the cleaned geocoded datasets.
In selecting clustering algorithms the goal was to cover as many different
approaches as possible and see what would have the best results on the data.
Based on our research [18], we found that density-based and grid-based methods
are usually more suitable for handling spatial data. For the partitioning
approach, K-Means and CLARANS were selected, Agglomerate Clustering was chosen
for the hierarchical approach, DBSCAN and OPTICS were selected for the density
based approach and CLIQUE was used for the grid-based approach. Overall, the
approach for how each method was implemented is quite similar, but nonetheless
will be broken down into more detail below.

####  IV-C1 K-Means Clustering

K-Means was the first algorithm implemented. It was implemented on each
dataset using the latitude and longitude coordinates to determine clusters. To
determine the optimal number of clusters, we used the silhouette score as the
evaluation metric, tested a range of 2 to 20 clusters, and plotted the
relationship between the silhouette score and the number of clusters. Finally,
we selected the optimal value corresponding to the highest silhouette score.
The clustering results were visualized using Folium maps.

Step 1: Accept the number of clusters to group data into and the dataset to
cluster as input values. Step 2: Initialize the first K clusters. Step 2.1:
Take the first k instances or. Step 2.2: Take a random sampling of k elements.
Step 3: Calculate the arithmetic means of each cluster formed in the dataset.
Step 4: K-means assigns each record in the dataset to only one of the initial
clusters. Step 4.1: Each record is assigned to the nearest cluster using a
measure of distance (e.g., Euclidean distance). Step 5: K-means re-assigns
each record in the dataset to the most similar cluster and re-calculates the
arithmetic mean of all the clusters in the dataset. [17]

Figure 1: Generalized pseudocode of traditional K-means

####  IV-C2 CLARANS Clustering

Considering that the K-Means algorithm is susceptible to outliers, we further
attempted the CLARANS (Clustering Large Applications based upon RANdomized
Search) algorithm. This algorithm minimizes the cost function through random
search and can efficiently handle large datasets. We implemented CLARANS
clustering using the pyclustering library and conducted grid search on
different parameter combinations to achieve the optimal clustering effect.
Again, the silhouette score was used to determine what the optimal parameters
for the algorithm were. This was repeated for each dataset to determine the
optimal parameters.

Step 1: Input parameters numlocal and maxneighbour. Step 2: Set current to an
arbitrary node in $G(n,k)$. Step 3: Set $j$ to 1. Step 4: Consider a random
neighbor $S$ of current, calculate the cost differential of the two nodes.
Step 5: If $S$ has a lower cost, set current to $S$, and go to Step 3. Step 6:
Otherwise, increment $j$ by 1. If $j\geq$ maxneighbour, go to Step 4. Step 7:
Otherwise, when $j>$ maxneighbour, compare the cost of current with mincost.
If the former is less than mincost, set mincost to the cost of current, and
set bestnode to current. Step 8: Increment $i$ by 1. If $i>$ numlocal, output
bestnode and halt. Otherwise, go to Step 2. [16]

Figure 2: Generalized version of CLARANS algorithm

####  IV-C3 CLIQUE Clustering

To explore hidden patterns in high-dimensional data, we also introduced the
grid-based density clustering algorithm CLIQUE (Clustering In QUEst). This
algorithm first divides the data space into a series of grid cells, then
identifies high-density cells, and finally forms clusters by combining
adjacent high-density cells. We implemented CLIQUE clustering using the
pyclustering library and conducted sensitivity analysis on parameters such as
cell size and density threshold.

####  IV-C4 DBSCAN Clustering

To assess a density based clustering method, DBSCAN was implemented on each of
the datasets, again with the silhouette score being used to determine the
optimal parameters DBSCAN functions by categorizing points as either core,
border or outlier/noise points. This is determined based on the density of the
points, a point becomes a core point if it has at least the minimum amount of
points needed to reach the threshold set by the user within its boundary (also
set by the user). Multiple different parameter sets were selected, for both
the threshold and the minimum amount of points needed for a point to become a
core point. To explain the algorithm, we first need to define density
connected point: Two points are called density connected if there is a core
point which is density reachable (i.e. connected through a series of core
points) from both the points.

Step 1: Choose a value for eps and MinPts. Step 2: For a particular data point
(x), calculate its distance from every other data point. Step 3: Find all the
neighborhood points of x which fall inside the circle of radius (eps) or
simply whose distance from x is smaller than or equal to eps. Step 4: Treat x
as visited and if the number of neighborhood points around x is greater or
equal to MinPts, then treat x as a core point. If it is not assigned to any
cluster, create a new cluster and assign it to that. Step 5: If the number of
neighborhood points around x is less than MinPts and it has a core point in
its neighborhood, treat it as a border point. Step 6: Include all the density-
connected points as a single cluster. (What density-connected points mean is
described later). Step 7: Repeat the above steps for every unvisited point in
the dataset and find out all core, border, and outlier points. [15]

Figure 3: Generalized version of DBSCAN algorithm

####  IV-C5 OPTICS Clustering

Optics clustering is also a density based clustering algorithm, but does not
require a minimum amount of points or a distance threshold to function.
Instead it requires a reach-ability distance. This creates a reach-ability
plot to determine what points can be reached from each other. The results of
this are another way to showcase how dense the distribution of points in the
dataset are.

Step 1: Mark every point of the dataset as ’unclustered’. Corresponding to
each point, mark both core distances and reachability distances as
’undefined’. Clusters = 1. Step 2: Pick any point $P\in X$ (the dataset) and
evaluate $N_{\epsilon}(P)$ ($\epsilon$ Neighborhood of P). Step 2.1: Compare
core distance of P only if $|N_{\epsilon}(P)|>\text{MinPts}$. Step 2.2: Assign
values of cluster to P once core distance is computed. Compute reachability
distance of every point in $N_{\epsilon}(P)$. Step 2.2.1: If they are
undefined, replace undefined with computed reachability distance. Step 2.2.2:
If a reachability distance exists for that point, replace it with the newly
computed reachability distance only if new reachability distance $<$ old
reachability distance. Step 3: We consider every unclustered element in
$N_{\epsilon}(P)$ and repeat Step 2. Step 4: When all elements of
$N_{\epsilon}(P)$ are clustered, along with the neighborhood of each point of
$N_{\epsilon}(P)$ [Step 3], we do the following: Step 4.1: $P$ = unclustered
point of $X$. Step 4.2: Cluster = Cluster + 1. Step 4.3: Repeat Step 2 to Step
3. We will keep on repeating the steps until the entire dataset is
clustered.[14]

Figure 4: Generalized version of OPTICS algorithm

####  IV-C6 Hierarchical Clustering

Hierarchical clustering builds a hierarchy of clusters, where the
agglomerative clustering method was chosen. This functions by selecting a
single data point as a single cluster and then merges pairs of clusters until
only one remains. Agglomerative clustering uses a tree-like structure called a
dendrogram, which is then cut to determine the optimal number of clusters at
different levels. The advantage to hierarchical clustering is that it does not
require the number of clusters to be specified in advance, where the data does
not need to naturally fall into a specific number of clusters to produce a
high quality result.

Step 1: Each data point is its own cluster. For N data points, we have N
clusters. Step 2: Find the inter-cluster distance between every pair of
clusters. Step 3: Join the two clusters having the lowest inter-cluster
distance. Step 4: Repeat Step 2 until either: Step 4.1: A set point or
threshold is reached. Step 4.2: No more clustering can be done.

Figure 5: Generalized version of Agglomerative Hierarchical Clustering
algorithm

###  IV-D Predictive Analysis

To predict the safety risks of communities, we constructed multiple linear
regression and random forest regression models.

####  IV-D1 Data Splitting and Feature Selection

We first used the chi-square test to select variables significantly correlated
with the dependent variables (crime, security incidents, traffic accidents).
Then, we randomly split the data into training set (80%) and testing set (20%)
for model training and evaluation.

####  IV-D2 Multiple Linear Regression

We constructed multiple linear regression models using the Sklearn library,
with the number of crimes, number of security incidents, and number of traffic
accidents as dependent variables and the selected significantly correlated
indicators as independent variables. We fitted the models on the training set
and evaluated them on the testing set using mean squared error and coefficient
of determination.

####  IV-D3 Random Forest Regression

Considering the possible nonlinear relationships between variables, we further
attempted random forest regression models. Random forest combines multiple
decision trees to effectively capture complex interactions between variables.
We implemented random forest regression using the Sklearn library and
optimized hyperparameters such as the number of trees and maximum depth
through grid search. We also calculated the feature importance of each
variable to assess its impact on prediction results.

####  IV-D4 Model Evaluation and Comparison

We evaluated the predictive performance of multiple linear regression and
random forest regression models on the testing set, using mean squared error
and coefficient of determination as evaluation metrics. We also plotted
scatter plots of actual values versus predicted values to visually demonstrate
the model fitting effects. Finally, we conducted comparative analysis of the
performance of the two types of models.

##  V Results

###  V-A Data Summarization

Fig. 6 reveals a varied landscape of crime in Calgary, with theft from
vehicles dominating as the most prevalent offense, followed by theft of
vehicles and break and enter incidents involving commercial properties.
Assault, both domestic and non-domestic, also remains a concerning issue, with
a notable number of reported incidents. Robbery, though relatively lower in
count, still poses a risk in public and commercial settings.

Figure 6: Total Number of Crimes for Each Category in Calgary

Fig. 7 reveals the top 10 traffic incident categories in Calgary, with ”2
vehicle incident” and ”Traffic Incident” leading. Issues like road blocking,
multi-vehicle incidents, and pedestrian involvement are also significant.

Figure 7: Top 10 Traffic Incident Categories in Calgary (2018-2023)

In Fig 8 and 9, we can easily see that Beltline and Downtown are the two
leading communities with highest total number of crimes and disorders in
Calgary. And the Forest Lawn community is also notable that comes next.

Figure 8: Top 10 Communities with the Highest Total Number of Crimes in
Calgary (2018-2023) Figure 9: Top 10 Communities with the Highest Total Number
of Disorders in Calgary (2018-2023)

Fig. 10 highlights the top 10 communities in Calgary with the highest number
of traffic incidents. Bridgeland/Riverside leads with 1,244 incidents,
followed closely by Beltline and Downtown Core with 1,153 and 1,103 incidents
respectively. Burns Industrial, Albert Park, and Manchester Industrial also
rank among the communities with notable traffic incident counts.

Figure 10: Top 10 Communities with Highest Number of Traffic Incidents
(2017-2024)

###  V-B Map Visualization

Fig. 11 shows the map visualization with multi-polygons colored by the number
of overall crimes in Calgary in each community. From a geospatial point of
view, we can see that large amount of Crimes happened in the centre areas of
Calgary, which are the Beltline and Downtown Core. We can also see in the
visualization that the communities in the Northeast sector are with slightly
more crimes than communities in other sectors.

Figure 11: Map with MultiPolygons Colored by number of Crimes in Calgary

Fig. 12 shows the map visualization with multi-polygons colored by the number
of overall disorders in Calgary in each community. Similar to fig. 11, we can
see that large amount of Crimes happened in the centre areas of Calgary, which
are the same Beltline and Downtown Core. And for the Northeast sector, the
number of disorders are also slights higher than other sectors but not as
obvious as previous map visualization for crimes.

Figure 12: Map with MultiPolygons Colored by number of Disorders in Calgary

Fig. 13 shows the map visualization with multi-polygons colored by the number
of overall traffic incidents in Calgary in each community. Comparing to crimes
and disorders, the traffic incidents also have a central tendency in Beltline,
Downtown Core with the additional Bridgeland-Riverside community. But the
distribution of traffic incidents is more dispersed around the centre areas of
Calgary. It is interesting that there seems to be more traffic incidents along
the Deerfoot Trail and Macleod Trail.

Figure 13: Map with MultiPolygons Colored by number of Traffic Incidents in
Calgary

###  V-C Temporal Analysis

Fig. 14 shows the Monthly Crime Trend Over Time by Category in Calgary. We can
see a slightly decreasing trend on the overall crimes and theft from vehicle
from year 2018 towards 2024.

Figure 14: Crime Trend Over Time by Category in Calgary

While in fig. 15, it is showing Disorder Trend Over Time in Calgary. Instead
of a decreasing trend, the disorder trend shows a periodic pattern every year
from year 2018 to 2024.

Figure 15: Disorder Trend Over Time in Calgary

And in fig. 16, it shows the Traffic Incident Trend Over Time in Calgary. It
is observable that there is a slightly increase trend for the number of
traffic incidents from year 2017 to 2024.

Figure 16: Traffic Incident Trend Over Time in Calgary

For fig 17, 18 and 19, they are showing the average Crimes, disorders or
traffic incidents per month in Calgary. We can see in fig. 17 that the average
number of crimes increases after April with the warmer weather and reach
average maximum in August. After that the average number of crimes decreases
with the temperature towards December.

Figure 17: Average Crime per Month in Calgary (2018-2023)

While in fig. 18, we can also observe an similar rising trend for the average
number of disorders, reaching the maximum in July.

Figure 18: Average Disorders per Month in Calgary (2018-2024)

And for fig. 19, we see a different trend in traffic incidents per month in
Calgary. It exhibits an increase trend starting in July towards December which
seems to be inversely proportion to the decreasing temperature.

Figure 19: Average Traffic Incidents per Month in Calgary

Fig. 20 shows the Number of Crimes Each Year by Category in Calgary. We can
see in this figure that, despite the slight differences in number each year,
the pattern on the distribution of crime categories are the same.

Figure 20: Number of Crimes Each Year by Category in Calgary

Fig. 21 illustrates the total number of disorders in Calgary from 2018 to
2024. Apart from year 2024 with incomplete data, disorder counts remained
relatively stable from 2018 to 2023, ranging from 83,701 to 94,514.

Figure 21: Total Number of Disorders in Calgary (2018-2024)

Fig 22 shows the top 5 Traffic Incident Categories along the years in Calgary.
We can see in the figure that the number of 2 vehicle incidents are decreasing
significantly while the blocking and general traffic incidents are increasing.
As the category column is only done by mapping key words or phrases from the
description column. The trends maybe a result of changing habits in writing
more detailed descriptions.

Figure 22: Top 5 Traffic Incident Categories along the year in Calgary

###  V-D Correlation Analysis Results

For the correlation analysis, as there are too many attributes in the
dataframe of community census, we need to use trial and error method and by
our knowledge to screen out attributes that could be related to crimes,
disorders and traffic incidents. And we have also tried to screen out
attributes that varying across different communities.

Fig 23 is the results of first trial in correlation analysis. It is a
correlation heatmap visualization showing the correlations between some
attributes in the community census. Despite of availability of correlation
results between different attributes in communities, they are not the interest
of this project. The interest of this project lies in the last 3 rows which
are the correlation of crimes, disorders and traffic incidents in related to
community attributes. We can see in the results that the number of crimes and
disorders are strongly correlated to the count of dwellings in a community,
and it is a much stronger correlation comparing to that of resident counts in
a community. Additionally, we can also see that crimes and disorders are
strongly correlated to the number of apartments and other apartment related
attributes. It indicates that we could probably anticipate more crimes and
disorders in a community if there are more apartments in a community or more
residents living in an apartment. Between crimes and disorders, they are
almost perfectly correlated to each other. While for traffic incidents, there
are no obvious correlations to any of the community attributes and it is
expected. It is interesting that the number of traffic incidents are
relatively correlated to the number of crimes and disorders in a community.

Figure 23: Correlation Heatmap (Community Census)

For fig. 24, we were trying to look into the how the number of preschool
children and how their family support the school systems in Calgary correlated
to the number of crimes, disorders and traffic incidents in a community apart
from other attributes that we discussed in fig. 18. We see in the results that
the crimes and disorders are not correlated to the number of preschool
children, but they showed slight correlation to the number of dwellings that
support public school system and both the public and separated school system.
It is interesting that the crimes and disorders are strongly correlated to the
number of dwellings with unknown support of school system or unable to
determine. It might hint that the more the number of families that do not care
about the school systems or not to answer such question in the census, the
more number of crimes and disorders could be anticipated in a community. And
for traffic incidents, the results matched the expectation that it would not
be correlated to the number of preschool children or what school systems
supported by the dwellings.

Figure 24: Correlation Heatmap (Community Children and Schools)

For fig. 25, it shows the correlation between crimes, disorders and traffic
incidents with the number of street light, their total wattage and the number
of trees in a community. The number of crimes, disorders and traffic incidents
show weak correlation to the total wattage of street lights in a community and
no correlation to the number of trees. Such weak correlation may be the
results of external correlation to some other attributes, such as the number
of apartments or dwellings in a community.

Figure 25: Correlation Heatmap (Lights and Trees)

Fig 26 shows the correlation between crimes, disorders and traffic incidents
with the number of pets, cats and dogs. The correlations between the target
interests and the pet attributes are weak such that we cannot derive any
insights from the results. It is expected that the pet attributes in a
community should not be correlated to crimes, disorder and traffic incidents,
but we just want to see if the results are not as expected.

Figure 26: Correlation Heatmap (Pets)

###  V-E Regression Results

For the regressions, we were not trying to build any accurate models. Instead,
we leveraged the linear and random forest regressors to determine the feature
importance of crimes, disorders, and traffic incidents. We fed the regressors
with strongly correlated attributes from previous correlation results. For
crimes and disorders, the regressors considered the number of dwellings with
unknown school support dominates the regression, which are 51% and 49%
respectively, followed by the number of persons living in an apartment, which
are 23% and 28% respectively. And for traffic incidents, the number of crimes
(37%) and disorders (25%) in a community dominates the regression than other
attributes.

###  V-F Clustering Results

It should be noted that clustering algorithms were only ran on the datasets
that contained latitude and longitude coordinates when acquired. For the
datasets where coordinates had to be calculated, clustering was not done as no
meaningful results could be acquired, and clusters were non-existent.

####  V-F1 K-Means

We ran the K-Means clustering algorithm on six of the datasets used. The two
datasets that did not receive clustering was the census data, and the
community disorder data. Clustering was ran on the crime data for K-means, but
it was quickly realized that no meaningful clusters would be derived since the
longitude and latitude was calculated based on the community centroids.

Figure 27: Silhouette Score Graph

To determine the optimal number of cluster for each dataset, silhouette scores
were calculated and the cluster number with that score was assigned when the
algorithm was re-ran with the optimal parameters.

Figure 28: K-Means Clustering Results. Top row: Traffic Camera, Traffic Incident; Middle row: Pets, Crime; Last row: Trees, Lumens DataFrame | Max Silhouette Score | Number of Clusters
---|---|---
Lumens | 0.4218 | 3
Trees | 0.4591 | 12
Traffic Incidents | 0.3802 | 16
Crime | 0.3941 | 3
Pets | 0.3813 | 3
Traffic Cameras | 0.4398 | 6
TABLE I: K-Means Results

Due to time constraints, the only hyper-parameter that was adjusted for
K-Means was the number of clusters, the other parameters were assumed to be 5
iterations, a random state of 0 and then the algorithm was only ran on one
centroid seed. These decisions were made to speed up computation time and
because the data showcased poor clustering results during the initial setup
phase.

####  V-F2 CLARANS Clustering

After the K-Means results were computer, some small changes were made to the
way clustering was done in order to reduce computational time. The major
change was that the crime dataset and traffic camera dataset would no longer
have clustering algorithms ran on them. The reason for this was discussed
above, but to re-iterate is that no meaningful clusters would be derived from
these datasets due to the nature of the latitude and longitude values within
them.

Figure 29: CLARANS Clustering Results. Clockwise from top-right: Lumens,
Trees, Pets, Traffic Incidents

The results of the CLARANS clustering algorithm are of a higher quality than
K-Means, but still not great overall. The only dataset that has what would be
considered good clustering results is the dataframe containing all of the
public trees in the City of Calgary. This can be seen in the top right map of
Figure 30, where there are some distinct clusters to be found in the map.
Otherwise, none of the dataframes have a high silhouette score indicating that
there is not much clustering to be found in the datasets - alike K-Means.

DataFrame | Silhouette Score | Clusters | Local Minima | Neighbours
---|---|---|---|---
Lumens | 0.5552 | 15 | 6 | 6
Trees | 0.8097 | 11 | 9 | 3
Traffic Incidents | 0.4027 | 12 | 10 | 9
Pets | 0.3886 | 10 | 9 | 5
TABLE II: CLARANS Results

####  V-F3 DBSCAN Clustering

DBSCAN clustering is by far the worst algorithm that is implemented on the
datasets, this is because for all intents and purposes no matter the dataset,
there is only one cluster to be found. This indicates that all of the data is
in close spatial proximity to each other, which is this true, but it also
means that it is impossible to make any insights from clustering through
DBSCAN.

Figure 30: DBSCAN Clustering Results. Top row: Lumens, Trees; Middle row:
Traffic incidents, Pets; Bottom row: Traffic cameras

Looking at Table 3, the Pets dataframe has a very high silhouette score, but
the EPS is so low it makes the entire dataframe into one cluster, so the high
silhouette score is more or less negated by the fact that no clustering
analysis can be done.

DataFrame | Max Silhouette Score | eps | min_samples
---|---|---|---
Lumens | 0.4161 | 0.006 | 2
Trees | 0.5680 | 0.009 | 2
Traffic Incidents | 0.3739 | 0.030 | 2
Pets | 0.9713 | 0.0001 | 2
Traffic Cameras | 0.3815 | 0.070 | 18
TABLE III: DBSCAN Results

####  V-F4 Hierarchical Clustering

Much alike the other algorithms, hierarchical clustering does not produce very
high silhouette scores, nor very good results. Granted, Hierarchical
clustering at least produces distinct clusters for all the tested dataframes,
but not much meaningful information can be extracted from them. Once again
further proving that clustering, no matter the method does not work well on
the selected datasets.

Figure 31: Hierarchical Clustering Results. Clockwise from top left: Lumens, Trees, Traffic Incidents, Pets DataFrame | Linkage | Number of Clusters | Silhouette Score
---|---|---|---
Lumens | ward | 3 | 0.4500
Trees | ward | 9 | 0.4379
Traffic Incidents | average | 14 | 0.3690
Pets | complete | 3 | 0.3721
TABLE IV: Hierarchical Clustering Results

####  V-F5 CLIQUE Clustering

Figure 32: Clique Clustering Results. Clockwise from top left: Lumens, Trees, Pets, Traffic Incidents DataFrame | Silhouette Score | Interval | Threshold
---|---|---|---
Lumens | 0.1220 | 18 | 0
Trees | 0.1220 | 18 | 0
Traffic Incidents | 0.4045 | 14 | 0
Pets | 0.3448 | 10 | 0
TABLE V: Clique Clustering Results

Overall, Clique clustering does not perform well in clustering the data. It
can be seen in all the images that one of the clusters dominates the majority
of the points in the dataframe. This makes deriving any results from the
figure extremely challenging as the Clique algorithm is indicating that there
is one major cluster in each dataset with a couple smaller peripheral
clusters. This is quite similar to DBSCAN, which also produced very poor
results.

####  V-F6 OPTICS Clustering

Figure 33: Optics Clustering Results. Clockwise from top left: Trees, Lumens, Pets, Traffic Incidents DataFrame | Silhouette Score | Radius | Neighbours
---|---|---|---
Lumens | -0.0990 | 0.01 | 8
Trees | 0.1995 | 0.01 | 8
Traffic Incidents | -0.3812 | 0.01 | 8
Pets | 0.3095 | 0.01 | 8
TABLE VI: Optics Clustering Results

Optics clustering produces extremely confusing results, with the Lumens
dataset, it suggests that there may be clusters of streetlights throughout the
city. This is not supported by other clustering algorithms but is interesting
nonetheless. It also suggests that there are clusters of trees throughout the
city, which is again not overly supported by the other algorithms. Then the
next two results are not sufficient for any further analysis, where the
clusters are either spanning giant portions of the city or are confined to
individual points. Two of the silhouette scores are also in the negative,
which indicates that hyper-parameters that are being used and tested. Due to
time constraints, there was not time to test further hyper-parameters to
confirm this theory.

##  VI Discussion and Future Work

###  VI-A Key Findings

This study utilized data analysis and data mining techniques to delve into the
crucial factors influencing community safety in the city of Calgary.

Through the exploratory data analysis, we revealed patterns, insights and
trends in geospatial, categorical and temporal perspectives.

While for correlation analysis, we found significant correlations between
crime rates, disorder incidents, traffic accidents, and several community
attributes, including population, housing types, streetlight quantity, and
tree quantity. It revealed the intrinsic connections between different
community attributes and the 3 main concerns. For instance, the population
related attributes demonstrated positive correlations with crimes and
disorders, while the apartment related attributes exhibited strong positive
correlations with crimes and disorders. This implies that the housing
structure may be primary factors influencing community crime. On the other
hand, crimes and disorders are strongly correlated to the number of dwellings
with unknown support of the school system or unable to determine. It implies
that, in a community, the more families not caring about the education
systems, there could be potentially more crimes and disorders.

And by regression analysis, we tried to find out which attribute contribute
mostly on the crimes, disorders and traffic incidents. The results revealed
that the number of families that don’t care about the education system is
contributing a large part in regressing the crimes and disorders. It implies
that how people care about the education system in Calgary or the education
system itself could be a key factor in crimes and disorders of the city. For
traffic incidents, it is as expected the same as the results of correlation
analysis, which is depending on the crimes and disorders instead of attributes
in a community.

We have also tried on clustering data mining technique. Overall, clustering
results were very poor across the board. K-Means overall produced the best
results out of all the algorithms, but even then the highest silhouette score
was only 0.4, which is not an optimal result. As all clustering algorithms do
a poor job at producing distinct cluster across all the datasets, the overall
indication is that the data is not overtly clustered or the hyper-parameters
are not correctly optimized. OPTICS algorithm showed an interesting
characteristic where the silhouette score stayed constant over different set
of hyperparameters; which can suggest that data is very difficult to cluster,
or there is an insufficient variation in hyperparameter, or our algorithm has
reached a local optimization plane and huge shift in the hyperparameter is
needed to get out of it. Most of the clustering gave us a negative silhouette
score. This happens when the mean distance between a sample and all other
points in the same cluster is greater than the mean distance between that
sample and all other points in the next nearest cluster, meaning that the
clustering algorithm has assigned a data point to the wrong cluster, as it is
more similar to points in another cluster than to points in its own cluster.
This further indicates that the clusters are overlapping or poorly separated.

The data cleaning process also has a flaw when it comes to producing
clustering results. For the datasets, such as crime, that did not have a
latitude and longitude originating from the dataset, are unable to produce
meaningful clustering. This is because the same community centroid coordinates
were provided for every entry that was located in that community. Causing
there to be not enough data points for there to be any meaningful clustering
results. This essentially rendered three of the seven datasets for Calgary to
be unusable for clustering algorithms. Another issue that arose is that from
the selected parameters is that a few number of clusters were found to be
optimal, making it incredibly challenging to find any significant clusters
when each cluster is covering a large portion of the city.

###  VI-B Innovations

The innovations of this study lie in: (1) integrating multiple heterogeneous
data sources including streetlights, trees, crime, and traffic to depict
community safety from multidimensional perspectives; (2) introducing advanced
clustering algorithms and machine learning models to reveal the distribution
patterns and influencing mechanisms of safety issues from both spatial and
attribute perspectives; (3) applying techniques such as feature importance
analysis to interpret the correlation analysis, providing actionable
intelligence for community safety governance.

###  VI-C Limitations and Future Directions

Due to time and data availability constraints, this study only covered limited
community indicators and data within a short-term timeframe. Future research
could collect more comprehensive data and conduct long-term spatio-temporal
and Trajectory analyses. Additionally, the causes of urban safety issues are
complex and diverse, making it difficult to elucidate the causal relationships
and mechanisms between various factors solely from a data perspective.
Subsequent research could integrate qualitative methods such as expert
interviews and case studies to explore the socioeconomic, institutional, and
cultural factors influencing community safety.

While our study focused on Calgary, the analysis framework and technical
roadmap can be generalized to other cities. Conducting comparative studies
across multiple cities would help discover common patterns, facilitate
knowledge exchange, and contribute wisdom to building safer and more inclusive
urban environments.

##  VII Conclusion

In conclusion, this study utilized data mining techniques to analyze key
factors affecting community safety in Calgary from multiple perspectives,
revealing spatial disparities in safety levels and establishing effective
predictive models. These findings not only fill the gap in quantitative urban
research but also provide new scientific evidence to urban managers and
policymakers, supporting fine-grained community safety governance. As we move
towards ”smart cities,” data mining undoubtedly will play a crucial role. We
look forward to more researchers engaging in this field, leveraging the power
of data to guide the construction of safer cities.

## References

  * [1] Hartigan J A, Wong M A. Algorithm AS 136: A k-means clustering algorithm[J]. Journal of the royal statistical society. series c (applied statistics), 1979, 28(1): 100-108.
  * [2] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman and A. Y. Wu, ”An efficient k-means clustering algorithm: analysis and implementation,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 7, pp. 881-892, July 2002.
  * [3] Ng R T, Han J. CLARANS: A method for clustering objects for spatial data mining[J]. IEEE transactions on knowledge and data engineering, 2002, 14(5): 1003-1016.
  * [4] Schubert E, Sander J, Ester M, et al. DBSCAN revisited, revisited: why and how you should (still) use DBSCAN[J]. ACM Transactions on Database Systems (TODS), 2017, 42(3): 1-21.
  * [5] Ankerst M, Breunig M M, Kriegel H P, et al. OPTICS: Ordering points to identify the clustering structure[J]. ACM Sigmod record, 1999, 28(2): 49-60.
  * [6] Liang K Y, Zeger S L. Regression analysis for correlated data[J]. Annual review of public health, 1993, 14(1): 43-68.
  * [7] Dong X L, Srivastava D. Big data integration[C]//2013 IEEE 29th international conference on data engineering (ICDE). IEEE, 2013: 1245-1248.
  * [8] Ferreira J, João P, Martins J. GIS for crime analysis: Geography for predictive models[J]. Electronic Journal of Information Systems Evaluation, 2012, 15(1): pp36 49-pp36 49.
  * [9] Zhao X, Tang J. Crime in urban areas: A data mining perspective[J]. Acm Sigkdd Explorations Newsletter, 2018, 20(1): 1-12.
  * [10] Chen H, Chung W, Xu J J, et al. Crime data mining: a general framework and some examples[J]. computer, 2004, 37(4): 50-56.
  * [11] Bernasco W, Elffers H. Statistical analysis of spatial crime data[J]. Handbook of quantitative criminology, 2010: 699-724.
  * [12] Anselin L, Cohen J, Cook D, et al. Spatial analyses of crime[J]. Criminal justice, 2000, 4(2): 213-262.
  * [13] Hand D J. Principles of data mining[J]. Drug safety, 2007, 30: 621-622.
  * [14] DarkProgrammerPB. (2019, December 26). OPTICS clustering Algorithm (from scratch). Medium. https://medium.com/@darkprogrammerpb/optics-clustering-algorithm-from-scratch-8d66960e238
  * [15] Hurra, T. (2023, April 11). DBSCAN — Make density-based clusters by hand. Medium. https://towardsdatascience.com/dbscan-make-density-based-clusters-by-hand-2689dc335120
  * [16] Ng, R., & Han, J. (2002). CLARANS: A method for clustering objects for spatial data mining. Knowledge and Data Engineering, IEEE Transactions On, 14, 1003–1016. https://doi.org/10.1109/TKDE.2002.1033770
  * [17] Oyelade, J., Oladipupo, O., & Obagbuwa, I. (2010). Application of k Means Clustering algorithm for prediction of Students Academic Performance. International Journal of Computer Science and Information Security, 7.
  * [18] Neethu C V & Subu Surendran. (2013). Review of Spatial Clustering Methods. International Journal of Information Technology Infrastructure, 2(3), 15–24. http://warse.org/pdfs/2013/ijiti01232013.pdf


# A Review on Semi-Supervised Relation Extraction

Yusen Lin
University of Maryland
<EMAIL_ADDRESS>

###### Abstract

Relation extraction (RE) plays an important role in extracting knowledge from
unstructured text but requires a large amount of labeled corpus. To reduce the
expensive annotation efforts, semi-supervised learning aims to leverage both
labeled and unlabeled data. In this paper, we review and compare three typical
methods in semi-supervised RE with deep learning or meta-learning: self-
ensembling, which forces consistent under perturbations but may confront
insufficient supervision; self-training, which iteratively generates pseudo
labels and retrain itself with the enlarged labeled set; dual learning, which
leverages a primal task and a dual task to give mutual feedback. Mean-teacher
[Tarvainen and Valpola, 2017], LST [Li et al., 2019], and DualRE [Lin et al.,
2019] are elaborated as the representatives to alleviate the weakness of these
three methods, respectively.

##  1 Introduction

Relation extraction (RE) refers to the automatic identification of the
relations given the entity mentions. For example, given ”Steve Jobs is the
founder of Apple”, the ”found_by” relation can be extracted between the
entities ”Apple” and ”Steve Jobs”. RE is essential in many downstream
applications like knowledge graph construction and question answering and
inference. However, it typically requires a massive labeled corpus, especially
for domain-specific RE.

To reduce labeling effort, it is significant to develop techniques like active
learning, distance supervision, semi-supervised learning, unsupervised
learning, in-context learning, and etc. Active learning reduces the labeling
cost by selecting the most uncertain samples for the annotator to annotate,
but still requires human-in-the-loop effort; distance supervision exploits an
external knowledge base; semi-supervised learning leverages both labeled and
unlabeled data; unsupervised learning relies on only unlabeled data but so far
needs further improvement; in-context learning in GPT-3 [Floridi and
Chiriatti, 2020] learns the knowledge during inference, but more progress in
research is still needed. This paper focuses on applying semi-supervised
learning on RE tasks through deep learning and meta-learning.

Three recent approaches, including self-ensembling, self-training, and dual
training, are mainly covered. Their principles and differences are shown in
figure 1, where mean-teacher [Tarvainen and Valpola, 2017] and DualRE [Lin et
al., 2019] are chosen as the examples for self-ensembling and dual learning,
respectively. Self-ensembling assumes the model remains consistent under
perturbations on the model parameters or the input data. However, with limited
labeled data, it is likely to encounter insufficient supervision because no
additional training data is introduced. In contrast, self-training predicts
pseudo labels and retrains the model iteratively with the continuously
enlarged labeled set. Despite avoiding insufficient supervision, it inevitably
suffers from a gradual drift due to biased predictions and accumulated errors.
To alleviate both issues, dual learning forms a close loop between a primal
task and a dual task to obtain mutual feedback signals and boost the entire
learning process. For RE, the duality occurs on retrieving mentions given a
specific relation and predicting relations given a specific mention.

This paper is organized as follows: Section 2 introduces self-ensembling and
its three advanced approaches; Section 3 talks about the pros and cons of
self-training and one recent way, LST [Li et al., 2019], to overcome the
gradual drift by meta-transfer-learning; Section 4 discusses the difference
between dual learning in RE and the above-mentioned methods, followed by the
description of DualRE [Lin et al., 2019]; Finally, Section 5 presents our
conclusions and future research directions.

Figure 1: Difference between self-training, self-ensembling and dual learning.

##  2 Self-ensembling

Self-ensembling comes from the general idea that better performance can be
yielded by ensembling multiple models. It extends the idea by ensembling
outputs from models under various regularization and input augmentation
conditions or on different training epochs. The concept behind it is to assume
no changes in the prediction of the unlabeled data even if small perturbations
exist on the model parameters or on the data.

In this article, we describe three advanced implementations of self-
ensembling, including $\Pi$-model, temporal ensembling [Laine and Aila, 2016],
and mean teachers [Tarvainen and Valpola, 2017].

###  2.1 $\Pi$-Model

Figure 2 demonstrates the idea of $\Pi$-model: given the same input with
various dropout conditions, $\Pi$-model imposes consistent predictions between
two realizations. Technically, for each training sample $x_{i}$ , where $i$
stands for the sample index, the network would predict twice, leading to
output vectors $z_{i}$ and $\tilde{z_{i}}$ . The loss function is composed of
supervised and unsupervised loss terms. The former is a standard cross-entropy
loss, only evaluated on labeled data, and $z_{i}$ is fed to it; the latter
takes the mean square loss between $z_{i}$ and $\tilde{z_{i}}$ and it is
evaluated on all data including the unlabeled ones. Besides, the mean square
loss is multiplied by a time-varying weighting function $w(t)$. The weighting
function $w(t)$ starts from 0, and then slowly ramps up along the Gaussian
curve after training a number of epochs. The final loss function is the sum of
these two loss terms.

Compared to traditional self-ensembling methods, which only force the final
classification to be consistent, it directly penalizes the network by
comparing the difference between two output vectors $z_{i}$ and
$\tilde{z_{i}}$ given the same input $x_{i}$ , imposing a much stronger
constraint. However, the training curve is readily jitter since the
$\tilde{z_{i}}$ is calculated based on a single training step. Meanwhile, it
would consume 2x training time due to evaluation twice per step.

###  2.2 Temporal Ensembling

The difference between $\Pi$-model and temporal ensembling is shown in figure
2. To overcome the weakness of $\Pi$-model, temporal ensembling leverages the
historical predictions. Instead of evaluating twice, it maintains an
exponential moving average (EMA) for the previous prediction as
$\tilde{z_{i}}$, reducing the noise and avoiding inference twice.

Due to dropout regularization and model learning, the output vector $z_{i}$
varies every training epoch. To aggregate these historical predictions with a
larger weight lying on the recent epochs, a matrix Z is provided and is
updated through a momentum method. Every training epoch, the output vector
$z_{i}$ is stored into $Z$ by $Z_{i}=\alpha Z_{i}+(1-\alpha)z_{i}$. The
$\alpha$ is the momentum term that 5 determines the weights of the recent
information. Compared with $\Pi$-model, the target vector $\tilde{z_{i}}$ is
replaced with the $Z_{i}$ in this method. However, the $Z_{i}$ needs to divide
by a factor $1-\alpha^{t}$ for correction of the startup bias before being
assigned to $\tilde{z_{i}}$, where t is the epoch index.

With the temporal design of the target vectors $\tilde{z_{i}}$, its training
is much more efficient than the training of $\Pi$-model. Most importantly, the
temporal accumulation of Z would make $\tilde{z_{i}}$ more consistent, less
jitter, and less noisy, compared to being generated every step in $\Pi$-model,
which leads to better performance in the empirical experiments of [Laine and
Aila, 2016]. As for the weakness, it may requires a relatively large memory
due to the matrix Z, especially if given a large dataset.

Figure 2: Difference between $\Pi$-model and Temporal ensembling [Laine and
Aila, 2016].

###  2.3 Mean Teachers

Compared to the EMA on historical prediction in temporal ensembling, mean
teacher, whose principle is shown in the self-ensembling part of figure 1,
applies the EMA on model weights. It fastens the pace of aggregating learned
information, instead of only updating the target vector $\tilde{z_{i}}$ once
per epoch. Without the limits of the matrix $Z$ in temporal ensembling, it
satisfies a larger dataset and works well with online learning. Moreover, the
experiments in [Tarvainen and Valpola, 2017] prove that it could produce
better performance and require less training time.

Mean teacher is composed of a student and a teacher model. The student model
shares a common role with the models of $\Pi$-model and temporal ensembling,
learned through a classification loss with labeled data and a consistency loss
with all data. One core difference is that the target vector $\tilde{z_{i}}$
is predicted by the teacher model instead of the student one. Since [Polyak
and Juditsky, 1992] proposed averaging the model parameters over the training
steps tends to predict more accurately, the teacher model shares the same
structure with the student one and simply takes the EMA of the student model
weights after every training step, without any learning.

##  3 Self-training

Self-training is the process of iteratively retraining the model with labeled
and pseudo-label data for improvement. The pseudo-label set is enlarged
continuously by high-confidence predictions of the model over the training. It
solves the insufficient-supervision limits of self-ensembling, resulting in,
usually, its outperforming self-ensembling in empirical studies, e.g., [Li et
al., 2019], especially in the case with scarce labeled data. However, they may
work in a complementary way.

Since the pseudo labels come from the model predictions, which could be
biased, most existing self-training methods inevitably bring the noise to the
labeled set. These cumulated errors may finally hurt the model performance,
which is called ’semantic drift’. To alleviate semantic drift, a recently
proposed method, LST [Li et al., 2019], leverages meta-transfer-learning [Sun
et al., 2019] to cherry-pick the pseudo labels meanwhile fine-tunes the model
with only the labeled set after each training step.

Figure 3: The computing flow of LST [Li et al., 2019].

###  3.1 Learning to Self-train (LST)

The computing flow of LST can be seen in figure 3, which consists of pseudo
labeling, cherry-picking, iterative retraining and fine-tuning model, and
meta-optimizing. The model is first pre-trained on a support set $S$ and then
pseudo-labels the unlabeled samples. Following cherry-picking the pseudo
labels by hard selection and soft weighting, the model is retrained on the
support set $S$ and the picked labeled set $R^{p}$ and then fine-tuned on only
the support set $S$. The final step is testing on a query set $Q$, acting as a
validation loss for the meta-learning optimization process of LST.

####  3.1.1 Pseudo-labeling

Like every common self-training method, the first step is to pre-train a
classifier $\theta$, and then predict the pseudo labels $Y^{R}$ for the
unlabeled set $R$ with the classifier $\theta$.

Theoretically, any model is applicable for $\theta$. Meta-transfer-learning
[Sun et al., 2019] is applied in [Li et al., 2019], which includes the inner
loop and the outer loop. The former is to train $\theta$ for a specific task
with $S$ , while the latter is to scale and shift the initialization weights
of the pre-trained network $\theta^{\prime}$ by meta-learning for quick fine-
tuning. $R$ is fed into $\theta$ for getting $Y^{R}$ after fine-tuning.

####  3.1.2 Cherry-picking

Cherry-picking is effective for reducing label noises and improving
performance, whose steps include the hard selection and soft weighting network
(SWN). Hard selection is to pick up top $Z$ samples per class based on the
confidence scores of $Y^{R}$. Given $C$ classes, there are $ZC$ samples in the
“cherries” $R^{p}$. The ”cherries” $R^{p}$ is then reweighted by a meta-
learned SWN before feeding to self-training. SWN tends to increase the weights
of better pseudo labels and decrease the worse ones. It first computes the
prototype feature of each class, which averages the features of the
corresponding class on $S$. Then, the sample feature is concatenated with it
as the input of SWN. Consequently, the weights w, output of SWN, somehow
reflect the distance between the pseudo labels and the prototype
representations of $C$ classes.

####  3.1.3 Iterative retraining and fine-tuning

Supposed $T$ steps exist in the inner loop, $\theta$ is first trained on both
$S$ and $R^{p}$ for $m$ steps ($\theta_{m}$), then is fine-tuned on only $S$
for $T-m$ steps ($\theta_{T}$). Before predicting $Y^{R}$ with the fine-tuned
$\theta_{T}$, the unlabeled set $R$ is split into multiple subsets, each
retraining occurs on a new subset $R^{\prime}$. $\theta_{T}$ then predicts on
$R^{\prime}$ to obtain more accurate pseudo labels $Y^{R}$ and enlarges
$R^{p}$ before the recursive self-training.

####  3.1.4 Meta optimizing

The inner loop is for learning $\theta$ in few steps with machine learning or
deep learning while the outer loop meta-optimizes for the ability to fast
adapt a pre-trained network $\theta^{\prime}$ to a new specific task. There
are multiple parameters to be meta-learned, including $\phi_{SWN}$ parameters
in SWN and $\phi_{\theta}$ parameters in $\theta$. The impact of $\phi_{SWN}$
only reflects on retraining through the generated soft weights while
$\phi_{\theta}$ affects the entire self-training process. To better serve the
effect of the parameters, $\phi_{SWN}$ and $\phi_{\theta}$ are updated in
different self-training stages. The losses of the retraining $\theta_{m}$ and
the fine-tuned $\theta_{T}$ are applied for meta-optimizing $\phi_{SWN}$ and
$\phi_{\theta}$ , respectively, with different meta-learning rates.

##  4 Dual learning

As mentioned in sections II and III, self-ensembling suffers from insufficient
supervision due to no extra pseudo labels generated, which limits the model
improvement, while biased predictions and accumulated errors inevitably make
self-training subject to the gradual drift. To alleviate these issues and
enhance the learning process, Dual learning leverages two related but
complementary tasks to optimize and regularize themselves. Specifically, for
relation extraction, recently, one of the state-of-the-art method, DualRE [Lin
et al., 2019], proposes the duality between retrieving sentences given a
certain relation and predicting the relation label given a specific sentence.

###  4.1 Dual Relation Extraction (DualRE)

Different from self-training that one model is trained to provide additional
pseudo-label data, one primal and dual modules, the prediction and retrieval
modules, exist in DualRE and are jointly optimized to enrich the training set
and enhance each other. The prediction module $P$ aims for relation extraction
by predicting relation labels given a sentence and aims to evaluate the
results from the retrieval module. The retrieval module $R$ ranks sentences
based on relevant scores given a certain relation label and outputs the top
ones. The retrieved sentences from the unlabeled corpus are then served as
pseudo-label data for the prediction module. The concept and the interaction
between two modules are shown in the dual learning of figure 1. Since both
modules provide pseudo labels, insufficient supervision is solved, while two
modules regulate each other during the joint learning process, leading to less
biased pseudo labels and alleviation of semantic drift. As for the objective
function, it consists of three terms, $O=O_{P}+O_{R}+O_{U}$, where $O_{P}$,
$O_{R}$, and $O_{U}$ are for the prediction module $P$, retrieval module $R$,
and unsupervised part, respectively.

####  4.1.1 Relation prediction module

Prediction module $P_{\theta}$, where $\theta$ is the parameters, mainly works
for predicting the relations given the mentions. An encoder is applied to
encode the mention pair and the corresponding context into a representation
vector $z$. Vector $z$ is then fed into a simple softmax classifier for
relation classification. For the encoder, it could be any feature extractor,
e.g., RNN-based, CNN-based, or Transformer-based. For the objective function,
$O_{P}=E_{(x,y)\in L}[logP_{\theta}(y|x)]$, cross-entropy is used given $x$ as
the mention pair and its context, $y$ as the relation label, and $L$ as the
labeled set.

####  4.1.2 Sentence retrieval module

Retrieval module $Q_{\phi}$ is for retrieving the most relevant mentions $x$
given a certain relation $y$, where $\phi$ is the parameters. In [Lin et al.,
2019], Learning-to-rank [Liu, 2009] is used to rank the relevance scores of
the mentions so that top mentions can be obtained. Learning-to-rank intends to
learn the joint distribution $Q_{\phi}(x,y)$ and its corresponding objective
function is $O_{R}=E_{(x,y)\in L}[logQ_{\phi}(x,y)]$. Since learning joint
distribution $Q_{\phi}(x,y)$ is intractable due to the high computation cost
of traversing all possible pairs of $(x,y)$ and $Q_{\phi}(x,y)$ is in
proportion to $Q_{\phi}(x,y)$ when given fixed probability of relation label
$Q(y)$, [Lin et al., 2019] learns $Q_{\phi}(x,y)$, instead. Pointwise and
pairwise approaches are available for learning-to-rank and empirical
experiments in [Lin et al., 2019] demonstrate the former one generally
performs better.

Pointwise approach: $Q_{\phi}(x,y)$ outputs the relevance scores between the
set of mentions ${x}$ and the relation label y for the retrieval module. By
taking the inner product between the encoded representation z from x and the
relation embedding $y_{e}$ from $y$ , followed by a sigmoid function,
$Q_{\phi}(x|y)=\sigma(z^{T}y_{e})$, it forces $Q_{\phi}(x|y)$ close to 1 when
$(x,y)$ are in the labeled set and close to 0 when $(x,y^{\prime})$ are not
the correct pairs. $E_{(x,y)\in L}[log\sigma(z^{T}y_{e})]+E_{(x,y^{\prime})\in
L}[log(1-\sigma(z^{T}y_{e}^{\prime}))]$ is the specific objective function,
where the former term maximizes the probabilities of the correct pairs whereas
the latter minimizes the probabilities of the incorrect pairs.

####  4.1.3 Interaction in the EM-based joint optimization process

Different from self-training, DualRE generates pseudo labels under the
cooperation of two modules. This collaboration helps reduce biased predictions
by regularizing the outputs of each other through majority voting.
Specifically, it takes the intersection instances as the final pseudo labels.
This process effectively alleviates both the insufficient supervision and the
semantic drift and improves the overall model performance. The objective
function of the unsupervised part is $O_{U}=E_{x\in U}[logQ_{\phi}(x)]\geq
E_{x\in U,y\sim P_{\theta}(y|x)}[log\frac{Q_{\phi}(x,y)}{P_{\theta}(y|x)}]$.
It is derived from the EM algorithm [Dempster et al., 1977] where $U$ is the
unlabeled data, $P_{\theta}$ is the prediction module, and $Q_{\phi}$ is the
retrieval module. The equal sign is available only if
$P_{\theta}(y|x)=Q_{\phi}(y|x)$, which may be achieved by taking the results
that two modules agree with. The overall objective function $O$ is optimized
with EM algorithm, alternatively updating the two modules by maximizing the
lower bound of $O_{U}$ (M step) and updating the prediction module
$P_{\theta}$ (E step).

In the E step, the prediction module $P_{\theta}$ is updated by fixing the
retrieval module $Q_{\phi}$ , which corresponds to minimizing the KL
divergence $KL(P_{\theta}(y|x)\|Q_{\phi}(y|x))$. Using the wake-sleep
algorithm [9], minimizing the reversed KL divergence
$KL(Q_{\phi}(y|x)\|P_{\theta}(y|x))$ obtains the same result
$P_{\theta}(y|x)=Q_{\phi}(y|x)$. For the M step, similar to the E step, the
retrieval module $Q_{\phi}$ is updated by fixing the prediction module
$P_{\theta}$. Each E and M steps train the modules with a shared version of
labeled and pseudo-label data to boost the overall model performance.

##  5 Conclusions and future research directions

Relation extraction is essential in information extraction from unstructured
text. However, it usually requires huge annotation efforts, especially for
domain-specific cases. This article aims to introduce three recent methods in
semi-supervised learning for RE, which include self-ensembling, self-training,
and dual learning. Self-ensembling forces consistency under perturbations but
may have the insufficient supervision issue; self-training recursively yields
the pseudo labels and retrains the model with the enlarged labeled set but may
suffer from gradual drift; dual learning leverages the duality of the
retrieval module and the prediction module to alleviate the above two
problems. Although these methods vary in props and cons, in fact, they could
be implemented in a complementary way. Besides, presently, considering the
language models like BERT [Devlin et al., 2018], T5 [Raffel et al., 2019],
GPT3 [Floridi and Chiriatti, 2020], and etc, have achieved many state-of-the-
art results in various applications, it is interesting to combine them into
semi-supervised learning in the future.

## References

  * [Dempster et al., 1977]  Arthur P Dempster, Nan M Laird, and Donald B Rubin.  1977\.  Maximum likelihood from incomplete data via the em algorithm.  Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1–22.
  * [Devlin et al., 2018]  Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  2018\.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805.
  * [Floridi and Chiriatti, 2020]  Luciano Floridi and Massimo Chiriatti.  2020\.  Gpt-3: Its nature, scope, limits, and consequences.  Minds and Machines, 30(4):681–694.
  * [Laine and Aila, 2016]  Samuli Laine and Timo Aila.  2016\.  Temporal ensembling for semi-supervised learning.  arXiv preprint arXiv:1610.02242.
  * [Li et al., 2019]  Xinzhe Li, Qianru Sun, Yaoyao Liu, Shibao Zheng, Qin Zhou, Tat-Seng Chua, and Bernt Schiele.  2019\.  Learning to self-train for semi-supervised few-shot classification.  arXiv preprint arXiv:1906.00562.
  * [Lin et al., 2019]  Hongtao Lin, Jun Yan, Meng Qu, and Xiang Ren.  2019\.  Learning dual retrieval module for semi-supervised relation extraction.  In The World Wide Web Conference, pages 1073–1083.
  * [Liu, 2009]  Tie-Yan Liu.  2009\.  Learning to rank for information retrieval.  Foundations and Trends in Information Retrieval, 3(3):225–331.
  * [Polyak and Juditsky, 1992]  Boris T Polyak and Anatoli B Juditsky.  1992\.  Acceleration of stochastic approximation by averaging.  SIAM journal on control and optimization, 30(4):838–855.
  * [Raffel et al., 2019]  Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  2019\.  Exploring the limits of transfer learning with a unified text-to-text transformer.  arXiv preprint arXiv:1910.10683.
  * [Sun et al., 2019]  Qianru Sun, Yaoyao Liu, Tat-Seng Chua, and Bernt Schiele.  2019\.  Meta-transfer learning for few-shot learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 403–412.
  * [Tarvainen and Valpola, 2017]  Antti Tarvainen and Harri Valpola.  2017\.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  arXiv preprint arXiv:1703.01780.