Showing posts with label facets. Show all posts
Showing posts with label facets. Show all posts

Friday, February 24, 2012

Experiments with Solr Faceting

Rationale

In my last project, I did quite a bit of work to customize Solr to serve results through it using our federated semantic (concept-based) search algorithms. In hindsight, I find that some of the work (especially around faceting) may not have been required, since Solr already provides ways to customize these behaviors using URL parameters (ie, no coding required). So I decided to see if I could implement some of the current behavior using Solr's built-in functionality, in a somewhat belated attempt to fill a gap in my knowledge.

I am also trying to find ways to move to a distributed Solr search setup. The problem is that there does not seem to be an awful lot of documentation on how to write Distributed Solr Components. However, as the Solr DistributedSearch wiki page indicates, most (or all) the built-in components support distributed search, so it makes sense to piggyback as much as possible on these.

Faceting

The faceting requirements for this application are as follows. There are three facet groups, for content source, category and review date.

The content source facets should be shown in descending order of counts, while the category facets should be displayed alphabetically by category name. But both of these are driven off indexed, non-tokenized fields, so all we need to do is specify the following parameters for these:

facet=true Enables faceting
facet.field=u_idx Facet by content source, order by count (default)
facet.field=u_category Facet by category
f.u_category.facet.sort=index Order category facets alphabetically

The review date facet is slightly more complicated. This requires us to define variable sized facets of 0-6 months old, 6 months to 1 year old, 1 to 2 years old, 2 to 5 years old and older than 5 years. Although Solr provides date faceting via facet.date, that is for fixed sized date intervals only, so we have to use the more powerful facet.query mechanism, and define queries for each facet in this group using Solr's date arithmetic. Here are the review date facet parameters.

facet.query=u_reviewdate:[NOW-6MONTH TO NOW] All records with reviewdate within last 6 months
facet.query=u_reviewdate:[NOW-1YEAR TO NOW-6MONTHS] All records with review date between 6 months to a year
facet.query=u_reviewdate:[NOW-2YEAR TO NOW-1YEAR] All records with review date between 1 and 2 years
facet.query=u_reviewdate:[NOW-5YEAR TO NOW-2YEAR] All records with review date between 2 and 5 years
facet.query=u_reviewdate:[NOW-100YEAR TO NOW-5YEAR] All records with review dates older than 5 years (to 100 years)

In addition, facets in each group are multi-select, and the facet filters should be OR'ed within each facet group, and AND'ed across facet groups. By default, Solr's fq parameters are applied in an AND fashion, so our client should group the facets appropriately to ensure this behavior. We do this by setting the currently selected facet into an "nfq" parameter, then regrouping the fq parameters at each request using logic as shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  def _groupFacets(self, fq, nfq):
    if not isinstance(fq, list):
      fqs = []
      fqs.append(fq)
    else:
      fqs = fq
    fqmap = {}
    map(lambda x: fqmap.update({x: set()}), \
      ["u_idx", "u_category", "u_reviewdate"])
    for fqe in fqs:
      # remove local parameters from previous call
      fqe = re.sub("^\\{.*:?[^}]\\}", "", fqe)
      fqee = fqe.split(" OR ")
      if len(fqee) > 0:
        k = fqee[0].split(":")[0]
        try:
          fqvs = map(lambda x: x.split(":")[1], fqee)
          fqmap[k].update(fqvs)
        except KeyError:
          pass
    # now add in the facet to the fqmap
    if len(nfq) > 0:
      (nfqk, nfqv) = nfq.split(":")
      fqmap[nfqk].add(nfqv)
    # now reconstruct the fq field
    newfqs = []
    for k in fqmap.keys():
      nv = map(lambda x: k + ":" + x, fqmap[k])
      if len(nv) > 0:
        newfqs.append("{!tag=" + k + "}" + " OR ".join(nv))
    return newfqs

We start off with an empty fq parameter. As each facet is selected, the nfq parameter is set, which is then regrouped into three fq parameters, one each for u_idx, u_category and u_reviewdate. So assuming the following sequence of selections: u_idx:adam, u_category:Disease, u_category:Birth Control, u_reviewdate:Less than 6 Months, the parameters look like:

1
2
3
fq={!tag=u_idx}u_idx:adam
&fq={!tag=u_category}u_category:Birth+Control OR u_category:Disease
&fq={!tag=u_reviewdate}u_reviewdate:[NOW-6MONTH TO NOW]

The local parameter tag names each filter, so we can exclude the latest filter from being counted against the current results. The last filter (in our case the u_reviewdate) should be excluded, so all the facet.query parameters would have the {!ex=u_reviewdate} local parameter set. If one of the other facet groups were the last selection, the appropriate facet.field would have the {!ex=...} local parameter set.

Highlighting

Being able to implement highlighting out of the box is not quite as important to my objective of distributed search as faceting, since my needs are a bit too custom to do out of the box, and in any case, this is on the slice of records for the current page, so not such a huge deal performance wise. But I wanted to know how to do it, and to build dynamic snippets for my results, so I did this as well.

The parameters to enable highlighting are fewer in number, although I didn't spend too much time refining it. Here are the parameters I used.

hl=true Enable highlighting
hl.fl=content Generate snippets off the content field
hl.snippets=3 Maximum number of fragments to generate for snippet
hl.fragsize=100 Maximum number of characters per snippet.

Sorting

Finally, the records need to be sorted by relevance (the default ordering) or by date (records reviewed most recently come first). This is done using a simple sort=u_reviewdate+desc parameter in the URL.

Python client code

I wrote a simple Python client that runs inside a CherryPy container and exposes a single search page. It fronts the Solr index that I built using Nutch over the last few weeks, converting Solr's JSON response to an interactive faceted search page. Here is the code for it.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
#!/usr/bin/python
import os.path

import cherrypy
import os
import re
import simplejson
import urllib
from urllib2 import *

SERVER_HOST = "localhost"
SERVER_PORT = 8080
SOLR_SERVER = "http://localhost:8983/solr/select"

class Root:

  def _getParam(self, req, name, default):
    return req.get(name) if req.get(name) != None else default

  def _tupleListToString(self, xs):
    s = ""
    for x in xs:
      (k, v) = x
      if len(s) > 0:
        s += "&"
      s += "=".join([k, v])
    return s

  def _groupFacets(self, fq, nfq):
    if not isinstance(fq, list):
      fqs = []
      fqs.append(fq)
    else:
      fqs = fq
    fqmap = {}
    map(lambda x: fqmap.update({x: set()}), \
      ["u_idx", "u_category", "u_reviewdate"])
    for fqe in fqs:
      # remove local parameters from previous call
      fqe = re.sub("^\\{.*:?[^}]\\}", "", fqe)
      fqee = fqe.split(" OR ")
      if len(fqee) > 0:
        k = fqee[0].split(":")[0]
        try:
          fqvs = map(lambda x: x.split(":")[1], fqee)
          fqmap[k].update(fqvs)
        except KeyError:
          pass
    # now add in the facet to the fqmap
    if len(nfq) > 0:
      (nfqk, nfqv) = nfq.split(":")
      fqmap[nfqk].add(nfqv)
    # now reconstruct the fq field
    newfqs = []
    for k in fqmap.keys():
      nv = map(lambda x: k + ":" + x, fqmap[k])
      if len(nv) > 0:
        newfqs.append("{!tag=" + k + "}" + " OR ".join(nv))
    return newfqs

  @cherrypy.expose
  def search(self, **kwargs):
    # retrieve url parameters, and create parameter list
    # for backend solr server
    solrparams = []
    sticky_params = []
    solrparams.append(tuple(["indent", self._getParam(\
      kwargs, "indent", "true")]))
    solrparams.append(tuple(["version", self._getParam(\
      kwargs, "version", "2.2")]))
    q = self._getParam(kwargs, "q", "*:*")
    solrparams.append(tuple(["q", q]))
    sticky_params.append(tuple(["q", q]))
    # fq parameters needs to grouped by facet group, so we can
    # do OR across members within the facet group, and AND for
    # facets across groups. For this, the fq parameter so far
    # is an array of fq PLUS the nfq parameter. This is
    # added to the existing fq to create a new grouped fq array.
    nfq = self._getParam(kwargs, "nfq", "")
    fq = self._groupFacets(self._getParam(kwargs, "fq", []), nfq)
    if isinstance(fq, list):
      if len(fq) > 0:
        for fqp in fq:
          solrparams.append(tuple(["fq", fqp]))
          sticky_params.append(tuple(["fq", fqp]))
    else:
      sticky_params.append(tuple(["fq", fq]))
    sort = self._getParam(kwargs, "sort", None)
    if sort != None:
      solrparams.append(tuple(["sort", sort]))
      sticky_params.append(tuple(["sort", sort]))
    solrparams.append(tuple(["start", \
      str(self._getParam(kwargs, "start", 0))]))
    solrparams.append(tuple(["rows", \
      str(self._getParam(kwargs, "rows", 10))]))
    solrparams.append(tuple(["facet", \
      str(self._getParam(kwargs, "facet", "true"))]))
    # for multi-fields, we need to mark the facet.field (or in case
    # of the Document Age facet, all the facet.query parameters with
    # the {!ex=fieldname} local parameters so it can be excluded from
    # the query
    facet_field = self._getParam(kwargs, "facet.field", \
      ["u_idx", "u_category"])
    if len(facet_field) > 0:
      for facet_fieldp in facet_field:
        if nfq != None and len(nfq.split(":")) == 2:
          nfqk = nfq.split(":")[0]
          if nfqk == facet_fieldp:
            solrparams.append(tuple(["facet.field", "{!ex=" + \
              nfqk + "}" + facet_fieldp]))
          else:
            solrparams.append(tuple(["facet.field", facet_fieldp]))
        else:
          solrparams.append(tuple(["facet.field", facet_fieldp]))
    facet_query = self._getParam(kwargs, "facet.query", [
      "u_reviewdate:[NOW-6MONTH TO NOW]",
      "u_reviewdate:[NOW-1YEAR TO NOW-6MONTHS]",
      "u_reviewdate:[NOW-2YEAR TO NOW-1YEAR]",
      "u_reviewdate:[NOW-5YEAR TO NOW-2YEAR]",
      "u_reviewdate:[NOW-100YEAR TO NOW-5YEAR]"
    ])
    nfqk = None
    if nfq != None and len(nfq.split(":")) == 2:
      nfqk = nfq.split(":")[0]
    for facet_queryp in facet_query:
      if nfqk == "u_reviewdate":
        solrparams.append(tuple(["facet.query", "{!ex=u_reviewdate}" + \
          facet_queryp]))
      else:
        solrparams.append(tuple(["facet.query", facet_queryp]))
    # facet sort
    solrparams.append(tuple(["f.u_category.facet.sort", \
      self._getParam(kwargs, "f.u_category.facet.sort", "index")]))
    # highlighting and summary generation
    solrparams.append(tuple(["hl", "true"]))
    solrparams.append(tuple(["hl.fl", "content"]))
    solrparams.append(tuple(["hl.snippets", "3"]))
    solrparams.append(tuple(["hl.fragsize", "100"]))
    # output format
    solrparams.append(tuple(["wt", "json"]))
    # result sort
    # display form
    html = """
<html><head><title>Search Test Page</title>
<style type="text/css">
em {
  background: rgb(255, 255, 0);
}
</style>
</head>
<body>
  <form name="sform" method="get" action="/search">
    <b>Query: </b><input type="text" name="q" value="%s"/>
    <input type="submit" value="Search"/>
  </form><br/><hr/>
    """ % (q)
    # make call to solr server
    params = urllib.urlencode(solrparams, True)
    conn = urllib.urlopen(SOLR_SERVER, params)
    rsp = simplejson.load(conn)
    # display facet navigation on LHS
    html += """
  <table cellspacing="3" cellpadding="3" border="0" width="100%">
    <tr>
      <td width="25%" valign="top">
    """
    # Source facet - this is a multi-select facet that is triggered
    # off the u_idx metadata field
    html += """
      <p><b>Source</b>
      <ul>
    """
    idx_facets = rsp["facet_counts"]["facet_fields"]["u_idx"]
    for i in range(0, len(idx_facets), 2):
      k = idx_facets[i]
      v = idx_facets[i+1]
      if int(v) == 0:
        html += """
          <li>%s (%s)</li>
        """ % (k, v)
      else:
        html += """
          <li><a href="/search?%s&nfq=u_idx:%s">%s (%s)</a></li>
        """ % (self._tupleListToString(sticky_params), k, k, v)
    html += """
      </ul></p>
    """
    # Category facet - this is a multi-select facet that is triggered
    # off the u_category field.
    html += """
      <p><b>Category</b>
      <ul>
    """
    category_facets = rsp["facet_counts"]["facet_fields"]["u_category"]
    for i in range(0, len(category_facets), 2):
      k = category_facets[i]
      v = category_facets[i+1]
      if k == "" or k == "default":
        continue
      if int(v) == 0:
        html += """
          <li>%s (%s)</li>
        """ % (k, v)
      else:
        html += """
          <li><a href="/search?%s&nfq=u_category:%s">%s (%s)</a></li>
        """ % (self._tupleListToString(sticky_params), k, k, v)
    html += """
      </ul></p>
    """
    # Document Age Facet - this is a multi-select facet driven by
    # custom queries
    time_facets = rsp["facet_counts"]["facet_queries"]
    html += """
      <p><b>Document Age</b>
      <ul>
    """
    time_facet_pos = 0
    time_facet_legends = [
      "Less than 6 Months",
      "6 Months - 1 Year",
      "1 Year - 2 Years",
      "2 Years - 5 Years",
      "More than 5 Years",
    ]
    for time_facet in time_facets:
      if int(time_facets[time_facet]) == 0:
        html += """
          <li>%s (%s)</li>
        """ % (time_facet_legends[time_facet_pos], time_facets[time_facet])
      else:
        html += """
          <li><a href="/search?%s&nfq=%s">%s (%s)</a></li>
        """ % (self._tupleListToString(sticky_params), time_facet, \
        time_facet_legends[time_facet_pos], time_facets[time_facet])
      time_facet_pos = time_facet_pos + 1
    # Main results
    html += """
      </ul></p>
      </td>
      <td width="75%" valign="top">
    """
    start = int(rsp["responseHeader"]["params"]["start"])
    rows = int(rsp["responseHeader"]["params"]["rows"])
    total = int(rsp["response"]["numFound"])
    next_start = start + rows if start + rows < total else 0
    prev_start = start - rows if start - rows >= 0 else -1
    qtime = rsp["responseHeader"]["QTime"]
    # Main result - prev/next links
    if prev_start > -1:
      html += """
        <a href="/search?%s&start=%d">Prev</a> |
      """ % (self._tupleListToString(sticky_params), prev_start)
    if next_start > 0:
      html += """
        <a href="/search?%s&start=%d">Next</a>
      """ % (self._tupleListToString(sticky_params), next_start)
    # Main result - metadata
    html += """
      <br/>
      <b>%d</b> to <b>%d</b> of <b>%d</b> results for <b>%s</b> in <b>%s</b>ms
      <br/>
    """ % (start+1, start+rows, total, q, qtime)
    # sort by relevance or date
    if sort == None:
      html += """
        <b>Sort by:</b> Relevance | 
           <a href="/search?%s&sort=u_reviewdate+desc">Date</a>
      """ % (self._tupleListToString(sticky_params))
    else:
      # remove the sort= parameter from the sticky param
      sticky_param_str = self._tupleListToString(sticky_params).replace(\
        "&sort=u_reviewdate desc", "")
      html += """
        <b>Sort by:</b> <a href="/search?%s">Relevance</a> | Date
      """ % (sticky_param_str)
    html += """
      <br/>
      <ol start="%d">
    """ % (start + 1)
    # Main results - data
    docs = rsp["response"]["docs"]
    for doc in docs:
      title = doc["title"]
      url = doc["url"]
      source = doc["u_idx"]
      category = "None"
      summary = "(no summary)"
      try:
        summary = "...".join(rsp["highlighting"][doc["id"]]["content"])
      except KeyError:
        content = doc["content"]
        summary = content[0:min(len(content), 250)] + "..."
      try:
        category = doc["u_category"]
      except KeyError:
        pass
      review_date = "None"
      try:
        review_date = doc["u_reviewdate"]
      except KeyError:
        pass
      html += """
        <li>
          <a href="%s">%s</a> [%s]
          <br/><font size="-1">Cat: %s, Reviewed: %s</font><br/>
          %s<br/>
        </li>
      """ % (url, title, source, category, str(review_date), summary)
    html += """
      </ol>
      </td>
    </tr>
  </table>
    """
    html += """
</body></html>
    """
    return [html]

if __name__ == '__main__':
  current_dir = os.path.dirname(os.path.abspath(__file__))
  # Set up site-wide config first so we get a log if errors occur.
  cherrypy.config.update({'environment': 'production',
    'log.access_file': 'site.log',
    'log.screen': True,
    "server.socket_host" : SERVER_HOST,
    "server.socket_port" : SERVER_PORT})
  cherrypy.quickstart(Root(), '/')

And here is a screenshot of the page in action...

The code is a bit on the monolithic side, but all I was after was a way to quickly surface the results in a easy to read (and easy to test) manner. Based on what I see so far, I think its possible to move faceting functionality out of my custom handler to URL parameters. Still not sure about the federated search handler, will report back as I find out more about that.

Update - 2012-02-29: Something I noticed while doing this work was that facet.fields are returned as a list of alternating facet and count, like ["facet1", count1, "facet2", count2, ...] rather than as a map, ie: {"facet1" : count1, "facet2" : count2, ...} (like facet.query responses do). Apparently this is by design, as Yonik Seeley explains in SOLR-3163 (which I opened, somewhat naively in retrospect). However, its easy enough to parse this structure using a for loop, as shown below. If this doesn't cut it for you, you may consider the json.nl parameter described in the link in SOLR-3163.

1
2
3
4
5
    idx_facets = rsp["facet_counts"]["facet_fields"]["u_idx"]
    for i in range(0, len(idx_facets), 2):
      k = idx_facets[i]
      v = idx_facets[i+1]
      # do something with key and value...

Saturday, April 14, 2007

Lucene Search within Search with BitSets

The Search within Search functionality is typically used when presenting results from an index in response to a user defined query. In addition to the search results returned to the user, we may want to show the user that he can drill down to get more focused search results for his query. So, for example, if the user searched for "cancer" on a medical search engine, in additions to pages that discuss cancer, we may want to show him how many occurences of "brain cancer", "lung cancer", etc, he can get from our index. These would be represented as a set of navigation links on the page. Clicking one of these links would spawn a fresh search with the augmented query term.

If you use Lucene, you will know that the popular ways of doing this is to either use a Boolean Query or search using a QueryFilter. A less popular, but incredibly powerful, way to count facet hits is to use BitSets returned by the QueryFilter. My ex-colleague Chris Hostetter refers to it in passing when announcing that CNET Category pages are powered by Lucene.

In this article, I present a Facet Hit counting class, which when passed in a reference to an IndexSearcher object, a reference to the base Lucene Query object, and a Map of facet names and their corresponding Query objects, returns a Map of facet names and their counts.

Caller code

The code for the caller would look something like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
  IndexSearcher searcher = new IndexSearcher("/path/to/index");
  Query baseQuery = new TermQuery(new Term("body", "cancer"));
  Map<String,Query> subQueries = new HashMap<String,Query>();
  subQueries.put("Lung Cancer", new TermQuery(new Term("body", "lung")));
  subQueries.put("Brain Cancer", new TermQuery(new Term("body", "brain")));
  subQueries.put("Skin Cancer", new TermQuery(new Term("body", "skin")));
  ...
  BitSetFacetHitCounter facetHitCounter = new BitSetFacetHitCounter();
  facetHitCounter.setSearcher(searcher);
  facetHitCounter.setBaseQuery(baseQuery);
  facetHitCounter.setSubQueries(subQueries);
  Map<String,Integer> counts = facetHitCounter.getFacetHitCounts();

The BitSetFacetHitCounter class

The code for the BitSetFacetHitCounter is shown below. The getFacetHitCounts() method creates the QueryFilter objects for the baseQuery and each of their subqueries and extracts their BitSets. Each bit in the BitSet corresponds to a Document in the index. If the bit is turned on, then the Document matched the query, else not. The intersection of the BitSets for the base query and the subquery is another BitSet, whose bits are turned on for those records where both the base query and the subquery are satisfied. In our example, the resulting BitSet will have only the bits for records containing "cancer" and "lung" turned on, so counting the 1's will give us the number of records for "lung cancer".

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class BitSetFacetHitCounter implements IFacetHitCounter {

  private Query baseQuery;
  private Map<String,Query> subQueries;
  private IndexSearcher searcher;

  public BitSetFacetHitCounter() {
    super();
  }

  public void setBaseQuery(Query baseQuery) {
    this.baseQuery = baseQuery;
  }

  public void setSubQueries(Map<String,Query> subQueries) {
    this.subQueries = subQueries;
  }

  public void setSearcher(IndexSearcher searcher) {
    this.searcher = searcher;
  }

  public Map<String,Integer> getFacetHitCounts() throws Exception {
    Map<String,Integer> facetCounts = new HashMap<String,Integer>();
    IndexReader reader = searcher.getIndexReader();
    QueryFilter baseQueryFilter = new QueryFilter(baseQuery);
    BitSet baseBitSet = baseQueryFilter.bits(reader);
    for (String attribute : subQueries.keySet()) {
      QueryFilter filter = new QueryFilter(subQueries.get(attribute));
      BitSet filterBitSet = filter.bits(reader);
      facetCounts.put(attribute, getFacetHitCount(baseBitSet, filterBitSet));
    }
    return facetCounts;
  }

  private int getFacetHitCount(BitSet baseBitSet, BitSet filterBitSet) {
    filterBitSet.and(baseBitSet);
    return filterBitSet.cardinality();
  }
}

Alternate implementations

The other options for doing this are using BooleanQueries and searching with QueryFilters. The code for the getFacetHitCounts() method using these methods are also shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  // using Boolean queries
  public Map<String,Integer> getFacetHitCounts() throws Exception {
    Map<String,Integer> facetCounts = new HashMap<String,Integer>();
    for (String attribute : subQueries.keySet()) {
      BooleanQuery facetQuery = new BooleanQuery();
      facetQuery.add(baseQuery, BooleanClause.Occur.MUST);
      facetQuery.add(subQueries.get(attribute), BooleanClause.Occur.MUST);
      Hits hits = searcher.search(facetQuery);
      facetCounts.put(attribute, hits.length());
    }
    return facetCounts;
  }

  // using search with QueryFilters
  public Map<String, Integer> getFacetHitCounts() throws Exception {
    Map<String,Integer> facetCounts = new HashMap<String,Integer>();
    for (String attribute : subQueries.keySet()) {
      QueryFilter filter = new QueryFilter(subQueries.get(attribute));
      Hits hits = searcher.search(baseQuery, filter);
      facetCounts.put(attribute, hits.length());
    }
    return facetCounts;
  }

Some performance numbers

I ran the same test case through all three implementations, working with 6 facets, in order to compare results. My experiments are not controlled, its simply tracking elapsed time using System.currentTimeMillis() in my JUnit test code, so your mileage may vary.

Implementation Elapsed time (ms)
Bit Set implementation 40
Query Filter implementation 41
Boolean Query Implementation 50

As you can see, there does not seem to be much difference, performance-wise, between the three implementations. However, I am guessing that the BitSet approach will outperform the others as the invocations are increased. Also, both the QueryFilter and the BitSet approach will take advantage of QueryFilter caching within Lucene, which can be useful if you are not using external caching.

Saturday, April 07, 2007

Document Classification using Naive Bayes

I have written earlier about faceted searching where each facet a document exposed represented a tag that was associated with the document. Of course, one of the most difficult aspects of setting up such a system is the setting up of the tags themselves. One way to build up the tag associations is to delegate it to the creator of the document, an approach taken by sites with user-generated content. Often, however, we have a large number of untagged documents, which we want to present as a searchable faceted collection. In such cases, we would have to assign the tags ourselves, which can be quite labor-intensive if we decide to do this manually.

One popular way to automatically tag documents is to use the Naive Bayes Classifier (BNC) algorithm. You can read about the math in the link, but basically BNC is based on the fact that if we know the probabilities of words appearing in a certain category of document, given the set of words in a new document, we can correctly predict if this new document is or is not that category of document.

I first heard of BNC from an ex-colleague who suggested the automatic tagging idea, extending what he understood about how SpamAssasin email spam filter works. Shortly thereafter, I read about it in Dr Dobb's Journal. But I never had the opportunity to actually use it until now.

I figured that since BNC seemed to be a useful algorithm, there would be open source implementation available on the web. I found a quite a few here. I looked through a few, but the only one I saw with halfway decent user-documentation was Classifier4J, so I chose that for my implementation of the automated tagger.

For my test data, I chose a collection of 21 articles I had written on my website years ago, and manually categorized into "Databases", "Web Development" and "Linux". The plan was to train a Bayesian Classifier instance with one match document from the target category and two non-match documents from the two other categories, then make it analyze all 21 documents. My initial implementation used the components provided in the classifier4j distribution - SimpleWordsDataSource for the words data source, the SimpleHTMLTokenizer for the tokenizer and the DefaultStopWordsProvider for the stop words provider.

However, the classification results were quite poor, and I wanted to find out why. I tried to build the package from source, but the project uses Maven 1.x which I am not familiar with, and I ended up building an empty jar file. I then tried to look at the words and their probabilities using the Eclipse debugger, but it did not give me any additional insights. So even though I try to avoid recreating functionality as much as possible, I ended up replacing most of the user-level components, depending only on classifier4j's core classes to do the probability calculations.

Usage

For convenience, I created the AutoTagger class, which is called from client code as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
  AutoTagger autoTagger = new AutoTagger();
  autoTagger.setStopwordFile(new File("/path/to/my/stopwords.txt"));
  autoTagger.setDataSource(new DriverManagerDataSource("com.mysql.jdbc.Driver",
    "jdbc:mysql://localhost:3306/classifierdb", "user", "pass"));

  autoTagger.addTrainingFile("database", databaseFilesArray);
  autoTagger.addTrainingFile("web", webFilesArray);
  autoTagger.addTrainingFile("linux", linuxFilesArray);
  autoTagger.train();

  double p = autoTagger.getProbabilityOfFileInCategory("database", someDbFile);

The AutoTagger internally contains references to a Map of Classifier objects keyed by category. The train() call will teach each of the Classifier the matched words for that category as well as the non-matches for all the other categories. The Bayesian classifier tends to produce probabilities that are either 0.01 to indicate no match and 0.99 to indicate a match.

The source for the AutoTagger class is shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class AutoTagger {

  private static final double CLASSIFICATION_CUTOFF_PROBABILITY = 0.5;
  
  private File stopwordFile;
  private DataSource dataSource;
  
  private Map<String,BatchingBayesianClassifier> classifiers = 
    new HashMap<String,BatchingBayesianClassifier>();
  private MultiMap categoryMap = new MultiHashMap();
  
  public AutoTagger() {
    super();
  }
  
  public void setStopwordFile(File stopwordFile) {
    this.stopwordFile = stopwordFile;
  }
  
  public void setDataSource(DataSource dataSource) {
    this.dataSource = dataSource;
  }
  
  public void addTrainingFiles(String category, File[] trainingFiles) {
    for (File trainingFile : trainingFiles) {
      categoryMap.put(category, trainingFile);
    }
    // if an instance of the classifier does not exist for category, create one
    if (! classifiers.containsKey(category)) {
      BatchingBayesianClassifier classifier = new BatchingBayesianClassifier(
        new JdbcWordsDataSource(dataSource),
        new CyberNekoHtmlTokenizer(DefaultTokenizer.BREAK_ON_WORD_BREAKS),
        new FileDrivenStopWordProvider(stopwordFile));
      classifiers.put(category, classifier);
    }
  }
  
  @SuppressWarnings("unchecked")
  public void train() throws WordsDataSourceException, ClassifierException, IOException {
    List<String> categoryList = new ArrayList<String>();
    categoryList.addAll(categoryMap.keySet());
    // teach the classifiers in all categories
    for (int i = 0; i < categoryList.size(); i++) {
      String matchCategory = categoryList.get(i);
      List<String> nonmatchCategories = new ArrayList<String>();
      for (int j = 0; j < categoryList.size(); j++) {
        if (i != j) {
          nonmatchCategories.add(categoryList.get(j));
        }
      }
      BatchingBayesianClassifier classifier = classifiers.get(matchCategory);
      List<File> teachMatchFiles = (List<File>) categoryMap.get(matchCategory);
      for (File teachMatchFile : teachMatchFiles) {
        String trainingFileName = teachMatchFile.getName();
        classifier.teachMatch(matchCategory, FileUtils.readFileToString(teachMatchFile, "UTF-8"));
        classifiers.put(matchCategory, classifier);
        for (String nonmatchCategory : nonmatchCategories) {
            classifier.teachNonMatch(nonmatchCategory,
            FileUtils.readFileToString(teachMatchFile, "UTF-8"));
          classifiers.put(nonmatchCategory, classifier);
        }
      }
    }
    classifiers.clear();
  }
  
  public boolean isFileInCategory(String category, File file)
      throws ClassifierException, WordsDataSourceException, IOException {
    return getProbabilityOfFileInCategory(category, file) >= CLASSIFICATION_CUTOFF_PROBABILITY;
  }
  
  public double getProbabilityOfFileInCategory(String category, File file) 
      throws ClassifierException, WordsDataSourceException, IOException {
    if (! classifiers.containsKey(category)) {
      BatchingBayesianClassifier classifier = new BatchingBayesianClassifier(
        new JdbcWordsDataSource(dataSource),
        new CyberNekoHtmlTokenizer(DefaultTokenizer.BREAK_ON_WORD_BREAKS),
        new FileDrivenStopWordProvider(stopwordFile));
      classifiers.put(category, classifier);
    }
    BatchingBayesianClassifier classifier = classifiers.get(category);
    if (classifier == null) {
      throw new IllegalArgumentException("Unknown category:" + category);
    }
    return classifier.classify(category, FileUtils.readFileToString(file, "UTF-8"));
  }
}

JdbcWordsDataSource

To be able to view (for debugging) the words that were being considered for the classification process, I needed to put them in a database. However, the provided JDBCWordsDataSource is very slow, because it tries to do an insert/update for each word that is not a stop word in the input document. I created a similar implementation of a JdbcWordsDataSource that will accumulate the inserts and updates until the entire document is read, then apply them all at once. It does the same thing during classification, by batching up all the words and issuing a single select call to get back all the word probability data. This produces a much more tolerable response time for the train() call (which is actually 3 calls, one teachMatch() and two teachNonMatch() calls in my case), and an almost instantaneous response for the classify() call. The code for my JdbcWordsDataSource is shown below:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/**
 * A Jdbc based implementation of ICategorisedWordsDataSource that can be
 * independently trained using files.
 */
public class JdbcWordsDataSource implements ICategorisedWordsDataSource {

  private JdbcTemplate jdbcTemplate;
  private Map<String,Integer> wordCountMap = new HashMap<String,Integer>();
  private Transformer quotingLowercasingTransformer = new Transformer() {
    public Object transform(Object input) {
      return "'" + StringUtils.lowerCase((String) input) + "'";
    }
  };
  
  public JdbcWordsDataSource(DataSource dataSource) {
    this.jdbcTemplate = new JdbcTemplate(dataSource);
  }
  
  public void addMatch(String word) throws WordsDataSourceException {
    addMatch(ICategorisedClassifier.DEFAULT_CATEGORY, word);
  }

  public void addMatch(String category, String word) throws WordsDataSourceException {
    addWord(word);
  }

  public void addNonMatch(String word) throws WordsDataSourceException {
    addNonMatch(ICategorisedClassifier.DEFAULT_CATEGORY, word);
  }

  public void addNonMatch(String category, String word) throws WordsDataSourceException {
    addWord(word);
  }

  public WordProbability getWordProbability(String word) throws WordsDataSourceException {
    return getWordProbability(ICategorisedClassifier.DEFAULT_CATEGORY, word);
  }

  @SuppressWarnings("unchecked")
  public WordProbability getWordProbability(String category, String word) 
      throws WordsDataSourceException {
    int matchCount = 0;
    int nonmatchCount = 0;
    List<Map<String,Integer>> rows = jdbcTemplate.queryForList(
      "select match_count, nonmatch_count " +
      "from word_probability " +
      "where word = ? and category = ?", 
      new String[] {word, category});
    for (Map<String,Integer> row : rows) {
      matchCount = row.get("MATCH_COUNT");
      nonmatchCount = row.get("NONMATCH_COUNT");
      break;
    }
    return new WordProbability(word, matchCount, nonmatchCount);
  }

  @SuppressWarnings("unchecked")
  public WordProbability[] calcWordsProbability(String category, String[] words) {
    List<WordProbability> wordProbabilities = new ArrayList<WordProbability>();
    List<String> wordsList = Arrays.asList(words);
    String query = "select word, match_count, nonmatch_count from word_probability where word in (" +
      StringUtils.join(new TransformIterator(wordsList.iterator(), quotingLowercasingTransformer), ',') +
      ") and category=?"; 
    List<Map<String,Object>> rows = jdbcTemplate.queryForList(query, new String[] {category});
    for (Map<String,Object> row : rows) {
      String word = (String) row.get("WORD");
      int matchCount = (Integer) row.get("MATCH_COUNT");
      int nonmatchCount = (Integer) row.get("NONMATCH_COUNT");
      WordProbability wordProbability = new WordProbability(word, matchCount, nonmatchCount);
      wordProbability.setCategory(category);
      wordProbabilities.add(wordProbability);
    }
    return wordProbabilities.toArray(new WordProbability[0]);
  }
  
  public void initWordCountMap() {
    wordCountMap.clear();
  }
  
  public void flushWordCountMap(String category, boolean isMatch) {
    for (String word : wordCountMap.keySet()) {
      int count = wordCountMap.get(word);
      if (isWordInCategory(category, word)) {
        updateWordMatch(category, word, count, isMatch);
      } else {
        insertWordMatch(category, word, count, isMatch);
      }
    }
  }
  
  @SuppressWarnings("unchecked")
  public void removeDuplicateWords() {
    List<Map<String,Object>> rows = jdbcTemplate.queryForList(
      "select word, count(*) dup_count " +
      "from word_probability " +
      "group by word " +
      "having dup_count > 1");
    List<String> words = new ArrayList<String>();
    for (Map<String,Object> row : rows) {
      words.add((String) row.get("WORD"));
    }
    jdbcTemplate.update("delete from word_probability where word in (" +
      StringUtils.join(new TransformIterator(words.iterator(), quotingLowercasingTransformer), ',') +
      ")");
  }
  
  private void addWord(String word) {
    int originalCount = 0;
    if (wordCountMap.containsKey(word)) {
      originalCount = wordCountMap.get(word);
    }
    wordCountMap.put(word, (originalCount + 1));
  }
  
  /**
   * Return true if the word is found in the category.
   * @param category the category to look up 
   * @param word the word to look up.
   * @return true or false
   */
  @SuppressWarnings("unchecked")
  private boolean isWordInCategory(String category, String word) {
    List<Map<String,String>> rows = jdbcTemplate.queryForList(
      "select word from word_probability where category = ? and word = ?", 
      new String[] {category, word});
    return (rows.size() > 0);
  }

  /**
   * @param category the category to update.
   * @param word the word to update.
   * @param isMatch if true, the word is a match for the category.
   */
  private void updateWordMatch(String category, String word, int count, boolean isMatch) {
    if (isMatch) { 
      jdbcTemplate.update(
        "update word_probability set match_count = match_count + ? " +
        "where category = ? and word = ?", 
        new Object[] {count, category, word});
    } else {
      jdbcTemplate.update(
        "update word_probability set nonmatch_count = nonmatch_count + ? " +
        "where category = ? and word = ?", 
        new Object[] {count, category, word});
    }
  }

  /**
   * @param category the category to insert.
   * @param word the word to update.
   * @param isMatch if true, the word is a match for the category.
   */
  private void insertWordMatch(String category, String word, int count, boolean isMatch) {
    if (isMatch) {
      jdbcTemplate.update("insert into word_probability(" +
        "category, word, match_count, nonmatch_count) values (?, ?, ?, 0)", 
        new Object[] {category, word, count});
    } else {
      jdbcTemplate.update("insert into word_probability(" +
          "category, word, match_count, nonmatch_count) values (?, ?, 0, ?)", 
          new Object[] {category, word, count});
    }
  }
}

The JdbcWordsDataSource decouples the word accumulation and persistence into two separate methods, which need to be called by the classifier. The accumulation is all done in memory, and a flushWordCountMap() will actually persist the map into the database.

BatchingBayesianClassifier

In order to use the batching capability, I needed to create a subclass of BayesianClassifier that would only take this particular implementation, and override the database dependent methods in the parent. The BatchingBayesianClassifier is shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Batches words for performance against the JdbcWordsDataSource. This is 
 * specific to this application's needs, so the constructor forces the caller
 * to provide specific implementations of the super-class's ctor args.
 */
public class BatchingBayesianClassifier extends BayesianClassifier {

  public BatchingBayesianClassifier(JdbcWordsDataSource wordsDataSource, 
      CyberNekoHtmlTokenizer tokenizer, FileDrivenStopWordProvider stopwordsProvider) {
    super(wordsDataSource, tokenizer, stopwordsProvider);
  }
  
  protected boolean isMatch(String category, String input[]) throws WordsDataSourceException {
    return (super.classify(category, input) > super.getMatchCutoff());
  }

  protected double classify(String category, String words[]) throws WordsDataSourceException {
    List<String> nonStopwords = new ArrayList<String>();
    FileDrivenStopWordProvider stopwordsProvider = (FileDrivenStopWordProvider) super.getStopWordProvider();
    for (String word : words) {
      if (stopwordsProvider.isStopWord(word)) {
        continue;
      }
      nonStopwords.add(word);
    }
    JdbcWordsDataSource wds = (JdbcWordsDataSource) super.getWordsDataSource();
    WordProbability[] wordProbabilities = wds.calcWordsProbability(category, nonStopwords.toArray(new String[0]));
    return super.normaliseSignificance(super.calculateOverallProbability(wordProbabilities));
  }

  protected void teachMatch(String category, String words[]) throws WordsDataSourceException {
    JdbcWordsDataSource wds = (JdbcWordsDataSource) super.getWordsDataSource();
    wds.initWordCountMap();
    super.teachMatch(category, words);
    wds.flushWordCountMap(category, true);
  }

  protected void teachNonMatch(String category, String words[]) throws WordsDataSourceException {
    JdbcWordsDataSource wds = (JdbcWordsDataSource) super.getWordsDataSource();
    wds.initWordCountMap();
    super.teachNonMatch(category, words);
    wds.flushWordCountMap(category, false);
  }

}

CyberNekoHtmlTokenizer

I also created my own implementation of the HTML Tokenizer using the NekoHTML parser from Cyberneko. This was because the SimpleHtmlTokenizer was crashing with the (admittedly bad and nowhere near spec-compliant) HTML in the documents. Cyberneko's NekoHTML parser is more forgiving, and I was able to pull out the body of my HTML document with the following implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class CyberNekoHtmlTokenizer extends DefaultTokenizer {

  public CyberNekoHtmlTokenizer() {
    super();
  }
  
  public CyberNekoHtmlTokenizer(int tokenizerConfig) {
    super(tokenizerConfig);
  }
  
  /**
   * Uses the Cyberneko HTML parser to parse out the body content from the
   * HTML file as a stream of text.
   * @see net.sf.classifier4J.ITokenizer#tokenize(java.lang.String)
   */
  public String[] tokenize(String input) {
    return super.tokenize(getBody(input));
  }
  
  public String getBody(String input) {
    try {
      DOMParser parser = new DOMParser();
      parser.parse(new InputSource(new ByteArrayInputStream(input.getBytes())));
      Document doc = parser.getDocument();
      NodeList bodyTags = doc.getElementsByTagName("BODY");
      if (bodyTags.getLength() == 0) {
        throw new Exception("No body tag in this HTML document");
      }
      Node bodyTag = bodyTags.item(0);
      return bodyTag.getTextContent();
    } catch (Exception e) {
      throw new RuntimeException("HTML Parsing failed on this document", e);
    }
  }
}

FileDrivenStopWordProvider

The DefaultStopWordProvider contained a hard coded array of stop words, which was pretty basic, so I built one to work off a file (the contents of which I scraped from the classifier4j message board, btw), which also treats numbers as stopwords. The code for the FileDrivenStopWordProvider is shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class FileDrivenStopWordProvider implements IStopWordProvider {

  private SortedSet<String> words = new TreeSet<String>();
  
  public FileDrivenStopWordProvider(File stopWordFile) {
    try {
      BufferedReader reader = new BufferedReader(
          new InputStreamReader(new FileInputStream(stopWordFile)));
      String word;
      while ((word = reader.readLine()) != null) {
        words.add(StringUtils.lowerCase(word.trim()));
      }
    } catch (FileNotFoundException e) {
      LOGGER.error("File:" + stopWordFile.getName() + " does not exist", e);
    } catch (IOException e) {
      LOGGER.error("Error reading file:" + stopWordFile.getName(), e);
    }
  }
  
  public boolean isStopWord(String word) {
    return words.contains(StringUtils.lowerCase(word.trim())) || StringUtils.isNumeric(word);
  }
}

Results

I ran the AutoTagger in two scenarios. The first was with low training, where I took the first file that was created in each category, and trained the classifiers with them, then ran the rest of the files against the trained classifiers. The assumption was that I knew what I was doing when classifying the first article, rather than attempt to shoehorn an article into an existing category set. The results from the run is shown below. The rows in gray indicate the files which were used for training.

File name Orig. class P(database) P(web) P(linux) Tags
artdb001 database 0.99 0.01 0.01 database
artdb002 database 0.99 0.01 0.01 database
artdb003 database 0.01 0.01 0.01 (none)
artdb005 database 0.01 0.01 0.01 (none)
artdb006 database 0.01 0.01 0.01 (none)
artdb007 database 0.01 0.01 0.01 (none)
artwb001 web 0.01 0.99 0.01 web
artwb002 web 0.01 0.01 0.01 (none)
artwb003 web 0.01 0.01 0.01 (none)
artwb004 web 0.01 0.01 0.01 (none)
artwb005 web 0.01 0.01 0.01 (none)
artwb006 web 0.01 0.01 0.01 (none)
artwb007 web 0.01 0.01 0.01 (none)
artli001 linux 0.01 0.01 0.01 (none)
artli002 linux 0.01 0.01 0.01 (none)
artli003 linux 0.01 0.01 0.01 (none)
artli004 linux 0.01 0.01 0.01 (none)
artli005 linux 0.01 0.01 0.01 (none)
artli006 linux 0.01 0.01 0.99 linux
artli007 linux 0.01 0.01 0.01 (none)
artli008 linux 0.01 0.01 0.01 (none)

As you can see, the results are not too great. Almost none of the documents besides the ones used for training were matched. This could be because of the paucity of training data. To rectify the situation, I created a high training scenario, where all but one of the files in each category is used for the training, then the trained classifiers are let loose on that one remaining file to see what category it is. The results for this test is shown below:

File name Orig. class P(database) P(web) P(linux) Tags
artdb001 database 0.99 0.01 0.01 database
artdb002 database 0.99 0.01 0.01 database
artdb003 database 0.99 0.01 0.01 database
artdb005 database 0.01 0.01 0.01 (none)
artdb006 database 0.99 0.99 0.01 database, web
artdb007 database 0.01 0.01 0.01 (none)
artwb001 web 0.01 0.99 0.01 web
artwb002 web 0.01 0.99 0.01 web
artwb003 web 0.01 0.01 0.01 (none)
artwb004 web 0.01 0.01 0.01 (none)
artwb005 web 0.01 0.99 0.01 web
artwb006 web 0.01 0.99 0.01 web
artwb007 web 0.99 0.99 0.01 database, web
artli001 linux 0.01 0.01 0.01 (none)
artli002 linux 0.01 0.01 0.99 linux
artli003 linux 0.01 0.01 0.01 (none)
artli004 linux 0.99 0.99 0.99 database, web, linux
artli005 linux 0.01 0.01 0.99 linux
artli006 linux 0.01 0.01 0.99 linux
artli007 linux 0.01 0.01 0.99 linux
artli008 linux 0.01 0.01 0.99 linux

The results are better than the first one, but it still misses a few. A surprising finding is that it finds that some articles can belong to multiple categories. Not so surprising, if you think that its the same person writing all three types, so a web article could involve a database, or a linux article could describe a database or webserver installation.

Conclusion

The BNC algorithm probably works best when there is much more training data available than what I provided it, and where the documents are more stratified, for example, politics versus technology, so there is less chance of overlapping words in each category. In my case, it does detect some things, but the results can probably be improved by providing more training data or pruning the words in the database after the training is complete and before classification is done.