← Back to branch summary

~ubuntu-branches/ubuntu/precise/weka/precise

« back to all changes in this revision

Viewing changes to weka/associations/ItemSet.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/associations/ItemSet.java
 
1
/*
 
2
 *    This program is free software; you can redistribute it and/or modify
 
3
 *    it under the terms of the GNU General Public License as published by
 
4
 *    the Free Software Foundation; either version 2 of the License, or
 
5
 *    (at your option) any later version.
 
6
 *
 
7
 *    This program is distributed in the hope that it will be useful,
 
8
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
 *    GNU General Public License for more details.
 
11
 *
 
12
 *    You should have received a copy of the GNU General Public License
 
13
 *    along with this program; if not, write to the Free Software
 
14
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
15
 */
 
16
 
 
17
/*
 
18
 *    ItemSet.java
 
19
 *    Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
 
20
 *
 
21
 */
 
22
 
 
23
package weka.associations;
 
24
 
 
25
import weka.core.FastVector;
 
26
import weka.core.Instance;
 
27
import weka.core.Instances;
 
28
 
 
29
import java.io.Serializable;
 
30
import java.util.Enumeration;
 
31
import java.util.Hashtable;
 
32
 
 
33
/**
 
34
 * Class for storing a set of items. Item sets are stored in a lexicographic
 
35
 * order, which is determined by the header information of the set of instances
 
36
 * used for generating the set of items. All methods in this class assume that
 
37
 * item sets are stored in lexicographic order.
 
38
 * The class provides the general methods used for item sets in class - and 
 
39
 * standard association rule mining.
 
40
 *
 
41
 * @author Eibe Frank (eibe@cs.waikato.ac.nz)
 
42
 * @version $Revision: 1.12 $
 
43
 */
 
44
public class ItemSet
 
45
  implements Serializable {
 
46
 
 
47
  /** for serialization */
 
48
  private static final long serialVersionUID = 2724000045282835791L;
 
49
  
 
50
  /** The items stored as an array of of ints. */
 
51
  protected int[] m_items;
 
52
 
 
53
  /** Counter for how many transactions contain this item set. */
 
54
  protected int m_counter;
 
55
 
 
56
  /** The total number of transactions */
 
57
  protected int m_totalTransactions;
 
58
 
 
59
  /**
 
60
   * Constructor
 
61
   * @param totalTrans the total number of transactions in the data
 
62
   */
 
63
  public ItemSet(int totalTrans) {
 
64
    m_totalTransactions = totalTrans;
 
65
  }
 
66
 
 
67
   /**
 
68
   * Constructor
 
69
   * @param totalTrans the total number of transactions in the data
 
70
   * @param array the attribute values encoded in an int array
 
71
   */
 
72
  public ItemSet(int totalTrans, int[] array){
 
73
       
 
74
       m_totalTransactions = totalTrans;
 
75
       m_items = array;
 
76
       m_counter =1;
 
77
   }
 
78
  
 
79
  /** Contsructor
 
80
   * @param array the item set represented as an int array
 
81
   */  
 
82
  public ItemSet(int[] array){
 
83
       
 
84
       m_items = array;
 
85
       m_counter = 0;
 
86
   }
 
87
 
 
88
  /**
 
89
   * Checks if an instance contains an item set.
 
90
   *
 
91
   * @param instance the instance to be tested
 
92
   * @return true if the given instance contains this item set
 
93
   */
 
94
  public boolean containedBy(Instance instance) {
 
95
    
 
96
    for (int i = 0; i < instance.numAttributes(); i++) 
 
97
      if (m_items[i] > -1) {
 
98
        if (instance.isMissing(i))
 
99
          return false;
 
100
        if (m_items[i] != (int)instance.value(i))
 
101
          return false;
 
102
      }
 
103
    return true;
 
104
  }
 
105
 
 
106
  /** Deletes all item sets that don't have minimum support.
 
107
   * @return the reduced set of item sets
 
108
   * @param maxSupport the maximum support
 
109
   * @param itemSets the set of item sets to be pruned
 
110
   * @param minSupport the minimum number of transactions to be covered
 
111
   */
 
112
  public static FastVector deleteItemSets(FastVector itemSets, 
 
113
                                          int minSupport,
 
114
                                          int maxSupport) {
 
115
 
 
116
    FastVector newVector = new FastVector(itemSets.size());
 
117
 
 
118
    for (int i = 0; i < itemSets.size(); i++) {
 
119
      ItemSet current = (ItemSet)itemSets.elementAt(i);
 
120
      if ((current.m_counter >= minSupport) 
 
121
          && (current.m_counter <= maxSupport))
 
122
        newVector.addElement(current);
 
123
    }
 
124
    return newVector;
 
125
  }
 
126
 
 
127
  /**
 
128
   * Tests if two item sets are equal.
 
129
   *
 
130
   * @param itemSet another item set
 
131
   * @return true if this item set contains the same items as the given one
 
132
   */
 
133
  public boolean equals(Object itemSet) {
 
134
 
 
135
    if ((itemSet == null) || !(itemSet.getClass().equals(this.getClass()))) {
 
136
      return false;
 
137
    }
 
138
    if (m_items.length != ((ItemSet)itemSet).m_items.length)
 
139
      return false;
 
140
    for (int i = 0; i < m_items.length; i++)
 
141
      if (m_items[i] != ((ItemSet)itemSet).m_items[i])
 
142
        return false;
 
143
    return true;
 
144
  }
 
145
 
 
146
  /**
 
147
   * Return a hashtable filled with the given item sets.
 
148
   *
 
149
   * @param itemSets the set of item sets to be used for filling the hash table
 
150
   * @param initialSize the initial size of the hashtable
 
151
   * @return the generated hashtable
 
152
   */
 
153
  public static Hashtable getHashtable(FastVector itemSets, int initialSize) {
 
154
 
 
155
    Hashtable hashtable = new Hashtable(initialSize);
 
156
 
 
157
    for (int i = 0; i < itemSets.size(); i++) {
 
158
      ItemSet current = (ItemSet)itemSets.elementAt(i);
 
159
      hashtable.put(current, new Integer(current.m_counter));
 
160
    }
 
161
    return hashtable;
 
162
  }
 
163
 
 
164
  /**
 
165
   * Produces a hash code for a item set.
 
166
   *
 
167
   * @return a hash code for a set of items
 
168
   */
 
169
  public int hashCode() {
 
170
 
 
171
    long result = 0;
 
172
 
 
173
    for (int i = m_items.length-1; i >= 0; i--)
 
174
      result += (i * m_items[i]);
 
175
    return (int)result;
 
176
  }
 
177
 
 
178
  /** Merges all item sets in the set of (k-1)-item sets
 
179
   * to create the (k)-item sets and updates the counters.
 
180
   * @return the generated (k)-item sets
 
181
   * @param totalTrans thetotal number of transactions
 
182
   * @param itemSets the set of (k-1)-item sets
 
183
   * @param size the value of (k-1)
 
184
   */
 
185
  public static FastVector mergeAllItemSets(FastVector itemSets, int size, 
 
186
                                            int totalTrans) {
 
187
 
 
188
    FastVector newVector = new FastVector();
 
189
    ItemSet result;
 
190
    int numFound, k;
 
191
 
 
192
    for (int i = 0; i < itemSets.size(); i++) {
 
193
      ItemSet first = (ItemSet)itemSets.elementAt(i);
 
194
    out:
 
195
      for (int j = i+1; j < itemSets.size(); j++) {
 
196
        ItemSet second = (ItemSet)itemSets.elementAt(j);
 
197
        result = new ItemSet(totalTrans);
 
198
        result.m_items = new int[first.m_items.length];
 
199
        
 
200
        // Find and copy common prefix of size 'size'
 
201
        numFound = 0;
 
202
        k = 0;
 
203
        while (numFound < size) {
 
204
          if (first.m_items[k] == second.m_items[k]) {
 
205
            if (first.m_items[k] != -1) 
 
206
              numFound++;
 
207
            result.m_items[k] = first.m_items[k];
 
208
          } else 
 
209
            break out;
 
210
          k++;
 
211
        }
 
212
        
 
213
        // Check difference
 
214
        while (k < first.m_items.length) {
 
215
          if ((first.m_items[k] != -1) && (second.m_items[k] != -1))
 
216
            break;
 
217
          else {
 
218
            if (first.m_items[k] != -1)
 
219
              result.m_items[k] = first.m_items[k];
 
220
            else
 
221
              result.m_items[k] = second.m_items[k];
 
222
          }
 
223
          k++;
 
224
        }
 
225
        if (k == first.m_items.length) {
 
226
          result.m_counter = 0;
 
227
         
 
228
          newVector.addElement(result);
 
229
        }
 
230
      }
 
231
    }
 
232
    return newVector;
 
233
  }
 
234
 
 
235
  /**
 
236
   * Prunes a set of (k)-item sets using the given (k-1)-item sets.
 
237
   *
 
238
   * @param toPrune the set of (k)-item sets to be pruned
 
239
   * @param kMinusOne the (k-1)-item sets to be used for pruning
 
240
   * @return the pruned set of item sets
 
241
   */
 
242
  public static FastVector pruneItemSets(FastVector toPrune, Hashtable kMinusOne) {
 
243
 
 
244
    FastVector newVector = new FastVector(toPrune.size());
 
245
    int help, j;
 
246
 
 
247
    for (int i = 0; i < toPrune.size(); i++) {
 
248
      ItemSet current = (ItemSet)toPrune.elementAt(i);
 
249
      for (j = 0; j < current.m_items.length; j++)
 
250
        if (current.m_items[j] != -1) {
 
251
          help = current.m_items[j];
 
252
          current.m_items[j] = -1;
 
253
          if (kMinusOne.get(current) == null) {
 
254
            current.m_items[j] = help;
 
255
            break;
 
256
          } else{ 
 
257
            current.m_items[j] = help;
 
258
          }
 
259
        }
 
260
      if (j == current.m_items.length) 
 
261
        newVector.addElement(current);
 
262
    }
 
263
    return newVector;
 
264
  }
 
265
 
 
266
  /**
 
267
   * Prunes a set of rules.
 
268
   *
 
269
   * @param rules a two-dimensional array of lists of item sets. The first list
 
270
   * of item sets contains the premises, the second one the consequences.
 
271
   * @param minConfidence the minimum confidence the rules have to have
 
272
   */
 
273
  public static void pruneRules(FastVector[] rules, double minConfidence) {
 
274
 
 
275
    FastVector newPremises = new FastVector(rules[0].size()),
 
276
      newConsequences = new FastVector(rules[1].size()),
 
277
      newConf = new FastVector(rules[2].size());
 
278
 
 
279
    for (int i = 0; i < rules[0].size(); i++) 
 
280
      if (!(((Double)rules[2].elementAt(i)).doubleValue() <
 
281
            minConfidence)) {
 
282
        newPremises.addElement(rules[0].elementAt(i));
 
283
        newConsequences.addElement(rules[1].elementAt(i));
 
284
        newConf.addElement(rules[2].elementAt(i));
 
285
      }
 
286
    rules[0] = newPremises;
 
287
    rules[1] = newConsequences;
 
288
    rules[2] = newConf;
 
289
  }
 
290
 
 
291
  /**
 
292
   * Converts the header info of the given set of instances into a set 
 
293
   * of item sets (singletons). The ordering of values in the header file 
 
294
   * determines the lexicographic order.
 
295
   *
 
296
   * @param instances the set of instances whose header info is to be used
 
297
   * @return a set of item sets, each containing a single item
 
298
   * @exception Exception if singletons can't be generated successfully
 
299
   */
 
300
  public static FastVector singletons(Instances instances) throws Exception {
 
301
 
 
302
    FastVector setOfItemSets = new FastVector();
 
303
    ItemSet current;
 
304
 
 
305
    for (int i = 0; i < instances.numAttributes(); i++) {
 
306
      if (instances.attribute(i).isNumeric())
 
307
        throw new Exception("Can't handle numeric attributes!");
 
308
      for (int j = 0; j < instances.attribute(i).numValues(); j++) {
 
309
        current = new ItemSet(instances.numInstances());
 
310
        current.m_items = new int[instances.numAttributes()];
 
311
        for (int k = 0; k < instances.numAttributes(); k++)
 
312
          current.m_items[k] = -1;
 
313
        current.m_items[i] = j;
 
314
        
 
315
        setOfItemSets.addElement(current);
 
316
      }
 
317
    }
 
318
    return setOfItemSets;
 
319
  }
 
320
 
 
321
  /**
 
322
   * Outputs the support for an item set.
 
323
   *
 
324
   * @return the support
 
325
   */
 
326
  public int support() {
 
327
 
 
328
    return m_counter;
 
329
  }
 
330
 
 
331
  /**
 
332
   * Returns the contents of an item set as a string.
 
333
   *
 
334
   * @param instances contains the relevant header information
 
335
   * @return string describing the item set
 
336
   */
 
337
  public String toString(Instances instances) {
 
338
 
 
339
    StringBuffer text = new StringBuffer();
 
340
 
 
341
    for (int i = 0; i < instances.numAttributes(); i++)
 
342
      if (m_items[i] != -1) {
 
343
        text.append(instances.attribute(i).name()+'=');
 
344
        text.append(instances.attribute(i).value(m_items[i])+' ');
 
345
      }
 
346
    text.append(m_counter);
 
347
    return text.toString();
 
348
  }
 
349
 
 
350
  /**
 
351
   * Updates counter of item set with respect to given transaction.
 
352
   *
 
353
   * @param instance the instance to be used for ubdating the counter
 
354
   */
 
355
  public void upDateCounter(Instance instance) {
 
356
 
 
357
    if (containedBy(instance))
 
358
      m_counter++;
 
359
  }
 
360
 
 
361
  /**
 
362
   * Updates counters for a set of item sets and a set of instances.
 
363
   *
 
364
   * @param itemSets the set of item sets which are to be updated
 
365
   * @param instances the instances to be used for updating the counters
 
366
   */
 
367
  public static void upDateCounters(FastVector itemSets, Instances instances) {
 
368
 
 
369
    for (int i = 0; i < instances.numInstances(); i++) {
 
370
      Enumeration enu = itemSets.elements();
 
371
      while (enu.hasMoreElements()) 
 
372
        ((ItemSet)enu.nextElement()).upDateCounter(instances.instance(i));
 
373
    }
 
374
  }
 
375
 
 
376
  /** Gets the counter
 
377
   * @return the counter
 
378
   */  
 
379
  public int counter(){
 
380
      
 
381
      return m_counter;
 
382
  }
 
383
  
 
384
  /** Gest the item set as an int array
 
385
   * @return int array represneting an item set
 
386
   */  
 
387
  public int[] items(){
 
388
      
 
389
      return m_items;
 
390
  }
 
391
  
 
392
  /** Gest the index of the value of the specified attribute
 
393
   * @param k the attribute index
 
394
   * @return the index of the attribute value
 
395
   */  
 
396
  public int itemAt(int k){
 
397
      
 
398
      return m_items[k];
 
399
  }
 
400
  
 
401
  /** Sets the counter
 
402
   * @param count the counter
 
403
   */  
 
404
  public void setCounter(int count){
 
405
      
 
406
      m_counter = count;
 
407
  }
 
408
  
 
409
  /** Sets an item sets
 
410
   * @param items an int array representing an item set
 
411
   */  
 
412
  public void setItem(int[] items){
 
413
      
 
414
      m_items = items;
 
415
  }
 
416
  
 
417
  /** Sets the index of an attribute value
 
418
   * @param value the inex of the attribute value
 
419
   * @param k the index of the attribute
 
420
   */  
 
421
  public void setItemAt(int value, int k){
 
422
      
 
423
      m_items[k] = value;
 
424
  }
 
425
}