fix clustering bugs
Change-Id: Ia1161055bff5e2e222422d07243524bf0a34d775
diff --git a/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java b/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
index c4e7e28..ef57939 100644
--- a/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
+++ b/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
@@ -52,6 +52,9 @@
private HashMap<String, HistogramCounter> mPredictor =
new HashMap<String, HistogramCounter>();
+ private HashMap<String, Integer> mClassCounts = new HashMap<String, Integer>();
+ private int mTotalClassCount = 0;
+
private static final double FEATURE_INACTIVE_LIKELIHOOD = 0.00000001;
private static final double LOG_INACTIVE = Math.log(FEATURE_INACTIVE_LIKELIHOOD);
@@ -91,9 +94,9 @@
if (!mCounter.containsKey(featureValue)) {
classCounts = new HashMap<String, Integer>();
mCounter.put(featureValue, classCounts);
+ } else {
+ classCounts = mCounter.get(featureValue);
}
- classCounts = mCounter.get(featureValue);
-
int count = (classCounts.containsKey(className)) ?
classCounts.get(className) + 1 : 1;
classCounts.put(className, count);
@@ -140,6 +143,8 @@
HashMap<String, Double> appScores = new HashMap<String, Double>();
double defaultLikelihood = getDefaultLikelihood(features);
+ HashMap<String, Integer> appearCounts = new HashMap<String, Integer>();
+
// compute all app scores
for (Map.Entry<String, HistogramCounter> entry : mPredictor.entrySet()) {
String featureName = entry.getKey();
@@ -152,16 +157,37 @@
for (Map.Entry<String, Double> item : scoreMap.entrySet()) {
String appName = item.getKey();
double appScore = item.getValue();
-
double score = (appScores.containsKey(appName)) ?
appScores.get(appName) : defaultLikelihood;
score += appScore - LOG_INACTIVE;
-
appScores.put(appName, score);
+
+ int count = (appearCounts.containsKey(appName)) ?
+ appearCounts.get(appName) + 1 : 1;
+ appearCounts.put(appName, count);
}
}
}
+ // TODO: this check should be unnecessary
+ if (mClassCounts.size() != 0 && mTotalClassCount != 0) {
+ for (Map.Entry<String, Double> entry : appScores.entrySet()) {
+ String appName = entry.getKey();
+ double appScore = entry.getValue();
+ if (!appearCounts.containsKey(appName)) {
+ throw new RuntimeException("appearance count error!");
+ }
+ int appearCount = appearCounts.get(appName);
+
+ if (!mClassCounts.containsKey(appName)) {
+ throw new RuntimeException("class count error!");
+ }
+ double appPrior =
+ Math.log(mClassCounts.get(appName)) - Math.log(mTotalClassCount);
+ appScores.put(appName, appScore - appPrior * (appearCount - 1));
+ }
+ }
+
// sort app scores
List<Map.Entry<String, Double> > appList =
new ArrayList<Map.Entry<String, Double> >(appScores.size());
@@ -173,7 +199,7 @@
}
});
- Log.e(TAG, "findTopApps appList: " + appList);
+ Log.v(TAG, "findTopApps appList: " + appList);
return appList;
}
@@ -190,6 +216,10 @@
counter.addSample(sampleId, featureValue);
}
}
+
+ int sampleCount = (mClassCounts.containsKey(sampleId)) ?
+ mClassCounts.get(sampleId) + 1 : 1;
+ mClassCounts.put(sampleId, sampleCount);
}
/*
@@ -201,6 +231,9 @@
counter.resetCounter();
}
mPredictor.clear();
+
+ mClassCounts.clear();
+ mTotalClassCount = 0;
}
/*
@@ -258,6 +291,39 @@
useFeature(entry.getKey());
mPredictor.get(entry.getKey()).setCounter(entry.getValue());
}
+
+ // TODO: this is a temporary fix for now
+ loadClassCounter();
+
return true;
}
+
+ private void loadClassCounter() {
+ String TIME_OF_WEEK = "Time of Week";
+
+ if (!mPredictor.containsKey(TIME_OF_WEEK)) {
+ throw new RuntimeException("Precition model error: missing Time of Week!");
+ }
+
+ HashMap<String, HashMap<String, Integer> > counter =
+ mPredictor.get(TIME_OF_WEEK).getCounter();
+
+ mTotalClassCount = 0;
+ mClassCounts.clear();
+ for (HashMap<String, Integer> map : counter.values()) {
+ for (Map.Entry<String, Integer> entry : map.entrySet()) {
+ int classCount = entry.getValue();
+ String className = entry.getKey();
+ mTotalClassCount += classCount;
+
+ if (mClassCounts.containsKey(className)) {
+ classCount += mClassCounts.get(className);
+ }
+ mClassCounts.put(className, classCount);
+ }
+ }
+
+ Log.e(TAG, "class counts: " + mClassCounts + ", total count: " +
+ mTotalClassCount);
+ }
}
diff --git a/bordeaux/service/src/android/bordeaux/services/BaseCluster.java b/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
index d00e5f0..03574a9 100644
--- a/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
+++ b/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
@@ -30,6 +30,11 @@
public double[] mCenter;
// protected double[] mCenter;
+ protected static final int VECTOR_LENGTH = 3;
+
+ private static final long FORGETTING_ENUMERATOR = 95;
+ private static final long FORGETTING_DENOMINATOR = 100;
+
// Histogram illustrates the pattern of visit during time of day,
protected HashMap<String, Long> mHistogram = new HashMap<String, Long>();
@@ -41,24 +46,26 @@
public BaseCluster(Location location) {
mCenter = getLocationVector(location);
-
mDuration = 0;
}
- public BaseCluster() {
- mCenter = new double[] {0f, 0f, 0f};
+ public BaseCluster(String semanticId, double longitude, double latitude,
+ long duration) {
+ mSemanticId = semanticId;
+ mCenter = getLocationVector(longitude, latitude);
+ mDuration = duration;
}
public String getSemanticId() {
return mSemanticId;
}
- protected void generateSemanticId(long index) {
+ public void generateSemanticId(long index) {
mSemanticId = "cluser: " + String.valueOf(index);
}
- public void setSemanticId(String semanticId) {
- mSemanticId = semanticId;
+ public long getDuration() {
+ return mDuration;
}
public boolean hasSemanticId() {
@@ -70,7 +77,7 @@
}
protected double[] getLocationVector(double longitude, double latitude) {
- double vector[] = new double[3];
+ double vector[] = new double[VECTOR_LENGTH];
double lambda = Math.toRadians(longitude);
double phi = Math.toRadians(latitude);
@@ -96,7 +103,7 @@
private double computeDistance(double[] vector1, double[] vector2) {
double product = 0f;
- for (int i = 0; i < 3; ++i) {
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
product += vector1[i] * vector2[i];
}
double radian = Math.acos(Math.min(product, 1f));
@@ -115,23 +122,12 @@
}
public void absorbCluster(BaseCluster cluster) {
- // the new cluster center is the average of the two clusters.
- double weight = ((double) mDuration) / (mDuration + cluster.mDuration);
- double clusterWeight = 1f - weight;
- double norm = 0;
- for (int i = 0; i < 3; ++i) {
- mCenter[i] = weight * mCenter[i] + clusterWeight * cluster.mCenter[i];
- norm += mCenter[i] * mCenter[i];
- }
- // normalize the center to be unit vector
- for (int i = 0; i < 3; ++i) {
- mCenter[i] /= norm;
- }
+ averageCenter(cluster.mCenter, cluster.mDuration);
absorbHistogram(cluster);
}
public void setCluster(BaseCluster cluster) {
- for (int i = 0; i < 3; ++i) {
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
mCenter[i] = cluster.mCenter[i];
}
mHistogram.clear();
@@ -173,4 +169,45 @@
mDuration += mHistogram.get(TimeStatsAggregator.WEEKDAY);
}
}
+
+ public void forgetPastHistory() {
+ mDuration *= FORGETTING_ENUMERATOR;
+ mDuration /= FORGETTING_DENOMINATOR;
+
+ for (Map.Entry<String, Long> entry : mHistogram.entrySet()) {
+ String key = entry.getKey();
+ long value = entry.getValue();
+
+ value *= FORGETTING_ENUMERATOR;
+ value /= FORGETTING_DENOMINATOR;
+
+ mHistogram.put(key, value);
+ }
+ }
+
+ protected void normalizeCenter() {
+ double norm = 0;
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
+ norm += mCenter[i] * mCenter[i];
+ }
+ norm = Math.sqrt(norm);
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
+ mCenter[i] /= norm;
+ }
+ }
+
+ protected void averageCenter(double[] newCenter, long newDuration) {
+ double weight = ((double) mDuration) / (mDuration + newDuration);
+ double newWeight = 1f - weight;
+
+ double norm = 0;
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
+ mCenter[i] = weight * mCenter[i] + newWeight * newCenter[i];
+ norm += mCenter[i] * mCenter[i];
+ }
+ norm = Math.sqrt(norm);
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
+ mCenter[i] /= norm;
+ }
+ }
}
diff --git a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java b/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
index 4bc0369..249be86 100644
--- a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
+++ b/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
@@ -38,41 +38,36 @@
private static String TAG = "ClusterManager";
- private static float LOCATION_CLUSTER_RADIUS = 50; // meter
+ private static float LOCATION_CLUSTER_RADIUS = 25; // meter
- private static float SEMANTIC_CLUSTER_RADIUS = 100; // meter
+ private static float SEMANTIC_CLUSTER_RADIUS = 75; // meter
// Consoliate location clusters (and check for new semantic clusters)
- // every 30 minutes (1800 seconds).
- private static final long CONSOLIDATE_INTERVAL = 1800;
-
- // Prune away clusters that are stayed for less than 3 minutes (180 seconds)
- private static long LOCATION_CLUSTER_THRESHOLD = 180;
+ // every 10 minutes (600 seconds).
+ private static final long CONSOLIDATE_INTERVAL = 600;
// A location cluster can be labeled as a semantic cluster if it has been
// stayed for at least 10 minutes (600 seconds) within a day.
private static final long SEMANTIC_CLUSTER_THRESHOLD = 600; // seconds
- // Reset location cluters every 6 hours (21600 seconds).
- private static final long LOCATION_REFRESH_PERIOD = 21600; // seconds
+ // Reset location cluters every 12 hours (43200 seconds).
+ private static final long LOCATION_REFRESH_PERIOD = 43200; // seconds
private static String UNKNOWN_LOCATION = "Unknown Location";
- private static String HOME = "Home";
-
- private static String OFFICE = "Office";
-
private Location mLastLocation = null;
private long mClusterDuration;
- private long mTimeRef = 0;
+ private long mConsolidateRef = 0;
+
+ private long mRefreshRef = 0;
private long mSemanticClusterCount = 0;
private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>();
- private ArrayList<SemanticCluster> mSemanticClusters = new ArrayList<SemanticCluster>();
+ private ArrayList<BaseCluster> mSemanticClusters = new ArrayList<BaseCluster>();
private AggregatorRecordStorage mStorage;
@@ -84,10 +79,13 @@
private static final String SEMANTIC_LATITUDE = "Latitude";
+ private static final String SEMANTIC_DURATION = "Duration";
+
private static final String[] SEMANTIC_COLUMNS =
new String[]{ SEMANTIC_ID,
SEMANTIC_LONGITUDE,
SEMANTIC_LATITUDE,
+ SEMANTIC_DURATION,
TimeStatsAggregator.WEEKEND,
TimeStatsAggregator.WEEKDAY,
TimeStatsAggregator.MORNING,
@@ -97,8 +95,8 @@
TimeStatsAggregator.NIGHT,
TimeStatsAggregator.LATENIGHT };
- private static final int mFeatureValueStart = 3;
- private static final int mFeatureValueEnd = 10;
+ private static final int mFeatureValueStart = 4;
+ private static final int mFeatureValueEnd = 11;
public ClusterManager(Context context) {
mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS);
@@ -120,172 +118,136 @@
Log.v(TAG, "sample duration: " + duration +
", number of clusters: " + mLocationClusters.size());
- // add the last location to cluster.
- // first find the cluster it belongs to.
- for (int i = 0; i < mLocationClusters.size(); ++i) {
- float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation);
- Log.v(TAG, "clulster " + i + " is within " + distance + " meters");
- if (distance < bestClusterDistance) {
- bestClusterDistance = distance;
- bestClusterIndex = i;
+ synchronized (mLocationClusters) {
+ // add the last location to cluster.
+ // first find the cluster it belongs to.
+ for (int i = 0; i < mLocationClusters.size(); ++i) {
+ float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation);
+ Log.v(TAG, "clulster " + i + " is within " + distance + " meters");
+ if (distance < bestClusterDistance) {
+ bestClusterDistance = distance;
+ bestClusterIndex = i;
+ }
}
- }
- // add the location to the selected cluster
- if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
- mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration);
- } else {
- // if it is far away from all existing clusters, create a new cluster.
- LocationCluster cluster = new LocationCluster(mLastLocation, duration);
- // move the center of the new cluster if its covering region overlaps
- // with an existing cluster.
- if (bestClusterDistance < 2 * LOCATION_CLUSTER_RADIUS) {
- Log.v(TAG, "move away activated");
- cluster.moveAwayCluster(mLocationClusters.get(bestClusterIndex),
- ((float) 2 * LOCATION_CLUSTER_RADIUS));
+ // add the location to the selected cluster
+ if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
+ mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration);
+ } else {
+ // if it is far away from all existing clusters, create a new cluster.
+ LocationCluster cluster = new LocationCluster(mLastLocation, duration);
+ mLocationClusters.add(cluster);
}
- mLocationClusters.add(cluster);
}
} else {
- mTimeRef = currentTime;
+ mConsolidateRef = currentTime;
+ mRefreshRef = currentTime;
if (mLocationClusters.isEmpty()) {
mClusterDuration = 0;
}
}
- long collectDuration = currentTime - mTimeRef;
- Log.e(TAG, "collect duration: " + collectDuration);
+ long collectDuration = currentTime - mConsolidateRef;
+ Log.v(TAG, "collect duration: " + collectDuration);
if (collectDuration > CONSOLIDATE_INTERVAL) {
// TODO : conslidation takes time. move this to a separate thread later.
- consolidateClusters(collectDuration);
- mTimeRef = currentTime;
- }
- mLastLocation = location;
- }
+ consolidateClusters();
+ mConsolidateRef = currentTime;
- private void consolidateClusters(long duration) {
- LocationCluster cluster;
- for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
- cluster = mLocationClusters.get(i);
- cluster.consolidate(duration);
-
- // remove transit clusters
- if (!cluster.passThreshold(LOCATION_CLUSTER_THRESHOLD)) {
- mLocationClusters.remove(cluster);
+ long refreshDuration = currentTime - mRefreshRef;
+ Log.v(TAG, "refresh duration: " + refreshDuration);
+ if (refreshDuration > LOCATION_REFRESH_PERIOD) {
+ updateSemanticClusters();
+ mRefreshRef = currentTime;
}
- }
-
- // merge clusters whose regions are overlapped. note that after merge
- // cluster center changes but cluster size remains unchanged.
- for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
- cluster = mLocationClusters.get(i);
- for (int j = i - 1; j >= 0; --j) {
- float distance = mLocationClusters.get(j).distanceToCluster(cluster);
- if (distance < LOCATION_CLUSTER_RADIUS) {
- mLocationClusters.get(j).absorbCluster(cluster);
- mLocationClusters.remove(cluster);
- }
- }
- }
-
- // check if new semantic clusters are found
- if (findNewSemanticClusters() &&
- mClusterDuration < LOCATION_REFRESH_PERIOD) {
saveSemanticClusters();
}
- if (mClusterDuration > LOCATION_REFRESH_PERIOD) {
- updateSemanticClusters();
- mClusterDuration = 0;
- }
+ mLastLocation = location;
}
- private boolean findNewSemanticClusters() {
- // select candidate location clusters
- ArrayList<LocationCluster> candidates = new ArrayList<LocationCluster>();
- for (LocationCluster cluster : mLocationClusters) {
- if (!cluster.hasSemanticId() &&
- cluster.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) {
- candidates.add(cluster);
+ private void consolidateClusters() {
+ synchronized (mSemanticClusters) {
+ LocationCluster locationCluster;
+ for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
+ locationCluster = mLocationClusters.get(i);
+ locationCluster.consolidate();
}
- }
- // assign each candidate to a semantic cluster
- boolean foundNewClusters = false;
- for (LocationCluster candidate : candidates) {
- // find the closest semantic cluster
- float bestClusterDistance = Float.MAX_VALUE;
- SemanticCluster bestCluster = null;
- for (SemanticCluster cluster : mSemanticClusters) {
- float distance = cluster.distanceToCluster(candidate);
- Log.v(TAG, "distance to semantic cluster: " + cluster.getSemanticId());
-
- if (distance < bestClusterDistance) {
- bestClusterDistance = distance;
- bestCluster = cluster;
+ // merge clusters whose regions are overlapped. note that after merge
+ // cluster center changes but cluster size remains unchanged.
+ for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
+ locationCluster = mLocationClusters.get(i);
+ for (int j = i - 1; j >= 0; --j) {
+ float distance =
+ mLocationClusters.get(j).distanceToCluster(locationCluster);
+ if (distance < LOCATION_CLUSTER_RADIUS) {
+ mLocationClusters.get(j).absorbCluster(locationCluster);
+ mLocationClusters.remove(locationCluster);
+ }
}
}
+ Log.v(TAG, mLocationClusters.size() + " location clusters after consolidate");
- // if candidate doesn't belong to any semantic cluster, create a new
- // semantic cluster
- if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) {
- // if it is far away from all existing clusters, create a new cluster.
- bestCluster = new SemanticCluster(candidate, mSemanticClusterCount++);
- String id = bestCluster.getSemanticId();
+ // assign each candidate to a semantic cluster and check if new semantic
+ // clusters are found
+ for (LocationCluster candidate : mLocationClusters) {
+ if (candidate.hasSemanticId() ||
+ candidate.hasSemanticClusterId() ||
+ !candidate.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) {
+ continue;
+ }
- // Add new semantic cluster to the list.
- mSemanticClusters.add(bestCluster);
+ // find the closest semantic cluster
+ float bestClusterDistance = Float.MAX_VALUE;
+ String bestClusterId = "Unused Id";
+ for (BaseCluster cluster : mSemanticClusters) {
+ float distance = cluster.distanceToCluster(candidate);
+ Log.v(TAG, distance + "distance to semantic cluster: " + cluster.getSemanticId());
- foundNewClusters = true;
+ if (distance < bestClusterDistance) {
+ bestClusterDistance = distance;
+ bestClusterId = cluster.getSemanticId();
+ }
+ }
+
+ // if candidate doesn't belong to any semantic cluster, create a new
+ // semantic cluster
+ if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) {
+ candidate.generateSemanticId(mSemanticClusterCount++);
+ mSemanticClusters.add(candidate);
+ } else {
+ candidate.setSemanticClusterId(bestClusterId);
+ }
}
- candidate.setSemanticId(bestCluster.getSemanticId());
+ Log.v(TAG, mSemanticClusters.size() + " semantic clusters after consolidate");
}
- candidates.clear();
- return foundNewClusters;
}
private void updateSemanticClusters() {
synchronized (mSemanticClusters) {
- // initialize semanticMap
- HashMap<String, ArrayList<BaseCluster> > semanticMap =
- new HashMap<String, ArrayList<BaseCluster> >();
- for (SemanticCluster cluster : mSemanticClusters) {
- String semanticId = cluster.getSemanticId();
- semanticMap.put(cluster.getSemanticId(), new ArrayList<BaseCluster>());
- semanticMap.get(semanticId).add(cluster);
+ // create index to cluster map
+ HashMap<String, BaseCluster> semanticIdMap =
+ new HashMap<String, BaseCluster>();
+ for (BaseCluster cluster : mSemanticClusters) {
+ // TODO: apply forgetting factor on existing semantic cluster stats,
+ // duration, histogram, etc.
+ cluster.forgetPastHistory();
+ semanticIdMap.put(cluster.getSemanticId(), cluster);
}
// assign each candidate to a semantic cluster
for (LocationCluster cluster : mLocationClusters) {
- if (cluster.hasSemanticId()) {
- semanticMap.get(cluster.getSemanticId()).add(cluster);
+ if (cluster.hasSemanticClusterId()) {
+ BaseCluster semanticCluster =
+ semanticIdMap.get(cluster.getSemanticClusterId());
+ semanticCluster.absorbCluster(cluster);
}
}
// reset location clusters.
mLocationClusters.clear();
- mLastLocation = null;
- mTimeRef = 0;
-
- // use candidates semantic cluster
- BaseCluster newCluster = new BaseCluster();
- for (ArrayList<BaseCluster> clusterList : semanticMap.values()) {
- SemanticCluster semanticCluster = (SemanticCluster) clusterList.get(0);
-
- if (clusterList.size() > 1) {
- newCluster.setCluster(clusterList.get(1));
- for (int i = 2; i < clusterList.size(); i++) {
- newCluster.absorbCluster(clusterList.get(i));
- }
- semanticCluster.absorbCluster(newCluster);
- } else {
- // cluster with no new candidate
- Log.e(TAG, "semantic cluster with no new location clusters: " +
- semanticCluster);
- }
- }
}
- saveSemanticClusters();
}
private void loadSemanticClusters() {
@@ -298,8 +260,9 @@
String semanticId = map.get(SEMANTIC_ID);
double longitude = Double.valueOf(map.get(SEMANTIC_LONGITUDE));
double latitude = Double.valueOf(map.get(SEMANTIC_LATITUDE));
- SemanticCluster cluster =
- new SemanticCluster(semanticId, longitude, latitude);
+ long duration = Long.valueOf(map.get(SEMANTIC_DURATION));
+ BaseCluster cluster =
+ new BaseCluster(semanticId, longitude, latitude, duration);
histogram.clear();
for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) {
@@ -321,7 +284,7 @@
mStorage.removeAllData();
synchronized (mSemanticClusters) {
- for (SemanticCluster cluster : mSemanticClusters) {
+ for (BaseCluster cluster : mSemanticClusters) {
rowFeatures.clear();
rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId());
@@ -329,6 +292,8 @@
String.valueOf(cluster.getCenterLongitude()));
rowFeatures.put(SEMANTIC_LATITUDE,
String.valueOf(cluster.getCenterLatitude()));
+ rowFeatures.put(SEMANTIC_DURATION,
+ String.valueOf(cluster.getDuration()));
HashMap<String, Long> histogram = cluster.getHistogram();
for (Map.Entry<String, Long> entry : histogram.entrySet()) {
@@ -347,7 +312,7 @@
if (mLastLocation != null) {
// TODO: use fast neatest neighbor search speed up location search
synchronized (mSemanticClusters) {
- for (SemanticCluster cluster: mSemanticClusters) {
+ for (BaseCluster cluster: mSemanticClusters) {
if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) {
return cluster.getSemanticId();
}
@@ -360,7 +325,7 @@
public List<String> getClusterNames() {
ArrayList<String> clusters = new ArrayList<String>();
synchronized (mSemanticClusters) {
- for (SemanticCluster cluster: mSemanticClusters) {
+ for (BaseCluster cluster: mSemanticClusters) {
clusters.add(cluster.getSemanticId());
}
}
diff --git a/bordeaux/service/src/android/bordeaux/services/LocationCluster.java b/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
index 078e643..c9f753f 100644
--- a/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
+++ b/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
@@ -27,15 +27,26 @@
public class LocationCluster extends BaseCluster {
public static String TAG = "LocationCluster";
- private boolean mIsNewCluster;
-
private ArrayList<Location> mLocations = new ArrayList<Location>();
private HashMap<String, Long> mNewHistogram = new HashMap<String, Long>();
+ private String mSemanticClusterId = null;
+
+ public void setSemanticClusterId(String semanticClusterId) {
+ mSemanticClusterId = semanticClusterId;
+ }
+
+ public String getSemanticClusterId() {
+ return mSemanticClusterId;
+ }
+
+ public boolean hasSemanticClusterId() {
+ return mSemanticClusterId != null;
+ }
+
// TODO: make it a singleton class
public LocationCluster(Location location, long duration) {
super(location);
- mIsNewCluster = true;
addSample(location, duration);
}
@@ -48,60 +59,52 @@
mLocations.add(location);
}
- public void consolidate(long interval) {
- // TODO: add check on interval
+ public void consolidate() {
+ // If there is no new location added during this period, do nothing.
+ if (mLocations.size() == 0) {
+ return;
+ }
+
double[] newCenter = {0f, 0f, 0f};
long newDuration = 0l;
-
// update cluster center
for (Location location : mLocations) {
double[] vector = getLocationVector(location);
long duration = location.getTime(); // in seconds
+ if (duration == 0) {
+ throw new RuntimeException("location duration is zero");
+ }
+
newDuration += duration;
- for (int i = 0; i < 3; ++i) {
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
newCenter[i] += vector[i] * duration;
}
}
- for (int i = 0; i < 3; ++i) {
+ if (newDuration == 0l) {
+ throw new RuntimeException("new duration is zero!");
+ }
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
newCenter[i] /= newDuration;
}
// remove location data
mLocations.clear();
- if (mIsNewCluster) {
- for (int i = 0; i < 3; ++i) {
- mCenter[i] = newCenter[i];
+ // The updated center is the weighted average of the existing and the new
+ // centers. Note that if the cluster is consolidated for the first time,
+ // the weight for the existing cluster would be zero.
+ averageCenter(newCenter, newDuration);
+
+ // update histogram
+ for (Map.Entry<String, Long> entry : mNewHistogram.entrySet()) {
+ String timeLabel = entry.getKey();
+ long duration = entry.getValue();
+ if (mHistogram.containsKey(timeLabel)) {
+ duration += mHistogram.get(timeLabel);
}
- mDuration = newDuration;
- mHistogram.clear();
- mHistogram.putAll(mNewHistogram);
- mIsNewCluster = false;
- } else {
- // the new center is weight average over latest and existing centers.
- // fine tune the weight of new center
- double newWeight = ((double) newDuration) / (newDuration + mDuration);
- double currWeight = 1f - newWeight;
- double norm = 0;
- for (int i = 0; i < 3; ++i) {
- mCenter[i] = currWeight * mCenter[i] + newWeight * newCenter[i];
- norm += mCenter[i] * mCenter[i];
- }
- // normalize
- for (int i = 0; i < 3; ++i) {
- mCenter[i] /= norm;
- }
- // update histogram
- for (Map.Entry<String, Long> entry : mNewHistogram.entrySet()) {
- String timeLabel = entry.getKey();
- long duration = entry.getValue();
- if (mHistogram.containsKey(timeLabel)) {
- duration += mHistogram.get(timeLabel);
- }
- mHistogram.put(timeLabel, duration);
- }
- mDuration += newDuration;
+ mHistogram.put(timeLabel, duration);
}
+ mDuration += newDuration;
mNewHistogram.clear();
}
@@ -110,21 +113,21 @@
* cluster move the center away from that cluster till there is no overlap.
*/
public void moveAwayCluster(LocationCluster cluster, float distance) {
- double[] vector = new double[3];
+ double[] vector = new double[VECTOR_LENGTH];
double dot = 0f;
- for (int i = 0; i < 3; ++i) {
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
dot += mCenter[i] * cluster.mCenter[i];
}
double norm = 0f;
- for (int i = 0; i < 3; ++i) {
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
vector[i] = mCenter[i] - dot * cluster.mCenter[i];
norm += vector[i] * vector[i];
}
norm = Math.sqrt(norm);
double radian = distance / EARTH_RADIUS;
- for (int i = 0; i < 3; ++i) {
+ for (int i = 0; i < VECTOR_LENGTH; ++i) {
mCenter[i] = cluster.mCenter[i] * Math.cos(radian) +
(vector[i] / norm) * Math.sin(radian);
}
diff --git a/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java b/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java
deleted file mode 100644
index b0d42ab..0000000
--- a/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java
+++ /dev/null
@@ -1,43 +0,0 @@
-/*
- * Copyright (C) 2012 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package android.bordeaux.services;
-
-import android.location.Location;
-import android.text.format.Time;
-import android.util.Log;
-
-import java.lang.Math;
-import java.util.ArrayList;
-import java.util.Map;
-
-public class SemanticCluster extends BaseCluster {
-
- public static String TAG = "SemanticCluster";
-
- public SemanticCluster(LocationCluster cluster, long semanticIndex) {
- mCenter = new double[3];
- for (int i = 0; i < 3; ++i) {
- mCenter[i] = cluster.mCenter[i];
- }
- generateSemanticId(semanticIndex);
- }
-
- public SemanticCluster(String semanticId, double longitude, double latitude) {
- setSemanticId(semanticId);
-
- mCenter = getLocationVector(longitude, latitude);
- }
-}