★ FEATURED ARTICLE #includeiostream#includevector#includemap#includealgorithm#includecmath#includememory#includenumeric// 数据结构定义 // 单个样本特征向量 类别标签整数编码structSample{std::vectordoublefeatures;intlabel;};// 决策树节点structTreeNode{boolis_leaffalse;intfeature_index-1;// 分裂特征索引doublethreshold0.0;// 分裂阈值feature threshold 走左否则走右intleaf_label-1;// 叶节点预测类别std::unique_ptrTreeNodeleft;std::unique_ptrTreeNoderight;};// 决策树分类器 classDecisionTreeClassifier{public:// 超参数对应 fitctree 的 Name-Value 参数intmin_samples_split2;// 最小分裂样本数MinParentSizeintmin_samples_leaf1;// 叶节点最小样本数MinLeafSizeintmax_depth100;// 最大深度doublemin_impurity_decrease0.0;// 最小不纯度下降// 训练voidfit(conststd::vectorstd::vectordoubleX,conststd::vectorinty){class_labels_.clear();label_to_class_.clear();for(intlabel:y){if(label_to_class_.find(label)label_to_class_.end()){label_to_class_[label]class_labels_.size();class_labels_.push_back(label);}}std::vectorSamplesamples(X.size());for(size_t i0;iX.size();i){samples[i].featuresX[i];samples[i].labellabel_to_class_[y[i]];}std::vectorintindices(samples.size());std::iota(indices.begin(),indices.end(),0);root_build_tree(samples,indices,0);}// 预测单个样本intpredict(conststd::vectordoublex)const{returnpredict_node(root_.get(),x);}// 批量预测std::vectorintpredict(conststd::vectorstd::vectordoubleX)const{std::vectorintresults;results.reserve(X.size());for(constautox:X){results.push_back(predict(x));}returnresults;}private:std::unique_ptrTreeNoderoot_;std::vectorintclass_labels_;// 编码 - 原始标签std::mapint,intlabel_to_class_;// 原始标签 - 编码// ---------- Gini 不纯度 ----------doublegini_impurity(conststd::vectorSamplesamples,conststd::vectorintindices)const{if(indices.empty())return0.0;std::mapint,intclass_counts;for(intidx:indices){class_counts[samples[idx].label];}doublegini1.0;doubletotalstatic_castdouble(indices.size());for(constauto[cls,count]:class_counts){doublepcount/total;gini-p*p;}returngini;}// ---------- 叶节点标签多数投票 ----------intmajority_label(conststd::vectorSamplesamples,conststd::vectorintindices)const{std::mapint,intclass_counts;for(intidx:indices){class_counts[samples[idx].label];}intbest_label-1,best_count-1;for(constauto[cls,count]:class_counts){if(countbest_count){best_countcount;best_labelcls;}}returnbest_label;}// ---------- 检查所有样本是否同类 ----------boolis_pure(conststd::vectorSamplesamples,conststd::vectorintindices)const{if(indices.empty())returntrue;intfirstsamples[indices[0]].label;for(intidx:indices){if(samples[idx].label!first)returnfalse;}returntrue;}// ---------- 在候选特征上寻找最佳分裂 ----------structSplitResult{intfeature_index-1;doublethreshold0.0;doublegain0.0;std::vectorintleft_indices;std::vectorintright_indices;boolvalidfalse;};SplitResultfind_best_split(conststd::vectorSamplesamples,conststd::vectorintindices)const{SplitResult best;doubleparent_ginigini_impurity(samples,indices);doubletotalstatic_castdouble(indices.size());intn_featuressamples[0].features.size();for(intfeat0;featn_features;feat){std::vectorstd::pairdouble,intvalues;// (feature_value, sample_idx)values.reserve(indices.size());for(intidx:indices){values.emplace_back(samples[idx].features[feat],idx);}std::sort(values.begin(),values.end(),[](constautoa,constautob){returna.firstb.first;});for(size_t i0;i1values.size();i){doublethreshold(values[i].firstvalues[i1].first)/2.0;if(std::abs(values[i].first-values[i1].first)1e-12)continue;std::vectorintleft_idx,right_idx;for(constautov:values){if(v.firstthreshold)left_idx.push_back(v.second);elseright_idx.push_back(v.second);}if(static_castint(left_idx.size())min_samples_leaf||static_castint(right_idx.size())min_samples_leaf)continue;doubleleft_ginigini_impurity(samples,left_idx);doubleright_ginigini_impurity(samples,right_idx);doubleweighted_gini(left_idx.size()/total)*left_gini(right_idx.size()/total)*right_gini;doublegainparent_gini-weighted_gini;if(gainbest.gain){best.feature_indexfeat;best.thresholdthreshold;best.gaingain;best.left_indicesstd::move(left_idx);best.right_indicesstd::move(right_idx);best.validtrue;}}}returnbest;}// ---------- 递归建树 ----------std::unique_ptrTreeNodebuild_tree(conststd::vectorSamplesamples,conststd::vectorintindices,intdepth){autonodestd::make_uniqueTreeNode();if(depthmax_depth){node-is_leaftrue;node-leaf_labelmajority_label(samples,indices);returnnode;}if(is_pure(samples,indices)){node-is_leaftrue;node-leaf_labelsamples[indices[0]].label;returnnode;}if(static_castint(indices.size())min_samples_split){node-is_leaftrue;node-leaf_labelmajority_label(samples,indices);returnnode;}SplitResult splitfind_best_split(samples,indices);if(!split.valid||split.gainmin_impurity_decrease){node-is_leaftrue;node-leaf_labelmajority_label(samples,indices);returnnode;}node-feature_indexsplit.feature_index;node-thresholdsplit.threshold;node-leftbuild_tree(samples,split.left_indices,depth1);node-rightbuild_tree(samples,split.right_indices,depth1);returnnode;}// ---------- 单节点预测 ----------intpredict_node(constTreeNode*node,conststd::vectordoublex)const{if(node-is_leaf)returnnode-leaf_label;if(x[node-feature_index]node-threshold)returnpredict_node(node-left.get(),x);elsereturnpredict_node(node-right.get(),x);}};// 主函数 intmain(){// 训练数据特征维度 2std::vectorstd::vectordoubleX{{2.0,1.0},{1.5,1.2},{1.8,0.9},{5.0,4.5},{5.5,4.0},{6.0,5.0},{1.0,2.0},{1.2,1.8},{0.8,2.2}};std::vectorinty{0,0,0,1,1,1,0,0,0};// 类别标签DecisionTreeClassifier clf;clf.min_samples_split2;clf.min_samples_leaf1;clf.max_depth10;clf.fit(X,y);// 预测新样本std::vectordoubletest{1.6,1.0};intpredclf.predict(test);std::coutPredicted label: predstd::endl;// 批量预测autopredsclf.predict(X);for(size_t i0;ipreds.size();i){std::coutSample i - preds[i]std::endl;}return0;}
阅读完成 · 觉得有帮助？
