← Back to branch summary

~ubuntu-branches/ubuntu/vivid/elki/vivid

« back to all changes in this revision

Viewing changes to src/de/lmu/ifi/dbs/elki/algorithm/clustering/DBSCAN.java

  • Committer: Package Import Robot
  • Author(s): Erich Schubert
  • Date: 2012-12-14 20:45:15 UTC
  • mfrom: (1.1.6)
  • Revision ID: package-import@ubuntu.com-20121214204515-4m0d0er9ivtu5w9d
Tags: 0.5.5-1
New upstream release: 0.5.5 interim release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/de/lmu/ifi/dbs/elki/algorithm/clustering/DBSCAN.java
34
34
import de.lmu.ifi.dbs.elki.data.type.TypeInformation;
35
35
import de.lmu.ifi.dbs.elki.data.type.TypeUtil;
36
36
import de.lmu.ifi.dbs.elki.database.QueryUtil;
37
 
import de.lmu.ifi.dbs.elki.database.ids.DBID;
38
37
import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
 
38
import de.lmu.ifi.dbs.elki.database.ids.DBIDMIter;
 
39
import de.lmu.ifi.dbs.elki.database.ids.DBIDRef;
39
40
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
 
41
import de.lmu.ifi.dbs.elki.database.ids.HashSetModifiableDBIDs;
40
42
import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs;
41
 
import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair;
42
43
import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery;
43
44
import de.lmu.ifi.dbs.elki.database.relation.Relation;
44
45
import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction;
 
46
import de.lmu.ifi.dbs.elki.distance.distanceresultlist.DistanceDBIDResult;
45
47
import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
46
48
import de.lmu.ifi.dbs.elki.logging.Logging;
47
49
import de.lmu.ifi.dbs.elki.logging.progress.FiniteProgress;
77
79
  /**
78
80
   * The logger for this class.
79
81
   */
80
 
  private static final Logging logger = Logging.getLogger(DBSCAN.class);
 
82
  private static final Logging LOG = Logging.getLogger(DBSCAN.class);
81
83
 
82
84
  /**
83
85
   * Parameter to specify the maximum radius of the neighborhood to be
84
86
   * considered, must be suitable to the distance function specified.
85
87
   */
86
 
  public static final OptionID EPSILON_ID = OptionID.getOrCreateOptionID("dbscan.epsilon", "The maximum radius of the neighborhood to be considered.");
 
88
  public static final OptionID EPSILON_ID = new OptionID("dbscan.epsilon", "The maximum radius of the neighborhood to be considered.");
87
89
 
88
90
  /**
89
91
   * Holds the value of {@link #EPSILON_ID}.
94
96
   * Parameter to specify the threshold for minimum number of points in the
95
97
   * epsilon-neighborhood of a point, must be an integer greater than 0.
96
98
   */
97
 
  public static final OptionID MINPTS_ID = OptionID.getOrCreateOptionID("dbscan.minpts", "Threshold for minimum number of points in the epsilon-neighborhood of a point.");
 
99
  public static final OptionID MINPTS_ID = new OptionID("dbscan.minpts", "Threshold for minimum number of points in the epsilon-neighborhood of a point.");
98
100
 
99
101
  /**
100
102
   * Holds the value of {@link #MINPTS_ID}.
136
138
    RangeQuery<O, D> rangeQuery = QueryUtil.getRangeQuery(relation, getDistanceFunction());
137
139
    final int size = relation.size();
138
140
 
139
 
    FiniteProgress objprog = logger.isVerbose() ? new FiniteProgress("Processing objects", size, logger) : null;
140
 
    IndefiniteProgress clusprog = logger.isVerbose() ? new IndefiniteProgress("Number of clusters", logger) : null;
 
141
    FiniteProgress objprog = LOG.isVerbose() ? new FiniteProgress("Processing objects", size, LOG) : null;
 
142
    IndefiniteProgress clusprog = LOG.isVerbose() ? new IndefiniteProgress("Number of clusters", LOG) : null;
141
143
    resultList = new ArrayList<ModifiableDBIDs>();
142
144
    noise = DBIDUtil.newHashSet();
143
145
    processedIDs = DBIDUtil.newHashSet(size);
144
 
    if(size >= minpts) {
 
146
    if(size < minpts) {
 
147
      // The can't be any clusters
 
148
      noise.addDBIDs(relation.getDBIDs());
 
149
      objprog.setProcessed(noise.size(), LOG);
 
150
    }
 
151
    else {
145
152
      for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
146
153
        if(!processedIDs.contains(iditer)) {
147
 
          expandCluster(relation, rangeQuery, iditer.getDBID(), objprog, clusprog);
 
154
          expandCluster(relation, rangeQuery, iditer, objprog, clusprog);
148
155
        }
149
156
        if(objprog != null && clusprog != null) {
150
 
          objprog.setProcessed(processedIDs.size(), logger);
151
 
          clusprog.setProcessed(resultList.size(), logger);
 
157
          objprog.setProcessed(processedIDs.size(), LOG);
 
158
          clusprog.setProcessed(resultList.size(), LOG);
152
159
        }
153
160
        if(processedIDs.size() == size) {
154
161
          break;
155
162
        }
156
163
      }
157
164
    }
158
 
    else {
159
 
      for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
160
 
        noise.add(iditer);
161
 
        if(objprog != null && clusprog != null) {
162
 
          objprog.setProcessed(noise.size(), logger);
163
 
          clusprog.setProcessed(resultList.size(), logger);
164
 
        }
165
 
      }
166
 
    }
167
165
    // Finish progress logging
168
166
    if(objprog != null) {
169
 
      objprog.ensureCompleted(logger);
 
167
      objprog.ensureCompleted(LOG);
170
168
    }
171
169
    if(clusprog != null) {
172
 
      clusprog.setCompleted(logger);
 
170
      clusprog.setCompleted(LOG);
173
171
    }
174
172
 
175
173
    Clustering<Model> result = new Clustering<Model>("DBSCAN Clustering", "dbscan-clustering");
194
192
   * @param startObjectID potential seed of a new potential cluster
195
193
   * @param objprog the progress object for logging the current status
196
194
   */
197
 
  protected void expandCluster(Relation<O> relation, RangeQuery<O, D> rangeQuery, DBID startObjectID, FiniteProgress objprog, IndefiniteProgress clusprog) {
198
 
    List<DistanceResultPair<D>> seeds = rangeQuery.getRangeForDBID(startObjectID, epsilon);
 
195
  protected void expandCluster(Relation<O> relation, RangeQuery<O, D> rangeQuery, DBIDRef startObjectID, FiniteProgress objprog, IndefiniteProgress clusprog) {
 
196
    DistanceDBIDResult<D> neighbors = rangeQuery.getRangeForDBID(startObjectID, epsilon);
199
197
 
200
198
    // startObject is no core-object
201
 
    if(seeds.size() < minpts) {
 
199
    if(neighbors.size() < minpts) {
202
200
      noise.add(startObjectID);
203
201
      processedIDs.add(startObjectID);
204
202
      if(objprog != null && clusprog != null) {
205
 
        objprog.setProcessed(processedIDs.size(), logger);
206
 
        clusprog.setProcessed(resultList.size(), logger);
 
203
        objprog.setProcessed(processedIDs.size(), LOG);
 
204
        clusprog.setProcessed(resultList.size(), LOG);
207
205
      }
208
206
      return;
209
207
    }
210
208
 
211
209
    // try to expand the cluster
 
210
    HashSetModifiableDBIDs seeds = DBIDUtil.newHashSet();
212
211
    ModifiableDBIDs currentCluster = DBIDUtil.newArray();
213
 
    for(DistanceResultPair<D> seed : seeds) {
 
212
    for(DBIDIter seed = neighbors.iter(); seed.valid(); seed.advance()) {
214
213
      if(!processedIDs.contains(seed)) {
215
214
        currentCluster.add(seed);
216
215
        processedIDs.add(seed);
 
216
        seeds.add(seed);
217
217
      }
218
218
      else if(noise.contains(seed)) {
219
219
        currentCluster.add(seed);
220
220
        noise.remove(seed);
221
221
      }
222
222
    }
223
 
    seeds.remove(0);
 
223
    seeds.remove(startObjectID);
224
224
 
225
225
    while(seeds.size() > 0) {
226
 
      DistanceResultPair<D> o = seeds.remove(0);
227
 
      List<DistanceResultPair<D>> neighborhood = rangeQuery.getRangeForDBID(o, epsilon);
 
226
      DBIDMIter o = seeds.iter();
 
227
      DistanceDBIDResult<D> neighborhood = rangeQuery.getRangeForDBID(o, epsilon);
 
228
      o.remove();
228
229
 
229
230
      if(neighborhood.size() >= minpts) {
230
 
        for(DistanceResultPair<D> neighbor : neighborhood) {
 
231
        for(DBIDIter neighbor = neighborhood.iter(); neighbor.valid(); neighbor.advance()) {
231
232
          boolean inNoise = noise.contains(neighbor);
232
233
          boolean unclassified = !processedIDs.contains(neighbor);
233
234
          if(inNoise || unclassified) {
248
249
      }
249
250
 
250
251
      if(objprog != null && clusprog != null) {
251
 
        objprog.setProcessed(processedIDs.size(), logger);
 
252
        objprog.setProcessed(processedIDs.size(), LOG);
252
253
        int numClusters = currentCluster.size() > minpts ? resultList.size() + 1 : resultList.size();
253
 
        clusprog.setProcessed(numClusters, logger);
 
254
        clusprog.setProcessed(numClusters, LOG);
254
255
      }
255
256
    }
256
257
    if(currentCluster.size() >= minpts) {
270
271
 
271
272
  @Override
272
273
  protected Logging getLogger() {
273
 
    return logger;
 
274
    return LOG;
274
275
  }
275
276
 
276
277
  /**