# This exercise is mostly for us to understand what kind of data we have and then
# run some simple stats on the fields/values in the data. Pandas will be great for that
import pandas as pd
pd.__version__

# Set default figure sizes
pylab.rcParams['figure.figsize'] = (16.0, 5.0)

# Lets take a peek at our system.log, with IPython you
# can execute system commands with '!' (also see %alias)

!head /var/log/system.log

# Okay so weird timestamp, machine name and then random stuff...
import dateutil.parser

# Helper function to make compact, composite labels for the syslog rows
def make_label(features):
    return unicode(':'.join([f[:6] for f in features]), 'utf-8').encode('ascii','ignore')

# Now process the syslog file, part of the challenge is parsing the darn thing.
# Typically each row in a syslog will have a timestamp first and then some random
# set of other fields split on whitespace. We're going to carefully pull out the
# timestamp but then just treat everything else as bag of tokens (sparse data).
date_index = []
with open('/var/log/system.log') as syslog:
    syslog_rows = syslog.readlines()
    syslog_events = []
    for row in syslog_rows:
        split_list = row.split()
        date_string = ' '.join(split_list[:3])
        try:
            date = dateutil.parser.parse(date_string)
        except (ValueError, TypeError) as e:
            continue # Going to skip rows where we can't get a timestamp
        features = split_list[4:]
        syslog_events.append({'features': features, 'label': make_label(features), 'type': features[0].split('[')[0]})
        date_index.append(date)
    dataframe = pd.DataFrame(syslog_events, index=date_index)

# Make sure our timestamp got pulled/parsed/converted correctly
type(dataframe.index[0])

dataframe.head(5)

# So what do we have? Datetime is our index, features is just the 
# syslog row split by whitespace and placed into a list. The label
# is just the features (truncated) and flattened with : separators.
# 'type' is just the syslog identifier right after the datetime and machine.
# Note: The parsing of the syslog is more art than science and syslogs
#       can vary greatly, but we haven't done any super magic here,
#       just basically thrown the row data into some bins...

dataframe.tail(5)

# We can get a count of all the unique values by running value_counts()
dataframe['label'].value_counts()

# Okay the breakout below gives us a sense for our challenge...

# Realize that we don't want the 'last message' events
dataframe = dataframe[dataframe['type'] != 'last']

"""
Explanation: Having Fun with Syslog.
<img align="right" src="http://www.sharielf.com/gifs/zz032411pony.jpg" width="180px">
In the next exercise we're going look at some syslog data. We'll take it up a notch by computing similarities with 'Banded MinHash' and running a hierarchical clustering algorithm.
Systems logs are particularly challenging because they often lack any kind of structure as all. For this exercise we're going to be looking at the /var/log/system.log of a typical Mac OSX Laptop. The first steps will be standard data inspection and plots, after that we'll pull out the big guns!
<br><br><br>
<br><br><br>
<figcaption>Image courtesy of Shari Elf: www.sharielf.com</figcaption>
End of explanation
"""


# Now prepare the data for plotting by pivoting on the 
# feature to create a new column (series) for each value

# Only pull out the top 7 syslog event types
topN = dataframe['type'].value_counts()[:7].index
subset = dataframe[dataframe['type'].isin(topN)]
print 'Subset: %d rows %d columns' % subset.shape

# We're going to add a new column called value (needed for pivot). This
# is a bit dorky, but needed as the new columns that get created should
# really have a value in them, also we can use this as our value to sum over.
subset['count'] = 1
pivot = pd.pivot_table(subset, values='count', rows=subset.index, cols=['type'], fill_value=.01)
by = lambda x: lambda y: getattr(y, x)
grouped = pivot.groupby([by('hour')]).sum()
grouped.plot(kind='bar', stacked=True)
grouped.plot()

"""
Explanation: Lets do standard histogram and event volume over time plots
End of explanation
"""


# Even for small syslogs the number of similarity pairs to compute quickly
# becomes quite large O(N**2), so for 100k rows that's 10 billion possible
# pairs. Using Banded MinHash will drastically reduce the number of 
# candidates that we have to compute.
import data_hacking.lsh_sims as lsh_sims

# Note: The parameters here are setup for feeding the results into a Hierarchical
#       Clustering algorithm, which needs as many similarities as you can get.
#       In general you'd parameters like num_hashes:20, lsh_bands:5 lsh_rows:4  
#       Note: lsh_bands*lsh_rows ^must^ equal num_hashes
params = {'num_hashes':20, 'lsh_bands':20, 'lsh_rows':1, 'drop_duplicates':True}
lsh = lsh_sims.LSHSimilarities(dataframe['features'], mh_params=params)
sims = lsh.batch_compute_similarities(distance_metric='jaccard', threshold=.2)

"""
Explanation: <img align="right" src="files/images/spice_weasel.jpg" width="300px" style="margin: 10px">
Well besides learning we have lots of kernel syslog messages, kinda boring...<br><br>So, lets take is up a notch with the good 'ol spice weasel! Bam!

Compute similarities between all rows within the system log using LSH
    Unlike conventional hash functions the goal of LSH (Locality Sensitive Hashing) is to maximize probability of "collision" of similar items rather than avoid collisions.
MinHash
Locality Sensitive Hashing
Mining of Massive Datasets



Use those similarities as the basis of a Hierarchical Clustering Algorithm
    Single-linkage clustering is one of several methods for agglomerative 
    hierarchical clustering.

Single Linkage Clustering
Hierarchical Clustering

Other popular online clustering algorithms
- DBSCAN
- OPTICS Algorithms
End of explanation
"""


# Lets look at the difference between Jaccard Similarity and Levenshtein Similarity
# So here similarity is a normalized measure of inverse distance...
print 'Jaccard Index (Sim): %f ' % lsh.jaccard_sim(['a','b','c','d'], ['a','b','d','c'])
print 'Levenshtein Distance: %f ' % lsh.levenshtein(['a','b','c','d'], ['a','b','d','c'])
print 'Levenshtein (Sim): %f ' % lsh.l_sim(['a','b','c','d'], ['a','b','d','c'])

# One more example for intuition (also note they don't have to be the same size)
print 'Jaccard Index (Sim): %f ' % lsh.jaccard_sim(['a','b','c'], ['a','b','c','x'])
print 'Levenshtein Distance: %f ' % lsh.levenshtein(['a','b','c'], ['a','b','c','x'])
print 'Levenshtein (Sim): %f ' % lsh.l_sim(['a','b','c'], ['a','b','c','x'])

# Okay now that we have the similarities between all the rows in our syslog
# we can start to investigate the results.
sims.sort(reverse=True)
print '*** Top sims ***'
sims[:10]
#sims[-10:]

print dataframe.iloc[376]['features']

print dataframe.iloc[1090]['features']

# The two feature sets should look quite similar (recall that this
# is just our syslog row split on white space and thrown into a list)

# So now for any row in our syslog we can see what rows are highly
# similar to that row.
query_item = ['Google', 'Chrome', 'Helper[11545]:', 'Process', 'unable', 'to', 'create', 'connection', 'because', 'the', 'sandbox', 'denied', 'the', 'right', 'to', 'lookup', 'com.apple.coreservices.launchservicesd', 'and', 'so', 'this', 'process', 'cannot', 'talk', 'to', 'launchservicesd.', ':', 'LSXPCClient.cp', '#426', '___ZN26LSClientToServerConnection21setupServerConnectionEiPK14__CFDictionary_block_invoke()', 'q=com.apple.main-thread']
lsh.top_N(query_item,dataframe['label'], 5)


# Note the query object doesn't have all the original features
query_item = ['Google', 'Chrome', 'Process', 'unable', 'to', 'sandbox']
lsh.top_N(query_item,dataframe['label'], 5)

"""
Explanation: The LSH Sims python class has two distance metrics
1) Jaccard Index: a set based distance metric (overlaps in sets of elements)

Jaccard Index

2) Levenshtein Distance: based on the edit distance of the elements (so order matters).

Levenshtein Distance
End of explanation
"""


# A simple example for illustration
import data_hacking.hcluster as hcluster

toy_data = [['a','b','c','d'],['a','b','d'],['a','b','e','d'],['a','b','f'],
            ['w','x','y','z'],['x','y','z'],['w','x','q','z','y'],
            ['r','s','t'],['u','s','t']]

toy_lsh = lsh_sims.LSHSimilarities(toy_data, mh_params=params)
toy_sims = toy_lsh.batch_compute_similarities(distance_metric='jaccard', threshold=.2)
    
# Compute a hierarchical clustering from the similarity list
toy_h_clustering = hcluster.HCluster(toy_data)
toy_h_clustering.set_sim_method(toy_lsh.jaccard_sim)
toy_h_tree, toy_root = toy_h_clustering.sims_to_hcluster(toy_sims)

# Plot the hierarchical tree
toy_h_clustering.plot_htree(toy_h_tree, prog='dot')


# Now we'll do the same thing for our syslog data

# Compute a hierarchical clustering from the similarity list
h_clustering = hcluster.HCluster(dataframe['features'])
h_clustering.set_sim_method(lsh.jaccard_sim)
h_tree, root = h_clustering.sims_to_hcluster(sims, agg_sim=.3)

# Here's an image for those folks not looking at it interactively

"""
Explanation: <div style="float: right; margin: 20px 20px 20px 20px"><img src="files/images/agg.jpg" style="margin: 10px"></div>
Hierarchical Clustering
Now we can use those similarities as the basis of a Hierarchical Clustering Algorithm. Single-linkage clustering is one of several methods for agglomerative hierarchical clustering. The image on the right is an example of how this works. 
We're using a bottom up method (image is flipped :), you simply sort the similarities and start building your tree from the bottom. If B and C are the most similar you link them, then D/E and so on until you complete the tree. The devil is definitely in the details on the implementation of this, so luckily we have a python class that does it for us.
End of explanation
"""


# Even better save the graph out to json format and visualize it with D3 (D3js.org)
import networkx.readwrite.json_graph
import json
graph_json = networkx.readwrite.json_graph.tree_data(h_tree, root=root)
json.dump(graph_json, open('h_tree.json','w'))

"""
Explanation: <img src="files/images/h_cluster.png">
End of explanation
"""


