ClusterManager.java revision 78a66d98346a69f65e9d38bb0c96a5418c007197
1/* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.bordeaux.services; 18 19import android.content.Context; 20import android.location.Location; 21import android.text.format.Time; 22import android.util.Log; 23 24import java.util.ArrayList; 25import java.util.HashMap; 26import java.util.HashSet; 27import java.util.List; 28import java.util.Map; 29 30/** 31 * ClusterManager incrementally indentify representitve clusters from the input location 32 * stream. Clusters are updated online using leader based clustering algorithm. The input 33 * locations initially are kept by the clusters. Periodially, a cluster consolidating 34 * procedure is carried out to refine the cluster centers. After consolidation, the 35 * location data are released. 36 */ 37public class ClusterManager { 38 39 private static String TAG = "ClusterManager"; 40 41 private static float LOCATION_CLUSTER_RADIUS = 50; // meter 42 43 private static float SEMANTIC_CLUSTER_RADIUS = 100; // meter 44 45 // Consoliate location clusters (and check for new semantic clusters) 46 // every 30 minutes (1800 seconds). 47 private static final long CONSOLIDATE_INTERVAL = 1800; 48 49 // Prune away clusters that are stayed for less than 3 minutes (180 seconds) 50 private static long LOCATION_CLUSTER_THRESHOLD = 180; 51 52 // A location cluster can be labeled as a semantic cluster if it has been 53 // stayed for at least 10 minutes (600 seconds) within a day. 54 private static final long SEMANTIC_CLUSTER_THRESHOLD = 600; // seconds 55 56 // Reset location cluters every 6 hours (21600 seconds). 57 private static final long LOCATION_REFRESH_PERIOD = 21600; // seconds 58 59 private static String UNKNOWN_LOCATION = "Unknown Location"; 60 61 private static String HOME = "Home"; 62 63 private static String OFFICE = "Office"; 64 65 private Location mLastLocation = null; 66 67 private long mClusterDuration; 68 69 private long mTimeRef = 0; 70 71 private long mSemanticClusterCount = 0; 72 73 private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>(); 74 75 private ArrayList<SemanticCluster> mSemanticClusters = new ArrayList<SemanticCluster>(); 76 77 private AggregatorRecordStorage mStorage; 78 79 private static String SEMANTIC_TABLE = "SemanticTable"; 80 81 private static String SEMANTIC_ID = "ID"; 82 83 private static final String SEMANTIC_LONGITUDE = "Longitude"; 84 85 private static final String SEMANTIC_LATITUDE = "Latitude"; 86 87 private static final String[] SEMANTIC_COLUMNS = 88 new String[]{ SEMANTIC_ID, 89 SEMANTIC_LONGITUDE, 90 SEMANTIC_LATITUDE, 91 TimeStatsAggregator.WEEKEND, 92 TimeStatsAggregator.WEEKDAY, 93 TimeStatsAggregator.MORNING, 94 TimeStatsAggregator.NOON, 95 TimeStatsAggregator.AFTERNOON, 96 TimeStatsAggregator.EVENING, 97 TimeStatsAggregator.NIGHT, 98 TimeStatsAggregator.LATENIGHT }; 99 100 private static final int mFeatureValueStart = 3; 101 private static final int mFeatureValueEnd = 10; 102 103 public ClusterManager(Context context) { 104 mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS); 105 106 loadSemanticClusters(); 107 } 108 109 public void addSample(Location location) { 110 float bestClusterDistance = Float.MAX_VALUE; 111 int bestClusterIndex = -1; 112 long lastDuration; 113 long currentTime = location.getTime() / 1000; // measure time in seconds 114 115 if (mLastLocation != null) { 116 // get the duration spent in the last location 117 long duration = (location.getTime() - mLastLocation.getTime()) / 1000; 118 mClusterDuration += duration; 119 120 Log.v(TAG, "sample duration: " + duration + 121 ", number of clusters: " + mLocationClusters.size()); 122 123 // add the last location to cluster. 124 // first find the cluster it belongs to. 125 for (int i = 0; i < mLocationClusters.size(); ++i) { 126 float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation); 127 Log.v(TAG, "clulster " + i + " is within " + distance + " meters"); 128 if (distance < bestClusterDistance) { 129 bestClusterDistance = distance; 130 bestClusterIndex = i; 131 } 132 } 133 134 // add the location to the selected cluster 135 if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) { 136 mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration); 137 } else { 138 // if it is far away from all existing clusters, create a new cluster. 139 LocationCluster cluster = new LocationCluster(mLastLocation, duration); 140 // move the center of the new cluster if its covering region overlaps 141 // with an existing cluster. 142 if (bestClusterDistance < 2 * LOCATION_CLUSTER_RADIUS) { 143 Log.v(TAG, "move away activated"); 144 cluster.moveAwayCluster(mLocationClusters.get(bestClusterIndex), 145 ((float) 2 * LOCATION_CLUSTER_RADIUS)); 146 } 147 mLocationClusters.add(cluster); 148 } 149 } else { 150 mTimeRef = currentTime; 151 152 if (mLocationClusters.isEmpty()) { 153 mClusterDuration = 0; 154 } 155 } 156 157 long collectDuration = currentTime - mTimeRef; 158 Log.e(TAG, "collect duration: " + collectDuration); 159 if (collectDuration > CONSOLIDATE_INTERVAL) { 160 // TODO : conslidation takes time. move this to a separate thread later. 161 consolidateClusters(collectDuration); 162 mTimeRef = currentTime; 163 } 164 mLastLocation = location; 165 } 166 167 private void consolidateClusters(long duration) { 168 LocationCluster cluster; 169 for (int i = mLocationClusters.size() - 1; i >= 0; --i) { 170 cluster = mLocationClusters.get(i); 171 cluster.consolidate(duration); 172 173 // remove transit clusters 174 if (!cluster.passThreshold(LOCATION_CLUSTER_THRESHOLD)) { 175 mLocationClusters.remove(cluster); 176 } 177 } 178 179 // merge clusters whose regions are overlapped. note that after merge 180 // cluster center changes but cluster size remains unchanged. 181 for (int i = mLocationClusters.size() - 1; i >= 0; --i) { 182 cluster = mLocationClusters.get(i); 183 for (int j = i - 1; j >= 0; --j) { 184 float distance = mLocationClusters.get(j).distanceToCluster(cluster); 185 if (distance < LOCATION_CLUSTER_RADIUS) { 186 mLocationClusters.get(j).absorbCluster(cluster); 187 mLocationClusters.remove(cluster); 188 } 189 } 190 } 191 192 // check if new semantic clusters are found 193 if (findNewSemanticClusters() && 194 mClusterDuration < LOCATION_REFRESH_PERIOD) { 195 saveSemanticClusters(); 196 } 197 198 if (mClusterDuration > LOCATION_REFRESH_PERIOD) { 199 updateSemanticClusters(); 200 mClusterDuration = 0; 201 } 202 } 203 204 private boolean findNewSemanticClusters() { 205 // select candidate location clusters 206 ArrayList<LocationCluster> candidates = new ArrayList<LocationCluster>(); 207 for (LocationCluster cluster : mLocationClusters) { 208 if (!cluster.hasSemanticId() && 209 cluster.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) { 210 candidates.add(cluster); 211 } 212 } 213 214 // assign each candidate to a semantic cluster 215 boolean foundNewClusters = false; 216 for (LocationCluster candidate : candidates) { 217 // find the closest semantic cluster 218 float bestClusterDistance = Float.MAX_VALUE; 219 SemanticCluster bestCluster = null; 220 for (SemanticCluster cluster : mSemanticClusters) { 221 float distance = cluster.distanceToCluster(candidate); 222 Log.v(TAG, "distance to semantic cluster: " + cluster.getSemanticId()); 223 224 if (distance < bestClusterDistance) { 225 bestClusterDistance = distance; 226 bestCluster = cluster; 227 } 228 } 229 230 // if candidate doesn't belong to any semantic cluster, create a new 231 // semantic cluster 232 if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) { 233 // if it is far away from all existing clusters, create a new cluster. 234 bestCluster = new SemanticCluster(candidate, mSemanticClusterCount++); 235 String id = bestCluster.getSemanticId(); 236 237 // Add new semantic cluster to the list. 238 mSemanticClusters.add(bestCluster); 239 240 foundNewClusters = true; 241 } 242 candidate.setSemanticId(bestCluster.getSemanticId()); 243 } 244 candidates.clear(); 245 return foundNewClusters; 246 } 247 248 private void updateSemanticClusters() { 249 synchronized (mSemanticClusters) { 250 // initialize semanticMap 251 HashMap<String, ArrayList<BaseCluster> > semanticMap = 252 new HashMap<String, ArrayList<BaseCluster> >(); 253 for (SemanticCluster cluster : mSemanticClusters) { 254 String semanticId = cluster.getSemanticId(); 255 semanticMap.put(cluster.getSemanticId(), new ArrayList<BaseCluster>()); 256 semanticMap.get(semanticId).add(cluster); 257 } 258 259 // assign each candidate to a semantic cluster 260 for (LocationCluster cluster : mLocationClusters) { 261 if (cluster.hasSemanticId()) { 262 semanticMap.get(cluster.getSemanticId()).add(cluster); 263 } 264 } 265 // reset location clusters. 266 mLocationClusters.clear(); 267 mLastLocation = null; 268 mTimeRef = 0; 269 270 // use candidates semantic cluster 271 BaseCluster newCluster = new BaseCluster(); 272 for (ArrayList<BaseCluster> clusterList : semanticMap.values()) { 273 SemanticCluster semanticCluster = (SemanticCluster) clusterList.get(0); 274 275 if (clusterList.size() > 1) { 276 newCluster.setCluster(clusterList.get(1)); 277 for (int i = 2; i < clusterList.size(); i++) { 278 newCluster.absorbCluster(clusterList.get(i)); 279 } 280 semanticCluster.absorbCluster(newCluster); 281 } else { 282 // cluster with no new candidate 283 Log.e(TAG, "semantic cluster with no new location clusters: " + 284 semanticCluster); 285 } 286 } 287 } 288 saveSemanticClusters(); 289 } 290 291 private void loadSemanticClusters() { 292 List<Map<String, String> > allData = mStorage.getAllData(); 293 HashMap<String, Long> histogram = new HashMap<String, Long>(); 294 295 synchronized (mSemanticClusters) { 296 mSemanticClusters.clear(); 297 for (Map<String, String> map : allData) { 298 String semanticId = map.get(SEMANTIC_ID); 299 double longitude = Double.valueOf(map.get(SEMANTIC_LONGITUDE)); 300 double latitude = Double.valueOf(map.get(SEMANTIC_LATITUDE)); 301 SemanticCluster cluster = 302 new SemanticCluster(semanticId, longitude, latitude); 303 304 histogram.clear(); 305 for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) { 306 String featureValue = SEMANTIC_COLUMNS[i]; 307 if (map.containsKey(featureValue)) { 308 histogram.put(featureValue, Long.valueOf(map.get(featureValue))); 309 } 310 } 311 cluster.setHistogram(histogram); 312 mSemanticClusters.add(cluster); 313 } 314 mSemanticClusterCount = mSemanticClusters.size(); 315 Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters."); 316 } 317 } 318 319 private void saveSemanticClusters() { 320 HashMap<String, String> rowFeatures = new HashMap<String, String>(); 321 322 mStorage.removeAllData(); 323 synchronized (mSemanticClusters) { 324 for (SemanticCluster cluster : mSemanticClusters) { 325 rowFeatures.clear(); 326 rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId()); 327 328 rowFeatures.put(SEMANTIC_LONGITUDE, 329 String.valueOf(cluster.getCenterLongitude())); 330 rowFeatures.put(SEMANTIC_LATITUDE, 331 String.valueOf(cluster.getCenterLatitude())); 332 333 HashMap<String, Long> histogram = cluster.getHistogram(); 334 for (Map.Entry<String, Long> entry : histogram.entrySet()) { 335 rowFeatures.put(entry.getKey(), String.valueOf(entry.getValue())); 336 } 337 mStorage.addData(rowFeatures); 338 Log.e(TAG, "saving semantic cluster: " + rowFeatures); 339 } 340 } 341 } 342 343 public String getSemanticLocation() { 344 String label = LocationStatsAggregator.UNKNOWN_LOCATION; 345 346 // instead of using the last location, try acquiring the latest location. 347 if (mLastLocation != null) { 348 // TODO: use fast neatest neighbor search speed up location search 349 synchronized (mSemanticClusters) { 350 for (SemanticCluster cluster: mSemanticClusters) { 351 if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) { 352 return cluster.getSemanticId(); 353 } 354 } 355 } 356 } 357 return label; 358 } 359 360 public List<String> getClusterNames() { 361 ArrayList<String> clusters = new ArrayList<String>(); 362 synchronized (mSemanticClusters) { 363 for (SemanticCluster cluster: mSemanticClusters) { 364 clusters.add(cluster.getSemanticId()); 365 } 366 } 367 return clusters; 368 } 369} 370