Discovering neighborhood clusters and uses therefor

• US 9,846,887 B1
• Filed: 08/30/2013
• Issued: 12/19/2017
• Est. Priority Date: 08/30/2012
• Status: Active Grant

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Cranshaw, Justin, Schwartz, Raz, Hong, Jason I., Sadeh-Koniecpol, Norman
• Primary Examiner(s): Gills, Kurtis
• Application Number:
  US14/015,506
• Time in Patent Office: 1,572 Days
• Field of Search: 705 734
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration

Abstract

Computer-based systems and methods for discovering neighborhood clusters in a geographic region, where the clusters have a mix of venues and are determined based on venue check-in data. The mix of venues for the clusters may be based on the social similarity between pairs of venues; or emblematic of certain neighborhood typologies; or emblematic of temporal check-in pattern types; or combinations thereof. The neighborhood clusters that are so discovered through venue-check in data could be used for many commercial and civic purposes.

Claims

1. A computer-based system comprising:

a plurality of electronic location sensors that capture time-stamped location data indicative of the location that venue visitors visit over time;

a computer database system that stores derived venue check-in data based on the time-stamped location data captured by the plurality of electronic location sensors, wherein the venue check-in data comprise venue check-in data from the multiple venue visitors for multiple venues in a geographic region;

a host computer system that comprises one or more processors that are in communication with the computer database system, wherein the one or more processors are programmed to;

generate a check-in intensity vector for each of the multiple venues based on the venue check-in data, each check-in intensity vector comprising a plurality of elements, each element corresponding to one or more venue visitors of the multiple venue visitors, and wherein values for the elements of the check-in intensity vector for a venue is based on at least a measure of intensity of check-ins of the corresponding one or more venue visitors to the venue over a predetermined period of time;

generate elements of a pairwise venue similarity matrix for the multiple venues, each generated element comprising a similarity score indicative of a similarity between a different pair of the multiple venues, wherein the similarity score for a pair of the venues is determined, by the one or more processors, based on at least a measure of the similarity between the check-in intensity vectors for each of the pair of venues; and

determine boundaries for two or more geographic clusters of venues in the geographic region, wherein the geographic clusters of venues are determined based on at least the generated elements of the pairwise venue similarity matrix, wherein each of the two or more geographic clusters of venues comprises a mix of one or more of the multiple venues; and

an analytics server system in communication with the host computer system, wherein in the analytics server system comprises one or more servers that are programmed to receive data about the two or more geographic clusters determined by the host computer system and provide analytics using the two or more geographic clusters determined by the host computer system.

2. The computer-based system of claim 1, wherein the similarity score for a pair of venues is determined based on both a geographical distance between the pair of the venues and a social distance between the pair of venues.

3. The computer system of claim 2, wherein the social distance between a pair of venues is determined, by the one or more processors, based on whether the pair of the venues is visited by common venue visitors in the check-in data.

4. The computer-based system of claim 3, wherein the similarity score for a pair of venues, venue i and venue j, is equal to a similarity measure when venue j is one of the m closest venues to venue i, and equal to zero when venue j is not one of the m closest venues to venue i.

5. The computer-based system of claim 4, wherein the similarity measure is computed based on a cosine similarity between venue i and venue j.

6. The computer-based system of claim 4, wherein the similarity measure is computed based on a Jaccard similarity between venue i and venue j.

7. The computer-based system of claim 3, wherein the similarity score for a pair of venues, venue i and venue j, is equal to a similarity measure when venue j is within a threshold distance r from venue i, and equal to zero when venue j is not within a threshold distance r from venue i.

8. The computer-based system of claim 3, wherein the similarity score for a pair of venues, venue i and venue j, is computed using a decay function that is a function of a distance between venue i and venue j.

9. The computer-based system of claim 2, wherein the similarity score for a pair of venues is determined, by the one or more processors, based on whether the pair of the venues is visited by common groups of venue visitors in the check-in data.

10. The computer-based system of claim 1, wherein:

the computer database system further stores venue category data for the multiple venues that indicate a venue category type for the multiple venues; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of venue category type in the venue category data emblematic of a neighborhood type, such that the mix of venues for each cluster is emblematic of a neighborhood type.

11. The computer-based system of claim 2, wherein:

the computer database system further stores venue category data for the multiple venues that indicate a venue category type for each of the multiple venues; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of venue category type in the venue category data emblematic of a neighborhood type, such that the mix of venues for each cluster is emblematic of a neighborhood type.

12. The computer-based system of claim 11, wherein the mix of venues is determined, by the one or more processors, using inference to compute a probabilistic distribution of venues for each cluster such that the mix of venues for each cluster is emblematic of a neighborhood type.

13. The computer-based system of claim 12, wherein the mix of venues is determined, by the one or more processors, using statistical sampling.

14. The computer-based system of claim 13, wherein the mix of venues is determined, by the one or more processors, using Gibbs sampling.

15. The computer-based system of claim 1, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.

16. The computer-based system of claim 2, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.

17. The computer-based system of claim 10, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.

18. The computer-based system of claim 11, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.

19. The computer-based system of claim 1, wherein the check-in data comprises at least one of check-in data from venue check-in applications and point-of-sale data.

20. The computer system of claim 1, wherein the geographic region comprises a city.

21. The computer system of claim 1, wherein the one or more processors are further programmed to compare the two or more identified geographic clusters of venues in the geographic region based on a similarity of distributions of venue visitors that visit the two or more identified geographic clusters.

22. The computer system of claim 1, wherein the venue visitors comprise persons selected from the group consisting of:

persons that use mobile check-in applications to check into venues;

persons that make electronic point-of-sale transactions that indicate a person was located at a particular venue at a particular time;

persons that indicate a preference for a particular venue through an online venue rating system; and

persons that indicate a preference for a particular venue through an online venue review system.

32. The system of claim 1, wherein the plurality of electronic location sensors comprise mobile computing devices that each executes venue check-in software.

33. The system of claim 1, wherein the plurality of electronic location sensors comprise sensors selected from the group consisting of:

mobile computing devices that each executes venue check-in software;

point-of-sale systems;

cameras;

biometric sensors;

vehicle sensors; and

presence sensors.

23. A computer-implemented method comprising:

storing, in a computer database system, derived venue check-in data that is based on time-stamped location data captured by a plurality of electronic location sensors, wherein the plurality of electronic location sensors that capture time-stamped location data indicative of the location that venue visitors visit over time, such that the derived venue check-in data comprises venue check-in data from multiple venue visitors for multiple venues in a geographic region;

generating, by one or more processors of a host computer system that is in communication with the computer database system, a check-in intensity vector for each of the multiple venues based on the venue check-in data, each check-in intensity vector comprising a plurality of elements, each element corresponding to one or more venue visitors of the multiple venue visitors, and wherein values for the elements of the check-in intensity vector for a venue is based on at least a measure of intensity of check-ins of the corresponding one or more venue visitors to the venue over a predetermined period of time;

generating, by the one or more processors, elements of a pairwise venue similarity matrix for the multiple venues that comprises a plurality of elements, each generated element comprising a similarity score indicative of a similarity between a different pair of the multiple venues, wherein the similarity score for a pair of the venues is determined, by the one or more processors, based on at least a measure of the similarity between the check-in intensity vectors for each of the pair of venues;

determining, by the one or more processors, boundaries for two or more geographic clusters of venues in the geographic region, wherein the geographic clusters of venues are determined based on at least the generated elements of the pairwise venue similarity matrix, wherein each of the two or more geographic clusters of venues comprises a mix of one or more venues; and

transmitting, by the host computer system to an analytics server system that is in communication with the host computer system via an electronic data network, the two or more geographic clusters determined by the host computer system such that the analytics server system is capable of providing analytics using the two or more geographic clusters determined by the host computer system.

24. The method of claim 23, wherein the similarity score for a pair of venues is determined based on both a geographical distance between the pair of the venues and a social distance between the pair of venues, wherein the social distance between a pair of venues is determined, by the one or more processors, based on whether the pair of the venues is visited by common venue visitors in the check-in data.

25. The method of claim 23, wherein:

the computer database system further stores venue category data for the multiple venues that indicate a venue category type for the multiple venues; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of venue category type in the venue category data emblematic of a neighborhood type, such that the mix of venues for each cluster is emblematic of a neighborhood type.

26. The method of claim 23, wherein:

the computer database system further stores venue category data for the multiple venues that indicate a venue category type for each of the multiple venues; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of venue category type in the venue category data emblematic of a neighborhood type, such that the mix of venues for each cluster is emblematic of a neighborhood type.

27. The method of claim 26, wherein the mix of venues is determined, by the one or more processors, using inference to compute a probabilistic distribution of venues for each cluster such that the mix of venues for each cluster is emblematic of a neighborhood type.

28. The method of claim 23, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.

29. The method of claim 24, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.

30. The method of claim 25, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.

31. The method of claim 26, wherein:

the check-in data from the venue visitors comprises check-in time data; and

the mix of venues for each cluster is further determined, by the one or more processors, based on patterns of check-in time in the venue check-in data, such that the mix of venues for each cluster is emblematic of one of a predetermined number of temporal check-in pattern types.