Just for fun, I ported this program to Haskell. It appears to generate identical results, and completes the training set in 11.23 user seconds.
I learnt Haskell before I tried using Clojure and really like it as a language. It doesn't surprise me that it runs faster. I'm guessing the feature value look-ups don't involve the extra unboxing that Java's maps do.
Types in Haskell are boxed as well, though it's possible to get around this with some GHC-specific hackery, I haven't done it.
But the biggest problem is the parsing code -- it actually spends around 70% of the runtime parsing the input! Changing to regular expressions may help that, but I gave up trying to find good documentation for Text.Regex.Posix.