Neural network based cluster visualization that computes pairwise distances between centroid locations, and determines a projected centroid location in a multidimensional space

• US 9,367,799 B2
• Filed: 10/28/2015
• Issued: 06/14/2016
• Est. Priority Date: 03/11/2014
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Hall, Patrick, Kaynar Kabul, Ilknur, Dean, Jared Langford, Abbey, Ralph, Haller, Susan, Silva, Jorge
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US14/924,929
• Publication Number:
  US 20160048756A1
• Time in Patent Office: 230 Days
• Field of Search: 706/12, 706/45
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 3/088 Non-supervised learning, e.g. competitive learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A computing device presents a cluster visualization based on a neural network computation. First centroid locations are computed for first clusters. Second centroid locations are computed for second clusters. Each centroid location includes a plurality of coordinate values where each coordinate value relates to a single variable of a plurality of variables. Distances are computed pairwise between each centroid location. An optimum pairing is selected based on a minimum distance of the computed pairwise distances where each pair is associated with a different cluster of a set of composite clusters. Noised centroid location data is created. A multi-layer neural network is trained with the noised centroid location data. A projected centroid location is determined in a multidimensional space for each centroid location as values of hidden units of a middle layer of the multi-layer neural network. A graph is presented for display that indicates the determined, projected centroid locations.

Claims

1. A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:

receive data that includes a plurality of observations with a plurality of data points defined for each observation,

wherein each data point of the plurality of data points is associated with a variable to define a plurality of variables;

compute a first plurality of centroid locations for a first set of clusters of a predetermined number of clusters by executing a clustering algorithm with a first portion of the received data and a first input parameter;

compute a second plurality of centroid locations for a second set of clusters of the predetermined number of clusters by executing the clustering algorithm with a second portion of the received data and a second input parameter,

wherein the first portion is different from the second portion or the first input parameter is different from the second input parameter,

wherein each centroid location of the first plurality of centroid locations and of the second plurality of centroid locations includes a plurality of coordinate values,

wherein each coordinate value relates to a single variable of the plurality of variables;

compute distances pairwise between each centroid location of the computed first plurality of centroid locations and each centroid location of the computed second plurality of centroid locations;

select an optimum pairing between the computed first plurality of centroid locations and the computed second plurality of centroid locations based on a minimum distance of the computed pairwise distances;

associate each pair of the selected optimum pairing with a different cluster of a set of composite clusters;

create noised centroid location data by adding a noise value to the computed first plurality of centroid locations and the computed second plurality of centroid locations;

train a multi-layer neural network with the created noised centroid location data;

determine a projected centroid location in a multidimensional space for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations as values of hidden units of a middle layer of the trained multi-layer neural network; and

present a graph for display that indicates the determined, projected centroid location for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations with a different label indicating each pair of the selected optimum pairing,

wherein a number of the hidden units of the middle layer defines a number of dimensions of the graph.

2. The non-transitory computer-readable medium of claim 1, wherein each distance of the distances is computed using an algorithm selected from a group comprising a Euclidian distance computation algorithm, a Manhattan distance computation algorithm, a Minkowski distance computation algorithm, a Hamming distance computation algorithm, and a Jacquard distance computation algorithm.

3. The non-transitory computer-readable medium of claim 1, wherein the first input parameter is a value of a first random seed for a first Monte Carlo iteration, and the second input parameter is a value of a second random seed for a second Monte Carlo iteration.

4. The non-transitory computer-readable medium of claim 1, wherein the first portion of the received data is a first subset of the plurality of observations, and the second portion of the received data is a second subset of the plurality of observations.

5. The non-transitory computer-readable medium of claim 4, wherein the computer-readable instructions further cause the computing device to select the first portion of the received data from the plurality of observations and to select the second portion of the received data from the plurality of observations.

6. The non-transitory computer-readable medium of claim 1, wherein the first portion of the received data is the plurality of observations associated with a first subset of the plurality of variables, and the second portion of the received data is the plurality of observations associated with a second subset of the plurality of variables.

7. The non-transitory computer-readable medium of claim 6, wherein the computer-readable instructions further cause the computing device to select the first portion of the received data from the plurality of variables and to select the second portion of the received data from the plurality of variables.

8. The non-transitory computer-readable medium of claim 7, wherein the first subset of the plurality of variables is randomly selected from the plurality of variables, and the second subset of the plurality of variables is randomly selected from the plurality of variables.

9. The non-transitory computer-readable medium of claim 6, wherein the computer-readable instructions further cause the computing device to select a plurality of decorrelated variables from the plurality of variables,

wherein the first subset of the plurality of variables is randomly selected from the selected plurality of decorrelated variables, and the second subset of the plurality of variables is randomly selected from the selected plurality of decorrelated variables.

10. The non-transitory computer-readable medium of claim 6, wherein a number of variables of the first subset of the plurality of variables is different from a second number of variables of the second subset of the plurality of variables.

11. The non-transitory computer-readable medium of claim 1, wherein a number of the hidden units of the middle layer is two or three.

12. The non-transitory computer-readable medium of claim 1, wherein a number of layers of the multi-layer neural network is at least three.

13. The non-transitory computer-readable medium of claim 1, wherein a number of the plurality of variables is at least four.

14. The non-transitory computer-readable medium of claim 1, wherein, for each coordinate value of the plurality of coordinate values of the computed first plurality of centroid locations and the computed second plurality of centroid locations, the noise value is computed as a random value from a statistical distribution algorithm,

wherein the computed noise value is added to a respective coordinate value of the computed first plurality of centroid locations and the computed second plurality of centroid locations.

15. The non-transitory computer-readable medium of claim 1, wherein training the multi-layer neural network comprises:

training each hidden layer of the multi-layer neural network with the created noised centroid location data separately as a single-layer neural network to define a weight for each hidden layer;

initializing the multi-layer neural network with the defined weight for each hidden layer; and

training each hidden layer of the initialized multi-layer neural network with the created noised centroid location data simultaneously to define a trained weight for each hidden layer that defines the trained multi-layer neural network.

16. The non-transitory computer-readable medium of claim 15, wherein determining the projected centroid location comprises:

for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations,

selecting the plurality of coordinate values associated with a respective centroid location;

executing the trained multi-layer neural network with the selected plurality of coordinate values using the trained weight for each hidden layer; and

selecting the values of the hidden units of the middle layer of the executed, trained multi-layer neural network as the determined projected centroid location for the respective centroid location.

17. The non-transitory computer-readable medium of claim 1, wherein determining the projected centroid location comprises:

for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations,

selecting the plurality of coordinate values associated with a respective centroid location;

executing the trained multi-layer neural network with the selected plurality of coordinate values; and

selecting the values of the hidden units of the middle layer of the executed, trained multi-layer neural network as the determined projected centroid location for the respective centroid location.

18. The non-transitory computer-readable medium of claim 1, wherein, before creating the noised centroid location data, the computer-readable instructions further cause the computing device to:

compute a third plurality of centroid locations for a third set of clusters of the predetermined number of clusters by executing the clustering algorithm with a third portion of the received data and a third input parameter,

wherein the third portion is different from the first portion and the second portion or the third input parameter is different from the first input parameter and the second input parameter,

wherein each centroid location of the third plurality of centroid locations includes the plurality of coordinate values.

19. The non-transitory computer-readable medium of claim 18, wherein, before creating the noised centroid location data, the computer-readable instructions further cause the computing device to:

compute a plurality of composite centroid locations as an average value for each coordinate between the plurality of coordinate values of each pair of centroid locations of the selected optimum pairing;

compute second distances pairwise between each centroid location of the computed plurality of composite centroid locations and each centroid location of the computed third plurality of centroid locations; and

select a second optimum pairing between the computed plurality of composite centroid locations and the computed third plurality of centroid locations based on a minimum distance of the computed pairwise second distances;

wherein the noised centroid location data is further created from the computed third plurality of centroid locations;

wherein the projected centroid location is further determined for each of the computed third plurality of centroid locations as the values of the hidden units of the middle layer of the trained multi-layer neural network; and

wherein the graph is further presented by indicating the determined, projected centroid location for each of the computed third plurality of centroid locations with the different label indicating the selected second optimum pairing between the computed plurality of composite centroid locations and the computed third plurality of centroid locations.

20. A computing device comprising:

a processor; and

a non-transitory computer-readable medium operably coupled to the processor, the computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the computing device to

receive data that includes a plurality of observations with a plurality of data points defined for each observation,

wherein each data point of the plurality of data points is associated with a variable to define a plurality of variables;

compute a first plurality of centroid locations for a first set of clusters of a predetermined number of clusters by executing a clustering algorithm with a first portion of the received data and a first input parameter;

compute a second plurality of centroid locations for a second set of clusters of the predetermined number of clusters by executing the clustering algorithm with a second portion of the received data and a second input parameter,

wherein the first portion is different from the second portion or the first input parameter is different from the second input parameter,

wherein each centroid location of the first plurality of centroid locations and of the second plurality of centroid locations includes a plurality of coordinate values,

wherein each coordinate value relates to a single variable of the plurality of variables;

compute distances pairwise between each centroid location of the computed first plurality of centroid locations and each centroid location of the computed second plurality of centroid locations;

select an optimum pairing between the computed first plurality of centroid locations and the computed second plurality of centroid locations based on a minimum distance of the computed pairwise distances;

associate each pair of the selected optimum pairing with a different cluster of a set of composite clusters;

create noised centroid location data by adding a noise value to the computed first plurality of centroid locations and the computed second plurality of centroid locations;

train a multi-layer neural network with the created noised centroid location data;

determine a projected centroid location in a multidimensional space for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations as values of hidden units of a middle layer of the trained multi-layer neural network; and

present a graph for display that indicates the determined, projected centroid location for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations with a different label indicating each pair of the selected optimum pairing,

wherein a number of the hidden units of the middle layer defines a number of dimensions of the graph.

21. The computing device of claim 20, wherein a number of the hidden units of the middle layer is two or three.

22. The computing device of claim 20, wherein, for each coordinate value of the plurality of coordinate values of the computed first plurality of centroid locations and the computed second plurality of centroid locations, the noise value is computed as a random value from a statistical distribution algorithm,

wherein the computed noise value is added to a respective coordinate value of the computed first plurality of centroid locations and the computed second plurality of centroid locations.

23. The computing device of claim 20, wherein training the multi-layer neural network comprises:

training each hidden layer of the multi-layer neural network with the created noised centroid location data separately as a single-layer neural network to define a weight for each hidden layer;

initializing the multi-layer neural network with the defined weight for each hidden layer; and

training each hidden layer of the initialized multi-layer neural network with the created noised centroid location data simultaneously to define a trained weight for each hidden layer that defines the trained multi-layer neural network.

24. The computing device of claim 20, wherein determining the projected centroid location comprises:

for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations,

selecting the plurality of coordinate values associated with a respective centroid location;

executing the trained multi-layer neural network with the selected plurality of coordinate values; and

selecting the values of the hidden units of the middle layer of the executed, trained multi-layer neural network as the determined projected centroid location for the respective centroid location.

25. A method of presenting a cluster visualization based on a neural network computation, the method comprising:

receiving data that includes a plurality of observations with a plurality of data points defined for each observation,

wherein each data point of the plurality of data points is associated with a variable to define a plurality of variables;

computing, by a computing device, a first plurality of centroid locations for a first set of clusters of a predetermined number of clusters by executing a clustering algorithm with a first portion of the received data and a first input parameter;

computing, by the computing device, a second plurality of centroid locations for a second set of clusters of the predetermined number of clusters by executing the clustering algorithm with a second portion of the received data and a second input parameter,

wherein the first portion is different from the second portion or the first input parameter is different from the second input parameter,

wherein each centroid location of the first plurality of centroid locations and of the second plurality of centroid locations includes a plurality of coordinate values,

wherein each coordinate value relates to a single variable of the plurality of variables;

computing, by the computing device, distances pairwise between each centroid location of the computed first plurality of centroid locations and each centroid location of the computed second plurality of centroid locations;

selecting, by the computing device, an optimum pairing between the computed first plurality of centroid locations and the computed second plurality of centroid locations based on a minimum distance of the computed pairwise distances;

associating, by the computing device, each pair of the selected optimum pairing with a different cluster of a set of composite clusters;

creating, by the computing device, noised centroid location data by adding a noise value to the computed first plurality of centroid locations and the computed second plurality of centroid locations;

training, by the computing device, a multi-layer neural network with the created noised centroid location data;

determining, by the computing device, a projected centroid location in a multidimensional space for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations as values of hidden units of a middle layer of the trained multi-layer neural network; and

presenting, by the computing device, a graph for display that indicates the determined, projected centroid location for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations with a different label indicating each pair of the selected optimum pairing,

wherein a number of the hidden units of the middle layer defines a number of dimensions of the graph.

26. The method of claim 25, wherein a number of the hidden units of the middle layer is two or three.

27. The method of claim 25, wherein, for each coordinate value of the plurality of coordinate values of the computed first plurality of centroid locations and the computed second plurality of centroid locations, the noise value is computed as a random value from a statistical distribution algorithm,

wherein the computed noise value is added to a respective coordinate value of the computed first plurality of centroid locations and the computed second plurality of centroid locations.

28. The method of claim 25, wherein training the multi-layer neural network comprises:

training, by the computing device, each hidden layer of the multi-layer neural network with the created noised centroid location data separately as a single-layer neural network to define a weight for each hidden layer;

initializing, by the computing device, the multi-layer neural network with the defined weight for each hidden layer; and

training, by the computing device, each hidden layer of the initialized multi-layer neural network with the created noised centroid location data simultaneously to define a trained weight for each hidden layer that defines the trained multi-layer neural network.

29. The method of claim 25, wherein determining the projected centroid location comprises:

for each of the computed first plurality of centroid locations and the computed second plurality of centroid locations,

selecting, by the computing device, the plurality of coordinate values associated with a respective centroid location;

executing, by the computing device, the trained multi-layer neural network with the selected plurality of coordinate values; and

selecting, by the computing device, the values of the hidden units of the middle layer of the executed, trained multi-layer neural network as the determined projected centroid location for the respective centroid location.

30. The method of claim 25, further comprising selecting, by the computing device, a plurality of decorrelated variables from the plurality of variables,

wherein the first portion of the received data is the plurality of observations associated with a first subset of the plurality of variables, and the second portion of the received data is the plurality of observations associated with a second subset of the plurality of variables,

wherein the first subset of the plurality of variables is randomly selected from the selected plurality of decorrelated variables, and the second subset of the plurality of variables is randomly selected from the selected plurality of decorrelated variables.