Toward Finding Latent Cities with Non-Negative Matrix Factorization
Eduardo Graells-Garrido Diego Caro Denis Parra
cs.SI


Efficient Web Service Composition via Knapsack-Variant Algorithm
    Shiliang Fan^1
Yubin Yang^1,*
    
================================================================




In the last decade, digital footprints have been used to cluster population activity into functional areas of cities.
  However, a key aspect has been overlooked: we experience our cities not only by performing activities at specific destinations, but also by moving from one place to another.
  In this paper, we propose to analyze and cluster the city based on how people move through it. Particularly, we introduce Mobilicities, automatically generated travel patterns inferred from mobile phone network data using NMF, a matrix factorization model.
  We evaluate our method in a large city and we find that mobilicities reveal latent but at the  same time interpretable mobility structures of the city. Our results provide evidence on how clustering and visualization of aggregated phone logs could be used in planning systems to interactively analyze city structure and population activity.






§ INTRODUCTION


The increasing availability of digital footprints, such as Web/App
access logs, user-generated content, and mobile phone network data, has
allowed to characterize the city at spatio-temporal granularities never
seen before. This means that the different functional areas of the city
can be estimated, based not only on how planners thought that the city
would be lived, but on how people actually used the different spaces
available to them <cit.>. However, this is not
enough to understand the city. As Charles Montgomery says in his book,
Happy City: “When we talk about cities, we usually end up talking
about how various places look and perhaps how it feels to be there in
those places. But to stop there misses half the story, because they way
we experience most parts of cities is at velocity: we glide past on the
way to somewhere else. City life is as much about moving through
landscapes as it is about being in them”
<cit.>.

Since people may spend a considerable amount of time while moving
through the city, and the quality of that time has a strong influence on
mood, health, and productivity <cit.>, it is important to
understand city structure with respect to mobility. Given that the
growth of cities is faster than the capability of traditional methods to
understand the city, it is important to have cost-effective ways to
analyze the city at scale <cit.>.

In this paper, inspired by Montogomery's ideas, we estimated a
characterization of the city defined by the collective experience of its
several areas. Particularly, we analyzed intra-city transportation
inferred from mobile phone network records, which we represented in a
Waypoints Matrix. This matrix, similar to document-term matrices
used in Information Retrieval, was decomposed using Non-Negative Matrix
Factorization (NMF) <cit.>. We interpreted and labeled
the obtained components, which we denoted Mobilicities. We
evaluated our pipeline by performing a case study in Santiago, Chile,
using mobile phone network data from the biggest telecommunications
company in the country. Our pipeline delivered interpretable results, in
contrast with a well-established method. We concluded that
mobilicities can be used within an intelligent user interface
aimed at mobility and transportation-analysis tasks.



§ BACKGROUND AND RELATED WORK


There has been a flurry of research of mobile phone network data known
as eXtended and Call Detail Records (X/CDR), as evidenced in
recent surveys on the area
<cit.>. Some examples include:
understanding socio-economic factors on the population
<cit.>, understanding family and social relations
<cit.>, characterizing response to emergencies
and critical events <cit.>, crime detection
<cit.>, credit scoring <cit.>,
test of urban theories <cit.>; and the provision of a
cost-effective way of understanding population dynamics and behavior in
developing countries <cit.>.

The mobile phone network events of a given device depict a
spatio-temporal trajectory that can be processed to infer trips, by
using geometric approaches based on transportation rules
<cit.>, or by clustering events in the trajectory
<cit.>. When individual trips are known, it is
possible to aggregate them into Origin-Destination (OD) matrices. This
analysis is common in the literature from X/CDR
<cit.>,
and shows that inferring individual mobility is a relevant problem.

Other important aspects are the characterization of land use
(e.g., residential areas, business areas, etc.) and
functional areas (i.e., delimited areas that serve specific or
multiple land uses). Since it is crucial to understand the dynamics of
these aspects, functional areas have been measured, monitored and
categorized using digital footprints
<cit.> and X/CDR
<cit.>.
A similar work to ours has applied NMF to understand trip purpose, and
build functional areas based on the spatial distribution of such
purposes <cit.>.

The key difference between the aforementioned work and our proposal is
the focus. Other work focuses on the destinations of trips, as well as
activities performed within places. As such, their definition of
functional area is limited by those places that, in transportation
terms, attract people <cit.>; yet, as mentioned
by urbanists, the city is experienced in sequence by moving from one
place to another <cit.>. Each citizen has an unique
version of the city, built upon the sequence of nodes, landmarks, and
paths traversed <cit.>. In this paper we show that, by
using mobility inferred from X/CDR, and using NMF to decompose/cluster
the different cities experienced by mobile phone users, we are able to
identify the different Mobilicities that comprise a big urban
city.
Even though we have centered the discussion around mobile phone network
data, it is possible to infer transportation and urban patterns from
other sources, particularly social media. Twitter has been shown to
be a good predictor of commuter flows <cit.> at
several scales <cit.>. Now, these approaches have the same
limitation as previous approaches: a focus on the origins and
destinations of trips, mainly due to their way of modelling mobility:
using gravity and radiation models (see <cit.> for a
comparison). Twitter data, while massive and
longitudinal, does not allow to infer within-trip behavior.



§ METHODS


Our methods can be summarized in a pipeline of three steps:


enumi.

  * Trip detection from X/CDR data, which, for each device in the
  dataset, identifies its corresponding daily trips, with origin,
  intermediate, and destination towers.

  * The construction of a Waypoint Matrix W that aggregates the
  intermediate towers of trips, of a given period of time, into a
  device-antenna matrix.

  * The decomposition of W using NMF into the product of two matrices,
  U and T, according to a number of k components, which we
  denote as mobilicities.


Trip Detection. To detect trips from X/CDR traces, we resort to
an algorithm based on transportation rules and trajectory simplification
<cit.>. The algorithm builds a space-time trajectory
from daily X/CDR events, where space is the cumulative distance between
consecutive connected towers, starting from zero at the first connection
of the day. This trajectory is simplified using a line-simplification
algorithm. Then, each segment from the simplified trajectory is
categorized according to transportation rules, such as the relationship
between the approximated trip distance and time, which is visually
inspected through the slope of the segment. In other words, the trip
detection allows us to separate X/CDR events into the following:
stationary events (the user was performing an activity),
trip start events (denoting the origin), trip end events
(denoting the destination), and within-trip events (denoting
mobility).

Building the Waypoints Matrix. Ideally, characterization of
within-trips events does not need to be done using aggregation. For
instance, GPS data allows to do rich clustering over specific
trajectories <cit.>. However, due to the billing
purpose of X/CDR data, it is possible that trips have few within-trip
events because of the billing cycle. Since we will focus on within-trip
events, we need to aggregate such events from an extended period of
time. Furthermore, some trips do not have within-trip events, such as
those with duration near to the billing cycle time, and those within
zones with low tower density. Hence, by aggregating all within-trip
events for a user in a period of time, the likelihood of identifying the
towers that characterize a specific user's mobility increases. We use
this schema to define a Waypoints Matrix W, defined as: 
    w_i,j = # of within-trip events of user  u_i  at tower  t_j/# of within-trip events of user  u_i
 This schema is equivalent to the L1-normalized document-term matrices
found in Information Retrieval, but without weighting with Tf-Idf
<cit.>. We do not apply Tf-Idf because its purpose is
to identify discriminative features; conversely, we want to extract
collective features. Additionally, note that this matrix is different to
those used in related work with NMF decompositions
<cit.>: there is a semantic difference between
within-trips and trip start/end events. To avoid this polysemic
behavior, we focus only on within-trips events.

Applying Non-Negative Matrix Factorization. To represent how users interact
with towers, we propose to decompose this matrix into two:
W = U × T, where U is a |u|× k matrix that encodes
k user latent features for |u| users, and T is a
k × |t| matrix that encode k latent tower features for
|t| different cell phone towers. Note that, by definition, all
w_i,j≥ 0. NMF allows us to decompose the matrix W into two
non-negative matrices, which gives a lower rank approximation for W,
such that W ≈ U × T <cit.>. This can be
formalized as the following optimization problem:
min_U,TW - U × T_F subject to U and T be
non-negative, where number of rows in U and the number of columns in
T correspond to the desired lower-rank approximation k.

Even though there is a variety of methods to decompose matrices, we
choose NMF, which has been applied in similar contexts with
interpretable results <cit.>. Then, we define a
mobilicity m_c as the weighted set of towers within the c
component of the decomposition, i.e., the c-th column of
matrix T. The parameter k must be chosen manually, and its value
should be ideally decided jointly between data scientists and domain
experts according to the context. Previous strategies for choosing
k have focused in measuring the stability of the components
<cit.> and in the variation of the residual sum of
squares curve between the original matrix and its decomposition
<cit.>. However, we prefer to manually
choose the number of components as these methods do not allow us to
incorporate external information such as the socio-economic distribution
of the city.



§ CASE STUDY: SANTIAGO, CHILE




We performed a case study on Santiago, the capital of Chile, with almost
8 million inhabitants. Its urban area covers a surface of 867.75 square
kilometers, and is composed of 35 independent administrative units
called municipalities (c.f. Fig. 1). Because this city has experienced accelerated
growth, and it is expected to keep growing at least until 2045
<cit.>, understanding its structure at scale is an
important and timely task.



 §.§ Datasets


Mobile Phone Network Data.
We studied an anonymized X/CDR dataset from Telefónica Chile, the
biggest telco. in Chile, with a market share of 33% in 2016. The
dataset contained records between July 27th and August 10th from 2016.
In total, we analyzed 124,414 users, who had enough connections to the
cell towers under analysis to estimate their daily trips between 6AM and
midnight, and had either a pre-paid or contract subscription. They
generated an average of 5.33 million billing records per day
(c.f. Fig. <ref>). The average inter-event times
for users range within 14.71 and 30.96 minutes, which shows a billing
cycle between fifteen and thirty minutes.







Telefónica has 1,464 cell phone towers in
the municipalities under consideration. We discarded towers that were
installed in in-door contexts (e.g., malls, hospitals,
etc.). This is possible because tower meta-data includes their
geographical position and their name. For out-door towers, the name
usually contains the nearest crossing, while in-door towers contain the
name of the place they lie in. In total, there were |t| = 1,082
out-door towers (see Fig. <ref>, Towers). The only
in-door towers that we kept were those installed within underground
metro stations.

OpenStreetMap. OSM (<http://openstreetmap.org>) is a
crowdsourced maps platform. We downloaded a dump of its data for Chile,
and then identified the highways within Santiago. We used
this information to contextualize the different mobilicities
identified by the NMF. We did so by finding the out-door towers that lie
within 250 meters of each highway, as shown in Fig.
<ref> (Labeled Towers).



 §.§ Trip Detection and Waypoints Matrix


Using the trip inference algorithm we detected 4,213,400 trips for 124,415 users (c.f. Table <ref> for descriptive statistics). 
Fig. <ref> shows the departure time distribution of all trips. One can see that business days exhibit expected peak-times related to work hours, and that weekends exhibit different patterns, such as a higher density at lunch time.





After detecting trips, we built the W matrix, of dimensions
|u| × |t|. Note that |u| = 95,027, because not all users
had within-trip events. 





 §.§ Factorization of the Waypoints Matrix

To perform the NMF decomposition, we chose
k = 8, because the city is usually divided into six big areas
(north, south, east, west, south-east, center) and, since we expect that
the results exhibit relationship with modes of transportation, we wanted
to see the effect of private and public transportation. Thus, k = 8
is an arguably reasonable choice (note that we discuss the choice of k at the next section).

Tower-Component Matrix.
Figure <ref> shows the results of the factorization, with one map for each component-tower column from the matrix. One can see that there is a strong geographical clustering of towers, which may be explained as W is essentially a co-occurrence matrix.





Fig. <ref> show how the sets of labeled towers (those near highways, near surface metro and within underground metro stations) relate to each component. This allows to see that some components tend to be more associated than others to some modes of transportation: C1, C2, C3 and C7 are more associated to metro than highways, while C4 exhibits the opposite behavior. Having both figures into account, the following is an interpretation of each mobilicity:



  C0: the east side of the city, including part of the center, next to
  the yellow metro line and one important highway of the city. This area
  is characterized for its business districts and high income
  residential areas (c.f. Fig. <ref>). As such, it is likely that its residents do not use
  public transportation, nor visit other mobilicities. Note how metro towers have lower association with this component in Fig. <ref>.

  C1: people that live in the southern part of the city, mostly between
  two metro lines. Since this area is characterized by low income, this means that they need to take
  a bus to reach the metro. 

  C2: the southeast area of the city, which is characterized by their
  dependency of two metro lines. This component contains mixed-income municipalities.

  C3: In contrast with the previous components, this one is completely focused on public transportation: it fully contains two metro lines in full, and partially other two. It also contains bus corridors that tend to connect to metro lines. 

  C4: the northern part of the city, which is mostly residential and of low income. The component also has a main street of the city as a kind of tentacle, showing that people who lives/work in this area, but who work/lives in another, uses this street as a way to get into the component.


  C5: the south-west part of the city, which is connected to downtown primarily
  through a highway and a metro line that is parallel to the highway.


  C6: the western area of the city. This area contains one of the most populated municipalities in the city.

  C7: similar to C6, but extending its reach to center areas of the city through a metro line a bus corridors. This makes this component dependent on public transport, and thus, the routes followed by its inhabitants tend to cluster, in contrast to what happens in C6.


In summary, latent cities seem to be comprised by three kinds of clusters of towers: those where people lives and moves, enclosed by specific limits (C0, C1, C6), those where people lives and work, but in different areas of the city, connected through the transportation network (C2, C4, C5, C7), and transportation infrastructure (C3). 



User-Component Matrix.
The user-component matrix may suggest that users pass through different mobilicities in their daily lives.  Fig. <ref> explores this potential behavior, by displaying how a sample of 25,000 users cluster around the corresponding components. One can see that, indeed, users tend to have a primary component, but they still belong to others. This would be the equivalent to, for instance, living in the suburbs, and having to travel long distances to go to work. Note that many users from C0, the wealthiest part of the city, have negligible association to other components – something expected due to the economical segregation of the city (c.f. Fig. <ref>).






Understanding k.
We showed the eight mobilicities (c.f. Fig. <ref>) to domain experts, who gave informal feedback – it made sense to split the city in this way, as we have interpreted earlier. Even though a formal evaluation with domain experts is left for future work, here we discuss the patterns that emerge when varying the parameter k which is the rank of the factorized matrix. We do so by estimating mobilicities with k' = 4 (c.f. Fig. <ref>) and k” = 12 (c.f. Fig. <ref>).

With four mobilicities, the clustering is mostly geographic: three components split the city. However, the fourth component is related to public transportation: it reconstructs several metro lines and bus corridors. In this aspect, it seems that using k' = 4 allows to obtain a similar result to k = 8.  Then, if one would like to differentiate cell towers with respect to general transportation patterns, this could be a reasonable choice.

With twelve mobilicities, the geographical clustering is still present, but the routes that connect distinct parts of the city become more evident – meaning that a mobilicity is comprised by one or two sectors of close towers (for instance, home and work locations), plus “bridges” that connect one mobilicity to another, based on the common routes followed by people. This behavior is expected, due to the co-occurrence property of the Waypoints Matrix. 

In summary, several values of k allow to infer soft-partitions of the city, as well as the way its inhabitants move between those partitions. A mobilicity may be a soft-partition, a soft-partition with bridges to other mobilicities, or a network of those bridges – namely, a transportation network. 





Comparing Interpretability with PCA/Truncated SVD.
To discuss further whether NMF is a good choice of model in terms of interpretability, we
estimated a Truncated SVD decomposition (equivalent to PCA) with k = 8 . Fig.
<ref> shows that, in contrast to NMF, there is no
geographical clustering nor correspondence to any infrastructure
available in the city. Thus, even though PCA is a widely used dimensionality reduction technique, it does not allow the interpretation nor clustering of the city in the same way as NMF does. 




§ CONCLUSIONS



We proposed the concept of mobilicities, which denotes the
different cities experienced by the inhabitants of a big city, and
depict its dynamics with respect to mobility and usage of modes of
transportation. The suitability of NMF to this kind of spatial data could be related to the fact that NMF is equivalent to spectral clustering <cit.>, which has performed well when grouping trip destination data <cit.>. However, as we have noted in our motivation, our input is not destination nor origin data; instead, it is spatial location while moving. This focus was inspired by the book Happy City <cit.>, reflecting
that our purpose was to help domain experts and policy designers to make
better, happier cities. Such purpose implies collaboration between the emerging
field of data science and the corresponding disciplines – transportation
and urban planning. However, evidence-based policy in those areas requires transparency
and interpretability, and many state of the art machine learning
techniques do not offer both qualities <cit.>. In
this paper, we have shown that NMF does offer both qualities when
applied to mobility data, and thus, is a promising technique to apply in
the field of Urban Computing <cit.>.  



Limitations and Future Work.
Critics may rightly say that we need a well-defined criteria to choose k. Future work should tackle this limitation using intelligent user interfaces aimed at domain experts. This opens two lines of research within the IUI: on the one hand, we could try other factorization methods for positive-only data such as SLIM, which has shown promising results in the past <cit.>, and would allow to understand how the choice of k influences the output and its interpretability. 
On the other hand, visualization and exploratory interfaces are tools
valued by domain experts <cit.>, and mobility has
been a recurring topic in visual analytics <cit.>.
Finally, our work did not consider the temporal aspects of transportation. Hence, future work should consider how to incorporate that dimension into the definition of Mobilicities.

Acknowledgements.
The analysis was performed using Jupyter Notebooks <cit.>, jointly with the scikit-learn <cit.>, pandas <cit.>, and geopandas libraries. The maps on this paper include data from ©OpenStreetMap contributors. We also thank Telefónica R&D in Santiago for facilitating the data for this study, in particular Pablo García Briosso. 
The author Denis Parra has been funded by Conicyt, Fondecyt grant 11150783, as well as Fondef grant id16i10222 and the BRT+ Centre of Excellence funded by VREF.
Finally, we thank the anonymous reviewers for the insightful comments that helped to improve this paper.


plain

