Ignore:
Timestamp:
08/17/12 09:05:19 (12 years ago)
Author:
sherbold
Message:
  • adapted to quest coding style
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/PredictionByPartialMatch.java

    r547 r559  
     1 
    12package de.ugoe.cs.quest.usageprofiles; 
    23 
    … …  
    1112/** 
    1213 * <p> 
    13  * Implements Prediction by Partial Match (PPM) based on the following formula 
    14  * (LaTeX-style notation):<br> 
     14 * Implements Prediction by Partial Match (PPM) based on the following formula (LaTeX-style 
     15 * notation):<br> 
    1516 * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n 
    1617 * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})<br> 
    … …  
    2324public class PredictionByPartialMatch extends TrieBasedModel { 
    2425 
    25         /** 
    26          * <p> 
    27          * Id for object serialization. 
    28          * </p> 
    29          */ 
    30         private static final long serialVersionUID = 1L; 
    31  
    32         /** 
    33          * <p> 
    34          * Minimum order of the Markov model. 
    35          * </p> 
    36          */ 
    37         protected int minOrder; 
    38  
    39         /** 
    40          * <p> 
    41          * Probability to use a lower-order Markov model 
    42          * </p> 
    43          */ 
    44         protected double probEscape; 
    45  
    46         /** 
    47          * <p> 
    48          * Constructor. Creates a new PredictionByPartialMatch model with a given 
    49          * Markov order and a default escape probability of 0.1. 
    50          * </p> 
    51          *  
    52          * @param markovOrder 
    53          *            Markov order of the model 
    54          * @param r 
    55          *            random number generator used by probabilistic methods of the 
    56          *            class 
    57          */ 
    58         public PredictionByPartialMatch(int markovOrder, Random r) { 
    59                 this(markovOrder, r, 0.1); 
    60         } 
    61  
    62         /** 
    63          * <p> 
    64          * Creates a new PredictionByPartialMatch model with a given Markov order 
    65          * and escape probability. 
    66          * </p> 
    67          *  
    68          * @param markovOrder 
    69          *            Markov order of the model 
    70          * @param r 
    71          *            random number generator used by probabilistic methods of the 
    72          *            class 
    73          * @param probEscape 
    74          *            escape probability used by the model 
    75          */ 
    76         public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) { 
    77                 this(markovOrder, 0, r, probEscape); 
    78         } 
    79  
    80         /** 
    81          * <p> 
    82          * Creates a new PredictionByPartialMatch model with a given Markov order 
    83          * and escape probability. 
    84          * </p> 
    85          *  
    86          * @param markovOrder 
    87          *            Markov order of the model 
    88          * @param minOrder 
    89          *            minimum order of the model; if this order is reached, there is 
    90          *            no escape 
    91          * @param r 
    92          *            random number generator used by probabilistic methods of the 
    93          *            class 
    94          * @param probEscape 
    95          *            escape probability used by the model 
    96          * @throws InvalidParameterException thrown if minOrder is less than 0 or greater than markovOrder or probEscape is not in the interval (0,1) 
    97          */ 
    98         public PredictionByPartialMatch(int markovOrder, int minOrder, Random r, 
    99                         double probEscape) { 
    100                 super(markovOrder, r); 
    101                 if( minOrder< 0 ) { 
    102                         throw new InvalidParameterException("minOrder must be greather than or equal to 0"); 
    103                 } 
    104                 if( minOrder>markovOrder) { 
    105                         throw new InvalidParameterException("minOrder must be less than or equal to markovOrder"); 
    106                 } 
    107                 if( probEscape<=0.0 || probEscape>=1.0) { 
    108                         throw new InvalidParameterException("probEscape must be in the interval (0,1)"); 
    109                 } 
    110                 this.probEscape = probEscape; 
    111                 this.minOrder = minOrder; 
    112         } 
    113  
    114         /** 
    115          * <p> 
    116          * Sets the escape probability of the model. 
    117          * </p> 
    118          *  
    119          * @param probEscape 
    120          *            new escape probability 
    121          */ 
    122         public void setProbEscape(double probEscape) { 
    123                 this.probEscape = probEscape; 
    124         } 
    125  
    126         /** 
    127          * <p> 
    128          * Returns the escape probability of the model. 
    129          * </p> 
    130          *  
    131          * @return escape probability of the model 
    132          */ 
    133         public double getProbEscape() { 
    134                 return probEscape; 
    135         } 
    136  
    137         /** 
    138          * <p> 
    139          * Calculates the probability of the next event based on the formula:<br> 
    140          * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} 
    141          * P_{MM^i}(X_n 
    142          * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... 
    143          * ,X_{n-min})<br> 
    144          * P_{MM^i} denotes the probability in an i-th order Markov model. 
    145          * </p> 
    146          *  
    147          * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
    148          *      de.ugoe.cs.quest.eventcore.Event) 
    149          */ 
    150         @Override 
    151         public double getProbability(List<Event> context, 
    152                         Event symbol) { 
    153                 if (context == null) { 
    154                         throw new InvalidParameterException("context must not be null"); 
    155                 } 
    156                 if (symbol == null) { 
    157                         throw new InvalidParameterException("symbol must not be null"); 
    158                 } 
    159                 double result = 0.0d; 
    160                 double resultCurrentContex = 0.0d; 
    161                 double resultShorterContex = 0.0d; 
    162  
    163                 List<Event> contextCopy; 
    164                 if (context.size() >= trieOrder) { 
    165                         contextCopy = new LinkedList<Event>(context.subList( 
    166                                         context.size() - trieOrder + 1, context.size())); 
    167                 } else { 
    168                         contextCopy = new LinkedList<Event>(context); 
    169                 } 
    170  
    171                 Collection<Event> followers = trie.getFollowingSymbols(contextCopy); // \Sigma' 
    172                 int sumCountFollowers = 0; // N(s\sigma') 
    173                 for (Event follower : followers) { 
    174                         sumCountFollowers += trie.getCount(contextCopy, follower); 
    175                 } 
    176  
    177                 int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) 
    178                 if (sumCountFollowers == 0) { 
    179                         resultCurrentContex = 0.0; 
    180                 } else { 
    181                         resultCurrentContex = (double) countSymbol / sumCountFollowers; 
    182                 } 
    183                 if (contextCopy.size() > minOrder) { 
    184                         resultCurrentContex *= (1 - probEscape); 
    185                         contextCopy.remove(0); 
    186                         if (contextCopy.size() >= minOrder) { 
    187                                 double probSuffix = getProbability(contextCopy, symbol); 
    188  
    189                                 if (followers.size() == 0) { 
    190                                         resultShorterContex = probSuffix; 
    191                                 } else { 
    192                                         resultShorterContex = probEscape * probSuffix; 
    193                                 } 
    194                         } 
    195                 } 
    196                 result = resultCurrentContex + resultShorterContex; 
    197  
    198                 return result; 
    199         } 
     26    /** 
     27     * <p> 
     28     * Id for object serialization. 
     29     * </p> 
     30     */ 
     31    private static final long serialVersionUID = 1L; 
     32 
     33    /** 
     34     * <p> 
     35     * Minimum order of the Markov model. 
     36     * </p> 
     37     */ 
     38    protected int minOrder; 
     39 
     40    /** 
     41     * <p> 
     42     * Probability to use a lower-order Markov model 
     43     * </p> 
     44     */ 
     45    protected double probEscape; 
     46 
     47    /** 
     48     * <p> 
     49     * Constructor. Creates a new PredictionByPartialMatch model with a given Markov order and a 
     50     * default escape probability of 0.1. 
     51     * </p> 
     52     *  
     53     * @param markovOrder 
     54     *            Markov order of the model 
     55     * @param r 
     56     *            random number generator used by probabilistic methods of the class 
     57     */ 
     58    public PredictionByPartialMatch(int markovOrder, Random r) { 
     59        this(markovOrder, r, 0.1); 
     60    } 
     61 
     62    /** 
     63     * <p> 
     64     * Creates a new PredictionByPartialMatch model with a given Markov order and escape 
     65     * probability. 
     66     * </p> 
     67     *  
     68     * @param markovOrder 
     69     *            Markov order of the model 
     70     * @param r 
     71     *            random number generator used by probabilistic methods of the class 
     72     * @param probEscape 
     73     *            escape probability used by the model 
     74     */ 
     75    public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) { 
     76        this(markovOrder, 0, r, probEscape); 
     77    } 
     78 
     79    /** 
     80     * <p> 
     81     * Creates a new PredictionByPartialMatch model with a given Markov order and escape 
     82     * probability. 
     83     * </p> 
     84     *  
     85     * @param markovOrder 
     86     *            Markov order of the model 
     87     * @param minOrder 
     88     *            minimum order of the model; if this order is reached, there is no escape 
     89     * @param r 
     90     *            random number generator used by probabilistic methods of the class 
     91     * @param probEscape 
     92     *            escape probability used by the model 
     93     * @throws InvalidParameterException 
     94     *             thrown if minOrder is less than 0 or greater than markovOrder or probEscape is 
     95     *             not in the interval (0,1) 
     96     */ 
     97    public PredictionByPartialMatch(int markovOrder, int minOrder, Random r, double probEscape) { 
     98        super(markovOrder, r); 
     99        if (minOrder < 0) { 
     100            throw new InvalidParameterException("minOrder must be greather than or equal to 0"); 
     101        } 
     102        if (minOrder > markovOrder) { 
     103            throw new InvalidParameterException( 
     104                                                "minOrder must be less than or equal to markovOrder"); 
     105        } 
     106        if (probEscape <= 0.0 || probEscape >= 1.0) { 
     107            throw new InvalidParameterException("probEscape must be in the interval (0,1)"); 
     108        } 
     109        this.probEscape = probEscape; 
     110        this.minOrder = minOrder; 
     111    } 
     112 
     113    /** 
     114     * <p> 
     115     * Sets the escape probability of the model. 
     116     * </p> 
     117     *  
     118     * @param probEscape 
     119     *            new escape probability 
     120     */ 
     121    public void setProbEscape(double probEscape) { 
     122        this.probEscape = probEscape; 
     123    } 
     124 
     125    /** 
     126     * <p> 
     127     * Returns the escape probability of the model. 
     128     * </p> 
     129     *  
     130     * @return escape probability of the model 
     131     */ 
     132    public double getProbEscape() { 
     133        return probEscape; 
     134    } 
     135 
     136    /** 
     137     * <p> 
     138     * Calculates the probability of the next event based on the formula:<br> 
     139     * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n 
     140     * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})<br> 
     141     * P_{MM^i} denotes the probability in an i-th order Markov model. 
     142     * </p> 
     143     *  
     144     * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List, 
     145     *      de.ugoe.cs.quest.eventcore.Event) 
     146     */ 
     147    @Override 
     148    public double getProbability(List<Event> context, Event symbol) { 
     149        if (context == null) { 
     150            throw new InvalidParameterException("context must not be null"); 
     151        } 
     152        if (symbol == null) { 
     153            throw new InvalidParameterException("symbol must not be null"); 
     154        } 
     155        double result = 0.0d; 
     156        double resultCurrentContex = 0.0d; 
     157        double resultShorterContex = 0.0d; 
     158 
     159        List<Event> contextCopy; 
     160        if (context.size() >= trieOrder) { 
     161            contextCopy = 
     162                new LinkedList<Event>(context.subList(context.size() - trieOrder + 1, 
     163                                                      context.size())); 
     164        } 
     165        else { 
     166            contextCopy = new LinkedList<Event>(context); 
     167        } 
     168 
     169        Collection<Event> followers = trie.getFollowingSymbols(contextCopy); // \Sigma' 
     170        int sumCountFollowers = 0; // N(s\sigma') 
     171        for (Event follower : followers) { 
     172            sumCountFollowers += trie.getCount(contextCopy, follower); 
     173        } 
     174 
     175        int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) 
     176        if (sumCountFollowers == 0) { 
     177            resultCurrentContex = 0.0; 
     178        } 
     179        else { 
     180            resultCurrentContex = (double) countSymbol / sumCountFollowers; 
     181        } 
     182        if (contextCopy.size() > minOrder) { 
     183            resultCurrentContex *= (1 - probEscape); 
     184            contextCopy.remove(0); 
     185            if (contextCopy.size() >= minOrder) { 
     186                double probSuffix = getProbability(contextCopy, symbol); 
     187 
     188                if (followers.size() == 0) { 
     189                    resultShorterContex = probSuffix; 
     190                } 
     191                else { 
     192                    resultShorterContex = probEscape * probSuffix; 
     193                } 
     194            } 
     195        } 
     196        result = resultCurrentContex + resultShorterContex; 
     197 
     198        return result; 
     199    } 
    200200} 
Note: See TracChangeset for help on using the changeset viewer.