Matching projects to land use codes using a graph of word embeddings
Sam Zhang
Open Counter Enterprises Inc.
[email protected]
Linh Vuong
Open Counter Enterprises Inc.
[email protected]
Joel Mahoney
Open Counter Enterprises Inc.
[email protected]
ABSTRACT
According to the World Bank, the United States is 49th in the world for ease of starting a business, 37th for ease of registering prop- erty, and 36th for ease of dealing with construction permits. These rankings reect ineciencies in state and local government, whose regulations dictate a wide range of permitting requirements, and whose implementation of these rules can vary widely. By applying a novel approach using a graph of word embeddings to select land use codes, we streamline a small but important step in the overall permitting process, which can have an outsized impact on the cost and complexity of commercial and residential projects. We have deployed this as the ocial business permitting software for over 40 jurisdictions, including San Diego, Oakland, and Salt Lake City.
CCS CONCEPTS
•Computing methodologies → Articial intelligence; •Applied computing → Computers in other domains ; • Information sys- tems → Information retrieval;
KEYWORDS
applied data science, civic tech, word embeddings, natural language processing, NLP, machine learning, urban planning, zoning ACM Reference Format:
Sam Zhang, Linh Vuong, and Joel Mahoney. 2018. Matching projects to land use codes using a graph of word embeddings. In Proceedings of KDD ’18 (KDD 2018 Applied Data Science). ACM, New York, NY, USA, 6 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn
1 INTRODUCTION
There are two common approaches to the practice of zoning in America: form-based and Euclidean zoning. Form-based zoning regulates the built environment by dening building types and physical features that are allowable in a given area. Euclidean zon- ing1 relies on a classication system known as "land uses, " which dene the activities that are allowable in a given location.
Land uses are typically organized into categories and subcat- egories. Categories cover topics such as "Commercial", "Indus- trial", and "Residential", while subcategories cover areas such as 1Named after the town of Euclid, Ohio, defendant in the 1926 Supreme Court case that established the constitutionality of zoning practices [6].
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for prot or commercial advantage and that copies bear this notice and the full citation on the rst page. Copyrights for third-party components of this work must be honored.
For all other uses, contact the owner/author(s).
KDD 2018 Applied Data Science, August 2018, London, UK
© 2018 Copyright held by the owner/author(s).
ACM ISBN 978-x-xxxx-xxxx-x/YY/MM.
https://doi.org/10.1145/nnnnnnn.nnnnnnn
"Light Manufacturing", "General Retail", and "Animal Services. " Individual land uses become as specic as Auto Muler - Instal- lation And Sales Only or even Manufacture of cereals, dis- tilled liquors, felt or shoddy, hair or hair products, pickles, sauerkraut, vinegar, yeast, soda or soda compounds, struc- tural clay products, meat products, not including any use rst specically listed below.
Some more examples of use codes
are provided in Table 1.
There are several factors that make it selecting the appropriate land use a challenge. Firstly, land uses vary widely by region, based on geographic and economic factors. For example, coastal commu- nities have uses related to their lakes and oceans (e.g. Marina or Boat Service), whereas agricultural communities have uses related to farming and food processing (e.g. Feed Lot or Hog Farrowing).
These regional variations make it dicult to dene a one-size-ts- all classication system2. There is no standard name for the same economic activity either. In Table 2, we illustrate some ambiguous categorizations of popular business types.
Secondly, land use codes can become outdated as economic ac- tivities evolve. Terminology can change, and the land use options can become outdated. Consider uses like San Francisco’s "Wool Pulling and Scouring" (an unlikely category for Silicon Valley star- tups), or "Drive-in Theatre. " These uses are likely to be irrelevant for most applicants, but add complexity to the classication system.
Even when older use codes are still relevant, it can be dicult to understand how modern uses should map to the existing options.
For example, it might not be immediately clear to a pilates studio owner that the best land use option for their business is Group Fitness Facility.
Lastly, land uses often include conditional options, which can add complexity to an otherwise straightforward selection. Consider the choices for "Restaurant" in Pacic Grove, California:
• Restaurant, fast food (non formula, no alcohol)
• Restaurant (formula or non formula)
• Restaurant (non formula)
• Restaurant (formula or non-formula, w/ alcohol)
• Restaurant (formula or non formula, w/ no alcohol)
• Restaurant (specialty, non formula, w/ beer and wine) • Restaurant (specialty, w/ no alcohol sales)
• Restaurant with a drive through (non formula, no alcohol) All of these details add complexity to a critical step in the per- mitting process, the stakes of which are high: a poor choice of land use can mean that your project will be prohibited at your chosen location, or that the permits required at this location will be more expensive. It also increases the diculty of turning a local 2The North American Industry Classication System is the best attempt [ 11], but the list is long, and the options are generally inapplicable.
Attachment D
KDD 2018 Applied Data Science, August 2018, London, UK Sam Zhang, Linh Vuong, and Joel Mahoney Table 1: Example use codes
Category Subcategory Name
Commercial Retail General Administrative
Commercial Services Group Fitness Facility
Recreation Public Assembly Recreation
Table 2: Ambiguous use codes
Common Term Legal Term 1 Legal Term 2
Cafe Eating and Drinking Facility Bakery
Gym Fitness Facility Health Center
Salon Personal Services Spa
Yoga Instructional studio Studios for dance
Table 3: Example deployed business portal sites
Jurisdiction Site
San Diego https://business.sandiego.gov
Santa Cruz https://opencounter.cityofsantacruz.com
Oakland https://oakland.opencounter.com
Salt Lake City https://slcgov.opencounter.com
solution for a particular jurisdiction into a global solution for any jurisdiction.
OpenCounter attempts to simplify the land use selection pro- cess by allowing applicants to search for common business types (pilates studio, cafe, etc.) and returning an appropriate selection of land use codes oered by the jurisdiction. This requires a nuanced approach to keyword mappings, given the diversity of options in each jurisdiction’s land use classication scheme.
This paper presents an algorithmic approach to handling the long tail of ambiguous classications without requiring sta discretion each time. For example, Chinese food, takeout, sushi, and tacos would all lead to use codes related to restaurants and food service without having to add each term individually.
The system has been deployed in over 40 jurisdictions. A few deployments are listed in Table 3.
2D A T A
OpenCounter oers local governments an applicant-facing busi- ness portal that simulates the experience of interacting with an employee at a permitting desk. To do this, each jurisdictions’s busi- ness permitting legislation is translated by a team at OpenCounter into a domain-specic language, which are represented in the portal ow as questions. The rst question that the applicant must answer is their project type, which is the query used to determine their land use code, because the land use is central to almost all of the permits and fees.
The land uses themselves are broken up into categories, subcate- gories, and names, as shown in Table 1. Municipalities with only a category and a name have an empty subcategory. Each land use may optionally include a description, as well as zero, one, or many sets of keywords to emphasize dierent semantic dimensions of the use code. The digitized land uses are available as a free online API at https://zoning.io.
We use a pre-trained model of the top 400,000 thousand words from English Wikipedia from the GloVe implementation of word embeddings [12]. Word embeddings are continuous vector repre- sentation of otherwise highly sparse text datasets. They have been shown to perform well on semantic similarity tasks [9] [12]. 3 MOTIV ATION
The solution of using a graph of word embeddings arises out of several considerations:
(1) Jurisdictions have requested we save applicants’ self-described project types so they can study how local business is chang- ing over time. This rules out OpenCounter’s previous itera- tion, an autocomplete search, which does not encourage the user to write out a complete project type before selecting an option.
(2) We want the user to be able to specify project types in their own words, rather than requiring them to learn the legalese in advance.
(3) Jurisdictions have slightly (and sometimes very) dierent sets of use codes from one another. They vary in quantity, detail, and even taxonomy. Therefore we cannot create a one-size-t-all multinomial classication solution that maps project types onto a single standard.
(4) The structure of the use codes across jurisdictions, although dierent, oers valuable similarities. We seek to exploit these similarities as a form of prior information.
(5) The smallest municipalities that use OpenCounter may only receive several applications a week. Furthermore, search trac is heavily concentrated toward a few popular use
codes. This makes it unfeasible to rely on data collected from live applicants to drive the algorithm.
(6) OpenCounter adds jurisdictions to its system at a rapid pace.
To require a large amount of human annotation for each new jurisdiction would be costly. Therefore we want the system to handle most English queries without requiring explicit annotation.
(7) The existing jurisdictions in OpenCounter may change their use codes or other municipal ordinances. The use code search needs to adapt to revised data as automatically as possible, to lower maintenance costs.
4 METHODOLOGY
On the rst interactive page of the OpenCounter business and zon- ing portals, the applicant is prompted to enter a project type. This is similar to what an applicant may be asked at a local permitting oce, and the user is expected to answer similarly. We prompt the user using a scrolling placeholder of common project types, such as cafe, yoga studio, and restaurant. We refer to the applicant’s project type as the query.
We perform two dierent query expansions – techniques that increase the surface area of the query [8]. When the applicant enters their query, the query is embedded into a continuous word vector model trained on English Wikipedia, augmenting their query with Attachment D
Matching projects to land use codes using a graph of word embeddings KDD 2018 Applied Data Science, August 2018, London, UK the semantic information from the model. This is similar to the approach in Diaz et al . [5], but we found it advantageous to use a global rather than domain-specic corpus, since our problem space requires reaching outside of the legal vocabulary of the municipal codes themselves.
The second query expansion relies on the similarities of use codes across jurisdictional lines. We construct a graph, explained below, and use it to expand the query with information from the closest matching use codes across the country. One jurisdiction may dene their use code for oce to be Commercial > Retail > Administrative, while another denes it as Commercial > Re- tail > Oce Administrative . We allow the existence of the more detailed use code to inform searches in the less detailed use code’s jurisdiction.
4.1 Embedding the use codes
OpenCounter services a set of over 40 jurisdictions , such as San Diego, Oakland, and Salt Lake City. Each jurisdiction j 2 has its own set of use codes Uj , which partition the set of all sets of use codes in OpenCounter U . Each use code has associated with it one or more keyword sets, [k1, k2,. . . ,kn ]. This is common for broad use codes, such as Commercial > Personal Services , which may refer to many dierent uses whose names may not be close in the vector space. We embed each keyword set as a point in the GloVe vector space.
Each use code begins as a bag of words representation,
[w0, w1,. . . ,wn ], (1)
which are a tokenized and preprocessed list of the parts of the use code shown in Table 1. Each keyword setki is then an additional bag of words [w0, w1,. . . ,wm ], with zero or more words, appended onto the original use code words. Thus we end up with m vectors, one for each keyword set, that overlap insofar as they share the vocabulary from the use code itself. This is transformed into a bag of vectors [p0, p1,. . . ,pn+m ] by embedding each word with the word vector model. We do not remove duplicate words, since they convey a meaningful emphasis on certain terms.
Each use code u 2 Uj is then represented as one or more tuples of (j, Æ ), with jurisdiction j and use and keyword vector Æ :
Æ = 1
n + m
n+m’
i=0
pi ⇤ id f (wi ), (2)
where id f is the inverse document frequency of a word across all OpenCounter jurisdictions.
Since we are only using the word embeddings to provide a dis- tance metric between words, we trade the ability to do semantic arithmetic for a degree of robustness against the Curse of Dimen- sionality by projecting the vectors onto a hypersphere [3].
When an applicant enters a search term into the search engine, we transform their query into a tuple (t, Æq), where t is the juris- diction of the applicant, and Æq the query transformed into a single vector using Equation 2.
4.2 Exploiting the use code graph
The similarities of use codes across jurisdictions oer structural information about the space of use codes that we exploit. We nd the closest use codes to the query across any jurisdiction, then the closest use code in the target jurisdiction from that intermediate use code.
We notice poor performance subjectively nding the direct dis- tances between the query and the uses in the target jurisdiction:
dists = {D(Æq, u), 8u 2 Ut }. (3)
We hypothesize this may be caused by the sparsity of certain ju- risdictions’ land use codes. For example, if the use for oce is spec- ied as Commercial > Administrative > General rather than Commercial > Administrative > Oce as it is in some jurisdic- tions, then the word oce may not match to that use code name as clearly.
To resolve that problem, we generalize our view of the problem to see that the direct search is a minimization of the path n’
i=0
pi ; pn 2 Ut , p0 = Æq, (4)
where p is the query vector.
By the triangle inequality, the objective function in Equation 4 always chooses the great circle distance across the hypersphere between
Æq and its nearest point in Ut . Instead, to encourage the system to make use of the prior structure within the graph, we begin by minimizing each step
D(pi , pi+1 |u 2 U , u < {p0, p1,. . . ,pi }). (5)
This opens up a potentially large search tree, but we nd it sucient to perform only two steps. For each u 2 U , we memoize the shortest path between each use and each other jurisdiction m(u, j) = ar min{D(u, uj )|uj 2 Uj , j 2 }. (6)
Then pn = p2 = m(p1, t). The nal score is created through a linear combination of Equations 4 and 6,
s(Æq, j) = c ⇤ D(Æq, p1) + m(p1, j), (7)
where c is a constant that dampens the tendency to jump directly to the searched jurisdiction.
This creates a precomputed graph G of size |U |⇥| 1|, where for every given use code, we nd the closest use code in every other jurisdiction. When the applicant makes a query, this graph nds distances to results in the applicant’s jurisdictions intermediated by this graph. This is what we call query expansion over the graph of word embeddings.
4.3 Productionization
The models were developed in Python using gensim [ 13], but to avoid maintaining a microservice in a separate programming lan- guage than our existing Rails application, we migrated the word vectors into Postgres to use with ActiveRecord. We store the data using the Postgres "cube" extension, which provides us with a hy- percube data structure as well as performant distance functions.
Attachment D
KDD 2018 Applied Data Science, August 2018, London, UK Sam Zhang, Linh Vuong, and Joel Mahoney Table 4: Common project types for evaluation
Cafe Dry clean Day spas
Restaurant Laundry Massage
Sandwich shop Laundromat Dentist
Juice bar Pet hotel Clinic
Brewery Auto repair Doctors oce
Winery Tune up Acupuncture
Bakeries Auto service Chiropractor
Cake shop Auto detailing Counseling
Donut Auto upholstery Boutique
Coee and tea Towing Baby clothes
Cupcake Bowling Furniture
Ice cream Gym Store
Salon Yoga Beauty supply
Blow-dry bar Pilates Eyeglass shop
Hair Co-working space Clothing store
Tattoo Escape games Garden supplies
Piercing Paintball Grocery store
5 EV ALUATION
We evaluate the performance of the use code search with two dierent methods: validation against labeled truth data, and analysis of user behavior.
5.1 Labeled truth data
We took a list of 51 project types that the OpenCounter accounts team anticipated to be common queries (Table 4). We selected a jurisdiction at random – Riverside, California – and out of its 129 use codes, manually selected up to three use codes that t each project type. Often a project type is not enough to select a single unambiguous land use. This set of truth data only consisted of 26 unique use codes, showing that at least in Riverside, only a fth of the use codes were anticipated to receive heavy usage. 3 We then evaluated our search engine using those predened queries and results, allowing each query to return up to ve results, as on the live website. The process was repeated for several varia- tions on the search algorithm. The system was evaluated for the proportion of relevant items that were retrieved (recall) but not for the proportion of retrieved items that were relevant (precision) [ 8], since the degree to which users use OpenCounter for exploratory planning of potential businesses is still unknown.
The three search methods we tested were:
(1) Substring match. This is similar to an autocomplete-based search system in a previous version of the OpenCounter busi- ness portal. We return any land use codes whose category, subcategory, and name contain the lowercased query text. (2) Direct search. This uses word vectors to nds the shortest path between the query and the use codes in the target
jurisdiction Uj without any intermediate graph search.
3The evaluation does not include any residential uses because the OpenCounter business portal does not include residential permits. This excludes 15 of the 129 use codes in Riverside. These residential use codes do appear in the search results for zoning purposes, however, and they are popular among users.
Table 5: Results of evaluation
Recall all Recall one
Substring Search 0.036 0.059
Direct Search 0.747 0.863
Graph Search 0.747 0.902
(3) Graph search. This uses the graph of word vectors to hop through zero or one use codes in other jurisdictions as a form of query expansion.
We evaluated recall on two metrics: recall of all of the relevant results for each use code (recall all ), and recall of any of the relevant results for each use code (recall one ). Queries that failed to return any results under the recall one criteria are italicized in Table 4, and results are in Table 5.
The graph search found at least one of the correct uses for 90.2% of the project types, and the direct search found at least one for
86.3%. The direct substring match performed extremely poorly, matching only 5.9%.
Since the particular choice of jurisdiction for evaluation was random, we expect the dierence between the direct search and graph search may be larger in a jurisdiction with a less detailed use code table than Riverside.
Evaluating the use code search against a xed set of labeled truth data enables a rigorous baseline for the system, but as a global measurement of system performance, it is dicult to interpret for the following reasons:
(1) The system depends on the graph of all use codes U , which is updated every time OpenCounter adds a new jurisdiction. (2) The human in the loop adds keyword sets to use codes to improve the quality of the search, especially around ambigu- ous use codes like
Commercial > Personal Services which
may have dierent keyword sets for tailor, barber, life coach, etc.
Since there is a direct trade-o between the amount of human annotation that goes into the system, and the quality of the results, we present these results without using any keyword sets whatso- ever. Thus these results serve as a lower bound on the quality of the search engine, especially since many of the popular queries require more annotation around the dierent inections of Commercial > Personal Services.
5.2 Analysis of user behavior
To assess the performance of the use code search on live data, we gathered metrics on:
(1) The distribution of number of searches that a user performs in a session.
(2) The percent of users who select a use code without resort- ing to the use code browser. We only display the use code browser after a search is made, so we can use the browsing of the use code table as a heuristic for people who gave up on the search itself.
A total of 10,795 unique applicant sessions have searched for a use code since we rst launched this feature. Out of those sessions, 3,441, or 31.8%, chose to browse the entire use code table as well.
Attachment D
Matching projects to land use codes using a graph of word embeddings KDD 2018 Applied Data Science, August 2018, London, UK Figure 1: Distribution of number of searches per session.
In Figure 1 the distribution of the number of searches performed in each user session is shown. Dots are placed on the rst ten data points, i.e., the cumulative percent of searches that end with one through ten searches or less. Around 95% of users search less than ve times, and 58% only search once during their session. A long tail exists of a handful of users who use the search feature upwards of a hundred times.
The tail of the number of searches performed in a session is long partly because of city sta assessing the system. City sta will often toggle between the use code search and the zoning map to look at how OpenCounter maps the zones of all of their use codes. Likewise, a proportion of the use code browser trac may be attributable to city sta as well.
6 DISCUSSION
The results suggest that machine learning systems can be deployed with success at the level of local government, surmounting chal- lenges of legislative complexity and bureaucracy. Rather than per- forming extensive research on land use regulations, or taking a trip down to city hall during business hours, applicants attempting to start a business are able to query a city website with a plain-text "project type" and receive an immediate response. Some pursue iterative exploration with the search, by modifying their query and searching again, but 95% of applicants search less than ve times.
The users in the 5% who search more than ve times form a long tail in total number of searches. In user research, we observe a subjective quality of fascination that these users have with the search interface. Many of these users are city sta, whom we ob- serve exploring the depths and boundaries of the system with a broad range of queries. These users often select a use code, pro- ceed to the next page, which shows an interactive map of their jurisdiction with the zones drawn, and backtrack to perform a new search to look at the map anew. This suggests that our machine learning approach toward land use is deeply novel, and presents to experienced zoning professionals an invitation to reason with their domain dierently. Indeed, the feedback we have received from city sta has been overwhelmingly positive.
In addition to the obvious benets to applicants and city sta, machine learning systems like these present strategic advantages for local government as well. It has been noted that the biggest challenges that local governments face with open data initiatives are decentralized data storage, external data sourcing, and not using data as part of the core process of public service [ 4]. By streamlin- ing permitting and other workow through data-driven tools like this, local governments can much more easily respond to records requests and fulll open data initiatives.
6.1 Future directions
We embed use codes into vectors by performing a tf-idf combination over the individual word vectors, which is unable to capture the semantics of phrases like soup kitchen and day spa. Use of embedded phrases [10] or paragraphs [ 7] instead of words may provide an immediate improvement on the quality of phrases.
OpenCounter is about to release a residential permitting portal for local governments. The use code search already indexes resi- dential land uses. Since homeowners are not looking to develop housing, a future direction is to apply a similar approach to match residential project types such as plumbing, fence work, and pool installation with their permits directly.
The ability to map unstructured project types to use codes presents possibilities for work on creating an empirically-based hierarchi- cal land use code standard. This work open the possibility for a data-driven descriptive, rather than prescriptive, land use standard that can be used in conjunction with the ocial municipal codes of diverse jurisdictions.
7 CONCLUSION
The US Census estimates that 1.2 million building permits were issued for privately-owned housing units in 2016, with a valuation of $237.1 billion [ 2]. The Small Business Administration estimates that over 500,000 new businesses opened in 2010, with this number growing to nearly 650,000 in 2013 [ 1]. For each of these residential permits and new businesses, OpenCounter could have provided essential information in a signicantly more user-friendly man- ner than what currently exists. Since November 2017, over 35,000 zoning lookups have been performed in OpenCounter’s tool; the median time to scope a project is 9 minutes, but over 50% of all lookups are done in 6 minutes or less. We believe that small im- provements to the mechanics of the permitting process can have a signicant eect on the ease of starting commercial and residential projects, which in turn will aect economic data in the region. It is not inconceivable that these improvements can therefore im- pact macroeconomic performance, and improve the United States’ ranking as compared to other advanced economies in the world.
To that eect, we deploy a search engine for land use codes that is currently being used by 41 municipal governments, with more jurisdictions added continuously. It embeds land use codes into a continuous vector space, and exploits the similarities between use code tables across jurisdictions to expand the search query.
This represents an unprecedented step in digitizing the municipal Attachment D
KDD 2018 Applied Data Science, August 2018, London, UK Sam Zhang, Linh Vuong, and Joel Mahoney code and introducing machine learning-driven technology to local government.
ACKNOWLEDGMENTS
The authors would like to thank Matthew Conway for feedback, and Philip Hale for support with data analysis.
The authors would also like to thank the anonymous referees for their valuable comments and helpful suggestions. The work is supported by Open Counter Enterprises Inc.
REFERENCES
[1] 2015. Small Business Proles for the States and Territories. Technical Report. U.S.
Small Business Administration.
[2] 2016. Annual Building Permits. Technical Report. U.S. Census Bureau. [3] Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. 2001. On the surprising behavior of distance metrics in high dimensional space. InInternational conference on database theory. Springer, 420–434.
[4] Peter Conradie and Sunil Choenni. 2014. On the barriers for local government releasing open data. Government Information Quarterly 31 (2014), S10–S17. [5] Fernando Diaz, Bhaskar Mitra, and Nick Craswell. 2016. Query expansion with locally-trained word embeddings. arXiv preprint arXiv:1605.07891 (2016). [6] Timothy Alan Fluck. 1986. Euclid v. Ambler: a retrospective. Journal of the American Planning Association 52, 3 (1986), 326–337.
[7] Quoc Le and Tomas Mikolov. 2014. Distributed representations of sentences and documents. In International Conference on Machine Learning. 1188–1196. [8] Christopher D Manning, Prabhakar Raghavan, Hinrich Schütze, et al . 2008. Intro- duction to information retrieval. Vol. 1. Cambridge university press Cambridge. [9] Tomas Mikolov, Kai Chen, Greg Corrado, and Jerey Dean. 2013. Ecient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013).
[10] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Je Dean. 2013.
Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems. 3111–3119. [11] John B Murphy. 1998. Introducing the North American industry classication system. Monthly Lab. Rev. 121 (1998), 43.
[12] Jerey Pennington, Richard Socher, and Christopher Manning. 2014. Glove:
Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 1532–1543. [13] R Rehurek and P Sojka. 2011. Gensim–python framework for vector space modelling. NLP Centre, Faculty of Informatics, Masaryk University, Brno, Czech Republic 3, 2 (2011).
Attachment D