Obviousness

Obviousness Analysis of US Patent 11222349 Under 35 U.S.C. § 103

This analysis evaluates the obviousness of US Patent 11222349, "Discovering neighborhood clusters and uses therefor," under 35 U.S.C. § 103, considering prior art available before the patent's priority date of August 30, 2012. The analysis focuses on the independent claims (Claims 1, 13, and 18) and identifies combinations of prior art references that would render these claims obvious to a person having ordinary skill in the art (PHOSITA).

Independent Claims Overview

The independent claims of US Patent 11222349 center on a computer-based system and method for discovering geographic clusters of venues using venue check-in data. Key aspects include:

• Claim 1 (System): A system with a database storing venue check-in data. Processors are programmed to generate a check-in intensity vector for each venue, then a pairwise venue similarity matrix where similarity scores are based on both geographical distance and social distance (determined by common venue visitors). Finally, the system identifies geographic clusters using this matrix.
• Claim 13 (Method): A method mirroring the steps of Claim 1, involving storing data, generating intensity vectors, generating a similarity matrix combining geographical and social distance, and identifying clusters.
• Claim 18 (Computer-Readable Medium): A computer-readable medium storing instructions to perform the method of Claim 13.

The core contribution claimed is the explicit combination of both geographical and social distance in a pairwise venue similarity matrix for the purpose of identifying "neighborhood clusters."

Identified Prior Art References

The patent itself cites several relevant works that predate its priority date, indicating they were known to the inventors and thus constitute prior art:

1. Cheng et al., “Exploring millions of footprints in location sharing services,” AAAI ICWSM, 2011. This reference concerns the analysis of user check-in data from location-based social networks (LBSNs). A PHOSITA would understand that such work involved collecting, storing, and analyzing venue check-in data, and representing venues based on user activity (e.g., "bag of check-ins" or "check-in intensity vectors") to derive social relationships or similarities between venues.
2. D. M. Blei and P. I. Frazier, “Distance dependent Chinese restaurant processes,” J. Mach. Learn. Res., November 2011 (ddCRP). This paper introduced the Distance Dependent Chinese Restaurant Process, a non-parametric Bayesian method for clustering non-exchangeable data. It teaches the use of a "similarity matrix A" to specify prior assumptions about the relationships between items for clustering. The term "distance dependent" suggests the ability to incorporate various forms of distance into the clustering process.
3. Ghosh et al., “Spatial distance dependent Chinese restaurant processes for image segmentation,” Neural Information Processing Systems, 2011. This work extends the ddCRP to hierarchical modeling and applies "Spatial distance dependent Chinese restaurant processes" specifically for image segmentation. Crucially, it demonstrates the explicit incorporation of "spatial distance" within a distance-dependent clustering framework.

Obviousness Analysis

A person having ordinary skill in the art (PHOSITA) in fields such as urban computing, data mining, or location-based services, before August 30, 2012, would have possessed a strong motivation to combine elements from these prior art references to arrive at the claimed invention.

Primary Reference (e.g., Cheng et al.): A PHOSITA would be familiar with systems and methods, as exemplified by Cheng et al., for collecting and analyzing user check-in data from LBSNs. This would teach:

• Storing venue check-in data from multiple users for multiple venues in a geographic region.
• Representing each venue by a "check-in intensity vector" (or "bag of check-ins"), where elements reflect the intensity of check-ins by various users over time.
• Calculating "social similarity" between pairs of venues based on common users visiting them, often using metrics like cosine or Jaccard similarity on these intensity vectors.
• Applying general clustering techniques to group venues based on these social similarities.

Motivation to Combine with Secondary References (Blei & Frazier, Ghosh et al.):

While social similarity is valuable, a PHOSITA attempting to define "neighborhood clusters" would recognize that geographical proximity is an indispensable characteristic of a neighborhood. Clusters based solely on social similarity might group venues that are socially related but geographically distant, which would not accurately reflect conventional neighborhood structures. The patent itself highlights the need to "discover[] neighborhood clusters in a city or other geographic region, where the clusters have a mix of venues and are determined based on venue check-in data" and notes that "Almost always, the geographical proximity of venues is a factor in grouping venues into a cluster".

Therefore, a PHOSITA would be highly motivated to combine geographical information with social similarity to produce more realistic and useful "geographic clusters" or "neighborhoods." The ddCRP framework introduced by Blei and Frazier provided a flexible mechanism for clustering based on a "pairwise similarity matrix" which could incorporate various measures of relationship.

Ghosh et al. further strengthens this motivation and provides a clear technical pathway by explicitly demonstrating the application of "Spatial distance dependent Chinese restaurant processes" for clustering in a spatial context. A PHOSITA would readily understand that the principles of incorporating "spatial distance" into a similarity-based clustering framework, as shown in Ghosh et al. for image segmentation, could be analogously applied to clustering venues in a geographical region.

Combining the Elements for Obviousness:

1. Generating Check-in Intensity Vectors and Social Similarity: A PHOSITA, starting with the teachings of Cheng et al., would generate check-in intensity vectors for venues and compute social similarity scores between venue pairs.
2. Incorporating Geographical Distance into a Pairwise Similarity Matrix: Given the goal of forming "neighborhood clusters" and the existence of "distance dependent" and "spatial distance dependent" clustering methods (Blei & Frazier, Ghosh et al.), a PHOSITA would find it obvious to integrate geographical distance into the similarity matrix used for clustering. Common methods for this integration, as described in US11222349 itself, include:
   • Setting similarity to zero if venues are beyond a certain geographical distance or not among each other's 'm' closest neighbors.
   • Using a decay function of geographical distance to weight the similarity score.
     These techniques for combining distance metrics into an affinity matrix for graph-based clustering were well-known in the art before 2012.
3. Identifying Clusters: Once such a pairwise venue similarity matrix (combining both social and geographical distance) is generated, applying any known graph-based clustering algorithm (e.g., spectral clustering, k-means, hierarchical clustering, all mentioned in the patent as alternatives) to identify the geographic clusters would be a straightforward and obvious step.

Conclusion:

The independent claims of US Patent 11222349, describing a system and method for discovering geographic clusters of venues by generating a pairwise venue similarity matrix that combines both geographical and social distance derived from venue check-in data, would have been obvious to a person having ordinary skill in the art before the priority date. The motivation to combine social and geographical factors for geographically meaningful "neighborhood clusters" is inherent in the problem domain, and the technical means for doing so were readily available through the understanding and combination of prior art such as Cheng et al., Blei & Frazier, and Ghosh et al. These references collectively teach the use of venue check-in data, social similarity derivation, distance-dependent clustering, and the incorporation of spatial distance into clustering algorithms.