File: tfidf.c

package info (click to toggle)
bow 19991122-4
  • links: PTS
  • area: main
  • in suites: woody
  • size: 2,544 kB
  • ctags: 2,987
  • sloc: ansic: 38,660; lisp: 1,072; makefile: 594; perl: 492; yacc: 149; sh: 91
file content (506 lines) | stat: -rw-r--r-- 14,966 bytes parent folder | download | duplicates (3)
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
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
/* Weight-setting and scoring implementation for TFIDF. */

/* Copyright (C) 1997, 1998, 1999 Andrew McCallum

   Written by:  Andrew Kachites McCallum <mccallum@cs.cmu.edu>

   This file is part of the Bag-Of-Words Library, `libbow'.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public License
   as published by the Free Software Foundation, version 2.
   
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA */

#include <bow/libbow.h>

#if !HAVE_LOG2F
#define log2f log
#endif

#if !HAVE_SQRTF
#define sqrtf sqrt
#endif

/* The number of documents with non-zero dot-product with the query. 
   Set in bow_tfidf_score(). */
int bow_tfidf_num_hit_documents;

#define DOING_LOG_COUNTS 1


/* Function to assign TFIDF weights to each element of each document
   vector. */
static void
bow_tfidf_set_weights (bow_barrel *barrel)
{
  int wi;			/* a "word index" into WI2DVF */
  int max_wi;			/* the highest "word index" in WI2DVF. */
  int ndocs;                    /* number of train documents looked at */
  double idf;			/* The IDF factor for a word */
  bow_dv *dv;			/* the "document vector" at index WI */
  double df;			/* "document frequency" */
#if 0
  int total_word_count;		/* total "document frequency" over all words */
#endif
  int dvi;			/* an index into the DV */
  bow_cdoc *cdoc;

  bow_verbosify (bow_progress, "Setting weights over words:          ");
  max_wi = MIN(barrel->wi2dvf->size, bow_num_words());

#if 0
  /* For certain cases we need to loop over all dv's to compute the
     total number of word counts across all words and all documents. */
  /* xxx Shouldn't this be changed, and put in the `for(wi..' loop below? */
  if (((bow_params_tfidf*)(barrel->method->params))->df_counts
      == bow_tfidf_occurrences)
    {
      total_word_count = 0;
      for (wi = 0; wi < max_wi; wi++) 
	{
	  dv = bow_wi2dvf_dv (barrel->wi2dvf, wi);
	  if (dv == NULL)
	    continue;
	  /* We have the document information, so we can determine which
	     documents are part the the training set. */
	  for (dvi = 0; dvi < dv->length; dvi++) 
	    {
	      cdoc = bow_cdocs_di2doc (barrel->cdocs, dv->entry[dvi].di);
	      if (cdoc->type == model)
		total_word_count += dv->entry[dvi].count;
	    }
	}
    }
#endif

  /* figure out the number of training documents */
  for (wi=ndocs=0; wi<barrel->cdocs->length; wi++) {
    cdoc = bow_array_entry_at_index (barrel->cdocs, wi);
    if (cdoc->type == bow_doc_train) {
      ndocs++;
    }
  }

  /* Loop over all vectors of documents (i.e. each word), calculate
     the IDF, then set the weights */
  for (wi = 0; wi < max_wi; wi++) 
    {
      /* Get the document vector for this word WI */
      dv = bow_wi2dvf_dv (barrel->wi2dvf, wi);

      if (dv == NULL)
	continue;

      /* Calculate the IDF, the "inverse document frequency". */

      /* First calculate document frequency. */
      df = 0;
      for (dvi = 0; dvi < dv->length; dvi++)
	{
	  cdoc = bow_array_entry_at_index (barrel->cdocs, dv->entry[dvi].di);
	  if (cdoc->type != bow_doc_train)
	    continue;
	  if (((bow_params_tfidf*)(barrel->method->params))->df_counts
	      == bow_tfidf_occurrences)
	    {
	      /* Make DF be the number of documents in which word WI occurs 
		 at least once.  (We can't just set it to DV->LENGTH because
		 we have to check to make sure each document is part of the
		 model. */
	      df++;
	    }
	  else if (((bow_params_tfidf*)(barrel->method->params))->df_counts
		   == bow_tfidf_words)
	    {
	      /* Make DF be the total number of times word WI appears
		 in any document. */
	      df += dv->entry[dvi].count;
	    }
	  else
	    bow_error ("Bad TFIDF parameter df_counts.");
	}

      /* Set IDF from DF. */
      if (df == 0) 
	{
	  /* There are no training documents with this word - ignore */
	  idf = 0.0;
	}
      else
	{
	  if (((bow_params_tfidf*)(barrel->method->params))->df_transform
	      == bow_tfidf_log)
	    idf = log2f (ndocs / df);
	  else if (((bow_params_tfidf*)(barrel->method->params))->df_transform
		   == bow_tfidf_sqrt)
	    idf = sqrtf (ndocs / df);
	  else if (((bow_params_tfidf*)(barrel->method->params))->df_transform
		   == bow_tfidf_straight)
	    idf = ndocs / df;
	  else
	    {
	      idf = 0;		/* to avoid gcc warning */
	      bow_error ("Bad TFIDF parameter df_transform.");
	    }
	}
      assert (idf == idf);	/* Make sure we don't have NaN. */

      /* Now loop through all the elements, setting their weights */
      for (dvi = 0; dvi < dv->length; dvi++)
#if DOING_LOG_COUNTS
	dv->entry[dvi].weight = log (dv->entry[dvi].count + 1) * idf;
#else
	dv->entry[dvi].weight = dv->entry[dvi].count * idf;
#endif
      
      /* Record this word's idf */
      dv->idf = idf;

      if (wi % 10 == 0)
	bow_verbosify (bow_progress, "\b\b\b\b\b\b%6d", max_wi - wi - 1); 
    }
  bow_verbosify (bow_progress, "\n");
}


/* Function to fill an array of the best matches to the document
   described by wv from the corpus in wi2dvf. There are 'best' elements
   in this array, in decreaseing order of their score. Nothing we can
   do if the we need more space to hold docs with the same scores as the
   final document in this list. The number of elements in the array is
   returned. The cdocs array is checked to make sure the
   document is in the model before getting it's vector product with
   the wv. Also, if the length field in cdocs is non-zero, then the
   product is divided by that length. */
int
bow_tfidf_score_old (bow_barrel *barrel, bow_wv *query_wv, 
		 bow_score *scores, int best, int loo_class)
{
  bow_dv_heap *heap;
  bow_cdoc *doc;
  int num_scores = 0;		/* How many elements are in this array */
  int current_di, wi, current_index, i;
  double current_score = 0.0, target_weight;
  float idf;

#if 0
  if (loo_class >= 0)
    bow_error ("PrInd cannot implement Leave-One-Out scoring.");
#endif

  /* Set the weights in the QUERY_WV.  Note: this is duplication of
     effort, since it was already done, but it was done incorrectly
     before, without the IDF. */
  bow_wv_set_weights_to_count_times_idf (query_wv, barrel);
  bow_wv_normalize_weights_by_vector_length (query_wv);

  if (query_wv->normalizer == 0)
    bow_error ("You forgot to set the weight normalizer of the QUERY_WV");

  /* Create the Heap of vectors of documents */
  heap = bow_make_dv_heap_from_wv (barrel->wi2dvf, query_wv);

  /* Keep looking at document/word entries until the heap is emptied */
  while (heap->length > 0)
    {
      /* Get the index of the document we're currently working on */
      current_di = heap->entry[0].current_di;

      /* Get the document structure */
      doc = bow_cdocs_di2doc (barrel->cdocs, current_di);
    
      /* If it's not a model document, then move on to next one */
      if (doc->type != bow_doc_train)
	{
	  do 
	    {
	      bow_dv_heap_update (heap);
	    }
	  while ((current_di == heap->entry[0].current_di)
		 && (heap->length > 0));
	
	  /* Try again */
	  continue;
	}

      /* Reset the index into out word vector */
      current_index = 0;

      /* Reset the weight */
      current_score = 0.0;

      /* Loop over all the words in this document, summing up the score */
      do
	{
	  wi = heap->entry[0].wi;
	  target_weight = 
	    heap->entry[0].dv->entry[heap->entry[0].index].weight;
	  /* We don't include NORMALIZER here because we multiple by it
	     all at once below. */

	  /* Find the correspoding word in our word vector */
	  while (wi > (query_wv->entry[current_index].wi))
	    current_index++;
	  assert (wi == query_wv->entry[current_index].wi);

	  /* Put in the contribution of this word */
	  /* xxx Under what conditions will IDF be zero?  Does the
	     right thing happen? */
	  idf = heap->entry[0].dv->idf;
	  assert (idf == idf);	/* testing for NaN */
	  /* xxx Why was this here?  assert (idf && idf > 0); */
	  current_score += 
	    (target_weight
	     * (query_wv->entry[current_index].weight 
		* query_wv->normalizer));

	  /* A test to make sure we haven't got NaN. */
	  assert (current_score == current_score);

	  /* Now we need to update the heap - moving this element on to its
	     new position */
	  bow_dv_heap_update (heap);
	}
      while ((current_di == heap->entry[0].current_di)
	     && (heap->length > 0));

      /* It is OK to normalize here instead of inside do-while loop 
	 above because we are summing the weights, and we can just
	 factor out the NORMALIZER. */
      assert (doc->normalizer > 0);
      current_score *= doc->normalizer;

      assert (current_score == current_score); /* checking for NaN */

      /* Store the result in the SCORES array */
      /* If we haven't filled the list, or we beat the last item in the list */
      if ((num_scores < best)
	  || (scores[num_scores - 1].weight < current_score))
	{
	  /* We're going to search up the list comparing element i-1 with
	     our current score and moving it down the list if it's worse */
	  if (num_scores < best)
	    {
	      i = num_scores;
	      num_scores++;
	    }
	  else
	    i = num_scores - 1;

	  /* Shift down all the bits of the array that need shifting */
	  for (; (i > 0) && (scores[i - 1].weight < current_score); i--)
	    scores[i] = scores[i-1];

	  /* Insert our new score */
	  scores[i].weight = current_score;
	  scores[i].di = current_di;
	}
    }

  bow_free (heap);

  /* All done - return the number of elements we have */
  return num_scores;
}



int
bow_tfidf_score (bow_barrel *barrel, bow_wv *query_wv, 
		 bow_score *scores, int scores_size, int loo_class)
{
  int num_scores = 0;		/* How many elements are in this array */
  int ci, i;
  float *lscores;
  int **wis;
  int wvi, dvi;
  bow_cdoc *cdoc;
  int num_hit_documents = 0;

#if 0
  if (loo_class >= 0)
    bow_error ("PrInd cannot implement Leave-One-Out scoring.");
#endif

  /* Yuck.  This is inefficient. */
  lscores = bow_malloc (barrel->cdocs->length * sizeof (float));
  wis = bow_malloc (barrel->cdocs->length * sizeof (int*));
  for (i = 0; i < barrel->cdocs->length; i++)
    {
      lscores[i] = 0;
      wis[i] = NULL;
    }

  /* Set the weights in the QUERY_WV.  Note: this is duplication of
     effort, since it was already done, but it was done incorrectly
     before, without the IDF. */
#if DOING_LOG_COUNTS
  bow_wv_set_weights_to_log_count_times_idf (query_wv, barrel);
#else
  bow_wv_set_weights_to_count_times_idf (query_wv, barrel);
#endif
  bow_wv_normalize_weights_by_vector_length (query_wv);

  for (wvi = 0; wvi < query_wv->num_entries; wvi++)
    {
      bow_dv *dv = bow_wi2dvf_dv (barrel->wi2dvf, query_wv->entry[wvi].wi);

      /* If the model doesn't know about this word, skip it. */
      if (!dv)
	continue;

      /* Loop over all documents/classes that contain word WI,
	 and increment their score. */
      for (dvi = 0; dvi < dv->length; dvi++)
	{
	  cdoc = bow_array_entry_at_index (barrel->cdocs, dv->entry[dvi].di);
	  lscores[dv->entry[dvi].di] += ((query_wv->entry[wvi].weight
					  * query_wv->normalizer)
					 * (dv->entry[dvi].weight
					    * cdoc->normalizer));
	  if (wis[dv->entry[dvi].di] == NULL)
	    {
	      int j;
	      wis[dv->entry[dvi].di] = bow_malloc ((query_wv->num_entries+1)
						   * sizeof (int));
	      for (j = 0; j < (query_wv->num_entries+1); j++)
		wis[dv->entry[dvi].di][j] = -1;
	    }
	  i = 0;
	  while (wis[dv->entry[dvi].di][i] >= 0)
	    i++;
	  assert (i <= query_wv->num_entries);
	  wis[dv->entry[dvi].di][i] = query_wv->entry[wvi].wi;
	  /* Why was this here? 
	     assert (wis[dv->entry[dvi].di][i] != 1); */
	}
    } 

  for (ci = 0; ci < barrel->cdocs->length; ci++)
    {
      if (lscores[ci] == 0)
	continue;
      
      num_hit_documents++;
      
      /* Store the result in the SCORES array */
      /* If we haven't filled the list, or we beat the last item in the list */
      if ((num_scores < scores_size)
	  || (scores[num_scores - 1].weight < lscores[ci]))
	{
	  /* We're going to search up the list comparing element i-1 with
	     our current score and moving it down the list if it's worse */
	  if (num_scores < scores_size)
	    {
	      i = num_scores;
	      num_scores++;
	    }
	  else
	    i = num_scores - 1;

	  /* Shift down all the bits of the array that need shifting */
	  for (; (i > 0) && (scores[i - 1].weight < lscores[ci]); i--)
	    scores[i] = scores[i-1];

	  /* Insert our new score */
	  scores[i].weight = lscores[ci];
	  scores[i].di = ci;

#if 1
	  {
	    /* Store the appearing words in NAME. */
	    char buf[BOW_MAX_WORD_LENGTH * query_wv->num_entries];
	    int j;

	    assert (wis[ci]);
	    buf[0] = '\0';
	    for (j = 0; wis[ci][j] >= 0; j++)
	      {
		strcat (buf, bow_int2word (wis[ci][j]));
		strcat (buf, " ");
	      }
	    scores[i].name = strdup (buf);
	    assert (scores[i].name);
	  }
#else
	  scores[i].name = NULL;
#endif
	}
    }

  bow_free (lscores);
  for (i = 0; i < barrel->cdocs->length; i++)
    {
      if (wis[i])
	bow_free (wis[i]);
    }
  bow_free (wis);

  bow_tfidf_num_hit_documents = num_hit_documents;

  /* All done - return the number of elements we have */
  return num_scores;
}

bow_params_tfidf bow_tfidf_params_tfidf_words =
{
  bow_tfidf_words,
  bow_tfidf_straight
};

bow_params_tfidf bow_tfidf_params_tfidf_log_words =
{
  bow_tfidf_words,
  bow_tfidf_log
};

bow_params_tfidf bow_tfidf_params_tfidf =
{
  bow_tfidf_occurrences,
  bow_tfidf_log
};

bow_params_tfidf bow_tfidf_params_tfidf_log_occur =
{
  bow_tfidf_occurrences,
  bow_tfidf_log
};

#define TFIDF_METHOD(PARAM_NAME)					\
rainbow_method bow_method_ ## PARAM_NAME =				\
{									\
  #PARAM_NAME,								\
  bow_tfidf_set_weights,						\
  0,				/* no weight scaling function */	\
  bow_barrel_normalize_weights_by_vector_length,			\
  bow_barrel_new_vpc_weight_then_merge,					\
  0,				/* no prior-setting function */		\
  bow_tfidf_score,							\
  bow_wv_set_weights_to_count_times_idf,				\
  bow_wv_normalize_weights_by_vector_length,				\
  bow_barrel_free,							\
  &bow_tfidf_params_ ## PARAM_NAME					\
};									\
void _register_method_ ## PARAM_NAME ()					\
 __attribute__ ((constructor));						\
void _register_method_ ## PARAM_NAME ()					\
{									\
  bow_method_register_with_name ((bow_method*)&                         \
                                 bow_method_ ## PARAM_NAME,		\
				 #PARAM_NAME,				\
				 sizeof (rainbow_method),               \
				 NULL);					\
}

TFIDF_METHOD(tfidf_words)
TFIDF_METHOD(tfidf_log_words)
TFIDF_METHOD(tfidf_log_occur)
TFIDF_METHOD(tfidf)