![](\"http://www.sharielf.com/gifs/zz032411pony.jpg\")
\n",
"\n",
"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.\n",
"\n",
"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!\n",
"\n",
"![](\"files/images/spice_weasel.jpg\")
\n",
"\n",
"#### Well besides learning we have lots of kernel syslog messages, kinda boring...So, lets take is up a notch with the good 'ol spice weasel! Bam!\n", "1. **Compute similarities between all rows within the system log using LSH**\n", " Unlike conventional hash functions the goal of LSH (Locality Sensitive Hashing) is to maximize probability of \"collision\" of similar items rather than avoid collisions.\n", " * [MinHash](http://en.wikipedia.org/wiki/MinHash)\n", " * [Locality Sensitive Hashing](http://en.wikipedia.org/wiki/Locality_sensitive_hashing)\n", " * [Mining of Massive Datasets](http://infolab.stanford.edu/~ullman/mmds/ch3.pdf)\n", "2. **Use those similarities as the basis of a Hierarchical Clustering Algorithm**\n", " Single-linkage clustering is one of several methods for agglomerative \n", " hierarchical clustering.\n", " - [Single Linkage Clustering](http://en.wikipedia.org/wiki/Single-linkage_clustering)\n", " - [Hierarchical Clustering](http://en.wikipedia.org/wiki/Hierarchical_clustering)\n", " \n", " Other popular online clustering algorithms\n", " - [DBSCAN](http://en.wikipedia.org/wiki/DBSCAN)\n", " - [OPTICS Algorithms](http://en.wikipedia.org/wiki/OPTICS_algorithm)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "12694 (0.64% out of 1979649) pairs returned from MinHash\n" ] } ], "source": [ "# Even for small syslogs the number of similarity pairs to compute quickly\n", "# becomes quite large O(N**2), so for 100k rows that's 10 billion possible\n", "# pairs. Using Banded MinHash will drastically reduce the number of \n", "# candidates that we have to compute.\n", "import data_hacking.lsh_sims as lsh_sims\n", "\n", "# Note: The parameters here are setup for feeding the results into a Hierarchical\n", "# Clustering algorithm, which needs as many similarities as you can get.\n", "# In general you'd parameters like num_hashes:20, lsh_bands:5 lsh_rows:4 \n", "# Note: lsh_bands*lsh_rows ^must^ equal num_hashes\n", "params = {'num_hashes':20, 'lsh_bands':20, 'lsh_rows':1, 'drop_duplicates':True}\n", "lsh = lsh_sims.LSHSimilarities(dataframe['features'], mh_params=params)\n", "sims = lsh.batch_compute_similarities(distance_metric='jaccard', threshold=.2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### The LSH Sims python class has two distance metrics\n", "\n", "1) Jaccard Index: a set based distance metric (overlaps in sets of elements)\n", " \n", " - [Jaccard Index](http://en.wikipedia.org/wiki/Jaccard_index)\n", "\n", "2) Levenshtein Distance: based on the edit distance of the elements (so order matters).\n", " \n", " - [Levenshtein Distance](http://en.wikipedia.org/wiki/Levenshtein_distance)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Jaccard Index (Sim): 1.000000 \n", "Levenshtein Distance: 2.000000 \n", "Levenshtein (Sim): 0.500000 \n" ] } ], "source": [ "# Lets look at the difference between Jaccard Similarity and Levenshtein Similarity\n", "# So here similarity is a normalized measure of inverse distance...\n", "print 'Jaccard Index (Sim): %f ' % lsh.jaccard_sim(['a','b','c','d'], ['a','b','d','c'])\n", "print 'Levenshtein Distance: %f ' % lsh.levenshtein(['a','b','c','d'], ['a','b','d','c'])\n", "print 'Levenshtein (Sim): %f ' % lsh.l_sim(['a','b','c','d'], ['a','b','d','c'])" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Jaccard Index (Sim): 0.750000 \n", "Levenshtein Distance: 1.000000 \n", "Levenshtein (Sim): 0.750000 \n" ] } ], "source": [ "# One more example for intuition (also note they don't have to be the same size)\n", "print 'Jaccard Index (Sim): %f ' % lsh.jaccard_sim(['a','b','c'], ['a','b','c','x'])\n", "print 'Levenshtein Distance: %f ' % lsh.levenshtein(['a','b','c'], ['a','b','c','x'])\n", "print 'Levenshtein (Sim): %f ' % lsh.l_sim(['a','b','c'], ['a','b','c','x'])" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "*** Top sims ***\n" ] }, { "data": { "text/plain": [ "[(1.0, 277, 1186),\n", " (0.9705882352941176, 376, 1090),\n", " (0.9666666666666667, 375, 1089),\n", " (0.9629629629629629, 1382, 1400),\n", " (0.9629629629629629, 1355, 1400),\n", " (0.9629629629629629, 1355, 1382),\n", " (0.9629629629629629, 1343, 1400),\n", " (0.9629629629629629, 1343, 1382),\n", " (0.9629629629629629, 1343, 1355),\n", " (0.9629629629629629, 1334, 1400)]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Okay now that we have the similarities between all the rows in our syslog\n", "# we can start to investigate the results.\n", "sims.sort(reverse=True)\n", "print '*** Top sims ***'\n", "sims[:10]\n", "#sims[-10:]" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['System', 'Events[8642]:', '.sdef', 'warning', 'for', 'type', \"'text\", '|', 'missing', 'value', '|', \"any'\", 'attribute', \"'uniqueID'\", 'of', 'class', \"'XML\", \"element'\", 'in', 'suite', \"'XML\", \"Suite':\", 'AppleScript', 'ID', 'references', 'may', 'not', 'work', 'for', 'this', 'property', 'because', 'its', 'type', 'is', 'not', 'NSNumber-', 'or', 'NSString-derived.']\n" ] } ], "source": [ "print dataframe.iloc[376]['features']" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['System', 'Events[9028]:', '.sdef', 'warning', 'for', 'type', \"'text\", '|', 'missing', 'value', '|', \"any'\", 'attribute', \"'uniqueID'\", 'of', 'class', \"'XML\", \"element'\", 'in', 'suite', \"'XML\", \"Suite':\", 'AppleScript', 'ID', 'references', 'may', 'not', 'work', 'for', 'this', 'property', 'because', 'its', 'type', 'is', 'not', 'NSNumber-', 'or', 'NSString-derived.']\n" ] } ], "source": [ "print dataframe.iloc[1090]['features']" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch:::LSXPCC:#426:___ZN2:q=com.',\n", " 'sim': 0.9629629629629629},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch:::LSXPCC:#426:___ZN2:q=com.',\n", " 'sim': 0.9629629629629629},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch:::LSXPCC:#426:___ZN2:q=com.',\n", " 'sim': 0.9629629629629629},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch:::LSXPCC:#426:___ZN2:q=com.',\n", " 'sim': 0.9629629629629629},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch:::LSXPCC:#426:___ZN2:q=com.',\n", " 'sim': 0.9629629629629629}]" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The two feature sets should look quite similar (recall that this\n", "# is just our syslog row split on white space and thrown into a list)\n", "\n", "# So now for any row in our syslog we can see what rows are highly\n", "# similar to that row.\n", "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']\n", "lsh.top_N(query_item,dataframe['label'], 5)\n" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch',\n", " 'sim': 0.2727272727272727},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch',\n", " 'sim': 0.2727272727272727},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch',\n", " 'sim': 0.2727272727272727},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch',\n", " 'sim': 0.2727272727272727},\n", " {'label': 'Google:Chrome:Helper:Proces:unable:to:create:connec:becaus:the:sandbo:denied:the:right:to:lookup:com.ap:and:so:this:proces:cannot:talk:to:launch',\n", " 'sim': 0.2727272727272727}]" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Note the query object doesn't have all the original features\n", "query_item = ['Google', 'Chrome', 'Process', 'unable', 'to', 'sandbox']\n", "lsh.top_N(query_item,dataframe['label'], 5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
![](\"files/images/agg.jpg\")
![](\"files/images/h_cluster.png\")
"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [],
"source": [
"# Even better save the graph out to json format and visualize it with D3 (D3js.org)\n",
"import networkx.readwrite.json_graph\n",
"import json\n",
"graph_json = networkx.readwrite.json_graph.tree_data(h_tree, root=root)\n",
"json.dump(graph_json, open('h_tree.json','w'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Please note the D3 vis below is embryonic, hoping to make it super cool...\n",
"To run the visualization in your web browser, here we're using port 9999 instead of standard 8888 because we may have IPython already running on 8888:\n",
"\n",
"\n",
"> cd data_hacking/fun_with_syslog\n",
"> python -m SimpleHTTPServer 9999 &\n",
"\n",
"\n",
"Now point your brower at the html file [http://localhost:9999/syslog_vis.html](http://localhost:9999/syslog_vis.html)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![](\"files/images/h_cluster_d3.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### ToDo\n",
"Really want to improve the interactive D3 based Hierarchical Tree Visualization [D3 Data Driven Documents](http://d3js.org)\n",
"\n",
"### Conclusions\n",
"We pulled in some syslog data into a Pandas dataframe, made some plots, computed row similarities with 'Banded MinHash' and used single-linkage clustering to build an agglomerative hierarchical cluster. Lots of possibilities from here, you could use just the LSH datastructure or the H-Cluster...\n",
"\n",
" - LogFile Viewer\n",
" - Click on a row, filter out everything that's similar\n",
" - Click on a row, color code all the other rows based on similarity\n",
" - Super fancy D3 zoom in/filter awesomeness..."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.6"
}
},
"nbformat": 4,
"nbformat_minor": 1
}