In this chapter, we're going to focus on knowledge-based social networks, and in particular, we'll work with the StackExchange sites. For some time, StackExchange has made public a periodic data dump of their sites (http://blog.stackexchange.com/category/cc-wiki-dump/). This will provide a great test bed for working with a social network site's data.

The data dump is made available through the Internet Archive (https://archive.org/). The webpage for that is currently at https://archive.org/details/stackexchange. You can download the entire dump using a BitTorrent client (http://www.bittorrent.com/) such as μTorrent (http://www.utorrent.com/). However, we're only interested in the StackOverflow posts and comments, so if you'd like, you can just download those two archives. Of course, combined they're about 6 GB, so the torrent may make the most sense, anyway.

The archived files are compressed using the 7z format. Windows users can get a utility for extracting this from the 7-zip site (http://www.7-zip.org/). That site's download page also has links to some unofficial binaries for Mac OS X and Linux (http://www.7-zip.org/download.html). Both of these platforms also have command-line binaries available. For example, Homebrew (http://brew.sh/) has a recipe for this named p7zip.

Extract this data into your project directory, into a subdirectory named data, using the following lines of code:

cd data
7z x ~/torrents/stackexchange/stackoverflow.com-Posts.7z

Now we're ready to start digging into the data and see what surprises it has for us.

First, we need to see how much data there will be. The raw archive for this part of the data is about 6 GB. Not insignificant, but it's not petabytes, either.

So the compressed file is almost 5 GB, and the expanded file is 23 GB! We have a lot of data to look at.

<row Id="4"
     PostTypeId="1"
     AcceptedAnswerId="7"
     CreationDate="2008-07-31T21:42:52.667"
     Score="251"
     ViewCount="15207"
     Body="&lt;p&gt;I want to use a track-bar to change a form's opacity.&lt;/p&gt;

&lt;p&gt;This is my code:&lt;/p&gt;

&lt;pre&gt;&lt;code&gt;decimal trans = trackBar1.Value / 5000;
this.Opacity = trans;
&lt;/code&gt;&lt;/pre&gt;

&lt;p&gt;When I try to build it, I get this error:&lt;/p&gt;

&lt;blockquote&gt;
  &lt;p&gt;Cannot implicitly convert type 'decimal' to 'double'.&lt;/p&gt;
&lt;/blockquote&gt;

&lt;p&gt;I tried making &lt;strong&gt;trans&lt;/strong&gt; to &lt;strong&gt;double&lt;/strong&gt;, but then the control doesn't work.This code has worked fine for me in VB.NET in the past. &lt;/p&gt;
"
     OwnerUserId="8"
     LastEditorUserId="2648239"
     LastEditorDisplayName="Rich B"
     LastEditDate="2014-01-03T02:42:54.963"
     LastActivityDate="2014-01-03T02:42:54.963"
     Title="When setting a form's opacity should I use a decimal or double?"
     Tags="&lt;c#&gt;&lt;winforms&gt;&lt;forms&gt;&lt;type-conversion&gt;&lt;opacity&gt;"
     AnswerCount="13"
     CommentCount="25"
     FavoriteCount="23"
     CommunityOwnedDate="2012-10-31T16:42:47.213" />

<row Id="7"
     PostTypeId="2"
     ParentId="4"
     CreationDate="2008-07-31T22:17:57.883"
     Score="193"
     Body="&lt;p&gt;An explicit cast to double isn't necessary.&lt;/p&gt;

&lt;pre&gt;&lt;code&gt;double trans = (double)trackBar1.Value / 5000.0;
&lt;/code&gt;&lt;/pre&gt;

&lt;p&gt;Identifying the constant as &lt;code&gt;5000.0&lt;/code&gt; (or as &lt;code&gt;5000d&lt;/code&gt;) is sufficient:&lt;/p&gt;

&lt;pre&gt;&lt;code&gt;double trans = trackBar1.Value / 5000.0;
double trans = trackBar1.Value / 5000d;
&lt;/code&gt;&lt;/pre&gt;
"
     OwnerUserId="9"
     LastEditorUserId="967315"
     LastEditDate="2012-10-14T11:50:16.703"
     LastActivityDate="2012-10-14T11:50:16.703"
     CommentCount="0" />

We can trace out some of the data that we'll need to use throughout this chapter. We can put these into the src/social_so/data.clj file.

We'll use two record types. The CountRank type will hold together a raw count and its rank in the list of frequencies, and the UserInfo type will store the user and the frequencies and ranks for the different types of posts that they've made. Look at the following code:

(defrecord CountRank [count rank])
(defrecord UserInfo [user post q a])

The post, q, and a fields will keep track of the frequencies and rank by all posts, by question posts, and by answer posts.

Together, these record structures should help us get a start in understanding this data and some of the patterns of participation.

For loading the data, let's move to a new file, named src/social_so/xml.clj, and let's give it the following namespace declaration:

(ns social-so.xml
  (:require [clojure.data.xml :as xml]
            [clojure.java.io :as io]
            [clojure.string :as str]
            [social-so.data :as d]
            [social-so.utils :as u])
  (:import [org.jsoup Jsoup]
           [org.jsoup.safety Whitelist]))

We'll use the functions in this namespace to read the XML file and build the records containing the data.

At the most basic level, we need to be able to read the post elements from the XML file. Look at the following code:

(defn read-posts [stream] (:content (xml/parse stream)))

We'll also need to access a little bit of data from each element. The following are some getter functions for an identifier for the user and for the post type code:

(defn get-user [el]
  (let [{:keys [attrs]} el]
    (or (u/->long (:OwnerUserId attrs))
        (u/to-lower (:OwnerDisplayName attrs)))))
(defn get-post-type [el]
  (u/->long (:PostTypeId (:attrs el))))

In this snippet, el represents the XML element being processed, and we're using a custom function to lowercase the string (social-so.utils/to-lower) to be a little defensive about being passed null values.

Loading the data from the XML files will take place in two stages. First, we'll get the raw frequencies, and then we'll sort the data several different ways and assign ranks to the data.

The way that we'll count the frequencies is to walk over the posts in the XML file. We'll maintain an index of the users with their UserInfo records. The first time each user is found, they will get a new UserInfo object. Subsequently, their UserInfo record will be updated with new counts.

Let's see how this works in practice.

The first function, update-user-info, operates on the level of a single record. It takes a UserInfo record and updates it based on the type of post currently being processed. If the record is nil, then a new one is created follows:

(defn update-user-info [user-id post-el user-info]
  (let [incrs {:question [1 0], :answer [0 1]}
        [q-inc a-inc] (incrs (get-post-type post-el))]
    (cond
      (nil? q-inc) user-info
      (nil? user-info) (d/->UserInfo user-id 1 q-inc a-inc)
      :else
      (assoc user-info
             :post (inc (:post user-info))
             :q (+ (:q user-info) q-inc)
             :a (+ (:a user-info) a-inc)))))

The next function operates at the level of the index from user-id to UserInfo records. It takes an XML post, and it gets the user's information from it. It tries to retrieve the UserInfo record for that user from the index, and it uses update-user-info to increment the counts in that record. Look at the following code:

(defn update-user-index [user-index post-el]
  (let [user (get-user post-el)]
    (->> user
      (get user-index)
      (update-user-info user post-el)
      (assoc user-index user))))

Finally, load-user-infos opens the XML file, reads in the posts, and counts the raw frequencies of the posts for each user. Finally, it forces the result with doall, because we're working inside of a with-open block, so we'll want to have the results fully realized before we close the file. Look at the following code:

(defn load-user-infos [filename]
  (with-open [s (io/input-stream filename)]
    (->> s
      read-posts
      (reduce update-user-index {})
      vals
      (remove nil?)
      doall)))

Now we're ready to walk over these, multiple times, and assign ranks based on the various counts.

Currently, we're storing the raw frequency under the UserInfo records' fields. However, we want to move the frequencies into a CountRank record and store the rank alongside it. We will achieve this by performing the following steps:

All of these functions make it simple to load the XML file and to assign the ranks. Look at the following code:

user=> (def users (x/load-xml
                    "data/stackoverflow.com-Posts"))
user=> (count users)
1594450
user=> (first users)
{:user 22656,
 :post {:count 28166, :rank 0},
 :q {:count 29, :rank 37889},
 :a {:count 28137, :rank 0}}

Now we have the information that we'll need to perform the first round of analyses.

Now that we have some data loaded, let's roll up our sleeves and see what we can learn from it.

Before we do, however, it would be nice to have some way to generate reports of which users are the most active for each type of post. Look at the following code:

(defn print-top-rank [col-name key-fn n users]
  (let [fmt "%4s   %6s   %14s
"
        sort-fn #(:rank (key-fn %))]
    (printf fmt "Rank" "User" col-name)
    (printf fmt "----" "------" "--------------")
    (doseq [user (take n (sort-by sort-fn users))]
      (let [freq (key-fn user)]
        (printf fmt (:rank freq) (:user user) (:count freq))))))

This allows us to create tables listing the top 10 (or so) users for each post type.

Based on this table, we can see that some users are very active. The top user has almost 8,000 more posts than the second most active user, who is still very, very active.

The following graph, of the post counts of the top 1,000 users, shows how quickly the activity falls off and how much the top users dominate the conversation:

We can break this down further, however. I would expect the people who post questions to behave differently than the people who post answers.

We can get the users who only post answers fairly easily, and then running the previous analyses on that subset is also not difficult. Let's see how this will work. Look at the following code:

user=> (def qs (filter #(zero? (:count (:a %))) users))
user=> (def q-counts
            (map (d/sum-count :q)
                 (d/quantile-on 5 #(:rank (:q %)) qs)))
user=> (def total (reduce + 0 q-counts))
user=> (count qs)
780460
user=> q-counts
(969148 272085 156092 156092 156092)
user=> (map #(float (/ % total)) q-counts)
(0.566916 0.15915973 0.09130809 0.09130809 0.09130809)

So first we filtered for only users who post no answers. This leaves us with 49 percent of the total number of users, so this is really an extremely large group of StackOverflow users.

However, the interesting part is that their distribution is more uniform. The most active quintile has posted less than two-thirds of the questions. The following graph makes that clear:

The ratios for these are much different than we've seen so far. This group is much less driven by a few users. But when you think about it, this makes sense. Many people who come to StackOverflow only post one question, and that's the extent of their interaction. In fact, the bottom three quintiles only post one question and no answers. That's almost 33 percent of the total number of users.

Let's see how this compares to those who post only answers.

Getting the users who only post answers will be almost exactly like the process we just went through. However, this time we'll switch questions and answers, of course. Look at the following code:

user=> (def as (filter #(zero? (:count (:q %))) users))
user=> (def a-counts (map (d/sum-count :a)
                          (d/quantile-on 5 #(:rank (:a %)) as)))
user=> (def total (reduce + 0 a-counts))
user=> (count as)
375667
user=> (float (/ (count as) (count users)))
0.23561831
user=> a-counts
(1413820 116198 75134 75134 75131)
user=> (map #(float (/ % total)) a-counts)
(0.80540407 0.06619396 0.042801227 0.042801227 0.042799518)

This time, we're working with a group roughly half the size of those who post only questions, roughly a quarter of the entire group of users. And the distribution of the top quintile is much closer to what we'd expect from the 80/20 rule.

Again, notice that the last few quintiles appear to have users who have only posted one answer. In fact, about 16 percent of the total number of users have posted no questions and only one answer. This seems to be one of the most curious groups, and trying to get more interaction out of them would be a priority (as I'm sure it has been for StackExchange).

The graph for this, shown following this paragraph, is somewhat between the last graph (for those who ask only questions) and the first few graphs. The first quintile is about 80 percent, but the rest don't taper off as much as they sometimes do.

Now let's look at the breakdown for the rest of the users, those who've posted both questions and answers.

The predicate needed to select those users who have posted both questions and answers will be slightly different than what we've seen in the last two sections. However, once we have those users, the analysis will be the same. The only wrinkle will be that we'll get the distribution for both questions and answers.

We'll get the users who answer both using a slightly more complicated predicate, which we will page to remove. Look at the following code:

user=> (def both (remove #(or (zero? (:count (:q %)))
                              (zero? (:count (:a %))))
                         users))
user=> (count both)
438261

Now we'll also need to compute the values for both the questions and the answers. First, let's see what the questions look like:

user=> (def bq-counts
            (map (d/sum-count :q)
                 (d/quantile-on 5 #(:rank (:q %)) both)))
user=> (def total (reduce + 0 bq-counts))
user=> bq-counts
(3450712 730467 335892 160458 87649)
user=> (map #(float (/ % total)) bq-counts)
(0.72415173 0.1532927 0.07048887 0.033673033 0.018393647)

The graph that follows makes clear that the ratios on this are more like the distribution that we'd expect:

Looking at the numbers for the answers from this group, we again seem to be following a very rough approximation of the 80/20 rule. Look at the following code:

user=> (def ba-counts
            (map (d/sum-count :a)
                 (d/quantile-on 5 #(:rank (:a %)) both)))
user=> (def total (reduce + 0 ba-counts))
user=> ba-counts
(8564601 740590 270367 122164 87649)
user=> (map #(float (/ % total)) ba-counts)
(0.8752454 0.075683385 0.027629714 0.01248435 0.008957147)

And the following is the graph for this data:

So the group who has posted both questions and answers seem to be more balanced and have a more typical interaction with the website.

Another way of looking at this data is to look at how the number of questions each user posts by the number of answers each posts. This gives us an indication of how active users are in each type of activity. Look at the following graph:

This graph makes clear that typically users engage in one type of activity or another, and there's not as much cross-over as you might have expected. Also, the scales of the axes are a bit deceiving: the y axis is over 16 times larger than the x axis.

Now that we have a better understanding of the way that users are interacting with StackOverflow and the ways that they're generating content, let's look at that content and see if we can figure out what makes a good answer and what doesn't.

Now that the data is in a usable form, let's turn our attention to categorizing the posts. To do this, we'll use MALLET (http://mallet.cs.umass.edu/). We saw MALLET before in Chapter 3, Topic Modeling – Changing Concerns in the State of the Union Addresses, on topic modeling. That's usually the task that this library is used for. However, it also provides an implementation of a number of classification algorithms, and we'll use one of those now.

Over the course of this chapter, we'll categorize the posts as what MALLET calls instances. This will divide them into categories based on features, or clues within each instance. We'll use MALLET to take each post, create an instance from it, identify its features and categories, and finally use those to train a classifier. We can later use this classifier on new posts.

MALLET represents each input as an Instance object. Instance objects contain their data, a target label, name, and other metadata.

MALLET works on collections of Instance objects as an InstanceList, which is just a collection of Instance objects. All the instances in the list are processed using the same pipe of transformations.

Each step in the pipe changes one property of each Instance object in the list. For example, one pipe (CharSequence2TokenSequence) tokenizes the input, and another (Target2Label) creates an index of the target labels.

The following figure illustrates this process:

For the features in the documents and their labels, the InstanceList also maintains alphabets. These are indexes from the input strings to integers. The integers serve to distinguish the inputs and also act as indexes in arrays. This allows MALLET to work with frequencies as an array, which saves both space and processing time. The trick is that all of the Instance objects being processed must share the same alphabet. The InstanceList makes sure that they do.

For our processing, to make clear what transformations we'll use, we'll define them all in a function named make-pipe. The following is that function:

(defn make-pipe []
  (SerialPipes.
    [(Target2Label.)
     (Input2CharSequence. "UTF-8")
     (CharSequence2TokenSequence.
       #"p{L}[p{L}p{P}]+p{L}")
     (TokenSequenceLowercase.)
     (TokenSequenceRemoveStopwords. false false)
     (TokenSequence2FeatureSequence.)
     (FeatureSequence2FeatureVector.)]))

What's happening here? Let's take the steps apart.

So, at the end of this pipeline, each document will be represented by a vector indicating how many times each feature appears in that document. Features can be almost anything, but usually they are words that appear in the document or metadata (author, date, tags) associated with that document. This is the format that the classifiers—as well as many other machine learning and natural language algorithms—expect.

This handles the processing of the Instance objects, but before we can do that, we'll need to convert the PostInfo objects into Instance objects.

MALLET has a number of classes that do this from more primitive data types. They take some kind of collection of primitive inputs and iterate over the Instance objects they represent. In our case, we'll use ArrayDataAndTargetIterator. This iterates over two string arrays. One contains each input's data, and the other contains each input's target.

We'll wrap creating this with the function post-info-iterator. This uses the accepted-tag function to decide whether the post was accepted or not and tag it appropriately. Look at the following code:

(defn accepted-tag [post-info]
  (if (:accepted-for post-info) "accepted" "not"))
(defn post-info-iterator [post-infos]
  (ArrayDataAndTargetIterator.
    (into-array (map :body-text post-infos))
    (into-array (map accepted-tag post-infos))))

Once we have these functions, we can use them to populate an InstanceList that will run all the documents through the transformation pipeline that we defined earlier. Look at the following code:

(defn post-info-instances [post-infos]
  (doto (InstanceList. (make-pipe))
    (.addThruPipe (post-info-iterator post-infos))))

Now we're ready. Let's pick up with the PostInfo sample that we extracted earlier and bound to s in the Processing the answers section. This contains a sequence of PostInfo instances. In the REPL, we can create an InstanceList using the functions that we just defined as follows:

user=> (def ilist (n/post-info-instances s))

Now we can think about how we're going to use these documents to train and test a classifier.

Before we can use a classifier, we have to train it on the training set that we just created.

For this example, we'll create a Naive Bayesian classifier. Again, we'll just create a thin wrapper function. In this case, it's not that significantly simpler than creating the Bayesian trainer and calling it on the data. However, it will allow us to use the trainer without having to tease out which MALLET packages we have to import. This allows us to require our social-so.nlp namespace into the REPL and execute the entire process.

The following is the wrapper:

(defn bayes-train [ilist] (.train (NaiveBayesTrainer.) ilist))

And we can use the following in the REPL to get a trained Bayesian classifier:

user=> (def bayes (n/bayes-train (:training tt-sets)))

That's it. We've trained our classifier. Now let's see how to use it.

To test the classifier, MALLET provides a Trial class that encapsulates running a classifier over some inputs that are already tagged. It provides counts over how accurate the classifier is and calculates statistics to show how well it does.

To make it easier to load the development environment and to use this class, we'll create a factory function for it as follows:

(defn trial [classifier ilist] (Trial. classifier ilist))

And now let's use this function at the REPL as follows:

user=> (def trial (n/trial bayes (:test tt-sets)))

Well, great. Now what can we do with this?