2013 | OriginalPaper | Buchkapitel
Compact Prediction Tree: A Lossless Model for Accurate Sequence Prediction
verfasst von : Ted Gueniche, Philippe Fournier-Viger, Vincent S. Tseng
Erschienen in: Advanced Data Mining and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 (
C
ompact
P
rediction
T
ree) 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 (
P
rediction by
P
artial
M
atching), DG (
D
ependency
G
raph) 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.