RF

RF(RandomFroest)

Posted by ZhengYang on 2016-07-12

RF(RandomForest)

CART是分类回归树，是用Gini指数最小化准则进行特征选择的。
RF是一个集成算法，是由多棵CART组成的，而且有重复抽样相同样本量的样本，无重复抽样一部分特征，构成每棵CART的样本。
因为实验需要，用c++实现了一个RF的demo。对比与sklearn上的随机森林，模型效果基本一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include <iostream>
#include <random>
#include <algorithm>  
#include <vector>
#include <set>
#include "stdafx.h"
#include "utils.h"
using namespace std;
int classK = 3; // 共3类
int classList[3] = { 1,3,6 }; // 每类的label
float* pk = new float[classK];
int ATTRS = 19; // 共19个属性
int ROWS = 117;
float** data_X;
float** data_y;
int ntrace = 821;
int nSample = 476;
int SampleRate = 2000;
int headNum = 120;
// 节点
struct Node {
    vector<int> ids;   // 记录该节点的所包含的节点的索引
    vector<int> attrs; // 记录已经使用的属性[0-18]
    int attr;
    float value;
    Node* left;
    Node* right;
};
// 初始化随机 ids，有放回抽样，同原数据集大小
vector<int> ids_init_random() {
    vector<int> vec;
    for (int i = 0; i < ROWS; ++i) {
        vec.push_back(rand() % ROWS);
    }
    return vec;
}
// 初始化随机 attr，无放回抽样，5个
vector<int> attrs_init_random() {
    vector<int> vec;
    int i = 0;
    int tmp = 0;
    bool flag = false; // 是否重复
    while (i<5) {   // 每棵树只选5个属性
        tmp = rand() % ATTRS;
        for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
            if (*it == tmp) {
                flag = true;
                break;
            }
        }
        if (!flag) {
            vec.push_back(tmp);
            ++i;
        }
        flag = false;
    }
    return vec;
}
// 传进来的是索引ids
float gini(vector<int> ids) {
    memset(pk, 0, sizeof(float)*classK);
    // 计算每类的概率
    for (vector<int>::iterator it = ids.begin(); it != ids.end(); it++) {
        for (int k = 0; k < classK; k++) {
            if (data_y[*it][0] == classList[k]) {
                pk[k] = pk[k] + 1;
                break;
            }
        }
    }
    float gini_p = 0;
    for (int k = 0; k < classK; k++) {
        if (ids.size() != 0)
            pk[k] = pk[k] / ids.size();
        gini_p = gini_p + pk[k] * (1 - pk[k]);
    }
    return gini_p;
}
// 尝试将cart树换成id3，但效果一般
//float entropy(vector<int> ids) {
//    memset(pk, 0, sizeof(float)*classK);
//    // 计算每类的概率
//    for (vector<int>::iterator it = ids.begin(); it != ids.end(); it++) {
//        for (int k = 0; k < classK; k++) {
//            if (data_y[*it][0] == classList[k]) {
//                pk[k] = pk[k] + 1;
//                break;
//            }
//        }
//    }
//    float entropy_p = 0;
//    for (int k = 0; k < classK; k++) {
//        if (ids.size() != 0)
//            pk[k] = pk[k] / ids.size();
//        entropy_p = entropy_p - pk[k] * log(pk[k]);
//    }
//    return entropy_p;
//
//}
int cart(Node* root) {
    // 计算该节点的准确率
    memset(pk, 0, sizeof(float)*classK);
    for (vector<int>::iterator it = root->ids.begin(); it != root->ids.end(); it++) {
        for (int k = 0; k < classK; k++) {
            if (data_y[*it][0] == classList[k]) {
                pk[k] = pk[k] + 1;
                break;
            }
        }
    }
    float mostvote = 0;
    int mostid = 0;
    for (int k = 0; k < classK; k++) {
        if (pk[k] > mostvote) {
            mostvote = pk[k];
            mostid = k;
        }
    }
    // 终止条件,少于10个，或者准确率高
    if (mostvote / root->ids.size() > 0.8) {
        root->value = classList[mostid];  // 叶子节点的分类结果，为[1,3,6]
        return 0;
    }
    // 先计算目前数据集的基尼指数
    float gini_p = gini(root->ids);
    // 再计算每个属性，每个分割点的基尼指数，越小越好
    vector<int> ids1;
    vector<int> ids2;
    float gini_p_min = FLT_MAX;  // 目标是取最小的基尼指数
    int gini_p_attr = 1;
    float gini_p_value = 0;
    float gini_tmp = 0;
    bool flag = false; // 该属性是否已经使用过
    for (vector<int>::iterator it_attr = root->attrs.begin(); it_attr!=root->attrs.end(); it_attr++) {
        for (vector<int>::iterator it_value = root->ids.begin(); it_value != root->ids.end(); it_value++) {
            //遍历分割点，然后遍历把元素都放 ids1和ids2 中
            for (vector<int>::iterator it = root->ids.begin(); it != root->ids.end(); it++) {
                if (data_X[*it][*it_attr] <= data_X[*it_value][*it_attr]) {
                    ids1.push_back(*it);
                }
                else {
                    ids2.push_back(*it);
                }
            }
            // 计算gini_p_attr,并找出最优的attr和value
            gini_tmp = gini(ids1)*ids1.size() / root->ids.size() + gini(ids2)*ids2.size() / root->ids.size();
            if (gini_tmp < gini_p_min) {
                gini_p_min = gini_tmp;
                gini_p_attr = *it_attr;
                gini_p_value = data_X[*it_value][*it_attr];
            }
            // 重新清理ids1，ids2，供下次循环使用
            ids1.clear();
            ids2.clear();
        }
    }
    // 将ids根据gini_p_attr和gini_n_value 分成ids1和ids2
    for (vector<int>::iterator it = root->ids.begin(); it != root->ids.end(); it++) {
        if (data_X[*it][gini_p_attr] <= gini_p_value) {
            ids1.push_back(*it);
        }
        else {
            ids2.push_back(*it);
        }
    }
    // 如果其中有一部分非常少，那么直接合并返回
    if (ids2.size() <= 5 || ids1.size() <= 5) {
        root->value = classList[mostid];
        return 0;
    }
    // 建立树节点
    root->attr = gini_p_attr;
    root->value = gini_p_value;
    // 递归建立左子树
    root->left = new Node;
    *root->left = { ids1, root->attrs, 0, 0, NULL, NULL };
    cart(root->left);
  // 递归建立右子树
    root->right = new Node;
    *root->right = { ids2, root->attrs, 0, 0, NULL, NULL };
    cart(root->right);
}
float cart_predict(Node* root, float* predict_X) {
    Node* cur = root;
    while (!(cur->left == NULL && cur->right == NULL)) {
        if (predict_X[cur->attr] <= cur->value) {
            cur = cur->left;
        }
        else {
            cur = cur->right;
        }
    }
    // 重新返回根节点
    //cur = root;
    return cur->value;
}