[orcid=0000-0001-7511-2910]

[1]

[cor1]Corresponding author.

# An Improved Approach for Estimating Social POI Boundaries With Textual
Attributes on Social Media

Cong Tran  Department of Computer Science and Engineering, Dankook University,
Yongin 16890, Republic of Korea  Dung D. Vu  Machine Learning R&D, Korbit AI,
Montreal QC H2T 2A3, Canada  Won-Yong Shin  Machine Intelligence & Data
Science Laboratory, Yonsei University, Seoul 03722  School of Mathematics and
Computing (Computational Science and Engineering), Yonsei University, Seoul
03722

###### Abstract

It has been insufficiently explored how to perform density-based clustering by
exploiting textual attributes on social media. In this paper, we aim at
discovering a social point-of-interest (POI) boundary, formed as a convex
polygon. More specifically, we present a new approach and algorithm, built
upon our earlier work on social POI boundary estimation (SoBEst). This SoBEst
approach takes into account both relevant and irrelevant records within a
geographic area, where relevant records contain a POI name or its variations
in their text field. Our study is motivated by the following empirical
observation: a fixed representative coordinate of each POI that SoBEst
basically assumes may be far away from the centroid of the estimated social
POI boundary for certain POIs. Thus, using SoBEst in such cases may possibly
result in unsatisfactory performance on the boundary estimation quality (BEQ),
which is expressed as a function of the $\mathcal{F}$-measure. To solve this
problem, we formulate a joint optimization problem of simultaneously finding
the radius of a circle and the POI’s representative coordinate $c$ by allowing
to update $c$. Subsequently, we design an iterative SoBEst (I-SoBEst)
algorithm, which enables us to achieve a higher degree of BEQ for some POIs.
The computational complexity of the proposed I-SoBEst algorithm is shown to
scale linearly with the number of records. We demonstrate the superiority of
our algorithm over competing clustering methods including the original SoBEst.

###### keywords:

Boundary estimation quality Geo-tagged record Representative coordinate Social
point-of-interest boundary Spatio–textual data.

##  1 Introduction

###  1.1 Background

With the pervasiveness of Global Positioning System (GPS)-enabled mobile
devices, services based on not only location-based social networks (LBSNs)
such as Foursquare [10] and Flickr [32] but also online social networks with
geo-tagging or check-in functionality such as Twitter [27, 40], Facebook [45],
and Instagram [17] have grown rapidly in recent years. These services provide
various platforms for hundreds of millions of users to share their location-
tagged media content objects such as photos, videos, musics, and texts. For
example, when users visit a point-of-interest (POI), they are likely to check
in, upload photos of their visit with annotations, or post geo-tagged textual
data via LBSNs [11, 16, 18, 38] to describe their individual idea, feeling, or
preference relevant to the POI. As a result, many textual postings have been
geo-tagged on social media. For example, there are currently more than 600
million tweets posted on Twitter per day,111www.internetlivestats.com. and
approximately $1\%$ of them are geo-tagged [34], corresponding to 6 million
geo-tagged tweets per day.

Given the availability of the location information from geo-tagged or check-in
records, there has been a steady interest in studying a variety of research
challenges on accurately identifying or recommending POIs using social media.
In particular, the problem of identifying POIs has a broad range of
applications including but not limited to geomarketing, event management,
urban planning, and location-based services. For example, POI identification
can be used in geomarketing, which is one of the most rapidly evolving trends
in marketing. As a marketing strategy of companies targeting promotion of a
shopping mall, flyers will be disseminated online hopefully only to the people
who come to visit the desired POI. Thus, company managers will not only be
aware of the explicit marketing zone but also reduce the marketing cost.

On the other hand, in general, an area-of-interest (AOI) [44, 25, 28, 30] has
been considered as either a single connected region or a union of disconnected
regions in which multiple neighboring geographic coordinates of POIs could be
found. Thus, we can interpret the AOI as a special region which possesses
significantly high popularity amongst the locals. While most studies have
focused on identifying a POI [23, 51], we focus on estimating an AOI due to
the robustness in reflecting interests of many users. To illustrate this
point, we would like to address that tourists’ interest often involves many
aspects of daily life, including sightseeing, dining, shopping, etc., which
cannot be covered by a single POI. Instead, an AOI that may contain various
POIs and their associated area (e.g., tourist attractions, popular venues, and
restaurants) often within a walking distance of each other would be ideal to
recommend to tourists.

###  1.2 Motivation and Main Contributions

In this paper, we would like to exploit textual attributes on social media in
more accurately discovering POI boundaries corresponding to AOIs. To this end,
by leveraging spatio–textual data on social media such as Twitter, we develop
our own approach and algorithm, built upon a preliminary version [47] of the
current work for effectively estimating a social POI boundary, SoBEst (which
was originally referred to as GeoSocialBound in [47]). Our study differs from
the most popular spatial clustering algorithm, so-called density-based spatial
clustering of application with noise (DBSCAN) [15], in the sense that DBSCAN
only exploits the set of geographic locations. For better understanding of our
study, we start by revisiting both the notion of social POI boundaries and the
SoBEst algorithm. A social POI boundary is defined as one cluster, which is
given by a convex polygon geographically formed by taking the convex hull of
geo-tagged records (e.g., geo-tagged tweets) that include a given textual
description such as a POI name within a circle to be optimized. In
geomarketing, the marketing zone is expected to cover all geo-tagged records
relevant to the desired POI with as little marketing cost as possible; thus,
it would be desirable to define the social POI boundary as a convex polygon
that is the smallest region enclosing all relevant records in terms of cost
efficiency as well as promotion effectiveness. Unlike most of existing spatial
clustering algorithms, we are interested in taking into account both relevant
and irrelevant records within a geographic area, where relevant records
contain a POI name or its variations in their text field. Intuitively, we
would expect the associated area to be neither too small nor too large. As two
scenarios, a small POI boundary would cover only an insignificant fraction of
relevant records while an unbounded region may contain many irrelevant
records. Given a POI name and its representative coordinate $c$, we aim to
obtain a geographic area of interest (i.e., a social POI boundary) as large as
possible, while maintaining a sufficiently high textual quality of the area,
which is computed from portions of both relevant and irrelevant records. For
example, suppose that there are two circles having the center $c$, indicated
by a green diamond, and radii $r_{1}$ and $r_{2}$ in Fig. 1, where
$r_{1}>r_{2}$. Red circles and black squares indicate relevant and irrelevant
records within the circle $(c,r_{i})$, respectively, for $i\in\\{1,2\\}$. In
the figure, it is seen that Circle 1 has a worse annotation quality since it
suffers from an overexpansion with a number of accompanying irrelevant geo-
tags near the boundary of the circle. In this case, to reduce the number of
irrelevant geo-tags, we need to decrease the radius of Circle 1, leading to an
increment of the quality. To balance this trade-off, we define a boundary
estimation quality (BEQ) as a function of the $\mathcal{F}$-measure [29],
denoted by $\mathcal{F}(c,r)$ for the radius $r$ of a circle to be found and
the POI’s representative coordinate $c$, where the $\mathcal{F}$-measure is a
popular measure of a test’s accuracy. From this measure, we expect to divide
the plane into two separate regions (i.e., an interior and an exterior) by
finding a sufficiently large circle containing a large number of relevant
records and a small number of irrelevant records. In addition, we observe that
the $\mathcal{F}$-measure tends to be hardly degraded up to a certain critical
point with respect to the radius $r$ from the initially given POI’s
representative coordinate $c^{(0)}$. Based on this observation, an
optimization problem in the sense of maximizing the BEQ including a coverage
term $(\frac{r}{\bar{r}})^{\alpha}$, denoted by
$\left(\frac{r}{\bar{r}}\right)^{\alpha}\mathcal{F}(c^{(0)},r)$, was
formulated in [47], where $\alpha\geq 0$ is the radius exponent, balancing
between different levels of geographic coverage, and $\bar{r}$ is a
normalization factor representing the maximum searching distance. To
effectively solve this problem, the computationally efficient SoBEst algorithm
was also presented in [47].

(a) Circle 1

(b) Circle 2

Figure 1: A sample dataset, where $r_{i}$ for $i\in\\{1,2\\}$ and $c$ indicate
the radius of a circle and the representative coordinate, respectively. Here,
red circles and black squares indicate relevant and irrelevant records,
respectively.

Although the approach in [47] is the first attempt to perform spatial
clustering using textual attributes on social media, we would like to raise
the following concern: a fixed representative coordinate of each POI that
SoBEst basically assumes may be far apart from the centroid of the estimated
social POI for centain POIs. In consequence, using SoBEst in such cases may
possibly result in unsatisfactory performance on the BEQ. We first empirically
confirm that there are indeed many such POIs. Then, to overcome this problem,
we introduce a joint optimization problem of simultaneously finding the radius
$r$ of a circle and the POI’s representative coordinate $c$. We also propose
an iterative SoBEst algorithm, dubbed I-SoBEst, by iteratively updating $r$
and $c$ for improving the estimation performance.

We empirically evaluate the performance of our I-SoBEst algorithm in terms of
$\left(\frac{r}{\bar{r}}\right)^{\alpha}\mathcal{F}(c,r)$ (i.e., BEQ) for
various radius exponents $\alpha$ and POIs. We verify the superiority of the
proposed approach over two baselines and three state-of-the-art density-based
clustering methods as well as the original SoBEst without updating $c$. In
this paper, we first compare our algorithm to a variant of the original DBSCAN
method, as a baseline, that does not inherently exploit the textual
information on social media, where the original DBSCAN in [15] is modified to
make it suitable for performance evaluation under our problem setting. Note
that, although there have been a variety of studies on designing state-of-the-
art DBSCAN algorithms [3, 6, 25, 28, 30] in diverse applications, they do not
reveal further improvement on the performance over our own variant of the
original DBSCAN in our setting since all of them were not developed based on
the textual attributes (i.e., relevant and irrelevant records). Our
experiments show that I-SoBEst significantly outperforms the modified DBSCAN
by up to an order of magnitude. We also compare our I-SoBEst algorithm to
another baseline method [20] and three state-of-the-art methods [46, 8, 49]
for discovering POI boundaries, and confirm the consistent superiority of
I-SoBEst for various environments. Moreover, via performance evaluation, we
identify the case where the gain of I-SoBEst over the original SoBEst without
updating the POI’s representative coordinate is promising. Our experiments
exhibit that the BEQ of I-SoBEst further improves SoBEst’s by up to 16.75%
depending on experimental settings. Finally, we analytically and numerically
show the computational complexity of I-SoBEst, which follows a linear scaling
with the number of geo-tags.

To the extent of our knowledge, this study subsuming our earlier work in [47]
is the first attempt to perform spatial clustering with high accuracy using
textual attributes on social media. The overall procedure of our I-SoBEst
algorithm including data acquisition and preprocessing steps is illustrated in
Fig. 2, where notations and detailed descriptions for each block are shown in
later sections.

Figure 2: The schematic overview of our I-SoBEst method.

###  1.3 Organization and Notations

The remainder of this paper is organized as follows. In Section 2, we review
the related work. Section 3 presents how to collect POIs and then how to
search relevant tweets for each POI. In Section 4, we present our joint
optimization problem for estimating social POI boundaries along with rigorous
definitions. Thereafter, we present the computationally efficient SoBEst
algorithm and its enhanced I-SoBEst algorithm in Section 5; followed by
empirical evaluation and computational complexity analysis in Section 6.
Finally, Section 7 summarizes the paper with some concluding remarks.

Table 1 summarizes the notations used throughout this paper. Some notations
will be more precisely defined in the following sections when we introduce our
problem formulation and algorithms.

Table 1: Summary of notations. Notation | Description
---|---
$c$ |  representative coordinate of a POI
$r$ |  radius of a circle
$\mathcal{F}(c,r)$ |  $\mathcal{F}$-measure for a given circle $(c,r)$
$r_{\texttt{cover}}$ |  approximate radius from a POI’s representative coordinate covering the geographic area of each POI
$r^{*}$ |  optimal radius of a circle
$\alpha$ |  radius exponent
$\eta$ |  target quality threshold
$\bar{r}$ |  searching distance
| $c^{(k)}$
---
updated representative coordinate of a POI after the $k^{\texttt{th}}$
iteration
| $\delta$
---
tolerance level of I-SoBEst
| $c^{*}$
---
finally updated representative coordinate of a POI
$\mathcal{D}(c,r)$ |  set of relevant records within a circle $(c,r)$
$\mathcal{D}_{\texttt{all}}(c,r)$ |  set of all geo-tagged records within a circle $(c,r)$
$\Delta r$ |  sampling interval in $(0,\bar{r}]$

##  2 Related Work

Our proposed algorithm is related to the following four broad fields of
research: AOI discovery, density-based spatial clustering, spatio–textual
similarity search, and clustering based on spatial and non-spatial attributes.

AOI discovery. The term AOI is also referred to as place-of-interest [33],
region-of-interest [43], or POI boundary [5, 46]. In a broad sense, the
research on AOI discovery can be categorized into the following two problems:
estimation of a small-scale AOI (i.e., a single POI boundary) and estimation
of large-scale AOIs (i.e., multiple POI boundaries).

First, the approaches to discovering an AOI on a small scale were studied in
[5, 20, 46], which lies in the same line as our work. In [5], geo-tagged
Flickr textual data, Wikipedia concepts, and links among them with a topical
similarity method were employed to discover a POI boundary. In [20], the
boundary of an AOI was estimated using kernel density estimation and support
vector machine (SVM) via geo-tagged Flickr photos. A two-phase algorithm for
estimating a POI boundary with linear scaling complexity in the number of
input records was proposed in [46].

Second, previous studies on discovery of large-scale AOIs usually result in a
list of areas containing multiple POIs [25, 28, 33, 43, 49, 26, 52]. In [25,
28], the authors presented a ranked list of attractive regions where many
tourism spots are located for recommendation to travellers. Areas in which
people tend to stay for a long time were discovered in [33]. In [43], both
public regions and personal regions were extracted by using check-in histories
on LBSNs. A technique that robustly identifies POIs’ boundaries based on the
local drastic changes of the data density was developed in [49]. In [26], an
end-to-end framework for discovering POIs/AOIs from temporal properties and
data attributes as well as geo-tagged photos was presented. In [52], AOIs were
discovered by fusing both sentimental attributes of locations and multi-
activity centers for each user.

Density-based spatial clustering. DBSCAN [15] has been known as one of the
most popular density-based spatial clustering algorithms [25, 28, 30] due to
the capability of indexing separated clusters, the robustness in detecting
outliers, and the ability to provide arbitrarily-shaped clusters. DBSCAN
algorithms find multiple clusters based on any source of location information
with reasonable computational complexity. As follow-up studies on DBSCAN,
numerous sophisticated algorithms have been developed as follows: a
generalized version of DBSCAN that differently measures the cardinality of
neighborhoods of a point was proposed in [39]; another DBSCAN algorithm that
generates clusters based on both spatial and temporal attributes was presented
in [3]; and hierarchical DBSCAN was introduced in [6] as an automated method
that measures the stability of clusters in a clustering hierarchy to select
proper input parameters of DBSCAN. Recently, several studies attempted to
reduce the computational complexity of DBSCAN algorithms by either employing
techniques such as bitmap indexing to support efficient neighbor grid queries
[4] or transforming the problem of identifying a core point to a k-nearest
neighbor (kNN) problem [9].

On the other hand, density peaks clustering (DPC) achieving competitive
performance in a non-iterative manner was recently developed in [37, 48, 50,
8] as an alternative to DBSCAN as it is based on the assumption that cluster
centers have higher density than their neighbors and are located sufficiently
far from other points with higher local density.

Spatio–textual similarity search. It is of importance to find spatially and
textually closest objects to query objects. To offer compelling solutions to
this problem, several algorithms [13, 12] were introduced. In particular, a
method to answer queries containing a location and a set of keywords was
presented in [13]. An index framework for processing top-$k$ query that takes
into account both spatial proximity and text relevancy was introduced in [12].
Although these algorithms study the spatio–textual distance between objects,
they are inherently different from our approach, which estimate a POI boundary
utilizing the textually relevant and irrelevant records on social media such
as Twitter.

Clustering based on spatial and non-spatial attributes. There have been recent
studies on the use of spatial and non-spatial attributes on social media to
improve the clustering performance in various applications. In [19], spectral
clustering was applied to identify clusters among gang members based on both
the observation of social interactions and the geographic locations of
individuals. By utilizing the geo-tagged textual data to find correlations
between textual descriptions (i.e., POI types) and locations, the problem of
discoverying AOIs grouped by categories was also studied in [44].

##  3 Data Acquisition and Processing

We describe how to collect POIs and Twitter data associated with their
locations. Thereafter, for each POI, we elaborate on our approach to search
for relevant tweets.

###  3.1 Collecting POIs

To obtain a set of POIs and their representive coordinates, we use an open
source database Geonames,222http://www.geonames.org. which has a great amount
of geographical information and concepts [1]. There are various feature
classes in the database such as spots, buildings, farms, roads, hills, rocks,
etc., but the following four representative categorized types are taken into
account along with four POIs: building (S.BLDG), stadium (S.STDM), museum
(S.MUS), and park (L.PRK). The four POI types are summarized in Table 2, where
POIs and their representative attributes in the table will be further
described in the next subsection.

Table 2: POI types and attributes of four POIs according to Geonames.

POI name |  Geonames category |  Representative coordinate $c^{(0)}=(c^{(0)}_{\textrm{lat}},c^{(0)}_{\textrm{lon}})$
---|---|---
Empire State Building |  S.BLDG |  ($40.74871^{o},-73.98597^{o}$)
Dodger Stadium |  S.STDM |  ($34.073611^{o},-118.24^{o}$)
Metropolitan Museum of Art |  S.MUS |  ($40.77891^{o},-73.96367^{o}$)
Busch Gardens |  L.PRK |  ($28.03363^{o},-82.41648^{o}$)

###  3.2 Collecting Twitter Data

We use Twitter Streaming Application Programming Interface (API) [22, 24, 31,
42], which has been widely used to collect data for topic modeling [22, 24],
network analysis [42], and statistical content analysis [31]. Streaming API
returns tweets matching a query provided by a Streaming API user. It was
reliably found that although the Twitter Streaming API only returns at most a
$1\%$ sample of all the tweets produced at a given moment, it returns an
almost complete set of geo-tagged tweets despite sampling [34].

Our dataset consists of 5,992,223 geo-tagged tweets recorded from 643,506
Twitter users from July 29, 2015 to August 29, 2015 (about one month) in the
US. Note that this short-term (one month) dataset is sufficient to estimate
social POI boundaries with high accuracy. We removed the content that was
automatically created by other services such as Tweetbot, TweetDeck, Twimight,
and so forth. We see that each tweet contains a number of entities that are
distinguished by their attributed field names. For data analysis, we adopt the
following three essential fields from the data of tweets:

  * •

_text_ : actual UTF-8 text of the status update;

  * •

_lat_ : latitude of the tweet’s location;

  * •

_lon_ : longitude of the tweet’s location.

As shown in Table 2, four POIs placed in the US are used for our analysis,
where a POI is selected for each Geonames category. Representative attributes
of the four POIs are summarized in Table 2. The third column of Table 2
represents the initial POI’s representative coordinate
$c^{(0)}=(c^{(0)}_{\textrm{lat}},c^{(0)}_{\textrm{lon}})$ provided by
Geonames, where $c^{(0)}_{\textrm{lat}}$ and $c^{(0)}_{\textrm{lon}}$ denote
the latitude and longitude measured in degrees, respectively.

###  3.3 Searching Relevant Tweets

Since users are able to tag a POI name (e.g., #buschgardens) or insert it
(e.g., Busch Gardens and Busch Park) in their tweets to describe their
interest in a POI, we can easily query all relevant tweets that contains the
POI name. On the other hand, a POI name may be misspelled or have other words
tacked on to it. Thus, we perform a keyword-based search by querying
semantically coherent but different words for a POI.333Note that brown
clustering can also be adopted to find semantically coherent variations of a
POI, even if it is not taken into account in our study. Relevant variations
for an annotation (i.e., a POI name) would include the hashtag followed by the
POI name, its abbreviated name, its synonyms (if any), etc. (refer to Table
3). Then, the dataset can be partitioned into two subsets of geo-tagged tweets
with and without the annotated POI names (refer to Table 4 in Section 6 for
detailed statistics of these two subsets for each POI).

Table 3: Search queries. POI name | Search queries
---|---
Empire State Building |  #empirestate, Empire State, Empirestate
Dodger Stadium |  #dodgerstadium, Dodger Stadium
Metropolitan Museum of Art |  #themet, #metropolitanmuseumofart, Metropolitan Museum of Art, The Met, Themet, Metropolitainmuseumofart
Busch Gardens |  #buschgardens, Buschgardens, Busch Gardens, Busch Park

##  4 Problem Description

In this section, we formulate our new optimization problem after formally
defining some important terms used for our analysis.

###  4.1 Definitions

We start by introducing three important definitions in analyzing the
estimation performance of social POI boundaries. As mentioned before, the
relevance of the data to a POI varies according to the geographic distance
between the POI’s representative coordinate and the locations where the data
are generated. The tweets posted in locations far away from the representative
coordinate of a POI are unlikely to have textual description for the POI.
Hence, it is remarkably important to formally define a social POI boundary and
to estimate it with high accuracy. Unlike density-based clustering algorithms
such as DBSCAN that find arbitrarily-shaped multiple clusters, to characterize
a social POI boundary, we focus only on finding the maximum possible distance
reachable from the POI’s representative coordinate, thereby enabling us to
significantly reduce the computational complexity compared to other density-
based clustering approaches [25, 28, 30].

Definition 1: Given a circle that has the representative coordinate $c$ of a
POI and a certain radius $r>0$, let $\mathcal{D}(c,r)$ denote the set of all
geo-tagged records (e.g., geo-tagged tweets) that include a given textual
description (i.e., a POI name) within the circle $(c,r)$. Then, a social POI
boundary is defined as a convex polygon geographically formed by taking the
convex hull of the given points in $\mathcal{D}(c,r)$.

As an example of geomarketing services, note that it would be desirable to
define the social POI boundary as a convex polygon that is the smallest region
enclosing all relevant records due to the cost efficiency as well as promotion
effectiveness. Contrary to LBSNs with check-in records and geo-tagged photos,
geo-tagged tweets with (semantically) different textual descriptions from a
POI name may occur especially on Twitter. Such irrelevant geo-tags may be
acceptable since one cannot expect that all geo-tags in a given region contain
the same textual description. For the sake of brevity, we denote geo-tags
whose text contains and does not contain an associated POI name by “relevant”
and “irrelevant” records, respectively. Similarly as in [41], to
quantitatively measure the number of relevant records, we introduce the
quality of an annotation in a given area in the following definition.

Definition 2: Given a textual description (i.e., a POI name), the quality of
the description in a circle $(c,r)$ is defined as

$\displaystyle{\textrm{Precision}{(c,r)}}$
$\displaystyle=\frac{|\mathcal{D}(c,r)|}{|\mathcal{D_{\texttt{all}}}(c,r)|}=\frac{TP{(c,r)}}{TP(c,r)+FP{(c,r)}},$
(1)

which is the ratio of true positives to all predicted positives, where $c$ and
$r$ denote the representative coordinate of a POI (corresponding to the center
of the circle) and the radius of the circle, respectively. Here,
$\mathcal{D}_{\texttt{all}}(c,r)$ denotes the set of all geo-tagged tweets
within the circle $(c,r)$ and is thus expressed as the sum of $TP{(c,r)}$ and
$FP{(c,r)}$; $TP{(c,r)}=|\mathcal{D}(c,r)|$ is the number of relevant records
inside the circle $(c,r)$; and
$FP{(c,r)}=|\mathcal{D}_{\texttt{all}}(c,r)\setminus\mathcal{D}(c,r)|$ is the
number of irrelevant records in the circle $(c,r)$.

Example 1: Let us recall the sample dataset having two circles in Fig. 1.
Then, red circles and black squares correspond to $TP(c,r_{i})$ and
$FP(c,r_{i})$, respectively. The annotation quality of each circle is computed
as

  * •

Circle 1: $\textrm{Precision}{(c,r_{1})}=\frac{8}{20}=0.40$;

  * •

Circle 2: $\textrm{Precision}{(c,r_{2})}=\frac{6}{8}=0.75$.

In our work, as a measure of boundary estimation accuracy, we use the
$\mathcal{F}$-measure to judge a boundary.

Definition 3: Given a POI name and a circle $(c,r)$, the $\mathcal{F}$-measure
is given by

$\displaystyle\mathcal{F}{(c,r)}=\frac{2\textrm{Precision}(c,r)\textrm{Recall}(c,r)}{\textrm{Precision}(c,r)+{\textrm{Recall}{(c,r)}}},$
(2)

which indicates the harmonic mean of $\textrm{Precision}(c,r)$ and
$\textrm{Recall}{(c,r)}$. Here, Recall$(c,r)$ is the ratio of true positives
to all actual positives, that is $\frac{TP{(c,r)}}{TP{(c,r)+FN{(c,r)}}}$; and
$FN(c,r)$ is the number of relevant records outside the circle $(c,r)$.

It is shown that the value of $TP(c,r)+FN(c,r)$ is fixed for a given dataset.
Thus, $\mathcal{F}(c,r)$ depends on $TP(c,r)$ and $FP(c,r)$ from (1). More
precisely, the $\mathcal{F}$-measure increases with high $TP(c,r)$ and low
$FP(c,r)$.

Example 2: For the two circles in Fig. 1, the $\mathcal{F}$-measure of each
circle is computed as

  * •

Circle 1: $\mathcal{F}{(c,r_{1})}=\frac{2\times 0.4\times 0.8}{0.4+0.8}=0.53$;

  * •

Circle 2: $\mathcal{F}{(c,r_{2})}=\frac{2\times 0.75\times
0.6}{0.75+0.6}=0.67$.

From Example 2, one can obviously see that $\mathcal{F}(c,r)$ becomes higher
when there are relatively more relevant records and less irrelevant records
inside the circle $(c,r)$.

(a) Empire State Building

(b) Dodger Stadium

(c) Metropolitan Museum of Art

(d) Busch Gardens

Figure 3: The $\mathcal{F}$-measure according to the radius $r$.

###  4.2 Optimization Problem

In this section, we elaborate on our new optimization problem that aims at
jointly finding the radius $r$ of a circle $(c,r)$ and the representative
coordinate $c$.

We begin by stating an interesting observation as follows. Fig. 3 depicts the
value of $\mathcal{F}$-measure when varying the radius $r$ (in meters) from
the initially given POI’s representative coordinate $c^{(0)}$ for each POI.
The maximum $\mathcal{F}(c^{(0)},r)$ for each POI is indicated by a red
circle. Interestingly, it is observed that the $\mathcal{F}$-measure tends to
be hardly degraded up to a certain critical point with respect to the radius
from the representative coordinate. For this reason, although it is desirable
to provide a social POI boundary with the highest $\mathcal{F}$-measure, it
would also be good to considerably extend the social POI boundary (to cover
more geographic region of the POI) at the cost of a slightly reduced value of
$\mathcal{F}(c^{(0)},r)$. One such application would include geomarketing as
companies targeting promotion of a shopping mall may want to expand their
marketing zone by disseminating flyers online to more people who are expected
to come to visit the desired POI while slightly sacrificing the promotion
accuracy (representing how many users accept the flyers as useful). For
example, see the Empire State Building in Fig. 3(a)—when the radius increases
from 60m to 110m, $\mathcal{F}(c^{(0)},r)$ decreases from 0.837 (a red circle)
to 0.792 (a black square), corresponding to only 5.68% reduction in
$\mathcal{F}(c^{(0)},r)$. Such a tendency can be found in the other examples.

In addition, we note that the approach in [47] finds the optimal radius $r$
for the initially given representative coordinate $c^{(0)}$ of a POI provided
by Geonames in the sense of maximizing the BEQ. However, motivated by the fact
that a fixed representative coordinate of each POI may be far away from the
corresponding centroid of all the relevant records in the estimated POI
boundary for certain POIs, we introduce a joint optimization problem of
finding both the radius $r$ of a circle $(c,r)$ and the POI’s representative
coordinate $c$ by allowing to update $c$. More specifically, we formulate a
new problem that aims at jointly finding both $r$ (in meters) and $c$ of a POI
such that the corresponding BEQ is maximized, as follows:444As an alternative
approach, the BEQ can be defined as the $\mathcal{F}_{\beta}$ measure for
$\beta\gg 1$, which is however not adopted in this work. Note that as
$\beta>1$, more emphasis is imposed on recall than precision, which thus may
lead to an extension of the social POI boundary compared to the case of
$\beta=1$.

$\displaystyle(c^{*},r^{*})=\arg\\!\max_{c,r}\left(\frac{r}{\bar{r}}\right)^{\alpha}\mathcal{F}(c,r)$
(3a) $\displaystyle\textrm{subject to}\quad 0<d(c,c^{(0)})+r\leq\bar{r}$ (3b)
$\displaystyle\quad\quad\quad\quad\quad\textup{ Precision}(c,r)\geq\eta,$ (3c)

where $\textup{Precision}(c,r)$ and $\eta\in(0,1)$ denote the textual quality
in a circle $(c,r)$ in (1) and the target quality threshold (which will be
specified in Section 6), respectively. Here, $\alpha$ is the radius exponent;
$d(c,c^{(0)})$ is the geographic distance between coordinates $c$ and
$c^{(0)}$, where $c^{(0)}$ is the initial representative coordinate of a POI
provided by Geonames; and $\bar{r}$ is the maximum searching distance and thus
is set to an arbitrarily large value such that
$\text{Precision}(c,\bar{r})\simeq 0$. In particular, the parameter $\alpha$
plays a crucial role in balancing different levels of coverage. For small
$\alpha$, a social POI boundary with the almost highest $\mathcal{F}$-measure
$\mathcal{F}(c,r)$ is found. As a special case, when $\alpha=0$, the original
problem is boiled down to maximizing $\mathcal{F}(c,r)$ under two constraints
(3b) and (3c). Equation (3b) is imposed so that the searching distance is
constrained to the maximum allowable radius $\bar{r}$ from the representative
coordinate $c^{(0)}$. Equation (3c) is imposed so that the given minimum ratio
of the number of relevant records in the circle $(c,r)$ to the number of all
geo-tagged tweets in the same circle can be guaranteed.

##  5 Proposed Estimation Method

In this section, we describe our computationally efficient I-SoBEst algorithm
that effectively solves the optimization problem in (3). For the completeness
of this paper, we also review the original SoBEst algorithm in [47].

In the algorithms, $\bar{r}$ is assumed to be arbitrarily large fulfilling
$\textup{Precision}(c,\bar{r})\simeq 0$ for the representative coordinate $c$
of a POI. We suppose that two classified sets $\mathcal{D}(c,\bar{r})$ and
$\mathcal{D}_{\texttt{all}}(c,\bar{r})$ are given as input, where
$\mathcal{D}{(c,\bar{r})}$ and $\mathcal{D}_{\texttt{all}}(c,\bar{r})$ denote
the sets of relevant records and all geo-tagged tweets, respectively, in the
circle $(c,\bar{r})$. Since the geo-tags’ coordinate is expressed in finite
precision, we perform uniform sampling from $(0,\bar{r}]$ with a given
sampling interval $\Delta r>0$, where $\Delta r$ is set to a small value
greater than the GPS error distance [36]. Input parameters $\alpha$ and $\eta$
are determined according to the target levels of geographic coverage and the
constraint of BEQ, respectively.

###  5.1 SoBEst Algorithm

We summarize the overall procedure of our earlier work, SoBEst, with a slight
modification in Algorithm 1. Since SoBEst is invoked multiple times within the
I-SoBEst algorithm (refer to Section 5.2 for more details), we hereby focus on
describing the $k^{\texttt{th}}$ iteration of SoBEst, which basically consists
of the following two phases.

  * •

Phase 1 (Lines 1–9 in Algorithm 1): We find the maximum radius $r_{M}$ such
that $\textup{Precision}(c^{(k)},r)\geq\eta$ in (3c) for
$0<d(c^{(k)},c^{(0)})+r\leq\bar{r}$ in (3b).

  * •

Phase 2 (Lines 11–18 in Algorithm 1): We find the optimal radius $r^{(k)}$
that maximizes $(\frac{r}{\bar{r}})^{\alpha}\mathcal{F}(c^{(k)},r)$ under the
constraints in (3b) and (3c).

Here, $c^{(k)}$ indicates the POI’s representative coordinate after the
$k^{\texttt{th}}$ iteration of SoBEst. In each phase, given a POI, we start by
using a circle centered at $c$ with radius $r_{i}=\Delta r$. The radius is
increased by $\Delta r$ for each step, and $r_{M}$ in Phase 1 or $r^{(k)}$ in
Phase 2 is updated gradually if a certain condition is fulfilled. For each
iterative step in Phase 1, the subroutine
Filter($r_{i},\mathcal{G}(c^{(k)},\bar{r})$) in Algorithm 2 is invoked to
collect the set
$\mathcal{G}(c^{(k)},r_{i})\subseteq\mathcal{G}(c^{(k)},\bar{r})$, where
$\mathcal{G}(c^{(k)},r_{i})$ is either $\mathcal{D}(c^{(k)},r_{i})\textrm{ or
}\mathcal{D}_{\texttt{all}}(c^{(k)},r_{i})$. To be specific, it follows that
$\mathcal{G}(c^{(k)},r_{i})=\\{q_{m}|d(c^{(k)},q_{m})\leq r_{i}\\}$, where
$d(c^{(k)},q_{m})$ denotes the geographic distance between $c^{(k)}$ and the
$m^{\texttt{th}}$ geo-tag’s coordinate $q_{m}$ in
$\mathcal{G}(c^{(k)},\bar{r})$.555When the shortest path between two geo-tags’
locations is measured along the surface of the Earth, the distance between two
locations can be computed according to the spherical law of cosines [14]. Line
2 in Algorithm 2 can be implemented by using a searching algorithm such as
R-trees [21]. The SoBEst algorithm finally returns
$r^{(k)},\mathcal{D}(c^{(k)},r^{(k)})$, and $\mathcal{F}(c^{(k)},r^{(k)})$ as
the output of Algorithm 1.

Algorithm 1 SoBEst [47]
---
Input:$\mathcal{D}(c^{(k)},\bar{r}),\mathcal{D}_{\texttt{all}}(c^{(k)},\bar{r}),\Delta
r,\alpha,\eta,c^{(k)}$
Output: $r^{(k)},\mathcal{D}(c^{(k)},r^{(k)}),\mathcal{F}(c^{(k)},r^{(k)})$
Initialization: $i\leftarrow 1;r_{i}\leftarrow\Delta r;r_{M}\leftarrow
0;r^{(k)}\leftarrow 0;$
$N\leftarrow\frac{\bar{r}}{\Delta r};TP(c^{(k)},r_{i})\leftarrow
0;FP(c^{(k)},r_{i})\leftarrow 0;$
$FN(c^{(k)},r_{i})\leftarrow 0;\mathcal{F}{(c^{(k)},r_{i})\leftarrow
0;}\mathcal{D}_{\texttt{all}}(c^{(k)},r_{i})\leftarrow\emptyset;$
$\mathcal{D}(c^{(k)},r_{i})\leftarrow\emptyset;\mathcal{F}{(c^{(k)},r^{(k)})}\leftarrow
0;$
$\textup{Precision}(c^{(k)},r_{i})\leftarrow
0;\textup{Recall}{(c^{(k)},r_{i})}\leftarrow 0$
01: for $i\leftarrow 1$ to $N$
02:
$\mathcal{D}_{\texttt{all}}(c^{(k)},r_{i})\leftarrow\textrm{Filter}(r_{i},\mathcal{D}_{\texttt{all}}(c^{(k)},\bar{r}))$
(see Algorithm 2)
03:
$\mathcal{D}(c^{(k)},r_{i})\leftarrow\textrm{Filter}(r_{i},\mathcal{D}(c^{(k)},\bar{r}))$
(see Algorithm 2)
04: $TP{(c^{(k)},r_{j})}\leftarrow|\mathcal{D}(c^{(k)},r_{j})|$
05:
$FP{(c^{(k)},r_{j})}\leftarrow|\mathcal{D}_{\texttt{all}}(c^{(k)},r_{j})\setminus\mathcal{D}(c^{(k)},r_{j})|$
06:
$\textrm{Precision}(c^{(k)},r_{i})\leftarrow\frac{TP{(c^{(k)},r_{i})}}{TP{(c^{(k)},r_{i})}+FP{(c^{(k)},r_{i})}}$
07: if $r_{i}>r_{M}$ and $\textrm{Precision}{(c^{(k)},r_{i})}\geq\eta$ then
08: $r_{M}\leftarrow r_{i}$
09: $r_{i+1}\leftarrow r_{i}+\Delta r$
10: $M\leftarrow\frac{r_{M}}{\Delta r}$
11: for $i\leftarrow 1$ to $M$
12:
$FN{(c^{(k)},r_{i})}\leftarrow|\mathcal{D}(c^{(k)},\bar{r})\setminus\mathcal{D}(c^{(k)},r_{i})|$
13:
$\textrm{Recall}(c^{(k)},r_{i})=\frac{TP{(c^{(k)},r_{i})}}{TP{(c^{(k)},r_{i})}+FN{(c^{(k)},r_{i})}}$
14:
$\mathcal{F}{(c^{(k)},r_{i})}=\frac{2\textrm{Precision}(c^{(k)},r_{i})\textrm{Recall}(c^{(k)},r_{i})}{\textrm{Precision}(c^{(k)},r_{i})+{\textrm{Recall}{(c^{(k)},r_{i})}}}$
15: if
$\left(\frac{r_{i}}{\bar{r}}\right)^{\alpha}\mathcal{F}{(c^{(k)},r_{i})}\geq\left(\frac{r^{(k)}}{\bar{r}}\right)^{\alpha}\mathcal{F}{(c^{(k)},r^{(k)})}$
then
16: $r^{(k)}\leftarrow r_{i}$
17: $\mathcal{F}{(c^{(k)},r^{(k)})}\leftarrow\mathcal{F}{(c^{(k)},r_{i})}$
18: $r_{i+1}\leftarrow r_{i}+\Delta r$
19: return
$r^{(k)},\mathcal{D}(c^{(k)},r^{(k)}),\mathcal{F}{(c^{(k)},r^{(k)})}$
Algorithm 2 Filter($r_{i},\mathcal{G}(c^{(k)},\bar{r})$)
---
Input: $\mathcal{G}(c^{(k)},\bar{r})$ $(\mathcal{D}(c^{(k)},\bar{r})\textrm{
or }\mathcal{D}_{\texttt{all}}(c^{(k)},\bar{r})),r_{i}$
Output: $\mathcal{G}(c^{(k)},r_{i})$ for $r_{i}\in(0,\bar{r}]$
Initialization: $m\leftarrow 1;l\leftarrow|\mathcal{G}(c^{(k)},\bar{r})|$
01: for $m\leftarrow 1$ to $l$
02: $\mathcal{G}(c^{(k)},r_{i})\leftarrow\\{q_{m}|d(c^{(k)},q_{m})\leq
r_{i}\\}$
03: return $\mathcal{G}(c^{(k)},r_{i})$

Afterwards, by solving the convex-hull problem (e.g., quickhull and an output-
sensitive convex-hull algorithm [7]), we can finally obtain the smallest
convex polygon that contains all the geo-tags in the set
$\mathcal{D}(c^{(k)},r^{(k)})$ quickly, corresponding to the estimated social
POI boundary.

###  5.2 I-SoBEst Algorithm

To effectively solve the joint optimization problem in (3), we introduce a
low-complexity algorithm, named I-SoBEst. The I-SoBEst algorithm is designed
in such a way that parameters $r$ and $c$ are iteratively updated until a
given termination criterion is fulfilled.666In our study, we aim at offering a
computationally efficient solution, rather than directly tackling the joint
optimization problem along with the optimality. The overall procedure is
summarized in Algorithm 3. For each iterative step, the subroutine
$\text{SoBEst}(\mathcal{D}(c^{(k)},\bar{r}),\mathcal{D}_{\texttt{all}}$
$(c^{(k)},\bar{r}),\Delta r,\alpha,\eta)$ is invoked to find the radius
$r^{(k)}$ for a given POI’s representative coordinate $c^{(k)}$, where $k$
indicates the iteration index and $r^{(k)},\mathcal{D}(c^{(k)},r^{(k)})$, and
$\mathcal{F}(c^{(k)},r^{(k)})$ are returned as the output of SoBEst. In Line 4
of the algorithm, $p_{l}^{(k)}$ denotes the $l^{\texttt{th}}$ geo-tag’s
coordinate such that $p_{l}^{(k)}$ $\in$ $\mathcal{D}(c^{(k-1)},$
$r^{(k-1)})$, and thus $\frac{\sum{p_{l}^{(k)}}}{L^{(k)}}$ represents the
centroid of all relevant records in the set
$\mathcal{D}(c^{(k-1)},r^{(k-1)})$. The algorithm operates under the
termination criterion in Line 6, where $\delta>0$ denotes the tolerance level
determining the convergence speed and will be specified later. In Section 6,
we shall show that the I-SoBEst algorithm outperforms the original SoBEst in
terms of the BEQ $\left(\frac{r}{\bar{r}}\right)^{\alpha}\mathcal{F}(c,r)$
while maintaining the linear run-time complexity.

Algorithm 3 I-SoBEst
---
Input:$\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r}),\mathcal{D}(c^{(0)},\bar{r}),\Delta
r,\alpha,\eta,\delta,c^{(0)},\bar{r}$
Output: $\mathcal{D}(c^{*},r^{*})$
Initialization: $k\leftarrow 0;r^{*}\leftarrow 0;c^{*}\leftarrow
c^{(0)};\mathcal{D}(c^{*},r^{*})\leftarrow\emptyset;$
$(r^{(0)},\mathcal{D}(c^{(0)},r^{(0)}),\mathcal{F}(c^{(0)},r^{(0)}))$
$\leftarrow\textup{SoBEst}(\mathcal{D}(c^{(0)},\bar{r}),\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r}),\Delta
r,\alpha,\eta)$
01: do
02: $k\leftarrow k+1$
03: $L^{(k)}=|\mathcal{D}(c^{(k-1)},r^{(k-1)})|$
04: $c^{(k)}\leftarrow\frac{\sum{p_{l}^{(k)}}}{L^{(k)}}$
05: $(r^{(k)},\mathcal{D}(c^{(k)},r^{(k)}),\mathcal{F}(c^{(k)},r^{(k)}))$
$\leftarrow\textup{SoBEst}(\mathcal{D}(c^{(k)},\bar{r}),\mathcal{D}_{\texttt{all}}(c^{(k)},\bar{r}),\Delta
r,\alpha,\eta)$
06: while
$\left(\frac{r^{(k)}}{\bar{r}}\right)^{\alpha}\mathcal{F}(c^{(k)},r^{(k)})\\!$
$-\left(\frac{r^{(k-1)}}{\bar{r}}\right)^{\alpha}\mathcal{F}(c^{(k-1)},r^{(k-1)})\geq\delta$
07: $c^{*}\leftarrow c^{(k-1)}$
08: $r^{*}\leftarrow r^{(k-1)}$
09: return $\mathcal{D}(c^{*},r^{*})$

###### Remark 1

Let us now state the convergence analysis of the I-SoBEst algorithm. Due to
the fact that we have a finite number of geo-tagged records, there are a
finite number of different representative coordinates $c^{(k)}$. It is obvious
that the result of SoBEst is deterministic for given $c^{(k)}$, corresponding
to a deterministic
$\left(\frac{r^{(k)}}{\bar{r}}\right)^{\alpha}\mathcal{F}(c^{(k)},r^{(k)})$.
From Line 6 of Algorithm 3, one can see that
$\left(\frac{r^{(k)}}{\bar{r}}\right)^{\alpha}\mathcal{F}(c^{(k)},r^{(k)})$ is
nonnegative and monotonically increasing after each iteration. Hence, I-SoBEst
converges to a local maximum in a finite number of iterations.

##  6 Performance Evaluation

In this section, using the proposed I-SoBEst algorithm in Section 5.2, we
first show experimental results for the BEQ and then analyze the overall
average computational complexity. The Twitter dataset and the set of POIs in
Section 3 are used for performance evaluation. Statistics of four POIs in
Table 2, including $|\mathcal{D}(c^{(0)},\bar{r})|$ (i.e., the number of
relevant records), $|\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r})|$, and
$r_{cover}$, are shown in Table 4. As depicted in the table, since four POIs
were selected according to each different Geonames category, both
$|\mathcal{D}(c^{(0)},\bar{r})|$ and
$|\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r})|$ are significantly different
from each other.

###  6.1 Experimental Setups

For all POIs, we assume $\eta=0.5$, which can be set to another value so as to
control the constraint of BEQ, and $\Delta r=10m$. Even if $\bar{r}$ is
assumed to be arbitrarily large, we need to set $\bar{r}$ to a reasonable
value in our experiment to efficiently reduce the complexity of the algorithm.
In our study, we assume ${\bar{r}}=\gamma r_{\texttt{cover}}$, where $\gamma$
is a positive constant and $r_{\texttt{cover}}$ denotes an approximate radius
from a POI’s representative coordinate covering the geographic area of each
POI and is obtained from Google Maps Geocoding
API.777https://developers.google.com/maps/documentation/geocoding/intro. The
Google Maps Geocoding API returns an approximate bounding box of a given POI,
constructed by the southwest and northeast corners, and the value of
$r_{\texttt{cover}}$ is obtained by computing the maximum of the two distances
between the POI’s representative coordinate and each of the southwest and
northeast corners. While $\gamma$ can be properly determined according to the
POI types (e.g., $\gamma=1$ for a cafeteria and $\gamma=10$ for an observation
point), we use $\gamma=10$ for all POIs for the sake of experimental
simplicity. That is, we set $\bar{r}=10r_{\texttt{cover}}$ for a given radius
$r_{\texttt{cover}}$ in Table 4, corresponding to the size of an approximate
bounding box of each POI. It is then empirically demonstrated that the
resulting $\text{Precision}(c,\bar{r})$ is negligibly small for all POIs,
which coincides with our statement in Section 4.2. Moreover, we take into
account the case where $\alpha\in[0,1]$ since otherwise, the objective
function in (3a) are largely dominated by the term
$\left(\frac{r}{\bar{r}}\right)^{\alpha}$. More precisely, the value of
$\alpha$ in geomarketing can be determined according to different marketing
strategies. If a strategy aims to maximize the promotion accuracy (i.e., the
$\mathcal{F}$-measure), then it is desirable to set $\alpha=0$, which results
in the minimum marketing cost. If a strategy is to expand the marketing zone
with a higher marketing cost while sacrificing the promotion accuracy, then
$\alpha$ needs to be set to a certain large positive value. In our
experiments, to cover various situations, it is assumed that
$\alpha\in\\{0,0.5,1\\}$. We assume $\delta=10^{-4}$ for all POIs, which can
be set to another value to adjust the convergence speed.

Table 4: Statistics of the four POIs. POI name | $|\mathcal{D}(c^{(0)},\bar{r})|$ | $|\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r})|$ |  |  $r_{\texttt{cover}}$ (m)
---
Empire State Building | 1,061 | 6,812 | 201
Dodger Stadium | 941 | 2,228 | 150
Metropolitan Museum of Art | 591 | 18,413 | 239
Busch Gardens | 166 | 297 | 660

###  6.2 Estimation Performance

Estimation results of the I-SoBEst algorithm are shown according to different
values of $\alpha\geq 0$ for the four POIs. When $\delta=10^{-4}$, the BEQ
$\left(\frac{r}{\bar{r}}\right)^{\alpha}\mathcal{F}(c,r)$ converges to
$\left(\frac{r^{*}}{\bar{r}}\right)^{\alpha}\mathcal{F}(c^{*},r^{*})$ within
three iterations. The BEQ of I-SoBEst for the four POIs is summarized in Table
5 in comparison with that of SoBEst without updating the POI’s representative
coordinate $c$, where $\alpha\in\\{0,0.5,1\\}$. For better understanding, the
social POI boundaries estimated by both SoBEst [47] and I-SoBEst are
illustrated in Fig. 5, where $\alpha\in\\{0,1\\}$; the red circles are the
relevant records; the green diamond is the initial representative coordinate
of each POI; and the blue diamond is the updated representative coordinate of
each POI. From Table 5 and Fig. 5, the following interesting findings are
observed.

  * •

When the updated representative coordinate $c^{*}$ of a POI is far away from
the initial one $c^{(0)}$ (e.g., Empire State Building and Busch Gardens), the
BEQ of I-SoBEst is enhanced up to $16.75\%$, compared to the original SoBEst
case, where the performance improvement over SoBEst is expressed as
$\frac{\text{(BEQ of {I-SoBEst}) - (BEQ of {SoBEst})}}{\text{BEQ of
{SoBEst}}}\times 100\%$.

  * •

On the other hand, when the two representative coordinates of a POI marked
with green and blue diamonds are close to each other (e.g., Dodger Stadium),
the performance improvement is marginal or does not exist.

In consequence, the distribution of relevant records (leading to a different
centroid) significantly affects the improvement rate of the BEQ. For example,
as illustrated in Fig. 5(d), the social POI boundary of Busch Gardens
estimated by I-SoBEst covers a part of the SheiKra roller coaster, which is
located in the western part of Busch Gardens, for all $\alpha$’s by
iteratively updating the POI’s representative coordinate; however, such a
tendency is not exhibited for the case estimated by the original SoBEst. Thus,
the social POI boundary estimated by I-SoBEst is more appropriate for
geomarketing in some cases where a fixed representative coordinate of each POI
is far away from the locations in which relevant records were posted.

Table 5: The BEQ of SoBEst and I-SoBEst. POI name | $\alpha$ |  | BEQ of SoBEst
---
| BEQ of I-SoBEst
---
Empire State Building |  |  | 0
---
0.5
1
| 0.837
---
0.187
0.049
| 0.874
---
0.205
0.056
Dodger Stadium |  |  | 0
---
0.5
1
| 0.759
---
0.566
0.480
| 0.760
---
0.566
0.480
Metropolitan Museum of Art |  |  | 0
---
0.5
1
| 0.844
---
0.224
0.060
| 0.847
---
0.236
0.066
Busch Gardens |  |  | 0
---
0.5
1
| 0.816
---
0.304
0.117
| 0.838
---
0.323
0.137

(a) Empire State Building

(b) Dodger Stadium

(c) Metropolitan Museum of Art

(d) Busch Gardens

Figure 5: Social POI boundaries estimated by SoBEst and I-SoBEst, where one
green diamond, one blue diamond, and red circles indicate the initial
representative coordinate, updated representative coordinate, and relevant
records, respectively, in each subfigure. Here, the size of each red circle is
increased according to the number of superimposed records.

####  6.2.1 Comparison With Competing Methods

Now, to verify the superiority of the proposed I-SoBEst algorithm, let us turn
to the performance comparison with two baseline methods and three state-of-
the-art methods. In the following, we briefly describe the basic mechanism,
parameter settings, and BEQs of each method.

DBSCAN (Baseline #1). As mentioned in the prior studies, DBSCAN is the most
commonly used density-based clustering algorithm in identifying the AOI, and
thus can be considered as a baseline method in this field of study. Rather
than adopting more recently developed state-of-the-art DBSCAN methods in [3,
6, 25, 28, 30], we use our own variant by modifying the original DBSCAN
algorithm in [15]. This is because all the DBSCAN methods do not exploit any
property of textual attributes in discovering clusters. More precisely, the
original one does not take into account any textual attributes and performs
clustering based purely on the spatial density. Our modified DBSCAN method is
suitable for performance evaluation under our problem setting since it enables
us to surely guarantee higher performance. Thus, instead of
$\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r})$, the set
$\mathcal{D}(c^{(0)},\bar{r})$ including solely relevant records is assumed to
be used as input of DBSCAN, which will result in a much higher BEQ. DBSCAN
operates based on two important parameters $MinPts$ and $\epsilon$, where
$MinPts$ is the minimum number of points required to form a dense region
within a distance threshold $\epsilon$ [15]. Setting $\epsilon$ too high
(e.g., $\epsilon$ = 10 km) may result in over-expanded clusters, while setting
it too low (e.g., $\epsilon$ = 10 m) may lead to missing large clusters. Our
modified DBSCAN method is suitable for performance evaluation under our
problem setting since it enables us to guarantee higher performance. Thus,
$\epsilon$ needs to be carefully chosen according to each POI type. Moreover,
$MinPts$ should be chosen as at least $3$ since otherwise, the result will be
the same as the hierarchical clustering case with the single link metric [2].
For a fair comparison with the proposed approach, we then select the one
having the largest number of relevant records among multiple clusters, named
the POI cluster, as a counterpart of the social POI boundary estimated from
SoBEst. Thereafter, using (1) and (2), the $\mathcal{F}$-measure of a given
POI cluster can be computed by replacing
$\mathcal{D}_{\texttt{all}}(c^{(0)},r)$ and $\mathcal{D}(c^{(0)},r)$ by the
set of all geo-tags and the set of all relevant records, respectively, only
within the POI cluster. In our work, we assume $MinPts=5$ and
$\epsilon=r_{\texttt{cover}}$, which are properly chosen to return a high
$\mathcal{F}$-measure for the selected POI cluster.

One-class support vector machine (OCSVM) (Baseline #2). OCSVM [35] is a well-
known unsupervised clustering technique for learning a decision boundary
between outliers and the rest of a given dataset, in which an input parameter
$\vartheta$ specifies the probability of outliers. In [20], the OCSVM
algorithm was employed to estimate a crisp boundary of an AOI—the set of
relevant geo-tagged records, corresponding to $\mathcal{D}(c^{(0)},\bar{r})$,
was exploited as input of the algorithm, where the parameter $\vartheta$ is
set to 0.14 based on the statistical analysis on regions with administrative
boundaries. Since this parameter setting results in a high
$\mathcal{F}$-measure for each selected POI cluster in our experiments, it is
adopted to evaluate the BEQ of OCSVM.

Two-phase estimation for POI boundaries (2P-BEst) (State-of-the-art #1). A
low-complexity two-phase POI boundary estimation (2P-BEst) algorithm was
developed in [46] as a state-of-the-art method by discovering a circle with
radius $r^{*}$ that covers one POI cluster. The algorithm takes
$\mathcal{D}(c^{(0)},\bar{r})$, which is the set of relevant records within a
circle $(c^{(0)},\bar{r})$, as the input along with the following three tuning
parameters: the radius interval $\Delta r_{1}$ for the first phase, the
interval granularity $Q$, and the threshold $\Delta\eta$ determining the
update condition for the first phase. In our experiments, $\Delta\eta$ and $Q$
are set to 100 and 10, respectively, as in [46], while $\Delta r_{1}$ is set
to $r_{\texttt{cover}}$, which is determined adaptively according to a given
POI and thus yields a relatively high $\mathcal{F}$-measure.

Fast density peak clustering (FastDPeak) (State-of-the-art #2). We implement
an efficient DPC algorithm, dubbed FastDPeak [8], as another state-of-the-art
method that detects the largest POI cluster based on the density of relevant
records (i.e., the set $\mathcal{D}(c^{(0)},\bar{r})$). FastDPeak tends to
perform quite poorly for four selected POIs due to the existence of
superimposed records since the local density of such records becomes extremely
high. Thus, the original algorithm is modified in such a way that 90% of
superimposed records are empirically removed to achieve a high BEQ through
intensive experiments, which can be well generalized over all four selected
POIs. In our experiments, an input parameter $C$, indicating the number of
detected clusters, is properly chosen to return a high BEQ for the selected
POI cluster.

Robust noise resistent POI identification (RNRPI) (State-of-the-art #3). We
employ another state-of-the-art algorithm of detecting boundaries of multiple
POIs in [49]. This algorithm introduces a technique incorporating Laplacian
zero-crossing points, which adaptively filters noise records from the set
$\mathcal{D}(c^{(0)},\bar{r})$ based on the local drastic changes of the data
density given by a Gaussian kernel density estimation function. Since the
density estimation function cannot perform properly due to the presence of
superimposed records, we also remove 90% of superimposed records as in
FastDPeak to achieve a higher degree of the BEQ for four selected POIs. In our
experiments, the parameter $\alpha$ corresponding to the step size for the
gradient of the density estimation function in RNRPI is set appropriately for
each POI.

Performance comparison. Due to the fact that four algorithms, including
DBSCAN, OCSVM, FastDpeak, and RNRPI return arbitrarily-shaped clusters, we
need to find a proper radius $r_{\texttt{D}}$ of the POI cluster in order to
evaluate the BEQ of these methods under our problem setting. In our work, the
radius $r_{\texttt{D}}$ is given by the maximum distance between all relevant
records in the cluster and the centroid of all the relevant records in the
cluster. Finally, we present performance comparison among SoBEst and I-SoBEst
as well as five competing methods in terms of BEQ in Fig. 6. From the figure,
the following insightful observations are found.

  * •

I-SoBEst outperforms all other methods in terms of BEQ by up to an order of
maginitude in almost all cases (refer to the Dodger Stadium for $\alpha=1$ to
see the largest improvement over FastDPeak).

  * •

When the initial representative coordinate $c^{(0)}$ is not correctly placed,
I-SoBEst can alleviate the weakness of SoBEst (refer to the Busch Garden for
$\alpha=1$ to see additional performance gain). The effect of the initial
representative coordinate on the BEQ can also be identified by comparing the
results of SoBEst and I-SoBEst algorithms in Figs. 5 and 6.

(a) $\alpha=0$

(b) $\alpha=0.5$

(c) $\alpha=1$

Figure 6: The performance comparison of I-SoBEst, SoBEst, DBSCAN, OCSVM,
2P-BEst, FastDPeak, and RNRPI algorithms, where the BEQ is illustrated
according to each POI, and ESB, DS, MMA, and BG indicate Empire State
Building, Dodger Stadium, Metropolitan Museum of Art, and Busch Gardens,
respectively.

###  6.3 Computational Complexity

In this subsection, we analyze the computational complexity of I-SoBEst
(Algorithm 3). Let us denote the cardinality of the set
$\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r})$ by
$n_{\texttt{all}}\triangleq|\mathcal{D}_{\texttt{all}}(c^{(0)},\bar{r})|$,
representing the number of all geo-tagged tweets in a circle
$(c^{(0)},\bar{r})$. In our I-SoBEst algorithm, the overall computational
complexity is dominated by SoBEst whose runtime complexity is given by
$\mathcal{O}(n_{\texttt{all}})$ according to the argument in [47]. More
specifically, it is shown that the computational complexity still scales as
$\mathcal{O}(n_{\texttt{all}})$ (i.e., linearity in $n_{\texttt{all}}$) as
long as the number of iterations is very small and, more importantly, is
independent of $n_{\texttt{all}}$. We numerically validate this argument by
examining that the number of iterations is at most three when $\delta=10^{-4}$
and the POIs in Table 4 are used. Next, in Fig. 7, the overall runtime is
evaluated when $n_{\texttt{all}}$ varies from 2,000 to 5,500 in an increment
of 500, where the social POI bound of Empire State Building is estimated for
$\alpha=1$ and $n_{\texttt{all}}$ points are randomly sampled from 6,812 geo-
tagged records for the Empire State Building. An asymptotic dotted line with a
proper bias is also plotted in Fig. 7, showing trends consistent with our
experimental result.

Figure 7: Runtime complexity for estimating the social POI boundary of the
Empire State Building.

##  7 Concluding Remarks

In this paper, we introduced an improved framework for estimating social POI
boundaries, which has a broad range of applications from geomarketing, event
management to urban planning, along with an iterative estimation method. Based
on our prior estimation approach exploiting the spatio–textual data on social
media, we presented a new joint optimization of the radius of a circle and the
POI’s representative coordinate $c$ by allowing to update $c$, and then
proposed the I-SoBEst algorithm. To show the effectiveness of our algorithm,
we numerically evaluated the BEQ for various $\alpha$’s and POIs, and
delineated the estimated social POI boundaries. It turned out that the
I-SoBEst algorithm is superior to the original SoBEst by up to 16.75% and
remarkably outperforms the baseline and state-of-the-art methods by up to an
order of magnitude for almost all cases. In addition, the computational
complexity of I-SoBEst was analytically shown and numerically validated. This
sheds light on the design of density-based clustering by intelligently
integrating spatial and textual attributes on social media.

## Acknowledgments

This research was supported by the Republic of Korea’s MSIT (Ministry of
Science and ICT), under the High-Potential Individuals Global Training Program
(No. 2020-0-01463) supervised by the IITP (Institute of Information and
Communications Technology Planning Evaluation), by a grant of the Korea Health
Technology R&D Project through the Korea Health Industry Development Institute
(KHIDI), funded by the Ministry of Health & Welfare, Republic of Korea
(HI20C0127), and by the Yonsei University Research Fund of 2020
(2020-22-0101). This paper was presented in part at the ACM SIGMOD Workshop on
Managing and Mining Enriched Geo-Spatio Data, San Francisco, CA, June 2016
[47].

## References

  * Ahlers [2013] Ahlers, D., 2013.  Assessment of the accuracy of GeoNames gazetteer data, in: Proc. 7th Worksh. Geo. Inf. Retrieval (GIR ’13), Orlando, FL. pp. 74–81.
  * Ankerst et al. [1999] Ankerst, M., Breunig, M.M., Kriegel, H.P., Sander, J., 1999\.  OPTICS: Ordering points to identify the clustering structure, in: Proc. ACM SIGMOD Int. Conf. Management of Data (SIGMOD ’99), Philadelphia, PA. pp. 49–60.
  * Birant and Kut [2007] Birant, D., Kut, A., 2007.  ST-DBSCAN: An algorithm for clustering spatial–temporal data.  Data Knowl. Engin. 60, 208–221.
  * Boonchoo et al. [2019] Boonchoo, T., Ao, X., Liu, Y., Zhao, W., Zhuang, F., He, Q., 2019.  Grid-based DBSCAN: Indexing and inference.  Pattern Recog. 90, 271–284.
  * Bui et al. [2015] Bui, T.H., Han, Y.J., Park, S.B., Park, S.Y., 2015\.  Detection of POI boundaries through geographical topics, in: Proc. 2015 Int. Conf. Big Data and Smart Comput. (BIGCOMP ’15), Jeju, South Korea. pp. 162–169.
  * Campello et al. [2013] Campello, R.J.G.B., Moulavi, D., Sander, J., 2013.  Density-based clustering based on hierarchical density estimates, in: Pacific-Asia Conf. Knowl. Disc. Data Mining (PAKDD ’13), Gold Coast, Australia. pp. 160–172.
  * Chan [1996] Chan, T.M., 1996.  Optimal output-sensitive convex hull algorithms in two and three dimensions.  Discrete Comput. Geometry 16, 361–368.
  * Chen et al. [2020] Chen, Y., Hu, X., Fan, W., Shen, L., Zhang, Z., Liu, X., Du, J., Li, H., Chen, Y., Li, H., 2020\.  Fast density peak clustering for large scale data based on knn.  Knowl.-Based Syst. 187, 1–7.
  * Chen et al. [2019] Chen, Y., Zhou, L., Pei, S., Yu, Z., Chen, Y., Liu, X., Du, J., Xiong, N., 2019.  KNN-BLOCK DBSCAN: Fast clustering for large-scale data.  IEEE Trans. Syst. Man Cyber. Syst. , 1–15.
  * Chen et al. [2014] Chen, Y., Zhuang, C., Cao, Q., Hui, P., 2014.  Understanding cross-site linking in online social networks, in: Proc. 8th Worksh. Social Netw. Mining and Analysis (SNA-KDD ’14), New York, NY. pp. 1–9.
  * Cho et al. [2011] Cho, E., Myers, S.A., Leskovec, J., 2011.  Friendship and mobility: User movement in location-based social networks, in: Proc. 17th ACM SIGKDD Int. Conf. Knowl. Disc. and Data Mining (KDD ’11), San Diego, CA. pp. 1082–1090.
  * Cong et al. [2009] Cong, G., Jensen, C.S., Wu, D., 2009.  Efficient retrieval of the top-$k$ most relevant spatial web objects.  Proc. VLDB Endowment 2, 337–348.
  * De Felipe et al. [2008] De Felipe, I., Hristidis, V., Rishe, N., 2008.  Keyword search on spatial databases, in: Proc. 24th IEEE Int. Conf. Data Engin. (ICDE ’08), Cancun, Mexico. pp. 656–665.
  * Ennis et al. [2013] Ennis, A., Chen, L., D. Nugent, C., Ioannidis, G., Stan, A., 2013.  High-level geospatial information discovery and fusion for geocoded multimedia.  Int. J. Pervasive Comput. Commun. 9, 367–382.
  * Ester et al. [1996] Ester, M., Kriegel, H.P., Sander, J., Xu, X., 1996.  A density-based algorithm for discovering clusters in large spatial databases with noise.  Data Mining Knowl. Disc. 96, 226–231.
  * Ference et al. [2013] Ference, G., Ye, M., Lee, W.C., 2013.  Location recommendation for out-of-town users in location-based social networks, in: Proc. 22nd ACM Int. Conf. Inf. & Knowl. Management (CIKM ’13), San Francisco, CA. pp. 721–726.
  * Ferwerda et al. [2015] Ferwerda, B., Schedl, M., Tkalcic, M., 2015.  Predicting personality traits with Instagram pictures, in: Proc. 3rd Worksh. Emotions and Personality in Personalized Syst. (EMPIRE ’15), Vienna, Austria. pp. 7–10.
  * Gao et al. [2014] Gao, H., Tang, J., Liu, H., 2014.  Personalized location recommendation on location-based social networks, in: Proc. 8th ACM Conf. Recommender Syst. (RecSys ’14), New York, NY. pp. 399–400.
  * van Gennip et al. [2013] van Gennip, Y., Hunter, B., Ahn, R., Elliott, P., Luh, K., Halvorson, M., Reid, S., Valasik, M., Wo, J., Tita, G.E., et al., 2013\.  Community detection using spectral clustering on sparse geosocial data.  SIAM J. Appl. Math. 73, 67–83.
  * Grothe and Schaab [2009] Grothe, C., Schaab, J., 2009\.  Automated footprint generation from geotags with kernel density estimation and support vector machines.  Spatial Cogn. Comput. 9, 195–211.
  * Guttman [1984] Guttman, A., 1984.  R-trees: A dynamic index structure for spatial searching, in: Proc. ACM SIGMOD Int. Conf. Management of Data (SIGMOD ’84), Boston, MA. pp. 47–57.
  * Hong and Davison [2010] Hong, L., Davison, B.D., 2010\.  Empirical study of topic modeling in Twitter, in: Proc. 1st Worksh. Social Media Analytics (SOMA ’10), Washington, DC. pp. 80–88.
  * Hu and Ester [2014] Hu, B., Ester, M., 2014.  Social topic modeling for point-of-interest recommendation in location-based social networks, in: Proc. 2014 IEEE Int. Conf. Data Mining (ICDM ’14), Shenzhen, China. pp. 845–850.
  * Joseph et al. [2014] Joseph, K., Landwehr, P.M., Carley, K.M., 2014.  Two 1%s don’t make a whole: Comparing simultaneous samples from Twitter’s streaming API.  Social Comput., Behavioral-Cultural Model. Pred. 8393, 75–83.
  * Kisilevich et al. [2010] Kisilevich, S., Mansmann, F., Keim, D., 2010.  P-DBSCAN: A density based clustering algorithm for exploration and analysis of attractive areas using collections of geo-tagged photos, in: Proc. 1st Int. Conf. Exhibition Comput. Geo. Research & Appl. (COM.Geo ’10), Washington, DC. pp. 1–4.
  * Kuo et al. [2018] Kuo, C.L., Chan, T.C., Fan, I., Zipf, A., et al., 2018\.  Efficient method for poi/roi discovery using flickr geotagged photos.  Int. J. Geo-Inf. 7, 121\.
  * Kwak et al. [2010] Kwak, H., Lee, C., Park, H., Moon, S., 2010.  What is twitter, a social network or a news media?, in: Proc. 19th Int. Conf. World Wide Web (WWW ’10), Raleigh, NC. pp. 591–600.
  * Laptev et al. [2014] Laptev, D., Tikhonov, A., Serdyukov, P., Gusev, G., 2014\.  Parameter-free discovery and recommendation of areas-of-interest, in: Proc. 22nd ACM Int. Conf. Advances in Geo. Inf. Syst. (SIGSPATIAL ’14), Dallas, TX. pp. 113–122.
  * Larsen and Aone [1999] Larsen, B., Aone, C., 1999.  Fast and effective text mining using linear-time document clustering, in: Proc. 5th ACM Int. Conf. Knowl. Disc. and Data Mining (KDD ’99), San Diego, CA. pp. 16–22.
  * Liu et al. [2012] Liu, J., Huang, Z., Chen, L., Shen, H.T., Yan, Z., 2012\.  Discovering areas of interest with geo-tagged images and check-ins, in: Proc. 20th ACM Int. Conf. Multimedia (MM ’12), Newyork, NY. pp. 589–598.
  * Mathioudakis and Koudas [2010] Mathioudakis, M., Koudas, N., 2010\.  TwitterMonitor: Trend detection over the Twitter stream, in: Proc. ACM Int. Conf. Management of Data (SIGMOD ’10), Indianapolis, IN. pp. 1155–1158.
  * Mislove et al. [2008] Mislove, A., Koppula, H.S., Gummadi, K.P., Druschel, P., Bhattacharjee, B., 2008.  Growth of the Flickr social network, in: Proc. 1st Worksh. Online Social Netw. (WOSP ’08), Seattle, WA. pp. 25–30.
  * Montoliu and Gatica-Perez [2010] Montoliu, R., Gatica-Perez, D., 2010\.  Discovering human places of interest from multimodal mobile phone data, in: Proc. 9th Int. Conf. Mobile and Ubiquitous Multimedia (MUM ’10), Limassol, Cyprus. pp. 1–10.
  * Morstatter et al. [2013] Morstatter, F., Pfeffer, J., Liu, H., Carley, K.M., 2013\.  Is the sample good enough? Comparing data from Twitter’s Streaming API with Twitter’s Firehose, in: Proc. 7th AAAI Int. Conf. Weblogs and Social Media (ICWSM ’13), Cambridge, MA. pp. 400–408.
  * Müller et al. [2001] Müller, K.R., Mika, S., Rätsch, G., Tsuda, K., Schölkopf, B., 2001.  An introduction to kernel-based learning algorithms.  IEEE Trans. Neural Netw. 12, 181–201.
  * Ranacher et al. [2016] Ranacher, P., Brunauer, R., Trutschnig, W., Van der Spek, S., Reich, S., 2016.  Why GPS makes distances bigger than they are.  Int. J. Geo. Inf. Sci. 30, 316–333.
  * Rodriguez and Laio [2014] Rodriguez, A., Laio, A., 2014\.  Clustering by fast search and find of density peaks.  Science 344, 1492–1496.
  * Rossi and Musolesi [2014] Rossi, L., Musolesi, M., 2014\.  It’s the way you check-in: Identifying users in location-based social networks, in: Proc. 2nd ACM Conf. Online Social Netw. (COSN ’14), Dublin, Ireland. pp. 215–226.
  * Sander et al. [1998] Sander, J., Ester, M., Kriegel, H.P., Xu, X., 1998\.  Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications.  Data Mining Knowl. Disc. 2, 169–194.
  * Shin et al. [2015] Shin, W.Y., Singh, B.C., Cho, J., Everett, A.M., 2015\.  A new understanding of friendships in space: Complex networks meet Twitter.  J. Inf. Sci. 41, 751–764.
  * Skovsgaard et al. [2014] Skovsgaard, A., Jensen, C.S., et al., 2014\.  A clustering approach to the discovery of points of interest from geo-tagged microblog posts, in: Proc. 15th IEEE Int. Conf. Mobile Data Management (MDM ’14), Brisbane, Australia. pp. 178–188.
  * Sofean and Smith [2012] Sofean, M., Smith, M., 2012\.  A real-time architecture for detection of diseases using social networks: Design, implementation and evaluation, in: Proc. 23rd ACM Conf. Hypertext and Social Media (HT ’12), Milwaukee, Wisconsin. pp. 309–310.
  * Tan et al. [2013] Tan, R., Gu, J., Chen, P., Zhong, Z., 2013.  Region of interest discovery in location-based social networking services with protected locations, in: Proc. Pacific-Asia Worksh. Intel. and Security Inf. (PAISI ’13), Beijing, China. pp. 9–18.
  * Van Canneyt et al. [2012] Van Canneyt, S., Schockaert, S., Van Laere, O., Dhoedt, B., 2012\.  Detecting places of interest using social media, in: Proc. 2012 IEEE/WIC/ACM Int. Joint Conf. Web Intel. and Intel. Agent Technol. (IAT ’12), Macau, China. pp. 447–451.
  * Viswanath et al. [2009] Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P., 2009\.  On the evolution of user interaction in Facebook, in: Proc. 2nd ACM Worksh. Online Social Netw. (WOSN ’09), Barcelona, Spain. pp. 37–42.
  * Vu and Shin [2015] Vu, D.D., Shin, W.Y., 2015.  Low-complexity detection of POI boundaries using geo-tagged tweets: A geographic proximity based approach, in: Proc. 8th ACM SIGSPATIAL Int. Worksh. Location-Based Social Netw. (LBSN ’15), Bellevue, WA. pp. 1–6.
  * Vu et al. [2016] Vu, D.D., To, H., Shin, W.Y., Shahabi, C., 2016.  GeoSocialBound: an efficient framework for estimating social POI boundaries using spatio–textual information, in: Proc. 3rd ACM SIGMOD Int. Worksh. Managing and Mining Enriched Geo-Spatial Data (GeoRich ’16), San Francisco, CA. pp. 1–6.
  * Xu et al. [2018] Xu, X., Ding, S., Shi, Z., 2018.  An improved density peaks clustering algorithm with fast finding cluster centers.  Knowl.-Based Syst. 158, 65–74.
  * Yang et al. [2017] Yang, Y., Gong, Z., Li, Q., U, L.H., Cai, R., Hao, Z., 2017.  A robust noise resistant algorithm for poi identification from flickr data, in: Proc. 26th Int. Joint Conf. Artificial Intel. (IJCAI ’17), Melbourne, Australia. pp. 3294–3300.
  * Yaohui et al. [2017] Yaohui, L., Zhengming, M., Fang, Y., 2017.  Adaptive density peak clustering based on k-nearest neighbors with aggregating strategy.  Knowl.-Based Syst. 133, 208–220.
  * Ye et al. [2011] Ye, M., Yin, P., Lee, W.C., Lee, D.L., 2011.  Exploiting geographical influence for collaborative point-of-interest recommendation, in: Proc. 34th ACM SIGIR Int. Conf. Research and Dev. Inf. Retrieval (SIGIR ’11), Beijing, China. pp. 325–334.
  * Zhao et al. [2020] Zhao, G., Lou, P., Qian, X., Hou, X., 2020.  Personalized location recommendation by fusing sentimental and spatial context.  Knowl.-Based Syst. 196, 1–12.