US6345265B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Clustering with mixtures of bayesian networks
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-12-23
•
Granted: 2002-02-05
•
Expires: 2018-12-23
Abstract
Abstract The invention employs mixtures of Bayesian networks to perform clustering. A mixture of Bayesian networks (MBN) consists of plural hypothesis-specific Bayesian networks (HSBNs) having possibly hidden and observed variables. A common external hidden variable is associated with the MBN, but is not included in any of the HSBNs. The number of HSBNs in the MBN corresponds to the number of states of the common external hidden variable, and each HSBN is based upon the hypothesis that the common external hidden variable is in a corresponding one of those states. In one mode of the invention, the MBN having the highest MBN score is selected for use in performing inferencing. The invention determines membership of an individual case in a cluster based upon a set of data of plural individual cases by first learning the structure and parameters of an MBN given that data and then using the MBN to compute the probability of each HSBN generating the data of the individual case.
Inventors
- 👤 Bo Thiesson
- 👤 Christopher A. Meek
- 👤 David Maxwell Chickering
- 👤 David Earl Heckerman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 08:21
CPC Classifications
G; G06; G06N; G06N5/00; G06N5/02; G06N5/022; G06N5/025; G06F; G06F18/00; G06F18/20; G06F18/29; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99944; Y10S707/99945; Y10S707/99948
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
149 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, an apparatus for determining membership of an individual case in a cluster based upon the set of data of plural individual cases, comprising: a processor; a memory having executable instructions stored therein; wherein said processor, in response to instructions stored in memory: constructs a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; computes with the MBN the probability of each of said HSBNs generating the data of said individual case; assigns said individual case to the cluster of the HSBN with the highest probability of generating the data of the case.
Claim 2
Dependent Claim
149 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, an apparatus for determining membership of an individual case in a cluster based upon the set of data of plural individual cases, comprising: a processor; a memory having executable instructions stored therein; wherein said processor, in response to instructions stored in memory: constructs a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; computes with the MBN the probability of each of said HSBNs generating the data of said individual case; assigns said individual case to the cluster of the HSBN with the highest probability of generating the data of the case.
Claim 3
Dependent Claim
42 words
The apparatus of claim 1 wherein said processor assigns said individual case to the cluster of the HSBN with the highest probability, in that said probability is the probability of said HSBN given the data of said case and given said MBN.
Claim 4
Dependent Claim
48 words
The apparatus of claim 1 wherein said processor assign said individual case, in that said processor associates said individual case with different clusters and a probability of said individual case being in said cluster corresponding to the probability of said cluster given the data of said individual case.
Claim 5
Dependent Claim
134 words
The apparatus of claim 1 wherein said processor computes with the MBN the probability of each of said HSBNs generating the data of said individual case in that said processor: first computes a first probability comprising the probability of the individual case given the cluster and given said MBN; second computes a second probability comprising the prior probability of said cluster given said MBN; multiplies said first and second probabilities together to obtain a product; repeats the first and second computing steps and the multiplying step for different ones of the cases in said set of data to obtain a set of products corresponding to said set of cases of said data; sums all of said products together to obtain a sum of products; and divides said first probability by said sum of products.
Claim 6
Dependent Claim
46 words
The apparatus of claim 1 wherein said cases correspond to observed behavior attributes of a set of individual users, and wherein said clusters comprise respective divisions of said set of said cases, each cluster corresponding to a particular state of a class variable characterizing said cases.
Claim 7
Dependent Claim
13 words
The apparatus of claim 5 wherein said class variable is a priori unknown.
Claim 8
Dependent Claim
152 words
The apparatus of claim 1 wherein said HSBNs have nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, said processor constructs a mixture of Bayesian networks, in that the processor: chooses a number of states of said discrete variables, and initializing said HSBNs; for each one of said HSBNs chooses a parameter search for a set of changes in said probability parameters which improves the goodness of said one HSBN in predicting said observed data, and modifying the probability parameters of said one HSBN accordingly; for each one of said HSBNs, chooses a structure score of said one HSBN reflecting the goodness of said one HSBN in predicting said observed data, conducting a structure search for a change in said structure which improves said structure search score, and modifying the structure of said one HSBN accordingly.
Claim 9
Dependent Claim
49 words
The apparatus of claim 7 wherein said processor computes a structure score of said one HSBN, in that the processor: computes from said observed data expected complete model sufficient statistics (ECMSS); computes from said ECMSS sufficient statistics for said one HSBN; computes said structure score from said sufficient statistics.
Claim 10
Dependent Claim
75 words
The apparatus of claim 8 wherein said processor computes said ECMSS, in that the processor: computes the probability of each combination of the states of the discrete hidden and observed variables; forms a vector for each observed case in said set of observed data, each entry in said vector corresponding to a particular one of the combinations of the states of said discrete variables; and sums the vectors over plural cases of said observed data.
Claim 11
Dependent Claim
49 words
The apparatus of claim 9 wherein said processor forms a vector such that each entry in said vector is formed to have plural sub-entries comprising: (a) the probability of the one combination of the states of the discrete variables, (b) sub-entry vectors representing the states of the continuous variables.
Claim 12
Dependent Claim
35 words
The apparatus of claim 10 wherein said processor computes the probability of the one combination of the states of the discrete variables in that the processor computes by inference in said mixture of Bayesian networks.
Claim 13
Dependent Claim
35 words
The apparatus of claim 10 wherein said processor forms each sub-entry such that said sub-entry vector has a vector multiplier corresponding to the probability of the one combination of the states of the discrete variables.
Claim 14
Dependent Claim
28 words
The apparatus of claim 12 wherein the processor computes sufficient statistics from said ECMSS comprises computing from said ECMSS the following: (a) mean, (b) scatter, (c) sample size.
Claim 15
Dependent Claim
28 words
The apparatus of claim 7 wherein said processor conducts a parameter search and modifies said probability parameters repeatedly and consecutively until a parameter search convergence criteria is met.
Claim 16
Dependent Claim
34 words
The apparatus of claim 7 in that said processor: repeats the steps of conducting a parameter search, computing the structure score and conducting a structure search until a structure search convergence criteria is met.
Claim 17
Dependent Claim
33 words
The of claim 14 in that said processor: repeats the steps of conducting a parameter search, computing the structure score and conducting a structure search until a structure search convergence criteria is met.
Claim 18
Dependent Claim
26 words
The apparatus of claim 15 wherein said processor uses said parameter search convergence criteria to determine whether the parameter search has converged at a local optimum.
Claim 19
Dependent Claim
28 words
The apparatus of claim 15 wherein said processor uses said parameter search convergence criteria to determine whether the parameter search has been repeated a certain number of times.
Claim 20
Dependent Claim
162 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, an apparatus for dividing the set of data representing a set of case cases into clusters of groups of said cases based upon similarity of the cases within a cluster comprising: a processor; a memory having executable instructions stored therein; wherein said processor, in response to instructions stored in memory: constructs a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; for each one of said cases, computes with the MBN the probability of each of said HSBNs generating the data of the one case; assigns each case to the cluster of the HSBN having the highest probability of generating the data of the case.
Claim 21
Dependent Claim
162 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, an apparatus for dividing the set of data representing a set of case cases into clusters of groups of said cases based upon similarity of the cases within a cluster comprising: a processor; a memory having executable instructions stored therein; wherein said processor, in response to instructions stored in memory: constructs a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; for each one of said cases, computes with the MBN the probability of each of said HSBNs generating the data of the one case; assigns each case to the cluster of the HSBN having the highest probability of generating the data of the case.
Claim 22
Dependent Claim
24 words
The apparatus of claim 19 wherein said probability is the probability of said HSBN given the data of said case and given said MBN.
Claim 23
Dependent Claim
64 words
The apparatus of claim 19 wherein said processor assigns each case to the cluster of the HSBN having the highest probability of generating the data of the case, in that said processor associates said one case with different clusters and a probability of said one case being in said cluster corresponding to the probability of said cluster given the data of said one case.
Claim 24
Dependent Claim
135 words
The apparatus of claim 20 wherein said processor computes with the MBN the probability of each of said HSBNs generating the data of the one case, in that said processor: first computes a first probability comprising the probability of the one case given the cluster and given said MBN; second computes a second probability comprising the prior probability of said cluster given said MBN; multiplies said first and second probabilities together to obtain a product; repeats the first and second computing steps and said the multiplying step for different ones of the cases in said set of data to obtain a set of products corresponding to said set of cases of said data; sums all of said products together to obtain a sum of products; and divides said first probability by said sum of products.
Claim 25
Dependent Claim
46 words
The apparatus of claim 19 wherein said cases correspond to observed behavior attributes of a set of individual users, and wherein said clusters comprise respective divisions of said set of said cases, each cluster corresponding to a particular state of a class variable characterizing said cases.
Claim 26
Dependent Claim
13 words
The apparatus of claim 23 wherein said class variable is a priori unknown.
Claim 27
Dependent Claim
152 words
The apparatus of claim 19 wherein said HSBNs have nodes corresponding to hidden and observed variables, each of said nodes storing a set of probability parameters and structure representing dependence relationships among said nodes, said processor constructs a mixture of Bayesian networks, in that said processor: chooses a number of states of said discrete variables, and initializing said HSBNs; for each one of said HSBNs conducts a parameter search for a set of changes in said probability parameters which improves the goodness of said one HSBN in predicting said observed data, and modifies the probability parameters of said one HSBN accordingly; for each one of said HSBNs, computes a structure score of said one HSBN reflecting the goodness of said one HSBN in predicting said observed data, conducts a structure search for a change in said structure which improves said structure search score, and modifies the structure of said one HSBN accordingly.
Claim 28
Dependent Claim
49 words
The apparatus of claim 25 wherein said processor computes a structure score of said one HSBN in that said processor: computes from said observed data expected complete model sufficient statistics (ECMSS); computes from said ECMSS sufficient statistics for said one HSBN; computes said structure score from said sufficient statistics.
Claim 29
Dependent Claim
75 words
The apparatus of claim 26 wherein said processor computes said ECMSS, in that said processor: computes the probability of each combination of the states of the discrete hidden and observed variables; forms a vector for each observed case in said set of observed data, each entry in said vector corresponding to a particular one of the combinations of the states of said discrete variables; and sums the vectors over plural cases of said observed data.
Claim 30
Dependent Claim
49 words
The apparatus of claim 27 wherein said processor forms a vector such that each entry in said vector is formed to have plural sub-entries comprising: (a) the probability of the one combination of the states of the discrete variables, (b) sub-entry vectors representing the states of the continuous variables.
Claim 31
Dependent Claim
30 words
The apparatus of claim 28 wherein said processor computes the probability of the one combination of the states of the discrete variables by inference in said mixture of Bayesian networks.
Claim 32
Dependent Claim
34 words
The apparatus of claim 28 wherein each sub-entry is formed such that said sub-entry vector has a vector multiplier corresponding to the probability of the one combination of the states of the discrete variables.
Claim 33
Dependent Claim
31 words
The apparatus of claim 30 wherein said processor computes sufficient statistics from said ECMSS in that said processor computes from said ECMSS the following: (a) mean, (b) scatter, (c) sample size.
Claim 34
Dependent Claim
28 words
The apparatus of claim 25 wherein said processor conducts a parameter search and modifies said probability parameters repeatedly and consecutively until a parameter search convergence criteria is met.
Claim 35
Dependent Claim
39 words
The apparatus of claim 25 further comprising instructions in response to which said processor: repeats the steps of conducting a parameter search, computes the structure score and conducts a structure search until a structure search convergence criteria is met.
Claim 36
Dependent Claim
39 words
The apparatus of claim 32 further comprising instructions in response to which said processor: repeats the steps of conducting a parameter search, computes the structure score and conducts a structure search until a structure search convergence criteria is met.
Claim 37
Dependent Claim
25 words
The apparatus of claim 33 wherein said parameter search convergence criteria is a determination of whether the parameter search has converged at a local optimum.
Claim 38
Dependent Claim
27 words
The apparatus of claim 33 wherein said parameter search convergence criteria is a determination of whether the parameter search has been repeated a certain number of times.
Claim 39
Dependent Claim
139 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, a method for determining membership of an individual case in a cluster based upon the set of data of plural individual cases, comprising: receiving said set of data on said signal-bearing medium; constructing a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; computing with the MBN the probability of each of said HSBNs generating the data of said individual case; assigning said individual case to the cluster of the HSBN with the highest probability of generating the data of the case.
Claim 40
Dependent Claim
139 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, a method for determining membership of an individual case in a cluster based upon the set of data of plural individual cases, comprising: receiving said set of data on said signal-bearing medium; constructing a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; computing with the MBN the probability of each of said HSBNs generating the data of said individual case; assigning said individual case to the cluster of the HSBN with the highest probability of generating the data of the case.
Claim 41
Dependent Claim
15 words
A computer-readable medium storing computer-executable instructions for carrying out the steps of claim 37 .
Claim 42
Dependent Claim
152 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, a method for dividing a set of data representing a set of case cases into clusters of groups of said cases based upon similarity of the cases within a cluster comprising: receiving said set of data on said signal-bearing medium; constructing a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; for each one of said cases, computing with the MBN the probability of each of said HSBNs generating the data of the one case; assigning each case to the cluster of the HSBN having the highest probability of generating the data of the case.
Claim 43
Dependent Claim
152 words
In a decision support system that receives, as an input on a signal-bearing medium, a set of data representing plural individual cases, a method for dividing a set of data representing a set of case cases into clusters of groups of said cases based upon similarity of the cases within a cluster comprising: receiving said set of data on said signal-bearing medium; constructing a mixture of Bayesian networks (MBN) using said set of data, said MBN comprising plural HSBNs corresponding to a hidden class variable having plural states being in a particular one of said states, each of said states corresponding to a respective cluster of said cases; for each one of said cases, computing with the MBN the probability of each of said HSBNs generating the data of the one case; assigning each case to the cluster of the HSBN having the highest probability of generating the data of the case.
Claim 44
Dependent Claim
15 words
A computer-readable medium storing computer-executable instructions for carrying out the steps of claim 39 .
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-02-04 | 2005-08-06 | 2006-02-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-02-04 | 2009-08-06 | 2010-02-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-02-04 | 2013-08-06 | 2014-02-05 | $7700.00 | Window Closed / Lapsed |