Lecture 9

Model Based Clustering

Thursday November 1, 2001

Lecturer: Larry Ruzzo

Notes: Shabnam Erfani

Before we discuss model-based clustering today, we review some probability theory.

Supposed we have a model that indicates how data is generated according to a certain probability distribution, say normal, denoted by:

Normal (μ, σ²): where μ is the mean, and σ² is the variance.

The probability distribution function (PDF) for normal distribution is:

ƒ (x) = (1 ∕ √(2πσ² ) ) _e -(x- μ) ²/2σ²

The pdf gives the probability that a sample is in interval dx (or has value dx). The normal pdf describes a bell shaped curve that is centered at μ and has variance σ². These 2 parameters exactly define what the normal distribution looks like. Our problem is reverse of this, given a set of data that have normal distribution, what can we tell about the shape of the curve? In other words, what are the values for parameters μ and σ² based on the observed data? The process of calculating μ and σ² from the sample data is called parameter estimation. Parameter estimation uses a function called the likelihood function:

L(X₁, X₂, …,X_n | θ₁ , θ₂): is the probability of n samples assuming values X₁, X₂, …,X_n given parameters θ₁ , θ₂ , in this case θ₁ = μ , θ₂ = σ² , in other words, this is the joint pdf of the random variables generating the sample points.

Assuming we have independent samples with normal distribution, the likelihood function is: _n

Π ƒ (X_i)

ⁱ⁼¹

To estimate the parameters we essentially pick pairs of parameters and try to maximize the likelihood function. The pair that produces the max likelihood is the best candidate for the solution

Let us try some simple examples to illustrate the point:

Suppose we have a normal distribution where we know that variance σ²=1, but we do not know the mean. So the likelihood function becomes:

_n

L(X | θ₁ , θ₂ =1 ) = Π (1/√2π) exp( -(X- θ₁ )²/2 )

ⁱ⁼¹

^{X here is the vector of random variables representing the samples}

To find the value that maximizes this function, we take its derivative and set it to zero. This may get us stuck at local maxima unless we have a convex function. Or we may have multiple values as solutions of the resulting equations. In this case we need to plug in the values one by one and see which one gives the max value for the likelihood function.

Since the likelohood function is an exponential, it is easier to take the natural log and then the derivative:

a) ln ( L(X| θ₁ ) ) = ∑ [ -(1/2)ln 2π – (X_i - θ₁ )²/2 ]

Taking the derivative of this function and equating to 0 results in:

d/d θ₁ (ln (L(X| θ₁ )) ) = 0 - ∑ (X_i - θ₁ ) =0 (all summations are over i=1…n)

Þ ∑ X_i - n θ₁ = 0 Þ θ₁ = ∑ X_i ¤ n

We see that the value that actually maximized the likelihood function is the same as the population mean, i.e. E(sample mean) = population mean. This is an unbiased estimation since the sample mean is the same as the population mean.

Now let’s consider the same example, but with both θ₁ and θ₂ unknown. Using equation a) above we get:

ln ( L(X| θ₁, θ₂ ) ) = ∑ [-(1/2) ln 2π θ₂ – (X_i - θ₁ )²/2 θ₂ ]

Now we take the partial derivative with respect to each unknown and set to zero:

¶ ¤ ¶ θ₁ ln ( L(X| θ₁, θ₂ ) ) = 0 + ∑ (X_i - θ₁ ) / θ₂ = 0

¶ ¤ ¶ θ₂ ln ( L(X| θ₁, θ₂ ) ) = ∑ [ -1 / 2θ₂ + (X_i - θ₁ )²/2 θ₂ ]

Þ θ₁ = ∑ X_i ¤ n = `X and θ<sub>2</sub> = ∑ (X<sub>i</sub> - `X) ² / n = s²

Note: This is a biased estimation for θ_2, since it is not the expected value for sample variance. However, as n®µ this estimation moves toward the unbiased function, which is the population variance.

Suppose we have a sample that is distributed as shown below:

* ******* * * **********************

If we try to fit this data into a normal distribution, we get a broad curve since the data has high variance. Another possibility is that we have two Gaussian distributions, which results in two curves with lower variance, “mixed” according to some ratio.

Mixture Model:

We have two parameters: t₁ and t₂ known as the mixing parameters, where t₁ + t₂ =1. We have two normal distributions: N( m₁, s₁²) and N( m₂, s₂²). A sample is drawn from the first distribution with probability t₁ and from the second distribution with probability t_2. This can easily be scaled to n distributions.

Now to perform parameter estimation, we need to know how to classify the sample points into the different distributions first and then calculate the mean and variance for each. However given the sample data we do not really know sample membership. We can use an algorithm called Expectation Maximization (EM) to estimate the parameters in this model, as we will see later.

Formally a mixture model is used to define a likelihood function as follows:

Parameters: t_i , ¦_i define the probability and pdf of each random variable contributing to the sample space.

_{n k}

L(X₁, X₂, …,X_n | t_i , ¦_i (q) ) = P S t_i ¦_i (X_j | q_i )

^{J=1 I=1}

The EM function provides a way to estimate parameters for this likelihood function. We will discuss EM and model-based clustering in more detail in the next lecture.

For now let’s look at an example of application of model based clustering to gene expression.

Note: The example discussed in class came from Dr. Ruzzo’s paper: Model-Based Clustering and Data Transformations for Gene Expression Data, which can be found at http://www.cs.washington.edu/homes/ruzzo/

The presentation used in class can be found here

Also, there is supplemental material at http://www.cs.washington.edu/homes/kayee/model/