IP Library Granted Patent US 11,842,291
Granted Patent B2
US 11,842,291 · App. 18/062,271 · Granted Dec 12, 2023

Creating a machine learning model with k-means clustering

Inventors: Mingge Deng (Mountain View, CA); Amir H. Hormati (Mountain View, CA); Xi Cheng (Mountain View, CA)
Assignee: Google LLC
G06N5/04G06F7/14G06F16/29G06N20/00
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,842,291
App. No.
18/062,271
Granted
Dec 12, 2023
Kind
B2
Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, that creates a machine learning model with k-means clustering. In some implementations, an instruction to create a model is obtained. A data set including geographic data and non-geographic data is received. The data set includes multiple data entries. Geographic centroids are determined from the geographic data. The data set is analyzed to obtain statistics of the data set. Transformed data is generated from the data set, the statistics, and the geographic centroids. A model is generated with the transformed data, the model indicating multiple data groupings.

Claims (86)

1. A computer-implemented method executed by data processing hardware that causes the data processing hardware to perform operations comprising:

obtaining an instruction to create a model;

receiving a data set comprising geographic data and non-geographic data, the data set having multiple data entries;

determining geographic centroids from the geographic data;

generating transformed data from the data set and the geographic centroids;

determining, using the transformed data, a number of multiple data groupings;

assigning positions to the multiple data groupings;

assigning data entries of the transformed data to a nearest data grouping using an Euclidean distance between the data entries and the positions;

generating the model using the assigned data entries; and

wherein:

assigning the data entries of the transformed data to the nearest data grouping using the Euclidean distance between the data entries and the positions comprises determining total Euclidean distances between the data entries and the position; and

determining the total Euclidean distances between the data entries and the position comprises:

determining Euclidean distances for transformed non-geographic data in the transformed data from each of the positions; and

determining Euclidean distances for transformed geographic data in the transformed data from each of the positions.

2. The method of claim 1 , wherein determining the total Euclidean distances between the data entries and the position further comprises:

aggregating the Euclidean distances for the transformed non-geographic data and the Euclidean distances for the transformed geographic data to obtain the total Euclidean distances;

comparing the total Euclidean distances to identify the positions that are nearest the data entries of the transformed data; and

based on the comparison, assigning the data entries of the transformed data to the multiple data groupings corresponding to the positions that are nearest the data entries of the transformed data.

3. The method of claim 1 , wherein determining the Euclidean distances for the transformed non-geographic data from each of the positions comprises:

determining Euclidean distances for numerical data components in the transformed non-geographic data from each of the positions; and

determining Euclidean distances for categorical data components in the transformed non-geographic data from each of the positions,

wherein aggregating the Euclidean distances comprises aggregating the Euclidean distances for the numerical data components, the Euclidean distances for the categorical data components, and the Euclidean distances for the transformed geographic data to obtain the total Euclidean distances.

4. The method of claim 1 , wherein determining the Euclidean distances for the transformed geographic data from each of the positions comprises:

determining geographic distances between the geographic centroids and each of the positions;

identifying a variance of the geographic data; and

using the variance to standardize the geographic distances,

wherein the Euclidean distances for the transformed geographic data include the standardized geographic distances.

5. The method of claim 1 , wherein generating the model comprises:

for each of the data groupings, determining a geometric center for data entries of the transformed data assigned to the respective data grouping; and

assigning the geometric centers to the data groupings as new positions,

wherein determining the geometric center comprises:

averaging the Euclidean distances for transformed non-geographic data in the transformed data corresponding to the data entries of the transformed data assigned to the respective data grouping; and

averaging the Euclidean distances for transformed geographic data in the transformed data corresponding to the data entries of the transformed data assigned to the respective data grouping.

6. The method of claim 5 , wherein generating the model with the transformed data comprises determining an accuracy of the model.

7. The method of claim 6 , wherein determining an accuracy of the model comprises:

determining that differences between the new positions and the positions meet a first threshold; or

determining that an average quantization error for the data entries of the transformed data assigned to the data groupings at the new positions meet a second threshold.

8. The method of claim 1 , wherein the operations further comprise:

receiving a second data set that includes second data entries;

using the model to assign the second data entries of the second data set to the data groupings;

updating the transformed data using the data set and the second data set; and

updating the model using the updated transformed data.

9. A system comprising:

data processing hardware; and

memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:

obtaining an instruction to create a model;

receiving a data set comprising geographic data and non-geographic data, the data set having multiple data entries;

determining geographic centroids from the geographic data;

generating transformed data from the data set and the geographic centroids;

determining, using the transformed data, a number of multiple data groupings;

assigning positions to the multiple data groupings;

assigning data entries of the transformed data to a nearest data grouping using an Euclidean distance between the data entries and the positions;

generating the model using the assigned data entries; and

wherein:

assigning the data entries of the transformed data to the nearest data grouping using the Euclidean distance between the data entries and the positions comprises determining total Euclidean distances between the data entries and the position; and

determining the total Euclidean distances between the data entries and the position comprises:

determining Euclidean distances for transformed non-geographic data in the transformed data from each of the positions; and

determining Euclidean distances for transformed geographic data in the transformed data from each of the positions.

10. The system of claim 9 , wherein determining the total Euclidean distances between the data entries and the position further comprises:

aggregating the Euclidean distances for the transformed non-geographic data and the Euclidean distances for the transformed geographic data to obtain the total Euclidean distances;

comparing the total Euclidean distances to identify the positions that are nearest the data entries of the transformed data; and

based on the comparison, assigning the data entries of the transformed data to the multiple data groupings corresponding to the positions that are nearest the data entries of the transformed data.

11. The system of claim 9 , wherein determining the Euclidean distances for the transformed non-geographic data from each of the positions comprises:

determining Euclidean distances for numerical data components in the transformed non-geographic data from each of the positions; and

determining Euclidean distances for categorical data components in the transformed non-geographic data from each of the positions,

wherein aggregating the Euclidean distances comprises aggregating the Euclidean distances for the numerical data components, the Euclidean distances for the categorical data components, and the Euclidean distances for the transformed geographic data to obtain the total Euclidean distances.

12. The system of claim 9 , wherein determining the Euclidean distances for the transformed geographic data from each of the positions comprises:

determining geographic distances between the geographic centroids and each of the positions;

identifying a variance of the geographic data; and

using the variance to standardize the geographic distances,

wherein the Euclidean distances for the transformed geographic data include the standardized geographic distances.

13. The system of claim 9 , wherein generating the model comprises:

for each of the data groupings, determining a geometric center for data entries of the transformed data assigned to the respective data grouping; and

assigning the geometric centers to the data groupings as new positions,

wherein determining the geometric center comprises:

averaging the Euclidean distances for transformed non-geographic data in the transformed data corresponding to the data entries of the transformed data assigned to the respective data grouping; and

averaging the Euclidean distances for transformed geographic data in the transformed data corresponding to the data entries of the transformed data assigned to the respective data grouping.

14. The system of claim 13 , wherein generating the model with the transformed data comprises determining an accuracy of the model.

15. The system of claim 14 , wherein determining an accuracy of the model comprises:

determining that differences between the new positions and the positions meet a first threshold; or

determining that an average quantization error for the data entries of the transformed data assigned to the data groupings at the new positions meet a second threshold.

16. The system of claim 9 , wherein the operations further comprise:

receiving a second data set that includes second data entries;

using the model to assign the second data entries of the second data set to the data groupings;

updating the transformed data using the data set and the second data set; and

updating the model using the updated transformed data.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 6, 2022
From: DENG, MINGGE; HORMATI, AMIR H.; CHENG, XI
To: GOOGLE LLC
Reel/Frame 061996/0321 →
Continuity (3)
Continuation 16843371 · Apr 8, 2020
Provisional Application 62831031 · Apr 8, 2019
Related Publication 20230094005A1 · Mar 30, 2023