Apparatus for Fast Clustering of Massive Data Based on Variate-Specific Population Strata

1 . An apparatus, for clustering a population of objects, comprising:

a memory device, storing computer executable instructions for execution by a processor, causing the processor to:

obtain:

identifiers of a set of variates characterizing each object of a population of objects;

a number of population strata for each variate of said set of variates; and

an object-characteristics vector for each object of the population of objects;

generate a cluster-indicator vector according to said number of population strata;

determine, for each variate, variate-strata boundaries according to a number of population strata of said each variate;

determine for said each object:

an object-strata-vector based on a respective object-characteristics vector of said each object and said variate-strata boundaries;

a cluster index as a dot product of the object-strata vector and the cluster-indicator vector;

add said each object to a cluster-membership storage area of a respective cluster corresponding to said cluster index, said storage area being initialized as an empty storage area.

2 . The apparatus of claim 1 wherein said computer executable instructions further cause said processor to communicate with members of said respective cluster.

3 . The apparatus of claim 1 wherein said computer executable instructions further cause said processor to determine variate-specific multipliers Q 0 , Q 1 , . . . , Q (v−1) using the recursion:

Q (v−1) =1,

Q j =S (j+1) ×Q (j+1) , for ( v− 1)> j≥ 0,

where v is a number of variates of said set of variates, v>1, S j is a number of population strata for variate j, 0≤j<v;

said cluster-indicator vector, denoted Θ, being defined as Θ={Q 0 , Q 1 , . . . Q (v−1) }.

4 . The apparatus of claim 3 wherein said computer executable instructions further cause said processor to:

determine for said each variate a respective cumulative density function;

determine (S−1) reference cumulative-density values of (j×1.0/S), 0≤j<S, S being said number of population strata; and

determine said variate-strata boundaries to correspond to said reference cumulative-density values.

5 . The apparatus of claim 4 wherein said computer executable instructions further cause said processor to determine stratum indices α j for each variate j, 0≤j<v, of said each object, based on comparing a value of each variate of said respective object-characteristics vector with said variate-strata boundaries, said object-strata vector, denoted Ω j , being defined as Ω j ={α 0 , α 1 , . . . α (v−1) }.

6 . The apparatus of claim 4 wherein said computer executable instructions further cause said processor to determine said respective cumulative distribution function based on computed moments for said each variate.

7 . The apparatus of claim 4 wherein said computer executable instructions further cause said processor to periodically update said respective cumulative density function and said variate-strata boundaries.

8 . The apparatus of claim 1 wherein said processor comprises multiple processing units and the computer executable instructions cause different processing units to concurrently determine said object-strata-vector and said cluster index.

9 . A method for clustering a population of objects, comprising:

employing a hardware processor for:

obtaining:

identifiers of a set of variates characterizing each object of a population of objects;

a number of population strata for each variate of said set of variates; and

an object-characteristics vector for each object of the population of objects;

generating a cluster-indicator vector according to said number of population strata;

determining, for each variate, variate-strata boundaries according to a number of population strata of said each variate;

determining for said each object:

an object-strata-vector based on an object-characteristics vector of said each object and said variate-strata boundaries;

a cluster index as a dot product of the object-strata vector and the cluster-indicator vector;

adding said each object to a cluster-membership storage area of a respective cluster corresponding to said cluster index, to produce a plurality of clusters, said storage area being initialized as an empty storage area.

10 . The method of claim 9 further comprising communicating with members of said respective cluster.

11 . The method of claim 9 further comprising determining variate-specific multipliers Q 0 , Q 1 , . . . , Q (v−1) using the recursion:

Q (v−1) =1,

Q j =S (j+1) ×Q (j+1) , for ( v− 1)> j≥ 0,

where v is a number of variates of said set of variates, v>1, S j is a number of population strata for variate j, 0≤j<v;

said cluster-indicator vector, denoted Θ, being defined as Θ={Q 0 , Q 1 , . . . Q (v−1) }.

12 . The method of claim 11 further comprising:

determining for said each variate a respective cumulative density function;

determining (S−1) reference cumulative-density values of (j×1.0/S), 0≤j<S, S being said number of population strata; and

determining said variate-strata boundaries to correspond to said reference cumulative-density values.

13 . The method of claim 12 further comprising determining stratum indices α j for each variate j, 0≤j<v, of said each object, based on comparing a value of each variate of said respective object-characteristics vector with said variate-strata boundaries, said object-strata vector, denoted Ω j , being defined as Ω j ={α 0 , α 1 , . . . α (v−1) }.

14 . The method of claim 12 further comprising determining said respective cumulative distribution function based on computed moments for said each variate.

15 . The method of claim 9 further comprising:

receiving an identifier of a specific commodity;

determining characteristics of a model consumer for the specific commodity based on acquired marketing information;

associating said specific commodity with a respective cluster according to said characteristics of said model consumer; and

communicating information relevant to said specific commodity to objects of said respective cluster.

16 . The method of claim 9 further comprising

pruning said plurality of clusters to eliminate each cluster having a number of objects below a predefined lower bound;

transferring objects of eliminated cluster to respective nearest clusters.

17 . The method of claim 9 further comprising ranking variates of said set of variates and selecting said number of population strata for each variate according to said ranking.

18 . The method of claim 9 wherein said hardware processor comprises multiple processing units and the method further comprises using different processing units to concurrently perform said determining for said each object an object-strata-vector and said determining for said each object a cluster index.

19 . An apparatus, for clustering a population of objects, comprising:

a memory device, having computer executable instructions stored thereon for execution by a processor, forming:

an information acquisition module for obtaining:

identifiers of a set of variates characterizing each object of a population of objects;

a number of population strata for each variate of said set of variates; and

an object-characteristics vector for each object of the population of objects;

a module for generating a cluster-indicator vector according to said number of population strata;

a module for determining, for each variate, variate-strata boundaries according to a number of population strata of said each variate;

a module for determining for said each object:

an object-strata-vector based on an object-characteristics vector of said each object and said variate-strata boundaries;

a cluster index as a dot product of the object-strata vector and the cluster-indicator vector;

a module for adding said each object to a cluster-membership storage area of a respective cluster corresponding to said cluster index, said storage area being initialized as an empty storage area.

20 . The apparatus of claim 19 further comprising:

a storage medium storing marketing data relating each commodity of selected commodities to characteristics of a respective model consumer;

a module for associating each said each commodity with a respective cluster according to said characteristics of said respective model consumer;

a module for communicating information relevant to said each commodity to members of said respective cluster.