Compact Prediction Tree: A Lossless Model for Accurate Sequence Prediction
Project description
CPT
What is it ?
This project is a cython open-source implementation of the Compact Prediction Tree algorithm using multithreading.
CPT is a sequence prediction model. It is a highly explainable model specialized in predicting the next element of a sequence over a finite alphabet.
This implementation is based on the following research papers:
- http://www.philippe-fournier-viger.com/ADMA2013_Compact_Prediction_trees.pdf
- http://www.philippe-fournier-viger.com/spmf/PAKDD2015_Compact_Prediction_tree+.pdf
Installation
You can simply use pip install cpt
.
Simple example
You can test the model with the following code:
from cpt.cpt import Cpt
model = Cpt()
model.fit([['hello', 'world'],
['hello', 'this', 'is', 'me'],
['hello', 'me']
])
model.predict([['hello'], ['hello', 'this']])
# Output: ['me', 'is']
For an example with the compatibility with sklearn, you should check the documentation.
Features
Train
The model can be trained with the fit
method.
If needed the model can be retrained with the same method. It adds new sequences to the model and do not remove the old ones.
Multithreading
The predictions are launched by default with multithreading with OpenMP.
The predictions can also be launched in a single thread with the option multithread=False
in the predict
method.
You can control the number of threads by setting the following environment variable OMP_NUM_THREADS
.
Pickling
You can pickle the model to save it, and load it later via pickle library.
from cpt.cpt import Cpt
import pickle
model = Cpt()
model.fit([['hello', 'world']])
dumped = pickle.dumps(model)
unpickled_model = pickle.loads(dumped)
print(model == unpickled_model)
Explainability
The CPT class has several methods to explain the predictions.
You can see which elements are considered as noise
(with a low presence in sequences) with model.compute_noisy_items(noise_ratio)
.
You can retrieve trained sequences with model.retrieve_sequence(id)
.
You can find similar sequences with find_similar_sequences(sequence)
.
You can not yet retrieve automatically all similar sequences with the noise reduction technique.
Tuning
CPT has 3 meta parameters that need to be tuned. You can check how to tune them in the documentation. To tune you can use the model_selection
module from sklearn
, you can find an example here on how to.
Benchmark
The benchmark has been made on the FIFA dataset, the data can be found on the SPMF website.
Using multithreading, CPT
was able to perform around 5000 predictions per second.
Without multithreading, CPT
predicted around 1650 sequences per second.
Details on the benchmark can be found here.
Further reading
A study has been made on how to reduce dataset size, and so training / testing time using PageRank on the dataset.
The study has been published in IJIKM review here. An overall performance improvement of 10-40% has been observed with this technique on the prediction time without any accuracy loss.
One of the co-author of CPT
has also published an algorithm subseq
for sequence prediction. An implementation can be found here
Support
If you enjoy the project and wish to support me, a buymeacoffee link is available.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for cpt-1.3.4-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3183e3991a25bc5c4fea0a00024e4a658608dd1f59793d72c9d0477852e046ab |
|
MD5 | 6fd581c829d8f89f6a5f147e42c9fab5 |
|
BLAKE2b-256 | 8656755c8655e9e2fda9ba7b97ed5ab1cb713d621a3c0bdcb0b759fb0e53bc33 |
Hashes for cpt-1.3.4-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7a9fa6667b50c7b639112ef61b2bef625e3957bae95cde6053118c5bd2f53894 |
|
MD5 | eb48947dafedddd4e8527b6d14e5c743 |
|
BLAKE2b-256 | d56501a9d8a5234f705cfdb9d06e7c863bbe0981565c29a04e137f3cf7f86198 |
Hashes for cpt-1.3.4-cp312-cp312-manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4cf4a8e0b06f8a0a1a185e679a7eaf8b5a4740185da3a8ec55f190717ba8502e |
|
MD5 | 642141d128bbe3bf69e4ab89c0a3cb36 |
|
BLAKE2b-256 | 6998a8345b5ae8049e02682540b4e9fa72059196e1fd7d943f35f6afda7702e1 |
Hashes for cpt-1.3.4-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b28fe19bd24ee42b07093c3dfd234911c6134e45dfbcddc17b161d3af70abd12 |
|
MD5 | cf199b4b4faf517f8bf6b2907d53e045 |
|
BLAKE2b-256 | fd59d467d67522bce0024cb3455e7ea3c277bf03093a38c3d67c1e7686764d7d |
Hashes for cpt-1.3.4-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c6f74293ba130e42cebf9433d15322ed6aac3aca091ef7a3628bced615ab8358 |
|
MD5 | 0010f4365bb513788c5ec27d6bb1553b |
|
BLAKE2b-256 | 92360276dfed23f6a9b50d907afa28ada9d97e36fc6808df8d56d43310baa30e |
Hashes for cpt-1.3.4-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 61bba5311f82b39b02677f8469c51b40efb3cfb33f2ad97c8eda7c50a8a66e79 |
|
MD5 | 7ad5628349a8816cbcd82a2368002fcd |
|
BLAKE2b-256 | d6023a11652166c107380826ef6feefb62e74066740cac1c13984daee05265d5 |
Hashes for cpt-1.3.4-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0b15bd534eb2c9c3b75289ef0013bfcdc7c72d7930e328a7b7f75c02ff91d936 |
|
MD5 | e636869c7a714bcd2745450165fa8586 |
|
BLAKE2b-256 | a7023a9c2061fd2f632832bb7160467519387114a2f4b537452cda77cc294e28 |
Hashes for cpt-1.3.4-cp311-cp311-manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 69923347ed83b37fd09890836f74debcd32aee0ad3efcbaf31ac59f95fe61fb3 |
|
MD5 | 26f7b92b5720f3da2ef52fb5e07e8371 |
|
BLAKE2b-256 | 7bb94064765961e64d7137ff2781f4f7ea07019e3e12ebcdee5e57594bb12ac1 |
Hashes for cpt-1.3.4-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b51b5dfffc65eb21f84ccb1826ed6ee03869b2801e24ecedc34c11f5c9a7f123 |
|
MD5 | 806d8df15f684cb1d33bbed36e4d8a3b |
|
BLAKE2b-256 | bbcb3207f8698cf18cb9a3027aef6402762e4ac3ced5990635be2ddbfc2abb48 |
Hashes for cpt-1.3.4-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ab14718208e45f6e7c59d893a6e41b80d0fd29eef202787f7f8a025a2ecd8baa |
|
MD5 | 3090c08fc3a7f093f77d0a770b87b822 |
|
BLAKE2b-256 | 911f392e519f24fa4ea43d008becaabf5820fc97fc38eb5652afd741d3456e67 |
Hashes for cpt-1.3.4-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7a14ca86c4457b8ba278814dba9c8f6c84cd0483347683c56dde9e2ed8c36304 |
|
MD5 | cbeeb4d16299f469658980551054165e |
|
BLAKE2b-256 | d001c8d99c739c636b1ca610d98ffa6a288ce3a04e7e0dbd2a84b37e7c7c3cb7 |
Hashes for cpt-1.3.4-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 98e5717ea2ed96a360b82c19cdcefd7f17afc4816072c7f2ef0f0358172a80da |
|
MD5 | 015308f9bc5435bf062673418d60a3a1 |
|
BLAKE2b-256 | 8a5dedb2e6c3a2ec9e5bf8df16929b45d643d926b2a137708d90be44b2d1e1c0 |
Hashes for cpt-1.3.4-cp310-cp310-manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 145df342309edc6072a3f3f9df401d2bb3eca651227c341f407a9412af841b5e |
|
MD5 | 3674e40bc6ea1846e4e5be3cba7d137c |
|
BLAKE2b-256 | 00a5844ed0508ca7d22064fa03d01d2592aa8861097df1d9f7ff47fe8d96daf9 |
Hashes for cpt-1.3.4-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f7e179e7ca20dbc87a5e311ebdd3f239f490473e390e8f52b559df0765f02f79 |
|
MD5 | 8b738f091cd70d2bf99880bfe0057aae |
|
BLAKE2b-256 | 442e9c86c00680b7c7b3d5af7481636ff8b96e36b32d11d1ec25632ed9a25ffe |
Hashes for cpt-1.3.4-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7bba8cf5fecdd3eb210d5d7f953651d5c0039f23c0e2460ee3c130dd3b278975 |
|
MD5 | 01e1c14f0fbe49ba78e1fcfdc4100f2e |
|
BLAKE2b-256 | 2d44fa9ce830fcb4c0836251afe616ef7a6c29bded671d6d22fc49b709dbd0dc |
Hashes for cpt-1.3.4-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 407e48a256ccc69b6aff08223765b8f408f0f71c7f54622ec393de9880818d98 |
|
MD5 | 4733448d60331a37ccd2caf6e90ad3ec |
|
BLAKE2b-256 | bd292fa21c58f53055a33e493c8d9af976a30b19c49c4b434bf04232420b4d6d |
Hashes for cpt-1.3.4-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e8fef858c4b4a37e3e7e28a32e1219146fae239a2e6a474a6e9317cc3f983915 |
|
MD5 | c437901d4ffe740fb78e1db0530dc8d1 |
|
BLAKE2b-256 | 79e70588c951c64e436be79b8c9cdbe25028dac7be3eae712b5c104b2484e5f7 |
Hashes for cpt-1.3.4-cp39-cp39-manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be312e50712dbda43174b283cf9f285ac489a186f3fea9655d5a9b21295e7176 |
|
MD5 | 5fbd8fd601be71d222e06706c410e899 |
|
BLAKE2b-256 | 5bf3c2093dc8d35d4efdfb730481083c40bf237d6679a0fb7c98527fdedfa1d3 |
Hashes for cpt-1.3.4-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ca4e538a6ddcb1fbb1d28a400d145e581f9bf039ad74bf0696f2d5a03d6e743 |
|
MD5 | d3d874eadc5ae38aac0542d0307f01e6 |
|
BLAKE2b-256 | f0c5588abf01d5c1fb7b6ead2eaa50b1b443b21df177f1f3c696dd694ca1508f |
Hashes for cpt-1.3.4-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e8deb0530090931a5de042a1bb4b2ae6ba977a1fb8840fa92747772db06c19d |
|
MD5 | f736141b4f1c101e724ff137c88dc90e |
|
BLAKE2b-256 | ed55253a5864d044c3b2052351ecfb7a16584c8153aa57e4e6fc1ee762db23e9 |
Hashes for cpt-1.3.4-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 88c65c9be51b604706e4155ba39346e94824b0f560c6bd0bf888f3a57d584346 |
|
MD5 | 2250f3ab6633c486235b60146c1a2dd6 |
|
BLAKE2b-256 | f0c938849473e190d22d4b735964786e50a8b374e04ac8d0c348f552ca550e64 |
Hashes for cpt-1.3.4-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cf7034ba703f3d334d93afa2944ca941fc40a968e1bbb8feaacc02adebc88e51 |
|
MD5 | 21ac9498eb67d6b881bd40979e3c4cdc |
|
BLAKE2b-256 | 82cacc93459c27c6c99d8eef2db6ed0b6fb39eabe900c110dfb6b4545d65e9cd |
Hashes for cpt-1.3.4-cp38-cp38-manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 26e05574fdf0d7169e829c90681107bf54cdffcee2097190c5c2a293f33d2c1f |
|
MD5 | 6058332b610634ba0ecfbc449409da68 |
|
BLAKE2b-256 | a3ee16ddace31b4200d50ad7f4f77fc51f7533015ecf18bf100de594d3a97665 |
Hashes for cpt-1.3.4-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 667538339d040cecdd76906be94b68de75354506002d285a987096ae6e69f1ff |
|
MD5 | f3ade33dc6c8c4b60ec819566830b70f |
|
BLAKE2b-256 | 78b042792ac05e15e9ced39960e7231d80ae0e051ac57af7c9fa492dc334eaef |
Hashes for cpt-1.3.4-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c53ebaff301fb0b8cc7f5854bc552a7d76c4ce56ac661dd8cfc4fc437d22251c |
|
MD5 | 40e5c9c5b137cd7d350c273c51ac6ba1 |
|
BLAKE2b-256 | 7b587af71d3964ae095ffa9f25e085e29052cef0edfd8064a2086aab218c3450 |