Goal-oriented clustering

• US 6,694,301 B1
• Filed: 03/31/2000
• Issued: 02/17/2004
• Est. Priority Date: 03/31/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Thiesson, Bo, Chickering, D. Maxwell, Platt, John C., Meek, Christopher A., Heckerman, David E.
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/540,255
• Time in Patent Office: 1,418 Days
• Field of Search: 706/45, 706/16, 706/20, 706/25, 324/772, 382/156, 712/10
• US Class Current: 706/45
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06F 18/41 Interactive pattern learning with a human teacher
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Clustering for purposes of data visualization and making predictions is disclosed. Embodiments of the invention are operable on a number of variables that have a predetermined representation. The variables include input-only variables, output-only variables, and both input-and-output variables. Embodiments of the invention generate a model that has a bottleneck architecture. The model includes a top layer of nodes of at least the input-only variables, one or more middle layer of hidden nodes, and a bottom layer of nodes of the output-only and the input-and-output variables. At least one cluster is determined from this model. The model can be a probabilistic neural network and/or a Bayesian network.

Claims

1. A computer-implemented method operable on a plurality of variables having a predetermined representation, the plurality of variables including a plurality of input-only variables, a plurality of output-only variables, and a plurality of both input-and-output variables, the method comprising:

generating a model comprising a bottleneck architecture, the model including a top layer of nodes including at least the plurality of input-only variables, at least one middle layer of discrete hidden nodes, and a bottom layer of nodes including the plurality of output-only variables and the plurality of input-and-output variables; and

,

determining at least one cluster from the model.

2. The method of claim 1, wherein determining the at least one cluster from the model comprises determining the at least one cluster as a predetermined partition of states of the hidden nodes of the at least one middle layer.

3. The method of claim 1, wherein the top layer of nodes includes only the plurality of input-only variables.

4. The method of claim 1, wherein the top layer of nodes also includes the plurality of input-and-output variables.

5. The method of claim 4, wherein the model comprises a Bayesian network.

6. The method of claim 1, wherein the model comprises a probabilistic neural network.

7. The method of claim 1, wherein the model comprises at least one arc, each arc connecting a pair of nodes within a same layer.

8. The method of claim 1, wherein the model comprises at least one arc, each arc connecting a node within the bottom layer with a node within one of the bottom and the top layers.

9. The method of claim 1, further comprising generating a solution to the model.

10. The method of claim 9, wherein generating a solution to the model comprises utilizing a Monte Carlo approach.

11. The method of claim 9, wherein distributions of the variables are differentiable with respect to parameters of the variables, and generating a solution to the model comprises utilizing a stochastic gradient approach.

12. The method of claim 9, wherein distributions of the variables are differentiable with respect to parameters of the variables, and generating a solution to the model comprises utilizing a Generalized Expectation Maximization (GEM) approach.

13. The method of claim 1, further comprising displaying a visualization of the at least one cluster.

14. The method of claim 13, wherein displaying the visualization of the at least one cluster comprises displaying a list of values for the plurality of input variables, such that an item having a value in the list renders the item more likely to be in a particular cluster.

15. The method of claim 13, wherein displaying the visualization of the at least one cluster comprises displaying a list of values for the plurality of output variables when an item is in a particular cluster.

16. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method operable on a plurality of variables having a predetermined representation, the plurality of variables including a plurality of input-only variables, a plurality of output-only variables, and a plurality of both input-and-output variables, the method comprising:

generating a model comprising a bottleneck architecture, the model including a top layer of nodes including at least the plurality of input-only variables, at least one middle layer of hidden nodes, and a bottom layer of nodes including the plurality of output-only variables and the plurality of input-and-output variables;

determining at least one cluster Corn the model as a predetermined partition of states of the hidden nodes of the at least one middle layer; and

,

generating a solution to the model.

17. The medium of claim 16, wherein the top layer of nodes includes only the plurality of input-only variables.

18. The medium of claim 16, wherein the top layer of nodes also includes the plurality of input-and-output variables.

19. The medium of claim 16, wherein the model comprises at least one arc, each arc connecting a pair of nodes within a same layer.

20. The medium of claim 16, wherein the model comprises at least one arc, each arc connecting a node within the bottom layer with a node within one of the bottom and the top layers.

21. The medium of claim 16, wherein generating a solution to the model comprises utilizing a Monte Carlo approach.

22. The medium of claim 16, wherein distributions of the variables are differentiable with respect to parameters of the variables, and generating a solution to the model comprises utilizing a stochastic gradient approach.

23. The median of claim 16, wherein distributions of the variables are differentiable with respect to parameters of the variables, and generating a solution to the model comprises utilizing an Expectation Maximization (EM) approach.

24. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method operable on a plurality of variables having a predetermined representation, the plurality of variables including a plurality of input-only variables, a plurality of output-only variables, and a plurality of both input-and-output variables, the method comprising:

generating a model comprising a bottleneck architecture, the model including a top layer of nodes including at least the plurality of input-only variables, at least one middle layer of hidden nodes, and a bottom layer of nodes including the plurality of output-only variables and the plurality of input-and-output variables;

determining at least one cluster from the model;

generating a solution to the model; and

,

displaying a visualization of the at least one cluster.

25. The medium of claim 24, wherein determining the at least one cluster from the model comprises determining the at least one cluster as a predetermined partition of states of the hidden nodes of the at least one middle layer.

26. The medium of claim 24, wherein the top layer of nodes includes only the plurality of input-only variables.

27. The medium of claim 24, wherein the top layer of nodes also includes the plurality of input-and-output variables.

28. The medium of claim 24, wherein displaying the visualization of the at least one cluster comprises displaying a list of values for the plurality of input-only variables, such that an item having a value in the list renders the item more likely to be in a particular cluster.

29. The medium of claim 24, wherein displaying the visualization of the at least one cluster comprises displaying a list of values for the plurality of output-only variables when an item is in a particular cluster.

30. A computer-implemented method for generating a model from which at least one cluster can be determined there from and operable on a plurality of variables having a predetermined representation, the plurality of variables including a plurality of input-only variables, a plurality of output-only variables, and a plurality of both input-and-output variables, the method comprising:

generating a model comprising a bottleneck architecture, the model including a top layer of nodes including at least the plurality of input-only variables, at least one middle layer of discrete hidden nodes, and a bottom layer of nodes including the plurality of output-only variables and the plurality of input-and-output variables.

31. The method of claim 30, wherein the top layer of nodes includes only the plurality of input-only variables.

32. The method of claim 30, wherein the top layer of nodes also includes the plurality of input-and-output variables.

33. The method of claim 30, wherein the model comprises at least one arc, each arc connecting a pair of nodes within a same layer.

34. The method of claim 30, wherein the model comprises at least one arc, each arc connecting a node within the bottom layer with a node within one of the bottom and the top layers.