Statistics 4240 - Data Mining

Professor,

Do you want to see estimated sigma or sigma square in the solution? Or, either one of them is fine? Thanks.

Either is fine. D.

I couldn't get the exact answer for example 8.5.1 as well, my answers are pretty close to yours.

Dear Professor,
The starting point is not that important, but the choice of threshhold of the convergence is very important. Is the threshhold must less than 0.001? Because when I chose threshhold under 0.001, it converge to same points.

The threshold should be set as small as you can - of course if you set it too small then the program will run for a very long time. D.

Has anyone managed to exactly reproduce the MLE's for the example in Section 8.5.1 of the book? I get pretty close but not quite the same:

mu0= 4.655897 var0= 0.8188169 mu1= 1.083148 var1= 0.811348 pi= 0.5545861 logLike= -38.91337

-

These starting values work pretty well: pi=0.6, mu1=0, mu2=4, sigma1=1, sigma2=4. D.

I think in the book page 238, the formula for sigma_sqaure_2 (variance of the second dist.) is wrong! (for EM algorithm) it should use mu2 (NOT mu1 !). Is that right?
I guess we have the coorect formula in the class ppt file.

Well spotted! Yes, the formula for sigma_square_2 should have mu2 in place of mu1. D.

Projects are due 5pm December 18th preferably via email. D.

For HW2, are we supposed to get the same estimates after certain times of iterations, no matter what u1, u2 we choose at the very beginning? My results are kind of different each time I ran the program, so I guess there must be something wrong with my code?

If you use reasonable starting values you should converge to the same place most of the time. Try pi=0.6, mu1=4, mu2=1,
sigma1=1, sigma2=2 and see what happens. D.

Dear Professor, could you go over the R program again next Tue 5:00pm, some of us missed your post and didn't make the 5:00pm session yesterday.

Sure - I can do that.

According to the book, a good way to construct initial guesses for mean1 and mean2 is ramdomly choose two of the observations. Can I plot the histogram and guess the two means instead?

Yes, that's fine.

How to calculate the responsibilities in the expectation (textbook Algorithm 8.1)? Can you explain in more details? Thank you.

Its just formula (8.42). The function phi stands for the normal density function. OK? D.

Professor, will you be available for homework or project questions this afternoon or during our class time? Please let us know the specific time you'll be in office. Thanks.

I'll available right now for a few minutes and again at about 4:30pm. I'll go over an R program to do the homework at 5pm. D.

Dear Professor:
You probably have told us about this, but I forgot.
How many pages should the report on the final project be? excluding codes
What issues or aspects should we address in report ?
for example: data sources? question? methods?
Thanks.

There is no page requirement. In your report you should describe clearly the problem you wanted to solve, the methods you used to solve it, and your results. D.

Dear Professor:

For HW 2, do we have to sort dataset at first? For R user, there is a package call "mclust" for EM algorithm, is it ok to use this package? Or other package you can recommend?

BEST
Feng-yu

No need to sort the data. Like the last homework, I want you to program this yourself. You can use any language you want or even Excel! D.

Right now the data set we tested the scan statistic was about 500 points, what if the points are less or more, should this affect the selection of number of iterations(999 or less or more) and also the selection of the initial window size.

Thanks,
Vandana

Generally the 999 has nothing to do with the size of the dataset. The dataset size might have some bearing on your choice of smallest window size - that depends on the particular problem you are looking at. D.

This is a very nice introduction to R

I'm using SAS for HW1, it will take long long time to permutate 999 times, will 300 times be OK? Thanks.

Sure. D.

Dear Professor,
Can you post the second homework now? We can have time to think about during the thanks-giving break. After that, the time will be very tight with all the finals approach.

Thanks.

I just posted the second homework assignment. D.

Hello professor,

In a varying window based program, should the minimum window size affect the output.Meaning when you do 1 to 2,1to3,...1 to 250, 2 to 3, 2to4, ...2 to 251 and so on
if we do 1 to 5 1 to 6 1 to 7 ....2 to 5, 2 to 6 and so on
the cluster window varies by a few locations meaning couple of points fall in or out of the window based on the initial window size.

thanks

Yes, in general the minimum window size does affect the answer you get. You need to think in advance about how small a cluster you could imagine being interesting. D.

Professor,
In the previous post you say

"Note you are not touching the locations here. Just sort the 0's and 1's in random order."

For a variable window should this matter since you are basing your iterations on each record and counting zero's or one's

For variable window if iterations are based on 0s and 1s, not miles , ie the window size is varying based on fatalaties and not miles so for example I start with the first point and go till first point then first till second, first till 3rd and so on , and then randomize the fatalaties and do this 999 times. Shouldn't it matter only if the window is varying based on miles.
Does this make any sense?

Thanks


I'm not exactly following the question. Note that the null hypothesis here is that there are no clusters. In considering the evidence against this hypothesis, we don't want to alter the locations of accidents along the road. Neither do we want to alter the total number of fatal accidents. D.

Professor,

I wanted to confirm the procedure to find the cluster..


1st iteration:
Sort the records based on location
Do permutations starting with 1st rec.
1 to 2,1to3,...1 to 250, 2 to 3, 2to4, ...2 to 251 and so on

For all these windows I calculate the lambda values.
So there will be probably 2500 lambda values for each iteration.
From all these lambda valuies I select the minimum and store it.
Also need to store the window for this one right?

Correct.

Now generate random nos.Sort data based on rand numbers.Do same
calculations.Generate lambdas.
Do 999 such iterations.

Note you are not touching the locations here. Just sort the 0's and 1's in random order.


So we calculate the cluster from the first iteration (without randomization) right?
Finally sort the 1000 lambda values & calculate p-value.

Is this procedure correct?

Looks fine! D.

Professor Madigan,
Could you please confirm that the alternative formula for lambda provided last class is correct?

Lambda = ((Xw/Nw)-(Xnw/Nnw)) / (((Xw/Nw)*(1-(Xw/Nw))+((Xnw/Nnw)*(1-(Xnw/(1-(Xnw/Nnw)))))^1/2


Well, I don't know about "correct" since there are really no restrictions on the test statistics that you use. Having said that, it would probably be best to use the appropriate variance term, and the expression above (and possibly mine in class) is missing the sample size terms from the denominator. This would give:


Lambda = ((Xw/Nw)-(Xnw/Nnw)) / (( (Xw/Nw)*(1-(Xw/Nw)) / Nw )+( (Xnw/Nnw) * (1-(Xnw/Xnw)) /Nnw ))^1/2



When should the homework be submitted?
Tuesday 5pm via email.


Also, since we don’t have many classes left until end of the semester and we may not be able to cover all topics, Could you please try to cover these 2 :
1. Support Vector Machines
2. Multidimensional Scaling

I was not planning to cover multidimensional scaling. Are other people also interested in this topic?

Professor,

1. I wrote a program to find the Lambda, how ever it kept giving me some infinite values or some other error values, I tried calculating lambda in excel too, however I still get same thing. I am doing a variable window so here when we do the Xw(1s in window) and Nw total pts in window, if both are equal then one term in the numerator is definetely zero, maybe more. If we add .5 to all it still dosent solve the problem. I know you said that some people got results, but I am stuck on this.Should I try using a different lamda as you suggested, but then again it wont solve the problem as you mentioned.

You can just skip windows that are all 1's or all 0's. Or, you can add 0.5 to x_w and x_nw (e.g. suppose inside a window there are 3 1's and no 0's. Then transform that to 3.5 1's and 0.5 0's.)

2. For variable window my iterations are based on 0s and 1s, not miles , ie my window size is varying based on fatalaties and not miles, is that incorrect. so for example I start with the first point and go till first point then first till second, first till 3rd and so on , and then I randomize the fatalaties and do this 999 times. Is this incorrect should I be varying my window on miles. I did go through the posts but I guess I dint undterstand it correctly.So wanted to make sure.

It doesn't make any difference because in the variable window case you are going to look at all possible windows. D.

Thanks

Professor,

When working with variable length windows are we taking random values for window length and adding up to mileage
eg. data is 10,25,67,.... and we add 10 miles for first window,15 miles for 2nd window and so on..
OR
we are supposed to randomly choose a certain number of records everytime we calculate.That is here the window is the number of records or the mileage?

Thanks

For the variable length case, the idea is to compute lambda for all possible windows. There are only finitely many of them so just enumerate them all (well, all except windows that cover say more than half the length of the entire road). Does that make sense? D.

Should the window size have a minimum? Would it make sense if we found a window with say 3 accidents? D.

It still isn't clear to me to which terms you would add .5. In what you last said, it seems you were adding it to the exponents but that doesn't help with [1-(x_w/n_w)] when x_w = n_w.

Suppose inside a window there are 3 1's and no 0's. Then transform that to 3.5 1's and 0.5 0's. D.

I'm really struggling on finding a usable lambda equation. I gave up on the one in the lecture because (1) you don't want to discard windows that have all 1s in them - they are very likely clusters and (2) the proposed solution of adding .5 to n_w, x_w, etc. doesn't work because the problem occurs when X_w = n_w so adding the same number to both of them won't help.

You have a point when you say that using a lambda that does not compute for windows that are purely 1's or purely 0's does not seem very satisfactory. However, using lambda some students have already gotten the "correct" answer to the homework. "Correct" here means they found the cluster than I inserted into the data.

Concerning the 0.5, what I meant was to add 0.5 to x_w and to n_w-x_w, etc.


I tried to simply look at the probability of a window using the following equation (prob_fatality)^X_w(1-prob_fatality)^(n_w - X_w). It doesn't work though because it is lowest for very large windows.

Could someone post a lambda that works?

You could try the "weight of evidence": log(Pr(fatal|window)/Pr(fatal|not window)). You will have the same problem with zeroes and again you can solve it by adding 0.5's. D.

No class tomorrow at 5pm. I will have an office hour at that time. D.

Professor,

When we use fixed length windows :
For the first iteration we sort the data based on the mileage and do calculations.From next iteration onwards we generate random numbers against each location and then sort the data based on the random numbers.

Right, but you don't sort the locations. The locations stay where they are. Its the labels alone (ie "fatal") that get shuffled.

Now, for the first time we can add up 5 or 10 or whatever miles to the location to get the next window and so on.But from the next iteration since the data is sorted based on random nos. do we have to take random nos. into account for windows or have to consider the location?

Thanks

Just to reiterate in case anyone misses the posts below. I made a mistake in class - its small values of lambda that we are looking for. Sorry!! I corrected the powerpoint slides on the web page. D.

BTW, does everyoe see why it should be smallest lambda? D.

To the classmate downstairs: After Dr. Madigan changed the largest lamda to the smallest lamda in the slides, the window with the smallest lamda is unique in our problem. So you don't have to worry about the case that there are multiple windows with the same smallest lamda. If it happened, the p-values for all the windows with the smallest lamda would be same. It will be more likely to happen in fixed window length situation. Hope my understanding will help you. :)

If we have several windows with the same lambda, do we need to include all those windows in the p-value computation?

Professor,

For the HW, how many iterations do we have to do of the calculations ideally?

Thanks


999 is certainly enough. D.

About HW: Is it necessary to compute p-value for each window or only one p-value must be computed for the whole problem and lambda values for each window get compared to this unique number?

You compute lambda for every window but its only the smallest lambda over all the windows that gets included in the p-value computation. Does that help? D.

In those special cases where lambda is NOT defined (division by zero) can we replace lambda by 1 so when compare to p-value it is not significant?

Sure - it won't make any difference since 1 will never be the smallest lambda. D.

Just to reiterate in case anyone misses the post below. I made a mistake in class - its small values of lambda that we are looking for. Sorry!! I corrected the powerpoint slides on the web page. D.

sorry professor i didnt read your reply properly .. ur last reply answered my question. so i need to sort the data set u have given and then proceed with the calculations. thank you and sorry again to post the same question

professor
wht i meant by the values in the data set 50 18 3 4 and 50 i added 50 with 18 to get 68 , and 68 with 3 to get 71 and 71 with 4 to get 75 and 75 with 50 to get 125 .so by this i obtain a new data set 50 68 71 75 125. i use this data set and use the for example a window of 5 and do the required calculation.. is this the way to proceed????
thank you

Dear Professor,

Wanted to clarify a few things for the HW.
What Xw,X-w,Nw,N-w stand for with an example

For a particular window, x_w is the number of 1's in the window and n_w is the total number of points in the window. x_-w and n_-w are the corresponding cons outside the window.

I also wanted to know if the window size is given with resp to the location (for eg if the window size was 10 and the intial value is 86 then the end value will be 96 and so on and so forth..) and that we have to add the 2nd element in the location with the first and 3 with the sum of the previous two (for eg if the data set is 50 18 3 4 50 the the dat set to be used for the window size would be 50 68 71 75 125)
thank you

I don't understand the question. The location column gives the actual location on the road measured from the start of the road. So, what do you mean when you say the dataset is "50 18 3 4 50"? If these are locations you need to put them in order. D.

Yikes! I made a mistake - its small values of lambda that we are looking for. Sorry!! I corrected the powerpoint slides on the web page. D.

I have the following questions:

1. Because the numerator is a fixed number independent of the windows, lamda is maximized when the denominator is minimized. The denominator is minimized when Xw/Nw=X_total/N_total. Thus the maximun value for lamda is 1.

But lambda is not defined when the window is all black or all white.

But lamdas in more than one windows can reach the maximum value 1. Does it mean that there are more than one cluster? shall we find out all the clusters? For example, when I am doing the variable length scan, if I choose the maximun points in a window is 60, then I have 27730 lamdas, and among them there are 145 lamdas equal to the maximum value 1. Each of the 145 windows with the maximum lamdas has 12 1's and 38 0's. Can I say that there are 145 clusters? But the windows are overlapped.(Like 6-55, 7-56, 8-57 etc.)

Interesting. I had not expected this to happen. If this is correct, then the scan statistic method will just have to report multiple windows each with the same p-value.


2. When I am doing the permutation test, I find out that almost all the maximum lamdas are equal to the maximum lamda value 1. For example, to save time I do 9 permutations, and find out that the maximum lamdas are all equal to 1. Is the p-value equal to 1/10=0.1? If I did 999 permutations, the maximum lamdas would probably equal 1, is the p-value 0.001? Is it reasonable? It seems that since the maximum lamdas are all equal, there is no effect of permutation, thus there is no cluster. Because the likelihood ratio test is to reject the null hypothesis when lamda is small. Is it reasonable to compute the p-value as 10/10=1 or 1000/1000=1( then fail to reject the null hypothesis)?

Lambda of 1 should not occur. Lambda is not defined in windows that are completely one color.


3. Is the following correct?(Po represents P_outside the window, X: the total number of fatals 120, N: 500)
lamda is the statistic for the likelihood ratio test.
lamda=max(under Ho: Pw=Po=P){Pw^Xw*(1-Pw)^(Nw-Xw)*(1-Po)^(X-Xw)*(1-Po)^(N-Nw-X+Xw)}/max{Pw^Xw*(1-Pw)^(Nw-Xw)*(1-Po)^(X-Xw)*(1-Po)^(N-Nw-X+Xw)}
=max{P^X*(1-P)^(N-X)}/max{Pw^Xw*(1-Pw)^(Nw-Xw)*(1-Po)^(X-Xw)*(1-Po)^(N-Nw-X+Xw)}
=[(X/N)^X * (1-X/N)^(N-X)]/[(Xw/Nw)^Xw * (1-Xw/Nw)^(Nw-Xw) * ((X-Xw)/(N-Nw))^(X-Xw) * ((N-Nw-X+Xw)/(N-Nw))^(N-Nw-X+Xw)] (This is the formula for lamda given in class.)
If the above is correct then lamda<=1, thus the maximum value for lamda is 1, lamda reaches its maximum value when Xw/Nw=X/N. Because lamda is between 0 and 1, why it is approximately Chi-square distribution? And in the example on the 5th slide, the largest lamdas are all exceed 1, how did these values come from?

The example on the fifth slide only shows a sample of the full set of x's.

Thanks you.

In the post about the lambda eqn, I meant that lambda is coming out smaller for windows with more 1s than for windows with more 0s.

I have following questions, for the permutation test:

1. do we fix the location column when everytime we relabel the x's?

That's an implemtation issue. Are you using perl to do this? What sorts of data structures are you using?

2. how can we choose the numbers of the random relabellings for the x's? say why we use 999 random relabellings in the slides? does it depend on how large is the dataset?

It doesn't have to be 999. The bigger the nunber the more accurately you can estimate the p-value. 999 should be more than enough.

Thank you.

Could there be an error in the lambda equation in the slide because lambda is coming out smaller for windows with more 0s than 1s?

The formula is correct - it does not favor 1's over 0's. Actually it is invariant to the labelling of one's and zeroes.


Incidentally, there is nothing magic about the LRT statistic. Maybe we should instead be using a statistic that looks for large numbers of 1's only. D.

In response to the answer to the last question, my software is calculating 0 to the power of 0 as 1 which is why it worked. But, could you answer the other question - if you use lambda as a measure should you be looking for the lowest or highest lambda?

Smallest. (I made a mistake in class when I said largest) D.

What is the meaning of lambda again? When I did a simple test with a window of 2, I get a lambda of .5769 when the window contains 2 0s, .7285 when the window has a 0 and a 1 and .0569 when the window contains two 1s. Is lambda just the likelihood of getting windows with these combinations? I thought we were supposed to find the highest lambda to find a cluster but that does not seem to be what is happening. I'm not sure if finding the smallest lambda makes sense either although it seems to bear out from the calculations. But since the cluster 0/1 had a higher lambda than 0/0, I'm not sure.

Something is not right here becuase when the window contains 2 zero's and 0 one's, lambda is not defined (see post below).

Lambda is a measure of how peculiar the relative proportions of zeroes and ones are in the window compared to outside the window. Its not particularly special - there are many alternative measures one could use. D.

For the lambda formula, could you verify that xsubw is the number of positives in the window and nsubw is the number of datapoints in the window? If so, than if all the datapoints in a window are positive xsubw/nsubw = 1 which makes the denominator of lambda 0. Do I have the meaning of the variables wrong?

That's correct - when there are no blacks or no reds in a window, lambda is not defined. You have two choices here. Either add 0.5 to x_w, n_w, x_nw, and n_nw before computing lambda, or, ignore windows that have this problem. Either solution should be fine. D.

Professor,

Now that we have the homeworks, the project and a presentation, what will be the weightage on each?

Thanks

presentation - 10%

homeworks - 10% each

project - remainder

There will be 2 or 3 homework assignments. D.

Professor,

Can we get the slides from the 5:00pm session yesterday.

Thank you.

I was going to show some examples in JMP - maybe I'll show them next week. D.

I just posted the homework assignment

Are we still going to have 5:00pm sessions for the rest of semester? I'm interested in Bayesian Model Averaging techniques and an example of how to implement it would be very helpful. Thanks.

I'll think about this. D.

I've decided to assign a few homeworks and cancel the final exam. I'm assigning the first homework today. Details in class and later on the web page. D.

Dear professor,

I am doing the project based on time series analysis.I was wondering if we could dicuss a little about issues related to seasonality in data, how to remove it.The effects it might have in case we plan to find out any emerging pattern and such other issues.

Thank you

Are we having classes tomorrow at 5:00 PM?

Any ideas for what we might do? We could have an open discussion about projects - people say what they are doing/planning to do and we could talk about it. Thoughts? D.

Professor: Could you please give some sources of good and large datasets? Thank you!

The repositories at UC Irivine are terrific.:

http://www.ics.uci.edu/~mlearn/MLRepository.html

http://kdd.ics.uci.edu/

Professor: Do you have the perl slides that you talked during the pre-class session? Thanks.

They are not mine so I don't want to post them on the web. Send me e-mail and I will send you a copy. D.

I prefer not to have final exam because the topic for the class are very broad and it will be difficult to prepare all the materials that we covered. Maybe focusing on project is a better way to learn from the class.

I agree with NOT having final exam. I think the project is a fair basis for the course grade. After all our class presentation also counts 10% of the final grade.

I agree to the policy of not having final exams, however there should be weightage on something else too, like the persentation, that we are doing in class. this way it will be subjective to every person's effort. Homeworks, as long as they are not too theoretical should be a good thing too.
Thanks

When is the project due?

Thursday December 18th at 5pm. D.

I am in favour of not having the final exam.But ,like someone has already mentioned before, am not supportive of the fact that grades will be based only on the project.
Instead can we have more weightage for the Presentations , also maybe we could have a homework where we can apply some methodologies and gain practical knowledge , and also the grade can get distributed.

Thanks

I am in favor of not including a final exam in the course, though the idea of questions like "you have this dataset, you want to do this, what method would ou use" sounds really interesting. I would have to disagree that only from a single project we will learn more . Instead of the final couldn't we just right a 2 to 3 page review (like the paper presentations we did in class) for the project that another student did and be graded on that as a final. This way we get an insight in two projects (seeing other methods implemented by other students). The project we are assigned to review should be anonymous. And for the "do it alone" concern, I guess it all comes down to how professional we are. We are in Grad. school after all And besides, I guess it would not be very comfortable going around asking people "Is this your project, tell me what you did and how....."
M.

Continuing with the discussion started yesterday about the class grading, I’d like to express my support for the idea of NOT having a final exam.
In my opinion, it is more convenient to base the grade on the final project rather than on any written exam, which perhaps would be too abstract with too many topics to cover.
I believe that all the methods that we’re learning are more useful if we know how to apply them to real data in a real world problem. The project would force people to apply that abstract mathematical knowledge of the book to a real case with numbers, rows and columns (which is the case in the majority of jobs).
Thanks.

Here's link to the powerpoint slides for the Bayesian network examples I showed yesterday in the 5pm session. D.

I like the idea, too. We can learn more useful stuffs from the project!

Skipping the final maybe ok, but how about the grade? Will the grade totally based on a project?

Yes, if we have no final, the project alone will dictate the grade. D.

I like the idea of skipping the final, so that we can focus on the project topic and do more research. There are so many interesting and useful information on the internet!

I think the suggestion of Graphical models for tomorrow is great. Besides, Dr. Madigan's idea of focusing in the paper is also good. I'm learning a lot researching in my topic and trying to figure out how to develop a model. I'd like to keep on working with it instead of preparing for the exam.

So this Tuesday at 5pm I'll talk about some applications of graphical models that I have worked on. D.

I give my vote to someone who gave the idea about having Graphical Markov example on next Tuesday.
Besides, I choose recommender system for final project, if some one is doing same project I would like to share or discuss about the idea and algorithm. If you are interested, email to ey34@mac.com.

Fengyu