MUTUALLY REPULSING CENTROIDS FOR SEGMENTING A VAST SOCIAL GRAPH
A method of generating a centroid set of mutually repulsing centroids for segmenting a vast social graph is disclosed. Each object of a collection of tracked objects of the social graph is characterized by a respective descriptor vector of multiple descriptor types. Starting with an empty centroid set, an object joins the centroid set as a centroid upon ascertaining that an affinity measure of the object to each centroid of the centroid set is less than a specified affinity threshold. The affinity threshold may be tuned to generate a target number of centroids. The affinity measure may be a dual radial-angular affinity measure. Rather than selecting the centroids from the collection of objects, a distribution function of descriptors of each descriptor type may be determined, candidate descriptor vectors may be generated by random sampling of each distribution, and a candidate descriptor vector joins the centroid set upon satisfying affinity conditions.
1 - 4 . (canceled)
5 . A method of generating centroids of a plurality of objects comprising:
specifying an affinity threshold and employing a processor to execute instructions for:
acquiring a descriptor vector of v variables, v>1, for each object of said plurality of objects;
initializing a centroid set to include an object of said plurality of objects; and
performing for each object of said plurality of objects processes of:
determining an affinity measure to each centroid of said centroid set based on a descriptor vector of said each object and a descriptor vector of said each centroid;
adding said each object as a centroid to said centroid set subject to ascertaining that said affinity measure to said each centroid is less than said affinity threshold;
thereby creating a set of uniformly spaced centroids for use in automated intelligent-marketing systems.
6 . The method of claim 5 wherein said acquiring comprises normalizing said v variables so that a value of each variable is within a predefined range.
7 . The method of claim 6 wherein said normalizing comprises scaling said variables so that a mean value of each variable equals 1.0.
8 . The method of claim 6 wherein said normalizing comprises shifting and scaling said variables so that a minimum value and a maximum value of each variable equal 0.0 and 1.0 respectively.
9 . The method of claim 6 wherein said normalizing comprises shifting and scaling said variables so that a minimum value of each variable equals 0.0 and a maximum value of each variable equals a respective variable-specific positive upper bound not exceeding 1.0.
10 . The method of claim 5 further comprising terminating said performing subject to ascertaining that said set of centroids contains a number of centroids equal to a predefined upper bound.
11 . The method of claims 5 , further comprising:
generating non-repeating randomly sequenced indices of objects of said plurality of objects; and
selecting objects of said plurality of objects at indices corresponding to said randomly sequenced indices.
12 . The method of claim 5 , wherein said determining comprises:
computing a radial affinity level and an angular-affinity level between said each object and said each centroid; and
computing said affinity measure as a function of the radial-affinity level and the angular-affinity level.
13 . The method of claim 12 wherein said function is a weighted sum of the radial-affinity level and the angular-affinity level.
14 . The method of claim 5 wherein:
said affinity threshold comprises a radial-affinity threshold and an angular-affinity threshold;
said determining comprises computing a radial affinity level and an angular-affinity level between said each object and said each centroid; and
said ascertaining comprises verifying that:
said radial-affinity level is less than said radial-affinity threshold; and
said angular-affinity level is less than said angular-affinity threshold.
15 . A method of creating centroids of a plurality of objects comprising:
specifying an affinity threshold and employing a processor to execute instructions for:
acquiring, for each object of said plurality of objects, a respective characterizing vector of v variables, v>1;
deducing for each variable a respective cumulative distribution function to produce v cumulative distribution functions;
generating a succession of descriptor vectors each comprising v variables;
initializing a centroid set to include one of said descriptor vectors;
and
performing for each descriptor vector of said succession of descriptor vectors processes of:
determining an affinity measure to each centroid of said centroid set based on said each descriptor vector and a descriptor vector of said each centroid;
assigning said each descriptor vector to said centroid set as a centroid subject to ascertaining that said affinity measure to said each centroid is less than said affinity threshold;
thereby the method creates a set of uniformly spaced centroids for use in automated intelligent-marketing systems.
16 . The method of claim 15 wherein said generating comprises randomly indexing an inverse of a cumulative distribution function of each variable of the v variables to determine v variable values forming a descriptor vector of said succession of descriptor vectors.
17 . The method of claim 15 wherein said acquiring comprises normalizing each of said v variables to be within a predefined range.
18 . The method of claim 15 wherein said acquiring comprises:
assigning for each variable a respective variable-specific weight greater than 0.0 and not exceeding 1.0; and
shifting and scaling each of said variables so that:
a minimum value of each variable equals 0.0; and
a maximum value of each variable equals a corresponding variable-specific weight.
19 . (canceled)
20 . The method of claim 15 further comprising terminating said performing upon determining that a count of centroids of said set of centroids equals a predefined upper bound.
21 . The method of claim 15 , wherein said determining comprises:
computing a radial affinity level and an angular-affinity level between said each descriptor vector and said each centroid; and
computing said affinity measure as a function of the radial-affinity level and the angular-affinity level.
22 . The method of claim 21 wherein said function is a weighted sum of the radial-affinity level and the angular-affinity level.
23 . The method of claim 15 wherein:
said specifying comprises itemizing said affinity threshold as a radial-affinity threshold and an angular-affinity threshold;
said determining comprises computing a radial affinity level and an angular-affinity level between said each descriptor vector and said each centroid; and
said ascertaining comprises verifying that:
said radial-affinity level is less than said radial-affinity threshold; and
said angular-affinity level is less than said angular-affinity threshold.
24 - 35 . (canceled)
36 . An apparatus for generating centroids of a plurality of objects comprising:
a memory device storing processor executable instructions causing a processor to:
determine an affinity threshold;
acquire a descriptor vector of v variables, v>1, for each object of said plurality of objects;
initialize a centroid set to include an object of said plurality of objects; and
for each object of said plurality of objects:
determine an affinity measure to each centroid of said centroid set as a function of a descriptor vector of said each object and a descriptor vector of said each centroid;
add said each object as a centroid to said centroid set subject to ascertaining that said affinity measure to said each centroid is less than said affinity threshold;
thereby the apparatus creates a set of uniformly spaced centroids for use in automated intelligent-marketing systems.
37 - 40 . (canceled)
41 . The apparatus of claim 36 wherein said processor executable instructions causing to determine an affinity measure further cause said processor to:
compute a radial affinity level and an angular-affinity level between said each object and said each centroid; and
compute said affinity measure as a function of the radial-affinity level and the angular-affinity level.