Unimelb COMP20008 Lecture 5

This material is made available to you by on behalf of the university of Melbourne under section one month three of the copyright act nineteen sixty eight it may be subject to copyright for more information visit the university copyright website。

Let's make a start safe if I can push the volume sound like testing testing testing testing。Can you guys hear me up the back yeah okay thanks um so welcome to lecture number number five I'm not Paul LA clearly um I'm James Bailey I'm collecturing the subject with with with Paul LA and lectures are a combination of of of both of us doing doing different things so the plan today well before I get on to the plan today just to say that the the project is imminent and when I get back from this lecture and and and spend an hour doing a final check I I'LL release it on the ls and you'LL have about about three weeks to to to To Get through that okay so keep an eye out for that late late this afternoon today what's the what's the plan today。

Pauline didn't't quite finish the the outlier detection section so I'm going To Going to finish that off that's from lecture four on on Friday um then then what I want to do is is get into it's it's missing values but it's a slightly a different type of missing values it's in the context of recommended systems so we're going to look at look at a couple of techniques for that we made a first some some of it to till Friday and Friday will also start visualization okay so so that's the plan a question to think about I'LL come back to this question maybe because I'm going To Go back and pick up from where pauline was here we go。

So as as as as you got to the end of last lecture was about it was about outliers and pauling was talking about what isn't outlier why we interested and the question is how do you find them um you can do you can do all all kinds of different things simple things exotic things um she started doing box plots so we'LL quickly just refresh our memory there um and there's there's a bunch about the techniques you can use there's a whole library of techniques you can use to find to find outliws and let's just let's just review them so there。

The a technique that pulling was was covering was was these things called box plots and the idea is you sort of sort your data from lowest to highest like ah a ruler from the lowest which is zero up to the highest which is above two you find the middle value which is the mediadn and that's that that horizontal line you have a box surrounding that and that sort of gives you。Um splits each of the hves in in half again so you get these these things called called quatiles which tell you the the center of h of h half so it's like I split this class down the middle and then I recursely split this side in the middle and that other side in the middle those are my my my coileils and this this this distance the sort of the width of the box is is something called into quata range and that's just a measure of spread so fifty percent of the data is going To Be in that in that range and there's some rules about about how you do it you can read those yourself you'LL get some practice in workshops。

And the question is what if you'VE got you'VE got outlines so what if you'VE got you know really high values that are far away from everything else so in the in the simple scenario you you you have these things called called whiskers so sort of like the the mustousache you'VE got these whiskers that that give you the maximum and the minimum but if the if the maximum and the minimum really high it's pretty hard to draw the box plot well um and so people do it a little bit differently they they they in fact。Make the whiskers mean something a little bit different the the whiskers just tell you how far away you are from the center so there's a rule for the whiskers and then you you color the outliws according to some logic so you you give it a a black a solid black if it's if it's very far away and you give it an open an open circle if it's far away but not but not too far。

Is is the idea so depending on how fair it is your color it and and that gives people an idea about about outline。And you might ask me James where do where do these rules come from why is it you know you got a rule you fill it in black if it's three times。The intercota range of it's three times the width and you do something else if it's one and a half they're just rules they they're not necessarily the only way to do it but they're a convention that um that people use so everyone can synchronize um so hopefully that's where pauling got to when there are any lingering questions from from from that before I before I move on will see an example in a moment I'LL keep moving um hisstograms was the was the other thing so you'VE all seen hisstograms the idea is that we that we just have a visualization that that tells us the you know the distribution of the data so where it's all where the most points can be can be found so we'VE got we'VE got a scenario what have we got we'VE got some transactions some money and。

We don't put it in buckets so if it was a if it was a small amount in the transaction between zero and a thousand dollars we put it in the first bucket if it was between one thousand and two thousand we put it in the second bucket similarly third bucket fourth bucket fifth bucket put it all inTo Buckets it's a hisstogram and it tells us。Tells us about how the data is spread across the different across the different values and so the idea is if I have a value that's that's way out to the right if it's seventy five hundred very very far away from anyone from anyone else and so that'you might you might argue that that's an outlier so you can you can use it in that in that way。

's all great you might ask how do we choose the bins the bin size how many bins how many bins do we have how wide are they and that's a bit of a a tricky one some rules of thumb but again that's there's a bit of an art an art to and it probably depend on on the data the data that you'VE got and and some of your own you know your own judgment about what looks good。But it's it can be a tricky thing。So hisstograms are a good way to to visualize data to to look for outlines and here's a he is a figure that that sort of matches matches them up so what we got we'VE got we'VE got some data the top one we got some outli and how do I know it's got outliers。

Because I can see that I got those circles in it so the circles are telling me outlis outlis you're in there so I got these these circles and it looks like most of the data is squashed around around fifty and that sort of it shown in our histogram on the right most of the data is in a narrow a narrow band around around fifty I'VE got another one down the bottom this time it doesn't have outlis um you'VE got somes it's it's not a great visualization but assume that there's no。Yeah there's no there's no circles it sort of looks a bit like a circle but I don't think it is a circle there so the idea is that everything is not too far away from the maximum and the minimum and looking at the histogram we can sort of we can sort of see that that's that maybe maybe be true it's not not spread out too much whereas in this one if I'm out at two hundred and I'm very very far away from the from the center。

All right maybe a practice。Before we do the practice we'LL just show you the next slide which will help so if I want to match up my my my hisstogram box plot this is what it looks like so。I just take my box plot and I put it sideway and I I I you know I have the lowest the lowest to the highest and you can see the the middle the middle kind of matches up with the middle here。So let's do an exercise see how we're going full screw to activate it。

And full screen。So。It's。Slightly small changed URL from the one poor lines probably used with you because I can't use the same one she has it's almost the same go there and vote well you think this。For this box plot you think whether this box plot corresponds to which of which of the four。

Twenty seconds then we'LL have a look。All right so the answer indeed is c。Most people have have gone for that weve got some outlis at b maybe d let's let let's have a think about the the box plot so you can see that the middle the the the middle value is is quite close to the minimum so you got this minimum down the bottom the the the middle the middle is quite close so that suggests that a lot of the data is is squashed squashed down towards the minimum so a lot of the points can be found in a very small small range down near the minimum value um and whereas the you know they're more spread out as you as you go up to the up to the maximum so some of these points up here a well away from the um the middle of value and you can sort of so it's ascymmetrical I suppose is another way to to think about it so that's why you wouldn't you wouldn't have number a because that sort of suggest everything is。

Spread spread evenly uniformly so there's an a an niceymmetry about it and the the clue is the most of the。

Most of the points in need minimum any queries or or questions or comments on on that one。Right okay。So so what did you got in your pocket youve got hisstograms you'VE got box plots and you'LL be you'LL be practicing them in your in your assignment both of both of those there'as I said there's lots of ways to detect that lives this there'last one the second last one this this this um next one is it's got more of a a statistical flavor so if you're a stat student or you'VE done some stats this this this will be this will be very familiar to you but its it it's it's coming from a a statistical direction and I guess the the idea is that in statistics a lot of the time you'VE got the data and you you model it using some mathematical function some some distribution um one of the very popular distributions is called a gasci distribution like a be curve um so based on based on making that assumption about。

Your data you can you can DeFine a way to calculate outlis and。This this particular method that I'LL show you the flavor of its I'm calling a UNI vaariant so it looks at just one one attribute at a time so one by one by one you can you can apply this this test um what do you do um well the the formula is telling us that I I compute I'm trying to I'm asking the question are there any outliws in my data set doesn't contain any outliws so I I try to find the worst case and the worst case is I found I find the data point that gives me the the largest value of this formula and that's the data point that when I subtract that the mean value and divide by the standard deviation it I find the max of that so that's an an example。

Here's some data we'VE got eight eight numbers。Eight eight measurements and first thing we do is we we compute the average the mean and that happens To Be two hundred and six something we all could also compute something called the standard deviation um you can you can look up the formula for that but it's essentially a measure of of spread how how how spread it is it's just the number you put it into a formula and for each for each data point I calculate I subtract the main I divide by the standard deviation I get a I get a I get a number this number down the bottom point four four nine for the first one point four three six for the second one etcter etctera etctera。

And so that that number if I if I do something with that number if I thresholder or I I put it into a a stats package I can I can get a I can get an indication of how extreme it is how how statistic unusual that particular point is compared to compared to all the other ones um so that's that's the flavor of what's what's happening let's see visualization perhaps here we go this one that's safer。Okay。This is just some website that let's me play around I'VE got I'VE got some data to hisstogram。Here'is my my histogram and you can see it's got this this normal shape kind of like a bell bell curve so most of the data around the middle。

So in in this case my my my my middle my meaning is four point five and then the the SD is the standard deviation is just telling me how spread my data is on either either side of the mean and you can see that that almost all of the data is within two standard deviations of the main。So if you're if you're two if you're if you're within two standard deviations distance of the mean most points are likely To Be covered by that by that rule approximately ninety five percent。Now I can play around with that let's have a play so I can I can move what can I do I think I can move blocks see if I can do it。I can I'm moving blocks so I'm moving some of the stuff from the left to the right what have I done I'VE I'VE shifted the main to the right。

A little bit so now it's now it's four point seven five now I can I can keep doing that I'keep moving things to the right。And I'm putting it all in the middle。And you can see how the mean is changing these points one and eight you can see there are a long way away from the middle how many standard deviations maybe to three four three or four standard deviations away from the middle so that's giving us some some indication that points this one and that one are are outlis based on the number of standard deviation。Units they are away from from the main。And you might ask well how far is too far how far is far so if if I'm three standard deviations is that really far or if I'm five do I have To Be five way To Be really far and again that's that's going To Be a little bit of matter of of judgment if you work in the social sciences if you do psychology often if you three standard deviations away from the middle that they regard that is pretty far。

In the social sciences in physics if you're trying to find out whether a physics result is unusual。If you're looking for say that higgs bos on you do an experiment you want to know wasn't unusual did I find the higgs Bo on be five standard deviations so you have To Be really really far in order for them to regard it as as unusual or far。Okay so that's that's that's a sorry that's the flavor of。

Rubsrubs test any any queries comments。Questions on that。All right。Well last one's easy you want to find an outlaw draw a picture draw a draw a scantter plot okay so here I'VE'VE all of these dots are football and they there's a plot that shows us for each football up I think the way axis is number of goals and the X axis is the amount of time they spend playing on the field so it draw these football I plot them on the on the on the scatter plot and particularly you can see the red one is very very far away。So you might and thats that guy at the top Daniel John kisa so based on these attributes because he looked so far away and we could say he's a he's an outlier just using our visual visual visual judgment。

Okay that's two day three day you can do the same the same thing。So this is this time it's a basketball basketball data set so this guy car cover you can see he is unusual in a sense that he'far away from most of the other most of the other players when I just consider these three three attributes。Okay so that's that's the final the final way you can do outli so summarizing what what I just said。You can do box plots。Method one you could do histograms look at the histogram method two you can do your your statistical tests your grabs test method three or method for you can do some visualization。

Again you'practice most of these in in your assignment you can draw visualizations of box plots and histograms and so forth all right good。Any queries or questions or comments before I move on to the next slide pack which is recommend recommend a system happy to take a moment。Anything。All right we'LL move on so here we go so。Recommended systems so when you first see this this。We're talking about missing missing data again so we're talking about missing data and fill in fill in data and we're talking about it in a very。

Specific context okay so we're we're talking about in a context where we're recommending things to to to people so。Classic example we all know movie recommended systems here we'VE got three people James John and Jill we'VE got some movies that they watch and they'VE been very nice to us and they'VE told us they'are rating for some of those movies they'VE given us feedback about how much they like each of those movies。And if we Netflix what we want to do is we want to predict the missing writingtings so we can recommend recommend movies to to to all our other customers okay。So it's we got missing values and we really really want to know what those missing values are if we'if we're Netflix because then we can make good recommendations we can。

We can please our customers we can delight our customers if we tell if we give them the suggestions that they like。Amazon through this we we see it everywhere book recommendations this numbers probably gone up seventy five percent probably small these days um personalizations and other name for it so if I can if I can give you a personalized recommend again you'LL have a you'LL have a better experience you're more likely To Be part of my my ecosystem。Where else where else do we see this so I guess online online dating recommending recommending people to to meet social networking recommending people to follow music jobs LinkedIn。

It's it's just a whole whole heap of stuff it's happening everywhere to us university maybe I don't know if we do that much of it at the university the university recommend anything to does it suggest what subjects you should be doing um maybe it does a little bit probably could do a better job。So how do we how do we do it so the idea is that you'VE got some model of the user you'VE got some attributes about the user。You'VE got some？Record of what they'VE been doing so they'VE been giving scores saying I like this movie or I I like this person or I like this song whatever um it could be explicit they give a score or the pace of money or it could just be some implicit measure that we we see how long I spend looking at it and if I spend longer it probably means they like it and and you can you can measure measure that。

So the idea is that we want to fill in filling the missing values and the logic is fairly simple we we make predictions about your missing values based on what everyone else is what everyone else is doing。So we we somehow look at the global global behavior and use that to make inferences about an individual and what what you like what you what you don't like。Based on your history based on everyone's history。So that's the that's the setup um you can you can make it a bit more mathematical what's what's happening we'VE got some rows which are users we'VE got some columns which are items which are movies or songs or whatever and each user writes。

Some of those items so you give a score for some of those things and for a particular user and a particular item we want to fill in the missing value so it's it's in mathematical terms it's learning a function's learning a function that that tells me what the the missing value is and and then we can recommend that recommend that to you。The question is how to。How to do it and and again the idea is fairly intuitive I can do it different ways one ways I recommend things to you based on。Based on people who are similar to you。So I recommend things to you based on who your sort of who your friends are sort of intuition so that's a user a user based technique recommendations based on people who are similar to you。

Another way to do it I make recommendations To Based on。Similar things you like so if you like action movies I'm probably going to recommend more action movies to you。Um if you like romance I'm probably going to recommend more romance to you is the the sort of the the flavor um so you can either look at the the the people who are like you or the movies that are similar to the things you like or you can do them both together and that's a rather more complex one that I'LL give you a flavor of but it's it''s it's outside the scope of what you need to know for examinations。So he is he is。Here's a actual data set so we'VE got we got users weve got items these could be movies or they could be you know anything you want they could be schools on an exam and we have to fill in the missing the missing bit。

Automatically we don't get to ask anyone any questions we just need an algorithm that takes this data and and feels in the missing the missing thing。Based on based on what you'what you'VE got。So in Netflix we have this huge database of all our customers and all our movies and all all the ratings they'VE given for those for those movies。All right so that's the that's the setup we look at the the Tech next next but I'happy to take a question or a comment before we move onto specifics any anything about the problem setup。That is'not not clear or you'd like to ask about yes from。Such man or a like man。

So the question is where does the data come from eighty five right so so where does this where does this come from so it'will depend on the application but。Um if these are if these are a rating out of out of twenty for the movies then then what's happened is people of some people have watched these movies and I'VE been asked to feel in a short survey at the end and they put in the number and that's that's what we'VE got we'VE got there we'VE got their recorded recorded writing that they are asked To Give。That's one that's one way to do it。Or maybe they watch the movie and we we maybe they clicked on the movie and we measured how long they looked at the movie before so it's it's it's number of minutes before doing anything else it could be a time。

So that's an implicit and implicit type of measurement as well so I could do it I could do it like that too does that answer your question okay good good question any other queries questions。Okay so question is how to how to do it so what we'LL do is well'we'LL we'LL just say that the flavor of the the user base methods first so the ideas we'VE got five happy users and one of those user users is the person we want to target we want to fill in their writingting for for something we want to infer their writing what do we do so first of all we。We we find out how similar they are to to everyone else so I find out how similar they are to everyone else and I choose a subset of those of those people so I'm not going to compare you against everyone else I'm going to compare you against the subset of people who are。

Similar to you and in this this case I compare you against the three the three closest people to you so we're just going to concentrate on those three。And then based on those three I'm going to I'm going To Be out of guess your writing your missing value。So various questions here one is how do I measure similarity。How how similar are you for the person sitting next to you。How similar are you to the person who watch these other movies we need a mathematical measure。We need a way of choosing which people to to compare you with the those three people um and and based on all those three people will somehow have to aggregate or or vote or or somehow use all of the information we'VE got to to predict your rating for a particular a particular movie okay that's that's the idea。

So breaking it breaking it down one one here's an example we'LL see how to do it for example we'VE got two two users u one u two and the columns are the the items so each of these users has rated one two three four five six items or rated some subset of them。So the the dashes are the missing things that they didn't bother to write and we want to find out how similar the two users are and you just comparing those two rows you need some mathematical measure for doing that。What what we'VE got here is one way to do it there's all kinds of ways you could do this but a simple way to do this is fill in the missing values so let's。

Let's do it so my first my first missing value is is eighteen point one and I'VE done that because that's the average value for that for that user and I do the same thing for the other user。Fourteen point one fourteen point one so now I now I don't have any missing values fantastic now I can compare those two two Rose and a simple way to do it is I just just compute the distance between them you clearly distance it's just the square root of the sum of squares。Of the the h h column so seventeen minus eight you take a different square eight point one four point one take a different square at it all up take the square root and you'VE got a distance。

So what does it mean it means we'VE got a number that tells us how far apart those two users are the bigger the number the further they are the more different they are the smaller the number the more similar they are。So we'got the distance and then what we really want is not a distance but a similarity um two words that you know related but but kind of opposite so the idea is that if two things are very far apart that'VE got low similarity if two things are very close they'VE got high similarity。So we need to we need to turn our distance into a into a similarity and we'VE just got a simple way of doing that we we just use this formula here and now I'I'VE got a number and it will be between zero and one and will tell me how similar you one and you are be some number between zero and and one。

Query questions on on on what we'how we'VE done that or any of the steps。Question down the front yes。The question is why why use the mean value for missing values the answer is it'just a simple it's a simple way to do it it's certainly not the only way to do it。And you might look at this and you might criticize and think it's a bit a bit naive a bit simple。Is that what you're thinking is there another way we could could do it would be the question。So maybe we have some other technique instead of main value we could plug that in here and use that to。That's also fine this is just a simple way to do it。

And you know we don't have To Get a really exact similar we're just looking for approximate similarity we're finding people a so you know close to me similar to me roughly roughly similarly roughly similar to me。Okay that's just an example maybe'you can practice that yourself。Um this this this slide here is just to make a note that you know another criticism you might might make is that maybe you don't like you think there be other ways to do this instead of u clearly distance and the answer as you'd be right you could comp correlation we'LL see that later in the course and there's all sorts of other more exotic ways of computing similarity but we won't get into them。Okay so what have I got I'VE got I'got a way of computing how similar I am to someone else based on based on those those ratings。

So what do I do at run time。Netflix wants to。Work out um you know what what my what my rating might be for a particular movie so it needs to work out what are users to compare me with so we can compute the top k。Most similar users so the key most similar people to me we do that at at runtime while'while I'm interacting with the system and then what do we do we just take the weighted average of their ratings。So you know I'VE got some I'VE got some movie。Um what's a movie aquaman so I haven't given a rating for aquaman Netflix finds the the three most similar people to me um who have given ratings for equaman and it just takes the average and that's what they infer that's what they infer for me。

The average is three point five then they think my rating for acqua man would be three point five based on the three people who are closest to most similar most similar to me。Very clean simple simple way to to make a estimate of what my writing for aqua man might might be。In fact that clear any questions there。We'VE got a measure for similarity find the similar people aggregate their ratings and that's that's how you get my writing now an issue is that。Sort of hidden here is that it can be pretty slow if you if you're really going to do it like this it would be pretty slow Netflix has I don't know tens of thousands millions of customers you don't want to have to spend a lot of time searching for。

People like me while I'm while I'm browsing their website that could be slow so you might you might want to。You know do it a bit quicker maybe a bit more approximately so one one trick you might do is instead of having every modeling everyone as an individual you could model groups instead of individuals so I I just say that you know in this example I want to have four groups and I'm going to compare me I'm in the center I'm read I'm just going To Be compared against the middle of each group so that's four four comparisons。Four similarity calculations rather than you know dozens of individual calculations against each each dot in that in that figure so the idea is you might you might speed it up in this sort of way。

What else to say in practice this is quite a popular method seems very simple but it's quite quite popular bit slow potentially you might speed it up another issue is that everyone it's very dynamic we're all watching different movies we're always updating our our ratings。Um so the the the model of h user is constantly changing so that means the similarity are constantly changing um so it's a little bit hard to pre compute this stuff you have to you have to keep keep upd dating it because it's always changing now the problem is new users what if I don't know anything about you I got no history for you what do I what do I do。

Who how do I know who you're similar to it you never watched the movie with Netflix before what does Netflix recommend to you。So it might discuss that a little bit in the in the workshop。Okay so that's that's the user user and I think it's quite intuitive finding people like you another way to do it is an item item based way to do it so。The idea is that we want to infer your right your writing for aquaman。We find what other movies you'VE watched which are similar to aquaman and see what your ratings were。So you know maybe watched some other movies about I know similar things they have fish or water or whatever um somehow we used those to infer infer what you think of aquaman so this is item item before I talk about it I'm just'm going to refresh your memory with with Greek letter notation you may may not have seen it。

We're going to use it the idea is it's just an easy way to write things out so you said this big Greek letter sIgMa and you got some。Sub script super scripts it just means some ADD things up and you'VE got an index which is I you ADD things up starting at one going up to five and you can you can make it a bit more complex you could have multiple things that vary but you'suming over one of them same sort of thing or I might not even specify the the the limit might be a variable itself。So。Bearing that in mind itemsem items we're going to need to compare items we're going to need to compute which items are similar to each other so which movies is a command similar to。

So I'going to compare this column against that other column。Okay。Same sort of thing so what are we going to do for each item aquaman we're going to find the kos similar items to aqua so the kos similar movies to aquaman。We can do the same sort of thing as we did for the user user for those those similarities those distances。And then so we do that offline we do that you know before any before before we even before we even have to make any recommendations we just do it as a a priest step。Then when we'VE got a user who's browsing online and we want to make a recommendation based on a predicted rating we're going to make a prediction。

Just as as a waited sum so your your rate for acquaman is the the weighted average of。Similar the ratings of similar movies to a man that you'VE you'VE rated so you'VE rated these similar movies take the weighted average and that's going To Be what I predict you think about about aqua it sort of looks a bit a bit a bit messy it's good to see an example so so here's here's our example we'VE got we'VE got some users。Rose got some columns movies we want to predict what does TIM think about inception what'what's his writing。What do we do so the first thing is we find out which this is offline before we even see you know before TIM is even browsing offline we find out which movies are similar to inception okay so inception is similar to which movies。

We do exactly the same thing as as before we compute a distance。So I I I should say I I feel in the missing values using using the the average like I did before I just done that they're involved then I I compareute I take other movies and compare them to inception I compare titanicception it has a distance of one point zero eight a similarity of point four eight I compare batman to inception it has a distance of three point two four similarity of point two four ETC and what do I do I take the top three similar。

Movies。So the three most similar movies to inception are Titanic the Martian and Jurassic world。You might like to reproduce the calculation make sure we'VE got it make sure we'got it correct get see you get the same numbers。So I got my top three movies and then what I do at um for TIM I want to find out what'he's writing for inception I take the three most similar movies that is watched。So TIM has watched Titanic the Martian and Jurassic world and he's given rating three of them three three point five the three I combine those using a weighted average in this formula and I come out and I predict that TIM has a。Would give a writing of three point one for for for inception。

So I'VE got a number tells me how much TIM likes inception based on similar movies that he has rated。Query question on that yes question yet。So what if TIM has so so so what what maybe for example if TIM hadn't rated Titanic we wouldn't use it so that would'be one of our kos similar things that we choose we just find the the next most similar。Good good question yeah okay so I'LL just say that again in in in this example TIM had actually rated Titanic and we were able to use it To Guesss his rating for inception if he hadn't rate a Titanic we wouldn't even bother to to use it because he's never we got no data for him about it really。

Do now that query question or about just answer it。No okay great so I encourage you to have a look at these calculations this calculation so if you can reproduce it。We can finish up there and maybe next time I'LL I'LL close this out by talking about how to do both of these things together all right thanks。

Hopefully the we it'all。

So doesn't from just use methods desc。'just。

I'm not sure if I'understood so what can'you do。So what is tell me what the problem is so this is。It matters that should receive us like this one。The。What did you just use it。会好的。为什？Can you if you using a map can use to not you know you know not pet。

So notepad is an APP that application of the map map you just talking on notpad you should better say。I know I think thatll work with that's how I do just type in no。Answer question yeah this three that the three one that take doesn has that this walk is but is we type next that what have like only two dollars nineteen like for two but not but you just start you。Yeah'。