Composite Radial-Angular Clustering Of A Large-Scale Social Graph
A method of segmenting a large number of objects representing tracked-users of a network into a number of clusters is disclosed. Each object is represented by a multi-dimensional vector representing descriptors of the object. An object is assigned to a particular cluster according to the radial distance to, and the angular displacement from, a centroid vector of the particular cluster.
1 . A method of clustering a plurality of objects comprising:
configuring at least one hardware processor to perform processes of:
generating a set of K centroids, K>1;
assigning each centroid to a respective cluster of a set of K clusters;
selecting objects of said plurality of objects in a predetermined order and for each object of said plurality of objects:
evaluating a composite affinity measure to each centroid of the K centroids based on a radial-affinity measure and an angular-affinity measure to said each centroid;
identifying a particular centroid of highest composite affinity measure;
assigning said each object to a particular cluster corresponding to the particular centroid; and
updating said particular centroid to a respective updated centroid to account for inclusion of said each object;
and
storing identifiers of objects assigned to said each cluster.
2 . The method of claim 1 wherein said each object is characterized by a respective vector of descriptors and said updating comprises steps of:
maintaining a count of current objects assigned to said particular cluster;
maintaining a vector sum of vectors of descriptors of said current objects; and
determining said respective updated centroid as said vector sum divided by said count.
3 . The method of claim 1 further comprising:
assigning to said each object a respective weight; and
establishing said predetermined order as a descending order according to weight.
4 . The method of claim 1 further comprising executing multiple cycles of said selecting, evaluating, identifying, assigning, and updating for said each object with the predetermined order for any cycle differing from the predetermined order for any other cycle of the multiple cycles.
5 . The method of claim 4 further comprising, for each cycle of said multiple cycles:
generating a respective pseudo-random sequence of different integers corresponding to memory addresses of vectors of descriptors of said plurality of objects; and
establishing said predetermined order according to said respective pseudo-random sequence.
6 . The method of claim 1 further comprising:
maintaining object-assignment records indicating for each object:
an identifier of a cluster to which said each object is assigned; and
a corresponding composite affinity measure;
executing a specified number of cycles of said selecting, evaluating, identifying, assigning, and updating for said each object of said plurality of objects; and
executing each of a specified number of succeeding cycles of said selecting, evaluating, identifying, assigning, and updating for only each object of a composite affinity measure below a specified level.
7 . The method of claim 1 further comprising:
determining an overall number of changes of object assignments to clusters for a cycle of said selecting, said evaluating, identifying, assigning, and updating for said each object; and
while a ratio of said overall number to a total number of objects of said plurality of objects exceeds a predefined threshold repeating said cycle at most a predefined number of times.
8 . The method of claim 1 further comprising determining each of said radial-affinity measure, said angular-affinity measure, and said composite affinity measure as a normalized value bounded between 0 and 1.0.
9 . The method of claim 1 wherein:
said angular affinity measure is determined as a dot product of vectors (C/∥C∥) and (P/∥P∥);
said radial affinity measure is determined as a ratio ∥P∥/(∥P∥+D); and
said composite affinity measure is a weighted sum of said angular affinity measure and said radial affinity measure;
where C denotes a centroid vector of said each centroid, P denotes an object vector of said each object vector, ∥C∥ denotes magnitude of C, ∥P∥ denotes magnitude of P, and D denotes the Euclidean distance ∥(P−C)∥.
10 . The method of claim 1 wherein:
said angular affinity measure is determined as a dot product of vectors (C/∥C∥) and (P/∥P∥);
said radial affinity measure is determined as (1−D/D*) for D<D* and 0.0 otherwise; and
said composite affinity measure is a weighted sum of said angular affinity measure and said radial affinity measure;
where C denotes a centroid vector of said each centroid, P denotes an object vector of said each object vector, ∥C∥ denotes magnitude of C, ∥P∥ denotes magnitude of P, and D denotes the Euclidean distance ∥(P−C)∥, and D* is a predefined distance threshold, D*>0.
11 . A system of clustering a plurality of objects comprising:
at least one hardware processor and at least one memory device storing processor readable instructions causing the at least one hardware processor to:
generate a set of K centroids, K>1;
assign each centroid to a respective cluster of a set of K clusters;
select objects of said plurality of objects in a predetermined order and for each object of said plurality of objects:
evaluate a composite affinity measure to each centroid of the K centroids based on a radial-affinity measure and an angular-affinity measure to said each centroid;
identify a particular centroid of highest composite affinity measure;
assign said each object to a particular cluster corresponding to the particular centroid; and
update said particular centroid to a respective updated centroid to account for inclusion of said each object;
and
store identifiers of objects assigned to said each cluster.
12 . The system of claim 11 further comprising means for characterizing said each object by a respective vector of descriptors, said processor readable instructions further causing said at least one hardware processor to:
maintain a count of current objects assigned to said particular cluster;
maintain a vector sum of vectors of descriptors of said current objects; and
determine said respective updated centroid as said vector sum divided by said count.
13 . The system of claim 11 further comprising means for assigning to said each object a respective weight, said processor readable instructions further causing said at least one processor to establish said predetermined order as a descending order according to weight.
14 . The system of claim 11 wherein said processor readable instructions further cause said at least one hardware processor to execute multiple cycles of assigning said plurality of objects to said set of clusters with the predetermined order of selecting objects for any cycle differing from the predetermined order for any other cycle of the multiple cycles.
15 . The system of claim 14 wherein said processor readable instructions further cause said at least one hardware processor to:
generate, for each cycle of said multiple cycles, a respective pseudo-random sequence of different integers corresponding to memory addresses of vectors of descriptors of said plurality of objects; and
establish said predetermined order according to said respective pseudo-random sequence.
16 . The system of claim 11 wherein said processor readable instructions further cause said at least one processor to:
maintain object-assignment records indicating for each object:
an identifier of a cluster to which said each object is assigned; and
a corresponding composite affinity measure;
execute a specified number of cycles of assigning objects to clusters for said each object of said plurality of objects; and
execute each of a specified number of succeeding cycles of assigning objects to clusters for only each object of a composite affinity measure below a specified level.
17 . The system of claim 11 wherein said processor readable instructions further cause said at least one hardware processor to:
determine an overall number of changes of object assignments to clusters for a cycle of assigning objects to clusters for said each object; and
repeat said cycle at most a predefined number of times while a ratio of said overall number to a total number of objects of said plurality of objects exceeds a predefined threshold.
18 . The system of claim 11 further comprising causing the at least one hardware processor to determine each of said radial-affinity measure, said angular-affinity measure, and said composite affinity measure as a normalized value bounded between 0 and 1.0.
19 . The system of claim 11 wherein said processor readable instructions further cause said at least one hardware processor to:
determine said angular affinity measure as a dot product of vectors (C/∥C∥) and (P/∥P∥);
determine said radial affinity measure as a ratio ∥P∥/(∥P∥+D); and
determine said composite affinity measure as a weighted sum of said angular affinity measure and said radial affinity measure;
where C denotes a centroid vector of said each centroid, P denotes an object vector of said each object vector, ∥C∥ denotes magnitude of C, ∥P∥ denotes magnitude of P, and D denotes the Euclidean distance ∥(P−C)∥.
20 . The system of claim 11 wherein said executable instructions further cause said at least one hardware processor to:
determine said angular affinity measure as a dot product of vectors (C/∥C∥) and (P/∥P∥);
determine said radial affinity measure as (1−D/D*) for D<D* and zero otherwise; and
determine said composite affinity measure as a weighted sum of said angular affinity measure and said radial affinity measure;
where C denotes a centroid vector of said each centroid, P denotes an object vector of said each object vector, ∥C∥ denotes magnitude of C, ∥P∥ denotes magnitude of P, and D denotes the Euclidean distance ∥(P−C)∥, and D* is a predefined distance threshold, D*>0.