From: Alex Gutteridge <alexg@...>
Date: 2012-09-03T18:57:38+09:00
Subject: Re: Looking for patterns in a collection

On 02.09.2012 23:52, Rainer Thiel wrote:
> Greetings, i have the following (fragment olny) :
>
> devices = [{d1 => [0,1,0,1,0,0,...]},
>            {d2 => [0,0,1,1,0,1,...]},
>            {d3 => [1,0,1,1,0,1,...]},
>            ...]
>
> Each hash represents device, the array of zeroes and ones 
> representing
> the presence or absence of a specific software executable on that
> device. (array index signifies a unique identifier to the executable)
>
> Scenario:
> A list of desktop computers (~600) that includes all software
> executables deployed on each machine. There more than 1,000 distinct
> executables deployed across these devices.
>
> I am trying to identify common patterns of software deployments, 
> looking
> for an algoritm that will arrange the current state into a limited,
> manageable set of discrete application profiles.
>
> No two devices are exactly alike, even after filtering out all the
> 'noise'  - different versions, common operating system and driver 
> files
> etc. So the comparison must proceed with some element of configurable
> tolerance.
>
> I have had a look at the Vector and Matrix classes but haven't found 
> any
> suitable built in method that would allow me to submit a suitably
> prepared list(an array of arrays?, an array of vectors?, a matrix?)
> which is then rationalised into a few recognisably discrete groups.
>
> Are there any libraries out ther i could leverage? I am not a maths /
> statistics guy?
>
> Regards, Rainer

A common distance metric for sets is the Jacquard distance 
(http://en.wikipedia.org/wiki/Jaccard_index). In your case each 
collection of executables is a set. Implementing it in Ruby is quite 
easy using the built in Array union and intersection operators:

a = [1,0,0,1,0,1]
b = [1,0,1,1,0,1]
c = [0,1,0,0,1,0]

a_idx = []
a.each_with_index{|x,i| x == 1 ? a_idx << i : nil}
b_idx = []
b.each_with_index{|x,i| x == 1 ? b_idx << i : nil}
c_idx = []
c.each_with_index{|x,i| x == 1 ? c_idx << i : nil}

#Distance from a to b is 0.25
((a_idx | b_idx).size.to_f - (a_idx & b_idx).size) / (a_idx | 
b_idx).size
#Distance from a to c is 1
((a_idx | c_idx).size.to_f - (a_idx & c_idx).size) / (a_idx | 
c_idx).size

Once you have calculated the distance between all machines in this way 
you can cluster them however you like. See 
(http://colinfdrake.com/2011/05/28/clustering-in-ruby.html) for an 
example of k-means clustering in Ruby. Another possibility is to 
generate a graph representation of your data and visualise with 
something like GraphViz (https://github.com/glejeune/Ruby-Graphviz/).

-- 
Alex Gutteridge