Take the 2-minute tour ×

I have a set of binary vectors where each vector represents one day of occupancy in a house and consists of 48 elements (each element for 30 minutes of the day). Each element can be 1 meaning that house was occupied and 0 for non occupied house.

My task is to predict the next day based on the history of the same days (Monday from history of Mondays etc.). So far I am using hamming distance to find 5 most similar days in the history and from them I calculate the probabilities of the occupancy as a mean of those 5 numbers. When the probability is higher than some X, in my case 0.4, I predict it to be occupied.

But there is definitely some more efficient way to do this, any algorithms that would capture the trend in the history?

share|improve this question
Personally I'd just use the mode to find the most frequent state of occupation in the history for each half-hour interval. If you want to only use the most recent states, then take only their modes. I offer this only to point out that you have to decide what approach to prediction you want to take, then implement it. Using complicated measures such as Hamming distances doesn't make the predictions better unless you have solid theoretical (or practical) support for the idea that using the Hamming distance is the right approach. The same argument applies to my suggestion to use the mode. –  High Performance Mark Apr 30 '13 at 18:36
Well basically what I am doing here is a taking the most frequent block but I use the hamming distance to pick the most suitable days from the previous days based on the data from the ongoing day. So I compare the beginning of the day with the beginnings of the previous days. So there is little bit of justification for the Hamming distance. What I am now trying to do is more like create a typical day or so ,this is what I mean by capturing the trend. –  user1306283 Apr 30 '13 at 18:52
more information might be useful, for example, the nature of occupancy or whether seasons/certain months of the year might have predictable patterns. –  גלעד ברקן Apr 30 '13 at 18:53
the nature of occupancy? I am not sure how you mean it but the data are from motion sensors in the house and from them I create the occupancy vectors. I am aiming for the patterns per day because then I want to control heating based on this patters. Is that the more info you were aiming for? –  user1306283 Apr 30 '13 at 18:56
yes, that helps –  גלעד ברקן Apr 30 '13 at 18:58

2 Answers 2

Your approach sounds fairly reasonable (it's called K-nearest neighbors or KNN), though I' not sure you're using the right distance metric (hamming distance so far this day). Your method is fairly sensitive to the precise structure of a day, and it will probably take a long time to adapt to things like vacations, while being perhaps oversensitive the first several hours of a day.

One alteration of your method I would try is looking at the previous 24 hours instead of "so far this day", or using both methods and averaging the results. Eg the previous 24 hour method would pick up on a vacation pretty quickly, but the so-far this day method might miss a vacation if the user happens to have never had a vacation day on a Wednesday or something. This is a similar concept to this rock paper scissors game, which looks at your last four throws to predict the next one.

Another alteration I'd consider is playing with the weights in the hamming distance calculation. Eg weigh each bit match by lambda^(-n), where lambda is a parameter you can adjust (start with something like 1.1), and n denotes the number of hours in the past that the bit represents.

Any of various classification algorithms, like SVM, logistic regression, random forests, etc. should also work quite well. Features to add to the feature vector:

  • day of week
  • hour
  • average occupancy this hour
  • average occupancy this day
  • average occupancy this (day, hour)
  • past occupancy N-grams (ie the bit vector of the previous N hours) for various values of N
  • is a holiday?
  • hours since sunrise

Finally, for a new user, it will probably take a while to get enough training data, so you might want to have two models: an overall model based on all your users and an individual user model. You can then weight the outputs of the two models, with the weight on the user model increasing

share|improve this answer
I agree with the hamming distance comment that it is fairly sensitive to the precise structure of the day. I slightly do not follow how the lambda^(-n) would improve that, basically what it does is decrease weight of the hours as they come during the day. The looking back 24 hours is a good idea I will have a look at that. Regarding the classifiers I have already used them in different applications but I am little bit unsure how to use them in time continuous environment. Would this mean to train them after each half an hour again? Pretty much it would, no? –  user1306283 May 10 '13 at 10:29
n is supposed to be the number of hours prior to the present. That way the two time periods matching at -10 hours is less significant than two time periods matching at -1 hours. For example if it's 11am, a difference at 10am is much more significant than a difference at 1am. I don't think you'd need a different model for each time of day. Just include each 1/2 hour as a binary feature in the feature vector (48 features in total). a Decision tree classifier will basically build a separate model for each half hour if it determines that's the best thing to do. –  RecursivelyIronic May 12 '13 at 19:30

You probably only want to save the N most recent days, and/or assign a greater weight to the more recent days. Otherwise the algorithm won't respond quickly enough to a change in the user's habits.

You might also get better results if you compare occupancy by intervals rather than by bit vectors - typically a house will be occupied/unoccupied for a large span of time, rather than e.g. alternating occupancy every half hour. This is especially true on weekdays, where the house will be unoccupied for eight (or nine, or ten) hours starting in the morning and lasting til evening; the occupancy interval in the morning will be a good predictor of the mid-day (un)occupancy interval, because if the occupant leaves for work early or late then they'll probably get home early or late. If they're still home at 10:00 or 11:00 then they're probably going to be home all day (due to being ill or on vacation). It's also easy to compare and index intervals compared to bit vectors - for example, you can store the days in an interval tree (or rather an interval tree converted into a treemap), with the interval as the key and the day(s) as the value, in order to quickly determine which days share the current day's morning occupancy interval.

You'll need two data structures: an array of interval trees (maps), one tree per day of the week, that uses the morning occupancy interval as the key and a collection of previous days as the value. This collection will need to aggregate the evening occupancy inteval(s); the predicted occupancy for any given half hour period is the mode of the previous days that have the same morning occupancy interval (so if you've stored 7 days and 5 of them predict occupancy at time X, then the data structure predicts occupancy at time X). You'll also need a queue of all previous days, so that you can remove the oldest days from the interval trees. (As an alternative, assign a greater weight to the more recent days; however, this is trickier to implement, since you'll need to also lower the older days' weights.)

You may find that you only need two interval trees, one for weekdays and one for weekends.

share|improve this answer

Your Answer

