Mahout Recommendation for MySQL Data (Network Trending)

[Tim Bass <ti...@gmail.com>]

We are thinking about installing Mahout on a Ubuntu server with a
MySQL database full of time series
data about network and server events.   We want to mine the data and
set up a statistical baseline for
for "normal" and "abnormal" patterns.

Is there an algorithm or method in Mahout ready to test in this type
of NMS environment?

Re: Mahout Recommendation for MySQL Data (Network Trending)

[Tim Bass <ti...@gmail.com>]

Dear Ted and Jeff,

My apologies for not following up on this earlier.  I've been busy on
a few other
projects, including some work in Amazon CloudFront/S3 and then, more
interestingly, work in virtual economics and virtual currency for an active
web community.

I just wanted to let you know have not fogotten about this discussion
and although I am current busy on web development projects, I do read
the mahout lists :-)

Again, my apologies for dropping the ball on my end.

Yours, Tim

On Thu, Apr 2, 2009 at 12:27 PM, Tim Bass  wrote:
> Hi Ted,
>
> I am on travel for a few days, starting in a few hours;  I'll respond
> in more detail
> when I am back.
>
> After reading your generous reply, it seems I need to outline the
> overall data and problem set,
> rough behavioral model, and other higher level abstractions to help
> insure the details
> fit the problem space.   I'll take a stab at this in my next post.
>
> More later....
>
> Yours sincerely, Tim
>
> On Thu, Apr 2, 2009 at 5:17 AM, Ted Dunning <te...@gmail.com> wrote:
>> On Wed, Apr 1, 2009 at 1:08 PM, Tim Bass <ti...@gmail.com> wrote:
>>
>>> I like the idea of clustering of mixture models and, think with a bit of
>>> effort, it would not be too difficult to create initial first order
>>> behavioral models.
>>> ...
>>> what might be the next steps?
>>>
>>
>> I think the first steps are:
>>
>> a) define and collect some sample data.  This should include real data and
>> some synthetic data for testing.
>>
>> b) define the form of behavioral models for clustering
>>
>> c) do an initial clustering
>>
>> d) diagnose what didn't work as planned
>>
>> You should say a bit about the data you have, but my guess is that you have
>> times, target host, general transaction type, source host and possibly user
>> name.  For a first step, I would use times, target host, transaction type
>> (or protocol or port) and source host.  I would obfuscate the source host by
>> picking a random salt and hashing the source IP or host name (and then
>> forget the key).  For synthetic data, I would generate several data files:
>>
>> 1) a mixture of 2,10 and 100 Poisson sources with rates selected over a
>> fairly wide range.  Each source should be identified by a single source host
>> and go to a single target host.
>>
>> 2) a mixture of 100 Poisson sources and 10 periodic sources with rates over
>> a wide range.
>>
>> 3) something more appropriate for the data that you have (and I don't know
>> about)
>>
>> The simplest behavioral models would simply be Poisson sources with a known
>> access rate.  That would not, however, handle periodic or nearly periodic
>> traffic.  My recommendation would be to start with a data source with times
>> distributed according to a gamma distribution for the real data.  Initially,
>> I would not look at source and target hosts in the models.
>>
>> The initial clustering should be run with differing amounts of the synthetic
>> data from (1) and Poisson models.  For small amounts of data, the clustering
>> should identify the high frequency components pretty easily.  With more
>> data, the lower frequency sources should become apparent.
>>
>> With data (1) and gamma models, the system should determine that the sources
>> are largely Poisson.
>>
>> With data (2) and Poisson models, it should be possible to show that the
>> periodic models are not well modeled, largely because the periodic data
>> won't be attached to a single model.  With data(2) and gamma models, the
>> Poisson sources should have appropriate shape parameters and the periodic
>> sources should have narrow range of predicted time between transactions.
>>
>> I don't know how much data will be required for this unlabeled source
>> separation task and it may turn out to be difficult to see the low rate
>> signals against the high rate background.  Choice of priors will be
>> important to avoid describing every data set as being singleton observations
>> from a large number of very low rate sources.  There may also be convergence
>> issues.  For example, if you have a Poisson source with rate 1 and a
>> periodic source with rate 0.1, the mixture of a Poisson and a very narrow
>> gamma distribution would fit the data very well, but it would be very hard
>> to notice by accident that every 10 or so events occur at a constant rate.
>> With labels, this will be much easier, of course.
>>
>> Depending on the results with synthetic data, it may be time to look at the
>> real data or we may need to move to more interesting models.
>>
>> The next interesting model that I would be curious about would be one which
>> combines rate and target host.  This would likely be done using a gamma for
>> rate and multinomial for target host.  1 or more sources should be shared by
>> individual source hosts to emulate proxying and multi-tasking so source host
>> would provide additional information.  This could be used to specify a
>> multi-level generative model where each source host is modeled by multiple
>> traffic sources and the number of traffic sources for each source host and
>> the individual rate and shape parameters would be the latent variables for
>> the model.
>>
>>
>>
>>
>>
>> --
>> Ted Dunning, CTO
>> DeepDyve
>>
>

Re: Mahout Recommendation for MySQL Data (Network Trending)

[Tim Bass <ti...@gmail.com>]

Hi Ted,

I am on travel for a few days, starting in a few hours;  I'll respond
in more detail
when I am back.

After reading your generous reply, it seems I need to outline the
overall data and problem set,
rough behavioral model, and other higher level abstractions to help
insure the details
fit the problem space.   I'll take a stab at this in my next post.

More later....

Yours sincerely, Tim

On Thu, Apr 2, 2009 at 5:17 AM, Ted Dunning <te...@gmail.com> wrote:
> On Wed, Apr 1, 2009 at 1:08 PM, Tim Bass <ti...@gmail.com> wrote:
>
>> I like the idea of clustering of mixture models and, think with a bit of
>> effort, it would not be too difficult to create initial first order
>> behavioral models.
>> ...
>> what might be the next steps?
>>
>
> I think the first steps are:
>
> a) define and collect some sample data.  This should include real data and
> some synthetic data for testing.
>
> b) define the form of behavioral models for clustering
>
> c) do an initial clustering
>
> d) diagnose what didn't work as planned
>
> You should say a bit about the data you have, but my guess is that you have
> times, target host, general transaction type, source host and possibly user
> name.  For a first step, I would use times, target host, transaction type
> (or protocol or port) and source host.  I would obfuscate the source host by
> picking a random salt and hashing the source IP or host name (and then
> forget the key).  For synthetic data, I would generate several data files:
>
> 1) a mixture of 2,10 and 100 Poisson sources with rates selected over a
> fairly wide range.  Each source should be identified by a single source host
> and go to a single target host.
>
> 2) a mixture of 100 Poisson sources and 10 periodic sources with rates over
> a wide range.
>
> 3) something more appropriate for the data that you have (and I don't know
> about)
>
> The simplest behavioral models would simply be Poisson sources with a known
> access rate.  That would not, however, handle periodic or nearly periodic
> traffic.  My recommendation would be to start with a data source with times
> distributed according to a gamma distribution for the real data.  Initially,
> I would not look at source and target hosts in the models.
>
> The initial clustering should be run with differing amounts of the synthetic
> data from (1) and Poisson models.  For small amounts of data, the clustering
> should identify the high frequency components pretty easily.  With more
> data, the lower frequency sources should become apparent.
>
> With data (1) and gamma models, the system should determine that the sources
> are largely Poisson.
>
> With data (2) and Poisson models, it should be possible to show that the
> periodic models are not well modeled, largely because the periodic data
> won't be attached to a single model.  With data(2) and gamma models, the
> Poisson sources should have appropriate shape parameters and the periodic
> sources should have narrow range of predicted time between transactions.
>
> I don't know how much data will be required for this unlabeled source
> separation task and it may turn out to be difficult to see the low rate
> signals against the high rate background.  Choice of priors will be
> important to avoid describing every data set as being singleton observations
> from a large number of very low rate sources.  There may also be convergence
> issues.  For example, if you have a Poisson source with rate 1 and a
> periodic source with rate 0.1, the mixture of a Poisson and a very narrow
> gamma distribution would fit the data very well, but it would be very hard
> to notice by accident that every 10 or so events occur at a constant rate.
> With labels, this will be much easier, of course.
>
> Depending on the results with synthetic data, it may be time to look at the
> real data or we may need to move to more interesting models.
>
> The next interesting model that I would be curious about would be one which
> combines rate and target host.  This would likely be done using a gamma for
> rate and multinomial for target host.  1 or more sources should be shared by
> individual source hosts to emulate proxying and multi-tasking so source host
> would provide additional information.  This could be used to specify a
> multi-level generative model where each source host is modeled by multiple
> traffic sources and the number of traffic sources for each source host and
> the individual rate and shape parameters would be the latent variables for
> the model.
>
>
>
>
>
> --
> Ted Dunning, CTO
> DeepDyve
>

Re: Mahout Recommendation for MySQL Data (Network Trending)

[Ted Dunning <te...@gmail.com>]

On Wed, Apr 1, 2009 at 1:08 PM, Tim Bass <ti...@gmail.com> wrote:

> I like the idea of clustering of mixture models and, think with a bit of
> effort, it would not be too difficult to create initial first order
> behavioral models.
> ...
> what might be the next steps?
>

I think the first steps are:

a) define and collect some sample data.  This should include real data and
some synthetic data for testing.

b) define the form of behavioral models for clustering

c) do an initial clustering

d) diagnose what didn't work as planned

You should say a bit about the data you have, but my guess is that you have
times, target host, general transaction type, source host and possibly user
name.  For a first step, I would use times, target host, transaction type
(or protocol or port) and source host.  I would obfuscate the source host by
picking a random salt and hashing the source IP or host name (and then
forget the key).  For synthetic data, I would generate several data files:

1) a mixture of 2,10 and 100 Poisson sources with rates selected over a
fairly wide range.  Each source should be identified by a single source host
and go to a single target host.

2) a mixture of 100 Poisson sources and 10 periodic sources with rates over
a wide range.

3) something more appropriate for the data that you have (and I don't know
about)

The simplest behavioral models would simply be Poisson sources with a known
access rate.  That would not, however, handle periodic or nearly periodic
traffic.  My recommendation would be to start with a data source with times
distributed according to a gamma distribution for the real data.  Initially,
I would not look at source and target hosts in the models.

The initial clustering should be run with differing amounts of the synthetic
data from (1) and Poisson models.  For small amounts of data, the clustering
should identify the high frequency components pretty easily.  With more
data, the lower frequency sources should become apparent.

With data (1) and gamma models, the system should determine that the sources
are largely Poisson.

With data (2) and Poisson models, it should be possible to show that the
periodic models are not well modeled, largely because the periodic data
won't be attached to a single model.  With data(2) and gamma models, the
Poisson sources should have appropriate shape parameters and the periodic
sources should have narrow range of predicted time between transactions.

I don't know how much data will be required for this unlabeled source
separation task and it may turn out to be difficult to see the low rate
signals against the high rate background.  Choice of priors will be
important to avoid describing every data set as being singleton observations
from a large number of very low rate sources.  There may also be convergence
issues.  For example, if you have a Poisson source with rate 1 and a
periodic source with rate 0.1, the mixture of a Poisson and a very narrow
gamma distribution would fit the data very well, but it would be very hard
to notice by accident that every 10 or so events occur at a constant rate.
With labels, this will be much easier, of course.

Depending on the results with synthetic data, it may be time to look at the
real data or we may need to move to more interesting models.

The next interesting model that I would be curious about would be one which
combines rate and target host.  This would likely be done using a gamma for
rate and multinomial for target host.  1 or more sources should be shared by
individual source hosts to emulate proxying and multi-tasking so source host
would provide additional information.  This could be used to specify a
multi-level generative model where each source host is modeled by multiple
traffic sources and the number of traffic sources for each source host and
the individual rate and shape parameters would be the latent variables for
the model.





-- 
Ted Dunning, CTO
DeepDyve

Re: Mahout Recommendation for MySQL Data (Network Trending)

[Tim Bass <ti...@gmail.com>]

This is exciting.  To clarify, experimentation is perfectly ok.   We
have a production web server where
we collect and store time series data (on nearly 350 metrics) in mysql
(on a different server) so we are not looking for
production code, but an experimental, collaborative, open effort.

I like the idea of clustering of mixture models and, think with a bit
of effort, it would
not be too difficult to create initial first order behavioral models.
 The good news is that we use zabbix, with is open
source collection into mysql, to collect the data, and zabbix has good
time-series charting features so it is easy
to visualize the data, see anomalies, etc.

Thanks so much for the interest.    We run the mysql database with all
the data on ubuntu linux, so
what might be the next steps?

Yours faithfully, Tim



On Wed, Apr 1, 2009 at 11:29 PM, Jeff Eastman
<jd...@windwardsolutions.com> wrote:
> Actually, the Dirichlet implementation in 0.1 *is* a parallel Hadoop version
> but it has a packaging issue that needs to be resolved to run it there. See
> my earlier thread about Dirichlet Example Class Not Found Exception. Your
> application is exactly the kind of problem that I was investigating when Ted
> suggested the Dirichlet approach. I would be very interested in seeing if we
> could apply it to your problem.
>
> Jeff
>
> Ted Dunning wrote:
>>
>> The short answer is no.
>>
>> The slightly longer answer is a highly qualified yes.
>>
>> There is an algorithm very recently in Mahout that does non-parametric
>> clustering of mixture models.  If you can define a reasonable form of
>> models
>> for your time series, then this algorithm would plausibly give you a set
>> of
>> models that would reasonably describe your original data.  Some of the
>> models in this mixture would represent various classes of normal events,
>> some would represent abnormal events in your training data (if there are
>> any).  There would also be a set of probability scores for each time
>> series
>> that tells you how well the mixture model describes that particular time
>> series.  Anomaly detection could be done by finding new events that are
>> poorly described by the mixture model defined by the training data.
>>
>> That said, the software is NOT production code.  Getting it to work on new
>> kinds of data with new kinds of models and learning to interpret the
>> output
>> is somewhat of a research project.  The code itself is relatively new and
>> you would be one of the first users.  Don't expect to go into production
>> next week.  Or next month.  The current code is also sequential in nature
>> rather than a parallel implementation.  A parallel implementation is being
>> worked on and Mahout contributors and committers (including me!) would be
>> happy to help you accelerate that development.
>>
>> The counter-caveat is that this could give you a state of the art anomaly
>> detector with contributions from you.
>>
>> On Wed, Apr 1, 2009 at 12:02 AM, Tim Bass <ti...@gmail.com> wrote:
>>
>>
>>>
>>> ... full of time series data about network and server events...   mine
>>> the
>>> data ..
>>> for "normal" and "abnormal" patterns.
>>>
>>> Is there an algorithm or method in Mahout ready to test in this type
>>> of NMS environment?
>>>
>>>
>>
>>
>>
>>
>
>

Re: Mahout Recommendation for MySQL Data (Network Trending)

[Jeff Eastman <jd...@windwardsolutions.com>]

Actually, the Dirichlet implementation in 0.1 *is* a parallel Hadoop 
version but it has a packaging issue that needs to be resolved to run it 
there. See my earlier thread about Dirichlet Example Class Not Found 
Exception. Your application is exactly the kind of problem that I was 
investigating when Ted suggested the Dirichlet approach. I would be very 
interested in seeing if we could apply it to your problem.

Jeff

Ted Dunning wrote:
> The short answer is no.
>
> The slightly longer answer is a highly qualified yes.
>
> There is an algorithm very recently in Mahout that does non-parametric
> clustering of mixture models.  If you can define a reasonable form of models
> for your time series, then this algorithm would plausibly give you a set of
> models that would reasonably describe your original data.  Some of the
> models in this mixture would represent various classes of normal events,
> some would represent abnormal events in your training data (if there are
> any).  There would also be a set of probability scores for each time series
> that tells you how well the mixture model describes that particular time
> series.  Anomaly detection could be done by finding new events that are
> poorly described by the mixture model defined by the training data.
>
> That said, the software is NOT production code.  Getting it to work on new
> kinds of data with new kinds of models and learning to interpret the output
> is somewhat of a research project.  The code itself is relatively new and
> you would be one of the first users.  Don't expect to go into production
> next week.  Or next month.  The current code is also sequential in nature
> rather than a parallel implementation.  A parallel implementation is being
> worked on and Mahout contributors and committers (including me!) would be
> happy to help you accelerate that development.
>
> The counter-caveat is that this could give you a state of the art anomaly
> detector with contributions from you.
>
> On Wed, Apr 1, 2009 at 12:02 AM, Tim Bass <ti...@gmail.com> wrote:
>
>   
>> ... full of time series data about network and server events...   mine the
>> data ..
>> for "normal" and "abnormal" patterns.
>>
>> Is there an algorithm or method in Mahout ready to test in this type
>> of NMS environment?
>>
>>     
>
>
>
>   

Re: Mahout Recommendation for MySQL Data (Network Trending)

[Ted Dunning <te...@gmail.com>]

The short answer is no.

The slightly longer answer is a highly qualified yes.

There is an algorithm very recently in Mahout that does non-parametric
clustering of mixture models.  If you can define a reasonable form of models
for your time series, then this algorithm would plausibly give you a set of
models that would reasonably describe your original data.  Some of the
models in this mixture would represent various classes of normal events,
some would represent abnormal events in your training data (if there are
any).  There would also be a set of probability scores for each time series
that tells you how well the mixture model describes that particular time
series.  Anomaly detection could be done by finding new events that are
poorly described by the mixture model defined by the training data.

That said, the software is NOT production code.  Getting it to work on new
kinds of data with new kinds of models and learning to interpret the output
is somewhat of a research project.  The code itself is relatively new and
you would be one of the first users.  Don't expect to go into production
next week.  Or next month.  The current code is also sequential in nature
rather than a parallel implementation.  A parallel implementation is being
worked on and Mahout contributors and committers (including me!) would be
happy to help you accelerate that development.

The counter-caveat is that this could give you a state of the art anomaly
detector with contributions from you.

On Wed, Apr 1, 2009 at 12:02 AM, Tim Bass <ti...@gmail.com> wrote:

> ... full of time series data about network and server events...   mine the
> data ..
> for "normal" and "abnormal" patterns.
>
> Is there an algorithm or method in Mahout ready to test in this type
> of NMS environment?
>



-- 
Ted Dunning, CTO
DeepDyve