[Gllug] Algorithm question for your Friday morning

[salsaman]

salsaman wrote:

> salsaman wrote:
>
>> Adrian McMenamin wrote:
>>
>>> Inspired by an article in the latest edition of Linux Journal (NB you
>>> really should subscribe - exchange rate makes it about 50% cheaper than
>>> buying in on the news stand) on top (1)
>>>
>>> I have some code that currently takes an arithmetic mean of people's
>>> preferences/votes. But it occurs to me that it would be better to 
>>> replace
>>> that with some sort of algorithm that weights historical votes less 
>>> than
>>> more recent votes.
>>>
>>> (I believe top(1) uses an exponential decay function)
>>>
>>> Is there a simple way to do this when the only record I currently 
>>> have of
>>> historic votes is the arithmetic mean?
>>>
>>>  
>>>
>> The algorithm is not difficult. Basically you currently calculate the 
>> mean value as:
>>
>> (a0+a1+a2+a3+a4+...an) / n = mean
>>
>> What you want to do is to weight current votes more than past votes.
>>
>> You can do this on a daily basis for example.
>>
>> From the equation above:
>>
>> mean * n = (a0+a1+a2+...an)
>>
>> Simply halving n will give today's votes twice as much effect as 
>> yesterday's votes, four times as much as the day before, etc.
>>
>> Of course, halving n might be too much, you could use some other 
>> factor, e.g.
>>
>> 1/sqrt(2) will give today's votes twice as much effect as those from 
>> 2 days ago and 4 times as much as from 4 days ago. Etc.
>>
>>
>> Gabriel.
>>
> Hmmm...maybe not so easy, because then the range is wrong.
>
>
> More thought is needed.
>
> Gabriel.
>



A better solution might be to allow today's votes to deviate more from 
the mean than previous votes.

E.g. the devience is (a-mean) with value (a-mean)+mean
where a is the vote value.

you could scale this, e.g.:

(a-mean)*2+mean

which would mean (no pun intended) today's votes can deviate the mean 
twice as much as past votes.

Of course eventually if you keep doing this, after a number of days, a 
single vote has more power than all of the past votes, so you might want 
to use a logarithmic method:

It will take several passes.

1) calculate mean normally

2) apply formula: vote=(a-mean)/days [where days is the number of days 
since vote was cast

3) recalculate mean using formula 2, then use new mean in formula 2.

Eventually you will arrive at a steady state where mean is the 
logarithmic mean of all the votes.

Gabriel.

-------------- next part --------------
-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug