Patent ID: 11928159
Assignee: GOOGLE LLC
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 10:
11. A computing system for generating a machine-learned model based on performing clustering with improved privacy, the computing system comprising:
one or more processors; and
one or more non-transitory computer-readable media that store instructions that, when executed by the one or more processors, cause the computing system to perform operations, the operations comprising:
obtaining data descriptive of a plurality of input datapoints expressed in a first dimensional space;
projecting the plurality of input datapoints into a second dimensional space that has a fewer number of dimensions than the first dimensional space;
generating in the second dimensional space a coarse centroid set for the plurality of input datapoints, wherein generating the coarse centroid set comprises, for each of a plurality of iterations:
defining, by the computing system, a plurality of subsets of neighboring datapoints respectively for the plurality of input datapoints, wherein the respective subset of neighboring datapoints for each input datapoint includes all input datapoints in a cover within a threshold distance of the input datapoint;
performing a sparse selection technique on the plurality of subsets of neighboring datapoints to select an additional candidate center; and
removing points within a distance of the additional candidate center;

transforming the coarse centroid set into a coreset;
performing a clustering algorithm on the coreset to determine the plurality of clusters;
determining a respective cluster center within the first dimensional space for each of the plurality of clusters based on a DensestBall algorithm and the plurality of clusters; and
training the machine-learned model by updating one or more parameters of the machine-learned model, wherein updating the one or more parameters is based on employing the respective cluster center for each of the plurality of clusters to evaluate a loss function of the machine-learned model.