Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I am trying to detect automated visits to a website. A typical data set for an automated client is of the form:

userid: visit_time1, visit_time2, ...
94562:  5, 10, 15, 25, 30
                  ^
                missed 

So the period of visit times is 5.

Occasionally (as I marked above), the automated client will miss a period but the next visit time will still be some integer multiple of the period.

Please note that the data is somewhat noisy as well. So a more realistic data set would look like:

userid: visit_time1, visit_time2, ...
94562:  5, 11, 14, 25, 30
                  ^
                missed 

Whereas a non-automated client would have a data set that looks more like:

13345: 5, 21, 34, 89

with no clear pattern.

I tried making a vector with 1's at the visit time indexes and 0's everywhere else. I then did autocorrelation and it worked quite well for subjectively determining whether a client is visiting at a regular interval. This was based on this question from the DSP stackexchange

However, I still don't know how to programmatically detect this behavior.

I also thought of testing the variance of the intervals between visits, but some intervals are multiples of the base period and this skews the mean.

share|improve this question
    
Your last sentence seems a reasonable approach, as long as the "occasional misses" are not too many. Are they? –  Alecos Papadopoulos Aug 27 at 17:37
    
Unfortunately yes. There is also the problem of thresholding the variance (or std dev). If the "period" is 5 and there is one miss, then the variance will be much larger than if the period is 60 and there is one miss. How could I deal with that? –  Bryan Glazer Aug 27 at 18:23
    
Oops, mistake above. The variance will be smaller for smaller periods. –  Bryan Glazer Aug 27 at 18:32
    
Another idea is to apply Data Clustering on the observed lengths (per visitor). The series from the automated visitors should exhibit a much more clear clustering, and with fewer clusters. I think there are metrics that measure this, but I am new to data clustering... Essentially, you are looking for "degree of similarity of the lengths inside each series" -that's how the idea came to me. –  Alecos Papadopoulos Aug 27 at 19:20
1  
@Glen_b woah. I actually just made that one up myself. Yet another point for human's inability to generate random numbers... –  Bryan Glazer Aug 28 at 14:39

2 Answers 2

In a comment, I proposed Data Clustering, but it appears to be an overkill, since we have uni-dimesnional data. Consider the following algorithm.

1) Take a series and calculate the lengths between visits

2) Obtain all unique values in the differenced series, as well as their frequencies

3) Single out the value in the differenced series with the highest frequency.

(check: is this value also the minimum length value? For an automated visitor, it should be, since it will be the "base period")

4) Divide all other values with this maximum-frequency value

5) Criterion: are all results of the previous divisions integers? If yes, you have an automated visitor.

The probability that a non-automated visitor will satisfy the criterion in 5) is next to zero. And I think the above is easy to program.

ADDENDUM

New information from the OP revealed that the observed lengths between visits are noisy. So here is a model, full of needed assumptions in order to provide a tangible result. The estimation method used is Method of Moments.

Let $\ell_i$ be the length between visits at time $t_i$ and $t_{i-1}$. Let $\tilde \ell$ be the "base-length" followed by a visitor (not necessarily an automaton), without the noise. Let $u_i$ be the noise contaminating the exact time of the visit.
Assumption 1: $u_i$ is an i.i.d. white noise (zero mean, constant variance, no autocorrelation). I understand that the contamination comes also in integer values, so we assume that $u_i$ follows a discrete distribution taking integer values, and it is symmetric around zero.

Finally, let $m_i=1,2,3,...$ be the parameter indicating whether the current length between visits is a multiple of the base period, and if it is ($m_i>1$), how many multiples is it. Assumption 2: $m_i$ follows a geometric distribution of the first variant, with parameter $0 \leq p \leq 1$.

Assumption 3: $u_i$ and $m_i$ are independent, across indices also.

Given all the above, the value of $\ell_i$ can be written as

$$\ell_i= m_i\tilde \ell +u_i $$ and it is a strictly stationary process. Note that this is a valid representation of lengths between visits from both automated and non-automated visitors.

We also have

$$E(\ell_i)= \frac 1{p}\tilde \ell, \;\;\;\; \text{Var}(\ell_i) = \frac {1-p}{p^2}\tilde \ell^2 + \sigma^2_u$$

But of greater interest is the 3d central moment of $\ell_i$, and this is due to the assumptions of a) symmetry of the distribution of $u_i$ around zero, and 2) Independence of $m_i$ and $u_i$. A little careful algebra gives

$$E(\ell_i - E(\ell_i))^3 = \tilde \ell^3E[m_i-E(m_i)]^3 = \tilde \ell^3\left(\frac{1-p}{p^2}\right)^{3/2}\cdot \frac {2-p}{\sqrt {1-p}}$$

where for quick derivation we have used the relation between the 3d central moment and the skewness coefficient (related to the $m_i$ r.v.). This magnitude is of interest because it does not contain the variance of $u_i$ (and it neither contains its 3d raw moment because given our symmetry around zero assumption, it is zero). Simplifying we get

$$E[\ell_i - E(\ell_i)]^3 = \tilde \ell^3\frac{(1-p)(2-p)}{p^3}$$

From the expression for the mean of $\ell_i$ we have $\tilde \ell = pE(\ell_i)$. Substituting into the 3d central moment, re-arranging, simplifying and decomposing, we get

$$\frac {E[\ell_i - E(\ell_i)]^3}{\Big [E(\ell_i)\Big]^3} = (1-p)(2-p)$$

$$\Rightarrow p^2 - 3p + \left(2-\frac {E[\ell_i - E(\ell_i)]^3}{\Big [E(\ell_i)\Big]^3}\right) = 0 $$

The ratio of expected values can be calculated from the sample, call this estimate simply $\hat q$. Then only one of the roots of the polynomial is meaningfull,

$$\hat p = \frac {3 - \sqrt {1+4\hat q}}{2}$$

which in turn will give us an estimate of $\tilde \ell$, and then, through the sample variance, an estimate also of $\sigma^2_u$.

What have we learned?

Well, consider what is the interpretation of $p$: it is the probability that $m_i$ will take the value $1$, and so in a long series, $1-p$ is the proportion of times the visitor will have missed one or more visit.
It seems to me that the lower $p$ is (the higher $1-p$ is -the more times the visitor misses a visit or more in a row), the less probable it appears that it is an automaton.

Also, the value of $\sigma^2_u$ should be expected to be lower for an automated visitor (assuming that it is less moody and idiosyncratic than a human being).

As a composite measure, the coefficient of variation standardizes the variability with respect to the mean value

$$\text{CV}(\ell_i) = \frac {\sqrt {\text{Var}(\ell_i)}}{E(\ell_i)} = \sqrt {(1-p)+\left(p/\tilde \ell\right)^2\sigma^2_u}$$

and we expect low values for it, for automated visitors.

Of course, since the above will be applied to all series individually, and this estimates will be obtained for all visitors, automated or not, it remains to determine a classification criterion. I 'll leave this task for the OP, if, that is, he decides to implement this method (for example, if there exists some series for which we know with certainty that they come from automated visitors, then we can work with them to obtain benchmark values for the thresholds related to the parameters).

A final note: if one wants to assume a specific distribution for $u_i$, one could also apply maximum likelihood, by obtaining the probability mass function of $\ell_i$, through convolution for discrete random variables.

share|improve this answer
    
I really should have mentioned this above. The data is actually somewhat noisy. So instead of [5, 10, 15] the reality is more like [6, 11, 14] –  Bryan Glazer Aug 27 at 20:24
    
Ah, what a disappointment...! But this makes the lengths a random variable, which opens up interesting avenues... –  Alecos Papadopoulos Aug 27 at 20:27
1  
Glad to hear that you decided to implement my approach (let's also hope that it will produce something meaningful...) It would be good to hear back from you (with positive or negative news). The $3$ in the expression is bona-fide exponentiation in the 3d power -after all this is what "3d moment" actually means - the expected value of a random variable (or of a function of random variables) raised in the 3d power. –  Alecos Papadopoulos Sep 2 at 15:45
    
Sorry for the long delay Alecos. Thanks for the answer. This did not work for me with a sample data-set. A few things: I think that $$\sqrt{1+4\hat q}$$ should be $$\sqrt{9-4\hat q}.$$Secondly, I tried the method with this dataset (60, 60, 60, 60, 61, 63, 62, 60, 60*12) and I got -6839.908 as the value of $$\hat p$$ –  Bryan Glazer Nov 4 at 0:53
    
I don't know how to interpret this. I implemented another method called the Rayleigh Statistic and it works well. I will provide an answer explaining the Rayleigh stat –  Bryan Glazer Nov 4 at 0:56

You could break down the sequence into several time windows. If you can assume the visits within each window are Poisson Random Process and that the process is homogeneous across the windows (this is largely based on how you feel it SHOULD behave, but it seems reasonable to me over a short duration), you can then determine if your visits per window significantly deviate from that assumed Poisson process. If so, you may have autobot.

To test for deviation from Poisson distribution, this question and answer may help: How can I test if given samples are taken from a Poisson distribution?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.