UC San Diego

People rapidly learn the capabilities of a new location, without observing every service and product. Instead they map a few observations to familiar clusters of capabilities, and assume the availability of other capabilities in the cluster. This dissertation proposes a similar approach to computer-based discovery of routine location capabilities, applying singular value decomposition to predict unobserved capabilities based on a combination of a small body of local observations and a larger body of data that is not specific to the location. I propose using the time and place of deleting items from a to-do list application to provide the local data. I also examined the effect of feedback on false positive errors, combined with a weighted singular value decomposition. For reminder purposes, an area within easy walking distance is a single location, but may contain many different shops and services, collectively offering its own combination of capabilities. A simple clustering algorithm would treat each combination as an independent cluster. Truncated singular value decomposition maps the observations to combinations of features, rather than to a single cluster. Simulations, using distributions derived from real world data, demonstrate the feasibility of this approach.The robustness of the technique was further tested by adding two difficulties, convenience stores and false training data. The convenience-store workload included some locations that provided only the thousand most frequently used capabilities, regardless of other cluster data. False positive feedback and feature weighting both allowed use of a larger truncation rank, improving convenience store results, and reduced errors due to false training data. The technique extends to estimate whether a capability is available at a given time. Data for short time intervals was "folded-in" to the singular value decomposition to obtain projections for those time intervals. The projections, interpreted as Poisson distribution arrival rates, were used to compare posterior probabilities for various time intervals given the observed data. The time extension was tested with workloads that included 24 hour supermarkets and early opening for a subset of capabilities at one location