Document term matrix in Clojure

Question

This is my very first foray into Clojure (I'm normally a Python-pushing data-type). I'm trying to create a simple term-document matrix as a vector of vectors, out of a vector of strings.

For those who aren't into textmining, the term-document matrix is a dataset in matrix form where the column names represent every word in a set of documents, each row is a document, and each cell is the number of times a given word appears in a given document.

This is the very first step in what I hope to be a useful text data-cleaning library, as well as a clojure learning project. After the basics are nailed down, I want to add functionality like n-grams, stemming, removing sparse terms, etc. etc. My ultimate goals involve performance, so I want to optimize this beginning part within an inch of its life right from the start in order to build on it later.

I'm also trying to minimize dependencies (right now there are none), though I'm willing to use incanter or clojure.core.matrix if there are big performance gains to be gotten thereby.

So obviously I have a long way to go, but here are some questions on this initial step:

1. Is this "good clojure?" I tried to stick to sort of basic functional programming practice, composing lots of short functions with discrete behavior and such. But I'm not yet sure what the norms are otherwise.

2. How do I optimize this? The particular parts of the existing code that smell funny to me, performance-wise, are:

   1. terdocmmap: there's gotta be a more efficient way of handling the sorting here than building a bunch of sparse maps then sorting them all. Ideally I'd like to build them in sorted form from the start somehow.

   2. termdocmatrix: the maps -> sequences -> vectors conversion seems really wasteful; I'd like to come up with a more efficient way.

I'm not worrying about namespace and project structure at this stage.

(require '[clojure.string :as str])
(require '[clojure.walk :as walk])

(defn whitesplit 
  "split a vector of string into vector of vectors of strings on whitespace" 
  [docs] 
  (map #(str/split % #" ") docs))

(defn stringcounts 
  "count frequencies of strings in vector of vectors of strings" 
  [stringvecs]
  (map frequencies stringvecs))   

(defn liststrings 
  "list all strings in doc set" 
  [stringvecs]
  (distinct 
    (apply concat stringvecs)))

(defn makezeroes 
  [stringlist] 
  (zipmap stringlist (repeat 0)))

(defn expandcounts 
  "based on strings in all docs, fill counts with 0 for unused strings in each single doc"
  [zeroes counts]
  (map #(merge-with + % zeroes) counts))

(defn bigmap
  "split vector of docs by spaces then make zero-filled map of counts"
  [docs]
  (let [stringvecs (whitesplit docs)]
    (expandcounts 
      (-> stringvecs liststrings makezeroes) 
      (-> stringvecs stringcounts))))  

(defn terdocmmap
  "make a sorted document-term-map of vector of docs with keywords"
  [docs]
  (walk/keywordize-keys  ; this is mainly for later flexibility
    (map #(into (sorted-map) %) (bigmap docs))))

(defn tdseqs
  "convert document-term-map into sequence of sequences"
  [tdmap]
  (cons 
    (keys (first tdmap))
    (map vals tdmap)))

(defn nestvecify 
  "sequence of sequences --> vector of vectors"
  [seqofseq]
  (into [] (map #(into [] %) seqofseq)))

(defn termdocmatrix 
  "make document term matrix as vector of vectors from vector of docs"
  [docs]
  (-> docs terdocmmap tdseqs nestvecify))

Example input and output:

(termdocmatrix ["this is a cat" "this is a dog" "woof and a meow" "woof woof woof meow meow words"])

Produces:

[[:cat :is :this :words :dog :and :meow :woof :a] [1 1 1 0 0 0 0 0 1] [0 1 1 0 1 0 0 0 1] [0 0 0 0 0 1 1 1 1] [0 0 0 1 0 0 2 3 0]]

Answer 1

Is this "good clojure?" I tried to stick to sort of basic functional programming practice, composing lots of short functions with discrete behavior and such.

I think you're doing more work (writing more functions and doing more data transformations) than necessary.

Two-and-a-half points in particular:

• In general I'd recommend writing functions that operate on one thing and applying them externally using map if necessary, as opposed to internalizing the map in the function -- especially if you're only using the function once or twice. This approach is often easier to compose and read, despite having to write map once or twice more.

  stringcounts, for example, is just (partial map frequencies). At a glance, (map frequencies ...) is easy to understand as a combination of two core functions, while stringcounts is another name to remember.

  Writing and composing short functions is good! But it's a balancing act of taste between general expressiveness ("I've written this pattern x times, it should go in a well-named function") and familiarity/ease of reading ("I'm very familiar with the core functions and how to combine them, and anything extra, especially if it's minor, is more to remember and learn"). Usually leaning more towards exposing the core functions is not a bad idea. But I'm just some guy.

• makezeroes and expandcounts can be combined and simplified by approaching the problem as "supply 0 if the term doesn't exist in the frequency map" instead of "make a 0-filled vector and merge the term counts on top". You can do this using the not-found param of get.

• mapv can be used to reduce the conversions between seq and vector.

Here's a condensed version of your code, incorporating these suggestions. The core process still uses frequencies and distinct, but I've removed some intermediate steps:

(defn white-split [s]
  (str/split s #"\s+"))

; Prepare a single document (apply this externally using `map`)
(defn prepare-doc [s]
  (->> s
       white-split
       (map keyword)))

(defn select-values
  "select-values :: [k], {k: v}, v -> [v]
  Maps each key in ks to its value in m, filling in with default if not found.
  Returns a vector."
  [ks m default]
  (mapv (fn [k] (get m k default))
        ks))

(def term-frequencies
  (comp frequencies prepare-doc))

(defn term-doc-matrix
  [docs]
  (let [freq-maps (map term-frequencies docs)
        terms (->> freq-maps (mapcat keys) distinct vec)]
    {:terms terms
     :freqs (mapv #(select-values terms % 0)
                  freq-maps)}))

Now, in this version I have term-doc-matrix returning a map instead of having the keys (terms) as the first row in the matrix.

You can change this fairly easily; my reasoning, though, keeping in mind that I'm not very familiar with text mining, is that

• this seems like a more useful intermediate form, because it separates the two parts of the data (keys and values), and
• prepending to a vector is slow (linear time), and I couldn't quickly come up with a similarly elegant way to start with [[keys]] and append onto it, without breaking some of the high-level abstractions.

---

Performance notes

My ultimate goals involve performance, so I want to optimize this beginning part within an inch of its life right from the start in order to build on it later.

Algorithmically, right now we

• loop through docs once to split each string into keywordized words and apply frequencies to it
  • easily parallelizable with pmap, depending on how long each doc tends to be
• make a vector of unique keys (terms)
  • this should be relatively quick, although distinct will be O(n)
• nested loops for term-to-freq-map lookups
  • O(len(freq-maps) * len(terms))
  • could be parallelized

I can't find any clear way of simplifying this process, so I'll just recommend using less intermediate functions (as above), and, if you can, parallelization.

Parallelization

...could speed some of this up. pmap is easy to substitute for map when the mapping function is heavy, although if it's relatively light then the overhead of thread scheduling makes it slower than normal map. There are also clojure.core.reducers.

A little more interestingly, tesser is extremely powerful and can be faster / more effective than reducers, but would involve a bit more postprocessing work because it doesn't guarantee order.

Transients

Clojure also provides ways to use internal mutable state inside a function for speed. select-values, in particular, could benefit from this, and would look more like this:

(defn select-values
  [ks m default]
  (persistent!
    (reduce (fn [v k]
              (conj! v (get m k default)))
            (transient [])
            ks)))

Answer 2

I'm pretty new at Clojure myself, and haven't studied the collection algorithms very much yet, so this may not address your performance concerns, but I did find a few things that could be improved.

---

Potential problem with "real" document input

As I started going through your functions and how they work together, I noticed that your logic makes the assumption that all input will always just be words separated by spaces. Perhaps your data set is already preprocessed before it enters your termdocmatrix function? Unless that is the case, any text from actual documents written by humans will have many artifacts like punctuation marks and such that you should probably account for.

I ran these to illustrate what happens with more "natural" document text:

(def docs-punc ["this is, a cat" "this is a dog." "woof: and a meow" "woof; woof woof! meow? meow words"])
(whitesplit docs-punc)
; => ([this is, a cat] [this is a dog.] [woof: and a meow] [woof; woof woof! meow? meow words])
(termdocmatrix docs-punc)
; => [[:cat :dog. :is :this :woof: :is, :words :meow? :woof! :and :meow :woof; :woof :a] [1 0 0 1 0 1 0 0 0 0 0 0 0 1] [0 1 1 1 0 0 0 0 0 0 0 0 0 1] [0 0 0 0 1 0 0 0 0 1 1 0 0 1] [0 0 0 0 0 0 1 1 1 0 1 1 1 0]]

That totally messed up the results as you can see. I added a strip-punc function at the top (I made punc-to-remove its own form for readability, personal preference), and a helper function to apply it to a vector of strings:

(defn strip-punc
  "remove punctuation marks in string using `punc-to-remove` capture pattern and replacing them with empty string"
  [str]
  (def punc-to-remove #"[.,;:!?$%&\*()]")
  (str/replace str punc-to-remove ""))

(defn vec-strip-punc
  "applies strip-punc to a vector of strings"
  [vec]
  (map #(strip-punc %) vec))

Then change your bigmap function accordingly to call it before you split the strings:

  (let [docs-no-punc (vec-strip-punc docs)
        stringvecs (whitesplit docs-no-punc)] ; etc.

Or alternatively inline style:

(let [stringvecs (whitesplit (vec-strip-punc docs))]

This will take care of pretty much all your general punctuation cases, and you can easily tweak the regex pattern as needed:

(def docs-punc ["this is, a cat%" "this $is a dog." "woof: and [a] meow*" "woof; (woof woof!) meow? meow words"])
(termdocmatrix docs-punc)
; => [[:cat :is :this :words :dog :and :meow :woof :a] [1 1 1 0 0 0 0 0 1] [0 1 1 0 1 0 0 0 1] [0 0 0 0 0 1 1 1 1] [0 0 0 1 0 0 2 3 0]]

---

Naming

Your names don't follow typical Lisp naming convention. According to Wikipedia on naming conventions (programming):

Common practice in most Lisp dialects is to use dashes to separate words in identifiers, as in with-open-file and make-hash-table. Global variable names conventionally start and end with asterisks: *map-walls*. Constants names are marked by plus signs: +map-size+.

Also since most/all your functions actually transform your data structure, I would suggest naming them in a way that suggests that. Perhaps also using an acronym consistently, let's say td (or even TD) for term-document, that would make it read better without being really verbose.

termdocmatrix -> TD-matrix-from-docs
terdocmmap -> TD-map-from-docs
tdseqs -> TD-seqs-from-TD-map

bigmap I don't think is a descriptive name. What is "big" in this context? In truth it reminds me of a Cartesian product, since each document entry in the docs vector will return its own map of all possible words, e.g., {this 1, is 1, a 1, cat 1, dog 0, woof 0, and 0, meow 0, words 0}. I would be tempted to call it something like cartesian-product-map or perhaps just cartesian-map.

I would also suggest to perhaps change whitesplit to space-split, since that is really what it is doing (it is not splitting other whitespace like \r \n \t. Or if you want to make it a true whitespace-split, then you should change #" " to the #"\s" special character which includes "all whitespace". Here is an article on RegexOne about it.