appleyuchi / Decision_Tree_Prune

This repository is targeted at popular pruning implementations(Continuous updating):

ID3 is just manually written code. MEP、EBP、PEP、CVP are operated on the model generated from: Quinlan-C4.5-Release8_and_python_interface_for_EBP/Src/quinlan-src/ which is from[1],the inventer's homepage.

Environment Requirement(Not a must):

Tips:
The command to delete all .pyc files:
find . -name "*.pyc"  | xargs rm -f

Note that :
In C4.5 and C5.0,when your datasets is very very small ,

you'll get very small model,then,

you will NOT get a "Simplified Tree"(pruned model)

from quinlan's implementation.

This means "pruned model"="unpruned model",

when under this case,copy the content of "result/unprune.txt" to "result/prune.txt"please.

----------------REP---Operation method(start)-------------------------------

Running Flows:

1.cd ID3-REP-post_prune-Python-draw

2.python jianzhi.py

----------------REP---Operation method(end)---------------------------------

----------------EBP--Operation method(start)--------------------------------

Ross Quinlan has already implemented EBP with C[1], so the following is just a Python interface.

Running Flows:

put crx.names and crx.data(change "crx" please when you use other datasets) under the path: Quinlan-C4.5-Release8_and_python_interface_for_EBP/Src/quinlan-src/

cd Quinlan-C4.5-Release8_and_python_interface_for_EBP/Src
python shell_execute.py crx > result.txt
python result_get.py(transform C model to Python model)
python predict.py

----------------EBP--Operation method(end)---------------------------------

----------------PEP--Operation method(start)-------------------------------

Running Flows:

Download datasets from[2]

Reorder it with the final column from small to large and get the former 200 items,and save them as abalone_parts.data(this step is just for easy to visualize afterwards)
3.

cp abalone_parts.data abalone.names   /decision_tree/Quinlan-C4.5-Release8_and_python_interface_for_EBP/Src/quinlan-src/
python shell_execute.py abalone > result.txt
python result_get.py(transform C model to Python model)  

get the model from the output of "python result_get.py"
and paste this model into top.py  

cp abalone_parts.data abalone.names decision_tree/PEP-finish/

python top.py

If you do not want to change datasets,
you can skip the former 4 steps and run step 5th only.

----------------PEP--Operation method(end)---------------------------------

----------------MEP--Operation method(start)---------------------------------

Running Flows:

1.cp abalone_parts.data abalone.names   /decision_tree/Quinlan-C4.5-Release8_and_python_interface_for_EBP/Src/quinlan-src/
python shell_execute.py abalone > result.txt
python result_get.py(transform C model to Python model)  

2.get the model from the output of "python result_get.py"
and paste this model into MEP_topmodule_down_to_top.py  

3.python MEP_topmodule_down_to_top.py　

----------------MEP--Operation method(end)---------------------------------

----------------CVP--Operation method(start)---------------------------------

Running Flows:

1.cp abalone_parts.data abalone.names   /decision_tree/Quinlan-C4.5-Release8_and_python_interface_for_EBP/Src/quinlan-src/
python shell_execute.py abalone > result.txt
python result_get.py(transform C model to Python model)  

2.get the model from the output of "python result_get.py"
and paste this model into CVP_top.py 

3.search "critical_value" in CVP_top.py and change it to be what you want.
4.python CVP_top.py

Of course,you can skip the first 3 steps if you just want to see its performance with default datasets(abalone_parts and credit-a)

----------------CVP--Operation method(end)---------------------------------

----------------CCP--Operation method(some relevant information-start)---------------------------------

Attention: Previous Work of CCP on CART From other repositories in Github and Google:

All of above three implementations are stored and annotated in the folder:

"several_wrong_implementations_CCP"

Note1:
This repository's CCP-implementation is performed based on sklearn's CART classification-model.
Here's the relevant issuse of official github of Sklearn.
https://github.com/scikit-learn/scikit-learn/issues/6557
They are trying to prune on sklearn's CART model with Cython(a faster python with C),which is still un-available.My  CCP implementation on sklearn's CART model is pure python.

Note2:
CCP  can also be used on C4.5(Not supported in this github),and the article which use CCP on C4.5 is《Simplifying Decision Trees》part2.1-J.R.Quinlan

----------------CCP--Operation method(some relevant information-end)---------------------------------

----------------CCP--Operation method(start)---------------------------------
Attention again,datasets with unKnown value is NOT supported.

The main flow to implement CCP on sklearn's model is as follows:
1.transform sklearn model to json-model. 
(I'm Not contributor of Sklearn,so the sklearn model can NOT be pruned directly,it need transformation.)
2.perform CCP on json model
3.get the best json-model from Tree Sets in CCP,and synchronized the original sklearn model with the best json-model
(we only synchronize the"Tree shape" between sklearn-model and json-style model,which is very helpful for drawing CCP-pruned json-model with graphviz)


The step to run CCP on sklearn's model is as follows:
1.delete all the files in the folder "visualization"
2.make sure your datasets has no unKnown value,or you need to pre-process it(It is a must).
If you don't pre-process the unKnown value,strange errors will occur.
3.cd decision_tree/sklearn_cart_CCP/sklearnCART2json_CCP/ 
and change the "name_path" and "data_path" in sklearn_CCP_top.py
4.python sklearn_CCP_top.py 
and get the best CCP-json-model and CCP-pruned  precision
5.Enjoy the pictures of all the TreeSets and "final bestTree" in the folder "visualization".

Note:
    1.
    Don't Set "max_depth" too large,
    or you'll need to wait for a very long time,
    if you persist running it with very large "max_depth",then graphviz may NOT be able to draw pictures under the folder "visualization".

    2.
datasets from UCI which have been tested:
credit-a
abalone

----------------CCP--Operation method(end)---------------------------------

-------------------ECP-Operation method(start)-----------------------

Running Flows:

    1.change your datasets path in file sklearn_ECP_TOP.py
    2.set b_SE=True in sklearn_ECP_TOP.py if you want this rule to select the best pruned tree.
    3.python sklearn_ECP_TOP.py in the path decision_tree/sklearn_cart-regression_ECP-finish/
    4.Enjoy the results in the folder＂visualization＂.

    datasets from UCI which have been tested:
    housing(boston)

-------------------ECP-Operation method(end)-----------------------

----------------------------------------

-------------------C5.0-EBP-Operation method(Start)-------------------

Training Flows: C50-EBP-finish/Train/Traing_Method.txt

Validation Flows: C50-EBP-finish/ValidateAndTest/Validation_Testing_Method.txt

The resource of C5.0 is from [4] (For Training) and [5] (For Validation and Testing)

-------------------C5.0-EBP-Operation method(end)-------------------

You may also interested in the inventer、history of Pruning Algorithms,

and you may want to compare the unpruned effects and pruned effects.

I have collected them together[3].

----------------------------Formatting For Kaggle---------------------------------------

Change .csv to .data and .names. See folder: CSV_Formatting

----------------------------Contact me------------------------------------------------

---------------------------update------------------------------------------------

issue 12887 of Sklearn Group fixes issue 6557.

However,R(t) of issue 12887 is different from what is written in[6]

Reference:

[1]C4.5 Package

[2]Abalone Datasets

[3]History of pruning algorithm development and python implementation(finished)

[4]C5.0 Package

[5]See5/C5.0

[6] Breiman L (1984)《 Classification and regression trees》