LocationCluster.java revision 83954e853dc1e1a28b2c3efbe1585f188266df02
1f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin/* 2f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * Copyright (C) 2012 The Android Open Source Project 3f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * 4f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * Licensed under the Apache License, Version 2.0 (the "License"); 5f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * you may not use this file except in compliance with the License. 6f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * You may obtain a copy of the License at 7f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * 8f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * http://www.apache.org/licenses/LICENSE-2.0 9f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * 10f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * Unless required by applicable law or agreed to in writing, software 11f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * distributed under the License is distributed on an "AS IS" BASIS, 12f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * See the License for the specific language governing permissions and 14f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * limitations under the License. 15f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin */ 16f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linpackage android.bordeaux.services; 17f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 18f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.location.Location; 19f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.text.format.Time; 20f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.util.Log; 21f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 22f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport java.lang.Math; 23f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport java.util.ArrayList; 245d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport java.util.HashMap; 255d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport java.util.Map; 26f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 27f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linpublic class LocationCluster extends BaseCluster { 28f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin public static String TAG = "LocationCluster"; 29f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 30f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin private static double FORGETTING_FACTOR = 0.1; 31f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 32f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin private boolean mIsNewCluster; 33f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 34f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin private ArrayList<Location> mLocations = new ArrayList<Location>(); 355d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private HashMap<String, Long> mNewHistogram = new HashMap<String, Long>(); 36f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 375d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin // TODO: make it a singleton class 385d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin public LocationCluster(Location location, long duration, long avgInterval) { 39f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin super(location, avgInterval); 40f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mIsNewCluster = true; 415d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin addSample(location, duration); 42f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 43f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 445d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin public void addSample(Location location, long duration) { 455d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin updateTemporalHistogram(location.getTime(), duration); 465d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 475d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin // use time field to store duation of this location 485d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin // TODO: extend Location class with additional field for this. 495d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin location.setTime(duration); 50f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mLocations.add(location); 51f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 52f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 53f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin public void consolidate(long interval) { 54f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // TODO: add check on interval 55f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double[] newCenter = {0f, 0f, 0f}; 56f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin long newDuration = 0l; 57f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 58f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // update cluster center 59f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (Location location : mLocations) { 60f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double[] vector = getLocationVector(location); 6183954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin long duration = location.getTime(); // in seconds 62f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 63f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin newDuration += duration; 64f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 65f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin newCenter[i] += vector[i] * duration; 66f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 67f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 68f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 69f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin newCenter[i] /= newDuration; 70f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 71f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // remove location data 72f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mLocations.clear(); 73f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 74f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin if (mIsNewCluster) { 75f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 76f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mCenter[i] = newCenter[i]; 77f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 78f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mDuration = newDuration; 795d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mHistogram.clear(); 805d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mHistogram.putAll(mNewHistogram); 815d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mNewHistogram.clear(); 825d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 83f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mIsNewCluster = false; 84f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } else { 85f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // the new center is weight average over latest and existing centers. 86f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // fine tune the weight of new center 87f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double newWeight = ((double) newDuration) / (newDuration + mDuration); 88f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin newWeight *= FORGETTING_FACTOR; 89f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double currWeight = 1f - newWeight; 90f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double norm = 0; 91f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 92f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mCenter[i] = currWeight * mCenter[i] + newWeight * newCenter[i]; 93f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin norm += mCenter[i] * mCenter[i]; 94f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 95f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // normalize 96f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 97f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mCenter[i] /= norm; 98f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 995d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin consolidateHistogram(newWeight, newDuration); 1005d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mNewHistogram.clear(); 101f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 102f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 103f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 104f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin /* 105f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * if the new created cluster whose covered area overlaps with any existing 106f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * cluster move the center away from that cluster till there is no overlap. 107f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin */ 108f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin public void moveAwayCluster(LocationCluster cluster, float distance) { 109f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double[] vector = new double[3]; 110f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 111f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double dot = 0f; 112f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 113f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin dot += mCenter[i] * cluster.mCenter[i]; 114f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 115f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double norm = 0f; 116f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 117f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin vector[i] = mCenter[i] - dot * cluster.mCenter[i]; 118f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin norm += vector[i] * vector[i]; 119f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 120f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin norm = Math.sqrt(norm); 121f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 122f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double radian = distance / EARTH_RADIUS; 123f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (int i = 0; i < 3; ++i) { 124f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mCenter[i] = cluster.mCenter[i] * Math.cos(radian) + 125f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin (vector[i] / norm) * Math.sin(radian); 126f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 127f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 1285d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 1295d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private void updateTemporalHistogram(long time, long duration) { 1305d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin HashMap<String, String> timeFeatures = TimeStatsAggregator.getAllTimeFeatures(time); 1315d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 13283954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin String timeOfWeek = timeFeatures.get(TimeStatsAggregator.TIME_OF_WEEK); 13383954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin long totalDuration = (mNewHistogram.containsKey(timeOfWeek)) ? 13483954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin mNewHistogram.get(timeOfWeek) + duration : duration; 13583954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin mNewHistogram.put(timeOfWeek, totalDuration); 13683954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin 1375d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin String timeOfDay = timeFeatures.get(TimeStatsAggregator.TIME_OF_DAY); 13883954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin totalDuration = (mNewHistogram.containsKey(timeOfDay)) ? 1395d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mNewHistogram.get(timeOfDay) + duration : duration; 1405d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mNewHistogram.put(timeOfDay, totalDuration); 1415d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 1425d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 1435d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private void consolidateHistogram(double weight, long newDuration) { 1445d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin long base = 1000; 1455d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin long newWeight = (long) (weight * base); 1465d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin long currWeight = base - newWeight; 1475d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 1485d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin for (Map.Entry<String, Long> entry : mHistogram.entrySet()) { 1495d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin String timeLabel = entry.getKey(); 1505d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin long duration = entry.getValue() * currWeight; 1515d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin if (mNewHistogram.containsKey(timeLabel)) { 1525d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin duration += mNewHistogram.get(timeLabel) * newWeight; 1535d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 1545d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin duration /= base; 1555d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mHistogram.put(timeLabel, duration); 1565d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 1575d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 1585d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin for (Map.Entry<String, Long> entry : mNewHistogram.entrySet()) { 1595d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin String timeLabel = entry.getKey(); 1605d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin if (!mHistogram.containsKey(timeLabel)) { 1615d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin long duration = newWeight * entry.getValue(); 1625d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin duration /= base; 1635d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mHistogram.put(timeLabel, duration); 1645d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 1655d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 1665d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mDuration = (mDuration * currWeight + newDuration * newWeight) / base; 1675d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 168f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin} 169