135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li/* 235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * Copyright (C) 2008-2009 The Android Open Source Project 335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * Licensed under the Apache License, Version 2.0 (the "License"); 535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * you may not use this file except in compliance with the License. 635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * You may obtain a copy of the License at 735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * http://www.apache.org/licenses/LICENSE-2.0 935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * 1035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * Unless required by applicable law or agreed to in writing, software 1135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * distributed under the License is distributed on an "AS IS" BASIS, 1235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * See the License for the specific language governing permissions and 1435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * limitations under the License. 1535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 1635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 17db567c390bd56c05614eaa83c02dbb99f97ad9ccRomain Guypackage android.gesture; 1835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 1935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liimport java.util.ArrayList; 2035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liimport java.util.Collections; 2135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liimport java.util.Comparator; 2235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liimport java.util.TreeMap; 2335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 2435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li/** 2535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li * An implementation of an instance-based learner 2635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li */ 2735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 2835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Liclass InstanceLearner extends Learner { 290e1ca5749a96778869ef62f939542a61c034209bRomain Guy private static final Comparator<Prediction> sComparator = new Comparator<Prediction>() { 300e1ca5749a96778869ef62f939542a61c034209bRomain Guy public int compare(Prediction object1, Prediction object2) { 310e1ca5749a96778869ef62f939542a61c034209bRomain Guy double score1 = object1.score; 320e1ca5749a96778869ef62f939542a61c034209bRomain Guy double score2 = object2.score; 330e1ca5749a96778869ef62f939542a61c034209bRomain Guy if (score1 > score2) { 340e1ca5749a96778869ef62f939542a61c034209bRomain Guy return -1; 350e1ca5749a96778869ef62f939542a61c034209bRomain Guy } else if (score1 < score2) { 360e1ca5749a96778869ef62f939542a61c034209bRomain Guy return 1; 370e1ca5749a96778869ef62f939542a61c034209bRomain Guy } else { 380e1ca5749a96778869ef62f939542a61c034209bRomain Guy return 0; 390e1ca5749a96778869ef62f939542a61c034209bRomain Guy } 400e1ca5749a96778869ef62f939542a61c034209bRomain Guy } 410e1ca5749a96778869ef62f939542a61c034209bRomain Guy }; 420e1ca5749a96778869ef62f939542a61c034209bRomain Guy 4335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li @Override 444758f1216bd16763c72500bc3c2f0fb43c08d613Yang Li ArrayList<Prediction> classify(int sequenceType, int orientationType, float[] vector) { 4535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ArrayList<Prediction> predictions = new ArrayList<Prediction>(); 4635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li ArrayList<Instance> instances = getInstances(); 4735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li int count = instances.size(); 4835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li TreeMap<String, Double> label2score = new TreeMap<String, Double>(); 4935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li for (int i = 0; i < count; i++) { 5035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li Instance sample = instances.get(i); 51e6ea003ab66ea8bd91bed8aaf5c3b4cd75555886Yang Li if (sample.vector.length != vector.length) { 5235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li continue; 5335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 5435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li double distance; 550a63716ed0e44f7cd32b81a444429318d42d8f08Romain Guy if (sequenceType == GestureStore.SEQUENCE_SENSITIVE) { 5646c53129c6f27c9193ab195a69cb50591b8c1fa2Romain Guy distance = GestureUtils.minimumCosineDistance(sample.vector, vector, orientationType); 5735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else { 5846c53129c6f27c9193ab195a69cb50591b8c1fa2Romain Guy distance = GestureUtils.squaredEuclideanDistance(sample.vector, vector); 5935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 6035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li double weight; 6135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (distance == 0) { 6235aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li weight = Double.MAX_VALUE; 6335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } else { 6435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li weight = 1 / distance; 6535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 6635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li Double score = label2score.get(sample.label); 6735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li if (score == null || weight > score) { 6835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li label2score.put(sample.label, weight); 6935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 7035aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 7135aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 720e1ca5749a96778869ef62f939542a61c034209bRomain Guy// double sum = 0; 73db567c390bd56c05614eaa83c02dbb99f97ad9ccRomain Guy for (String name : label2score.keySet()) { 7435aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li double score = label2score.get(name); 750e1ca5749a96778869ef62f939542a61c034209bRomain Guy// sum += score; 7635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li predictions.add(new Prediction(name, score)); 7735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 7835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 7935aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li // normalize 800e1ca5749a96778869ef62f939542a61c034209bRomain Guy// for (Prediction prediction : predictions) { 810e1ca5749a96778869ef62f939542a61c034209bRomain Guy// prediction.score /= sum; 820e1ca5749a96778869ef62f939542a61c034209bRomain Guy// } 8335aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 840e1ca5749a96778869ef62f939542a61c034209bRomain Guy Collections.sort(predictions, sComparator); 8535aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li 8635aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li return predictions; 8735aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li } 8835aa84b1f9f5e42dd00cb66df993ed1628c8963bYang Li} 89