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 = 25; // meter 42 43 private static float SEMANTIC_CLUSTER_RADIUS = 75; // meter 44 45 // Consoliate location clusters (and check for new semantic clusters) 46 // every 10 minutes (600 seconds). 47 private static final long CONSOLIDATE_INTERVAL = 600; 48 49 // A location cluster can be labeled as a semantic cluster if it has been 50 // stayed for at least 10 minutes (600 seconds) within a day. 51 private static final long SEMANTIC_CLUSTER_THRESHOLD = 600; // seconds 52 53 // Reset location cluters every 24 hours (86400 seconds). 54 private static final long LOCATION_REFRESH_PERIOD = 86400; // seconds 55 56 private static String UNKNOWN_LOCATION = "Unknown Location"; 57 58 private Location mLastLocation = null; 59 60 private long mClusterDuration; 61 62 private long mConsolidateRef = 0; 63 64 private long mRefreshRef = 0; 65 66 private long mSemanticClusterCount = 0; 67 68 private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>(); 69 70 private ArrayList<BaseCluster> mSemanticClusters = new ArrayList<BaseCluster>(); 71 72 private AggregatorRecordStorage mStorage; 73 74 private static String SEMANTIC_TABLE = "SemanticTable"; 75 76 private static String SEMANTIC_ID = "ID"; 77 78 private static final String SEMANTIC_LONGITUDE = "Longitude"; 79 80 private static final String SEMANTIC_LATITUDE = "Latitude"; 81 82 private static final String SEMANTIC_DURATION = "Duration"; 83 84 private static final String[] SEMANTIC_COLUMNS = 85 new String[]{ SEMANTIC_ID, 86 SEMANTIC_LONGITUDE, 87 SEMANTIC_LATITUDE, 88 SEMANTIC_DURATION, 89 TimeStatsAggregator.WEEKEND, 90 TimeStatsAggregator.WEEKDAY, 91 TimeStatsAggregator.MORNING, 92 TimeStatsAggregator.NOON, 93 TimeStatsAggregator.AFTERNOON, 94 TimeStatsAggregator.EVENING, 95 TimeStatsAggregator.NIGHT, 96 TimeStatsAggregator.LATENIGHT }; 97 98 private static final int mFeatureValueStart = 4; 99 private static final int mFeatureValueEnd = 11; 100 101 public ClusterManager(Context context) { 102 mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS); 103 104 loadSemanticClusters(); 105 } 106 107 public void addSample(Location location) { 108 float bestClusterDistance = Float.MAX_VALUE; 109 int bestClusterIndex = -1; 110 long lastDuration; 111 long currentTime = location.getTime() / 1000; // measure time in seconds 112 113 if (mLastLocation != null) { 114 if (location.getTime() == mLastLocation.getTime()) { 115 return; 116 } 117 // get the duration spent in the last location 118 long duration = (location.getTime() - mLastLocation.getTime()) / 1000; 119 mClusterDuration += duration; 120 121 Log.v(TAG, "sample duration: " + duration + 122 ", number of clusters: " + mLocationClusters.size()); 123 124 synchronized (mLocationClusters) { 125 // add the last location to cluster. 126 // first find the cluster it belongs to. 127 for (int i = 0; i < mLocationClusters.size(); ++i) { 128 float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation); 129 Log.v(TAG, "clulster " + i + " is within " + distance + " meters"); 130 if (distance < bestClusterDistance) { 131 bestClusterDistance = distance; 132 bestClusterIndex = i; 133 } 134 } 135 136 // add the location to the selected cluster 137 if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) { 138 mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration); 139 } else { 140 // if it is far away from all existing clusters, create a new cluster. 141 LocationCluster cluster = new LocationCluster(mLastLocation, duration); 142 mLocationClusters.add(cluster); 143 } 144 } 145 } else { 146 mConsolidateRef = currentTime; 147 mRefreshRef = currentTime; 148 149 if (mLocationClusters.isEmpty()) { 150 mClusterDuration = 0; 151 } 152 } 153 154 long collectDuration = currentTime - mConsolidateRef; 155 Log.v(TAG, "collect duration: " + collectDuration); 156 if (collectDuration > CONSOLIDATE_INTERVAL) { 157 // TODO : conslidation takes time. move this to a separate thread later. 158 consolidateClusters(); 159 mConsolidateRef = currentTime; 160 161 long refreshDuration = currentTime - mRefreshRef; 162 Log.v(TAG, "refresh duration: " + refreshDuration); 163 if (refreshDuration > LOCATION_REFRESH_PERIOD) { 164 updateSemanticClusters(); 165 mRefreshRef = currentTime; 166 } 167 saveSemanticClusters(); 168 } 169 170 mLastLocation = location; 171 } 172 173 private void consolidateClusters() { 174 synchronized (mSemanticClusters) { 175 LocationCluster locationCluster; 176 for (int i = mLocationClusters.size() - 1; i >= 0; --i) { 177 locationCluster = mLocationClusters.get(i); 178 locationCluster.consolidate(); 179 } 180 181 // merge clusters whose regions are overlapped. note that after merge 182 // cluster center changes but cluster size remains unchanged. 183 for (int i = mLocationClusters.size() - 1; i >= 0; --i) { 184 locationCluster = mLocationClusters.get(i); 185 for (int j = i - 1; j >= 0; --j) { 186 float distance = 187 mLocationClusters.get(j).distanceToCluster(locationCluster); 188 if (distance < LOCATION_CLUSTER_RADIUS) { 189 mLocationClusters.get(j).absorbCluster(locationCluster); 190 mLocationClusters.remove(locationCluster); 191 } 192 } 193 } 194 Log.v(TAG, mLocationClusters.size() + " location clusters after consolidate"); 195 196 // assign each candidate to a semantic cluster and check if new semantic 197 // clusters are found 198 for (LocationCluster candidate : mLocationClusters) { 199 if (candidate.hasSemanticId() || 200 candidate.hasSemanticClusterId() || 201 !candidate.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) { 202 continue; 203 } 204 205 // find the closest semantic cluster 206 float bestClusterDistance = Float.MAX_VALUE; 207 String bestClusterId = "Unused Id"; 208 for (BaseCluster cluster : mSemanticClusters) { 209 float distance = cluster.distanceToCluster(candidate); 210 Log.v(TAG, distance + "distance to semantic cluster: " + 211 cluster.getSemanticId()); 212 213 if (distance < bestClusterDistance) { 214 bestClusterDistance = distance; 215 bestClusterId = cluster.getSemanticId(); 216 } 217 } 218 219 // if candidate doesn't belong to any semantic cluster, create a new 220 // semantic cluster 221 if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) { 222 candidate.generateSemanticId(mSemanticClusterCount++); 223 mSemanticClusters.add(candidate); 224 } else { 225 candidate.setSemanticClusterId(bestClusterId); 226 } 227 } 228 Log.v(TAG, mSemanticClusters.size() + " semantic clusters after consolidate"); 229 } 230 } 231 232 private void updateSemanticClusters() { 233 synchronized (mSemanticClusters) { 234 // create index to cluster map 235 HashMap<String, BaseCluster> semanticIdMap = 236 new HashMap<String, BaseCluster>(); 237 for (BaseCluster cluster : mSemanticClusters) { 238 // TODO: apply forgetting factor on existing semantic cluster stats, 239 // duration, histogram, etc. 240 cluster.forgetPastHistory(); 241 semanticIdMap.put(cluster.getSemanticId(), cluster); 242 } 243 244 // assign each candidate to a semantic cluster 245 for (LocationCluster cluster : mLocationClusters) { 246 if (cluster.hasSemanticClusterId()) { 247 BaseCluster semanticCluster = 248 semanticIdMap.get(cluster.getSemanticClusterId()); 249 semanticCluster.absorbCluster(cluster); 250 } 251 } 252 // reset location clusters. 253 mLocationClusters.clear(); 254 } 255 } 256 257 private void loadSemanticClusters() { 258 List<Map<String, String> > allData = mStorage.getAllData(); 259 HashMap<String, Long> histogram = new HashMap<String, Long>(); 260 261 synchronized (mSemanticClusters) { 262 mSemanticClusters.clear(); 263 for (Map<String, String> map : allData) { 264 String semanticId = map.get(SEMANTIC_ID); 265 double longitude = Double.valueOf(map.get(SEMANTIC_LONGITUDE)); 266 double latitude = Double.valueOf(map.get(SEMANTIC_LATITUDE)); 267 long duration = Long.valueOf(map.get(SEMANTIC_DURATION)); 268 BaseCluster cluster = 269 new BaseCluster(semanticId, longitude, latitude, duration); 270 271 histogram.clear(); 272 for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) { 273 String featureValue = SEMANTIC_COLUMNS[i]; 274 if (map.containsKey(featureValue)) { 275 histogram.put(featureValue, Long.valueOf(map.get(featureValue))); 276 } 277 } 278 cluster.setHistogram(histogram); 279 mSemanticClusters.add(cluster); 280 } 281 mSemanticClusterCount = mSemanticClusters.size(); 282 Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters."); 283 } 284 } 285 286 private void saveSemanticClusters() { 287 HashMap<String, String> rowFeatures = new HashMap<String, String>(); 288 289 mStorage.removeAllData(); 290 synchronized (mSemanticClusters) { 291 for (BaseCluster cluster : mSemanticClusters) { 292 rowFeatures.clear(); 293 rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId()); 294 295 rowFeatures.put(SEMANTIC_LONGITUDE, 296 String.valueOf(cluster.getCenterLongitude())); 297 rowFeatures.put(SEMANTIC_LATITUDE, 298 String.valueOf(cluster.getCenterLatitude())); 299 rowFeatures.put(SEMANTIC_DURATION, 300 String.valueOf(cluster.getDuration())); 301 302 HashMap<String, Long> histogram = cluster.getHistogram(); 303 for (Map.Entry<String, Long> entry : histogram.entrySet()) { 304 rowFeatures.put(entry.getKey(), String.valueOf(entry.getValue())); 305 } 306 mStorage.addData(rowFeatures); 307 Log.e(TAG, "saving semantic cluster: " + rowFeatures); 308 } 309 } 310 } 311 312 public String getSemanticLocation() { 313 String label = LocationStatsAggregator.UNKNOWN_LOCATION; 314 315 // instead of using the last location, try acquiring the latest location. 316 if (mLastLocation != null) { 317 // TODO: use fast neatest neighbor search speed up location search 318 synchronized (mSemanticClusters) { 319 for (BaseCluster cluster: mSemanticClusters) { 320 if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) { 321 return cluster.getSemanticId(); 322 } 323 } 324 } 325 } 326 return label; 327 } 328 329 public List<String> getClusterNames() { 330 ArrayList<String> clusters = new ArrayList<String>(); 331 synchronized (mSemanticClusters) { 332 for (BaseCluster cluster: mSemanticClusters) { 333 clusters.add(cluster.getSemanticId()); 334 } 335 } 336 return clusters; 337 } 338} 339