TY - GEN
T1 - Compact prediction tree
T2 - 9th International Conference on Advanced Data Mining and Applications, ADMA 2013
AU - Gueniche, Ted
AU - Fournier-Viger, Philippe
AU - Tseng, S.
PY - 2013
Y1 - 2013
N2 - Predicting the next item of a sequence over a finite alphabet has important applications in many domains. In this paper, we present a novel prediction model named CPT (Compact Prediction Tree) which losslessly compress the training data so that all relevant information is available for each prediction. Our approach is incremental, offers a low time complexity for its training phase and is easily adaptable for different applications and contexts. We compared the performance of CPT with state of the art techniques, namely PPM (Prediction by Partial Matching), DG (Dependency Graph) and All-K-th-Order Markov. Results show that CPT yield higher accuracy on most datasets (up to 12% more than the second best approach), has better training time than DG and PPM, and is considerably smaller than All-K-th-Order Markov.
AB - Predicting the next item of a sequence over a finite alphabet has important applications in many domains. In this paper, we present a novel prediction model named CPT (Compact Prediction Tree) which losslessly compress the training data so that all relevant information is available for each prediction. Our approach is incremental, offers a low time complexity for its training phase and is easily adaptable for different applications and contexts. We compared the performance of CPT with state of the art techniques, namely PPM (Prediction by Partial Matching), DG (Dependency Graph) and All-K-th-Order Markov. Results show that CPT yield higher accuracy on most datasets (up to 12% more than the second best approach), has better training time than DG and PPM, and is considerably smaller than All-K-th-Order Markov.
KW - accuracy
KW - compression
KW - next item prediction
KW - sequence prediction
UR - http://www.scopus.com/inward/record.url?scp=84893143738&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-53917-6_16
DO - 10.1007/978-3-642-53917-6_16
M3 - Conference contribution
AN - SCOPUS:84893143738
SN - 9783642539169
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 177
EP - 188
BT - Advanced Data Mining and Applications - 9th International Conference, ADMA 2013, Proceedings
Y2 - 14 December 2013 through 16 December 2013
ER -