Computer-Implemented Systems And Methods For Variable Clustering In Large Data Sets

• US 20100153456A1
• Filed: 12/17/2008
• Published: 06/17/2010
• Est. Priority Date: 12/17/2008
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Latour, Dominique Joseph, Lee, Taiyeong, Duling, David Rawlins
• Granted Patent: US 8,190,612 B2
• Time in Patent Office: Days
• US Class Current: 707/791
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

Computer-implemented systems and methods are provided for creating a cluster structure from a data set containing input variables. Global clusters are created within a first stage, by computing a similarity matrix from the data set. A global cluster structure and sub-cluster structure are created within a second stage, where the global cluster structure and the sub-cluster structure are created using a latent variable clustering technique and the cluster structure output is generated by combining the created global cluster structure and the created sub-cluster structure.

Claims

1. A computer-implemented method for creating a cluster structure from a data set containing a plurality of input variables, comprising:

creating global clusters, within a first stage, by computing a similarity matrix from the data set;

creating, within a second stage, both a global cluster structure and a sub-cluster structure;

wherein the global cluster structure and the sub-cluster structure are created using a latent variable clustering technique; and

forming, as output to a computer-readable data store, the cluster structure by combining the created global cluster structure and the created sub-cluster structure.

2. The method of claim 1, wherein global clusters created within the first stage contain homogeneous variables.

3. The method of claim 1, wherein the similarity matrix that is computed from the data set is a distance matrix, correlation matrix, or a covariance matrix.

4. The method of claim 1, wherein a pre-defined number of global clusters are created in the first stage.

5. The method of claim 4, wherein the pre-defined number of global clusters is chosen based upon a pre-selected criterion.

6. The method of claim 5, wherein the pre-selected criterion is a cubic clustering criterion (CCC).

7. The method of claim 1, wherein latent variables are generated by the latent variable clustering technique;

wherein the generated latent variables are used to form the global cluster structure and the sub-cluster structure.

8. The method of claim 7, forming the global cluster structure based upon global cluster components that are generated from the first stage.

9. The method of claim 8, wherein the global cluster components are generated by principal components or centroid components.

10. The method of claim 7, wherein the latent variable clustering technique includes performing factor analysis, principal component analysis, simple unweighted average of variables, or combinations thereof.

11. The method of claim 7, further comprising:

generating sub-cluster components for each of the sub-clusters in a particular global cluster.

12. The method of claim 1, wherein the first stage creates the global clusters in order to reduce processing by the second stage.

13. The method of claim 1, wherein the first stage creates the global clusters in order to reduce latent variable processing by the second stage in order to create the global cluster structure and the sub-cluster structure.

14. The method of claim 1, wherein the formed cluster structure contains a number of variables that is less than number of variables in the data set.

15. The method of claim 14, wherein variables in the data set are independent variables for predicting a target within a prediction model;

wherein variables in the formed cluster structure are independent variables for predicting the target within the prediction model.

16. The method of claim 15, wherein the prediction model provides predictions with respect to whether a customer is likely to purchase a product or service.

17. The method of claim 1, wherein the first stage and the second stage execute upon one or more data processors.

18. The method of claim 1, wherein the created global clusters and the created global cluster structure and sub-cluster structure are stored in a computer-readable storage medium.

19. A computer-implemented system for creating a cluster structure from a data set containing a plurality of input variables, comprising:

first instructions configured to execute on a data processor for creating global clusters, within a first stage, by computing a similarity matrix from the data set;

second instructions configured to execute on a data processor for creating, within a second stage, both a global cluster structure and a sub-cluster structure;

wherein the global cluster structure and the sub-cluster structure are created using a latent variable clustering technique; and

a computer-readable data store for storing the cluster structure that has been generated by combining the created global cluster structure and the created sub-cluster structure.

20. A computer-readable storage medium having stored thereon cluster data structures that are created based upon a data set containing a plurality of input variables, the data structure comprising:

a first data structure containing the data set;

a second data structure containing one or more global clusters created by computing a distance matrix from the data set;

a third data structure containing a global cluster structure;

a fourth data structure containing a sub-cluster structure; and

a fifth data structure containing a cluster structure formed by combining the global cluster structure and the sub-cluster structure;

wherein the global cluster structure and the sub-cluster structure are created using a latent variable clustering technique.