ClusterManager.java revision c7c9cf164cc58d03156a53be35e58c3b75871a23
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 = 50; // meter 44 45 private static long CONSOLIDATE_INTERVAL = 21600000; // 46 47 private static long LOCATION_CLUSTER_THRESHOLD = 180000; // in milliseconds 48 49 private static long SEMANTIC_CLUSTER_THRESHOLD = 1800000; // in milliseconds 50 51 private static String UNKNOWN_LOCATION = "Unknown Location"; 52 53 private static String HOME = "Home"; 54 55 private static String OFFICE = "Office"; 56 57 private Location mLastLocation = null; 58 59 private long mTimeRef = 0; 60 61 private long mSemanticClusterCount = 0; 62 63 private ArrayList<LocationCluster> mLocClusters = new ArrayList<LocationCluster>(); 64 65 private ArrayList<SemanticCluster> mSemanticClusters = new ArrayList<SemanticCluster>(); 66 67 private AggregatorRecordStorage mStorage; 68 69 private static String SEMANTIC_TABLE = "SemanticTable"; 70 71 private static String SEMANTIC_ID = "ID"; 72 73 private static String SEMANTIC_LONGITUDE = "Longitude"; 74 75 private static String SEMANTIC_LATITUDE = "Latitude"; 76 77 private static String[] SEMANTIC_COLUMNS = 78 new String[]{ SEMANTIC_ID, SEMANTIC_LONGITUDE, SEMANTIC_LATITUDE}; 79 80 public ClusterManager(Context context) { 81 mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS); 82 83 loadSemanticClusters(); 84 } 85 86 public void addSample(Location location) { 87 float bestClusterDistance = Float.MAX_VALUE; 88 int bestClusterIndex = -1; 89 long lastDuration; 90 long currentTime = location.getTime(); 91 92 if (mLastLocation != null) { 93 // get the duration spent in the last location 94 long duration = location.getTime() - mLastLocation.getTime(); 95 Log.v(TAG, "sample duration: " + duration + 96 ", number of clusters: " + mLocClusters.size()); 97 98 // add the last location to cluster. 99 // first find the cluster it belongs to. 100 for (int i = 0; i < mLocClusters.size(); ++i) { 101 float distance = mLocClusters.get(i).distanceToCenter(mLastLocation); 102 Log.v(TAG, "clulster " + i + " is within " + distance + " meters"); 103 if (distance < bestClusterDistance) { 104 bestClusterDistance = distance; 105 bestClusterIndex = i; 106 } 107 } 108 109 // add the location to the selected cluster 110 if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) { 111 Log.v(TAG, "add sample to cluster: " + bestClusterIndex + ",( " + 112 location.getLongitude() + ", " + location.getLatitude() + ")"); 113 mLocClusters.get(bestClusterIndex).addSample(mLastLocation, duration); 114 } else { 115 // if it is far away from all existing clusters, create a new cluster. 116 LocationCluster cluster = 117 new LocationCluster(mLastLocation, duration, CONSOLIDATE_INTERVAL); 118 // move the center of the new cluster if its covering region overlaps 119 // with an existing cluster. 120 if (bestClusterDistance < 2 * LOCATION_CLUSTER_RADIUS) { 121 Log.e(TAG, "move away activated"); 122 cluster.moveAwayCluster(mLocClusters.get(bestClusterIndex), 123 ((float) 2 * LOCATION_CLUSTER_RADIUS)); 124 } 125 mLocClusters.add(cluster); 126 } 127 } else { 128 mTimeRef = currentTime; 129 } 130 131 long collectDuration = currentTime - mTimeRef; 132 Log.e(TAG, "collect duration: " + collectDuration); 133 if (collectDuration > CONSOLIDATE_INTERVAL) { 134 // TODO : conslidation takes time. move this to a separate thread later. 135 consolidateClusters(collectDuration); 136 mTimeRef = currentTime; 137 } 138 139 /* 140 // TODO: this could be removed 141 Log.i(TAG, "location : " + location.getLongitude() + ", " + location.getLatitude()); 142 if (mLastLocation != null) { 143 Log.i(TAG, "mLastLocation: " + mLastLocation.getLongitude() + ", " + 144 mLastLocation.getLatitude()); 145 } // end of deletion 146 */ 147 148 mLastLocation = location; 149 } 150 151 private void consolidateClusters(long duration) { 152 LocationCluster cluster; 153 154 for (int i = mLocClusters.size() - 1; i >= 0; --i) { 155 cluster = mLocClusters.get(i); 156 cluster.consolidate(duration); 157 158 // TODO: currently set threshold to 1 sec so almost none of the location 159 // clusters will be removed. 160 if (!cluster.passThreshold(LOCATION_CLUSTER_THRESHOLD)) { 161 mLocClusters.remove(cluster); 162 } 163 } 164 165 // merge clusters whose regions are overlapped. note that after merge 166 // cluster center changes but cluster size remains unchanged. 167 for (int i = mLocClusters.size() - 1; i >= 0; --i) { 168 cluster = mLocClusters.get(i); 169 for (int j = i - 1; j >= 0; --j) { 170 float distance = mLocClusters.get(j).distanceToCluster(cluster); 171 if (distance < LOCATION_CLUSTER_RADIUS) { 172 mLocClusters.get(j).absorbCluster(cluster); 173 mLocClusters.remove(cluster); 174 } 175 } 176 } 177 178 updateSemanticClusters(); 179 180 saveSemanticClusters(); 181 } 182 183 private void loadSemanticClusters() { 184 List<Map<String, String> > allData = mStorage.getAllData(); 185 186 mSemanticClusters.clear(); 187 for (Map<String, String> map : allData) { 188 String semanticId = map.get(SEMANTIC_ID); 189 double longitude = Double.valueOf(map.get(SEMANTIC_LONGITUDE)); 190 double latitude = Double.valueOf(map.get(SEMANTIC_LATITUDE)); 191 192 SemanticCluster cluster = new SemanticCluster( 193 semanticId, longitude, latitude, CONSOLIDATE_INTERVAL); 194 mSemanticClusters.add(cluster); 195 } 196 197 mSemanticClusterCount = mSemanticClusters.size(); 198 Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters."); 199 } 200 201 private void saveSemanticClusters() { 202 HashMap<String, String> rowFeatures = new HashMap<String, String>(); 203 Log.e(TAG, "save " + mSemanticClusters.size() + " semantic clusters."); 204 205 mStorage.removeAllData(); 206 for (SemanticCluster cluster : mSemanticClusters) { 207 rowFeatures.clear(); 208 rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId()); 209 210 rowFeatures.put(SEMANTIC_LONGITUDE, 211 String.valueOf(cluster.getCenterLongitude())); 212 rowFeatures.put(SEMANTIC_LATITUDE, 213 String.valueOf(cluster.getCenterLatitude())); 214 mStorage.addData(rowFeatures); 215 } 216 } 217 218 private void updateSemanticClusters() { 219 220 HashMap<String, ArrayList<BaseCluster> > semanticMap = 221 new HashMap<String, ArrayList<BaseCluster> >(); 222 for (SemanticCluster cluster : mSemanticClusters) { 223 String semanticId = cluster.getSemanticId(); 224 semanticMap.put(cluster.getSemanticId(), new ArrayList<BaseCluster>()); 225 semanticMap.get(semanticId).add(cluster); 226 } 227 228 // select candidate location clusters 229 ArrayList<LocationCluster> candidates = new ArrayList<LocationCluster>(); 230 for (LocationCluster cluster : mLocClusters) { 231 if (cluster.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) { 232 candidates.add(cluster); 233 } 234 } 235 236 // assign each candidate to a semantic cluster 237 for (LocationCluster candidate : candidates) { 238 if (candidate.hasSemanticId()) { 239 // candidate has been assigned to a semantic cluster 240 continue; 241 } 242 243 // find the closest semantic cluster 244 float bestClusterDistance = Float.MAX_VALUE; 245 SemanticCluster bestCluster = null; 246 for (SemanticCluster cluster : mSemanticClusters) { 247 float distance = cluster.distanceToCluster(candidate); 248 Log.e(TAG, "distance to semantic cluster: " + cluster.getSemanticId()); 249 250 if (distance < bestClusterDistance) { 251 bestClusterDistance = distance; 252 bestCluster = cluster; 253 } 254 } 255 256 // add the location to the selected cluster 257 SemanticCluster semanticCluster; 258 if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) { 259 // if it is far away from all existing clusters, create a new cluster. 260 bestCluster = new SemanticCluster(candidate, CONSOLIDATE_INTERVAL, 261 mSemanticClusterCount++); 262 String id = bestCluster.getSemanticId(); 263 semanticMap.put(id, new ArrayList<BaseCluster>()); 264 semanticMap.get(id).add(bestCluster); 265 } 266 String semanticId = bestCluster.getSemanticId(); 267 candidate.setSemanticId(semanticId); 268 semanticMap.get(semanticId).add(candidate); 269 } 270 candidates.clear(); 271 Log.e(TAG, "number of semantic clusters: " + semanticMap.size()); 272 273 // use candidates semantic cluster 274 mSemanticClusters.clear(); 275 for (ArrayList<BaseCluster> clusterList : semanticMap.values()) { 276 SemanticCluster semanticCluster = (SemanticCluster) clusterList.get(0); 277 278 Log.e(TAG, "id: " + semanticCluster.getSemanticId() + ", list size: " + 279 clusterList.size()); 280 281 if (clusterList.size() > 1) { 282 // cluster with no new candidate 283 semanticCluster.setCluster(clusterList.get(1)); 284 for (int i = 2; i < clusterList.size(); i++) { 285 semanticCluster.absorbCluster(clusterList.get(i)); 286 } 287 } 288 mSemanticClusters.add(semanticCluster); 289 } 290 } 291 292 public String getSemanticLocation() { 293 String label = LocationStatsAggregator.UNKNOWN_LOCATION; 294 295 // instead of using the last location, try acquiring the latest location. 296 if (mLastLocation != null) { 297 // TODO: use fast neatest neighbor search speed up location search 298 for (SemanticCluster cluster: mSemanticClusters) { 299 if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) { 300 return cluster.getSemanticId(); 301 } 302 } 303 } 304 return label; 305 } 306} 307